Secant Line Search for Frank-Wolfe Algorithms

David Mart\'inez-Rubio; Deborah Hendrych; Mathieu Besan\c{c}on; Sebastian Pokutta

REVIEW 3 major objections 6 minor 17 references

Secant Line Search for Frank-Wolfe Algorithms

T0 review · 3 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A secant-method step-size rule gives Frank-Wolfe algorithms exact-line-search performance at low cost.

desk verdict Practical and well-tested idea, but Theorem 3.1 is false as stated: the clipping bug in Algorithm 2 can make the inner loop diverge, and the curvature assumption of Lemma 2.1 is not implied by strict convexity. read the letter →

arxiv 2501.18775 v2 pith:IK55JQ7D submitted 2025-01-30 math.OC

Deborah Hendrych , Mathieu Besançon , David Martínez-Rubio , Sebastian Pokutta This is my paper · ORCID

classification math.OC MSC 90C2590C3065K05

keywords secantlinesearchFrank-Wolfestep-sizestrategyconditionalgradientsconstrainedconvexoptimizationlocalsmoothnessglobalconvergence

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces Secant Line Search (SLS), a step-size rule for Frank-Wolfe algorithms that solves the one-dimensional line search problem by finding the root of the directional derivative with the secant method. The central claim is that SLS is as effective as an exact line search, matches the local-smoothness adaptivity of backtracking methods, and needs only a handful of gradient evaluations per line search, often one for quadratic objectives. This matters because the cost of line search usually eats into the effective convergence rate of Frank-Wolfe; a cheap, adaptive, and reliable step choice makes the whole algorithm faster in wall-clock time without changing its theoretical guarantees. The central theoretical result, Theorem 3.1, states that on a strictly convex smooth objective over a compact convex set, Frank-Wolfe with SLS initialized at $\gamma_0=0$ and $\gamma_1=\rho$ converges at its optimal rate, and every SLS call converges to the line-search minimizer.

What carries the argument

The working object is the directional derivative $\varphi(\gamma)=\langle\nabla f(\mathbf{x}_t-\gamma\mathbf{d}_t),\mathbf{d}_t\rangle$ along the Frank-Wolfe direction, whose zero is the optimal step size. SLS updates $\gamma_{n+1}=\gamma_n-\varphi(\gamma_n)(\gamma_n-\gamma_{n-1})/(\varphi(\gamma_n)-\varphi(\gamma_{n-1}))$, clipping to $[0,\gamma_{\max}]$. The load-bearing lemma, Lemma 2.1, guarantees monotone convergence to the root when $|\varphi'|$ strictly increases with distance from the root, a condition the proof of Theorem 3.1 derives from strict convexity of $f$; the paper also notes that the secant method converges superlinearly, with order $(1+\sqrt5)/2\approx1.618$, for simple roots, and in one iteration for quadratics.

What would settle it

Run the SLS loop on a strictly convex smooth function chosen so that $\varphi(\gamma)$ has a root but $|\varphi'(\gamma)|$ is not increasing in distance from it, with $\gamma_0=0$ and a tiny $\gamma_1$; if the secant iterates converge to a different point, oscillate, or leave the interval, Theorem 3.1's universality claim fails. A concrete candidate is a one-dimensional strictly convex function with an oscillating third derivative along the search direction, and the functions used in the paper's portfolio or optimal-design instances are natural places to look.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is that the classical secant method, usually only locally convergent, becomes globally convergent when used as a line search inside Frank-Wolfe, because the feasible step is confined to $[0,\gamma_{\max}]$ and the root of the directional derivative is bracketed by the geometry of the algorithm. Theorem 3.1 asserts that for strictly convex smooth $f$ and compact convex $X$, the Frank-Wolfe iterates with SLS behave exactly as if an exact line search were used (up to a tolerance $\epsilon$), and each inner secant loop converges.

Load-bearing premise

The load-bearing premise is that along each search direction the absolute slope of the directional derivative increases with distance from the optimal step and that the two starting guesses, $\gamma_0=0$ and $\gamma_1=\rho$, lie on the same side of it; strict convexity alone does not force this, and the required size of $\rho$ is left unspecified.

Editorial extensions

If this is right

Any Frank-Wolfe variant that uses a line search can substitute SLS without changing its convergence rate, including away-step, pairwise, and blended pairwise conditional gradients.
For convex quadratic objectives, each SLS call converges in a single iteration, making SLS comparable in cost to the standard short-step rule while requiring no Lipschitz constant and exploiting local smoothness.
The warm-started version of SLS reuses the previous optimal step, further cutting inner iterations to around one on average in the reported experiments.
On generalized self-concordant objectives, the paper expects superlinear convergence of the inner secant iterations whenever the relevant third derivative is nonzero, giving high-precision step sizes in very few evaluations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same bracketing argument might transfer SLS to other constrained descent methods whose steps live in a bounded interval and whose update direction is a feasible descent direction; the paper itself only claims this for Frank-Wolfe variants.
A quantitative bound on "$\rho$ small" would turn Theorem 3.1 into a checkable initialization rule; the paper leaves the perturbation unspecified.
The curvature-growth condition in Lemma 2.1 may hold for broader function classes than strict convexity; if verified, SLS would apply beyond smooth convex optimization.
SLS's low inner-iteration count suggests it could be paired with inexact linear oracles, where the cost of solving the direction subproblem dominates and the line search becomes nearly free.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The useful part of this paper is real: secant line search for Frank-Wolfe is a neat practical idea, and the experimental study is among the more careful I have seen. Warm-starting, one gradient evaluation per inner iteration, and the observation that quadratics converge in one secant step all make this an attractive default step-size choice in practice. The experiments cover sensible problem classes and the code is in FrankWolfe.jl, so a practitioner can take this and run with it. Credit where due: the bounded-interval structure of Frank-Wolfe is exploited in a way that is new, and the idea is clearly worth trying.

But the theory overreaches badly. Theorem 3.1 says every SLS call converges, and the proof just says the assumptions of Lemma 2.1 are satisfied. They are not. Strict convexity of f makes φ(γ) strictly increasing, but Lemma 2.1 needs |φ'(γ)| to increase as you move away from the root — a curvature-growth condition that f(x)=x^4 already violates. On top of that, Algorithm 2 clips the secant iterate to [0,γmax] and still terminates only when |φ|<ε. If the unconstrained line-search minimizer lies beyond γmax, the constrained optimum is on the boundary, φ does not vanish there, and the loop never terminates. The stress-test example min_{x∈[0,1]}(x-10)^2 is exactly right: the first secant step finds the root at 10, clips to 1, φ(1)=18, and the loop repeats forever. The authors are aware something can go wrong — Remark 4.1 suggests a backtracking fallback — but Theorem 3.1 is stated unconditionally. The appendix's inexact line search analysis is also informal, though that is a secondary issue.

Who is this for? Someone who wants a cheap, adaptive step size for FW in practice and is prepared to test it. The empirical evidence suggests SLS performs well. But the paper's headline theoretical guarantee is not a guarantee; it is a conjecture with a broken proof. The fix is feasible: add the curvature condition, and change the stopping rule so clipping at a boundary terminates and returns that boundary step. As written, I would not cite the theorem, though I would cite the empirical strategy.

If this came to me as an editor, I would send it to a referee. The practical contribution is solid and the theoretical flaw is fixable; it deserves referee time rather than a desk reject.

Referee Report

3 major / 6 minor

Summary. The paper introduces Secant Line Search (SLS), a step-size rule for Frank-Wolfe (FW) algorithms that applies the secant method to the scalar equation φ(γ) = ⟨∇f(x_t − γd_t), d_t⟩ = 0 arising from exact line search, with iterates clipped to the interval [0, γ_max]. The main theoretical result, Theorem 3.1, claims that for strictly convex and smooth f over a compact convex set, every SLS inner call converges and the FW algorithm inherits its exact-line-search convergence rate. The supporting analysis consists of Lemma 2.1 (monotone convergence of the unclipped secant method under a curvature-growth condition), a local superlinear convergence discussion, an informal inexact-line-search rate appendix, and an extensive numerical study over quadratic, OED, portfolio, and matrix optimization instances implemented in FrankWolfe.jl.

Significance. The proposed strategy is well motivated: if the convergence guarantee were correct, SLS would provide a cheap, adaptive alternative to exact line search that often needs only one or two inner gradient evaluations, and the experimental section is a real asset. The paper ships reproducible experiments in an established open-source package, compares against several standard step-size rules, and reports competitive wall-clock performance on most problem classes. The standalone Lemma 2.1 is essentially correct under its stated curvature-growth hypothesis. However, the central claim linking SLS to FW is not established: Theorem 3.1's proof does not verify the lemma's hypothesis, and Algorithm 2, as written, can fail to terminate on simple instances where the unconstrained line-search root lies outside the feasible interval. Since the paper's headline contribution is precisely this guarantee, the numerical results, however extensive, cannot compensate for the failure of the theory.

major comments (3)

[§2.1 (Lemma 2.1) and §3 (Theorem 3.1)] Lemma 2.1 requires |φ′(x)| to be strictly increasing in |x − a|, but the proof of Theorem 3.1 verifies only that φ is strictly monotone (from strict convexity of f) and then asserts that the assumptions of Lemma 2.1 are satisfied; this is a genuine gap. Strict convexity gives φ′(γ) = −d_tᵀ∇²f(x_t − γd_t)d_t < 0, which says nothing about the growth of |φ′| away from the root. For example, f(x) = x² − cos(x) is strictly convex and smooth on [0,1]; with x₀ = 0.1 and d₀ = x₀ − v₀ = 0.1, one has |φ′(γ)| = x₀²(2 + cos(x₀(1−γ))), which strictly decreases as γ moves away from the root γ_a = 1, so Lemma 2.1 does not apply even though the theorem's assumptions hold. The same-side initialization premise also requires ρ < γ_a, which is not quantified and can fail when the line-search root is very close to zero (e.g., near optimality); the theorem therefore proves neither the convergence of each SLS call nor the inherited FW rate.
[Algorithm 2, lines 7–12] Algorithm 2's stopping rule is incompatible with the clipping in line 8. Lemma 2.1 analyzes the unclipped recurrence, whereas Algorithm 2 clips every candidate to [0, γ_max] and terminates only when |φ₀| < ε (line 12); if the unconstrained root of φ lies outside [0, γ_max], the constrained minimizer sits at the boundary, where φ does not vanish, so no iterate can satisfy the stopping rule. Concretely, for min_{x∈[0,1]} (x−10)² with x₀ = 0, d₀ = x₀ − v₀ = −1, and φ(γ) = 2(10−γ), the first secant step produces γ = 10, line 8 clips it to 1, and the loop recomputes φ(1) = 18 forever for any ε < 18. This contradicts the 'each SLS call converges' claim of Theorem 3.1 and the text's statement that clipping yields the constrained optimum; the fallback mentioned in Remark 4.1 is not implemented in Algorithm 2 or assumed in the theorem.
[§3 and Appendix A] The claimed 'optimal rate' of FW under SLS is not actually quantified. Theorem 3.1 inherits the rate from exact line search 'up to the line search tolerance ε', but Appendix A, which is supposed to specify how FW rates depend on the line-search error, never defines the 'δ_t-minimizer' it uses and never connects the tolerance ε of Algorithm 2 (a condition on |φ|) to the δ_t entering (A.2). Since |φ(γ)| < ε alone does not bound f(x_t − γd_t) − min f on the segment without additional smoothness assumptions, the link between the implemented stopping rule and the claimed rate is missing; this is load-bearing because the theorem's first assertion is precisely the rate statement.

minor comments (6)

