Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods
This work addresses the practical challenge of tuning SGD in machine learning by theoretically justifying the superiority of adaptive methods in handling large gradients without prior knowledge.
The paper proves that untuned SGD achieves an order-optimal convergence rate of O(T^{-1/4}) for smooth objectives but suffers from an unavoidable exponential dependence on the smoothness constant, and shows that adaptive methods like NSGD, AMSGrad, and AdaGrad eliminate this dependency without requiring problem parameters.
The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize $η_t = η/\sqrt{t}$ relies on well-tuned $η$ depending on problem parameters such as Lipschitz smoothness constant, which is often unknown in practice. In this work, we prove that SGD with arbitrary $η> 0$, referred to as untuned SGD, still attains an order-optimal convergence rate $\widetilde{O}(T^{-1/4})$ in terms of gradient norm for minimizing smooth objectives. Unfortunately, it comes at the expense of a catastrophic exponential dependence on the smoothness constant, which we show is unavoidable for this scheme even in the noiseless setting. We then examine three families of adaptive methods $\unicode{x2013}$ Normalized SGD (NSGD), AMSGrad, and AdaGrad $\unicode{x2013}$ unveiling their power in preventing such exponential dependency in the absence of information about the smoothness parameter and boundedness of stochastic gradients. Our results provide theoretical justification for the advantage of adaptive methods over untuned SGD in alleviating the issue with large gradients.