betaFeedback

WorksMathematics

Adaptive First-Order Methods with Composite Gradient Error

Abstract

We study first-order optimization with inexact gradients whose errors combine a component proportional to the true gradient norm and a uniformly bounded absolute component. We develop an adaptive gradient descent scheme that selects estimates of the smoothness constant and both error parameters through a computable backtracking condition using exact function values. Its analysis yields convergence for smooth objectives and functions satisfying Polyak-Lojasiewicz condition. For strongly convex objectives, we propose a composite-error intermediate gradient method, that adapts to unknown smoothness while using known error bounds and a strong convexity parameter μμ. With fixed smoothness LL, acceleration is retained when α=O((μ/L)1/4)α=\mathcal{O}\left(\left(μ/ L \right)^{1/4}\right), larger admissible errors yield intermediate rates. Throughout the range 0⩽α⩽1/30 \leqslant α\leqslant 1/3, the absolute error bound δδ contributes at most O(δ2/μ)\mathcal{O} \left(δ^2/μ\right) to the objective residual, without additional amplification by the condition number.

Introduction

Inexact gradient information affects both the progress of an optimization method and the accuracy of its output. Relative errors scale with the magnitude of the true gradient and therefore diminish as the gradient vanishes, whereas an absolute error component may persist near a minimizer. When the smoothness constant or the error parameters are unknown, the algorithm must also determine suitable step sizes from the information available during the iteration. The purpose of this paper is to study these issues within a common deterministic error model and to develop adaptive gradient methods with explicit convergence guarantees.

We consider the unconstrained minimization problem:

min⁡x∈Rnf(x),(1)\min_{x \in\mathbb{R}^n} f(x), \tag*{(1)}

where f:Rn→Rf : \mathbb{R}^n \to\mathbb{R} is differentiable. We assume that the minimum is attained and write f∗=min⁡x∈Rnf(x)f^* = \min_{x \in\mathbb{R}^n} f(x). Given an initial point x0x^0, let x∗x^* be a minimizer closest to x0x^0 in the Euclidean norm, and set R=∥x0−x∗∥2R = \lVert x^0 - x^* \rVert_2. Throughout, ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle and ∥⋅∥2\lVert\cdot\rVert_2 denote the Euclidean inner product and norm, respectively. For a differentiable function, convexity is characterized by

(∀x,y∈Rn)f(x)+⟨∇f(x),y−x⟩≤f(y).(2)(\forall x,y \in\mathbb{R}^{n})\qquad f(x) + \langle\nabla f(x),y-x\rangle\leq f(y). \tag*{(2)}

We express LL-smoothness, with L>0L > 0, through the quadratic upper model

(∀x,y∈Rn)f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥x−y∥22.(3)(\forall x,y \in\mathbb{R}^{n})\qquad f(y) \leq f(x) + \langle\nabla f(x),y-x\rangle+ \frac{L}{2}\lVert x-y\rVert_{2}^{2}. \tag*{(3)}

For the analysis of the intermediate method, we additionally assume that ff is μ\mu-strongly convex, with μ>0\mu> 0:

(∀x,y∈Rn)f(x)+⟨∇f(x),y−x⟩+μ2∥x−y∥22≤f(y).(4)(\forall x,y \in\mathbb{R}^{n})\qquad f(x) + \langle\nabla f(x),y-x\rangle+ \frac{\mu}{2}\lVert x-y\rVert_{2}^{2} \leq f(y). \tag*{(4)}

In this case the minimizer is unique. Some of our gradient descent results instead use the Polyak–Łojasiewicz (PL) condition with parameter μ>0\mu> 0:

(∀x∈Rn)12μ∥∇f(x)∥22≥f(x)−f∗.(5)(\forall x \in\mathbb{R}^{n})\qquad\frac{1}{2\mu}\lVert\nabla f(x)\rVert_{2}^{2} \geq f(x)-f^{*}. \tag*{(5)}

We consider gradient-based first-order methods; standard treatments of this class are given in [2, 3, 6, 7, 8, 9]. When gradients are queried at the iterates, the usual linear-span restriction takes the form

xN+1∈x0+span⁡{∇~f(x0),∇~f(x1),…,∇~f(xN)},(6)x^{N+1} \in x^{0} + \operatorname{span}\left\{ \widetilde{\nabla} f(x^{0}),\widetilde{\nabla} f(x^{1}),\ldots,\widetilde{\nabla} f(x^{N}) \right\}, \tag*{(6)}

where ∇~f(xk)\widetilde{\nabla} f(x^{k}) is an approximation for ∇f(xk)\nabla f(x^{k}).

The exact gradient is assumed to be unavailable. Instead, an inexact oracle returns ∇~f(x)\widetilde{\nabla} f(x) satisfying the composite error condition

