Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization

Anne Rubbens, Sébastien Colla, Julien M. Hendrickx · 2025

Read Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization by Anne Rubbens, Sébastien Colla, Julien M. Hendrickx (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-05466.txt.

Introduction

Anne Rubbens, Sébastien Colla, and Julien Hendrickx build a computer-aided framework that certifies how well noisy optimization methods can do in the worst case, in this 2025 arXiv paper. Their tool sits inside the Performance Estimation approach. Given a method, a class of problems, and a noise model stated through its mean and spread, it builds a semidefinite program whose answer is a convergence guarantee.

The same machinery covers plain noisy gradients, finite-sum problems, and block-coordinate schemes, with or without variance reduction. The authors run it on the stochastic gradient method under several noise rules. The rates it returns match known results and improve some, notably for bounded-variance noise and block-coordinate updates.

Catalog record

CREATORAnne Rubbens, Sébastien Colla, Julien M. Hendrickx
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Computer-aided analyses of stochastic first-order methods, via interpolation conditions for stochastic optimization Anne Rubbens, Sébastien Colla, Julien M. Hendrickx Abstract This work proposes a framework, embedded within the Performance Estimation framework (PEP), for obtaining worst-case performance guarantees on stochastic first-order methods. Given a first-order method, a function class, and a noise model with prescribed expectation and variance properties, we present a range of semidefinite programs (SDPs) of increasingly large size, whose solutions yield increasingly strong convergence guarantees on the problem. Eventually, we propose SDPs whose size depends on 2 N 2^{N} , with N N the number of iterations analyzed, that yield tight guarantees, attained by specific functions and noise distributions within these classes. On the other side of the spectrum, we propose SDPs whose size depends linearly on N N , and numerically show that, on many problems, they already provide tight guarantees. The framework accommodates a wide range of stochastic settings, with finite or infinite support, including the unstructured noise model with bounded variance, finite-sum optimization, and block-coordinate methods, in a unified manner, as guarantees apply to any setting consistent with the noise model, i.e., its expectation and variance. It covers both non-variance-reduced and variance-reduced methods. Using the framework, we analyze the stochastic gradient method under several noise models, and illustrate how the resulting numerical and analytical convergence rates connect with existing results. In particular, we provide improved convergence rates on the unstructured noise model with bounded variance and in the block-coordinate setting. Interpolation conditions for stochastic optimization. 1 Introduction Consider an unconstrained minimization problem \min_{x\in\mathbb{R}^{d}}f(x), (1) where f:\mathbb{R}^{d}\to\mathbb{R} is a differentiable convex function. To solve Eq. 1 , consider a stochastic first-order black-box optimization method, i.e., a method that relies on evaluations of f and noisy evaluations of its gradient at a sequence of iterates. Such methods include, e.g., the stochastic gradient method (SGD) whose iteration is given by \displaystyle x_{k+1}=x_{k}-\alpha_{k}(\nabla f(x_{k})+\varepsilon_{k}), (SGD) where \varepsilon_{k} is a zero-mean random variable, independent across queries. Stochastic first-order methods, as opposed to exact first-order methods, i.e., \varepsilon_{k}=0,\ \forall k , naturally arise in a wide range of contexts where one has access to (or prefers to compute) an unbiased estimator of the gradient of f rather than the gradient itself. Depending on these contexts, the distribution of of \varepsilon_{k} satisfies different assumptions. Additive noise on deterministic gradients The simplest setting arises when minimizing a deterministic function whose gradient evaluations are corrupted by additional zero-mean stochastic noise. This noise can be either relative , with variance depending on the gradient norm or absolute , with variance independent of the gradient norm. Such noise may arise in practice from limited numerical precision (e.g., floating-point computations), from simulation or measurement-based functions involving inherent randomness or error, or from intentional perturbations used to ensure data privacy, as in differentially private algorithms [ 6 ] . Stochastic optimization problems Another example is the minimization of an expectation, i.e., \displaystyle f(x)=\mathbb{E}_{\xi\sim\mathcal{D}}[f_{\xi}(x)], (2) where samples \xi\sim\mathcal{D} are available, but the distribution \mathcal{D} itself is unknown. In such cases, gradients of f are unavailable, contrary to gradients of f_{\xi} , which provide an unbiased estimator of \nabla f . Hence, methods rely on unbiased noisy evaluations \nabla f_{\xi}(x_{k})=\nabla f(x_{k})+\varepsilon_{k} . Stochastic optimization problems are particularly relevant in statistical supervised learning. Indeed, letting \mathcal{D} be the unknown distribution linking inputs and outputs, \xi be an input-output sample drawn from \mathcal{D} , x a prediction model, and f_{\xi}(x) the loss incurred by x on \xi , minimizing f corresponds to minimizing the expected risk or loss of x ; see, e.g., [ 12 , Section 3.1] . Finite-sum minimization One of the most studied categories of problems relying on stochastic optimization consists of the minimization of a large sum of functions, i.e., \displaystyle f(x)=\sum_{i=1}^{n}f_{i}(x), (3) where n is large and f_{i} ’s are differentiable convex functions. In contrast with the first two examples, exact computation of \nabla f is possible in this case, but is computationally expensive. On the other hand, choosing uniformly at random an index i\in\{1,2,\ldots,n\} , furnishes \nabla f_{i}(x) , an unbiaised estimator of \nabla f(x) , whose computation is approximately n times cheaper than the one of \nabla f(x) . As shown, e.g., in [ 11 ] , it can therefore be advantageous to minimize ( 3 ) using stochastic methods that rely on \nabla f_{i}(x_{k})=\nabla f(x_{k})+\varepsilon_{k} , instead of \nabla f(x_{k}) . Alternative ways to construct estimators of \nabla f in this setting, leading to different assumptions on \varepsilon_{k} , are discussed in Section 1.1 . Such minimization problems typically arise as approximations of ( 2 ) using n independent samples of \xi , see, e.g., [ 12 , Section 3.1] . Randomized block-coordinate descent methods Finally, another example consists of minimizing large-dimensional differentiable functions, that exhibit component-wise structure. In this setting, it is again possible to compute the exact gradient, but it is computationally advantageous to evaluate the gradient only along a single coordinate, chosen uniformly at random. In this case, methods sample d\mathbf{e}_{i}^{\top}\nabla f(x_{k})\mathbf{e}_{i}=\nabla f(x_{k})+\varepsilon_{k} , where \mathbf{e}_{i} is the i -th unit vector, d is the dimension of x , and \varepsilon_{k} is zero-mean. Such methods are known as randomized coordinate descent (RCD) methods, and can be generalized to gradient estimators along blocks of coordinates; see, e.g., [ 54 , 7 ] . Goal . Given a function class \mathcal{F} , a stochastic first-order black-box method \mathcal{M} , and the expectation and variance of the estimator of the gradient \mathcal{M} has access to, we aim at obtaining a worst-case guarantee on the performance of \mathcal{M} on \mathcal{F} , i.e., a bound on the accuracy of the solution after N iterations of \mathcal{M} , valid for all functions in \mathcal{F} and all distributions of \varepsilon satisfying the given assumptions. In particular, we say the bound is tight when attained by a specific function under a specific noise distribution. 1.1 Related works Stochastic first-order methods First-order stochastic methods, first introduced in [ 58 ] , have since then been the subject of extensive research, see, e.g., [ 10 , 12 , 32 , 37 , 55 ] and references therein. Analyses depend on (i) the method, (ii) the function class considered, and (iii) the noise model, that is, at minima, its variance and expectation, and, in some structural settings as the finite sum and the block-coordinate settings, additional information on its distribution. A widely analyzed model, though restrictive, is the additive bounded noise model ( \mathbb{E}_{\varepsilon_{k}}[\|\varepsilon_{k}\|^{2}]\leq\sigma^{2} ), see, e.g., [ 51 , 52 , 53 ] . Under this model, methods ranging from SGD, with or without iterates averaging [ 57 , 62 ] , to methods involving momentum [ 81 , 33 , 13 , 15 , 23 ] have been designed and analyzed on smooth convex functions. Stochastic first-order methods have also been extensively analyzed in the finite-sum setting f=\frac{1}{n}\sum_{i}f_{i} . Analyses depend on the properties of the f_{i} ’s, and on the way an estimator of \nabla f(x_{k}) is constructed. Classical assumptions include convexity and L_{i} -smoothness of each f_{i} , and boundedness of the variance at the optimum, i.e., \mathbb{E}[f_{i}(x_{\star})]=\sigma_{\star}\leq+\infty , where x_{\star} is a minimizer of f . Under these assumptions, ( SGD ) where gradient estimators sample \nabla

Read the complete text