A Two-Dimensional Extremizer for Relatively Inexact Gradient Descent
Abstract
We give an explicit extremal function for one step of gradient descent when the gradient error is bounded relative to the true gradient. The function is the sum of a quadratic in one coordinate and a Huber function in the other. It attains, for every admissible relative error level and every stepsize in the intermediate regime, the proposed worst-case constants for both the final squared gradient divided by the initial objective gap and the final squared gradient divided by the objective decrease. This proves Conjecture 2.6 of Vernimmen and Glineur, first stated in June 2025. A change of variable reduces the parameter description to a scalar cubic with a rigorously specified root. We prove all parameter inequalities, derive a nonnegative-square certificate for the upper bound, and verify the matching construction directly. We also characterize the exact one-dimensional worst-case value and prove that two dimensions are necessary in the open intermediate regime.
Related
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Optimal Design of Distributed Inexact Gradient Tracking: Exact Worst-case Convergence Rate and Explicit Parameters
- Tight Stationarity Transfer and Repeatability for Inexact Proximal-Gradient Methods
- Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
- PL conditions do not guarantee convergence of gradient descent-ascent dynamics
BibTeX
@misc{zhao2026twodimensional,
title = {{A Two-Dimensional Extremizer for Relatively Inexact Gradient Descent}},
author = {Jinze Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00156},
eprint = {2610.00156},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00156},
}
RIS
TY - UNPB
TI - A Two-Dimensional Extremizer for Relatively Inexact Gradient Descent
AU - Jinze Zhao
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00156
UR - https://arxiv.org/abs/2610.00156
AB - We give an explicit extremal function for one step of gradient descent when the gradient error is bounded relative to the true gradient. The function is the sum of a quadratic in one coordinate and a Huber function in the other. It attains, for every admissible relative error level and every stepsize in the intermediate regime, the proposed worst-case constants for both the final squared gradient divided by the initial objective gap and the final squared gradient divided by the objective decrease. This proves Conjecture 2.6 of Vernimmen and Glineur, first stated in June 2025. A change of variable reduces the parameter description to a scalar cubic with a rigorously specified root. We prove all parameter inequalities, derive a nonnegative-square certificate for the upper bound, and verify the matching construction directly. We also characterize the exact one-dimensional worst-case value and prove that two dimensions are necessary in the open intermediate regime.
ER -