(∀x∈Rn)∥∇~f(x)−∇f(x)∥22≤α∥∇f(x)∥22+δ,0≤α<1,0≤δ.(7)(\forall x \in\mathbb{R}^{n})\qquad\lVert\widetilde{\nabla} f(x)-\nabla f(x)\rVert_{2}^{2} \leq\alpha\lVert\nabla f(x)\rVert_{2}^{2}+\delta,\qquad0 \leq\alpha< 1, 0 \leq\delta. \tag*{(7)}

Both adaptive procedures use exact function values to evaluate their acceptance conditions. Thus, the inexactness considered here concerns the gradient, not the function values. The proposed methods can also be run using exact specifications of the function and the error, in which case the function values themselves need not be used.

Various models of inexact first-order information have been studied in [1, 4, 5, 6, 9, 11]. Our analysis is formulated directly in terms of the norm bound (7). To make its two components explicit, define ζ(x)=∇~f(x)−∇f(x)\zeta(x)=\widetilde{\nabla} f(x)-\nabla f(x). By Lemma A.5, condition (7) is equivalent to the existence of a decomposition

ζ(x)=∇~f(x)−∇f(x)=ζa(x)+ζr(x),∥ζa(x)∥2≤δ,∥ζr(x)∥2≤α∥∇f(x)∥2.(8)\zeta(x)=\widetilde{\nabla} f(x)-\nabla f(x)=\zeta_{a}(x)+\zeta_{r}(x),\qquad\lVert\zeta_{a}(x)\rVert_{2}\leq\delta,\qquad\lVert\zeta_{r}(x)\rVert_{2}\leq\alpha\lVert\nabla f(x)\rVert_{2}. \tag*{(8)}

The purely relative model is obtained by setting δ=0\delta=0:

(∀x∈Rn)∥∇~f(x)−∇f(x)∥22≤α∥∇f(x)∥22.(9)(\forall x \in\mathbb{R}^{n})\qquad\lVert\widetilde{\nabla} f(x)-\nabla f(x)\rVert_{2}^{2}\leq\alpha\lVert\nabla f(x)\rVert_{2}^{2}. \tag*{(9)}

The purely absolute model corresponds to α=0\alpha= 0:

(∀x∈Rn)∥∇~f(x)−∇f(x)∥2≤δ.(10)(\forall x \in\mathbb{R}^{n}) \qquad\lVert\widetilde{\nabla} f(x) - \nabla f(x) \rVert_{2} \le\delta. \tag*{(10)}

Contributions. We develop two adaptive procedures with different information requirements. The first is a gradient descent method that allows adaptation of the smoothness estimate and of both error estimates. Separate switches determine which quantities are updated, while a shared backtracking index controls the active estimations. We obtain convergence for smooth and PL objectives. Regularization technique yields result for convex problems with purely relative gradient error. The second procedure is the Algorithm 2 (CE-AIGM). For strongly convex objectives, it adapts the smoothness estimate while keeping the strong convexity parameter and the error bounds fixed and known. In the fixed-smoothness setting, the accelerated convergence is retained when α=O((μ/L)1/4)\alpha= O((\mu/L)^{1/4}), larger admissible relative errors lead to intermediate guarantees (see Theorem 3.1).

Organization. § 2 presents adaptive gradient descent and its stationarity, PL, and regularization-based guarantees. § 3 introduces CE-AIGM and explains its accelerated and intermediate regimes. Auxiliary inequalities, regularization lemmas, and the proofs for the two algorithms are collected in Appendix § 5-D.

Adaptive gradient descent

We first consider gradient descent when the smoothness constant and the parameters of the composite error model are not necessarily known. Algorithm 1 uses a computable backtracking condition to select a step together with the error estimates needed to accept it. It also provides options FαF_{\alpha}, FδF_{\delta}, and FLF_{L} that enable or disable the corresponding adaptivity. The active parameters nevertheless share a single search index, rather than being estimated through three independent searches. An estimate whose adaptation is disabled must already be a guaranteed upper bound on the corresponding parameter:

Fα=false⇒α0≥α,Fδ=false⇒δ0≥δ,FL=false⇒L0≥L.F_{\alpha} = \text{false} \Rightarrow\alpha_{0} \ge\alpha,\quad F_{\delta} = \text{false} \Rightarrow\delta_{0} \ge\delta,\quad F_{L} = \text{false} \Rightarrow L_{0} \ge L.

For the maxima defining the search bounds below, we use the conventions 0/0=10/0 = 1 and log⁡20=−∞\log_{2} 0 = -\infty.

Algorithm 1 Adaptive Gradient Descent (x0x^0, NN, α0\alpha_0, FαF_\alpha, δ0\delta_0, FδF_\delta, L0L_0, FLF_L)

