Secant Line Search for Frank-Wolfe Algorithms
Authors: Deborah Hendrych
Sebastian Pokutta
Mathieu Besançon
David Martínez-Rubio
Venue: ICML 2025 poster (2025)
Keywords: First-order methods
Frank-Wolfe algorithms
Secant
Primary area: optimization->convex
TL;DR: A new line search for Frank-Wolfe algorithms based on the secant method

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., 2020), 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.

Secant Line Search for Frank-Wolft Algorithms
Deborah Hendrych 12
Sebastian Pokutta" 12
Mathieu Besançon" *3
David Martínez-Rubio"
Abstract
subproblem's 's function evaluations are available us, which corresponds to computing partial derivatives of making the secant method (instead of the Newton-Raphson method) the natural choice.
We present a new step-size strategy based on the secant method for Frank- Wolle algorithms. This strategy, which requires mild assumptions about the function under consideration, can be applied to any Frank- algorithm. It is as effective as full line search and, in particular, allows for adapt- ing to the local smoothness of the function, such as in Pedregosa et al. (2020), but comes with a significantly reduced computational cost, leading to higher effective rates of convergence. We pro- vide theoretical guarantees and demonstrate the effectiveness of the strategy through numerical experiments.
Related Work
There is abundance of work on line search strategies for optimization, as step-size rules can significantly impact the performance of optimization algorithms, both computation- ally and in terms of convergence rates. Standard examples of step-size strategies in unconstrained optimization include backtracking and golden ratio search (see e.g.. (Nocedal) & Wrright 1999)). A notable recent example is the Silver Step-size Schedule (Altschuler & Parrilo 2023 2024a b) which achieves partial acceleration for smooth convex opti- mization via standard gradient descent. Here, we will only provide a brief overview of the prior works most closely related to ours.
1. Introduction
We are interested in solving constrained optimization prob- lems of the form
The requirements for a step-size strategy are typically that it should be (1) effective (making progress), (2) efficient (low computational cost), and (3) adaptive (adapting the local smoothness of the function). As bonus, the strategy should be simple and robust so that it is easy to implement. While achieving two out of the three requirements is relatively easy, achieving all three is challenging. Recently, Malit- sky & Mishchenko (2020; 2023) made sigmificant progress in this direction by providing an adaptive step-size strat- egy that does not perform line search, satisfying all three requirements. This sparked lot of interest, with alter- native approaches (see e.g., Zhou et al. (2024) based on the Barzilai-Borwein two-point step-size (Barzilai & Bor wein 1988)) being analyzed. These approaches estimate the inverse of the local Lipschitz smoothness constant via two points x, y as (7f(x)-Vf(x) and then use this (with modifications) as the step-size "tt for an update of the form X(+1 < x; 7 (x(x). A close inspection reveals that this is effectively modified (higher-dimensionall) secant step. The resulting step-size strategy performs well com- putationally with great adaptivity to the function geometry. Unfortunately. the approach comes with two caveats for the setting we are interested in. First, it cannot be carried over to the Frank-Wolfe setting as the analysis relies on the con- vergence of the iterates the optimal point. This, however, is not necessarily given for Frank-Wolf algorithms (Bolte)
min fxx)
(1.1)
xEX
with first-order method, relying only on gradient and func- tion evaluations, where is smooth function and X is
compact convex set onto which projection is potentially expensive. In this case, variants of the Trank-Wolfe (FW)
algorithm (Frank & Wolfe 1956; Levitin & Polyak 1966) are a popular choice. One operation required for most FW variants is a choice of step size to update the iterate x, along descent direction. We present new line search strategy based on the secant method for these algorithms. To this end, we will solve for roots of the optimality system of the line search problem. Together with the first-order requirement of the main algorithm, this means that only
Ix-y]
"Equal contribution 'uue Institute Berlin, Berlin, Germany 'Berlin Institute of Technology, Berlin, Germany 'Université Grenoble Alpes, Inria, Laboratoire d'Informatique Grenoble, Grenoble, France "Signal Theory and Communications Depart- ment, Carlos III University of Madrid, Madrid, Spain. Corre- spondence to: Sebastian Pokutta <pokutta@ ciautta@xib.dde @zi.de>>. Mathieu Be- sançon <mathicu. www.niiiw.esncooeeeee @ frr, David Martinez-Rube <dm- rubio ing uc3m.es>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Secant Line Search for Frank-Wolfe
al. 2024), due to their affine-invarianc. We point out that this is also not just an artifact but the proposed step- size strategy deliberately gives up the monotonic descent requirement to achieve larger steps, which is incompati- ble with Frank-Wole convergence analysis. Second, the methods use dampened secant steps which lead to the loss of superlinear convergence of the secant method as can be seen from Equation (2.6) in [Section 2.2, where the equal- ity does not hold anymore as the lower-order terms do not cancel. This is not an issue in the settings considered by the aforementioned works as they perform single secant steps only. However, we want to capitalize on the potentially super-linear convergence.
apply here. Stabilization of locally convergent algorithms has been topic that already received significant attention decades ago, see e.g., (Polak 1975 1976) and the secant method has been also used for the solution of simultaneous nonlinear equations (Wolfe] 1959).
Contribution
Our contribution can be summarized as follows:
New step-size strategy. With line searches, the key trade- off is between the cost of the search, which reduces the effective rate of convergence, and improved step sizes. We provide a new step-size strategy, coined Secant Line Search (SLSS), which solves the line search problem via the secant method. This leads to an extremely fast strategy and, while it technically does not meet all previously for a step size due to its search-type nature, the iteration count usually so low (around 6 - 7 iterations) that it practically does satisfy all requirements. Moreover, the strategy is adaptive in the sense that it exploits favorable local smoothness and it can be applied to any Frank-Wolfe algorithm, due to the constrained nature of the problems Wolfe is applied to. In fact, for quadratics, SLS converges in one iteration and exploits the local smoothness of the function in the direction of the descent.
Step-size strategies for Frank- can essentially be grouped into three types (see e.g., (Braun et al., 2022) for an extensive overview): (1) open-loop strategies of the form 7 स with E 2 2 being an integer. These strategies recently received new attention as they can achieve higher convergence rates than e.g., line search strategies in some settings (see e.g., (Bach 2021] Wirth et al. [023] 2024)) (ii) so-called stort-steps, which are effectively the solution aris- ing from the smoothness inequality but require knowledge of the gradient Lipschitz constant (iii) line search strategies, where basically any strategy can be used, however, the cur- rent gold standard is the adaptive backtracking line search of Pedregosa et al. a (2020), which also approximates the local smoothness constant and its numerically more stable variant from Pokutta (2024). Another recent successful approach has been the monotonic open-loop strategy of (Carderera et al. |021 2024), which was originally developed for (gen- eralized) self-concordant functions but often performs very well in general. We highlight that even though we gathered these methods under "line search", they are strictly speaking not line search methods since they terminate with conditions other than (near-)optimality on the segment given by the de- scent direction. The adaptive step sizes from (edreeedee et al. (2020): PPokutta| (2024) test that a local Lipschitz smooth- ness estimate produces valid lower bound on the primal progress while the monotonic step size from Carderera et al. 2021 2024) tests primal improvement on top of an open- loop step-size schedule.
requirements
Theoretical guarantees. Using the secant method to solve the line search problem comes with multiple issues for most optimization algorithms since the secant method, while of- ten very fast, is not necessarily convergent. However, due to the special structure of FW algorithms that do not fol- low the gradient but use alternative directions of the form X - V2. cf. Algorithm I the solution to the line search problem is confined to a bounded interval [0, "maax] Ex- ploiting this property, we can guarantee convergence under mild assumptions in Lemma 2.1 and Theorem 3.1
Numerical experiments. We provide extensive numeri- cal experiments demonstrating the superior computational performance of SL.S over other step sizes. We also discuss implementation enhancements that further reduce compu- tational costs, making SLS practical option for a broad class of problems, being either the best performing option or close to the best one. The results show that SLS not only accelerates the convergence of FW compared to other step-size strategies but is also highly competitive in time thanks a low number of secant iterations within the line search. This low line search cost and improved convergence make SLS an excellent new step size choice for FW algo- rithms for a broad range of problems. Our strategy might be more broadly applicable to other algorithm classes beyond FW but may require stronger assumptions or safeguards to guarantee convergence.
Other notable recent approaches in the context of uncon- strained optimization include speeding up the backtracking search with an adaptive retraction (Cavalcanti al.) 2024)) which can be applied broadly and might be adaptable to the Frank- Wolfe setting. Moreover, the local convergence of quasi-Newton methods of the Broyden class have been heav- ily studied in recent work (see e.g., (Jin & Mokhtari 2023 Rodomanov & Nesterov] 2022, 2021)) to provide finer and finite-time convergence guarantees. While highly interest- ing in their own right, these approaches are only tangentially related to our work here as we directly use the secant method and many of the challenges of quasi- MesitN methods do not
2

---

Secant Line Search for Frank-Wolfe
Preliminaries and Notation
p(x) Clearly A ((x,)) = A (y, 2). Further, observe that S(x,y) plv) 2 A(r.)) = y A(2.)) Sy,, We will now establish a first convergence result of the secant method.
We use bold-faced letters x denote vectors and non-bold- faced letters x to denote scalars. Throughout the paper, we will use for the iteration count of the outer algorithm, typically iterations of the FW method and n for the iteration count of the line search method, We let ll-Il denote the Euclidean norm and ( the standard inner product.
Lemma 2.1. Let a be a rool of q: + IR and let U be a one-sided neighborhood of a. Further assume that lip' (x)) is strictly increasing in |x |x- a] with x E U, i.e, as we move away from a; in particular a is the only root on U and yp monotone on U. Then, we have:
2. The Secant Method
S(x. y) 1,
0 <
The Secant Method (see c.g., Papakonstantinou & Tapia )2013) is a well-known method for finding the root of function pp: I-- + R. It is based on the recursion:
a
for all + z,y E U, i.e., the distance to is strictly decreasing.
Fn Fn
Tn+1 - 2n - ((x))) ((x,) 11
(2.1)
Proof. Note that (a(a) = 0 and let x, E U be arbitrary with z,y, all distinct. We differentiate the following two cases.
with initial values To, chosen appropriately. We can think of the secant method as an approximate version of Newton's method, which uses the update
Case 1: |ar -all al < by - a/. i.e., x is closer to a. Observe that we have:
In+1 f In - (((n)) (x(n))
(2.2)
(x(x)
using the approximation:
S(I y)
2
A(r.y]
x a
x a
(((n) P (xx) ((x
(2.3)
A (xx, y) -a) = A(x, a) A(x, y)
((x)) - p((a)
In Fn-1
The secant method predates Newton's method by over 3000 years (Papakonstantinou & Tapia 2013).
By monotonicity A(z.a) > 0. Moreover, since [x'())) is A(r,y)
One should think about :7(7) f(x; (z)))) in our application. Before considering the line search problem, we establish global convergence when the absolute value of the derivative of the function yp is increasing as we move away from the root, c.g., if "p > O. We also recall the convergence rate of the secant method near the root. The latter is folklore and many different proofs exist, we provide sketch of the argument only. For global convergence, the proof is probably known (and straightforward) but we are not aware of any direct reference and thus we provide it here. It ensures convergence under suitable initialization and mild assumptions for our setting. Throughout this sec- tion we assume that yp is a smooth function and sufficiently differentiable.
stricly increasing as we move away from a in 24, we have A (zz a) < Axx y). so that 0 < S(x.y))a < 1 follows; this also implies that we do not leave U and stay on the same side of a as S(x.y)-e >0
Case 2: |x - a ly - al. i.e., y is closer to a. Similar as w-a and using S(r, v) = S(y,
before after factoring out z-a we similarly obtain:
zyy) A
S a a
y
x
1/
a (1
A (v. a)
1
a
A A(z, v)
Now observe that 0 g-a and A a) A(x, as
2.1. Global Convergence
above, that 0 <
S(x.v)-a < 1 follows.
x-a
In general, the secant method is not globally convergent. However, we can show that under suitable assumptions, the secant method converges monotonically to root in cases relevant for our line search problem. To simplify the exposition, we introduce the notation Axx,)) v) ((=)-p(s) and S(a, v) x [
Now, the property 0 < S(z.2)a < 1 proven in the two x-a
cases above imply that In+1 In converges to O. More- p(an)
over, In - In=11
A(2 and |A(nn
max ( (2o)). lyp (x1))) which implies that p(xx.) con- verges to 0 and thus In converges to a.
r-y
w(x)
so that the secant method can be
written as:
The lemma above basically states that if, in a neighborhood U of the root, the function is monotone, has strict curva- ture, and the initial points zo. 21 are both on the same side
(2(xn)
In+1 f- S(Zn, In-1) 2(n)) In
(2.4)
A A(In In-1)
3

---

Secant Line Search for Frank-Wolfe
of the root, then the secant method converges monotoni- cally to the root. This is for example the case if g > O holds. We will later see that in case of our line search problem, apart from the strict curvature condition, all other conditions are satisfied naturally. Note, that the requirement that (p((z)) is strictly increasing can be relaxed to require A A(a x) < A(r, v) whenever x lies between a and y and A (a, r). A(x,3) y) having the same sign, not requiring that f to be smooth.
Remark 2.3 (Secant Method vs Newton's Method in Black- -Box Optimization), The secant method has an advantage over Newton's method in black-box optimization, where only function evaluations are available, as it avoids gradient computations and requires just one function evaluation per iteration. However, even when both function and gradient evaluations are available in an oracle model at roughly the same cost, we can perform roughly two secant iterations for every Newton iteration, potentially making the secant method faster in practice, despite its lower order of con- vergence (order Rs 1.618) compared to Newton's 's quadratic convergence (order 2) with effective orders of convergence of 1.618 = 2.62 vs. 2.
Remark 2.2 (Rate and Order of Convergence). Note that Lemma 2.1 makes no statement about the order of conver- gence. This is for good reason arbitrarily slow conver- gence (still linear though with small rates) is compatible with the Lemma 2.1 globally and locally. In fact, the convergence order and rate is a function of the multiplic- ity of the root. As a simple example consider (xx) = xm with m > 2. which satisfies our assumptions. The con- vergence rate of the secant method is linear with rate A with 0 < x 1, that X + Am-1 = 1; see e.g., (Diez 2003). Note, though that if the secant method converges it converges at least with order 1, i.e., linearly.
In white-box settings, where gradients can be computed efficiently, such as through reverse automatic differentiation (AD), the function evaluation becomes essentially free as byproduct of the gradient evaluation, making Newton's method potentially more favorable due to its faster conver- gence rate. We would like to stress that essentially all our arguments also apply to a variant that would use Newton's 's method for the line search problem; in in[Lemma 2. we would simply invoke the mean value theorem and replace A Aax, y) with yp (ar) and then the proof would work analogously.
2.2. Local Convergence
Let ((a) = 0. For the sake of exposition we consider the case of a simple root and assume that go is twice differ- entiable with (a() # 0 and ("(a) * O. We define the iterates as In = a + en to perform an error analysis with the recursion:
For our setting however, we assume that we ultimately want to optimize function f with a first-order oracle and we will run the secant method for the line search problem over the directional derivative of f. so that second-order information is not available. For the sake of completeness however, we did run some synthetic tests, see Seeston B comparing the Newton's method and the secant method on problems as they appear in our setting, with both AD and user-provided derivatives for the second-order access, and found that in practice the secant method is superior in the first case and almost always faster in the second case. One reason for this that both in the case of automatic differentation and manual gradients, each line search subproblem requires a Hessian- vecttor computation, while not exploiting that infor- mation beyond the step size. This "partially second-order" method was already observed in Carderera et al. (202T) not to perform well against a fully first-order method due to the high cost per iteration and little additional gain.
Gx+1 En -i-(a(a
6n fn-1
(2.5)
ppaa + En) - plaa- - =
Using Taylor expansion:
(0(0) 2 2= ec') Me), (2.6)
pla +)) = ('(ae
2
(a 20'(a)
where M
we can derive the recursion:
(a(a)
1 2
En- 16m-
(2.7)
(a)
By analyzing the series of log(Gn) derive an error estimate of:
Diez
2003
we can
Finally, a note on Brent's method (Brent 1971), also called method, is in order; see also Flannery et al. 1992). Brent (2013) for more details. While this root- finding method is often considered the gold standard for derivative-free root finding with an order of convergence of RJ 1.839, it is significantly more involved and expensive than the secant method and in our tests for our problems, was outperformed by the secant method. This can be attributed to the secant method's 's lower computational cost per iteration and the fact that we do (almost) never require the additional safeguards of Brent's 's method because of the already present
(a()) (a)
1xx al 1453
|n+11 - al ~
(2.8)
ie., we have a convergence of order 1+y5 1.618. For full proof, see e.g.. Grinshpan] (2024) and for the con- vergence for roots of higher order we refer the reader to Diez (2003). In fact, for roots of order m 2 2, the conver- gence rate drops from superlinear to linear with rate À with << < 1, so that X + m 1; see e.g. Diez 2003).
4

---

Secant Line Search for Frank-Wolfe
step size bounds for FW together with Lemma 2.1 We benchmarked in Julia via Rootss j1 well in Python via SciPy.
we have sp(r) = (5(x, -d,), ) de) and use the recursion:
7n+1 '/ (Vf(x, indd), In - 7n-1
(3.4)
3. The Secant Method for Line Search in Frank-Wolfe Algorithms
(V - (n),)) dd)) (V
It is important to note that SLS does not approximate the in- verse of the local Lipschitz constant of f in contrast to (Mal) itsky & Mishchenko | 2023). Rather, it approximates the relevant quantity in the Frank-Woll context, which is
To disambiguate, we denote the iterates of the secant method applied to the line search problem by "n and the iterates of the Frank- algorithm by Tt-- We are interested in solving Problem (I.I) with f being a smooth and convex function. In Algorithm I] we recall the vanilla -olfe algorithm and refer the interested reader to Braun et al. (2022) for more advanced variants.
related (and identical for quadratics) to 7. [V((x))d
|d
An implementation of Secant Line Search (SLS) is given in Algorithm 2] The algorithm is purposefully written in a verbose fashion to highlight that, apart from the initial two points, only one gradient evaluation is required per iteration. In [Section A, we specify how the convergence rates of Frank- behave depending on different choices of the enror parameter within the line search subproblems.
Algorithm 1 Frank- Wolfe algorithm (Frank & Wolfe 1956 Levitin & Polyak] 1966)
1: Input: Initial point x E X, number of iterations T
2: Output: Final iterate XX
3: for t -2=00 to do
4: Vi + argmin(V
Algorithm 2 Secant Line Search (SLS)
vex
1: Input: Function initial point xt, direction de, initial step sizes "0, 71 tolerance 6
5: X++1 + (1 74 )x + 7eV:
6: end for
2: Output: Step size ?-
3: Initialize 7-1 < Yo. Tu t 71
Most Wolfe variants update the iterate as:
4: Compute --1 < (VI(x; - --1d)),
5: Compute Po < (Vf(x; - -)od)), di)
X X, yd,,
(3.1)
6: repeat
7: Update Y1 t- 70- 80
70 -0-11
with de being direction and 7 E [0, Ymaax] determined by the specific FW variant under consideration. For instance,
400 pp-1
8: 71 + max(0, min (71: m
(clip)
Update y-1 + 7o. 7o + 7/1
d = X2 V2 and Tmax = 1 for a standard FW step as we can see in Allorithm I] A key point common to all vari- ants is that iterates are maintained as convex combinations of extreme points of the feasible set X, so that typically Tmax < 1.
10: Update 9--1 t P0
11: Compute yo < (Vf(x, %0,,),
12:
until Ispal <
13:
return 7-' + 70
When the step size y is determined by line search, the goal is to choose so that progress is maximized, i.e., we solve the line search problem:
As already indicated carlier we have that %a E [0, 1] as the iterates are convex combinations of the extreme points of the feasible set X' with the current iterate. In fact, due not following the gradient but rather updating Xx+1 f- (1 (1-7) >)x; V. after the first iteration, the op- timal solution Ya of (3.3) is almost always in the interval (0. To see that Yo > 0, observe that the Frank-Wolfe gap (V.(x;;,x, - vz) > 0 by convexity of f and definition of v, as long as x, is not optimal and hence x, - v, is a descent direction. The upper bound typically depends on the function class under consideration. For the upper bound in the case of L-smooth functions, see, e.g., (Braun et al., 2022 Remark 2.5) and for (generalized) self-concordant functions, see (Carderera et al.) 202 2024). We highlight that 2a < 1 is not necessary for our arguments to work but it is useful as it basically ensures that the root is to be found in the interval (0, 1). When this is not the case and clipping
+ argmin f(x: - 7dd).
(3.2)
YE Nmmxa)
This is equivalent to finding the root of the optimality con- dition:
,y J
f(x - 7d1)= = =0,
(3.3)
and since we consider convex and smooth functions such solution exists. Moreover, we can deliberately ignore the constraint y E [0, Tmmax because if the optimal 7 is outside of this interval, we can simply clip it to the boundary, which will be the optimal solution to the constrained problem.
Applying the secant method to the line search problem (3.
5

---

Secant Line Search for Frank-Wolfe
oceurs, still make significant progress (at least as much as the optimal short step) and typically such a step halves the primal gap.
be applied basically any other variants of the Frank- Wolfe algorithm, e.g., the Away-Step Frank- Wolfe algo- rithm (Wolfe] 1970; LacosteJJelll & Jaggi 2015). the Pair- wise Conditional Gradients (Lacoste-Julien & Jaggi 2015),
With this, we can now establish the convergence of the Secant Line Search (SLS) when used in a Trank-Wolfe algorithm.
the Blended (Pairwise) Conditional Gradients algorithms (Braun et al. 2019 Tsuji et al. 2022), and Decomposition-
invariant Conditional Gradients (Garber & Meshij 2016) Bashin & Zhang 2017). Some of these methods - typi- cally those that explicitly maintain a so-called active set, i.e., subset of extreme points from which convex com- bination forms the current iterate have "drop steps", i.e., iterations that do not guarantee progress but instead spar- sify the active set, via e.g., away or pairwise steps when clipping occurs. Nonetheless, the same analysis can ap- plied to these methods as well by carrying out over the. We present computational experiments for these algorithms as well below and in the appendix.
Theorem 3.1 (Convergence of SLS). Let| f be a strictly convex and smooth function and let X' be a compact convex set. Then running the Frank- Frank-Wolfe algorithm Algorithm 1} with SLS initialized with 700 = 0 and in- p. where iis small positive perturbation, converges at its optimal rate (which depends on f and X) and each SLS call converges.
Proof. If SLS converges, then it returns the optimal solution to the line search problem (3.3) and hence the iterates of the Folfe algorithm are chosen as if run with exact line search (up to the line search tolerance e), so that the first part of the theorem is trivially true.
Remark 3.4 (Secant Line Search for Quadratics). If f is convex quadratic, then the line search problem (3.3 is an aftine-linear equation. If the iterate x₁ is not optimal yet, then x - V; is a descent direction, so that the slope of the affine-linear function is negative and the secant method converges in single iteration.
remains to verify the assumptions of Lemma 2.T] As is strictly convex, so is f(xx - -dd,) for any x, E X and d, Xt Vt as obtained via Algorithm I] Hence the derivative 2. ()d of f(x; yd,) is strictly increasing in 7. MMoeevver the initial points too = 0 and m = To + are on the same side of the root, so that the assumptions of Lemma 2.1 are satisfied.
As such SLS is almost as cheap as the short-step step size, which would evaluate
7 max { O, 0. (V.(x)),, - vi) - 1 }
}
While the above theorem only guarantees (linear) conver- gence of SLS in the line search problems, the following remarks give indications for cases in which we can expect superlinear convergence of SLS.
T. [| - vell [
while not requiring knowledge of T, and exploiting local smoothness, with progress least as good as the short step.
Remark 3.2 (Superlinear convergence for self-concordant functions). Let f be self-concordant on X. Then for any x, E X and de = x; - V; we have that
For the sake of completeness, note that if we would run Newton's 's method here, provided we would have access to second-order information, then we would need at least one additional second-order evaluation; which is precisely also what we observed in SSection B. where we compared the secant and Newton's method.
g3
G²
0y3 f(x - (F) s 2 022 2222 f(x; - (T)) (3.5)
for all T 10. Thus if 88 8.
-(x 7d)) + for all
4. Computational Experiments
T E [0, 1]. then 7/ is a simple root of Equation (.3) so that we can expect superlinear convergence.
We evaluate the performance of SLS on several prob- lem classes All experiments are carried out in Julia with the blended pairwise FW variant implemented in FolfeWolfe.jl (Besançon et al., 2022, 2025) with default parameters and a one-hour time limit. Additional experi- ments on standard FW are presented in the appendix. An instance is considered solved if the FW gap reaches 10-7, The implementation of the experiments was done with the Julia package Frank Wolfe. and is available as part of the package.
Moreover, the constant M appearing in Equation 2.6 is obtained as:
o (1)x)-77))(7a) M = 2 0 2x
(3.6)
In particular in the case of superlinear convergence, SL. achieves very high precision, which is often helpful for ill-conditioned problems, with very few iterations.
Remark 4.1 (Implementation Details and Improvements). In the following, we discuss some algorthmic considerations ensuring good performance in a wide range of problems.
Remark 3.3 (Other FW variants). While we considered the vanilla Frank- Wolfe algorithm, the same analysis can
6

---

Secant Line Search for Frank-Wolfe
Implementation Safeguards. In the theorem above, we as- sumed that the function f is strictly convex. This assump- tion is not necessarily satisfied although the function may be strictly convex on the line we search on. To make SLS robust and safe, whenever the secant method fails, one may run any fallback strategy, c.g., backtracking line search.
even in non-quadratic cases. High average iteration counts correspond to instances causing numerical instabilities.
40
Warm-starting. We can warm-start SLS by using the optimal n" from the last call and initializing the secant method with Yu 7 and "1 To + p. This further reduces the number of inner iterations in our experiments.
# instances
20
We briefly list the problem classes used for experiments. Detailed descriptions can be found in the appendix. "OA" and "OD" correspond to optimal design of experiment prob- lems with A- and D-criterion respectively. "Port" are portfo- lio instances with a log-revenue objective. "QuadProb" and "III" are quadratic instances over the simplex with low and high condition number respectively. "Birkhoff", "Spec" and "Nuclear" quadratic instances over the Birkhoff polytope, the spectraplex, and nuclear norm ball respectively.
2.5
Average Secant Iterations
Birkhoff
Quadratic
Cl-Conditiooed
Nuclear
A- Optimal
D-Optimal
Quadratic
Simple
Spectrahedron
Portfolio
We benchmark the performance of SLS against the adap- tive step-size strategies of Pedregosa et al. (2020); Pookutaa
(2024), the golden-ratio and backtracking line search strate- gies, the monotonic step size of Carderera et al.] (2021]
Figure f. Average secant iteration count by problem class. The graph is truncated at 3 iterations on the right, only affecting the numerically unstable Hendrych et al. 2024) with very flat descent directions. Note that the average number can lower than due to warm-starting.
A-Optimal instances, which are known
2024), and the agnostic step size, using the implementations
from the FrankWolfe, ji package. All strategies are run with the target accuracy of 10-?, compatible with the gap stopping criterion we set. In the main part, we com- pare SLS against the adaptive step size (default strategy in FrankWolfe. j1), the agnostic step size, and the back- tracking line search. All other experiments with much more detailed reporting are available in [Section C
Aggregated results for all instance classes are compiled in Table I and broken down in more detail in the appendix. Note that the agnostic step size does not ensure convergence on non-smooth functions such as OA and OD. The SLS strategy outperforms the two other methods in number of FW iterations, gap and time most instance classes. It is particularly interesting that SLS outperforms an essentially free to compute step size such as the agnostic on instance classes on which fast convergence rates can be guaranteed, such as a squared distance objective on a polytope. While SLS is not systematically the fastest strategy for all instance types, it is often very close the best option, making it an effective and robust choice for wide spectrum of problems.
Fig. 2 illustrates the evolution of the step size from the adaptive and secant strategies on four instances on which the secant method converged to the desired FW gap. The convergence of SL. is notably faster on the nuclear norm and portfolio instances, while maintaining higher step sizes during the first iterations. On the D-OED and quadratic problems, we also notice that the step size computed by secant oscillates less than the adaptive line search.
Fig. I shows the number of iterations needed by SLS to converge on all problem classes, the total number of in- stances per problem class can be found in Table For most quadratic problems (Birkhoff, III, QuadProb, Spec), SLS re- quires at most one iteration in accordance with Rith/Kr 3.4] Quadratics on the nuclear norm ball are the exception, with some instances taking more than line search on average. This can be traced back to numerical issues, since on most instances the primal gap is quickly be- low 10-10 10 but the dual gap remains large due to extremely large nuclear norm ball radii. Importantly, the average itera- tion count remains low, around 1.5 1.5, for all solved instances
Detailed trajectories of the most important step-size strate- gies are illustrated in Fig. 3 for four instances of different types. They show the superior performance of SLS com- pared to backtracking line search, to the first-order adaptive strategy of Pokutta (2024), and open-loop step sizes. We compare here against the open-loop strategy because of its popularity for Frank- Wolfe, even though it is not known to converge on non-smooth self-concordant functions such as the OD and portfolio objectives. We highlight that the performance against the number of iterations carries over to the convergence against wall-clock time, showing that SLS is performant to minimize the function on the segment,
secant iteration per

