<figure><img src="image_1.png" /></figure>

HAL
open science

Secant Line Search for Frank-Wolfe Algorithms

Deborah Hendrych, Sebastian Pokutta, Mathieu Besançon, David Martínez-Rubio

► To cite this version:

Deborah Hendrych, Sebastian Pokutta, Mathieu Besançon, David Martínez-Rubio. Secant Line Search for Frank-Wolfe Algorithms. ICML 2025 - Forty-Second International Conference on Machine Learning, Jul 2025, Vancouver (BC), Canada. pp.1-22. hal-05086780

HAL Id: hal-05086780

https://hal.science/hal-05086780v1

Submitted on 8 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Secant Line Search for Frank-Wolfe Algorithms

Deborah Hendrych*¹² Sebastian Pokutta*¹² Mathieu Besançon*³ David Martínez-Rubio*⁴

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.

# 1. Introduction

We are interested in solving constrained optimization problems of the form

$$ \min_{x \in \mathcal{X}} f(x) \qquad (1.1) $$

with a first-order method, relying only on gradient and function evaluations, where $f$ is a smooth function and $\mathcal{X}$ is a compact convex set onto which projection is potentially expensive. In this case, variants of the Frank-Wolfe (FW) algorithm (Frank & Wolfe, 1956; Levitin & Polyak, 1966) are a popular choice. One operation required for most FW variants is a choice of a step size to update the iterate $x_t$ along a descent direction. We present a 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

subproblem's function evaluations are available to us, which corresponds to computing partial derivatives of $f$, making the secant method (instead of the Newton-Raphson method) the natural choice.

Related Work

There is an abundance of work on line search strategies for optimization, as step-size rules can significantly impact the performance of optimization algorithms, both computationally 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 & Wright, 1999)). A notable recent example is the Silver Step-size Schedule (Altschuler & Parrilo, 2023; 2024a;b), which achieves partial acceleration for smooth convex optimization via standard gradient descent. Here, we will only provide a brief overview of the prior works most closely related to ours.

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 to the local smoothness of the function). As a 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, Malitsky & Mishchenko (2020; 2023) made significant progress in this direction by providing an adaptive step-size strategy that does not perform line search, satisfying all three requirements. This sparked a lot of interest, with alternative approaches (see e.g., Zhou et al. (2024) based on the Barzilai-Borwein two-point step-size (Barzilai & Borwein, 1988)) being analyzed. These approaches estimate the inverse of the local Lipschitz smoothness constant via two points $x, y$ as $\frac{\|x-y\|}{\|\nabla f(x)-\nabla f(y)\|}$ and then use this (with modifications) as the step-size $\gamma_t$ for an update of the form $x_{t+1} \leftarrow x_t - \gamma_t \nabla f(x_t)$. A close inspection reveals that this is effectively a modified (higher-dimensional) secant step. The resulting step-size strategy performs well computationally 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 convergence of the iterates to the optimal point. This, however, is not necessarily given for Frank-Wolfe algorithms (Bolte

<footnote>*Equal contribution †Zuse Institute Berlin, Berlin, Germany ‡Berlin Institute of Technology, Berlin, Germany §Université Grenoble Alpes, Inria, Laboratoire d'Informatique de Grenoble, Grenoble, France ||Signal Theory and Communications Department, Carlos III University of Madrid, Madrid, Spain. Correspondence to: Sebastian Pokutta <pokutta@zib.de>, Mathieu Besançon <mathieu.besancon@inria.fr>, David Martínez-Rubio <dmrubio@ing.uc3m.es>.</footnote>
et al., 2024), due to their affine-invariance. 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-Wolfe 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.

