Gradient descent with momentum --- to accelerate or to super-accelerate?

• URL: http://arxiv.org/abs/2001.06472v1
• Date: Fri, 17 Jan 2020 18:50:07 GMT
• Title: Gradient descent with momentum --- to accelerate or to super-accelerate?
• Authors: Goran Nakerst, John Brennan, Masudul Haque
• Abstract summary: We show that the algorithm can be improved by extending this acceleration' Super-acceleration is also easy to incorporate into adaptive algorithms like RMSProp or Adam.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider gradient descent with `momentum', a widely used method for loss function minimization in machine learning. This method is often used with `Nesterov acceleration', meaning that the gradient is evaluated not at the current position in parameter space, but at the estimated position after one step. In this work, we show that the algorithm can be improved by extending this `acceleration' --- by using the gradient at an estimated position several steps ahead rather than just one step ahead. How far one looks ahead in this `super-acceleration' algorithm is determined by a new hyperparameter. Considering a one-parameter quadratic loss function, the optimal value of the super-acceleration can be exactly calculated and analytically estimated. We show explicitly that super-accelerating the momentum algorithm is beneficial, not only for this idealized problem, but also for several synthetic loss landscapes and for the MNIST classification task with neural networks. Super-acceleration is also easy to incorporate into adaptive algorithms like RMSProp or Adam, and is shown to improve these algorithms.

Related papers

• Rethinking PGD Attack: Is Sign Function Necessary? [131.6894310945647]
  We present a theoretical analysis of how such sign-based update algorithm influences step-wise attack performance. We propose a new raw gradient descent (RGD) algorithm that eliminates the use of sign. The effectiveness of the proposed RGD algorithm has been demonstrated extensively in experiments.
  arXiv  Detail & Related papers  (2023-12-03T02:26:58Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  We present a novel, fast (exponential rate), ab initio (hyper-free) gradient based adaption. The main idea of the method is to adapt the $alpha by situational awareness. It can be applied to problems of any dimensions n and scales only linearly.
  arXiv  Detail & Related papers  (2023-09-12T14:36:13Z)
• Improving Gradient Methods via Coordinate Transformations: Applications to Quantum Machine Learning [0.0]
  Machine learning algorithms heavily rely on optimization algorithms based on gradients, such as gradient descent and alike. The overall performance is dependent on the appearance of local minima and barren plateaus, which slow-down calculations and lead to non-optimal solutions. In this paper we introduce a generic strategy to accelerate and improve the overall performance of such methods, allowing to alleviate the effect of barren plateaus and local minima.
  arXiv  Detail & Related papers  (2023-04-13T18:26:05Z)
• Scaling Forward Gradient With Local Losses [117.22685584919756]
  Forward learning is a biologically plausible alternative to backprop for learning deep neural networks. We show that it is possible to substantially reduce the variance of the forward gradient by applying perturbations to activations rather than weights. Our approach matches backprop on MNIST and CIFAR-10 and significantly outperforms previously proposed backprop-free algorithms on ImageNet.
  arXiv  Detail & Related papers  (2022-10-07T03:52:27Z)
• Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models [158.19276683455254]
  Adaptive gradient algorithms borrow the moving average idea of heavy ball acceleration to estimate accurate first second-order moments of gradient for accelerating convergence. Nesterov acceleration converges faster than ball acceleration in theory and also in many empirical cases. In this paper we develop a new Nesterov momentum estimation (NME) method, which avoids the extra computation and memory overhead of computing gradient at the point. We show that Adan surpasses the corresponding SoTAs on both vision transformers (ViTs and CNNs) and sets new SoTAs for many popular networks.
  arXiv  Detail & Related papers  (2022-08-13T16:04:39Z)
• Reparametrizing gradient descent [0.0]
  We propose an optimization algorithm which we call norm-adapted gradient descent. Our algorithm can also be compared to quasi-Newton methods, but we seek roots rather than stationary points.
  arXiv  Detail & Related papers  (2020-10-09T20:22:29Z)
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
  In this work, we adapt the integral quadratic constraints theory to first-order methods for smooth and strongly-varying games and iteration. We provide emphfor the first time a global convergence rate for the negative momentum method(NM) with an complexity $mathcalO(kappa1.5)$, which matches its known lower bound. We show that it is impossible for an algorithm with one step of memory to achieve acceleration if it only queries the gradient once per batch.
  arXiv  Detail & Related papers  (2020-09-23T20:02:00Z)
• Multi-kernel Passive Stochastic Gradient Algorithms and Transfer Learning [21.796874356469644]
  The gradient algorithm does not have control over the location where noisy gradients of the cost function are evaluated. The algorithm performs substantially better in high dimensional problems and incorporates variance reduction.
  arXiv  Detail & Related papers  (2020-08-23T11:55:19Z)
• Variance Reduction with Sparse Gradients [82.41780420431205]
  Variance reduction methods such as SVRG and SpiderBoost use a mixture of large and small batch gradients. We introduce a new sparsity operator: The random-top-k operator. Our algorithm consistently outperforms SpiderBoost on various tasks including image classification, natural language processing, and sparse matrix factorization.
  arXiv  Detail & Related papers  (2020-01-27T08:23:58Z)
• Resolving learning rates adaptively by locating Stochastic Non-Negative Associated Gradient Projection Points using line searches [0.0]
  Learning rates in neural network training are currently determined a priori to training using expensive manual or automated tuning. This study proposes gradient-only line searches to resolve the learning rate for neural network training algorithms.
  arXiv  Detail & Related papers  (2020-01-15T03:08:07Z)
• 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)

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.