math.OCNov 4, 2025

Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity

Authors: Dan Garber

Abstract

We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) matrix domains given by the spectrahedron and nuclear-norm balls. A key technical ingredient is a complementarity condition that captures solution sparsity---face dimension for polytopes and rank for matrices. We present two algorithms: (1) a purely linear optimization oracle (LOO) method for polytopes that has optimal worst-case first-order (FO) oracle complexity and, aside of a finite \emph{burn-in} phase and up to a logarithmic factor, has LOO complexity that scales with r/εr/\sqrtε, where εε is the target accuracy and rr is the solution sparsity (independently of the ambient dimension), and (2) a hybrid scheme that combines FW with a sparse projection oracle (e.g., low-rank SVDs for matrix domains with low-rank solutions), which also has optimal FO oracle complexity, and after a finite burn-in phase, only requires O(1/ε)O(1/\sqrtε) sparse projections and LOO calls (independently of both the ambient dimension and the sparsity level of optimal solutions). Our results close a gap on how to accelerate recent advancements in linearly-converging FW algorithms for strongly convex optimization, without paying the price of the dimension.

Explore similar work

CardsList
May 1, 2026math.OC

Randomized Subspace Nesterov Accelerated Gradient

Randomized-subspace methods reduce the cost of first-order optimization by using only low-dimensional projected-gradient information, a feature that is attractive in forward-mode automatic differentiation and communication-limited settings. While Nesterov acceleration is well understood for full-gradient and coordinate-based methods, obtaining accelerated methods for general subspace sketches that use only projected-gradient information and can improve over full-dimensional Nesterov acceleration in oracle complexity is technically nontrivial. We develop randomized-subspace Nesterov accelerated gradient methods for smooth convex and smooth strongly convex optimization under matrix smoothness and generic sketch moment assumptions. The key technical ingredient is a three-sequence formulation tailored to matrix smoothness, which recovers the corresponding classical Nesterov methods in the full-dimensional case. The resulting theory establishes accelerated oracle-complexity guarantees and makes explicit how matrix smoothness and the sketch distribution enter the complexity. It also provides a unified basis for comparing sketch families and identifying when randomized-subspace acceleration improves over full-dimensional Nesterov acceleration in oracle complexity.
Gaku Omiya, Pierre-Louis Poirion, Akiko Takeda
NesterovAlternating Direction Method Of MultiplierNonconvex
AskPDF
May 4, 2026math.OC

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with \tilde{\mkern1mu O}(ε^{-5/3}) Global Rate

We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve O(ε−5/3log⁡(1/ε))O(ε^{-5/3}\log(1/ε)) oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.
Sichao Xiong, Sadok Jerad, Coralia Cartis
Convex OptimizationZeroth-Order OptimizationSpectral PreconditioningOptimal Sample Complexity
AskPDF
Oct 2, 2025math.OC

Smooth Quasar-Convex Optimization with Constraints

Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current nearly optimal algorithms work only in affine spaces due to the loss of one degree of freedom when working with general convex constraints. Obtaining an accelerated algorithm that makes nearly optimal O~(1/(γε))\widetilde{O}(1/(γ\sqrt{\varepsilon})) first-order queries to a γγ-quasar convex smooth function \emph{with constraints} was independently asked as an open problem in Martínez-Rubio (2022); Lezane, Langer, and Koolen (2024). In this work, we solve this question by designing an inexact accelerated proximal point algorithm that we implement using a first-order method achieving the aforementioned rate and, as a consequence, we improve the complexity of the accelerated geodesically Riemannian optimization solution in Martínez-Rubio (2022). We also analyze projected gradient descent and Frank-Wolfe algorithms in this constrained quasar-convex setting. To the best of our knowledge, our work provides the first analyses of first-order methods for quasar-convex smooth functions with general convex constraints.
David Martínez-Rubio
NonconvexConvex OptimizationRiemannian OptimizationSample Complexity
AskPDF