Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets

Abstract

The Frank-Wolfe method (a.k.a. conditional gradient algorithm) for smooth optimization has regained much interest in recent years in the context of large scale optimization and machine learning. A key advantage of the method is that it avoids projections - the computational bottleneck in many applications - replacing it by a linear optimization step. Despite this advantage, the known convergence rates of the FW method fall behind standard first order methods for most settings of interest. It is an active line of research to derive faster linear optimization-based algorithms for various settings of convex optimization. In this paper we consider the special case of optimization over strongly convex sets, for which we prove that the vanila FW method converges at a rate of $\frac{1}{t^2}$. This gives a quadratic improvement in convergence rate compared to the general case, in which convergence is of the order $\frac{1}{t}$, and known to be tight. We show that various balls induced by ${\ell }_p$ norms, Schatten norms and group norms are strongly convex on one hand and on the other hand, linear optimization over these sets is straightforward and admits a closed-form solution. We further show how several previous fast-rate results for the FW method follow easily from our analysis.

References in corpus (5)

• Generalized power method for sparse principal component analysis
• Large-Scale Convex Minimization with a Low-Rank Constraint
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Projection-free Online Learning
• An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms

Cited by in corpus (39)

• Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees
• A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
• Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls
• One Sample Stochastic Frank-Wolfe
• Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
• Projection-Free Optimization on Uniformly Convex Sets
• Curvature of Feasible Sets in Offline and Online Optimization
• Revisiting Projection-free Online Learning: the Strongly Convex Case
• Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition
• Improved Regret Bounds for Projection-free Bandit Convex Optimization
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators on Domains Given by Linear Minimization Oracles
• Online Learning with Continuous Variations: Dynamic Regret and Reductions
• On the Effectiveness of Richardson Extrapolation in Machine Learning
• Boosting Frank-Wolfe by Chasing Gradients
• Local and Global Uniform Convexity Conditions
• A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
• A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• Distributed Optimization with Projection-free Dynamics
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
• Alternating conditional gradient method for convex feasibility problems
• Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
• How Does Momentum Help Frank Wolfe?
• Non-convex Conditional Gradient Sliding
• Heavy Ball Momentum for Conditional Gradient
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
• Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Projection-Free Algorithms in Statistical Estimation
• Frank-Wolfe variants for minimization of a sum of functions
• Sparse Inverse Problems Over Measures: Equivalence of the Conditional Gradient and Exchange Methods
• Faster Rates for the Frank-Wolfe Algorithm Using Jacobi Polynomials
• Semi-Stochastic Frank-Wolfe Algorithms with Away-Steps for Block-Coordinate Structure Problems
• Fast and Scalable Lasso via Stochastic Frank-Wolfe Methods with a Convergence Guarantee
• Trace-Norm Adversarial Examples
• $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles
• Primal-Dual Block Frank-Wolfe
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets