Asymptotic and Non-Asymptotic Convergence of AdaGrad for Non-Convex Optimization via Novel Stopping Time-based Analysis

• URL: http://arxiv.org/abs/2409.05023v2
• Date: Tue, 19 Nov 2024 13:57:39 GMT
• Title: Asymptotic and Non-Asymptotic Convergence of AdaGrad for Non-Convex Optimization via Novel Stopping Time-based Analysis
• Authors: Ruinan Jin, Xiaoyu Wang, Baoxiang Wang,
• Abstract summary: We introduce an innovative comprehensive analysis of Ada, filling the existing gaps in the literature. We derive almost sure and mean-prodd in expectation for AdaGrad. In addition, we demonstrate the average non-a-bpt-d gradient measured by the rate-prod in expectation, which is potentially independent of the existing results.
• Score: 17.34603953600226
• License:
• Abstract: Adaptive optimizers have emerged as powerful tools in deep learning, dynamically adjusting the learning rate based on iterative gradients. These adaptive methods have significantly succeeded in various deep learning tasks, outperforming stochastic gradient descent (SGD). 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, filling the existing gaps in the literature. We introduce an innovative stopping time technique from probabilistic theory, which allows us to establish the stability of AdaGrad under mild conditions for the first time. 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 independent of interest for future research on other adaptive stochastic algorithms.

Related papers

• 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)
• Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory [30.061707627742766]
  We aim for instance-optimality, a strong notion of adaptivity which asserts that, on any particular problem instance, the algorithm under consideration outperforms all consistent algorithms. In this paper, we take the first step toward developing a non-asymptotic theory of instance-optimal decision making with general function approximation.
  arXiv  Detail & Related papers  (2023-04-24T21:51:58Z)
• 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)
• 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)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  We address the problem of policy evaluation in discounted decision processes, and provide Markov-dependent guarantees on the $ell_infty$error under a generative model. We establish both and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms.
  arXiv  Detail & Related papers  (2020-03-16T17:15:28Z)
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization [73.38702974136102]
  Various types of parameter restart schemes have been proposed for accelerated algorithms to facilitate their practical convergence in rates. In this paper, we propose an algorithm for solving nonsmooth problems.
  arXiv  Detail & Related papers  (2020-02-26T16:06:27Z)
• 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.