Strongly convex gradient-norm worst-case conjecture

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

xi+1=xihLf(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)2LRmax(κ(κ1)+(1κh)N,1hN).\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.

Sources & referencesView supporting material

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.