Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity Article Swipe

MAKE IMPACT

Garber, Dan · YOU? · · 2025 · Open Access ·

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 the unit nuclear-norm ball. 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/\sqrtε$, where $ε$ is the target accuracy and $r$ is the solution sparsity $r$ (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/\sqrtε)$ sparse projections and LOO calls (independently of both the ambient dimension and the rank 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.

Type

article

Landing Page

http://arxiv.org/abs/2511.02821

PDF

https://arxiv.org/pdf/2511.02821

OA Status

green

OpenAlex ID

https://openalex.org/W7104183390

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7104183390

Canonical identifier for this work in OpenAlex

Title

Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity

Work title

Type

article

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-11-04

Full publication date if available

Authors

Garber, Dan

List of authors in order

Landing page

https://arxiv.org/abs/2511.02821

Publisher landing page

PDF URL

https://arxiv.org/pdf/2511.02821

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2511.02821

Direct OA link when available

Concepts

Mathematics, Polytope, Dimension (graph theory), Convex optimization, Oracle, Logarithm, Matrix (chemical analysis), Mathematical optimization, Permutation matrix, Minification, Regular polygon, Rank (graph theory), Projection (relational algebra), Complementarity theory, Weighting, Linear complementarity problem, Low-rank approximation, Lasso (programming language), Combinatorics, Compressed sensing, Algorithm, Linear matrix inequality, Linear programming, Optimization problem, Convex function, Matrix completion, Sparse matrix, Block matrix, Computational complexity theory, Focus (optics), Estimator, Complementarity (molecular biology)

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload