On Solving Minimization and Min-Max Problems by First-Order Methods with Relative Error in Gradients

\fnm Artem \sur Vasin, \fnm Valery \sur Krivchenko, \fnm Dmitry \sur Kovalev, \fnm Fedyor \sur Stonyakin, \fnm Pavel \sur Dvurechensky, \fnm Mohammad \sur Alkousa, \fnm Nikita \sur Kornilov, \fnm Alexander \sur Gasnikov · 2025

Read On Solving Minimization and Min-Max Problems by First-Order Methods with Relative Error in Gradients by \fnm Artem \sur Vasin, \fnm Valery \sur Krivchenko, \fnm Dmitry \sur Kovalev, \fnm Fedyor \sur Stonyakin, \fnm Pavel \sur Dvurechensky, \fnm Mohammad \sur Alkousa, \fnm Nikita \sur Kornilov, \fnm Alexander \sur Gasnikov (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-2503-06628.txt.

Introduction

Artem Vasin and a team of co-authors study optimization methods that must cope with flawed slope data in a 2025 paper. First order methods steer by the slope of a cost surface, and most theory assumes that slope is exact. In practice even computer rounding adds error, and other tasks add more, so methods must tolerate a share of error in each slope.

The authors propose a fast single loop method that keeps its best rate even at the largest tolerable error, and they map how the rate slips as error grows. They extend the same questions to paired min max problems and show known methods stay robust there too.

Catalog record

CREATOR\fnm Artem \sur Vasin, \fnm Valery \sur Krivchenko, \fnm Dmitry \sur Kovalev, \fnm Fedyor \sur Stonyakin, \fnm Pavel \sur Dvurechensky, \fnm Mohammad \sur Alkousa, \fnm Nikita \sur Kornilov, \fnm Alexander \sur Gasnikov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06628

Browse the full library · About the Tower of Babel

Full text

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

On Solving Minimization and Min-Max Problems by First-Order Methods with Relative Error in Gradients \fnm Artem \sur Vasin, \fnm Valery \sur Krivchenko, \fnm Dmitry \sur Kovalev, \fnm Fedyor \sur Stonyakin, \fnm Pavel \sur Dvurechensky, \fnm Mohammad \sur Alkousa, \fnm Nikita \sur Kornilov, \fnm Alexander \sur Gasnikov Abstract First-order methods for minimization and saddle point (min-max) problems are widely used for solving large-scale problems, in particular arising in machine learning. The majority of works obtain favorable complexity guarantees of such methods, assuming that exact gradient information is available. At the same time, even the use of floating-point representation of real numbers already leads to relative error in all the computations. Relative errors also arise in such applications as bilevel optimization, inverse problems, derivative-free optimization, and inexact proximal methods. This paper answers several theoretical open questions on first-order optimization methods under relative errors in the first-order oracle. We propose an explicit single-loop accelerated gradient method that preserves optimal linear convergence rate under maximal possible relative error in the gradient, and explore the tradeoff between the relative error and deterioration in the linear convergence rate. We further explore similar questions for saddle point problems and nonlinear equations, showing, for the first time in the literature, that a variant of gradient descent-ascent and the extragradient method are robust to such errors and providing estimates for the maximum level of noise that does not break linear convergence. \MHInternalSyntaxOn \MHInternalSyntaxOff \equalcont These authors contributed equally to this work. \equalcont These authors contributed equally to this work. [4] \fnm Nazarii \sur Tupitsa 1] \orgdiv Department of Applied Mathematics, \orgname Moscow Institute of Physics and Technology (MIPT), \orgaddress \city Moscow, \country Russia 2] \orgname Yandex & Institute for System Programming of the Russian Academy of Sciences (ISP RAS), \orgaddress \city Moscow, \country Russia 3] \orgname Innopolis University, \orgaddress \city Innopolis, \country Russia 4] \orgname Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), \orgaddress \city Abu Dhabi, \country United Arab Emirates 5] \orgname Weierstrass Institute for Applied Analysis and Stochastics (WIAS), \orgaddress \city Berlin, \country Germany 6] \orgname Skolkovo Institute of Science and Technology (Skoltech), \orgaddress \city Moscow, \country Russia 7] \orgname Steklov Mathematical Institute of the Russian Academy of Sciences, \orgaddress \city Moscow, \country Russia 8] \orgname Institute for Information Transmission Problems, \orgaddress \city Moscow, \country Russia keywords: first-order methods, inexact gradients, nonlinear equations, saddle point problems 1 Introduction Numerical methods in general and continuous optimization algorithms in particular inevitably rely on the floating-point representation of real numbers, which is the most common and practical way to handle real numbers in computational systems. This approach allows for efficient storage and arithmetic operations while accommodating a wide range of values, albeit with some precision limitations, described by IEEE754 standard [ 1 ] . As described in [ 2 ] the approximation error of a positive real number x with a floating-point number \hat{x} is given by \displaystyle|x-\hat{x}|\leqslant\delta|x|, (1) where \delta=2^{-p} is called machine delta, and a precision p is a number of bits used for the mantissa (or significant digits) in the floating-point representation. Indeed, we can denote a number in floating-point format as: \begin{gathered}\hat{x}=(-1)^{s}B\cdot 2^{E-E_{0}},\quad B=1.b_{0}b_{1}\dots b_{p},\;b_{j}\in\{0,1\},\;s\in\{0,1\}.\end{gathered} (2) We call machine delta \delta such gap between 1 and next larger floating point number. One can see, that \delta=0.0\dots 1=2^{-p} . Using notation from [ 2 ] we can define unit in the last place function: \text{ulp}(\hat{x})=0.0\dots 1\cdot 2^{E-E_{0}}=\delta 2^{E-E_{0}} . Note, that for positive floating-point numbers \hat{x} , value \hat{x}+\text{ulp}(\hat{x}) will be next larger floating point number. Estimating the error of approximation for a positive real number x with floating-point numbers ( 2 ), we obtain: |x-\hat{x}|\leqslant\text{ulp}(\hat{x})=\delta 2^{E-E_{0}}\leqslant\delta B2^{E-E_{0}}\leqslant\delta\hat{x}\leqslant\delta|x| . Here we assume, that \hat{x} is a lower estimation for x . We see that \delta is a bound for the relative error of this approximation. In other words, the use of floating-point numbers of the IEEE754 standard leads to relative errors in all the computations. For example, using single-precision 32-bit float (FP32) ( p=23,E_{0}=127,0\leqslant E\leqslant 255 ) we obtain \delta=2^{-23}\approx 1.19e-07 , double-precision 64-bit float (FP64) ( p=52,E_{0}=1023,0\leqslant E\leqslant 2047 ) we obtain \delta=2^{-52}\approx 2.22e-16 , half-precision 16-bit float (FP16) ( p=10,E_{0}=15,0\leqslant E\leqslant 31 ) we obtain \delta=2^{-10}\approx 9.77e-04 . From inequality ( 1 ), it is evident that the approximation error is relative rather than absolute, meaning that it depends on the magnitude of the number x . The study of the influence of relative error is motivated by modern applications, where a less accurate representation of real numbers such as quantization is widely used [ 3 , 4 , 5 ] to reduce model size and improve inference speed, maintaining efficiency [ 6 ] , but increasing relative error. Such relative errors potentially influence all the machine computations, of which we are particularly concerned with optimization in a wider sense. Optimization with inexact gradients. First, motivated by the widespread use of optimization methods in ML, we consider an unconstrained optimization problem \min\limits_{x\in\mathbb{R}^{d}}f(x), (3) where f:\mathbb{R}^{d}\longrightarrow\mathbb{R} is continuously differentiable function, and focus on gradient-type methods with relative error (or relative noise) in the gradient. More precisely, following [ 7 ] , we assume that an algorithm has access to an inexact gradient \widetilde{\nabla}f(x) , that for some \alpha\in[0,1) and all x satisfies \displaystyle\|\widetilde{\nabla}f(x)-\nabla f(x)\|_{2}\leqslant\alpha\|\nabla f(x)\|_{2}. (4) Apart from floating-point representation, relative error is natural for implicit optimization problems where evaluating the gradient or objective value requires solving an auxiliary problem that cannot be solved exactly. For example, in PDE-constrained optimization, the constraints are given by partial differential equations (PDEs), which add significant computational challenges [ 8 , 9 ] . Similarly, in bilevel optimization, the upper-level problem includes constraints defined by the solution to a lower-level problem, leading to additional inexactness [ 10 , 11 , 12 ] . Inexact gradients are also common in optimal control and inverse problems, where solving ODEs or PDEs is needed to compute the gradient of the objective function [ 13 ] . Also, relative errors appear in the analysis of gradient approximation in Derivative Free Optimization [ 14 ] . Last but not least, relative error often appears in inexact proximal methods that are used as an envelope to construct optimal methods in different contexts, see, e.g., [ 15 , 16 ] . Then a non-optimal method is used to evaluate inexact proximal step and the inexactness is measured relatively. Yet, unlike our paper, the first-order oracle in these methods is assumed to be exact. For a deeper exploration of gradient inexactness, refer to [ 17 , 7 , 18 , 19 , 20 , 21 ] and the references therein. We underline that most of these works focus on absolute error in the gradients, and the literature covering the setting of relative error ( 4 ) is quite scarce. Given the above applications, it is important to understand what theoretical guarantees it is possible to obtain for optimization algorithms under relative inexactness. Remark 1 . It may seem that the relative inexactness assumption is quite strong since it implies that the quality of the approximate gradient \widetilde{\nabla}f(x) improves as the algorithm converges to a stationary point where \nabla f(x)=0 . At the same time, this assumption holds in a number of applications, in particular, listed above, i.e., it

Read the complete text