Gradient Descent Exponent ($C_{35}$)

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$: $x_{k+1} := x_k - s\cdot \nabla f(x_k)$. In general, $s$ can be chosen to vary with the step $k$. The function gap $f(x_k) - \inf f$, 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 $C_{35}$ is the largest exponent $c$ such that there exists a step schedule $s : \mathbb{N} \to \mathbb{R}$ so that vanilla gradient descent has a worst-case convergence of $O(k^{-c})$.