---

Secant Line Search for Frank- Wolfe
A
10
Step
Step
Adaptive
Adaptive Secant
10
Secant
10
109
201
10
16a
10
100
10a
10
19a
10
Iserations
Iterations
(a) Nuclear Norm
(b) D-Optimal Experiment Design Problem
100
10
10-3
Step
Step
10
10-2
Adaptive
Adaptive Socant
Socant
10
8
100
100
10
10a
30
104
10
Trerations
Tterations
(c) Portfolio
(d) Standard Quadratic
Figure 2, Comparison the step sizes per iteration for the Secant and Adaptive line search.
but also efficient in terms of computations despite requiring gradient calls, unlike, c.g., backtracking which evaluates the function only. On the ball example in particular. backtracking quickly stagnates despite theoretically being equivalent line search.
nuclear norm

---

Secant Line Search for Frank-Wolfe
Table Summary of the performance all considered problems. The number of instances per problem classes written in the brackets. The geometric mean the solving time taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up the tolerance. The average number of iterations is taken all solved instances.
Socant
Adaptive
Agnostic
Backtracking
Dual gap
FW iterations
Dual gap
# FW iterations
Dual gap
# FW iterations
Dual gap
# FW iterations
Prob.
Time
Time
Time (5)
Time
Birk. [30]
427.6
<le-7
10624
614.6
2.47e-7
17506
2959.9
8.76e-7
731017
248.5
<le-7
7283
In [50]
15.3
<Ic-7
20
15.9
<lc-7
26
1227.7
4.35c-6
120361
13.9
<le-7
34
Noclear [30]
204.6
0.133
1071
600.6
0.139
2547
3600.0
753000.0
3600.0
11400.0
OA [50]
475.7
0,0333
2194
3600.0
0.0935
3600.0
0.13
3600.0
5.02e-5
OD [50]
199.2
8.08c-5
828
252.0
2.90c-7
1496
3542.2
3.83e-4
>9M
158.8
<le-7
748
Port [13]
0.5
<le-7
28
4,6
1,44e-7
66
2083.7
2.09c-06
1263
166.8
3.63e-7
40
QuadProb
340.7
0,000217
15046
355.7
0,000237
20814
3043.1
0.000163
>30M
426.4
0.000624
32585
Spec [50]
34.5
1.77e-7
124
41.1
3.8c-7
192.3
2.13c-6
4252
168.7
1.35c-6
1347
0.22
0.22
Secent
Adappioo
Prinel
FW Prinmal
0.3
Aguostic
0.2
Adaption
Backtracking
Go
16-17
1042
162
81
(WW E0p
10m2
20
00h
1.000
Time (9)
Tine (6)
(a) Nuclear Norm
(b) D-Optimal Experiment Design Problem
Peined
10-12
10-12
500
1.000
1.500
0.5
1- 10
20
100
167
101
Becuee
Adleptice
Aguonite
10
Pecest
FW
Adlettine
Aguastic
10
13-7
20,100 Etutto 00,000 20.10)
100
100
Time (+)
Iserations
Time (4)
(c) Portfolio
(d) Standard Quadratic
Figure 3. Progress of the primal value and FW gap for two problems with quadratic objective (nuclear norm and standard quadratic) and for two problems with a sell-connordant objective (D-Opt and portfolio). (a), the iterations and are truncated 10000 10 s. repectively, since Backtracking and Agnostic stall this instance.

