Equal-rate convergence conjecture for the fast gradient method sequences

Let x0,x1,x_0,x_1,\dots and y1,y2,y_1,y_2,\dots be the main and auxiliary sequences, respectively, defined by the fast gradient method (FGM), and let ff be the objective function in the considered convex minimization problem. Equal-rate convergence conjecture for FGM. The sequences of objective values {f(xi)}\{f(x_i)\} and {f(yi)}\{f(y_i)\} converge to the optimal value of the problem with the same rate of convergence.

The conjecture is motivated by numerical bounds indicating that the main and auxiliary sequences perform very similarly, with the auxiliary sequence appearing slightly better than the classical bound. The authors state that the complexity of the auxiliary sequence was unknown, so the claim remains open in the supplied text.

Sources & referencesView supporting material

Primary source

Yoel Drori and Marc Teboulle, “Performance of first-order methods for smooth convex minimization: a novel approach”, arXiv:1206.3209 (2012).

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.