Stability and convergence analysis of AdaGrad for non-convex optimization via novel stopping time-based techniques

• URL: http://arxiv.org/abs/2409.05023v3
• Date: Sun, 29 Dec 2024 02:53:55 GMT
• Title: Stability and convergence analysis of AdaGrad for non-convex optimization via novel stopping time-based techniques
• Authors: Ruinan Jin, Xiaoyu Wang, Baoxiang Wang,
• Abstract summary: Adaptive gradients (AdaGrad) have emerged as powerful tools in deep learning. We provide a comprehensive analysis of AdaGrad and bridge the existing gaps in the literature.
• Score: 17.34603953600226
• License:
• Abstract: Adaptive gradient optimizers (AdaGrad), which dynamically adjust the learning rate based on iterative gradients, have emerged as powerful tools in deep learning. These adaptive methods have significantly succeeded in various deep learning tasks, outperforming stochastic gradient descent. However, despite AdaGrad's status as a cornerstone of adaptive optimization, its theoretical analysis has not adequately addressed key aspects such as asymptotic convergence and non-asymptotic convergence rates in non-convex optimization scenarios. This study aims to provide a comprehensive analysis of AdaGrad and bridge the existing gaps in the literature. We introduce a new stopping time technique from probability theory, which allows us to establish the stability of AdaGrad under mild conditions. We further derive the asymptotically almost sure and mean-square convergence for AdaGrad. In addition, we demonstrate the near-optimal non-asymptotic convergence rate measured by the average-squared gradients in expectation, which is stronger than the existing high-probability results. The techniques developed in this work are potentially of independent interest for future research on other adaptive stochastic algorithms.

Related papers

• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  gradient-variation online learning aims to achieve regret guarantees that scale with variations in gradients of online functions. Recent efforts in neural network optimization suggest a generalized smoothness condition, allowing smoothness to correlate with gradient norms. We provide the applications for fast-rate convergence in games and extended adversarial optimization.
  arXiv  Detail & Related papers  (2024-08-17T02:22:08Z)
• High Probability Analysis for Non-Convex Stochastic Optimization with Clipping [13.025261730510847]
  gradient clipping is a technique for dealing with the heavy-tailed neural networks. Most theoretical guarantees only provide an in-expectation analysis and only on the performance. Our analysis provides a relatively complete picture for the theoretical guarantee of optimization algorithms with gradient clipping.
  arXiv  Detail & Related papers  (2023-07-25T17:36:56Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  An analysis of convex and non- optimization methods often requires the Lipsitzness gradient, which limits the analysis by this trajectorys. Recent work generalizes the gradient setting via the non-uniform smoothness condition.
  arXiv  Detail & Related papers  (2023-06-02T04:21:59Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems [34.68590236021379]
  This paper introduces systematic algorithmic stability measures and the gap between the quantitative gradients and the population. We show how we apply these algorithms to achieve an implicit regular iteration step sizes and the adaptive gradient descent.
  arXiv  Detail & Related papers  (2022-06-14T18:14:30Z)
• A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization [0.0]
  It is thought that adaptive optimization algorithms represent the key pillar behind the of the Learning field. In this paper we introduce adaptive momentum techniques for different non-smooth objective problems.
  arXiv  Detail & Related papers  (2021-10-16T09:47:57Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Convergence Properties of Stochastic Hypergradients [38.64355126221992]
  We study approximation schemes for the hypergradient, which are important when the lower-level problem is empirical risk on a large dataset. We provide numerical experiments to support our theoretical analysis and to show the advantage of using hypergradients in practice.
  arXiv  Detail & Related papers  (2020-11-13T20:50:36Z)
• A High Probability Analysis of Adaptive SGD with Momentum [22.9530287983179]
  Gradient Descent (DSG) and its variants are the most used algorithms in machine learning applications. We show for the first time the probability of the gradients to zero in smooth non setting for DelayedGrad with momentum.
  arXiv  Detail & Related papers  (2020-07-28T15:06:22Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
  We prove adaptive gradient methods in expectation of gradient convergence methods. Our analyses shed light on better adaptive gradient methods in optimizing non understanding gradient bounds.
  arXiv  Detail & Related papers  (2018-08-16T20:25:28Z)

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.