Iteration Complexity of Feasible Descent Methods for Convex Optimization

Po-Wei Wang; Chih-Jen Lin

In many machine learning problems such as the dual form of SVM, the objective function to be minimized is convex but not strongly convex. This fact causes difficulties in obtaining the complexity of some commonly used optimization algorithms. In this paper, we proved the global linear convergence on a wide range of algorithms when they are applied to some non-strongly convex problems. In particular, we are the first to prove $O(\log(1/\epsilon))$ time complexity of cyclic coordinate descent methods on dual problems of support vector classification and regression.

Iteration Complexity of Feasible Descent Methods for Convex Optimization

Abstract