Gradient Descent: Horizon, Dimension, and Step Signs

Current state

The joint-bounds paper studies the best worst-case objective gap after $N$ steps in dimension $d$, for smooth convex functions and step sizes fixed in advance.

For nonnegative steps, it sharpens Ye–Liu’s lower bound and makes its dimension dependence explicit. Together with Altschuler–Parrilo’s silver schedules, this gives the optimal rate $N^{-s+o(1)}$, where $s={\log }_2(1+\sqrt{2})$, whenever $d/\log N\to \infty$. For arbitrary real steps, it improves Ye–Liu’s lower-bound exponent in dimension $N+1$ from $1.6342$ to $1.5570595$.

A second paper determines the exact asymptotic constant, approximately $0.30419477598$, for the lower bound supplied by scalar quadratics and Huber tests whose iterates stay in one affine region. Complete elliptic integrals characterize the constant.

Negative steps cannot improve the scalar minimax value at any horizon, or the minimax value in any dimension through five steps. The companion papers construct schedules whose worst-case objective gap is strictly larger in two dimensions than in one, at every horizon from three onward. For any real $N$-step schedule, the worst-case value is constant once $d\ge N+1$.

Future plans

The optimal rates in fixed dimension and the full scalar minimax value remain open. Whether negative steps improve the minimax value is unresolved for nonseparable objectives in dimension at least two beyond five steps.