Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper proves that gradient descent (GD) and stochastic gradient descent (SGD) cannot achieve the optimal $1/\sqrt{T}$ last-iterate convergence rate for minimizing convex Lipschitz functions with standard, anytime stepsize schedules. Specifically, it demonstrates that any such stepsize sequence for GD will incur an unavoidable polylogarithmic factor in $T$ compared to the optimal rate. This resolves a conjecture by Jain et al. [2019] and suggests that slightly suboptimal stopping times are inherent in these algorithms.
Even in the noiseless setting of gradient descent, achieving optimal last-iterate convergence without knowing the time horizon is provably impossible, requiring an excess polylogarithmic factor.
We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. By now, it is known that standard stepsize choices lead to a last iterate convergence rate of $\log T/\sqrt{T}$ after $T$ steps. A breakthrough result of Jain et al. [2019] recovered the optimal $1/\sqrt{T}$ rate by constructing a non-standard stepsize sequence. However, this sequence requires choosing $T$ in advance, as opposed to common stepsize schedules which apply for any time horizon. Moreover, Jain et al. conjectured that without prior knowledge of $T$, no stepsize sequence can ensure the optimal error for SGD's last iterate, a claim which so far remained unproven. We prove this conjecture, and in fact show that even in the noiseless case of GD, it is impossible to avoid an excess poly-log factor in $T$ when considering an anytime last iterate guarantee. Our proof further suggests that such (slightly) suboptimal stopping times are unavoidably common.
Weizmann