Research map / Learning theory and algorithms / Combinatorial and search optimization
Secant Line Search 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.
Proposes Secant Line Search (SLS), a step-size rule for Frank-Wolfe algorithms that solves the line search root-finding problem with the secant method, giving line-search-quality steps at low cost.
Problem
Choosing step sizes for Frank-Wolfe algorithms: exact/full line search is effective but costly, while cheap rules (open-loop, short-step, adaptive) either need Lipschitz constants or lose adaptivity; existing adaptive rules from unconstrained optimization do not carry over to FW.
Approach
Apply the secant method to the one-dimensional optimality condition of the FW line search, using only directional derivative (gradient) evaluations, with iterates clipped to [0, gamma_max]; the bounded interval guarantees convergence under mild conditions, and for quadratics it converges in one iteration.
Key results
- SLS is the fastest on several classes, e.g., Port solved in 0.5 s vs 4.6 s for adaptive and Spec 34.5 s vs 41.1 s, and Nuclear 204.6 s vs 600.6 s for adaptive.
- Average secant iterations per line search is around 1.5 on solved instances, and SLS needs at most one iteration on most quadratic problems.
- On random line-search instances, the secant method was 3-4x faster than Newton's method (quadratic 4.15x, arbitrary 3.31x).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Secant instead of Adaptive step size | Blended pairwise FW · Birkhoff | time (s): 427.6 vs 614.6 | Hurt |
| Use Secant instead of Backtracking step size | Blended pairwise FW · Birkhoff | time (s): 427.6 vs 248.5 | Hurt |
| Use Secant instead of Adaptive step size | Blended pairwise FW · Ill | time (s): 15.3 vs 15.9 | Helped |
| Use Secant instead of Backtracking step size | Blended pairwise FW · Ill | time (s): 15.3 vs 13.9 | Hurt |
| Use Secant instead of Adaptive step size | Blended pairwise FW · Nuclear | time (s): 204.6 vs 600.6 | Helped |
| Use Secant instead of Backtracking step size | Blended pairwise FW · Nuclear | time (s): 204.6 vs 3600.0 | Helped |
| Use Secant instead of the compared step sizes | Blended pairwise FW · OA | time (s): 475.7 vs 3600.0 | Helped |
| Use Secant instead of Adaptive step size | Blended pairwise FW · OD | time (s): 199.2 vs 252.0 | Helped |
| Use Secant instead of Backtracking step size | Blended pairwise FW · OD | time (s): 199.2 vs 158.8 | Hurt |
| Use Secant instead of Adaptive step size | Blended pairwise FW · Port | time (s): 0.5 vs 4.6 | Helped |
| Use Secant instead of Adaptive step size | Blended pairwise FW · QuadProb | time (s): 340.7 vs 355.7 | Helped |
| Use Secant instead of Adaptive step size | Blended pairwise FW · Spec | time (s): 34.5 vs 41.1 | Helped |
Surprising findings
- Secant method beat Brent's method in the authors' tests, despite Brent's higher order of convergence.
- Backtracking line search, which is theoretically equivalent, stalls on the nuclear norm instance while SLS does not.
Limitations
- Secant method is not globally convergent in general; convergence needs strict convexity along the line and a fallback (e.g., backtracking) is suggested.
- Numerical instability on A-optimal and nuclear norm instances with flat directions leads to higher iteration counts.
- Not systematically the fastest; agnostic and other rules win on some instance classes.
Experimental setup
Datasets: Optimal design of experiments (A- and D-criterion) instances Portfolio optimization instances Synthetic quadratics on simplex Birkhoff polytope quadratics Spectraplex and nuclear norm ball matrix completion instances
Benchmarks: Optimal design (OA, OD) Portfolio (Port) Ill-conditioned quadratics (Ill) QuadProb Birkhoff Spec Nuclear
Metrics: wall-clock time FW iterations dual gap average secant iterations per line search
Baselines: Adaptive line search (Pedregosa et al., 2020) Agnostic open-loop step size Backtracking line search Golden-ratio line search Monotonic step size
Builds on: Frank-Wolfe Barzilai-Borwein step size adaptive step size for Frank-Wolfe (Pedregosa et al., 2020) blended pairwise conditional gradients monotonic step size for generalized self-concordant functions
Closest papers by meaning
- Beyond Short Steps in Frank-Wolfe Algorithms (ICLR 2026 · similarity 0.87)
- Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.84)
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features (ICML 2024 · similarity 0.84)
- Efficient Quadratic Corrections for Frank-Wolfe Algorithms (NeurIPS 2025 · similarity 0.84)
- Frank-Wolfe Beyond 1/t Convergence (NeurIPS 2026 · similarity 0.83)
- Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search (NeurIPS 2024 · similarity 0.83)
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.