A Fully Adaptive Frank-Wolfe Algorithm for Relatively Smooth Problems and Its Application to Centralized Distributed Optimization.

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

Read A Fully Adaptive Frank-Wolfe Algorithm for Relatively Smooth Problems and Its Application to Centralized Distributed Optimization. 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-2507-05669.txt.

Introduction

A A Vyguzov and F S Stonyakin make a classic optimizer tune itself. Their 2025 paper revisits the Frank-Wolfe method for constrained problems whose objectives are smooth only relative to a reference shape, a setting where fixed step rules need constants nobody knows.

Their fully adaptive variant adjusts its step from local clues alone and still converges, at a linear rate when the objective is also strongly curved in the relative sense. The second half shows the setting is not exotic. In shared distributed optimization, a variance-style assumption on gradients makes the global objective relatively strongly curved on its own. There the adaptive method provably accelerates, thanks to a better relative condition number. Theory and application arrive in one package.

Catalog record

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

Source: https://arxiv.org/abs/2507-05669

Browse the full library · About the Tower of Babel

Full text

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

A Fully Adaptive Frank-Wolfe Algorithm for Relatively Smooth Problems and Its Application to Centralized Distributed Optimization. A.A. Vyguzov, F.S. Stonyakin Abstract We study the Frank-Wolfe algorithm for constrained optimization problems with relatively smooth and relatively strongly convex objectives. Building upon our previous work, we propose a fully adaptive variant of the Frank-Wolfe method that dynamically adjusts the step size based on both the relative smoothness constant and the Triangle Scaling Exponent (TSE) of the Bregman divergence. Our method does not require prior knowledge of the function parameters and guarantees convergence using only local information. We establish a linear convergence rate under relative strong convexity and provide a detailed theoretical analysis of the proposed adaptive step-size rule. Furthermore, we demonstrate how relative smoothness and strong convexity naturally arise in the setting of centralized distributed optimization. Under a variance-type assumption on the gradients, we show that the global objective becomes relatively strongly convex with respect to the Bregman divergence generated by a local function. This structure allows us to apply our adaptive Frank-Wolfe algorithm, leading to provable acceleration due to an improved relative condition number. We support our theoretical findings with numerical experiments, showing that the proposed method outperforms both non-adaptive and partially adaptive variants, especially in distributed settings. 1 Introduction We consider the following constrained optimization problem: \displaystyle\min_{x\in Q}\quad f(x), (1) where Q is a convex and compact subset of \mathbb{R}^{n} , and f:Q\to\mathbb{R} is a convex function. We denote by x^{*} and f^{*} the solution and optimal value of problem ( 1 ), respectively. We assume that f in ( 1 ) is relatively smooth ( [ 2 ] , [ 19 ] ) with smoothness constant L>0 , meaning it satisfies the following condition: f(x)\leq f(y)+\langle\nabla f(y),x-y\rangle+LV(x,y),\quad\forall x,y\in Q, (2) where V(x,y) is the Bregman divergence between x and y , defined as V(x,y)=h(x)-h(y)-\langle\nabla h(y),x-y\rangle . Here, h is a convex (not necessarily strongly convex) reference function. Furthermore, we assume that the divergence function V(x,y) in ( 2 ) satisfies the Triangle Scaling Exponent (TSE) property with some constant \gamma\in(1,2] , as introduced in [ 13 ] : V((1-\theta)x+\theta z,(1-\theta)x+\theta\tilde{z})\leq\theta^{\gamma}V(z,\tilde{z}),\quad\forall\theta\in[0,1],\quad\forall x,z,\tilde{z}\in Q. (3) The TSE property plays a key role in the convergence analysis of optimization algorithms under relative smoothness. The value of \gamma depends on the choice of divergence. For instance, for the Euclidean distance (a special case of Bregman divergence) or the Kullback–Leibler divergence, we have \gamma=1 . For other divergences, \gamma may not be explicitly known. Notably, for the Itakura–Saito (IS) divergence, it is known that \gamma>0.5 , although the exact value remains unspecified. In this paper, we continue the development of the Frank-Wolfe method for relatively smooth objectives, initiated in [ 27 ] . We propose a modified adaptive step size for the Bregman setting, which depends not only on the parameter L from ( 2 ), but also on the TSE exponent \gamma from ( 3 ): \alpha_{k}:=\min\left\{\left(\frac{-\langle\nabla f(x_{k}),d_{k}\rangle}{2L_{k}V(s_{k},x_{k})}\right)^{\frac{1}{\gamma_{k}-1}},1\right\}. (4) The Frank-Wolfe update step is given by: x_{k+1}=x_{k}+\alpha_{k}d_{k}, (5) where \mathrm{LMO}_{Q}(g)=\arg\min_{z\in Q}g^{\top}z is the linear minimization oracle (LMO), and d_{k}=s_{k}-x_{k} is the descent direction, with s_{k}\in\mathrm{LMO}_{Q}(\nabla f(x_{k})) . A similar idea for adapting the step size was explored in [ 25 ] and [ 21 ] , but our condition for adaptation and the corresponding procedure differ, which leads to distinct convergence behavior and analysis. We establish a linear convergence rate for the proposed method under relative strong convexity. This analysis has not been presented in prior works. Definition 1 A function f is said to be relatively strongly convex if it is differentiable on Q and there exists \mu>0 such that the following condition holds: f(x)\geq f(y)+\langle\nabla f(y),x-y\rangle+\mu LV(x,y),\quad\forall x,y\in Q. (6) The Frank-Wolfe method is well-suited for distributed optimization problems due to its simpler implementation compared to gradient-based methods. Constrained problems over structured domains also naturally occur in many applications; see, for instance, the survey [ 11 ] . Our result enables the application of the method to centralized distributed optimization problems. Specifically, we consider the following objective: F(x)=\frac{1}{m}\sum_{j=1}^{m}f_{j}(x)\to\min, (7) where each function f_{j} corresponds to a node (e.g., a computer) in a network, which computes \nabla f_{j} . We assume the existence of a central node that maintains access to the aggregate gradient: \tilde{F}(x)=\frac{1}{\tilde{m}}\sum_{l=1}^{\tilde{m}}f_{l}(x)\quad\text{(or simply $f_{1}(x)$)}. (8) The remaining nodes transmit their gradient information \nabla f_{j} to the central node. The central node thus has access to \nabla F(x) , but not necessarily to the full function value F(x) ; it may only know \tilde{F}(x) . Additionally, in our analysis we employ the assumption of so-called statistical similarity : \|\nabla F(x)-\nabla\tilde{F}(x)-\nabla F(y)+\nabla\tilde{F}(y)\|^{2}\leq\sigma\|x-y\|^{2},\quad\forall x,y, where \sigma>0 quantifies the degree of similarity between the Hessian matrices of the local and global loss functions. Statistical similarity is a widely used technique for accelerating distributed optimization methods (see [ 24 ] , [ 1 ] , [ 23 ] , [ 26 ] ; and in the context of variational inequalities, see [ 4 ] , [ 3 ] ). These works leverage the similarity structure of the data to obtain improved theoretical guarantees. However, they do not address constrained problems or the Frank-Wolfe method. The idea of improving the condition number via relative smoothness and statistical similarity was initially introduced in [ 15 ] , where it was applied to empirical risk minimization using gradient-based algorithms. In this work, we extend this approach to the Frank-Wolfe method. 1.1 Contributions and Outline Our main contributions are as follows: • We propose a fully adaptive Frank-Wolfe method with Bregman step size for relatively smooth problems. The method does not rely on prior knowledge of problem-specific parameters. • A linear convergence rate is established for relatively smooth and relatively strongly convex problems, given additional assumptions on the exact solution. • We theoretically demonstrate that the proposed method outperforms its Euclidean counterpart in the centralized distributed optimization setting. • We provide empirical evidence that our method outperforms non-adaptive and partially adaptive variants. 1.2 Related works The Frank-Wolfe algorithm originally introduced in [ 10 ] , also known as the Conditional Gradient Method [ 18 ] , has become a cornerstone in modern optimization due to its projection-free nature and its suitability for constrained problems. The algorithm has computational advantages in high-dimensional settings and its compatibility with structured constraint sets such as simplices, trace-norm balls, and polytopes. Unlike classical projected gradient methods, Frank-Wolfe replaces the often costly projection step with a cheaper linear minimization oracle making it especially attractive in large-scale applications where projection is prohibitively expensive (see more on this in [ 7 ] and [ 6 ] Table 1.1). Its simplicity, interpretability, and natural ability to produce sparse or low-rank solutions have led to successful applications in machine learning, signal processing, and statistics (see more about applications in reviews [ 6 ] , [ 5 ] , [ 22 ] ) The resurgence of interest in Frank-Wolfe methods has also led to an array of algorithmic extensions aimed at improving convergence rates, accommodating stochastic or inexact oracles (see [ 14 ] and [ 12 ] ), and exploiting structure in modern optimization problems. Notable developments include the Away-Step Frank-Wolfe [ 16 ] , pairwise variants [ 17 ] , and adaptive step-size schemes [ 21 ] .

Read the complete text