← All problems
Unverified
Anytime Convergence Rate of Gradient Descent
For an -smooth convex function , gradient descent uses
where the stepsize sequence is fixed independently of the stopping time. What is the best anytime convergence rate, uniformly over all such ? In particular, do there exist a schedule and an exponent such that, for every -smooth convex , every minimizer , and every ,
The guarantee must concern itself, not , and must hold at every horizon.