---

Secant Line Search for Frank-Wolfe
Impact Statement
Besançon, M., Carderera, A., and Pokutta, S. Frank Wolfe.l high-performance and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. INFORMS Journal on Computing, 34(5):2611 1-22000012202,-0--- 2022.
This work introduces a novel step-size strategy for Frank- Wolfe algorithms, leveraging the secant method. By refor- mulating the line search problem root-finding task, our approach significantly reduces computational costs while maintaining effectiveness and adaptivity to local smooth- ness properties. This innovation not only enhances the performance of Frank-Wolf algorithms but also provides a framework that could be extended to other optimization methods, potentially transforming fields that rely on con- strained optimization, such as operations research, machine learning, and engineering design. The broader implications of this work lie in its ability to bridge theoretical and practi- cal optimization challenges. By offering a computationally efficient and theoretically sound step-size strategy, we en- able researchers and practitioners to tackle larger and more complex problems than previously feasible. This could lead to advancements in areas such resource allocation, network design, and large-scale machine learning, where constrained optimization is ubiquitous. Ethically, this work aligns with the goal of advancing open scientific inquiry and computational efficiency, and we do not foresee any ethical issues; the same holds true for immediate social impact.
Besançon, M., Designolle, S., Halbey, J., Hendrych, D.,
Kuzinowicz, D., Pokutta, S., Troppens, H., Herrmanns- doerfer, D. V., and Wirth, E. Improved algorithms and novel applications of the FrankWolfe. library. arXiv preprint
/46/3, 2025.
URL https://
wxx.v.oxg/abs/25011..
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, 2024.
Braun, G., Pokutta, S., Tu, D., and Wright, S. Blended conditional gradients: the unconditioning of conditional gradients. In Proceedings of the 36th International Con- ference on Machine Learning, 2019.
Braun, G., Carderera, A., Combettes, C. W., Hassani, H.,
Karbasi, A., Mokhtari, A., and Pokutta, S. Conditional gradient methods. arXiv preprint urXiv:2211.14103, 2022.
Brent, R. An algorithm with guaranteed convergence for finding zero of function. The computer journal, 14(4): 422-425, 1971.
References
Altschuler, J. and Parrilo, P. Acceleration by stepsize hedg-
ing: Multi-step descent and the silver stepsize schedule. Journal of the ACM, 2023.
Brent, R. P. Algorithms for minimization without derivatives. Courier Corporation, 2013.
Altschuler, J. M. and Parrilo, P. A. Acceleration by random stepsizes: Hedging, equalization, and the arcsine stepsize schedule. arXiv preprint arXlv:2412.05790, 2024a.
Carderera, A., Besançon, M., and Pokutta, S. Simple
steps are all you need: Frank- Wolfe and generalized self- concordant functions. Advances Neural Information Processing Systems, 2021.
Altschuler, J. M. and Parrilo, P. A. Acceleration by stepsize
hedging: Silver stepsize schedule for smooth convex opti- mization. Mathematical Programming, pp. 1-14, 2024b.
Carderera, A., Besançon, M., and Pokutta, S. Scalable Frank-Wolfe on generalized celf-concordant functions via simple steps. SIAM Journal on Optimization, 34(3), 2024.
Bach, F. On the effectiveness of Richardson extrapolation in data science. SIAM Journal on Mathematics of Data 2021.
Science,
Cavalcanti, J. V., Lessard, L., and Wilson, A. C. Adap- tive backtracking for faster optimization. arXiv preprint arXiv:2408. 13150, 2024.
Badr, E., Attiya, H., and El Ghamry, A. Novel hybrid al- gorithms for root determining using advantages of open methods and bracketing methods. Alexandria Engineer- ing Journal, (12)): 5779-11588 2022.
Diez, P. A note the convergence of the secant method for simple and multiple roots. Applied mathematics letters, 16(8): 2003.
Barzilai, J. and Borwein, M. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1):141- 148, 1988.
Dvurechensky, P., Safin, K., Shtern, S., and Staudigl, M. Generalized self-concordant analysis of Frank-Wolfe al- gorithms. Mathematical Programming, (98(1):255-322 2023.
Bashiri, M. A. and Zhang, X. Decomposition-invaree -nvariiaa con- ditional gradient for general polytopes with line search. Advances in neural information processing systems, 30, 2017.
Flannery, B. P., Press, W. H. Teukolsky, S. A., and Vetter- ling, W. Numerical recipes in c. Press Syndicate of the University of Cambridge, New York, 24(78):36, 1992.
10

---

Secant Line Search for Frank-Wolfe
Frank, M. and Wolfe, P. An algorithm for quadratic pro- gramming. Naval research logistics quarterly, 3(1-2): 95-110, 1956.
Pedregosa, F., Negiar, G., Askari, A., and Jaggi. M. Linearly convergent Soane-Woffe with backtracking line-search. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics. PMLR, 2020.
Garber. D. and Meshi, O. Linear-memory and decomposition-invaris linearly convergent conditional gradient algorithm for structured polytopes. Advances in neural information processing systems, 29, 2016.
Pokutta, S. The Frank-Wolfe algorithm: short introduction. Jahresbericht der Deutschen Mathematiker Vereinigunnnin,, 126:3-33 5, 2024.
Grinshpan, A. Order of convergence of the secant method. Lecture Notes, 2024. httpss//wwwt math drexel edu/-tolya/30) secant. .dff
Polak, E. On the global stabilization of locally convergent algorithms for optimization and root finding. IFAC Pro- ceedings Volumes, 8(1):346-300, 1975.
Hendrych, D., Besançon, M., and Pokutta, S. Solv- ing the optimal experiment design problem with mixed-integer convex methods. In Liberti, L. (ed.), 22nd International Symposium on Experimental Algorithms (SEA 2024), volume 301 of Leibniz In- ternational Proceedings in Informatics (LIPIcs), pp. 16:1-16:22, Dagstuhl, Germany, 2024. Schloss Dagstuhl Leiibniz-Zenrrum für Informatik. ISBN 978-3-95977- 325-6. doi: 1.42300LPIIc..SEA.222.....
Polak, E. On the global stabilization of locally convergent algorithms. Automatica, 120ia,,,222444 12(4):337-342, 1976.
Rodomanov, A. and Nesterov, Y. New results on superlinear convergence of classical quasi-Newton methods. Journal of optimization theory and applications, 188:744-769, 2021.
Rodomanov, and Nesterov, Y. Rates of superlinear con- vergence for classical quasi-Newton methods. Mathemat- ical Programming, pp. 1-32, 2022.
URL
Jin, Q. and Mokhtari, A. Non-asymptotic superlinear conver- genee of standard quasi-Ners Newton methods. Mathematical Programming, 200(1 (000())445-4040 2023.
Tsuji, K. K., Tanaka, K., and Pokutta, Pairwise condi- tional gradients without swap steps and sparser kernel herding. In International Conference on Machine Learn- ing, pp. 21864-21888 PMLR, 2022.
Lacoste-Julien, S. and Jaggi, M. On the global linear vergence of Frank-Wolfe optimization variants. In Pro- ceedings of the 29th Conference on Neural Information Processing Systems, pp. 566-575. PMLR, 2015.
Wirth, E., Kerdreux, T., and Pokutta, Acceleration of Frank-Wond Wolfe algorithms with open loop step-sizes. Pro- ceedings AISTATS, 2023.
Levitin, E. S. and Polyak, B. T. Constrained minimiza- tion methods. USSR Computational Mathematics and Mathematical Physics, 6(5):1-50, 1966.
Wirth, E., Peña, J., and Pokutta, S. Accelerated affine- invariant convergence rates the Frank-Wolfe algorithm with open-loop step-sizes. to appear in Mathematical Programming A, 12 2024.
Malitsky, Y. and Mishchenko, K. Adaptive gradient descent without descent. In International Conference Machine Learning, pp. 6702-6712. PMLR, 2020.
Wolfe, P. The secant method for simultaneous nonlinear equations. Communications of the ACM, 2(12): 12-13, 1959.
Malitsky, Y. and Mishchenko. K. Adaptive proximal gra- dient method for convex optimization. arXiv preprint arXiv:2308. 02261, 2023.
Wolfe, P. Convergence theory in nonlinear programming. Integer and nonlinear programming, pp. 1-36, 1970.
Nocedal, and Wright, S. J. Numerical optimization. Springer, 1999.
Zhou, D., Ma, S., and Yang. J. AdaBB: Adaptive Barzilai-
Borwein method for convex optimization. arXiv preprint arXh::2401.08024 2024.
Papakonstantinou, M. and Tapia, R. A. Origin and evolu- tion of the secant method in one dimension. The American Mathematical Monthly, 120(6):500-511 2013.

---

Secant Line Search for Frank-Wolfe
A. Precision of FW's Line Search
In this section, we analyze the convergence of the FW algorithm when there an inexact computation of the line search, depending on the choice of the accuracy parameters.
Assume f: R R is convex, and differentiable in an open set containing the convex and compact feasible set X' and let D def diam(XX. Also, assume f is L-smooth X, that is,
L ||x ||--||², for all x, E X.
f(y) - [(x) + (V f(y). yy + 2
Algorithm Frank- Wolfe with inexact line search
Input: Function f. initial point Xo-
for = 0 to do
2: Vi + argmin (Vf(x)), v)
vER"
3: Xr+1 minimiizer of [0,1] - R, f((1 7)xx + 7v))
4:
end for
We define positive weights > 0 for all & 2 0, to be determined later, and A, del Ei ag Thus, A O. We also define the following lower bound on f(x*), where x* here is defined as minimizer in argminxex f(x):
Axf (xe) + + ae (Vf(x)), xxi)
axf(xe) + ae (Vf(x)) ve xx))
E=
A.L
where we applied convexity in ( and for 2, we applied the definition of Va in the algorithm, which is why define this point. Define the primal-dual gap
G. del f(x+11) L, 2 f(x-1)) f(x"),
(A.1)
and note that upper bound fxx++1) is one step ahead, which helps the analysis. We obtain the following, for t 2 0, and
x
del Ar-1
X,
ae
Ve:
As
As
A.G. - G- Ars(x(+1) - Ac-15(x))
4 axf(x)) + Σ
T-1 ged + at (VS(x)), xi) + Σ aee(VV -xi)
4-1
1-1
Σ
art (x)) + Σ ar (V ve xi))
+
(A.2)
(Vf(x(): Ac(x++1 -x:) - -x1)) + LA,
|| - xil1 2 A,de
La? 2A,
3 LD'aa'
||v x1 A,de
+ A.d, del E..
24,
In 1 we grouped terms to get Ax(f(x(+1) f(xx)) used that the assumption on x makes this term be bounded by the value that the smoothness inequality yields for any point, and in particular for x up to a 6, error coming from the line search. In 2 we used twice the definition of x which implies A (x - xx) = a (v.. xt). In 3) we bounded the distance of points by the diameter D.
12

---

Secant Line Search for Pronk-Wolfe
Now with the choice az = 21 + and A,
Eizo a, (1+ + ()((+ + 2) we have, by telescoping and dividing by Aç:
(1x+1)--(x7) S. -
1
Σ
E,
1
1 Σ
LD
+ A = (++ l)(t+ +2)
Σ
22D
+
1 t
Σ A,8;
A 1=0
A i=0
2A,
1=0 i+2
A 1=0
2LD
1 1
Σ A,o
+
+ AO 1=0
(A.3)
If we choose constant 6, = 6, the sum of the terms with ó on the right hand side becomes O(t5). So if we are aiming to get an e-minimizer after T steps, we can choose 7 so that the first summand on the right hand side is e/2 and we can choose d (e/TT) so that the second summand e/2 after T steps. ca. Another option would be to choose 5; 2A,
which yields 1. A. Ei Azd; 24. E Li- ai after any number of steps.
B. Experimental Results for Secant Method vs Newton's Method
A natural question to ask is whether we can replace the secant method with the Newton's 's method in SLS for higher performance, provided that we have access to second-order information. It turns out that apart from requiring additional second-order ormation that may not be available, even if available and computed via automatic differentiation or provided directly, the secant method is faster than the Newton's 's method in practice in our application context.
To this end we ran the following computational experiments. We run SLS with secant method and Newton's 's method in isolation outside of the Frank-Wolfs algorithm to avoid (1) any overheads that may arise and (2) side effects due to different trajectories that the algorithms may take and that propagate, so that different line search problems would be solved.
For this experiment, we performed two different types of experiments. We first ran both methods on a subset of the instances from Badr al. (2022). as they cover a broad range of cases, also outside our direct application context. We ran each variant 1000 times for each instance and report total timings. Both methods were run with the same initial step size Yo 0 and m = "to P with - 10-5 and the target accuracy of 10-8, For these tests, computed the gradient function via automatic differentiation. We report the average time in seconds for each method to find solution with relative accuracy of 10-5
We then ran the two methods on 1000 randomly generated line-search instances for two relevant cases that typically occur in the context of the Frank-Wold algorithm. For the case where f is a quadratic function, we used the same instance generation as done in /eccionn 4 for the quadratics and randomly sampled and d from the unit sphere. For the case where f is a non-quadratic function, we derive the line search problems from the portfolio optimization instances. In the quadratic case, the gradient has been provided directly and in the case of the non-quadratic functions, we used finite differences compute the gradient; to more closely mimic the line search problems that we encounter.
We report the timings in Table 2 and provide some visualizations of the considered problems in Fig.
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 problem maximizing an information criterion on the probability simplex and which was tackled by FW method in Hendrych et al. (2024). The objective functions of both the 'A' and 'D' criteria are generalized self- celf-conc,,,,nt, not globally smooth, and result in two groups of instances which we denote by "OA" and "OD" respectively.
Portfolio Optimization. We consider a portfolio optimization model with log-revenue similar to Dvurechensky et al. (2023): Carderera et al. (2021 2024). The instances are taken from Carderera et al. (2024) and denoted by "Port". The objective function also (generalized) self-concordant and satisfies the conditions of Remark 3.2
13

---

Secant Line Search for Prank-Wolf
0.07
0.00
vini -0.0
Seowe Methed Stepe
Neston Nitted Sipp
0,00
0.00
0.04
wint (fi ndl d
0.08
Newton Metaod Steps
0.01
-0.15
0.00
0.00
0.5
-0.2
-0.4
-0.00
-0.15
-0.5
2(1) = [fia -40.d) d)
-0.3%
Secart Melhed
Medaed Sope
-0.35
0.0
02
0.4
066
0.8
10
0.0
02
0.6
0.6
0.5
15
(fix ni)l
Stys
Newtzo Melbed Steps
-2.3
0-
-50
-7.
-125
via]
1/i= -d.a))
1500
Sccart Methed Sizpe
Mathed
-15
-17.5
0.0
0.2
1.4
066
0.6
1.0
0.0
0.2
0.4
0..
0.5
1.0
(fix -d).))
Secor Methed Sopp.
Method Sieo
-2
-4
-10
-12
v(+) 3/ -w0).()
Sccani Medaed Stepo
-6-
30-
Stepe
010
022
0.4
0.5
0.5
1.0
00
0.3
0.4
01.
0.5
10
Figure 4. Various runs of SLS with the secant and Newton's 's method. (Top Row) Instances where f is not quadratic function. (Bottom Row) Instances where f is quadratic function.
14

---

