Convergence Rate of Frank-Wolfe for Non-Convex Objectives
read the original abstract
We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of $O(1/\sqrt{t})$ on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gradient methods (though on slightly different measures of stationarity).
This paper has not been read by Pith yet.
Forward citations
Cited by 9 Pith papers
-
Fused Gromov-Wasserstein Distance with Feature Selection
Fused Gromov-Wasserstein distances are extended with feature selection via Lasso/Ridge regularization or simplex-constrained weights, yielding theoretical bounds, metric properties, and an alternating minimization algorithm.
-
Accelerating LMO-Based Optimization via Implicit Gradient Transport
LMO-IGT achieves O(ε^{-3.5}) iteration complexity for stochastic LMO optimization via implicit gradient transport with a single gradient per step and introduces the regularized support function as a unified stationari...
-
Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization
An approximate IPTR framework for linearly constrained optimization uses low-rank projector updates to cut per-iteration cost while preserving feasibility and convergence guarantees, with experiments showing 2.48x speedup.
-
Competitive Algorithms for Online Budget-Constrained Continuous DR-Submodular Problems
A primal-dual Generalized Sequential algorithm achieves the first competitive ratio bound for online monotone DR-submodular maximization subject to linear packing constraints, matching the tight bound known for linear...
-
BLADE: Scalable Bi-level Adaptive Data Selection for LLM Training
BLADE converts influence-based bi-level data selection into a Hessian-free penalized objective with a dynamic reference model, proves first-order convergence, and reports better performance than prior methods on LLM training.
-
Conformal Reliability: A New Evaluation Metric for Conditional Generation
Introduces Conformal ReLiability (CReL) framework to compute a conformal-prediction-based reliability score measuring worst-case performance in prediction sets for conditional generative models.
-
Efficient Test-Time Finetuning of LLMs via Convex Reconstruction and Gradient Caching
HullFT performs test-time finetuning by sparse convex reconstruction of query embeddings followed by gradient caching on repeated examples, yielding better quality-efficiency tradeoffs than prior TTFT methods.
-
Model Merging: Foundations and Algorithms
New cycle-consistent optimization, task vector theory, singular vector decompositions, adaptive routing, and efficient evolutionary search provide foundations for merging neural network weights across tasks.
-
Gradient projection and conditional gradient methods for constrained nonconvex minimization
Proves global linear convergence of a gradient projection method on manifolds via the Lezanski-Polyak-Lojasiewicz condition and identifies conditions for linear-rate global convergence of the full-step conditional gra...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.