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 L, acceleration is retained when α=𝒪((μ/ L )1/4), larger admissible errors yield intermediate rates. Throughout the range 0 leqslant αleqslant 1/3, the absolute error bound δ contributes at most 𝒪 (δ2/μ) to the objective residual, without additional amplification by the condition number.
Related
- Efficient Parameter-Free First-Order Methods for Nonsmooth Composite Minimax Optimization
- Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
- Composite and Stochastic Smoothed Decentralized Bregman Proximal-Gradient Methods
- The Convergence Rate of Accelerated Proximal Gradient Methods with General Inertia Term for Convex Composite Multiobjective Optimization
- Restart and Adaptive Acceleration in Stochastic Gradient Methods
BibTeX
@misc{vasin2026adaptive,
title = {{Adaptive First-Order Methods with Composite Gradient Error}},
author = {Artem Vasin and Alexander Tyurin and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24863},
eprint = {2610.24863},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24863},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adaptive First-Order Methods with Composite Gradient Error
AU - Artem Vasin
AU - Alexander Tyurin
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24863
UR - https://arxiv.org/abs/2610.24863
AB - 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 L, acceleration is retained when α=𝒪((μ/ L )^1/4), larger admissible errors yield intermediate rates. Throughout the range 0 leqslant αleqslant 1/3, the absolute error bound δ contributes at most 𝒪 (δ^2/μ) to the objective residual, without additional amplification by the condition number.
ER -