← All setups

Inexact Gradient Strongly Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Inexact Gradient Strongly Convex Minimization

We consider minimizing a differentiable, μ-strongly convex function f:E→R on a real Hilbert space E, with quadratic upper curvature bound L≥μ>0. A given point x0∈E lies within distance R≥0 of a global minimizer x⋆. At x∈E, the oracle returns a vector g∈E with relative gradient error controlled by α∈[0,1) and additive error controlled by δ≥0. For a tolerance ε>0 compatible with this error, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the joint law of the algorithm’s and oracle’s randomness.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives only E, L, x0, μ, and α; the parameters δ, R, and ε may enter the oracle-call budget but are not algorithm inputs. In addition to the ranges above, the parameters satisfy 136δ2≤μ(1−α)2ε.

Our assumptions:

Assumption 1 (Smoothness and strong convexity). The function f is Fréchet differentiable everywhere on E. For every x,y∈E, f(y)≤f(x)+⟨∇f(x),y−x⟩+L2∥y−x∥2,f(y)≥f(x)+⟨∇f(x),y−x⟩+μ2∥y−x∥2.

Assumption 2 (Inexact gradient oracle). Queries may be made at any point x∈E. Every oracle reply g∈E satisfies ∥g−∇f(x)∥≤α∥∇f(x)∥+δ. This bound holds for every query history and every realization of the oracle randomness. Replies may depend on the history, and the oracle randomness may be dependent across calls. The algorithm’s randomness is independent of the oracle randomness.

Assumption 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

On a real Hilbert space, f is differentiable with global quadratic upper and lower models of curvature L and μ, where 0<μ≤L. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R. Every oracle reply obeys ∥g−∇f(x)∥≤α∥∇f(x)∥+δ, with 0≤α<1 and δ,R≥0; errors may depend on the call and seed. The target is f(xN)−f(x⋆)≤ε almost surely, with ε>0 and 136δ2≤μ(1−α)2ε. The constructed method uses L,μ,α,x0; the setup imposes no algorithm restriction.

Inexact-gradient strongly convex optimization: InexactGradientStronglyConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedInexactStronglyConvex (Ours) (⋆⋆⋆) (review) O(1+[κ1−α+α2κ1−α]ℓ)
(2) RE-AGM (Vasin and Gasnikov 2026, Thm. 6.1) O(1+(κ+ακ)ℓ); α≤1/3, ε≥Cmin{κ,α−1}δ2/μ. Euclidean space. (1): for κ−1/2≤α≤1/3, gain min{ακ,α−1}. At α=κ−1/4, O(1+κ1/2ℓ) instead of O(1+κ3/4ℓ). Certified floor drops to O(δ2/μ); extends to α<1.
(3) RE-AGM (Vasin et al. 2025, Thm. 4) O(1+κℓ); δ=0, α<c0κ−1/2. Euclidean space. (1): matches this rate; retains it up to α=O(κ−1/4) bounded away from 1, instead of O(κ−1/2). Scope: permits absolute error subject to its floor.
(4) RE-AGM (Vasin et al. 2025, Thm. 5) O(1+ακℓ); δ=0, κ−1/2/3≤α≤1/3. Euclidean space. (1): gain min{ακ,α−1} for κ−1/2≤α≤1/3; reaches κ1/4 at α=κ−1/4. Scope: adds absolute error subject to its floor.
(5) GD (Vasin and Gasnikov 2026, Thm. 5.2) O(1+κ(1+α)(1−α)3ℓ); ε≥C1+α(1−α)3δ2μ. Euclidean smooth PL functions; displayed initialization on the common strongly convex setup. (1): for large κ, α≤κ−1/4 and common admissible accuracy, O(1+κℓ) instead of O(1+κℓ). (1) requires strong convexity instead of the PL inequality.
(6) Fast gradient method (Gaucher et al. 2026, Thm. 3.3) O(1+κℓ); α=0, ε≥Cκδ2/μ. Euclidean space; additive-error specialization. (1): at α=0, certified floor δ2/μ instead of κδ2/μ in order; certifies acceleration below (6)’s threshold when δ2/μ≲ε≪κδ2/μ. Scope: adds relative error.

Abbr: κ=L/μ, ℓ=log⁡(1+LR2/ε); costs count inexact-gradient calls. C denotes a sufficiently large universal constant in sufficient accuracy conditions; α−1=+∞ at α=0. c0=(2−1)/(182). PL: ∥∇f(x)∥2≥2μ(f(x)−f(x⋆)).

Gaucher, Renaud, Aymeric Dieuleveut, and Hadrien Hendrikx. 2026. From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization Under Similarity. arXiv:2602.03329v1. https://doi.org/10.48550/arXiv.2602.03329.
Vasin, Artem, and Alexander Gasnikov. 2026. Lower and Upper Bounds of the Convergence Rate of Gradient Methods with Composite Noise in Gradient. arXiv:2603.12376v1. https://doi.org/10.48550/arXiv.2603.12376.
Vasin, Artem, Valery Krivchenko, Dmitry Kovalev, et al. 2025. On Solving Minimization and Min-Max Problems by First-Order Methods with Relative Error in Gradients. arXiv:2503.06628v3. https://doi.org/10.48550/arXiv.2503.06628.

Lean setup