← All problems
Unverified

Anytime Convergence Rate of Gradient Descent

For an LL-smooth convex function f ⁣:Rd→Rf\colon\mathbb R^d\to\mathbb R, gradient descent uses

xt+1=xt−ηt∇f(xt), x_{t+1}=x_t-\eta_t\nabla f(x_t),

where the stepsize sequence (ηt)t≥0(\eta_t)_{t\geq0} is fixed independently of the stopping time. What is the best anytime convergence rate, uniformly over all such ff? In particular, do there exist a schedule and an exponent α>1\alpha>1 such that, for every LL-smooth convex ff, every minimizer x⋆x^\star, and every T∈NT\in\mathbb N,

f(xT)−f(x⋆)≤L∥x0−x⋆∥2Tα? f(x_T)-f(x^\star)\leq \frac{L\|x_0-x^\star\|^2}{T^\alpha}?

The guarantee must concern xTx_T itself, not min⁡t≤Tf(xt)\min_{t\leq T}f(x_t), and must hold at every horizon.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu