Research map / Optimization / Nonconvex and smooth optimization
Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Sarah Frank-Wolfe (SARAH-based stochastic FW with loopless full-gradient refresh) and Saga Sarah Frank-Wolfe (adds SAGA-style gradient table to avoid full gradients) for finite-sum constrained optimization, with improved oracle/LMO complexity in convex and non-convex cases.
Problem
Stochastic finite-sum minimization over convex compact constraint sets where projections are expensive, requiring projection-free methods that avoid full gradients and large batches while achieving the best oracle complexity.
Approach
Combine SARAH's recursive gradient estimator with a loopless full-gradient refresh inside Frank-Wolfe, and further replace the refresh with SAGA-style gradient memory so that no full gradients are needed; analysis uses a Lyapunov function that tracks the gradient estimation error alongside the objective gap.
Key results
- Sarah Frank-Wolfe achieves stochastic oracle complexity Õ(n + sqrt(n)·L̃D²/ε) in the convex case with batch size 1, the best among stochastic projection-free methods per the authors' table.
- Saga Sarah Frank-Wolfe removes full gradient computations entirely while retaining the same convex and non-convex guarantees as the SARAH-based method.
- Experiments on l1-ball constrained logistic regression and nonlinear least squares over LibSVM datasets show the proposed methods are superior or comparable to baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the SARAH estimator with the SAGA-SARAH estimator to avoid full-gradient computations | Sarah Frank-Wolfe · Convex and non-convex stochastic finite-sum minimization | Theoretical convergence guarantees | No clear effect |
| Use small batches instead of large batches | Sarah Frank-Wolfe · Non-convex stochastic finite-sum minimization | SFO complexity: \mathcal{O}\left( n + \frac{\sqrt{n}}{\varepsilon^2}\right) -> \mathcal{O}\left( \frac{n}{\varepsilon^2}\right) | Hurt |
| Use small batches instead of large batches | Sarah Frank-Wolfe · Non-convex stochastic finite-sum minimization | LMO complexity: \mathcal{O}\left( \frac{1}{\varepsilon^2}\right) -> \mathcal{O}\left( \frac{n}{\varepsilon^2}\right) | Hurt |
| Increase batch size from b=1 to b=\sqrt{n} | Sarah Frank-Wolfe · Convex stochastic finite-sum minimization | LMO complexity: \mathcal{\tilde O} \left(n + \tfrac{\sqrt{n} \tilde L D^2}{\varepsilon}\right) -> \mathcal{\tilde O} \left(\sqrt{n} + \t | Helped |
| Increase batch size from b=1 to b=\sqrt{n} | Sarah Frank-Wolfe · Non-convex stochastic finite-sum minimization | LMO complexity: \mathcal{O}\left( \tfrac{n (\tilde L^2 + L^2) D^4 + (h^0)^2}{\varepsilon^2}\right) -> \mathcal{O}\left( \tfrac{ (\tilde | Helped |
Surprising findings
- The authors report that the SAGA-related Frank-Wolfe result in a prior paper appears to contain an error and they give a corrected, different complexity.
Limitations
- Non-convex LMO complexity and convex SFO complexity have a gap to lower bounds; the authors note these are not known to be optimal.
- Saga variant requires extra O(nd) memory for the gradient table.
- Best non-convex oracle complexity requires large batches; small batches give worse non-convex estimates.
Experimental setup
Datasets: LibSVM datasets
Benchmarks: LibSVM logistic regression LibSVM nonlinear least squares
Metrics: relative suboptimality vs. number of full gradient computati
Baselines: SVRF SFW SPIDER-FW Stochastic Conditional Gradient (SCG) Frank-Wolfe (deterministic) Stochastic Frank-Wolfe variants with SAGA/SPIDER
Builds on: Frank-Wolfe SARAH SAGA SVRG loopless SVRG (L-SVRG)
Closest papers by meaning
- Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization (ICML 2020 · similarity 0.95)
- Variance-Reduced and Projection-Free Stochastic Optimization (ICML 2016 · similarity 0.93)
- Stochastic Frank-Wolfe for Composite Convex Minimization (NeurIPS 2019 · similarity 0.92)
- Can Stochastic Zeroth-Order Frank-Wolfe Method Converge Faster for Non-Convex Problems? (ICML 2020 · similarity 0.91)
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noises (ICML 2026 · similarity 0.90)
- Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.