Secant Line Search for Prank-Wolfe
Table Comparison of execution times between Secant and Newton's methods for various test functions. Where 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 routine. Timings are averaged over 1000 runs.
Function
Secant Time (s)
Newton's Time (s)
Newton/Secant
f(x) x² -2
3,42c-06
4.32c-05
12.62
f(x) x² -5
3.14e-06
5.47e-05
17.42
f(x) x² 10
2.82c-06
4.13e-05
14.65
f(x) x²2
3.70e-06
4.63e-05
12.52
f(x) x² + 2x -
3,47e-06
4.11e-05
11.85
f(x) x² 2
4.81e-06
4.64e-05
9.65
[(x) ze
1.01e-05
5.89e-05
5.83
f(x) cos( x)
6.39e-06
4.39e-05
6.88
Line Search (quadratic)
1.92e-05
7.97e-05
4.15
Line Search (arbitrary)
3.75e-05
1.24e-04
3.31
Quadratics on the simplex. Ill-conditioned problems are constructed convex quadratic minimization on the simplex with high condition number on the Hessian and denoted "III". Well-conditioned quadratic problems denoted "QuadProb" are built using the squared Euclidean distance to a random point over the simplex.
Optimization on the spectraplex and nuclear norm ball. In order to study the behavior of SLS on non-polyhedral constraint sets, we apply it to matrix completion problems in the symmetric and nonsymmetric cases, i.e., optimizing over the spectraplex and nuclear norm ball and respectively denoted with "Spec" and "Nuclear".
Birkhoff polytope. The problem class "Birkhoff" corresponds minimizing least-square objective the Birkhoff polytope, the convex hull of all permutation matrices of given size.
We compare more siep-size strategies, including the backtracking and golden ratio line-search strategies, the adaptive step size with zero-th order and first-order information from Pedregosa et al. (2020) and Pokutta (2024) respectively, the
monotonic step size designed for generalized self-concordant functions Carderera et al. (2021 2024), and the open-loop agnostic step size of the form
t+2
Figures 5] to 12 present trajectories of the primal value and FW gaps for instances of all problem classes using the different step-size strategies. We notice on the ill-conditioned and simple quadratic problems in Fig. 6 and Fig. 1T respectively that then golden-ratio line search starts with trajectory similar to the backtracking and secant step sizes but start to stagnate due to numerical inaccuracies earlier before reaching the desired FW gap tolerance. This is due to its stopping criterion incurring a higher additive error on the step size.
We primarily used the Blended Pairwise Conditional Gradients (BPCG) algorithm from Tsuji et al. (022 the default active-set algorithm in FrankWolfe ji-for all experiments. Similar to the Away-step Frank-Wole Wolfe (see e.g., Lacoste Julien & Jaggi (013)), it requires step size computed with an exact approximate line search, in particular to ensure accelerated convergence rates in favorable cases (e.g., uniformly convex functions uniformly convex feasible regions). Note that in particular for BPCG the backtracking line search sometimes favorably interacts with the drop step mechanics of the BPCG algorithm, leading unexpected performance improvements.
For completeness, we also present experiments for SLS applied to the standard FW algorithm as implemented in FrankWol fe. jl Fig. and Fig. 15
15

---

Secant Line Search for Frank- Wolfe
0.34
Secant
0.34
Atlattive
Agaoatic
Monotonic
Primal
Golden Ratio
Adaptive
0.38
0.33
Backtracking
100
16
102
103
104
10
-
10
102
104
10-
10-2
-3
10-3
FW gap
10-4
10-5
10 -5
10
10-7
10
10
10
102
103
104
10
100
10a
104
Ittrationss
Time (s)
Figure 5. Progress of the primal value and FW gap for an instance of the Birkhoff problem. The Golden Ratio line search from the FrankNolfe. ji package stalls due numerical issues.
Table Instances of the Birkhoff problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric of the dual gap is only taken over instances that could not be solved up the tolerance. The average number of iterations taken over all solved instances.
Secunt
Adaptivve
Aymostic
Backtracking
Iter per
#
Iter
Iter
Iter
Dim
Time (4)
FW iterations
Time (6)
FW
per
Time (6)
PW iterations
per
Time (s)
FW
per
iterations
iterations
10000
90.3
209.7
19457
36000
70.5
7547
107.0
22500
13835
818.6
22589
30000
4.53e
9123
32.1
40000
1137.4
11965
10.5
1838.5
<16-7
19483
3600UU
8:71e
8392
12.8
62500
10272
<16-7
16295
3601UU
1.28e-00
1130.5
6994
90000
3946
<te-7
9353
36001
2.47x077
3601U11
1.58c-06
4.5
2253,3
7732
16

---

Secant Line Search for Frank-Wolfe
19.9
19.9
Adaptive
Agnostic
Monotonic
Primal
Golden Ratio
Adaptive Zero
Backtracking
19.8
100
10a
102
103
10
10
10
10a
10-2
10-2
FW gap
10
10
10-6
10 2
10-8
100
101
102
103
-4
10-2
100
102
Iterations
Time (s)
Figure Progress primal value gap for an instance of Ill-Conditioned Quadratic problem. For golden ratio line search the same remark applies in the Birkhoff problem (see Fig. 5
Table Instances of Ill-Conditioned Quadratic problem ordered by difficulty. The geometric mean the solving time taken over all instances. The geometrie mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of itcrations taken over solved instances.
Secant
Adaptive
Agnostic
Backtracking
Tter
Iter per
Iter per
Dual
Dual
Dim
Time (s)
FW iterations
per
Time (s)
FW iterations
Time (s)
FW iterations
Time (6)
FW
iterations
<le/7
<le.7
<lc-7
<1e-7
<1e-7
<le-7
<le7
27742
17

---

Secant Line Search for Frank-Wolf
1042
10
Sucant
Adaplive
Aguostic
10-1
Monotonic
Primal
Gulden Ratio
Adaptive Zero
Dacktracking
10
10 14
10-
10
2,000
4,000
6,000
8,000
10,000
106
FW gap
10-1
10-8
10
2,000
4,000
6,000
8,000
10,000
Iterations
Time (s)
Figure 7. Progress of the primal value and FW gap for instance of the Nuclear problem. The secant line search is not only significantly faster than the other methods but also reaches much higher final accuracy.
Table Instances of the Nuclear problem ordered difficulty. The geometric 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 taken over all solved instances.
Adaptive
Agnostic
Backtracking
Dim
Time (s)
FW
per
Time (s)
FW
per sec
Time (s)
per
Time (s)
per
gap
iterations
sec
Sterations
gap
iterations
iterations
2503
0.3
<le-7
511
2555
0.5
<ite-7
E611
3223.0
3630LD
1.34a-4i
5351
3000.0
1.60e-tb
3316.4
10000
1.1
<ie-7
702.6
25011
1.30--01
3161
4060.2
3630D
2.82-04
2550
3400.0
1250.5
32500
Wi1.5
<tei7
1662
2.1
1.4ea001
4ET4
2.2
3600D
3.70-4466
11.00
3400.0
1.12eett
40000
1.38c-01
5.50c400
1.36-01
3630.0
5.712
8.90e
18

---

Secant Line Search for Prank-Wolfe
102
102
Primal
101
10
10
10
10
10
10a
10
10
102
103
105
PW gap
10
Secant
Adaptive
Agnoatic
10-3
10
Golden Ratio
Adaptive Zero
Backtracking
10
10
169
101
10
103
10a
10-4
10-1
102
Iterations
Time (s)
Figure Progress the primal value and FW gap for instance the A-Optimal Experiment Design problem. the agnostic step size the same remark applies as in the D-Optimal Experiment Design problem (see Fig.
Table Instances of the A-Optimal Experiment Design problem ordered by difficulty. The geometric mean of the solving time taken over all instances. The geometric mean of the dual gap only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.
Secunt
Adaptive
Agnostic
Backrackkng
Time
Dual goi
FW Serations
#
Isar per see
Time
Dual gop
FW iterations
Iter scc
Time
Dual gop
FW
Iter per
Time
Dual gup
FW itcrations
Iter
iterations
2013.6 scc
500
100
<3e77
1478.5
350011
6.8Ml
512.2
30000
1
300810
970.5
500
<lc-7
6.47c
7.3x.
401
22/9.1
2536-04
3812
35000
1.84-66
16950
3.50-411
3400.1
100
2689.
<le?
2976
35000
3.54.45
16660
1.26-001
3400.0
1:8c-th
107
35656
2.
3240
0.7
350001
2.15e 01
36000
2.55 I1
30
2441/)
1.71e -6
500
38000
8:13:-13
38000
4.53-01
36000
3.50e-01
3600.0
1.4e-16
0.6
1000
3600
9.41:-02
38000
3.te-01
044
36000
4.63c-01
1.3
3600.0
4.75-404
0.5
19

---

Secant Line Search for Frank-Woon
0.22
0.22
Primal
0.18
0.18
100
10a
10a
108
10
10
102
16
109
FW gap
10-2
Secant
0000000
10
Adaptive
Agnostic
10
Monatonic
Golden Ratio
Adaptive
10-6
Backtraeking
10
200
104
102
10
10
102
10a
Iterations
Time (s)
Figure Progress the primal value and FW gap for an instance D-Optimal Experiment Design problem. significant uptick in the primal value for the agnostic is expected (a) the agnostic step size does not guarantee primal progress in contrast to the other step sizes used here and (h) the agnostic step size strictly speaking cannot be applied to the D-Optimal Experiment Design problem (Hendrych) et al. 2024) 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 Instances of the D 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 only taken over instances that could not solved up to the tolerance. The average number of iterations is taken all solved instances. Brackets indicate that all instances basically solved up the tolerance up to some numerical error.
Secant
Adaptive
Agnostic
Hackracking
Dual EdР
#
Iter per sec
Dual gap
#
lter per sec
Dual SAI
#
lter per sec
Dual gap
ler
FW
FW
FW
par
Sterations
iterations
iterations
iterations
sec
100
<le-7
305
1530L0
<ie-7
653
2176.7
3061.6
[xle
240
2523.4
6.1
<le-7
219
2190,0
201
<le-7
439
417.3
<te-7
915
653.6
36000
2.34e
948.5
<le.T
376
470.0
[ste-]]
15.4
[<te-7]
500
8.00c005
101
724.1
<lo-7
15211
16000)
4 4.10-04
S36.
<1a-7
932
100
1066.7
<le.7
1095
LD
1268.)
<le.
1986
3600D
546e
2.5
354.
<1o-7
998
1.1
500
1881,
[<le-7]
1228
2252.9
<le-
2117
3600D
9.55 04
1.3
1294.8
<la
1131
100
3413.0
8-85-415
1354
3180
2012
0.7
S600D
1.0005
1.0
199.1
<le7
1199
0.6
20

---

Secant Line Search for Frank-Waud Wolfe
20
20
Adaptive
Agnostic
Monotonic
Primal
Golden Ratio
Adaptive Zero
Backtracking
10
10
5
5
10
10a
10a
103
104
10
10"
100
10
101
10-2
FW gap
B
Wmwmp
10-5
10-3
10-8
10-8
100
101
102
104
104
10-4
10-2
10
10
Iterations
Time (s)
Figure 10. Progress of the primal value and FW for an instance of the Portfolio problem.
Table Instances of Portfolio problem ordered by difficulty. The geometric mean of solving time is taken over instances. The geometric mean of the dual gap is only taken over instances that could not be solved to the tolerance. The average number of iterations taken over solved instances.
Secant
Adaptive
Agnostic
Backtracking
Dim
Time
Dual gap
FW iterations
Iter per sec
Time
Dual gap
FW iterations
Tter S0C
Time
Dual gap
FW iterations
Fter
Time (8)
Dual gap
FW iterations
#
Iter 50c
sec
608.4
1267
<le-7
<1e-7
21

---

Secant Line Search for Prank-Wolfe
1033
10a
Sccant
Adaptive
Agnostic
Monotanle
Golden
Adagtive
Ratio
7am
10
Backtracking
Primal
10
10-7
10-12 12
10-12
1. 10
10
20
104
10a
10
10
FW gop
10-3
10-5
10-5
10
20,0000
000
60,000
10.000
1- 10
Iterations
Time (8)
Figure 11. Progress of the primal value and FW gap for instance of the Simple Quadratic problem.
Table Instances of the Standard Quadratic problem ordered by difficulty. The geometric mean of the solving time taken over all instances. The geometric mean of the dual gap 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
Agnosric
Backtracking
Dual gap
Iter
Dual
lter
Dual gap
lter
Dual
her
Dim
Time
FW
Time
FW
Time
FW
Time
FW
115TUL
126033
13W81
6.8
<cl-7
52545
471K3
19300
3.456407
311K.5
<clo7
51385
3367.5
12913
10900
1:92--04
2.4
16000
3.1ke-b6
333
39900
1.346-81
10.0
5600.
5.tte-isi
3.5
40000
360000
2:10c-04
2.5
36000
2.45e
36000
2.32c
9.7
3600.
5.77c-uu
3.8
1.30e-04
5600/0
5.104444
1.50e.04
22

---

Secant Line Search for Prank-Wolf
Secant
Adaattive
Agnostic
Monotonic
Primal
Golden Ratio
Adaptive Zero
0.99
Backtracking
B BEERG HPXI
100
16a
104
103
104
10
10
10A
10
104
104
10-1
10
FW gap
10-3
10
10-5
10-5 5
10
10-7
100
10
10
103
10
10-3
10
16
103
Iterations
Time (s)
Figure 12. Progress primal value and gap for instance of the Spectrahedron prohlem.
Table 10. Instances of the Spectrahedron problem ordered by difficulty. The geometric 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.
Adaptive
Agmostic
Backsracking
Iter
Dual gup
Iter per
Dual gap
Iter per
Time (s)
per sec
(4)
(4)
(s)
per
gap
Elcrations
itcrations
soc
itcrations
soc
gap
ilrratonss
10000
8.4
<ic-9
454
1135.0
0.4
<dc-7
435
1067.5
2.5
<ie-
F1323
6029.2
<1e-
4818
2056.2
41000
26.3
<te-1
atl
15.2
28.2
<16-7
385
13.7
76.6
<1e-7
51.4
80.3
<te-7
18.2
50000
<le/
<la/
250000
33
18930
11.4
188
<lc-7
$219
133640
3462
356.6
<16-7
1972
45020
312.5
1.76-8
0.5
357.5
4.962-07
6160
1656-00
577.]
1.108:06
0.4
64900
7K3
<ie3
0.1
1002
<1c-7
8.1
3941
531640
0.3
678.5
143--0
112
0L3
110000
535.
<le7
987.4
<16-7
1000
3.85c:00
36000
1.0000
L.65077
14613
231c-06
23

---

Secant Line Search for Prank-Wolfe
Step den
Stop saa
Step
10-11
Adogezoo
ton3
Adaptiv
Adageiso
Bacatione
Itacations
Docatione
(a) Birkhoff Problem
(h) III Conditioned Quadratic
(c) Nuclear
10
10-3
Shop
Stap
Srop
13-4
10-11
Adaptive Secunt
Adsgeiv
10-1
Serant
10a
10'
107
10
101
10
Rrenatioss
Trenatioss
Tieeatioee
(d) A-Optimal Experiment Design
(e) D-Optimal Experiment Design
(f) Portfolio
20-1
Stop A6e
10-9
Malptive
10:4
Adaptiive
Secaul
Secuut
6P
11.
Teeratioss
(g) Simple Quadratic
(h) Spectrahedron
Figure 13. Computed step sizes over iteration for the Secant line search and Adaptive line search various problem classes.
24

---

