Strongly convex gradient-norm worst-case conjecture

At least 10 years old · documented by

Let f∈Fμ,L(Rd)f\in\mathcal{F}_{\mu,L}(\mathbb{R}^d) be a smooth strongly convex function with minimizer x∗x_*, let R=∥x0−x∗∥2R=\lVert x_0-x_*\rVert_2, and set κ=μ/L\kappa=\mu/L. For 0≤h≤20\leq h\leq 2, the gradient method with normalized step size h/Lh/L generates iterates

xi+1=xi−hL∇f(xi).x_{i+1}=x_i-\frac{h}{L}\nabla f(x_i).

Strongly convex gradient-norm conjecture. Every sequence of iterates generated in this way satisfies

∥∇f(xN)∥2≤LRmax⁡(κ(κ−1)+(1−κh)−N,∣1−h∣N).\lVert\nabla f(x_N)\rVert_2\leq LR\max\left(\frac{\kappa}{(\kappa-1)+(1-\kappa h)^{-N}},\lvert1-h\rvert^N\right).

The conjecture predicts the exact worst-case gradient norm through one-dimensional piecewise quadratic functions, analogously to the objective-value results. It is based on numerical experiments in both the smooth convex and smooth strongly convex settings, and no proof or resolution is given in the source.

References

Primary source

Adrien B. Taylor, Julien M. Hendrickx and François Glineur, “Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods”, arXiv:1502.05666 (2016).

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.