Frank-Wolfe Algorithms for ( L 0 , L 1 ) (L_{0},L_{1}) -smooth functions

A.A. Vyguzov, F.S. Stonyakin · 2025

Read Frank-Wolfe Algorithms for ( L 0 , L 1 ) (L_{0},L_{1}) -smooth functions by A.A. Vyguzov, F.S. Stonyakin (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-2510-16468.txt.

Introduction

A. A. Vyguzov and F. S. Stonyakin refine a classic solver in their 2025 paper. The Frank-Wolfe method solves smooth tasks by steps toward a corner point. Smoothness here means how fast the slope of a cost can change. Their new form suits costs whose smoothness blends two rates at once.

The new method provably meets its goal faster than the classic form. A second, adaptive form tunes its own smoothness rates as it runs. That tuning adds speed and keeps the steps stable. Number tests back the theory with clear wins over past forms. Faster solvers help in machine learning, where such tasks run at huge scale. The pair share full proofs for both new forms.

Catalog record

CREATORA.A. Vyguzov, F.S. Stonyakin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16468

Browse the full library · About the Tower of Babel

Full text

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

Frank-Wolfe Algorithms for ( L 0 , L 1 ) (L_{0},L_{1}) -smooth functions A.A. Vyguzov, F.S. Stonyakin Abstract We propose a new version of the Frank–Wolfe method, called the ( L 0 , L 1 ) (L_{0},L_{1}) -Frank–Wolfe algorithm, developed for optimization problems with ( L 0 , L 1 ) (L_{0},L_{1}) -smooth objectives. We establish that this algorithm achieves superior theoretical convergence rates compared to the classical Frank–Wolfe method. In addition, we introduce a novel adaptive procedure, termed the Adaptive ( L 0 , L 1 ) (L_{0},L_{1}) -Frank–Wolfe algorithm, which dynamically adjusts the smoothness parameters to further improve performance and stability. Comprehensive numerical experiments 1 1 1 The code can be downloaded here confirm the theoretical results and demonstrate the clear practical advantages of both proposed algorithms over existing Frank–Wolfe variants. 1 Introduction In this paper, we consider the minimization problem \displaystyle\min_{x\in Q}\;f(x), (1) where Q is a convex compact set and f is a convex and (L_{0},L_{1}) -smooth function. A function f is said to be (L_{0},L_{1}) -smooth if, for all x , it satisfies \|\nabla^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla f(x)\|, (2) for some constants L_{0},L_{1}>0 (throughout this paper, unless specified otherwise, we use the standard Euclidean norm \|.\| for vectors, and the standard spectral norm \|.\| for matrices). This notion was introduced in [ 21 ] , where it was used to explain the superior convergence behavior of the clipped gradient descent method on deep learning problems compared to standard gradient descent (GD). Later, in [ 20 ] (see Remark 2.3), this definition was extended from twice differentiable to once differentiable functions. Specifically, a differentiable function f is said to be (L_{0},L_{1}) -smooth if, for all x,y\in\mathbb{R}^{d} such that \|x-y\|\leq\frac{1}{L_{1}} , we have \|\nabla f(x)-\nabla f(y)\|\leq(L_{0}+L_{1}\|\nabla f(y)\|)\|x-y\|. (3) This condition generalizes the standard L -smoothness assumption. Indeed, when L_{1}=0 , the inequalities above reduce to the classical definition of L -smoothness. Hence, the (L_{0},L_{1}) -smoothness condition defines a broader class of functions than the conventional L -smooth case. Motivated by this generalization, we modify the standard shortest-step rule in the Frank–Wolfe method. Let us briefly recall the classical Frank–Wolfe algorithm [ 6 ] with the shortest-step rule [ 10 ] . The update rule is given by x_{k+1}=x_{k}+\alpha_{k}d_{k}, (4) where k is the iteration index, \alpha_{k}\in[0,1] , d_{k}=s_{k}-x_{k} , and s_{k}\in\mathrm{LMO}_{Q}(\nabla f(x_{k}))=\arg\min_{z\in Q}\,(\nabla f(x_{k})^{\top}z) (5) is the output of the linear minimization oracle (LMO) over Q . In the case of the shortest-step rule, the step size is chosen as \alpha_{k}:=\min\left\{1,\frac{-\nabla f(x_{k})^{\top}d_{k}}{L\|d_{k}\|^{2}}\right\}. This observation motivates us to extend the Frank–Wolfe method ( 4 ) to (L_{0},L_{1}) -smooth objectives by introducing the following step-size rule: \alpha_{k}:=\min\left\{1,\frac{-\nabla f(x_{k})^{\top}d_{k}}{(L_{0}+L_{1}\|\nabla f(x_{k})\|)\,\|d_{k}\|^{2}_{2}\,e}\right\}. (6) It is well known (see, for example, [ 3 ] , [ 2 ] , [ 10 ] ) that the Frank–Wolfe method achieves a linear convergence rate under additional assumptions. Our theoretical analysis shows that the proposed Frank–Wolfe variant, with the step size defined in ( 6 ), exhibits a superior convergence rate. The acceleration arises from the fact that L_{1}<L and L_{0}<L , where L denotes the standard smoothness parameter. When the solution lies in the interior of a function satisfying the PL condition, our algorithm is significantly faster than the standard method due to the absence of the PL-condition parameter \mu in the convergence rate when L_{0}>L_{1}|\nabla f(x_{k})| . A summary of the corresponding convergence rate estimates is provided in Table 1 . Moreover, as mentioned earlier, not all (L_{0},L_{1}) -smooth functions are L -smooth, meaning that our algorithm applies to a broader class of functions. To illustrate this, we list several examples (see [ 7 ] ): • f(x)=\|x\|^{n} , where n is a positive integer, with L_{0}=2n and L_{1}=2n-1 ; • f(x)=\exp(a^{\top}x) , where L_{0}=0 and L_{1}=\|a\| ; • the logistic loss f(x)=\log(1+\exp(-a^{\top}x)) , where a\in\mathbb{R}^{d} , for which L_{0}=0 and L_{1}=\|a\| , while the standard smoothness constant is L=\|a\|^{2} , which is typically much larger than L_{1} . Table 1: Convergence rates of the standard Frank–Wolfe (FW) method with the shortest step size (see, e.g., [ 3 ] , [ 10 ] ) and the proposed (L_{0},L_{1}) -FW method ( 1 ) under different assumptions. Abbreviations: PL – Polyak–Łojasiewicz condition; C – convex; SC – strongly convex. Here, c is the constant from the inequality \|\nabla f(x)\|\geq c>0 , \lambda denotes the strong convexity constant of the feasible set (see Definition 2 ), \mu is the PL-condition constant (see Definition 3 ), T s the number of iterations for which L_{0}\leq L_{1}\|\nabla f(x)\| and K is the number of iterations for which L_{0}>L_{1}\|\nabla f(x)\| . Algorithm Objective Domain Assumptions Rate FW C; L -smooth SC \|\nabla f(x_{k})\|\geq c f(x_{k})-f^{\ast}\leq(f(x_{0})-f^{\ast})\min\!\left\{\frac{1}{2},\,1-\frac{\lambda c}{2L}\right\}^{\,k-1} (L_{0},L_{1}) -FW C; (L_{0},L_{1}) -sm. SC \|\nabla f(x_{k})\|\geq c f(x_{k+1})-f^{*} \leq\left(f(x_{0})-f^{*}\right)\cdot \min\left\{{\frac{1}{2}},1-\frac{\lambda}{e}\frac{1}{2L_{1}}\right\}^{T}\cdot \min\left\{\frac{1}{2},1-\frac{\lambda}{e}\frac{c}{2L_{0}}\right\}^{K} FW C; PL; L -smooth C B(x^{\ast},r)\subseteq Q f(x_{k})-f^{\ast}\leq(f(x_{0})-f^{\ast})\min\!\left\{\frac{1}{2},\,1-\frac{r^{2}\mu^{2}}{2LD^{2}}\right\}^{\,k-1} (L_{0},L_{1}) -FW C; PL; (L_{0},L_{1}) -sm. C B(x^{\ast},r)\subseteq Q f(x_{k+1})-f^{*}\leq (f(x_{0})-f^{*})\cdot \min\left\{\frac{1}{2},1-\frac{r}{4eL_{1}D^{2}}\right\}^{T}\cdot \min\left\{\frac{1}{2},1-\frac{r^{2}\mu}{2eL_{0}D^{2}}\right\}^{K} FW C; L -smooth C f(x_{k+1})-f^{*}\leq\frac{2LD^{2}}{k+3} (L_{0},L_{1}) -FW C; (L_{0},L_{1}) -smooth C f(x^{k})-f(x^{*}) \leq\frac{2e\left(L_{0}+L_{1}\sup_{k}\|\nabla f(x_{k})\|\right)D^{2}}{k+3} Next, we introduce a novel adaptive procedure that updates each of the parameters L_{0} and L_{1} independently. This procedure differs from standard adaptive techniques—originally proposed in [ 12 ] and later extended to the Frank–Wolfe method in [ 1 ] , [ 19 ] , and [ 14 ] —where the L parameter is halved before each iteration and then doubled until a specific condition is satisfied. In our case, we have two parameters, allowing us to adjust them proportionally to their contribution to the overall term in the step size ( 6 ). This makes the adaptation more flexible and prevents overly aggressive changes at each iteration. In our approach, the parameters are updated differently. For implementation details, see Algorithm 2 . We will demonstrate in Section 5 that this adaptive mechanism yields a significant performance improvement and consistently outperforms all baseline methods across various experimental settings. 1.1 Contributions and Outline Our main contributions are summarized as follows: • We propose a new variant of the Frank–Wolfe algorithm designed for (L_{0},L_{1}) -smooth objectives and provide a theoretical analysis showing that it achieves superior convergence rates compared to the classical Frank–Wolfe method. • We support our theoretical findings by numerical experiments demonstrating that the proposed algorithm significantly outperforms the standard variant. • We introduce a novel adaptive procedure for dynamically updating the (L_{0},L_{1}) parameters. Experimental results show that this adaptation mechanism consistently yields substantial performance improvements across all tested settings. • We prove that, in the general convex case, the proposed algorithm is never worse than the classical Frank–Wolfe method and maintains the optimal convergence rate of O(1/k) . 1.2 Related works A variety of optimization algorithms have been analyzed under the (L_{0},L_{1}) -smoothness framework. The pioneering work [ 21 ] studied the clipped gradient descent algorithm, later extended in [ 20 ] to include momentum acceleration. Further improvements for the stochastic setting were proposed in [ 9 ] . Subsequent analyses for gradient descent on (L_{0},L_{1}) -smooth functions include (L_{0},L_{1}) -GD ( [ 7 ] , [ 18 ] , [ 11 ] ), Normalized GD ( [ 22 ] , [ 18 ] , [ 4 ] ), GD with Polyak step size ( [ 7 ] , [ 18 ] ), random

Read the complete text