Parameter-free Locally Accelerated Conditional Gradients

Abstract

Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time.

References in corpus (9)

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Variance-Reduced and Projection-Free Stochastic Optimization
• On Acceleration with Noise-Corrupted Gradients
• Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
• Blended Conditional Gradients: the unconditioning of conditional gradients
• CINDy: Conditional gradient-based Identification of Non-linear Dynamics -- Noise-robust recovery
• The condition of a function relative to a polytope
• Projection-Free Adaptive Gradients for Large-Scale Optimization
• Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach

Cited by in corpus (2)

• Linear Bandits on Uniformly Convex Sets
• $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles