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.