[§2.1, Lemma 2.1] The statement that 'in particular a is the only root on U and φ is monotone on U' does not follow from the strict increase of |φ′| in |x−a| alone; monotonicity should be an explicit hypothesis (the remark following the lemma partially acknowledges this).
[§3] The displayed definition 'φ(γ) = ⟨f(x_t − γd_t), d_t⟩' is missing the gradient operator and should read ⟨∇f(x_t − γd_t), d_t⟩; moreover, this φ is the negative of the derivative of the line-search objective, a sign convention worth stating explicitly.
[Abstract and References] The abstract cites 'Pedregosa et al 2018', but the reference list gives Pedregosa et al. (2020); these should be aligned.
[Remark 3.3] Remark 3.3 ends with the incomplete phrase 'by carrying out over the.'; the sentence should be completed or removed.
[Remark 4.1 and Fig. 1] Remark 4.1: 'algorthmic' should read 'algorithmic', and the introduction's claim of 'around 6−7 iterations' for SLS should be reconciled with the average counts of roughly 1.5 reported in Fig. 1.
[Appendix A, Eq. (A.2)] The displayed derivation in (A.2) uses overlapping struck-through and grouped terms that make the algebra difficult to follow; it should be typeset with explicit term-by-term grouping, and the assumption that line-search error enters through a δ_t term should be stated before the inequality.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SLS convergence analysis is a self-contained root-finding argument, and the paper's self-citations are not load-bearing.

full rationale

The derivation chain is: define the secant recurrence for φ(γ)=⟨∇f(x_t−γd_t),d_t⟩; prove a standalone global-convergence lemma for the secant method (Lemma 2.1); then apply that lemma to the Frank-Wolfe line-search subproblem in Theorem 3.1. No fitted constants are renamed as predictions, no target result is embedded in the assumptions by construction, and no uniqueness or convergence guarantee is imported from a self-citation chain. The statement 'If SLS converges, then it returns the optimal solution to the line search problem' is a definitional reduction to exact line search, not a hidden equation equivalence: the paper still attempts to prove that SLS converges via Lemma 2.1. Self-citations such as FrankWolfe.jl, the OED benchmark, and prior FW step-size work appear in experiments and background, but the main theorem does not rest on them. The skeptical objection that strict convexity alone may not suffice for Lemma 2.1's monotonicity-of-|φ'| hypothesis, and that clipping in Algorithm 2 may conflict with the stopping rule, identifies a possible correctness gap, not circularity. Under the stated rules, correctness risks do not raise the circularity score.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claim relies on two unstated conditions (curvature growth and same-side initialization) that are not guaranteed by the stated assumptions. No fitted constants are used in the derivation; rho and epsilon are implementation parameters.

free parameters (2)

rho (initial perturbation) = unspecified; e.g., 1e-5
gamma_1 = gamma_0 + rho. The theorem requires rho small enough that both initial points lie on the same side of the line-search root, but no bound is given.
line-search tolerance epsilon = unspecified; reported as 1e-7 compatible with FW gap target
Termination criterion |phi_0| < epsilon; influences the accuracy of the step size and, through Appendix A, the outer convergence rate.

assumptions (4)

domain assumption Strict convexity and smoothness of f, compact convex X
Stated in Theorem 3.1; these are the standard Frank-Wolfe assumptions.
ad hoc to paper Curvature-growth condition: |d_t^T Hess(f)(x_t - gamma d_t) d_t| is strictly increasing in distance from the line-search root
Needed for Lemma 2.1 but not stated in Theorem 3.1 or verified in its proof. This is the hidden assumption on which the convergence guarantee rests.
ad hoc to paper Initial points gamma_0 and gamma_1 are on the same side of the root
Required by Lemma 2.1; the theorem asserts rho is a 'small positive perturbation' without quantifying it.
domain assumption Clipping to [0, gamma_max] does not prevent convergence of the secant iterates
Algorithm 2 clips every iterate, but no proof covers the clipped recursion. This is implicitly assumed by the convergence statement.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Secant Line Search for Frank-Wolfe Algorithms." pith.science (2026). https://pith.science/paper/IK55JQ7D

