Secant Line Search for Frank-Wolfe Algorithms

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

Read Secant Line Search for Frank-Wolfe Algorithms by Deborah Hendrych, Sebastian Pokutta, Mathieu Besançon, David Martínez-Rubio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18775.txt.

Introduction

A family of optimization methods moves toward a goal by always stepping toward the best corner of the allowed region, and the step size makes or breaks their speed. Deborah Hendrych and co-authors give those methods a smarter stride in a 2025 paper, borrowed from the classic secant trick for finding roots. The stride adapts to how smooth the ground is right where the walker stands.

Full line search finds the best stride but pays dearly for it. The secant stride matches that quality at a far lower cost, which lifts the true speed of the whole method. The team proves the guarantees behind the claim under mild conditions. Tests on standard problems back the math. The strategy drops into any method of the family without changing its bones.

Catalog record

CREATORDeborah Hendrych, Sebastian Pokutta, Mathieu Besançon, David Martínez-Rubio
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-18775

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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. † † affiliationnotice: Equal contribution 1 Introduction We are interested in solving constrained optimization problems of the form \min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x}) (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 \mathbf{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 ; Altschuler & Parrilo, 2024a ; Altschuler & Parrilo, 2024b ) , 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) ; Malitsky & Mishchenko (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 \mathbf{x},\mathbf{y} as \frac{\left\|\mathbf{x}-\mathbf{y}\right\|}{\left\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\right\|} and then use this (with modifications) as the step-size \gamma_{t} for an update of the form \mathbf{x}_{t+1}\leftarrow\mathbf{x}_{t}-\gamma_{t}\nabla f(\mathbf{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 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 incompatible 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 equality 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\geq 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 ; Wirth et al., 2024 ) ) (ii) so-called short-steps, which are effectively the solution arising 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 current 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 ; Carderera et al., 2024 ) , which was originally developed for (generalized) 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 descent direction. The adaptive step sizes from Pedregosa et al. (2020) ; Pokutta (2024) test that a local Lipschitz smoothness estimate produces a valid lower bound on the primal progress while the monotonic step size from Carderera et al. (2021) ; Carderera et al. (2024) tests primal improvement on top of an open-loop step-size schedule. Other notable recent approaches in the context of unconstrained 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 heavily studied in recent work (see e.g., ( Jin & Mokhtari, 2023 ; Rodomanov & Nesterov, 2022 ; Rodomanov & Nesterov, 2021 ) ) to provide finer and finite-time convergence guarantees. While highly interesting 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 ; Polak, 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,

Read the complete text