Optimization Online


Conditional Gradient Sliding for Convex Optimization

Guanghui Lan (glan***at***ise.ufl.edu)
Yi Zhou (yizhou***at***ufl.edu)

Abstract: In this paper, we present a new conditional gradient type method for convex optimization by utilizing a linear optimization (LO) oracle to minimize a series of linear functions over the feasible set. Different from the classic conditional gradient method, the conditional gradient sliding (CGS) algorithm developed herein can skip the computation of gradients from time to time, and as a result, can achieve the optimal complexity bounds in terms of not only the number of calls to the LO oracle, but also the number of gradient evaluations. More specifically, we show that the CGS method requires ${\cal O}(1/\sqrt{\epsilon})$ and ${\cal O}(\log (1/\epsilon))$ gradient evaluations, respectively, for solving smooth and strongly convex problems, while still maintaining the optimal ${\cal O}(1/\epsilon)$ bound on the number of calls to the LO oracle. We also develop variants of the CGS method which can achieve the optimal complexity bounds for solving stochastic optimization problems and an important class of saddle point optimization problems. To the best of our knowledge, this is the first time that these types of projection-free optimal first-order methods have been developed in the literature. Some preliminary numerical results have also been provided to demonstrate the advantages of the CGS method.

Keywords: convex programming, complexity, conditional gradient method, Frank-Wolfe method, Nesterov's method

Category 1: Convex and Nonsmooth Optimization

Citation: Technical Report, Department of Industrial and Systems Engineering, University of Florida.

Download: [PDF]

Entry Submitted: 10/16/2014
Entry Accepted: 10/16/2014
Entry Last Modified: 10/17/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society