pipette
ESEspañol

Adaptive First-Order Methods with Composite Gradient Error

Artem Vasin, Alexander Tyurin, Alexander Gasnikov

Preprint

In the authors' words

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 , acceleration is retained when , larger admissible errors yield intermediate rates. Throughout the range , the absolute error bound contributes at most to the objective residual, without additional amplification by the condition number.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.