1: Input: Starting point x0x^0, number of steps N≥1N \ge1. 2: Input: 0≤α0<10 \le\alpha_0 < 1 - initial estimation of relative error, 3: Input: Fα∈{false,true}F_\alpha\in\{\text{false},\text{true}\} - whether to adapt the relative error. 4: Input: δ0≥0\delta_0 \ge0 - initial estimation of absolute error, 5: Input: Fδ∈{false,true}F_\delta\in\{\text{false},\text{true}\} - whether to adapt the absolute error. 6: Input: L0>0L_0 > 0 - initial estimation of smoothness, 7: Input: FL∈{false,true}F_L \in\{\text{false},\text{true}\} - whether to adapt the smoothness. 8: Set J0=0J_0 = 0. 9: for k=0…N−1k = 0 \ldots N - 1 do 10: α^k,δ^k,L^k,θk,xk+1=Step⁡(Jk,xk,α0,Fα,δ0,Fδ,L0,FL)\hat{\alpha}_k,\hat{\delta}_k,\hat{L}_k,\theta_k,x^{k+1} = \operatorname{Step}(J_k,x^k,\alpha_0,F_\alpha,\delta_0,F_\delta,L_0,F_L). 11: while f(xk+1)>f(xk)−θk∥∇f(xk)∥22+14(1+α^k)2L^kδ^k2f(x^{k+1}) > f(x^k) - \theta_k\lVert\nabla f(x^k)\rVert_2^2 + \frac{1}{4(1+\hat{\alpha}_k)^2\hat{L}_k}\hat{\delta}_k^2 do 12: Jk=Jk+1J_k = J_k + 1. 13: α^k,δ^k,L^k,θk,xk+1=Step⁡(Jk,xk,α0,Fα,δ0,Fδ,L0,FL)\hat{\alpha}_k,\hat{\delta}_k,\hat{L}_k,\theta_k,x^{k+1} = \operatorname{Step}(J_k,x^k,\alpha_0,F_\alpha,\delta_0,F_\delta,L_0,F_L). 14: end while 15: Jk+1=max⁡{0,Jk−1}J_{k+1} = \max\{0,J_k - 1\}. 16: end for 17: Output: xNx^N. 19: function Step⁡(t,x,α0,Fα,δ0,Fδ,L0,FL)\operatorname{Step}(t,x,\alpha_0,F_\alpha,\delta_0,F_\delta,L_0,F_L) 20: α^=1−1−α02t\hat{\alpha} = 1 - \frac{1-\alpha_0}{2^t} If (FαF_\alpha is true) else α0\alpha_0. 21: δ^=2tδ0\hat{\delta} = 2^t\delta_0 If (FδF_\delta is true) else δ0\delta_0. 22: L^=2tL0\hat{L} = 2^tL_0 If (FLF_L is true) else L0L_0. 23: h=1−α^4L^(1+α^)2h = \frac{1-\hat{\alpha}}{4\hat{L}(1+\hat{\alpha})^2}. 24: θ=132L^(1+α^)4\theta= \frac{1}{32\hat{L}(1+\hat{\alpha})^4}. 25: y=x−h∇^f(x)y = x - h\widehat{\nabla}f(x). 26: return (α^,δ^,L^,θ,y)(\hat{\alpha},\hat{\delta},\hat{L},\theta,y). 27: end function

References

  1. [1]A. Ajalloeian and S.U. Stich, On the convergence of sgd with biased gradients, arXiv preprint arXiv:2008.00051 (2020).arxiv.org/abs/2008.00051
  2. [2]A. Beck, First-order methods in optimization, SIAM, 2017.DOI
  3. [3]S. Bubeck, Convex optimization: Algorithms and complexity, Foundations and trends in Machine Learning 8 (2015), pp. 231–357.arxiv.org/abs/1405.4980
  4. [4]O. Devolder, F. Glineur, and Y. Nesterov, First-order methods of smooth convex optimization with inexact oracle, Mathematical Programming 146 (2014), pp. 37–75.
  5. [5]O. Devolder, F. Glineur, Y. Nesterov, et al., First-order methods with inexact oracle: the strongly convex case, CORE discussion papers 2013016 (2013), p. 47.
  6. [6]A. Gasnikov, Universal gradient descent, arXiv preprint arXiv:1711.00394 (2017).arxiv.org/abs/1711.00394
  7. [7]A. Nemirovski, Information-based complexity of convex programming, Lecture notes 834 (1995).
  8. [8]Y. Nesterov, et al., Lectures on convex optimization, Vol. 137, Springer, 2018.DOI
  9. [9]B.T. Polyak, Introduction to optimization (1987).
  10. [10]A. Tyurin, Q. Pham, V. Khrulkov, and I. Oseledets, LongTails: Automated research in optimization (2026).arxiv.org/abs/2611.13872
  11. [11]A. Vasin, A. Gasnikov, P. Dvurechensky, and V. Spokoiny, Accelerated gradient methods with absolute and relative noise in the gradient, Optimization Methods and Software 38 (2023), pp. 1180–1229.arxiv.org/abs/2102.02921

Paper details

vlnc:W_tx6bzcx2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6

View statement
Looking for related papers…
Contents