Let f be a convex function with 1-Lipschitz gradient. We assume black-box access to the function and its gradient. Gradient descent will converge to a global minimum with an appropriate choice of step size s: xk+1:=xk−s⋅∇f(xk). In general, s can be chosen to vary with the step k. The function gap f(xk)−inff, will then converge like O(k−c) for some exponent c where k is the iteration counter. While fixed step sizes achieve c=1, time-varying patterns of increasing and decreasing step sizes can lead to improved rates of convergence, increasing the exponent.
The constant C35 is the largest exponent c such that there exists a step schedule s:N→R so that vanilla gradient descent has a worst-case convergence of O(k−c).