@misc{pith2026250118775,
  author       = {Pith},
  title        = {Pith review of: Secant Line Search for Frank-Wolfe Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IK55JQ7D}},
  note         = {Machine review of arXiv:2501.18775}
}

read the original abstract

We present a new step-size strategy based on the secant method for Frank-Wolfe algorithms. This strategy, which requires mild assumptions about the function under consideration, can be applied to any Frank-Wolfe algorithm. It is as effective as full line search and, in particular, allows for adapting to the local smoothness of the function, such as in Pedregosa et al 2018, but comes with a significantly reduced computational cost, leading to higher effective rates of convergence. We provide theoretical guarantees and demonstrate the effectiveness of the strategy through numerical experiments.

Figures

Figures reproduced from arXiv: 2501.18775 by the authors.

**Figure 1.** shows the number of iterations needed by SLS to converge on all problem classes, the total number of instances per problem class can be found in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

**Figure 2.** Comparison of the step sizes per iteration for the Secant and Adaptive line search. but also efficient in terms of computations despite requiring gradient calls, unlike, e.g., backtracking which evaluates the function only. On the numerically-challenging nuclear norm ball example in particular, backtracking quickly stagnates despite theoretically being an equivalent line search. Acknowledgements Research reported in… view at source ↗

**Figure 3.** Progress of the primal value and FW gap for two problems with a quadratic objective (nuclear norm and standard quadratic) and for two problems with a self-concordant objective (D-Opt and portfolio). In (a), the iterations and time are truncated at 10000 and 10 s, repectively, since Backtracking and Agnostic stall on this instance. Hendrych, D., Besançon, M., and Pokutta, S. Solving the optimal experiment design pro… view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: Various runs of SLS with the secant and Newton’s method. (Top Row) Instances where f is not a quadratic function. (Bottom Row) Instances where f is a quadratic function. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]

**Figure 5.** Figure 5: Progress of the primal value and FW gap for an instance of the Birkhoff problem. The Golden Ratio line search from the FrankWolfe.jl package stalls out due to numerical issues [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]

**Figure 6.** Figure 6: Progress of the primal value and FW gap for an instance of the Ill-Conditioned Quadratic problem. For the golden ratio line search the same remark applies as in the Birkhoff problem (see [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

**Figure 7.** Figure 7: Progress of the primal value and FW gap for an instance of the Nuclear problem. The secant line search is not only significantly faster than the other methods but also reaches a much higher final accuracy [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

**Figure 8.** Figure 8: Progress of the primal value and FW gap for an instance of the A-Optimal Experiment Design problem. For the agnostic step size the same remark applies as in the D-Optimal Experiment Design problem (see [PITH_FULL_IMAGE:figures/full_fig_p019_8.png]

**Figure 9.** Figure 9: Progress of the primal value and FW gap for an instance of the D-Optimal Experiment Design problem. The significant uptick in the primal value for the agnostic is expected as (a) the agnostic step size does not guarantee primal progress in contrast to the other step si…

**Figure 10.** Figure 10: Progress of the primal value and FW gap for an instance of the Portfolio problem [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]

**Figure 11.** Figure 11: Progress of the primal value and FW gap for an instance of the Simple Quadratic problem [PITH_FULL_IMAGE:figures/full_fig_p022_11.png]

**Figure 12.** Figure 12: Progress of the primal value and FW gap for an instance of the Spectrahedron problem [PITH_FULL_IMAGE:figures/full_fig_p023_12.png]

**Figure 13.** Figure 13: Computed step sizes over iteration for the Secant line search and Adaptive line search on various problem classes. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_13.png]

**Figure 14.** Figure 14: Progress of the primal value and FW gap for an instance of the Nuclear problem using Vanilla Frank-Wolfe. 100 101 102 103 104 0.99 0.99 0.99 0.99 Primal Secant Adaptive Agnostic Monotonic Golden Ratio Adaptive Zero Backtracking 100 101 102 103 0.99 0.99 0.99 0.99 100 …

**Figure 15.** Figure 15: Progress of the primal value and FW gap for an instance of the Spectrahedron problem using Vanilla Frank-Wolfe. 25 [PITH_FULL_IMAGE:figures/full_fig_p025_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 10 canonical work pages

[1]

(A.3) If we choose constant δt =δ , the sum of the terms with δ on the right hand side becomes O(tδ)

i+ 2 + 1 At tX i=0 Aiδi < 2LD2 t+ 2 + 1 At tX i=0 Aiδi. (A.3) If we choose constant δt =δ , the sum of the terms with δ on the right hand side becomes O(tδ). So if we are aiming to get an ϵ-minimizer after T steps, we can choose T so that the first summand on the right hand side is ϵ/2 and we can choose δ= Θ(ϵ/T)so that the second summand isϵ/2afterTsteps...

work page 2022
[2]

Ill”. Well-conditioned quadratic problems denoted “QuadProb

Comparison of execution times between Secant and Newton’s methods for various test functions. Where f is explicitly provided, the gradient function is computed via automatic differentiation. For the line search problems, the gradient is provided directly and not computed via automatic differentiation, as those are instances extracted from the line search ...

work page 2020
[3]

In (a), the iterations and time are truncated at 10000 and 10 s, repectively, since Backtracking and Agnostic stall on this instance

Progress of the primal value and FW gap for two problems with a quadratic objective (nuclear norm and standard quadratic) and for two problems with a self-concordant objective (D-Opt and portfolio). In (a), the iterations and time are truncated at 10000 and 10 s, repectively, since Backtracking and Agnostic stall on this instance. Hendrych, D., Besançon, ...

work page 2024
[4]

OA” and “OD

C. Additional Experiments In this appendix, we provide additional information and context on the instance classes, and report more fine-grained results on experiments by problem class. Optimal Design of Experiment (OED).Optimal Design of Experiment is a problem maximizing an information criterion on the probability simplex and which was tackled by a FW me...

work page 2024
[7]

The geometric mean of the solving time is taken over all instances

Instances of the D-Optimal Experiment Design problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances. Brackets indicate that all instanc...

work page 1986
[8]

ISBN 978-3-95977- 325-6

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977- 325-6. doi: 10.4230/LIPIcs.SEA.2024.16. URL https://drops.dagstuhl.de/entities/ document/10.4230/LIPIcs.SEA.2024.16. Jin, Q. and Mokhtari, A. Non-asymptotic superlinear conver- gence of standard quasi-Newton methods.Mathematical Programming, 200(1):425–473,

doi:10.4230/lipics.sea.2024.16 2024
[10]

The geometric mean of the solving time is taken over all instances

Instances of the Spectrahedron problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances. Secant Adaptive Agnostic Backtracking Dim # Time...

work page
[13]

0.5 <1e-7 284.6 1.44e-7 66 2083.7 2.09e-06 1263 166.8 3.63e-7 40 QuadProb

work page

Show all 17 references

[14]

The geometric mean of the solving time is taken over all instances

Instances of the Birkhoff problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken ...
[15]

The geometric mean of the solving time is taken over all instances

Instances of the Ill-Conditioned Quadratic problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of ite...
[16]

We only included it here for completeness and since it is the textbook step-size rule for the vanilla Frank-Wolfe algorithm

as it does not work for generalized self-concordant functions (Carderera et al., 2021; 2024). We only included it here for completeness and since it is the textbook step-size rule for the vanilla Frank-Wolfe algorithm. Table

2021
[1970]

AdaBB: Adaptive Barzilai- Borwein method for convex optimization.arXiv preprint arXiv:2401.08024,

Zhou, D., Ma, S., and Yang, J. AdaBB: Adaptive Barzilai- Borwein method for convex optimization.arXiv preprint arXiv:2401.08024,

arXiv
[2019]

W., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S

Braun, G., Carderera, A., Combettes, C. W., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S. Conditional gradient methods.arXiv preprint arXiv:2211.14103,

arXiv
[2020]

and Mishchenko, K

Malitsky, Y . and Mishchenko, K. Adaptive proximal gra- dient method for convex optimization.arXiv preprint arXiv:2308.02261,

arXiv
[2023]

Altschuler, J. M. and Parrilo, P. A. Acceleration by random stepsizes: Hedging, equalization, and the arcsine stepsize schedule.arXiv preprint arXiv:2412.05790, 2024a. Altschuler, J. M. and Parrilo, P. A. Acceleration by stepsize hedging: Silver stepsize schedule for smooth co...

arXiv
[2024]

V ., Lessard, L., and Wilson, A

Cavalcanti, J. V ., Lessard, L., and Wilson, A. C. Adap- tive backtracking for faster optimization.arXiv preprint arXiv:2408.13150,

arXiv
[2025]

Bolte, J., Combettes, C

URL https:// arxiv.org/abs/2501.14613. Bolte, J., Combettes, C. W., and Pauwels, E. The iterates of the Frank-Wolfe algorithm may not converge.Mathemat- ics of Operations Research, 49(4):2565–2578,

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

(A.3) If we choose constant δt =δ , the sum of the terms with δ on the right hand side becomes O(tδ)

i+ 2 + 1 At tX i=0 Aiδi < 2LD2 t+ 2 + 1 At tX i=0 Aiδi. (A.3) If we choose constant δt =δ , the sum of the terms with δ on the right hand side becomes O(tδ). So if we are aiming to get an ϵ-minimizer after T steps, we can choose T so that the first summand on the right hand side is ϵ/2 and we can choose δ= Θ(ϵ/T)so that the second summand isϵ/2afterTsteps...

work page 2022

[2] [2]

Ill”. Well-conditioned quadratic problems denoted “QuadProb

Comparison of execution times between Secant and Newton’s methods for various test functions. Where f is explicitly provided, the gradient function is computed via automatic differentiation. For the line search problems, the gradient is provided directly and not computed via automatic differentiation, as those are instances extracted from the line search ...

work page 2020

[3] [3]

In (a), the iterations and time are truncated at 10000 and 10 s, repectively, since Backtracking and Agnostic stall on this instance

Progress of the primal value and FW gap for two problems with a quadratic objective (nuclear norm and standard quadratic) and for two problems with a self-concordant objective (D-Opt and portfolio). In (a), the iterations and time are truncated at 10000 and 10 s, repectively, since Backtracking and Agnostic stall on this instance. Hendrych, D., Besançon, ...

work page 2024

[4] [4]

OA” and “OD

C. Additional Experiments In this appendix, we provide additional information and context on the instance classes, and report more fine-grained results on experiments by problem class. Optimal Design of Experiment (OED).Optimal Design of Experiment is a problem maximizing an information criterion on the probability simplex and which was tackled by a FW me...

work page 2024

[5] [7]

The geometric mean of the solving time is taken over all instances

Instances of the D-Optimal Experiment Design problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances. Brackets indicate that all instanc...

work page 1986

[6] [8]

ISBN 978-3-95977- 325-6

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977- 325-6. doi: 10.4230/LIPIcs.SEA.2024.16. URL https://drops.dagstuhl.de/entities/ document/10.4230/LIPIcs.SEA.2024.16. Jin, Q. and Mokhtari, A. Non-asymptotic superlinear conver- gence of standard quasi-Newton methods.Mathematical Programming, 200(1):425–473,

doi:10.4230/lipics.sea.2024.16 2024

[7] [10]

The geometric mean of the solving time is taken over all instances

Instances of the Spectrahedron problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances. Secant Adaptive Agnostic Backtracking Dim # Time...

work page

[8] [13]

0.5 <1e-7 284.6 1.44e-7 66 2083.7 2.09e-06 1263 166.8 3.63e-7 40 QuadProb

work page