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 $\mu$. With fixed smoothness $L$, acceleration is retained when $\alpha=\mathcal{O}\left(\left(\mu / L \right)^{1/4}\right)$, larger admissible errors yield intermediate rates. Throughout the range $0 \leqslant \alpha \leqslant 1/3$, the absolute error bound $\delta$ contributes at most $\mathcal{O} \left(\delta^2/\mu \right)$ to the objective residual, without additional amplification by the condition number.