Research map / Optimization / Nonconvex and smooth optimization
Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Assume strict complementarity for Frank-Wolfe with away-steps and line-search | Frank-Wolfe with away-steps and line-search · Convex minimization over a polytope with quadratic growth | linear convergence rate: exp(-Θ(t/d)) -> exp(-Θ(t/dim F*)) | Helped |
| Require strict complementarity and bounded gradient perturbation | Optimal face under a perturbed objective · Convex optimization over a polytope | preservation of the optimal face: ν < δ/[D(1 + 2β/α)] | Helped |
| Restrict the optimal solution to a vertex while allowing arbitrary Frank-Wolfe-type methods | Frank-Wolfe-type methods initialized at a standard basis vector · Down-closed unit simplex S↓_d | iterations to approximation error lower than 1/d: Ω(d) | Hurt |
| Increase dimension from 400 to 600 in the sparse-recovery experiment | Least-squares recovery · Unit simplex sparse-vector recovery | average strict complementarity parameter δ: 0.8594 -> 0.5090 | Mixed |
| Increase dimension from 600 to 1000 in the sparse-recovery experiment | Least-squares recovery · Unit simplex sparse-vector recovery | average strict complementarity parameter δ: 0.5090 -> 0.4505 | No clear effect |
| Increase dimension from 1000 to 1200 in the sparse-recovery experiment | Least-squares recovery · Unit simplex sparse-vector recovery | average strict complementarity parameter δ: 0.4505 -> 0.5176 | Mixed |
Closest papers by meaning
- Blended Conditonal Gradients (ICML 2019 · similarity 0.93)
- Decomposition-Invariant Conditional Gradient for General Polytopes with Line Search (NeurIPS 2017 · similarity 0.91)
- Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (NeurIPS 2016 · similarity 0.91)
- Frank-Wolfe Beyond 1/t Convergence (NeurIPS 2026 · similarity 0.89)
- Efficient Quadratic Corrections for Frank-Wolfe Algorithms (NeurIPS 2025 · similarity 0.89)
- 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.