Research map / Optimization / Nonconvex and smooth optimization
Efficient Quadratic Corrections for Frank-Wolfe Algorithms
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.
Introduces Corrective Frank-Wolfe (CFW), a framework of active-set corrective steps, and two quadratic correction steps (QC-LP, QC-MNP) that accelerate FW variants on quadratic objectives and improve SCG and SOCGS.
Problem
Fully-corrective Frank-Wolfe is computationally expensive because minimizing a quadratic over conv(active set) is as hard as the original problem; prior corrective variants lack a unified framework and fast corrections for quadratic objectives.
Approach
A general corrective FW framework whose corrective steps only need a descent or drop criterion, plus two quadratic corrections that relax the FCFW subproblem to the affine hull of the active set, solved via an LP (QC-LP, enforcing nonnegativity) or a linear system with an MNP-style ratio test (QC-MNP), with a hybrid with BPCG local pairwise steps.
Key results
- QC-LP and QC-MNP substantially accelerate convergence over FW, AFW, PFW and BPCG on K-sparse regression (n=500, m=10000) for K in {5,20}.
- On entanglement detection, QC-MNP shows drastic initial acceleration and solves to optimality in a fraction of the iterations and time of baselines.
- SCG with a step size 2/(sqrt(t+2) ln(t+2)) achieves an O(1/sqrt(t)) rate, improving on the original O(log t/sqrt(t)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply QC-LP or QC-MNP corrections to BPCG | Frank-Wolfe methods on K-Sparse regression · K-Sparse regression (K=5,20) | iterations to optimality | Helped |
| Use QC-MNP corrections | Frank-Wolfe methods for entanglement detection · Entanglement detection (a=0.25, 0.5) | iterations and time to optimality | Helped |
| Use QC-LP corrections | Frank-Wolfe methods for entanglement detection · Entanglement detection (a=0.25, 0.5) | trajectory | No clear effect |
| Use QC-MNP or QC-LP corrections | SCG for projection onto the Birkhoff polytope and shifted ℓ2 ball · Birkhoff polytope and shifted ℓ2 ball projection (n=300,500) | convergence | Mixed |
| Use the FW variant from the comparison instead of quadratic corrections | SCG for projection onto the Birkhoff polytope and shifted ℓ2 ball · Birkhoff polytope and shifted ℓ2 ball projection (n=300,500) | convergence | Hurt |
| Use QC-MNP or QC-LP instead of BPCG for the inner step | SOCGS logistic regression · Logistic regression on ℓ1 ball (gisette; k=50,200) | primal value and FW gap | Helped |
| Increase the number of inner iterations | SOCGS with quadratic corrections · Logistic regression on ℓ1 ball (gisette; k=50,200) | acceleration over BPCG | Hurt |
| Use QC-MNP rather than QC-LP | SOCGS logistic regression inner step · Logistic regression on ℓ1 ball (gisette; k=50,200) | acceleration | Helped |
| Use QC-MNP rather than QC-LP | SOCGS logistic regression inner step · Logistic regression on ℓ1 ball (gisette; k=50,200) | wall-clock time | Hurt |
| Use FW or PFW instead of the other tested methods | Frank-Wolfe methods for entanglement detection · Entanglement detection (a=0.25, 0.5) | time | Hurt |
Surprising findings
- The LP in QC-LP is rarely feasible on entanglement detection, so it mostly falls back to pairwise steps and behaves similarly to BPCG.
- Both QC methods hit numerical precision limits on the Birkhoff projection instances and would need adjusted tolerances for longer runs.
Limitations
- Quadratic corrections are only defined for quadratic objectives; general convex objectives rely on other steps.
- QC-LP is often infeasible in practice, reducing benefit to fallback pairwise steps.
- Numerical precision limits on some instances (Birkhoff projection).
Experimental setup
Datasets: gisette
Benchmarks: K-sparse polytope regression entanglement detection 3x3 states Birkhoff polytope projection with shifted l2 ball logistic regression over l1 ball (gisette)
Metrics: primal gap iterations wall-clock time FW gap
Baselines: Frank-Wolfe Away-step Frank-Wolfe Pairwise Frank-Wolfe BPCG FCFW SCG original FW variant
Builds on: Blended Conditional Gradients Blended Pairwise Conditional Gradients Fully-Corrective Frank-Wolfe Minimum-Norm Point algorithm Split Conditional Gradient
Closest papers by meaning
- Beyond Short Steps in Frank-Wolfe Algorithms (ICLR 2026 · similarity 0.90)
- Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence (ICML 2020 · similarity 0.89)
- Fast Frank–Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions (ICLR 2026 · similarity 0.89)
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features (ICML 2024 · similarity 0.87)
- Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.87)
- Frank-Wolfe Beyond 1/t Convergence (NeurIPS 2026 · similarity 0.86)
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.