Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods

• URL: http://arxiv.org/abs/2305.12475v1
• Date: Sun, 21 May 2023 14:40:43 GMT
• Title: Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods
• Authors: Junchi Yang, Xiang Li, Ilyas Fatkhullin and Niao He
• Abstract summary: We show that adaptive methods over untuned SGD alleviating the issue with smoothness and information advantage. Our results provide theoretical justification for adaptive methods over untuned SGD in the absence of such exponential dependency.
• Score: 22.052459124774504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize $\eta_t = \eta/\sqrt{t}$ relies on well-tuned $\eta$ depending on problem parameters such as Lipschitz smoothness constant, which is often unknown in practice. In this work, we prove that SGD with arbitrary $\eta > 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.

Related papers

• Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
  We show that AdaGrad outperforms SGD by a factor of $d$ under certain conditions. Motivated by this, we introduce assumptions on the smoothness structure of the objective and the gradient variance.
  arXiv  Detail & Related papers  (2024-06-07T02:55:57Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  We propose an adaptive variance method, called AdaSpider, for $L$-smooth, non-reduction functions with a finitesum structure. In doing so, we are able to compute an $epsilon-stationary point with $tildeOleft + st/epsilon calls.
  arXiv  Detail & Related papers  (2022-11-03T14:41:46Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  We propose a new, simplified high probability analysis of AdaGrad for smooth, non- probability problems. We present our analysis in a modular way and obtain a complementary $mathcal O (1 / TT)$ convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness.
  arXiv  Detail & Related papers  (2022-04-06T13:50:33Z)
• Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise [11.768495184175052]
  We introduce a general framework for nonlinear gradient descent scenarios when gradient noise exhibits heavy tails. We show that for a nonlinearity with bounded outputs and for the gradient noise that may not have finite moments of order greater than one, the nonlinear SGD converges to zero at rate$O(/tzeta)$, $zeta in (0,1)$. Experiments show that, while our framework is more general than existing studies of SGD under heavy-tail noise, several easy-to-implement nonlinearities from our framework are competitive with state of the art alternatives on real data sets
  arXiv  Detail & Related papers  (2022-04-06T06:05:52Z)
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
  Such problems arise frequently in machine learning in the context of robust empirical risk minimization. We consider the accelerated primal dual (SAPD) algorithm as a robust method against gradient noise. We show that our method improves upon SAPD both in practice and in theory.
  arXiv  Detail & Related papers  (2022-02-19T22:12:30Z)
• The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance [46.15915820243487]
  We show that AdaGrad-Norm exhibits an order optimal convergence of $mathcalOleft. We show that AdaGrad-Norm exhibits an order optimal convergence of $mathcalOleft.
  arXiv  Detail & Related papers  (2022-02-11T17:37:54Z)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  We design step-size schemes that make gradient descent (SGD) adaptive to (i) the noise. We prove that $T$ iterations of SGD with Nesterov iterations can be near optimal. Compared to other step-size schemes, we demonstrate the effectiveness of a novel novel exponential step-size scheme.
  arXiv  Detail & Related papers  (2021-10-21T19:22:14Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  We provide sharp upper and lower bounds for several forms of gradient descent (SGD) on arbitrary Lipschitz nonsmooth convex losses. Our bounds allow us to derive a new algorithm for differentially private nonsmooth convex optimization with optimal excess population risk.
  arXiv  Detail & Related papers  (2020-06-12T02:45:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.