Secant Line Search for Frank- Wolfe
1013
1012
Becaus
Agoostie
19
Golden Ratlo
Aduptive
Backtracking
10-14
10-14
2,000
4,000
6,000
10,000
2618
304
FW
10-1
se04e
10
10
10
Berations
Time
Figure 14. Progress of primal value and FW gap for instance of the Nuclear problem using Vanilla Frank Wolfe.
0.90
Adaption
0.59
Aguostic
Menotonie
Primal
0.99
Golden Batio
0.99
Adaptive
Backtracking
0.90
0.99
0.90
8-
0.59
E 2--BBIBB
1.00
101
103
10
160
304
102
105
104
10--
gAp
10-
10
10-8
100
102
10
104
100
10A
102
163
Berations
Time
Figure Progress of the primal value and FW gap for instance of the Spectrahedron problem using Vanilla Frank-Wolfe Wolfe.
25


Reviews:
[{"review_id": "xYF9JFuKNy", "reviewer": "Reviewer_vWCY", "summary": "This paper suggests that in Frank-Wolfe algorithm, one can use the Secant Method to set the step size for performance improvement.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Line 159, left column: $S(x,y) = S(y,x)$ is not true.\n\n$ S(x, y) = S(y, x) $ holds. Writing the definition and multiplying by $\\Delta(x, y) = \\Delta(y, x)$ and reorganizing, we obtain that the expression is equivalent to $ (x-y)\\Delta(x,y) = \\phi(x) - \\phi(y) $, which clearly holds true by definition of $ \\Delta(x, y) $\n\n> Proof of lemma 2.1 is dubious: by what monotonicity can one claim that $\\frac{\\Delta(x,a)}{\\Delta(x,y)} > 0$? Also, the argument for $<1$ part is also shaky.\n\nThe monotonicity of $\\phi$, as assumed in the statement, trivially implies that $\\Delta(z, w) > 0$, for all $z, w \\in \\mathcal{U}$ as by definition monotonicity means $\\phi(z) - \\phi(w) > 0$ if $z - w > 0$.\nOur proof is correct, see also the response to Reviewer bzSe.", "claims_and_evidence": "Line 159, left column: $S(x,y) = S(y,x)$ is not true.\n\nProof of lemma 2.1 is dubious: by what monotonicity can one claim that $\\frac{\\Delta(x,a)}{\\Delta(x,y)} > 0$? Also, the argument for $<1$ part is also shaky.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "sNmZpPrlnS", "reviewer": "Reviewer_dXfc", "summary": "The paper introduces a novel step-size strategy for Frank-Wolfe (FW) algorithms called Secant Line Search (SLS), which utilizes the secant method to determine step sizes efficiently.  SLS requires only function and gradient evaluations, making it computationally less expensive while adapting to the local smoothness of the function. The authors establish theoretical guarantees for convergence. Empirical results across various constrained optimization problems show that SLS achieves faster convergence and reduced computational in general.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and questions.\n\n> Limited theoretical novelty. The convergence guarantee is derived by directly combining the existing convergence results of the Frank-Wolfe method and the secant method.\n\nThe theoretical novelty is indeed not the central element here, however in contrast to gradient descent methods where there it is hard (if not next to impossible) to make the secant method work consistently as a line search, in the context of Frank-Wolfe the Secant Line Search actually becomes a valid line search method. So the contribution here is really showing that in the settings were FW methods are usually applied we have a global theoretical guarantee that the secant method works. \n\n> Evidence of claims (more convincing if references about the convergence of the Frank-Wolfe method were added in Theorem 3.1). (the linear convergence mentioned in lines 287–288 and the superlinear convergence in Remark 3.2 are not supported by proofs or references)\n\n We did not include an in-depth discussion about the local convergence of the secant method because it is not the main focus of the paper and has been established elsewhere. In fact, we cited Díez 2003 who provided an in-depth analysis and provided the convergence rate inducing equation $\\lambda^m + \\lambda^{m-1} = 1$, where m is the multiplicity of the root; $\\lambda$ is then the rate we can expect. What we did provide though is a proof for the *global convergence* in common FW settings, which is the key crux for the secant method as it is not a globally convergent method in general. This way we can ensure that the secant method can be used as line search method.\nWe will restate the Theorem etc to make this more clear.\n\n> Self concordance \n\nThe self-concordant property is defined in (3.5), we will rephrase to make this more clear and will reference this in the introduction.\n\nTo sum up, our main contributions are (A) we perform comprehensive experiments on the secant line search in a wide variety of benchmarks and against a wide variety of alternative step-sizes showing its advantages over previous approaches and (B) we observed that the structure of the FW algorithm is such that under mild assumptions it is always guaranteed to converge from any initialization (and the line search always occurs over a compact segment), which justifies that our method works in practice.", "claims_and_evidence": "Please refer to the \"Other Strengths And Weaknesses\" section.", "methods_and_evaluation_criteria": "Please refer to the \"Other Strengths And Weaknesses\" section.", "theoretical_claims": "Please refer to the \"Other Strengths And Weaknesses\" section.", "experimental_designs_or_analyses": "Please refer to the \"Other Strengths And Weaknesses\" section.", "relation_to_broader_scientific_literature": "Not sure.", "essential_references_not_discussed": "Please refer to the \"Other Strengths And Weaknesses\" section.", "other_strengths_and_weaknesses": "Strength:\n\n1. Empirical results demonstrate the effectiveness of the proposed line search method.\n\n\nWeakness:\n\n1. Limited theoretical novelty. The convergence guarantee is derived by directly combining the existing convergence results of the Frank-Wolfe method and the secant method.\n\n\n2. Claims are not supported by sufficient evidence. It would be more convincing if references about the convergence of the Frank-Wolfe method were added in Theorem 3.1. Additionally, the ``linear convergence'' mentioned in lines 287–288 and the ``superlinear convergence'' in Remark 3.2 are not supported by proofs or references.", "other_comments_or_suggestions": "1. The paper would be easier to understand if the related work section were moved after the introduction of the secant method.\n\n2. Lines 40–48 are difficult to follow because they rely on techniques defined later in the paper.\n\n3. The self-concordant property is not defined.", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C1NiKFwPnB", "reviewer": "Reviewer_bzSe", "summary": "This paper proposes Secant Line Search (SLS),  a new step size strategy for Frank-Wolfe algorithms, by posing line search as root finding and using the secant method to solve it. The method is simple and easy to implement. The same principle can seemingly be applied in line search for algorithms other than Frank-Wolfe. The strategy is validated through numerical experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and questions on the paper.\n\nWe agree that using root finding methods for line search is not new and in fact many line search methods, such as e.g., bisection line search is of that type. However, (Quasi-)Newton methods, secant methods, etc are traditionally *not* used as line search methods because in general there is no guarantee that they are globally converging. Put differently, *if* they converge they are fast but they may not converge at all. This is different here where we actually proved that in the setting of FW methods, where the step size is guaranteed to be confined between 0 and 1 (or 0 and a weight smaller than one for some FW variants), we *can* guarantee global convergence under mild assumptions that are often satisfied in contexts where FW methods are applied: we only require strict convexity. \n\nIn Lemma 2.1, we do not show convergence by just saying that this property holds:  $ 0 < S(x,y) < 1 $. As it can be read at the end of our proof, we have instead that by $ x_{n+1} = S(x_n, x_{n-1}) $ and by that property then $ x_n -x_{n+1} $ converges to $0$. And because it is by definition $ \\phi(x_n) / \\Delta(x_n, x_{n-1}) = x_n - x_{n+1} \\to 0 $ and $\\Delta(x_n, x_{n-1})$ is upper bounded by a constant, it can only be that $ \\phi(x_n) \\to 0 $ and that can only be if $x_n \\to a$, as specified in our proof.\n\nQuestion 3: We present each problem class in more detail, including the type of constraint set in the appendix due to space constraint. Our benchmark problems contain standard problems from the Frank-Wolfe literature, e.g. similar to some classes studied in Pedregosa et al 2018, Dvurechensky et al 2023, Carderera et al 2021 which all introduce new step-size strategies for FW. We were also careful to include different function classes (self-concordant, quadratics) and conditioning to be able to showcase the performance of SLS in a wide array of applications. \nFurthermore, our experiments assess multiple criteria for the proposed step size:\n1. Is it making FW converge fast, as counted by the number of iterations? This question will typically have the same answer for all line searches given infinite precision (e.g. using arbitrary-size floating point numbers or rational arithmetic). However, when using 64-bit floating points, we showed that great differences can occur in behavior because of floating-point error accumulation, see Figure 5 in the appendix, in which golden ratio, another line search, quickly stalls in terms of FW gap precisely because of numerics. In contrast, we empirically observe the numerical robustness of SLS, even in ill-conditioned problems (when the Lipschitz constant is very high).\n2. Is the method also effective in time, meaning that the good performance of the step size is not outweighed by the computational cost of the inner iterations evaluating the gradient at the candidate point?\n\nWe answer both questions positively thanks to the computational experiments, evaluating the methods against iterations and time. We also compute the number of inner line search iterations throughout the Frank-Wolfe runs, empirically showing this remains consistently low throughout experiments. This ensures that SLS is also a suitable step size for problems where the gradient is particularly costly to evaluate (relative to the LMO).\n\nQ1: SLS shows superior performance on all problems with a quadratic objective function. It, in particular, shows stable performance even for ill-conditioned problems.\nAdditionally, we also see a good performance on generalized self concordant objectives like the A-Optimal and D-Optimal Design problems and the Portfolio problem with log revenue. \n\nQ2: Frank-Wolfe is stopped if we reach either the dual gap of 1e-7 or a time of 1 hour (we will state this explicitly in the paper). The different strategies lead to different trajectories of Frank-Wolfe hence the different end points. Since there is a time limit, the dual gap value is of interest for the unsolved instances as we can compare how much progress each method obtained within the time. In the table, the geometric mean of the dual gap is only computed for the unsolved instances. \n\nThe tolerance in the line search corresponds to one on the univariate derivative, which directly leads to a bounded function error ($\\gamma \\in [0,1]$). Others, e.g. Pedregosa et al 2020, Bomze et al 2019 have studied approximate LS for FW. We will highlight these references in the revised version.\n\nTo sum up, our main contributions are (A) we perform comprehensive experiments on the secant line search in a wide variety of benchmarks and against a wide variety of alternative step-sizes showing its advantages over previous approaches and (B) we observed that the structure of the FW algorithm is such that under mild assumptions it is always guaranteed to converge from any initialization (and the line search always occurs over a compact segment), which justifies that our method works in practice.", "claims_and_evidence": "As I understand it, the paper lists three contributions: proposing a new step size strategy based on the secant method, providing theoretical guarantees for this strategy when coupled with the Frank-Wolfe algorithm and demonstrating that the new strategy outperforms standard ones used for Frank-Wolfe.\n\nBased on my assessment, I believe that only the last contribution may be substantiated. \n\nI think that using the secant method for line search is not a new idea, if that was what the authors meant. For example, Chapter 7 in (E.K.P. Chong and S.H. Zak. An Introduction to Optimization. Fourth edition. Wiley, 2013) makes an explicit connection between line search and one-dimensional search methods such as the secant method. This connection is also mentioned in lectures notes such as https://www.princeton.edu/~aaa/Public/Teaching/ORF363_COS323/F14/ORF363_COS323_F14_Lec7.pdf\nand some post at https://math.stackexchange.com/questions/3785724/line-search-using-secant-method\nPlease correct me if I misunderstood this but, to the best of my knowledge, this does not count as a contribution.\n\nIt also seems to me (see Theoretical Claims) that there may be an issue with the proof of lemma 2.1, which is the foundation of the further theoretical results. In any case, since SLS is not an exact line search, I think it would be important to establish a relationship between epsilon in the stopping criterion and the step size produced by SLS, and also its implications for convergence rates.\n\nFinally, the paper does present empirical evidence that the method does work well in practice, but I think a more thorough discussion and clearer presentation of the results are required. First, in my view it would be much more informative if the results were grouped by problem in different subsections of the Computational Experiments section. Then, each problem could be presented in more detail, for example writing the objective function and/or describing the compact convex set on which each problem is defined as readers might not be familiar with typical benchmark problems for Frank-Wolfe. In this vein, it would be helpful to elaborate on what makes a good benchmark for Frank-Wolfe methods, which properties are stress-tested by which problem objectives, data and constraints. This would also help to delineate the problem setting in which SLS works best. Also, there could be an explicit mention of how the initial point of each problem instance was chosen and why, which I could not find in the paper. Finally, each subsection could contain a plot or a succinct table clearly conveying how SLS fares with respect to other methods.", "methods_and_evaluation_criteria": "Yes, the evaluation criteria make sense, but I’m not sure how comprehensive the experiments are because I’m not very familiar with Frank-Wolfe literature", "theoretical_claims": "Lemma 2.1: don’t you have to show the ratio (S(x,y)-a)/(x-a) < 1-delta for some delta in (0,1)? Counterexample: if x_{n}=a+eps+(½)^{n} with small eps in (0,1), then 0< (x_{n+1}-a)/(x_{n}-a)=(eps+(½)^{n+1})/(eps+(½)^{n}) < 1, but x_{n} converges to a+eps>a. I don’t know if it’s possible to find some phi such that secant method produces the above x_{n+1}, but the point is that the condition that 0 < (S(x,y)-a)/(x-a) < 1 is not enough to prove that x_{n} and phi(x_{n}) converge to a and phi(a).\nThe local convergence analysis (section 2.2) assumes phi’(a) is nonzero, but SLS approximately finds precisely the point where the derivative of f(x_{t} - gamma * d_{t}) w.r.t. gamma is zero. Is it possible to overcome this assumption?\nSince the critical point of f(x_{t} - gamma d_{t}) in terms of gamma is only solved approximately, it would be useful to understand the relationship between the approximation error epsilon and the actual convergence rate obtained with the SLS step size.", "experimental_designs_or_analyses": "I checked the experiments and they look sound, but I think their presentation could improve by a lot, as remarked above.", "relation_to_broader_scientific_literature": "The idea of using the secant method as a line search procedure could be more broadly applicable beyond Frank-Wolfe algorithms, but it seems that this idea is not new.", "essential_references_not_discussed": "As referenced above, for example in chapter 7 of (E.K.P. Chong and S.H. Zak. An Introduction to Optimization. Fourth edition. Wiley, 2013), using the secant method for line search does not seem to be a novel idea and it would be important to explain in detail what is novel in SLS with respect to previous work.", "other_strengths_and_weaknesses": "The argument used in the proof of lemma 2.1 is nice, although I believe there is still some work to be done.", "other_comments_or_suggestions": "Minor:\nThe contribution paragraph \"New step-size strategy\" makes reference to some requirements that are described in the second paragraph of the Related Work section. Readers that skip the text before the contributions would not understand what the authors mean.\nI would use a different font size for the contribution paragraphs and Preliminaries and Notation.\nRecent approaches (e.g. https://arxiv.org/pdf/1905.09997) using stochastic line search in the context of neural networks also go by the name of SLS. FW and NN are probably sufficiently separated that this won’t cause any confusion, but I just wanted to let the authors know.\n(Line 162, second column) The last sentence of the last paragraph of the second column on pg. 3 can be written more clearly, e.g., \"x lies between the points a and y, and the differences delta(a,x) and delta(x,y)\"\n(Line 303, second column) The acronym BPCG is used here, but only defined later on line 706.\nMaking the plot colors darker (e.g. green and darkorange) in Figure 1 would make them easier to see.\nStarting the discussion in section 4 with step size and iteration count remarks is distracting, I think the actual performance results should come first. That is, I think Table 1 and Figure 3 should come before Figures 1 and 2. First, you present empirical evidence that SLS works well through Table 1 and Figure 3 and then you could hypothesize why based on the step size and line search information conveyed by Figures 1 and 2.\nTable 1 could have an extra \"gain\" column quantifying the performance gains/losses of SLS with respect to the best performing method among the remaining methods. Also, if a method is not able to reach the desired precision, it might be better to simply apply a different color to the performance metrics or highlight them somehow in that particular problem instance rather than reporting the dual gap, which is confusing. In particular, it seems that the results of the best performing method are reported in bold font, but shouldn’t these only include methods that actually reached the desired precision?\nFor problems in which the primal gap is not zero, I would suggest plotting primal-primal* in log scale instead of primal in linear scale, where primal* is the least primal gap found by all methods.\n\nTypos:\n(Line 64, first column) The three types of step-size strategies for FW have inconsistent numbering: (1), (ii), (iii)\nIs gamma_{a}=gamma_{\\ast}?\n(Line 328, first column) Is the phrase “Nonetheless, the same analysis can be applied to these methods as well by carrying out over the.”” complete?", "questions_for_authors": "1. On which problems SLS outperforms other line search methods?\n2. What was the stopping criterion used in the experiments? For example, in Figure 3a Adaptive FW and SLS seem to stop at somewhat arbitrary points.\n3. What makes a convincing benchmark for FW? What are the features that good experiments should capture?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y3qkcDr9la", "reviewer": "Reviewer_rqBT", "summary": "This paper introduces a new step-size strategy, the Secant Line Search (SLS), to optimize the Frank-Wolfe (FW) algorithm. SLS leverages the secant method to solve the line search problem, which reduces the computational cost compared to traditional methods. Theoretical guarantees for SLS’s convergence are provided, and numerical experiments show its superiority over other commonly used step-size strategies in terms of both computational performance and convergence speed.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and questions.\n\n> The paper lacks a detailed complexity analysis for the proposed methods.\n\nWe provide an analysis of the local superlinear convergence rate of the secant method and of its global convergence under suitable assumptions, which is an improvement over what can be stated in the unconstrained case, specifically relying on the setup of Frank-Wolfe algorithms in which the line search happens on a bounded line segment. This superlinear convergence guarantees that in practice, we perform an almost exact line search while remaining highly tractable, as can be noticed from the low number of secant iterations. We must highlight that our results are agnostic to the optimization problem, the precise convergence rate will depend on local properties of the function.\n\n> In Lemma 2.1, the convergence guarantees rely on assumptions that seem quite strict, which may limit the broader applicability of the method.\n\nThe assumption might not be as strict as they seem; see Theorem 3.1. It suffices that the problem is strictly convex. \n\n> The analysis in Section 2.2 raises some concerns, as the symbol \"≈\" is used frequently. This could suggest a lack of rigor in the analysis.\n\nWe use \"≈\" to ignore lower order terms for the sake of clarity. Specifically the contents of section 2.2 are provided for intuition, since it is folklore and the proof of this specific case is known and can be found, e.g., in Grinshpan (2024).\n\nTo sum up, our main contributions are (A) we perform comprehensive experiments on the secant line search in a wide variety of benchmarks and against a wide variety of alternative step-sizes showing its advantages over previous approaches and (B) we observed that the structure of the FW algorithm is such that under mild assumptions it is always guaranteed to converge from any initialization (and the line search always occurs over a compact segment), which justifies that our method works in practice.", "claims_and_evidence": "The authors provide both theoretical analysis and experimental results to confirm their claim that SLS is computationally efficient and improves the convergence of Frank-Wolfe algorithms.", "methods_and_evaluation_criteria": "The proposed method, Secant Line Search (SLS), is a feasible approach to the Frank-Wolfe algorithm’s step-size problem. The evaluation criteria used for the experiments (such as the number of iterations and computational time) are appropriate and align with typical benchmarks in optimization problems.", "theoretical_claims": "Theoretical guarantees for the SLS strategy are provided and are supported by lemmas and theorems, including Lemma 2.1 and Theorem 3.1.", "experimental_designs_or_analyses": "The experimental designs are sound, comparing SLS against other step-size strategies across a wide range of problems. The authors present results from several problem classes, demonstrating the practical applicability and efficiency of SLS.", "relation_to_broader_scientific_literature": "The key contributions of the paper relate well to the broader literature on optimization algorithms, particularly the Frank-Wolfe method.", "essential_references_not_discussed": "The authors do a good job of citing the relevant works in optimization and Frank-Wolfe algorithms.", "other_strengths_and_weaknesses": "Strengths:\n1. The proposed method addresses the step-size selection problem in a way that largely reduces the computational cost of the Frank-Wolfe algorithm while maintaining good convergence properties. \n2. The experiments provide evidence of its effectiveness, particularly in terms of the number of iterations and overall computational time.\n\nWeaknesses:\n\n1. The paper lacks a detailed complexity analysis for the proposed methods, particularly in terms of sample complexity. For instance, how many gradient computations are required to achieve an $\\epsilon$-optimal point? A more formal analysis would offer better insights into the theoretical performance of SLS.\n  \n2. In Lemma 2.1, the convergence guarantees rely on assumptions that seem quite strict, which may limit the broader applicability of the method.\n\n3. The analysis in Section 2.2 raises some concerns, as the symbol \"≈\" is used frequently. This could suggest a lack of rigor in the analysis.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See the Weakness part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The main contribution of this paper is to show that the secant method enjoys global convergence guarantees for the line-search step of the Frank-Wolfe method. The method is easy to implement and efficient, as validated through numerical experiments. While some reviewers raised limited theoretical novelty as a concern, I do not consider it as substantially limited; I find it interesting that a simple and overlooked mechanism can, in fact, provide an effective solution for the line search of the Frank-Wolfe algorithm. On the negative side, the analysis relies on a strict convexity assumption which limits its applicability and relevance. I strongly recommend the authors to follow the suggestions raised by the reviewers to further improve the presentation quality.
Decision: Accept (poster)