Tightness conjecture for gradient descent with variable mid-range stepsizes

About 2 years old · traced to

Let f∈Fμ,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,…,N−1i=0,\dots,N-1. Variable-mid-range-stepsize tightness conjecture. The convergence-rate bound from the preceding theorem is tight:

max⁡f∈Fμ,L; x012Lmin⁡0≤i≤N{∥∇f(xi)∥2}=f(x0)−f∗1+∑i=0N−1γ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.

References

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.