Tightness conjecture for gradient descent with variable mid-range stepsizes

Let fFμ,Lf\in\mathcal{F}_{\mu,L} with μ(,0)\mu\in(-\infty,0), and consider NN gradient-descent iterations from x0x_0 with stepsizes satisfying γiL[1,\gbari[1]]\gamma_iL\in[1,\gbari[1]] for i=0,,N1i=0,\dots,N-1. Variable-mid-range-stepsize tightness conjecture. The convergence-rate bound from the preceding theorem is tight:

maxfFμ,L;x012Lmin0iN{f(xi)2}=f(x0)f1+i=0N1γiL(2γiL)(2γiμ)2γiLγiμ.\max_{f\in\mathcal{F}_{\mu,L};\,x_0}\frac{1}{2L}\min_{0\leq i\leq N}\{\|\nabla f(x_i)\|^2\} = \frac{f(x_0)-f_*}{1+\sum_{i=0}^{N-1}\gamma_iL\frac{(2-\gamma_iL)(2-\gamma_i\mu)}{2-\gamma_iL-\gamma_i\mu}}.

This claim would establish exact worst-case convergence rates in the nonconstant mid-range stepsize regime. The paper says it is supported by numerical verification of the interpolation conditions, but gives no proof, so it remains open.

Sources & referencesView supporting material

Primary source

Teodor Rotaru, François Glineur and Panagiotis Patrinos, “Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions”, arXiv:2406.17506 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.