Step-size strategies for Frank-Wolfe 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
$\gamma_t = \frac{\ell}{\ell+t}$ with $\ell \ge 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., 2023; 2024)) (ii)
so-called short-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. (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., 2021; 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 Pedregosa et al.
(2020); Pokutta (2024) test that a local Lipschitz smooth-
ness estimate produces a 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.

Other notable recent approaches in the context of uncon-
strained optimization include speeding up the backtracking
search with an adaptive retraction (Cavalcanti et 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-Newton methods do not

apply here. Stabilization of locally convergent algorithms
has been a 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 (SLS)*, 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-listed requirements for a step size due to its search-type nature, the iteration count is 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 Frank-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.

**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 often very fast, is not necessarily convergent. However, due to the special structure of FW algorithms that do not follow the gradient but use alternative directions of the form $x_t - v_t$, cf. Algorithm 1, the solution to the line search problem is confined to a bounded interval $[0, \gamma_{\max}]$. Exploiting this property, we can guarantee convergence under mild assumptions in Lemma 2.1 and Theorem 3.1.

**Numerical experiments.** We provide extensive numerical experiments demonstrating the superior computational performance of SLS over other step sizes. We also discuss implementation enhancements that further reduce computational costs, making SLS a 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 to 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 algorithms 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.
## Preliminaries and Notation

We use bold-faced letters $x$ to denote vectors and non-bold-faced letters $x$ to denote scalars. Throughout the paper, we will use $t$ 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 $\|\cdot\|$ denote the Euclidean norm and $\langle \cdot, \cdot \rangle$ the standard inner product.

## 2. The Secant Method

The Secant Method (see e.g., Papakonstantinou & Tapia (2013)) is a well-known method for finding the root of a function $\varphi: \mathbb{R} \to \mathbb{R}$. It is based on the recursion:

$$x_{n+1} \leftarrow x_n - \varphi(x_n) \cdot \frac{x_n - x_{n-1}}{\varphi(x_n) - \varphi(x_{n-1})}, \quad (2.1)$$

with initial values $x_0, x_1$ chosen appropriately. We can think of the secant method as an approximate version of Newton's method, which uses the update

$$x_{n+1} \leftarrow x_n - \varphi(x_n) \cdot \frac{1}{\varphi'(x_n)} \quad (2.2)$$

using the approximation:

$$\varphi'(x_n) \approx \frac{\varphi(x_n) - \varphi(x_{n-1})}{x_n - x_{n-1}}. \quad (2.3)$$

The secant method predates Newton's method by over 3000 years (Papakonstantinou & Tapia, 2013).

One should think about $\varphi(\gamma) = f(x_t - \gamma \nabla f(x_t))$ in our application. Before considering the line search problem, we establish global convergence when the absolute value of the derivative of the function $\varphi$ is increasing as we move away from the root, e.g., if $\varphi''\varphi > 0$. We also recall the convergence rate of the secant method near the root. The latter is folklore and many different proofs exist, we provide a 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 section we assume that $\varphi$ is a smooth function and sufficiently differentiable.

### 2.1. Global Convergence

In general, the secant method is not globally convergent. However, we can show that under suitable assumptions, the secant method converges monotonically to a root in cases relevant for our line search problem. To simplify the exposition, we introduce the notation $\Delta(x, y) \doteq \frac{\varphi(x) - \varphi(y)}{x-y}$ and $S(x, y) \doteq x - \frac{\varphi(x)}{\Delta(x, y)}$, so that the secant method can be written as:

$$x_{n+1} \leftarrow S(x_n, x_{n-1}) = x_n - \frac{\varphi(x_n)}{\Delta(x_n, x_{n-1})}. \quad (2.4)$$

Clearly $\Delta(x, y) = \Delta(y, x)$. Further, observe that $S(x, y) = x - \frac{\varphi(x)}{\Delta(x, y)} = y - \frac{\varphi(y)}{\Delta(x, y)} = S(y, x)$. We will now establish a first convergence result of the secant method.

**Lemma 2.1.** Let $a$ be a root of $\varphi: \mathbb{R} \to \mathbb{R}$ and let $\mathcal{U}$ be a one-sided neighborhood of $a$. Further assume that $|\varphi'(x)|$ is strictly increasing in $|x-a|$ with $x \in \mathcal{U}$, i.e., as we move away from $a$; in particular $a$ is the only root on $\mathcal{U}$ and $\varphi$ is monotone on $\mathcal{U}$. Then, we have:

$$0 < \frac{S(x, y) - a}{x - a} < 1,$$

for all $a \neq x, y \in \mathcal{U}$, i.e., the distance to $a$ is strictly decreasing.

*Proof.* Note that $\varphi(a) = 0$ and let $x, y \in \mathcal{U}$ be arbitrary with $x, y, a$ all distinct. We differentiate the following two cases.

*Case 1:* $|x-a| < |y-a|$, i.e., $x$ is closer to $a$. Observe that we have:

$$\begin{aligned} \frac{S(x, y) - a}{x - a} &= \frac{x - \frac{\varphi(x)}{\Delta(x, y)} - a}{x - a} \\ &= 1 - \frac{\varphi(x) - \varphi(a)}{\Delta(x, y)(x - a)} = 1 - \frac{\Delta(x, a)}{\Delta(x, y)}. \end{aligned}$$

By monotonicity $\frac{\Delta(x, a)}{\Delta(x, y)} > 0$. Moreover, since $|\varphi'(x)|$ is strictly increasing as we move away from $a$ in $\mathcal{U}$, we have $\Delta(x, a) < \Delta(x, y)$, so that $0 < \frac{S(x, y)-a}{x-a} < 1$ follows; this also implies that we do not leave $\mathcal{U}$ and stay on the same side of $a$ as $\frac{S(x, y)-a}{x-a} > 0$

*Case 2:* $|x-a| > |y-a|$, i.e., $y$ is closer to $a$. Similar as before after factoring out $\frac{y-a}{x-a}$ and using $S(x, y) = S(y, x)$ we similarly obtain:

$$\begin{aligned} \frac{S(x, y) - a}{x - a} &= \frac{y - a}{x - a} \cdot \frac{y - \frac{\varphi(y)}{\Delta(x, y)} - a}{y - a} \\ &= \frac{y - a}{x - a} \left( 1 - \frac{\Delta(y, a)}{\Delta(x, y)} \right). \end{aligned}$$

Now observe that $0 < \frac{y-a}{x-a} < 1$ and $\Delta(y, a) < \Delta(x, y)$ as above, so that $0 < \frac{S(x, y)-a}{x-a} < 1$ follows.

Now, the property $0 < \frac{S(x, y)-a}{x-a} < 1$ proven in the two cases above imply that $x_{n+1} - x_n$ converges to 0. Moreover, $x_n - x_{n+1} = \frac{\varphi(x_n)}{\Delta(x_n, x_{n-1})}$ and $|\Delta(x_n, x_{n-1})| < \max\{|\varphi'(x_0)|, |\varphi'(x_1)|\}$, which implies that $\varphi(x_n)$ converges to 0 and thus $x_n$ converges to $a$. $\square$

The lemma above basically states that if, in a neighborhood $\mathcal{U}$ of the root, the function is monotone, has strict curvature, and the initial points $x_0, x_1$ are both on the same side
of the root, then the secant method converges monotonically to the root. This is for example the case if $\varphi''\varphi > 0$ 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 $|\varphi'(x)|$ is strictly increasing can be relaxed to require $\Delta(a, x) < \Delta(x, y)$ whenever $x$ lies between $a$ and $y$ and $\Delta(a, x), \Delta(x, y)$ having the same sign, not requiring that $f$ to be smooth.

**Remark 2.2 (Rate and Order of Convergence).** Note that Lemma 2.1 makes no statement about the order of convergence. This is for good reason as arbitrarily slow convergence (still linear though with small rates) is compatible with the Lemma 2.1 both globally and locally. In fact, the convergence order and rate is a function of the multiplicity of the root. As a simple example consider $\varphi(x) = x^m$ with $m > 2$, which satisfies our assumptions. The convergence rate of the secant method is linear with rate $\lambda$ with $0 < \lambda < 1$, so that $\lambda^m + \lambda^{m-1} = 1$; see e.g., (Díez, 2003). Note, though that if the secant method converges it converges at least with order 1, i.e., linearly.

## 2.2. Local Convergence

Let $\varphi(a) = 0$. For the sake of exposition we consider the case of a simple root and assume that $\varphi$ is twice differentiable with $\varphi'(a) \neq 0$ and $\varphi''(a) \neq 0$. We define the iterates as $x_n = a + \epsilon_n$ to perform an error analysis with the recursion:

$$ \epsilon_{n+1} = \epsilon_n - \varphi(a + \epsilon_n) \cdot \frac{\epsilon_n - \epsilon_{n-1}}{\varphi(a + \epsilon_n) - \varphi(a + \epsilon_{n-1})} \quad (2.5) $$

Using a Taylor expansion:

$$ \varphi(a + \epsilon) \approx \varphi'(a)\epsilon + \frac{\varphi''(a)}{2}\epsilon^2 = \epsilon\varphi'(a)(1 + M\epsilon), \quad (2.6) $$

where $M \doteq \frac{\varphi''(a)}{2\varphi'(a)}$, we can derive the recursion:

$$ \epsilon_{n+1} \approx \frac{\varphi''(a)}{2\varphi'(a)}\epsilon_{n-1}\epsilon_n. \quad (2.7) $$

By analyzing the series of $\log(\epsilon_n)$ (Díez, 2003), we can derive an error estimate of:

$$ |x_{n+1} - a| \approx \left| \frac{\varphi''(a)}{2\varphi'(a)} \right|^{\frac{\sqrt{5}-1}{2}} |x_n - a|^{\frac{1+\sqrt{5}}{2}}, \quad (2.8) $$

i.e., we have a convergence of order $\frac{1+\sqrt{5}}{2} \approx 1.618$. For a full proof, see e.g., Grinshpan (2024) and for the convergence for roots of higher order we refer the reader to Díez (2003). In fact, for roots of order $m \ge 2$, the convergence rate drops from superlinear to linear with rate $\lambda$ with $0 < \lambda < 1$, so that $\lambda^m + \lambda^{m-1} = 1$; see e.g., Díez (2003).

**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 convergence (order $\approx 1.618$) compared to Newton's quadratic convergence (order 2) with effective orders of convergence of $1.618^2 \approx 2.62$ vs. 2.

In white-box settings, where gradients can be computed efficiently, such as through reverse automatic differentiation (AD), the function evaluation becomes essentially free as a byproduct of the gradient evaluation, making Newton's method potentially more favorable due to its faster convergence rate. We would like to stress that essentially all our arguments also apply to a variant that would use Newton's method for the line search problem; in Lemma 2.1 we would simply invoke the mean value theorem and replace $\Delta(x, y)$ with $\varphi'(x)$ and then the proof would work analogously.

For our setting however, we assume that we ultimately want to optimize a 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 Appendix 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 is that both in the case of automatic differentiation and manual gradients, each line search subproblem requires a Hessian-vector computation, while not exploiting that information beyond the step size. This “partially second-order” method was already observed in Carderera et al. (2021) not to perform well against a fully first-order method due to the high cost per iteration and little additional gain.

Finally, a note on Brent's method (Brent, 1971), also called Brent-Dekker 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 $\approx 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 lower computational cost per iteration and the fact that we do (almost) never require the additional safeguards of Brent's method because of the already present
step size bounds for FW together with Lemma 2.1. We benchmarked in Julia via Roots.jl as well as in Python via SciPy.

### 3. The Secant Method for Line Search in Frank-Wolfe Algorithms

To disambiguate, we denote the iterates of the secant method applied to the line search problem by $\gamma_n$ and the iterates of the Frank-Wolfe algorithm by $x_t$. We are interested in solving Problem (1.1) with $f$ being a smooth and convex function. In Algorithm 1 we recall the vanilla Frank-Wolfe algorithm and refer the interested reader to Braun et al. (2022) for more advanced variants.

**Algorithm 1** Frank-Wolfe algorithm (Frank & Wolfe, 1956; Levitin & Polyak, 1966)

1: **Input:** Initial point $x_0 \in \mathcal{X}$, number of iterations $T$

2: **Output:** Final iterate $x_T$

3: **for** $t = 0$ **to** $T-1$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp; $v_t \leftarrow \operatorname{argmin}_{v \in \mathcal{X}} \langle \nabla f(x_t), v \rangle$

5: &nbsp;&nbsp;&nbsp;&nbsp; $x_{t+1} \leftarrow (1 - \gamma_t)x_t + \gamma_t v_t$

6: **end for**

Most Frank-Wolfe variants update the iterate as:

$$x_{t+1} \leftarrow x_t - \gamma \mathbf{d}_t, \quad (3.1)$$

with $\mathbf{d}_t$ being a direction and $\gamma \in [0, \gamma_{\max}]$ determined by the specific FW variant under consideration. For instance, $\mathbf{d}_t = x_t - v_t$ and $\gamma_{\max} = 1$ for a standard FW step as we can see in Algorithm 1. A key point common to all variants is that iterates are maintained as convex combinations of extreme points of the feasible set $\mathcal{X}$, so that typically $\gamma_{\max} \le 1$.

When the step size $\gamma$ is determined by line search, the goal is to choose $\gamma$ so that progress is maximized, i.e., we solve the line search problem:

$$\gamma \leftarrow \operatorname{argmin}_{\gamma \in [0, \gamma_{\max}]} f(x_t - \gamma \mathbf{d}_t). \quad (3.2)$$

This is equivalent to finding the root of the optimality condition:

$$\frac{\partial}{\partial \gamma} f(x_t - \gamma \mathbf{d}_t) = 0, \quad (3.3)$$

and since we consider convex and smooth functions $f$ such a solution exists. Moreover, we can deliberately ignore the constraint $\gamma \in [0, \gamma_{\max}]$ because if the optimal $\gamma$ 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.3),

we have $\varphi(\gamma) = \langle f(x_t - \gamma \mathbf{d}_t), \mathbf{d}_t \rangle$ and use the recursion:

$$\gamma_{n+1} \leftarrow \gamma_n - \frac{\langle \nabla f(x_t - \gamma_n \mathbf{d}_t), \mathbf{d}_t \rangle}{\gamma_n - \gamma_{n-1}} \cdot \frac{\langle \nabla f(x_t - \gamma_n \mathbf{d}_t), \mathbf{d}_t \rangle - \langle \nabla f(x_t - \gamma_{n-1} \mathbf{d}_t), \mathbf{d}_t \rangle}{\langle \nabla f(x_t - \gamma_n \mathbf{d}_t), \mathbf{d}_t \rangle} \quad (3.4)$$

It is important to note that SLS does not approximate the inverse of the local Lipschitz constant of $f$ in contrast to (Maltitsky & Mishchenko, 2020; 2023). Rather, it approximates the relevant quantity in the Frank-Wolfe context, which is related (and identical for quadratics) to $\frac{1}{L} \frac{\langle \nabla f(x_t), \mathbf{d}_t \rangle}{\|\mathbf{d}_t\|^2}$.

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 Appendix A, we specify how the convergence rates of Frank-Wolfe behave depending on different choices of the error parameter $\epsilon$ within the line search subproblems.

**Algorithm 2** Secant Line Search (SLS)

1: **Input:** Function $f$, initial point $x_t$, direction $\mathbf{d}_t$, initial step sizes $\gamma_0, \gamma_1$, tolerance $\epsilon$

2: **Output:** Step size $\gamma^*$

3: Initialize $\gamma_{-1} \leftarrow \gamma_0, \gamma_0 \leftarrow \gamma_1$

4: Compute $\varphi_{-1} \leftarrow \langle \nabla f(x_t - \gamma_{-1} \mathbf{d}_t), \mathbf{d}_t \rangle$

5: Compute $\varphi_0 \leftarrow \langle \nabla f(x_t - \gamma_0 \mathbf{d}_t), \mathbf{d}_t \rangle$

6: **repeat**

7: &nbsp;&nbsp;&nbsp;&nbsp; Update $\gamma_1 \leftarrow \gamma_0 - \varphi_0 \cdot \frac{\gamma_0 - \gamma_{-1}}{\varphi_0 - \varphi_{-1}}$

8: &nbsp;&nbsp;&nbsp;&nbsp; $\gamma_1 \leftarrow \max\{0, \min\{\gamma_1, \gamma_{\max}\}\}$ \{clip\}

9: &nbsp;&nbsp;&nbsp;&nbsp; Update $\gamma_{-1} \leftarrow \gamma_0, \gamma_0 \leftarrow \gamma_1$

10: Update $\varphi_{-1} \leftarrow \varphi_0$

11: Compute $\varphi_0 \leftarrow \langle \nabla f(x_t - \gamma_0 \mathbf{d}_t), \mathbf{d}_t \rangle$

12: **until** $|\varphi_0| < \epsilon$

13: **return** $\gamma^* \leftarrow \gamma_0$

As already indicated earlier we have that $\gamma_a \in [0, 1]$ as the iterates are convex combinations of the extreme points of the feasible set $\mathcal{X}$ with the current iterate. In fact, due to not following the gradient but rather updating $x_{t+1} \leftarrow (1 - \gamma_t)x_t + \gamma_t v_t$ after the first iteration, the optimal solution $\gamma_a$ of (3.3) is almost always in the interval $(0, 1)$. To see that $\gamma_a > 0$, observe that the Frank-Wolfe gap $\langle \nabla f(x_t), x_t - v_t \rangle > 0$ by convexity of $f$ and definition of $v_t$ as long as $x_t$ is not optimal and hence $x_t - v_t$ 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., 2021; 2024). We highlight that $\gamma_a < 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
occurs, we still make significant progress (at least as much as the optimal short step) and typically such a step halves the primal gap.

With this, we can now establish the convergence of the Secant Line Search (SLS) when used in a Frank-Wolfe algorithm.

**Theorem 3.1 (Convergence of SLS).** Let $f$ be a strictly convex and smooth function and let $\mathcal{X}$ be a compact convex set. Then running the Frank-Wolfe algorithm (Algorithm 1) with SLS initialized with $\gamma_0 = 0$ and $\gamma_1 = \gamma_0 + \rho$, where $\rho$ is a small positive perturbation, converges at its optimal rate (which depends on $f$ and $\mathcal{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 Frank-Wolfe algorithm are chosen as if run with exact line search (up to the line search tolerance $\epsilon$), so that the first part of the theorem is trivially true.

It remains to verify the assumptions of Lemma 2.1. As $f$ is strictly convex, so is $f(\mathbf{x}_t - \gamma \mathbf{d}_t)$ for any $\mathbf{x}_t \in \mathcal{X}$ and $\mathbf{d}_t = \mathbf{x}_t - \mathbf{v}_t$ as obtained via Algorithm 1. Hence the derivative $\frac{\partial}{\partial \gamma} f(\mathbf{x}_t - \gamma \mathbf{d}_t)$ of $f(\mathbf{x}_t - \gamma \mathbf{d}_t)$ is strictly increasing in $\gamma$. Moreover, the initial points $\gamma_0 = 0$ and $\gamma_1 = \gamma_0 + \rho$ are on the same side of the root, so that the assumptions of Lemma 2.1 are satisfied. $\square$

While the above theorem only guarantees (linear) convergence of SLS in the line search problems, the following remarks give indications for cases in which we can expect superlinear convergence of SLS.

**Remark 3.2 (Superlinear convergence for self-concordant functions).** Let $f$ be self-concordant on $\mathcal{X}$. Then for any $\mathbf{x}_t \in \mathcal{X}$ and $\mathbf{d}_t = \mathbf{x}_t - \mathbf{v}_t$ we have that

$$ \left| \frac{\partial^3}{\partial \gamma^3} f(\mathbf{x}_t - \gamma \mathbf{d}_t)(\tau) \right| \le 2 \frac{\partial^2}{\partial \gamma^2} f(\mathbf{x}_t - \gamma \mathbf{d}_t)(\tau)^{\frac{3}{2}} \quad (3.5) $$

for all $\tau \in [0, 1]$. Thus if $\frac{\partial^3}{\partial \gamma^3} f(\mathbf{x}_t - \gamma \mathbf{d}_t)(\tau) \ne 0$ for all $\tau \in [0, 1]$, then $\gamma_a$ is a simple root of Equation (3.3), so that we can expect superlinear convergence.

Moreover, the constant $M$ appearing in Equation (2.6) is obtained as:

$$ M = \frac{\frac{\partial^3}{\partial \gamma^3} f(\mathbf{x}_t - \gamma \mathbf{d}_t)(\gamma_a)}{2 \frac{\partial^2}{\partial \gamma^2} f(\mathbf{x}_t - \gamma \mathbf{d}_t)(\gamma_a)}. \quad (3.6) $$

In particular in the case of superlinear convergence, SLS achieves very high precision, which is often helpful for ill-conditioned problems, with very few iterations.

**Remark 3.3 (Other FW variants).** While we considered the vanilla Frank-Wolfe algorithm, the same analysis can

be applied to basically any other variants of the Frank-Wolfe algorithm, e.g., the Away-Step Frank-Wolfe algorithm (Wolfe, 1970; Lacoste-Julien & Jaggi, 2015), the Pairwise Conditional Gradients (Lacoste-Julien & Jaggi, 2015), the Blended (Pairwise) Conditional Gradients algorithms (Braun et al., 2019; Tsuji et al., 2022), and Decomposition-invariant Conditional Gradients (Garber & Meshi, 2016; Bashiri & Zhang, 2017). Some of these methods – typically those that explicitly maintain a so-called active set, i.e., a subset of extreme points from which a convex combination forms the current iterate – have “drop steps”, i.e., iterations that do not guarantee progress but instead sparsify the active set, via e.g., away or pairwise steps when clipping occurs. Nonetheless, the same analysis can be applied to these methods as well by carrying out over the. We present computational experiments for these algorithms as well below and in the appendix.

**Remark 3.4 (Secant Line Search for Quadratics).** If $f$ is a convex quadratic, then the line search problem (3.3) is an affine-linear equation. If the iterate $\mathbf{x}_t$ is not optimal yet, then $\mathbf{x}_t - \mathbf{v}_t$ is a descent direction, so that the slope of the affine-linear function is negative and the secant method converges in a single iteration.

As such SLS is almost as cheap as the short-step step size, which would evaluate

$$ \gamma = \max \left\{ 0, \min \left\{ \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle}{L \|\mathbf{x}_t - \mathbf{v}_t\|^2}, 1 \right\} \right\}, $$

while not requiring knowledge of $L$ and exploiting local smoothness, with progress at least as good as the short step.

For the sake of completeness, note that if we would run Newton'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 Appendix B, where we compared the secant and Newton's method.

## 4. Computational Experiments

We evaluate the performance of SLS on several problem classes. All experiments are carried out in Julia with the blended pairwise FW variant implemented in FrankWolfe.jl (Besançon et al., 2022; 2025) with default parameters and a one-hour time limit. Additional experiments 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 FrankWolfe.jl and is available as part of the package.

**Remark 4.1 (Implementation Details and Improvements).** In the following, we discuss some algorithmic considerations ensuring good performance in a wide range of problems.
*Implementation Safeguards.* In the theorem above, we assumed that the function $f$ is strictly convex. This assumption 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, e.g., backtracking line search.

*Warm-starting.* We can warm-start SLS by using the optimal $\gamma^*$ from the last call and initializing the secant method with $\gamma_0 = \gamma^*$ and $\gamma_1 = \gamma_0 + \rho$. This further reduces the number of inner iterations in our experiments.

We briefly list the problem classes used for our experiments. Detailed descriptions can be found in the appendix. “OA” and “OD” correspond to optimal design of experiment problems with A- and D-criterion respectively. “Port” are portfolio instances with a log-revenue objective. “QuadProb” and “Ill” are quadratic instances over the simplex with a low and high condition number respectively. “Birkhoff”, “Spec” and “Nuclear” are quadratic instances over the Birkhoff polytope, the spectraplex, and a nuclear norm ball respectively.

We benchmark the performance of SLS against the adaptive step-size strategies of Pedregosa et al. (2020); Pokutta (2024), the golden-ratio and backtracking line search strategies, the monotonic step size of Carderera et al. (2021; 2024), and the agnostic step size, using the implementations from the *FrankWolfe.jl* package. All strategies are run with the target accuracy of $10^{-7}$, compatible with the gap stopping criterion we set. In the main part, we compare SLS against the adaptive step size (default strategy in *FrankWolfe.jl*), the agnostic step size, and the backtracking line search. All other experiments with much more detailed reporting are available in Appendix C.

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 SLS 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. 1 shows the number of iterations needed by SLS to converge on all problem classes, the total number of instances per problem class can be found in Table 1. For most quadratic problems (Birkhoff, Ill, QuadProb, Spec), SLS requires at most one iteration in accordance with Remark 3.4. Quadratics on the nuclear norm ball are the exception, with some instances taking more than one secant iteration per line search on average. This can be traced back to numerical issues, since on most instances the primal gap is quickly below $10^{-10}$ but the dual gap remains large due to extremely large nuclear norm ball radii. Importantly, the average iteration count remains low, around 1.5, for all solved instances

even in non-quadratic cases. High average iteration counts correspond to instances causing numerical instabilities.

<figure><img src="image_3.png" /><figcaption>Figure 1. Average secant iteration count by problem class. The graph is truncated at 3 iterations on the right, only affecting the A-Optimal instances, which are known to be numerically unstable (Hendrych et al., 2024) with very flat descent directions. Note that the average number can be lower than 1 due to warm-starting.</figcaption></figure>

Aggregated results for all instance classes are compiled in Table 1 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 on 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 to the best option, making it an effective and robust choice for a wide spectrum of problems.

Detailed trajectories of the most important step-size strategies are illustrated in Fig. 3 for four instances of different types. They show the superior performance of SLS compared 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,
<figure><img src="image_4.png" /><figcaption>Figure 2. Comparison of the step sizes per iteration for the Secant and Adaptive line search.</figcaption></figure>

but also efficient in terms of computations despite requiring
gradient calls, unlike, e.g., backtracking which evaluates the
function only. On the numerically-challenging nuclear norm
ball example in particular, backtracking quickly stagnates
despite theoretically being an equivalent line search.

Acknowledgements

Research reported in this paper was partially supported
through the Research Campus Modal funded by the German
Federal Ministry of Education and Research (fund numbers
05M14ZAM,05M20ZBM) and the Deutsche Forschungs-
gemeinschaft (DFG) through the DFG Cluster of Excel-
lence MATH+. David Martínez-Rubio was partially funded
by the project IDEA-CM (TEC-2024/COM-89). Mathieu
Besançon was partially supported by MIAI at Université
Grenoble Alpes (ANR-19-P3IA-0003).

References

Altschuler, J. and Parrilo, P. Acceleration by stepsize hedg-
ing: Multi-step descent and the silver stepsize schedule.

Journal of the ACM, 2023.

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

Altschuler, J. M. and Parrilo, P. A. Acceleration by stepsize
hedging: Silver stepsize schedule for smooth convex opti-
mization. *Mathematical Programming*, pp. 1–14, 2024b.

Bach, F. On the effectiveness of Richardson extrapolation
in data science. *SIAM Journal on Mathematics of Data
Science*, 3(4):1251–1277, 2021.

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*, 61(12):11579–11588, 2022.

Barzilai, J. and Borwein, J. M. Two-point step size gradient
methods. *IMA journal of numerical analysis*, 8(1):141–
148, 1988.
<table><caption>**Table 1.** Summary of the performance on all considered problems. The number of instances per problem classes are written in the brackets. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Prob.</th><th colspan="3">Secant</th><th colspan="3">Adaptive</th><th colspan="3">Agnostic</th><th colspan="3">Backtracking</th></tr><tr><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th></tr></thead><tbody><tr><td>Birk. [30]</td><td>427.6</td><td>&lt;1e-7</td><td>10624</td><td>614.6</td><td>2.47e-7</td><td>17506</td><td>2959.9</td><td>8.76e-7</td><td>731017</td><td><strong>248.5</strong></td><td>&lt;1e-7</td><td><strong>7283</strong></td></tr><tr><td>Ill [50]</td><td>15.3</td><td>&lt;1e-7</td><td><strong>20</strong></td><td>15.9</td><td>&lt;1e-7</td><td>26</td><td>1227.7</td><td>4.35e-6</td><td>120361</td><td><strong>13.9</strong></td><td>&lt;1e-7</td><td>34</td></tr><tr><td>Nuclear [30]</td><td><strong>204.6</strong></td><td><strong>0.133</strong></td><td><strong>1071</strong></td><td>600.6</td><td>0.139</td><td>2547</td><td>3600.0</td><td>753000.0</td><td>-</td><td>3600.0</td><td>11400.0</td><td>-</td></tr><tr><td>OA [50]</td><td><strong>475.7</strong></td><td>0.0333</td><td><strong>2194</strong></td><td>3600.0</td><td>0.0935</td><td>-</td><td>3600.0</td><td>0.13</td><td>-</td><td>3600.0</td><td><strong>5.02e-5</strong></td><td>-</td></tr><tr><td>OD [50]</td><td>199.2</td><td>8.08e-5</td><td>828</td><td>252.0</td><td>2.90e-7</td><td>1496</td><td>3542.2</td><td>3.83e-4</td><td>&gt;9M</td><td><strong>158.8</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>748</strong></td></tr><tr><td>Port [13]</td><td><strong>0.5</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>28</strong></td><td>4.6</td><td>1.44e-7</td><td>66</td><td>2083.7</td><td>2.09e-06</td><td>1263</td><td>166.8</td><td>3.63e-7</td><td>40</td></tr><tr><td>QuadProb [30]</td><td><strong>340.7</strong></td><td>0.000217</td><td><strong>15046</strong></td><td>355.7</td><td>0.000237</td><td>20814</td><td>3043.1</td><td><strong>0.000163</strong></td><td>&gt;30M</td><td>426.4</td><td>0.000624</td><td>32585</td></tr><tr><td>Spec [50]</td><td><strong>34.5</strong></td><td><strong>1.77e-7</strong></td><td><strong>124</strong></td><td>41.1</td><td>3.8e-7</td><td>139</td><td>192.3</td><td>2.13e-6</td><td>4252</td><td>168.7</td><td>1.35e-6</td><td>1347</td></tr></tbody></table>

Bashiri, M. A. and Zhang, X. Decomposition-invariant conditional gradient for general polytopes with line search. *Advances in neural information processing systems*, 30, 2017.

Besançon, M., Carderera, A., and Pokutta, S. FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. *INFORMS Journal on Computing*, 34(5):2611–2620, 2022.

Besançon, M., Designolle, S., Halbey, J., Hendrych, D., Kuzinowicz, D., Pokutta, S., Troppens, H., Herrmannsdoerfer, D. V., and Wirth, E. Improved algorithms and novel applications of the FrankWolfe.jl library. *arXiv preprint arXiv:2501.14613*, 2025. URL https://arxiv.org/abs/2501.14613.

Bolte, J., Combettes, C. W., and Pauwels, E. The iterates of the Frank-Wolfe algorithm may not converge. *Mathematics 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 Conference 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 arXiv:2211.14103*, 2022.

Brent, R. P. An algorithm with guaranteed convergence for finding a zero of a function. *The computer journal*, 14(4): 422–425, 1971.

Brent, R. P. *Algorithms for minimization without derivatives*. Courier Corporation, 2013.

Carderera, A., Besançon, M., and Pokutta, S. Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions. *Advances in Neural Information Processing Systems*, 5 2021.

Carderera, A., Besançon, M., and Pokutta, S. Scalable Frank-Wolfe on generalized self-concordant functions via simple steps. *SIAM Journal on Optimization*, 34(3), 4 2024.

Cavalcanti, J. V., Lessard, L., and Wilson, A. C. Adaptive backtracking for faster optimization. *arXiv preprint arXiv:2408.13150*, 2024.

Díez, P. A note on the convergence of the secant method for simple and multiple roots. *Applied mathematics letters*, 16(8):1211–1215, 2003.

Dvurechensky, P., Safin, K., Shtern, S., and Staudigl, M. Generalized self-concordant analysis of Frank-Wolfe algorithms. *Mathematical Programming*, 198(1):255–323, 2023.

Flannery, B. P., Press, W. H., Teukolsky, S. A., and Vetterling, W. Numerical recipes in c. Press Syndicate of the University of Cambridge, New York, 24(78):36, 1992.

Frank, M. and Wolfe, P. An algorithm for quadratic programming. *Naval research logistics quarterly*, 3(1-2): 95–110, 1956.

Garber, D. and Meshi, O. Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. *Advances in neural information processing systems*, 29, 2016.

Grinshpan, A. Order of convergence of the secant method. Lecture Notes, 2024. https://www.math.drexel.edu/~tolya/300_secant.pdf.
<figure><img src="image_5.png" /><figcaption>**Figure 3.** Progress of the primal value and FW gap for two problems with a quadratic objective (nuclear norm and standard quadratic) and for two problems with a self-concordant objective (D-Opt and portfolio). In (a), the iterations and time are truncated at 10000 and 10 s, respectively, since Backtracking and Agnostic stall on this instance.</figcaption></figure>

Hendrych, D., Besançon, M., and Pokutta, S. Solving 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 International Proceedings in Informatics (LIPIcs)*, pp. 16:1–16:22, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-325-6. doi: 10.4230/LIPIcs.SEA.2024.16. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.16.

Jin, Q. and Mokhtari, A. Non-asymptotic superlinear convergence of standard quasi-Newton methods. *Mathematical Programming*, 200(1):425–473, 2023.

Lacoste-Julien, S. and Jaggi, M. On the global linear con-

vergence of Frank-Wolfe optimization variants. In *Proceedings of the 29th Conference on Neural Information Processing Systems*, pp. 566–575. PMLR, 2015.

Levitin, E. S. and Polyak, B. T. Constrained minimization methods. *USSR Computational Mathematics and Mathematical Physics*, 6(5):1–50, 1966.

Malitsky, Y. and Mishchenko, K. Adaptive gradient descent without descent. In *International Conference on Machine Learning*, pp. 6702–6712. PMLR, 2020.

Malitsky, Y. and Mishchenko, K. Adaptive proximal gradient method for convex optimization. *arXiv preprint arXiv:2308.02261*, 2023.

Nocedal, J. and Wright, S. J. *Numerical optimization*. Springer, 1999.
Papakonstantinou, J. M. and Tapia, R. A. Origin and evolution of the secant method in one dimension. *The American Mathematical Monthly*, 120(6):500–517, 2013.

Pedregosa, F., Negiar, G., Askari, A., and Jaggi, M. Linearly convergent Frank-Wolfe with backtracking line-search. In *Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics*. PMLR, 2020.

Pokutta, S. The Frank-Wolfe algorithm: a short introduction. *Jahresbericht der Deutschen Mathematiker-Vereinigung*, 126:3–35, 1 2024.

Polak, E. On the global stabilization of locally convergent algorithms for optimization and root finding. *IFAC Proceedings Volumes*, 8(1):346–350, 1975.

Polak, E. On the global stabilization of locally convergent algorithms. *Automatica*, 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, A. and Nesterov, Y. Rates of superlinear convergence for classical quasi-Newton methods. *Mathematical Programming*, pp. 1–32, 2022.

Tsuji, K. K., Tanaka, K., and Pokutta, S. Pairwise conditional gradients without swap steps and sparser kernel herding. In *International Conference on Machine Learning*, pp. 21864–21883. PMLR, 2022.

Wirth, E., Kerdreux, T., and Pokutta, S. Acceleration of Frank-Wolfe algorithms with open loop step-sizes. *Proceedings of AISTATS*, 1 2023.

Wirth, E., Peña, J., and Pokutta, S. Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes. *to appear in Mathematical Programming A*, 12 2024.

Wolfe, P. The secant method for simultaneous nonlinear equations. *Communications of the ACM*, 2(12):12–13, 1959.

Wolfe, P. Convergence theory in nonlinear programming. *Integer and nonlinear programming*, pp. 1–36, 1970.

Zhou, D., Ma, S., and Yang, J. AdaBB: Adaptive Barzilai-Borwein method for convex optimization. *arXiv preprint arXiv:2401.08024*, 2024.
## A. Precision of FW's Line Search

In this section, we analyze the convergence of the FW algorithm when there is an inexact computation of the line search, depending on the choice of the accuracy parameters.

Assume $f: \mathbb{R}^n \to \mathbb{R}$ is convex, and differentiable in an open set containing the convex and compact feasible set $\mathcal{X}$, and let $D \stackrel{\text{def}}{=} \text{diam}(\mathcal{X})$. Also, assume $f$ is $L$-smooth in $\mathcal{X}$, that is,

$$f(\mathbf{y}) \le f(\mathbf{x}) + \langle \nabla f(\mathbf{y}), \mathbf{x} - \mathbf{y} \rangle + \frac{L}{2} \|\mathbf{x} - \mathbf{y}\|^2, \text{ for all } \mathbf{x}, \mathbf{y} \in \mathcal{X}.$$

**Algorithm 3 Frank-Wolfe with inexact line search**

**Input:** Function $f$, initial point $\mathbf{x}_0$.

1: **for** $t = 0$ **to** $T$ **do**

2: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{v}_t \leftarrow \text{argmin}_{\mathbf{v} \in \mathbb{R}^n} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$

3: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{t+1} \leftarrow \delta_t$-minizer of $g: [0, 1] \to \mathbb{R}$, $\gamma \mapsto f((1-\gamma)\mathbf{x}_t + \gamma\mathbf{v}_t)$

4: **end for**

We define positive weights $a_\ell > 0$ for all $\ell \ge 0$, to be determined later, and $A_t \stackrel{\text{def}}{=} \sum_{i=0}^t a_i$. Thus, $A_{-1} = 0$. We also define the following lower bound on $f(\mathbf{x}^*)$, where $\mathbf{x}^*$ here is defined as a minimizer in $\text{argmin}_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x})$:

$$\begin{align*}
A_t f(\mathbf{x}^*) &\overset{\textcircled{1}}{\ge} \sum_{\ell=0}^t a_\ell f(\mathbf{x}_\ell) + \sum_{\ell=0}^t a_\ell \langle \nabla f(\mathbf{x}_\ell), \mathbf{x}^* - \mathbf{x}_\ell \rangle \\
&\overset{\textcircled{2}}{\ge} \sum_{\ell=0}^t a_\ell f(\mathbf{x}_\ell) + \sum_{\ell=0}^t a_\ell \langle \nabla f(\mathbf{x}_\ell), \mathbf{v}_\ell - \mathbf{x}_\ell \rangle \\
&\stackrel{\text{def}}{=} A_t L_t,
\end{align*}$$

where we applied convexity in (1), and for (2), we applied the definition of $\mathbf{v}_\ell$ in the algorithm, which is why we define this point. Define the primal-dual gap.

$$G_t \stackrel{\text{def}}{=} f(\mathbf{x}_{t+1}) - L_t \ge f(\mathbf{x}_{t+1}) - f(\mathbf{x}^*), \quad (A.1)$$

and note that upper bound $f(\mathbf{x}_{t+1})$ is one step ahead, which helps the analysis. We obtain the following, for $t \ge 0$, and $\tilde{\mathbf{x}}_{t+1} \stackrel{\text{def}}{=} \frac{A_{t-1}}{A_t} \mathbf{x}_t + \frac{a_t}{A_t} \mathbf{v}_t$:

$$\begin{align}
A_t G_t - A_{t-1} G_{t-1} &= A_t f(\mathbf{x}_{t+1}) - A_{t-1} f(\mathbf{x}_t) \nonumber \\
&\quad - \left( a_t f(\mathbf{x}_t) + \sum_{\ell=0}^{t-1} a_\ell f(\mathbf{x}_\ell) + a_t \langle \nabla f(\mathbf{x}_t), \mathbf{v}_t - \mathbf{x}_t \rangle + \sum_{\ell=0}^{t-1} a_\ell (\langle \nabla f(\mathbf{x}_\ell), \mathbf{v}_\ell - \mathbf{x}_\ell \rangle) \right) \nonumber \\
&\quad + \left( \sum_{\ell=0}^{t-1} a_\ell f(\mathbf{x}_\ell) + \sum_{\ell=0}^{t-1} a_\ell (\langle \nabla f(\mathbf{x}_\ell), \mathbf{v}_\ell - \mathbf{x}_\ell \rangle) \right) \tag{A.2}
\end{align}$$

$$\overset{\textcircled{1}}{\le} \langle \nabla f(\mathbf{x}_t), A_t(\tilde{\mathbf{x}}_{t+1} - \mathbf{x}_t) - a_t(\mathbf{v}_t - \mathbf{x}_t) \rangle + \frac{LA_t}{2} \|\tilde{\mathbf{x}}_{t+1} - \mathbf{x}_t\|^2 + A_t \delta_t$$

$$\overset{\textcircled{2}}{=} \frac{L a_t^2}{2A_t} \|\mathbf{v}_t - \mathbf{x}_t\|^2 + A_t \delta_t \le \frac{L D^2 a_t^2}{2A_t} + A_t \delta_t \stackrel{\text{def}}{=} E_t.$$

In (1) we grouped terms to get $A_t(f(\mathbf{x}_{t+1}) - f(\mathbf{x}_t))$ used that the assumption on $\mathbf{x}_{t+1}$ makes this term be bounded by the value that the smoothness inequality yields for any point, and in particular for $\tilde{\mathbf{x}}_{t+1}$, up to a $\delta_t$ error coming from the line search. In (2) we used twice the definition of $\tilde{\mathbf{x}}_{t+1}$ which implies $A_t(\mathbf{x}_{t+1} - \mathbf{x}_t) = a_t(\mathbf{v}_t - \mathbf{x}_t)$. In (3), we bounded the distance of points by the diameter $D$.
Now with the choice $a_t = 2t + 2$ and $A_t = \sum_{i=0}^{t} a_i = (t+1)(t+2)$ we have, by telescoping and dividing by $A_t$:

$$ 
\begin{aligned}
f(\mathbf{x}_{t+1}) - f(\mathbf{x}^*) &\leq G_t \leq \frac{1}{A_t} \sum_{i=0}^{t} E_i = \frac{1}{A_t} \sum_{i=0}^{t} \frac{LD^2 a_i^2}{2A_i} + A_i \delta_i = \frac{1}{(t+1)(t+2)} \sum_{i=0}^{t} \frac{2LD^2(i+1)}{i+2} + \frac{1}{A_t} \sum_{i=0}^{t} A_i \delta_i \\
&< \frac{2LD^2}{t+2} + \frac{1}{A_t} \sum_{i=0}^{t} A_i \delta_i.
\end{aligned} 
\quad (A.3) $$

If we choose constant $\delta_t = \delta$, the sum of the terms with $\delta$ on the right hand side becomes $O(t\delta)$. So if we are aiming to get an $\epsilon$-minimizer after $T$ steps, we can choose $T$ so that the first summand on the right hand side is $\epsilon/2$ and we can choose $\delta = \Theta(\epsilon/T)$ so that the second summand is $\epsilon/2$ after $T$ steps.

Another option would be to choose $\delta_i = \frac{\epsilon a_i}{2A_i}$, which yields $\frac{1}{A_t} \sum_{i=0}^{t} A_i \delta_i = \frac{\epsilon}{2A_t} \sum_{i=0}^{t} a_i = \frac{\epsilon}{2}$ 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 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 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 method in isolation outside of the Frank-Wolfe 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 et 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 $\gamma_0 = 0$ and $\gamma_1 = \gamma_0 + \rho$ with $\rho = 10^{-5}$ and to the target accuracy of $10^{-8}$. For these tests, we computed the gradient function via automatic differentiation. We report the average time in seconds for each method to find a solution with a 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-Wolfe algorithm. For the case where $f$ is a quadratic function, we used the same instance generation as done in Section 4 for the quadratics and randomly sampled $x$ 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 to 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. 4.

## C. Additional Experiments

In this appendix, we provide additional information and context on the instance classes, and report more fine-grained results on experiments by problem class.

**Optimal Design of Experiment (OED).** Optimal Design of Experiment is a problem maximizing an information criterion on the probability simplex and which was tackled by a FW method in Hendrych et al. (2024). The objective functions of both the ‘A’ and ‘D’ criteria are generalized self-concordant, 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 is also (generalized) self-concordant and satisfies the conditions of Remark 3.2.
<figure><img src="image_6.png" /><figcaption>Figure 4. Various runs of SLS with the secant and Newton's method. (Top Row) Instances where $f$ is not a quadratic function. (Bottom Row) Instances where $f$ is a quadratic function.</figcaption></figure>
<table><caption>**Table 2.** Comparison of execution times between Secant and Newton's methods for various test functions. Where *f* is explicitly provided, the gradient function is computed via automatic differentiation. For the line search problems, the gradient is provided directly and not computed via automatic differentiation, as those are instances extracted from the line search routine. Timings are averaged over 1000 runs.</caption><thead><tr><th>Function</th><th>Secant Time (s)</th><th>Newton's Time (s)</th><th>Newton/Secant</th></tr></thead><tbody><tr><td>f(x) = x<sup>2</sup> - 2</td><td>3.42e-06</td><td>4.32e-05</td><td>12.62</td></tr><tr><td>f(x) = x<sup>2</sup> - 5</td><td>3.14e-06</td><td>5.47e-05</td><td>17.42</td></tr><tr><td>f(x) = x<sup>2</sup> - 10</td><td>2.82e-06</td><td>4.13e-05</td><td>14.65</td></tr><tr><td>f(x) = x<sup>2</sup> - x - 2</td><td>3.70e-06</td><td>4.63e-05</td><td>12.52</td></tr><tr><td>f(x) = x<sup>2</sup> + 2x - 7</td><td>3.47e-06</td><td>4.11e-05</td><td>11.85</td></tr><tr><td>f(x) = x<sup>3</sup> - 2</td><td>4.81e-06</td><td>4.64e-05</td><td>9.65</td></tr><tr><td>f(x) = xe<sup>x</sup> - 7</td><td>1.01e-05</td><td>5.89e-05</td><td>5.83</td></tr><tr><td>f(x) = x - cos(x)</td><td>6.39e-06</td><td>4.39e-05</td><td>6.88</td></tr><tr><td>Line Search (quadratic)</td><td>1.92e-05</td><td>7.97e-05</td><td>4.15</td></tr><tr><td>Line Search (arbitrary)</td><td>3.75e-05</td><td>1.24e-04</td><td>3.31</td></tr></tbody></table>

**Quadratics on the simplex.** Ill-conditioned problems are constructed as convex quadratic minimization on the simplex with a high condition number on the Hessian and denoted “Ill”. 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 to minimizing a least-square objective on the Birkhoff polytope, the convex hull of all permutation matrices of a given size.

We compare more step-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 in Carderera et al. (2021; 2024), and the open-loop agnostic step size of the form $\frac{2}{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. 11 respectively that then golden-ratio line search starts with a 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. (2022)—the default active-set algorithm in *FrankWolfe.jl*—for all experiments. Similar to the Away-step Frank-Wolfe (see e.g., Lacoste-Julien & Jaggi (2015)), it requires a step size computed with an exact or approximate line search, in particular to ensure accelerated convergence rates in favorable cases (e.g., uniformly convex functions or 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 *FrankWolfe.jl* in Fig. 14 and Fig. 15.
<figure><img src="image_7.png" /><figcaption>Figure 5. Progress of the primal value and FW gap for an instance of the Birkhoff problem. The Golden Ratio line search from the FrankWolfe.jl package stalls out due to numerical issues.</figcaption></figure>

<table><caption>Table 3. Instances of the Birkhoff problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th rowspan="2">Time (s)</th><th colspan="3">Secant</th><th colspan="3">Adaptive</th><th colspan="3">Agnostic</th><th colspan="3">Backtracking</th></tr><tr><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>2500</td><td>5</td><td>10.4</td><td>&lt;1e-7</td><td>6274</td><td>603.3</td><td>14.6</td><td>&lt;1e-7</td><td>9768</td><td>669.0</td><td>1111.7</td><td>&lt;1e-7</td><td>731017</td><td>657.6</td><td><strong>6.0</strong></td><td>&lt;1e-7</td><td><strong>3919</strong></td><td>653.2</td></tr><tr><td>10000</td><td>5</td><td>133.6</td><td>&lt;1e-7</td><td>12063</td><td>90.3</td><td>209.7</td><td>&lt;1e-7</td><td>19437</td><td>92.7</td><td>3600.0</td><td>2.01e-07</td><td>-</td><td>97.0</td><td><strong>70.5</strong></td><td>&lt;1e-7</td><td><strong>7547</strong></td><td>107.0</td></tr><tr><td>22500</td><td>5</td><td>523.2</td><td>&lt;1e-7</td><td>13835</td><td>26.4</td><td>818.6</td><td>&lt;1e-7</td><td>22589</td><td>27.6</td><td>3600.0</td><td>4.53e-07</td><td>-</td><td>30.1</td><td><strong>284.5</strong></td><td>&lt;1e-7</td><td><strong>9123</strong></td><td>32.1</td></tr><tr><td>40000</td><td>5</td><td>1137.4</td><td>&lt;1e-7</td><td>11965</td><td>10.5</td><td>1838.5</td><td>&lt;1e-7</td><td>19443</td><td>10.6</td><td>3600.0</td><td>8.71e-07</td><td>-</td><td>12.1</td><td><strong>658.1</strong></td><td>&lt;1e-7</td><td><strong>8392</strong></td><td>12.8</td></tr><tr><td>62500</td><td>5</td><td>2022.4</td><td>&lt;1e-7</td><td>10272</td><td>5.1</td><td>3043.7</td><td>&lt;1e-7</td><td>16293</td><td>5.4</td><td>3600.0</td><td>1.28e-06</td><td>-</td><td>6.6</td><td><strong>1130.5</strong></td><td>&lt;1e-7</td><td><strong>6994</strong></td><td>6.2</td></tr><tr><td>90000</td><td>5</td><td>3344.8</td><td>&lt;1e-7</td><td>9333</td><td>2.8</td><td>3600.0</td><td>2.47e-07</td><td>-</td><td>3.1</td><td>3600.0</td><td>1.58e-06</td><td>-</td><td>4.5</td><td><strong>2253.3</strong></td><td>&lt;1e-7</td><td><strong>7722</strong></td><td>3.4</td></tr></tbody></table>
<figure><img src="image_8.png" /><figcaption>Figure 6. Progress of the primal value and FW gap for an instance of the Ill-Conditioned Quadratic problem. For the golden ratio line search the same remark applies as in the Birkhoff problem (see Fig. 5).</figcaption></figure>

<table><caption>Table 4. Instances of the Ill-Conditioned Quadratic problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th colspan="4">Secant</th><th colspan="4">Adaptive</th><th colspan="4">Agnostic</th><th colspan="4">Backtracking</th></tr><tr><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>500</td><td>5</td><td><b>0.0</b></td><td>&lt;1e-7</td><td><b>25</b></td><td><b>Inf</b></td><td>0.0</td><td>&lt;1e-7</td><td>30</td><td>Inf</td><td>40.7</td><td>&lt;1e-7</td><td>336307</td><td>8263.1</td><td>0.1</td><td>&lt;1e-7</td><td>39</td><td>390.0</td></tr><tr><td>1000</td><td>5</td><td>9.1</td><td>&lt;1e-7</td><td><b>16</b></td><td>1.8</td><td>9.7</td><td>&lt;1e-7</td><td>22</td><td>2.3</td><td>1385.4</td><td>3.14e-06</td><td>118</td><td>9.2</td><td><b>7.6</b></td><td>&lt;1e-7</td><td>31</td><td>4.1</td></tr><tr><td>1500</td><td>5</td><td><b>12.5</b></td><td>&lt;1e-7</td><td><b>21</b></td><td>1.7</td><td>13.1</td><td>&lt;1e-7</td><td>29</td><td>2.2</td><td>3600.0</td><td>1.99e-06</td><td>-</td><td>6.3</td><td>17.7</td><td>&lt;1e-7</td><td>38</td><td>2.1</td></tr><tr><td>2000</td><td>5</td><td><b>13.7</b></td><td>&lt;1e-7</td><td><b>17</b></td><td>1.2</td><td>13.0</td><td>&lt;1e-7</td><td>21</td><td>1.6</td><td>860.4</td><td>4.20e-06</td><td>309</td><td>8.4</td><td>17.2</td><td>&lt;1e-7</td><td>29</td><td>1.7</td></tr><tr><td>2500</td><td>5</td><td>23.6</td><td>&lt;1e-7</td><td><b>20</b></td><td>0.8</td><td>25.4</td><td>&lt;1e-7</td><td>27</td><td>1.1</td><td>1944.4</td><td>5.29e-06</td><td>370</td><td>3.5</td><td><b>22.1</b></td><td>&lt;1e-7</td><td>37</td><td>1.7</td></tr><tr><td>3000</td><td>5</td><td>31.3</td><td>&lt;1e-7</td><td><b>22</b></td><td>0.7</td><td>32.1</td><td>&lt;1e-7</td><td>28</td><td>0.9</td><td>2133.8</td><td>4.85e-06</td><td>501</td><td>2.5</td><td><b>23.3</b></td><td>&lt;1e-7</td><td>36</td><td>1.5</td></tr><tr><td>3500</td><td>5</td><td>17.7</td><td>&lt;1e-7</td><td><b>13</b></td><td>0.7</td><td>23.0</td><td>&lt;1e-7</td><td>20</td><td>0.9</td><td>1413.0</td><td>5.74e-06</td><td>56</td><td>3.5</td><td><b>15.6</b></td><td>&lt;1e-7</td><td>24</td><td>1.5</td></tr><tr><td>4000</td><td>5</td><td>36.4</td><td>&lt;1e-7</td><td><b>22</b></td><td>0.6</td><td>32.9</td><td>&lt;1e-7</td><td>26</td><td>0.8</td><td>3600.0</td><td>4.91e-06</td><td>-</td><td>1.7</td><td><b>27.4</b></td><td>&lt;1e-7</td><td>38</td><td>1.4</td></tr><tr><td>4500</td><td>5</td><td>28.1</td><td>&lt;1e-7</td><td><b>21</b></td><td>0.7</td><td>32.0</td><td>&lt;1e-7</td><td>28</td><td>0.9</td><td>744.3</td><td>4.52e-06</td><td>145</td><td>4.8</td><td><b>24.4</b></td><td>&lt;1e-7</td><td>38</td><td>1.6</td></tr><tr><td>5000</td><td>5</td><td>38.6</td><td>&lt;1e-7</td><td><b>22</b></td><td>0.6</td><td>35.2</td><td>&lt;1e-7</td><td>27</td><td>0.8</td><td>2774.2</td><td>4.94e-06</td><td>1565</td><td>1.8</td><td><b>25.5</b></td><td>&lt;1e-7</td><td>34</td><td>1.3</td></tr></tbody></table>
<figure><img src="image_9.png" /><figcaption>Figure 7. Progress of the primal value and FW gap for an instance of the Nuclear problem. The secant line search is not only significantly faster than the other methods but also reaches a much higher final accuracy.</figcaption></figure>

<table><caption>Table 5. Instances of the Nuclear problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th rowspan="2">Time (s)</th><th colspan="3">Secant</th><th colspan="3">Adaptive</th><th colspan="3">Agnostic</th><th colspan="3">Backtracking</th></tr><tr><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>2500</td><td>5</td><td><strong>0.2</strong></td><td>&lt;1e-7</td><td><strong>511</strong></td><td>2555.0</td><td>0.5</td><td>&lt;1e-7</td><td>1611</td><td>3222.0</td><td>3600.0</td><td>1.34e+04</td><td>-</td><td>5381.0</td><td>3600.0</td><td>1.60e+04</td><td>-</td><td>3316.4</td></tr><tr><td>10000</td><td>5</td><td><strong>1.1</strong></td><td>&lt;1e-7</td><td><strong>873</strong></td><td>793.6</td><td>260.1</td><td>1.37e-01</td><td>3161</td><td>4060.2</td><td>3600.0</td><td>2.68e+04</td><td>-</td><td>2860.3</td><td>3600.0</td><td>2.34e+04</td><td>-</td><td>1250.8</td></tr><tr><td>22500</td><td>5</td><td><strong>803.8</strong></td><td>&lt;1e-7</td><td><strong>1662</strong></td><td>2.1</td><td>2665.2</td><td>1.41e-01</td><td>4274</td><td>2.2</td><td>3600.0</td><td>3.70e+06</td><td>-</td><td>11.9</td><td>3600.0</td><td>1.12e+04</td><td>-</td><td>4.2</td></tr><tr><td>40000</td><td>5</td><td><strong>2997.0</strong></td><td><strong>1.28e-01</strong></td><td><strong>1912</strong></td><td>1.3</td><td>3600.0</td><td>1.38e-01</td><td>-</td><td>1.6</td><td>3600.0</td><td>4.27e+06</td><td>-</td><td>12.3</td><td>3600.0</td><td>6.60e+03</td><td>-</td><td>2.5</td></tr><tr><td>62500</td><td>5</td><td>3600.0</td><td><strong>1.32e-01</strong></td><td>-</td><td>1.1</td><td>3600.0</td><td>1.39e-01</td><td>-</td><td>1.4</td><td>3600.0</td><td>5.63e+06</td><td>-</td><td>10.9</td><td>3600.0</td><td>8.94e+03</td><td>-</td><td>1.7</td></tr><tr><td>90000</td><td>5</td><td>3600.0</td><td><strong>1.38e-01</strong></td><td>-</td><td>1.0</td><td>3600.0</td><td>1.40e-01</td><td>-</td><td>1.4</td><td>3600.0</td><td>5.71e+06</td><td>-</td><td>12.5</td><td>3600.0</td><td>8.98e+03</td><td>-</td><td>1.5</td></tr></tbody></table>
<figure><img src="image_10.png" /><figcaption>Figure 8. Progress of the primal value and FW gap for an instance of the A-Optimal Experiment Design problem. For the agnostic step size the same remark applies as in the D-Optimal Experiment Design problem (see Fig. 9).</figcaption></figure>

<table><caption>Table 6. Instances of the A-Optimal Experiment Design problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th rowspan="2">Time (s)</th><th colspan="3">Secant</th><th colspan="3">Adaptive</th><th colspan="3">Agnostic</th><th colspan="3">Backtracking</th></tr><tr><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>100</td><td>5</td><td><strong>0.6</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>887</strong></td><td>1478.3</td><td>3600.0</td><td>6.00e-07</td><td>-</td><td>512.2</td><td>3600.0</td><td>1.85e-05</td><td>-</td><td>2613.6</td><td>3600.0</td><td>1.90e-06</td><td>-</td><td>970.6</td></tr><tr><td>200</td><td>5</td><td><strong>3.2</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>1413</strong></td><td>441.6</td><td>3600.0</td><td>6.93e-07</td><td>-</td><td>315.1</td><td>3600.0</td><td>6.78e-05</td><td>-</td><td>1141.4</td><td>3600.0</td><td>1.59e-06</td><td>-</td><td>267.2</td></tr><tr><td>300</td><td>5</td><td><strong>420.5</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>1971</strong></td><td>4.7</td><td>3600.0</td><td>7.15e-07</td><td>-</td><td>43.9</td><td>3600.0</td><td>7.32e-03</td><td>-</td><td>16.2</td><td>3600.0</td><td>1.64e-06</td><td>-</td><td>1.9</td></tr><tr><td>400</td><td>5</td><td><strong>775.3</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>2315</strong></td><td>3.0</td><td>3600.0</td><td>8.87e-07</td><td>-</td><td>3.7</td><td>3600.0</td><td>2.16e-02</td><td>-</td><td>9.7</td><td>3600.0</td><td>1.82e-06</td><td>-</td><td>1.2</td></tr><tr><td>500</td><td>5</td><td><strong>1284.7</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>2901</strong></td><td>2.3</td><td>3600.0</td><td>4.47e-05</td><td>-</td><td>2.0</td><td>3600.0</td><td>7.51e-02</td><td>-</td><td>5.4</td><td>3600.0</td><td>1.56e-06</td><td>-</td><td>1.1</td></tr><tr><td>600</td><td>5</td><td><strong>2209.3</strong></td><td><strong>2.53e-04</strong></td><td><strong>3012</strong></td><td>1.1</td><td>3600.0</td><td>1.04e-06</td><td>-</td><td>2.7</td><td>3600.0</td><td>3.59e-02</td><td>-</td><td>7.7</td><td>3600.0</td><td>1.30e-06</td><td>-</td><td>1.0</td></tr><tr><td>700</td><td>5</td><td><strong>2059.5</strong></td><td><strong>&lt;1e-7</strong></td><td><strong>2976</strong></td><td>1.4</td><td>3600.0</td><td>3.34e-03</td><td>-</td><td>1.5</td><td>3600.0</td><td>1.76e-01</td><td>-</td><td>3.2</td><td>3600.0</td><td>1.28e-06</td><td>-</td><td>0.9</td></tr><tr><td>800</td><td>5</td><td><strong>3565.6</strong></td><td>2.45e-06</td><td><strong>3240</strong></td><td>0.7</td><td>3600.0</td><td>2.15e-01</td><td>-</td><td>0.6</td><td>3600.0</td><td>2.55e-01</td><td>-</td><td>3.0</td><td>3600.0</td><td><strong>1.71e-06</strong></td><td>-</td><td>0.8</td></tr><tr><td>900</td><td>5</td><td>3600.0</td><td>8.13e-03</td><td>-</td><td>0.5</td><td>3600.0</td><td>4.53e-01</td><td>-</td><td>0.6</td><td>3600.0</td><td>3.50e-01</td><td>-</td><td>1.8</td><td>3600.0</td><td><strong>1.41e-05</strong></td><td>-</td><td>0.6</td></tr><tr><td>1000</td><td>5</td><td>3600.0</td><td>9.41e-02</td><td>-</td><td>0.3</td><td>3600.0</td><td>3.81e-01</td><td>-</td><td>0.4</td><td>3600.0</td><td>4.63e-01</td><td>-</td><td>1.3</td><td>3600.0</td><td><strong>4.75e-04</strong></td><td>-</td><td>0.5</td></tr></tbody></table>
<figure><img src="image_11.png" /><figcaption>Figure 9. Progress of the primal value and FW gap for an instance of the D-Optimal Experiment Design problem. The significant uptick in the primal value for the agnostic is expected as (a) the agnostic step size does not guarantee primal progress in contrast to the other step sizes used here and (b) the agnostic step size strictly speaking cannot be applied to the D-Optimal Experiment Design problem (Hendrych et al., 2024) as it does not work for generalized self-concordant functions (Carderera et al., 2021; 2024). We only included it here for completeness and since it is the textbook step-size rule for the vanilla Frank-Wolfe algorithm.</figcaption></figure>

<table><caption>Table 7. Instances of the D-Optimal Experiment Design problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances. Brackets indicate that all instances were basically solved up to the tolerance up to some numerical error.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th rowspan="2">Time (s)</th><th colspan="3">Secant</th><th colspan="3">Adaptive</th><th colspan="3">Agnostic</th><th colspan="3">Backtracking</th></tr><tr><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>100</td><td>5</td><td>0.2</td><td>&lt;1e-7</td><td>306</td><td>1530.0</td><td>0.3</td><td>&lt;1e-7</td><td>653</td><td>2176.7</td><td>3061.6</td><td>[&lt;1e-7]</td><td>&gt;9M</td><td>2523.4</td><td><b>0.1</b></td><td>&lt;1e-7</td><td><b>219</b></td><td>2190.0</td></tr><tr><td>200</td><td>5</td><td>1.1</td><td>&lt;1e-7</td><td>459</td><td>417.3</td><td>1.4</td><td>&lt;1e-7</td><td>915</td><td>653.6</td><td>3600.0</td><td>2.34e-07</td><td>-</td><td>948.8</td><td><b>0.8</b></td><td>&lt;1e-7</td><td><b>376</b></td><td>470.0</td></tr><tr><td>300</td><td>5</td><td>128.0</td><td>&lt;1e-7</td><td>534</td><td>4.2</td><td>64.9</td><td>[&lt;1e-7]</td><td>1088</td><td>13.4</td><td>3600.0</td><td>1.80e-05</td><td>-</td><td>15.4</td><td><b>105.3</b></td><td>&lt;1e-7</td><td><b>451</b></td><td>4.3</td></tr><tr><td>400</td><td>5</td><td>439.7</td><td>[&lt;1e-7]</td><td>780</td><td>1.4</td><td>327.2</td><td>&lt;1e-7</td><td>1423</td><td>4.3</td><td>3600.0</td><td>4.68e-05</td><td>-</td><td>9.0</td><td><b>241.3</b></td><td>&lt;1e-7</td><td><b>648</b></td><td>2.7</td></tr><tr><td>500</td><td>5</td><td><b>376.1</b></td><td>&lt;1e-7</td><td>812</td><td>2.2</td><td>775.4</td><td>&lt;1e-7</td><td>1570</td><td>2.0</td><td>3600.0</td><td>7.57e-05</td><td>-</td><td>6.8</td><td>384.8</td><td>&lt;1e-7</td><td><b>727</b></td><td>1.9</td></tr><tr><td>600</td><td>5</td><td><b>371.0</b></td><td>&lt;1e-7</td><td>876</td><td>2.4</td><td>1354.2</td><td>[&lt;1e-7]</td><td>1585</td><td>0.9</td><td>3600.0</td><td>8.03e-05</td><td>-</td><td>6.9</td><td>415.2</td><td>&lt;1e-7</td><td><b>815</b></td><td>2.0</td></tr><tr><td>700</td><td>5</td><td>728.5</td><td>&lt;1e-7</td><td>1029</td><td>1.4</td><td>1523.1</td><td>[&lt;1e-7]</td><td>1866</td><td>0.7</td><td>3600.0</td><td>4.74e-04</td><td>-</td><td>3.1</td><td><b>589.7</b></td><td>&lt;1e-7</td><td><b>912</b></td><td>1.5</td></tr><tr><td>800</td><td>5</td><td>1066.7</td><td>&lt;1e-7</td><td>1096</td><td>1.0</td><td>1268.0</td><td>&lt;1e-7</td><td>1986</td><td>1.6</td><td>3600.0</td><td>6.06e-04</td><td>-</td><td>2.5</td><td><b>884.8</b></td><td>&lt;1e-7</td><td><b>998</b></td><td>1.1</td></tr><tr><td>900</td><td>5</td><td>1881.2</td><td>[&lt;1e-7]</td><td>1228</td><td>0.5</td><td>2282.9</td><td>&lt;1e-7</td><td>2177</td><td>1.0</td><td>3600.0</td><td>9.85e-04</td><td>-</td><td>1.3</td><td><b>1294.8</b></td><td>&lt;1e-7</td><td><b>1131</b></td><td>0.9</td></tr><tr><td>1000</td><td>5</td><td>3413.0</td><td>8.08e-05</td><td>1334</td><td>0.3</td><td>3389.9</td><td>2.90e-07</td><td>2212</td><td>0.7</td><td>3600.0</td><td>1.09e-03</td><td>-</td><td>1.0</td><td><b>1978.3</b></td><td>&lt;1e-7</td><td><b>1199</b></td><td>0.6</td></tr></tbody></table>
<figure><img src="image_12.png" /><figcaption>Figure 10. Progress of the primal value and FW gap for an instance of the Portfolio problem.</figcaption></figure>

<table><caption>Table 8. Instances of the Portfolio problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th rowspan="2">Time (s)</th><th colspan="2">Secant</th><th colspan="3">Adaptive</th><th colspan="3">Agnostic</th><th colspan="3">Backtracking</th></tr><tr><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>800</td><td>4</td><td>0.5</td><td>&lt;1e-7</td><td>26</td><td>52.0</td><td>0.6</td><td>&lt;1e-7</td><td>64</td><td>106.7</td><td>608.4</td><td>7.19e-07</td><td>1263</td><td>2872.9</td><td>0.2</td><td>&lt;1e-7</td><td>37</td><td>185.0</td></tr><tr><td>1200</td><td>4</td><td><b>0.5</b></td><td><b>&lt;1e-7</b></td><td>23</td><td>46.0</td><td>11.1</td><td>1.63e-07</td><td>58</td><td>8339.3</td><td>3600.0</td><td>1.41e-06</td><td>-</td><td>445.7</td><td>3600.0</td><td>3.98e-07</td><td>-</td><td>88.9</td></tr><tr><td>1500</td><td>5</td><td><b>0.6</b></td><td><b>&lt;1e-7</b></td><td>34</td><td>56.7</td><td>7.6</td><td>1.25e-07</td><td>74</td><td>14273.2</td><td>3600.0</td><td>3.45e-06</td><td>-</td><td>333.9</td><td>758.8</td><td>3.28e-07</td><td>53</td><td>193.9</td></tr></tbody></table>
<figure><img src="image_13.png" /><figcaption>Figure 11. Progress of the primal value and FW gap for an instance of the Simple Quadratic problem.</figcaption></figure>

<table><caption>Table 9. Instances of the Standard Quadratic problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th rowspan="2">Time (s)</th><th colspan="2">Secant</th><th colspan="2">Adaptive</th><th colspan="2">Agnostic</th><th colspan="2">Backtracking</th></tr><tr><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>2500</td><td>5</td><td><strong>0.5</strong></td><td>&lt;1e-7</td><td><strong>6491</strong></td><td>12982.0</td><td>0.5</td><td>&lt;1e-7</td><td>9083</td><td>18166.0</td><td>1313.2</td><td>&lt;1e-7</td><td>&gt;30M</td><td>23600.7</td><td>1.2</td><td>&lt;1e-7</td><td>13885</td><td>11570.8</td></tr><tr><td>10000</td><td>5</td><td><strong>5.5</strong></td><td>&lt;1e-7</td><td><strong>23601</strong></td><td>4291.1</td><td>6.9</td><td>&lt;1e-7</td><td>32545</td><td>4716.7</td><td>3600.0</td><td>3.45e-07</td><td>-</td><td>5558.5</td><td>15.6</td><td>&lt;1e-7</td><td>51285</td><td>3287.5</td></tr><tr><td>22500</td><td>5</td><td>3600.0</td><td><strong>1.92e-04</strong></td><td>-</td><td>2.4</td><td>6.9</td><td>2.18e-04</td><td>-</td><td>3.3</td><td>3600.0</td><td>2.24e-04</td><td>-</td><td>10.0</td><td>3600.0</td><td>5.56e-04</td><td>-</td><td>3.6</td></tr><tr><td>40000</td><td>5</td><td>3600.0</td><td><strong>2.10e-04</strong></td><td>-</td><td>2.5</td><td>6.9</td><td>2.43e-04</td><td>-</td><td>3.2</td><td>3600.0</td><td>2.32e-04</td><td>-</td><td>9.7</td><td>3600.0</td><td>5.77e-04</td><td>-</td><td>3.8</td></tr><tr><td>62500</td><td>5</td><td>3600.0</td><td><strong>2.30e-04</strong></td><td>-</td><td>2.4</td><td>6.9</td><td>2.55e-04</td><td>-</td><td>3.2</td><td>3600.0</td><td>2.04e-04</td><td>-</td><td>9.1</td><td>3600.0</td><td>6.39e-04</td><td>-</td><td>3.6</td></tr><tr><td>90000</td><td>5</td><td>3600.0</td><td><strong>2.36e-04</strong></td><td>-</td><td>2.3</td><td>6.9</td><td>2.34e-04</td><td>-</td><td>3.5</td><td>3600.0</td><td>1.56e-04</td><td>-</td><td>8.6</td><td>3600.0</td><td>7.26e-04</td><td>-</td><td>3.4</td></tr></tbody></table>
<figure><img src="image_14.png" /><figcaption>Figure 12. Progress of the primal value and FW gap for an instance of the Spectrahedron problem.</figcaption></figure>

<table><caption>Table 10. Instances of the Spectrahedron problem ordered by difficulty. The geometric mean of the solving time is taken over all instances. The geometric mean of the dual gap is only taken over instances that could not be solved up to the tolerance. The average number of iterations is taken over all solved instances.</caption><thead><tr><th rowspan="2">Dim</th><th rowspan="2">#</th><th rowspan="2">Time (s)</th><th colspan="3">Secant</th><th colspan="3">Adaptive</th><th colspan="3">Agnostic</th><th colspan="3">Backtracking</th></tr><tr><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th><th>Time (s)</th><th>Dual gap</th><th># FW iterations</th><th>Iter per sec</th></tr></thead><tbody><tr><td>10000</td><td>5</td><td><strong>0.4</strong></td><td>&lt;1e-7</td><td><strong>454</strong></td><td>1135.0</td><td>0.4</td><td>&lt;1e-7</td><td>435</td><td>1087.5</td><td>2.5</td><td>&lt;1e-7</td><td>17323</td><td>6929.2</td><td>2.2</td><td>&lt;1e-7</td><td>4528</td><td>2058.2</td></tr><tr><td>40000</td><td>5</td><td><strong>26.3</strong></td><td>&lt;1e-7</td><td><strong>400</strong></td><td>15.2</td><td>28.2</td><td>&lt;1e-7</td><td>385</td><td>13.7</td><td>76.6</td><td>&lt;1e-7</td><td>4094</td><td>53.4</td><td>80.3</td><td>&lt;1e-7</td><td>1463</td><td>18.2</td></tr><tr><td>90000</td><td>5</td><td><strong>15.7</strong></td><td>&lt;1e-7</td><td><strong>158</strong></td><td>10.1</td><td>21.4</td><td>&lt;1e-7</td><td>300</td><td>14.0</td><td>67.4</td><td>&lt;1e-7</td><td>4442</td><td>65.9</td><td>43.1</td><td>&lt;1e-7</td><td>727</td><td>16.9</td></tr><tr><td>160000</td><td>5</td><td><strong>11.2</strong></td><td>&lt;1e-7</td><td><strong>42</strong></td><td>3.8</td><td><strong>10.7</strong></td><td>&lt;1e-7</td><td>46</td><td>4.3</td><td>145.2</td><td>3.48e-07</td><td>1788</td><td>28.1</td><td>100.6</td><td>&lt;1e-7</td><td>1097</td><td>10.9</td></tr><tr><td>250000</td><td>5</td><td><strong>7.7</strong></td><td>&lt;1e-7</td><td><strong>6</strong></td><td>0.8</td><td>9.3</td><td>&lt;1e-7</td><td>9</td><td>1.0</td><td>25.3</td><td>&lt;1e-7</td><td>103</td><td>4.1</td><td>41.5</td><td>&lt;1e-7</td><td>612</td><td>14.7</td></tr><tr><td>360000</td><td>5</td><td><strong>17.4</strong></td><td>&lt;1e-7</td><td><strong>22</strong></td><td>1.3</td><td>18.8</td><td>&lt;1e-7</td><td>25</td><td>1.3</td><td>523.9</td><td>1.73e-07</td><td>2462</td><td>9.1</td><td>366.6</td><td>&lt;1e-7</td><td>1472</td><td>4.0</td></tr><tr><td>490000</td><td>5</td><td><strong>312.8</strong></td><td>1.77e-07</td><td><strong>10</strong></td><td>0.5</td><td>357.5</td><td>4.86e-07</td><td>13</td><td>0.5</td><td>616.9</td><td>2.05e-06</td><td>5</td><td>0.4</td><td>577.1</td><td>1.10e-06</td><td>3</td><td>0.4</td></tr><tr><td>640000</td><td>5</td><td><strong>78.7</strong></td><td>&lt;1e-7</td><td><strong>9</strong></td><td>0.1</td><td>100.2</td><td>&lt;1e-7</td><td>11</td><td>0.1</td><td>594.1</td><td>5.71e-07</td><td>35</td><td>0.3</td><td>678.5</td><td>1.43e-06</td><td>112</td><td>0.3</td></tr><tr><td>810000</td><td>5</td><td><strong>525.3</strong></td><td>&lt;1e-7</td><td><strong>54</strong></td><td>0.1</td><td>587.4</td><td>&lt;1e-7</td><td>66</td><td>0.1</td><td>3600.0</td><td>3.83e-06</td><td>-</td><td>0.1</td><td>3600.0</td><td>1.65e-06</td><td>-</td><td>0.1</td></tr><tr><td>1000000</td><td>5</td><td><strong>195.7</strong></td><td>&lt;1e-7</td><td><strong>43</strong></td><td>0.2</td><td>373.1</td><td>1.66e-07</td><td>22</td><td>0.2</td><td>1464.3</td><td>2.31e-06</td><td>47</td><td>0.2</td><td>775.2</td><td>1.04e-06</td><td>6</td><td>0.2</td></tr></tbody></table>
<figure><img src="image_15.png" /><figcaption>(a) Birkhoff Problem</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>(b) Ill Conditioned Quadratic</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>(c) Nuclear</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>(d) A-Optimal Experiment Design</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>(e) D-Optimal Experiment Design</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(f) Portfolio</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(g) Simple Quadratic</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(h) Spectrahedron</figcaption></figure>

Figure 13. Computed step sizes over iteration for the Secant line search and Adaptive line search on various problem classes.
<figure><img src="image_23.png" /><figcaption>Figure 14. Progress of the primal value and FW gap for an instance of the Nuclear problem using Vanilla Frank-Wolfe.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 15. Progress of the primal value and FW gap for an instance of the Spectrahedron problem using Vanilla Frank-Wolfe.</figcaption></figure>