Gradient descent with large momentum finds flatter minima.
problem Understanding the effects of momentum in gradient descent.
method Empirical and theoretical analysis of gradient descent with large momentum.
result Large momentum leads to flatter minima than gradient descent.
Error estimates found between SGD with momentum and Langevin diffusion.
problem Quantifying the difference between SGD with momentum and Langevin diffusion.
method Established error estimates using 1-Wasserstein and total variation distances.
result Quantitative error estimates between SGD with momentum and underdamped Langevin diffusion.
This study uses continuous-time analysis to understand how momentum affects the optimisation of diagonal linear networks.
problem The effect of momentum on the optimisation trajectory of gradient descent.
method Leveraging a continuous-time approach to analyze momentum gradient descent with step size γ and momentum parameter β.
result Small values of λ help recover sparse solutions in overparametrised regression settings.
Momentum improves deep learning generalization by stabilizing noise and learning features.
problem Improving generalization in deep learning models.
method Empirical and theoretical analysis of gradient descent with momentum (GD+M) vs. gradient descent (GD) in binary classification tasks.
result GD+M outperforms GD in generalization, especially in datasets with shared features and varying margins.
Fine-grained analysis of gradient descent with momentum provides modified loss equations.
problem Understanding the dynamics of gradient descent with momentum.
method Fine-grained analysis and derivation of modified loss equations.
result Global approximation bounds and continuous modified equations for HB.
Gradient descent-based optimization methods underpin the parameter training of neural networks, and hence comprise a significant component in the impressive test results found in a number of applications. Introducing stochasticity is key to their success in practical problems, and there is some understanding of the rol…
We present a unifying framework for adapting the update direction in gradient-based iterative optimization methods. As natural special cases we re-derive classical momentum and Nesterov's accelerated gradient method, lending a new intuitive interpretation to the latter algorithm. We show that a new algorithm, which we …
MGD with early stopping tends to ridge regularization in least squares regression.
problem Characterizing the implicit regularization of MGD with early stopping.
method Continuous-time view of MGD (momentum gradient flow) and comparison with explicit ridge regularization.
result Under optimal tuning, the risk of MGF is no more than 1.54 times that of ridge.
A new accelerated method with simpler momentum update rules.
problem Optimizing parameters in machine learning models.
method Proposes a novel accelerated stochastic gradient method with simpler momentum update rules.
result The method outperforms Sgdm and Adam in practical problems.
Momentum improves federated learning convergence.
problem Accelerating convergence in federated learning.
method Integrates momentum into federated learning via momentum gradient descent.
result Momentum federated learning accelerates convergence compared to standard federated learning.
This work studies the implicit bias of mini-batch SGD in classification.
problem Understanding the implicit bias of mini-batch SGD in multi-class classification.
method Characterizes how batch size, momentum, and variance reduction affect convergence and max-margin behavior under different norms.
result Momentum enables small-batch convergence to an approximate max-margin solution, while variance reduction recovers the exact full-batch bias.
Super-acceleration of gradient descent with momentum improves loss function minimization.
problem Minimizing loss functions in machine learning.
method Extending Nesterov acceleration by using gradients at multiple steps ahead.
result Super-acceleration of the momentum algorithm is beneficial for various loss landscapes and tasks.
The paper analyzes convergence in SGD with momentum and proposes a diagnostic test.
problem Detecting convergence in stochastic gradient descent with momentum.
method Analyzes the transient and stationary phases of SGD with momentum, constructs a statistical diagnostic test.
result The proposed diagnostic test effectively detects convergence in the stationary phase of SGD with momentum.
The paper improves Kaczmarz algorithm with momentum for linear least squares.
problem Improving convergence of the Kaczmarz algorithm for linear least squares.
method Integrates geometrically smoothed momentum into the randomized Kaczmarz algorithm.
result Proves expected error reduction in singular vector directions.
Momentum SGD fails to track nonstationary optima due to drift amplification.
problem Tracking nonstationary optima in stochastic optimization.
method Theoretical analysis of SGD and momentum variants under strong convexity and smoothness.
result Momentum incurs a drift-amplification penalty that diverges as the momentum parameter approaches 1, leading to systematic lag.
New minibatching strategy reduces stochastic gradient bias in optimisation.
problem Reducing bias in stochastic gradient descent.
method Symmetric Minibatching Strategy combined with momentum.
result Reduced stochastic gradient bias from O ( h 2 ) \mathcal{O}(h^2) O ( h 2 ) to O ( h 4 ) \mathcal{O}(h^4) O ( h 4 ) . SRSGD improves DNN training speed and accuracy.
problem Training deep neural networks is computationally expensive and slow.
method Scheduled Restart SGD (SRSGD) combines NAG momentum with momentum reset.
result SRSGD achieves better error rates with fewer training epochs.
MSGD outperforms SGD in overparametrized settings with faster convergence rates.
problem Optimization of non-convex functions with momentum.
method Momentum Stochastic Gradient Descent (MSGD) with rigorous analysis.
result MSGD converges exponentially faster than SGD in overparametrized settings.
In this paper we study several classes of stochastic optimization algorithms enriched with heavy ball momentum. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic dual subspace ascent. This is the first time momentum variants of several of these metho…
New insights into training machine learning models with momentum.
problem Lack of theoretical understanding on the generalization error of momentum-based methods.
method Analyzed modified momentum-based update rule (SGDEM) for smooth Lipschitz loss functions.
result SGDEM admits an upper-bound on the generalization error for smooth Lipschitz loss functions.
Integrates momentum into RNNs to improve training.
problem Vanishing gradient in RNNs during training.
method Established connection between RNN dynamics and GD, integrated momentum.
result MomentumRNNs alleviate vanishing gradient issue and improve convergence.
SNGM improves large-batch training accuracy.
problem Improving generalization in large-batch training.
method Stochastic Normalized Gradient Descent with Momentum.
result SNGM achieves better test accuracy than MSGD and other large-batch methods.
Proposes momentum methods for Lie groups, improving on classical algorithms.
problem Optimization on nonlinear spaces, especially Lie groups.
method Generalizes Nesterov's Accelerated Gradient method to Lie groups.
result Demonstrates faster convergence for NAG-like methods on Lie groups.
Polyak's momentum accelerates training of neural networks.
problem Understanding and explaining the acceleration effect of Polyak's momentum in neural network training.
method Modular analysis of Polyak's momentum for training wide ReLU networks and deep linear networks.
result Polyak's momentum achieves an accelerated linear rate of ( 1 − Θ ( 1 κ ′ ) ) t (1-Θ(\frac{1}{\sqrt{κ'}}))^t ( 1 − Θ ( κ ′ 1 ) ) t for training wide ReLU networks and deep linear networks. Momentum affects optimization differently at small vs large batch sizes near instability.
problem Understanding how momentum impacts optimization near the edge of stability.
method Demonstrated through batch-size dependent behavior of SGD with momentum.
result Momentum operates in two distinct regimes: amplifying stochastic fluctuations at small batch sizes and stabilizing at large batch sizes.
New loss function connects learning rate and momentum.
problem Finding optimal learning rate and momentum empirically.
method Proposes a new information-theoretical loss function.
result Loss, learning rate, and momentum are closely connected.
SGDM accelerates faster than SGD with large batch sizes and permits broader learning rates.
problem Understanding the role of momentum in SGDM and its convergence rates.
method Analysis of SGDM convergence rates under strongly convex settings, including finite-sample rates and asymptotic normality of the averaged estimator.
result SGDM converges faster than SGD with large batch sizes and permits broader learning rates.
Tuning hyperparameters of learning algorithms is hard because gradients are usually unavailable. We compute exact gradients of cross-validation performance with respect to all hyperparameters by chaining derivatives backwards through the entire training procedure. These gradients allow us to optimize thousands of hyper…
Improved convergence for Polyak steps with momentum in smooth convex optimization.
problem Optimizing smooth strongly convex functions with limited information.
method Polyak steps with momentum, derived for accelerated gradient method.
result Convergence guarantees for accelerated gradient method with Polyak steps and momentum.
The paper analyzes how hyperparameters affect SGD with momentum's convergence rate.
problem The role of hyperparameters in SGD with momentum's convergence rate.
method Theoretical analysis using a hyperparameters-dependent stochastic differential equation (hp-dependent SDE).
result The optimal linear rate of convergence depends on both the learning rate and the momentum coefficient.
Paper analyzes high probability convergence of adaptive SGD with momentum.
problem Theoretical understanding of adaptive SGD with momentum in nonconvex settings is incomplete.
method High probability analysis under weak assumptions.
result First high probability convergence proof for gradients to zero in Delayed AdaGrad with momentum.
ASVGD accelerates SVGD for efficient sampling.
problem Slow SVGD in high-dimensional sampling.
method Accelerated gradient flow in a metric space of probability densities, using Nesterov's method and momentum-based updates.
result ASVGD outperforms SVGD and other methods in sampling efficiency.
New bounds for model generalization under deterministic gradient descent.
problem Establishing generalization bounds for models trained with gradient descent methods.
method PAC-Bayesian bounds for deterministic optimisation algorithms.
result Fully computable bounds that depend on initial distribution and Hessian.
A fast method for training linear classifiers maximizes margins.
problem Training linear classifiers with maximum margins.
method Momentum-based gradient method derived from convex dual with Nesterov acceleration.
result Exponentially faster convergence rate compared to standard methods.
The paper optimizes regret using covariance between costs and decisions.
problem Optimizing expected regret in decision-making problems.
method Developed derivative theory of covariance regret functional, derived Gâteaux derivative, and extended to constrained optimization.
result Gradient of covariance regret is the cost covariance matrix, with implications for portfolio optimization.
FedNAG improves federated learning accuracy and reduces training time.
problem Efficiency of federated learning with gradient descent.
method Nesterov Accelerated Gradient (NAG) applied to federated learning (FL) with additional momentum and model aggregation.
result FedNAG increases learning accuracy by 3-24% and reduces training time by 11-70%.
Stochastic gradient descent (\textsc{Sgd}) methods are the most powerful optimization tools in training machine learning and deep learning models. Moreover, acceleration (a.k.a. momentum) methods and diagonal scaling (a.k.a. adaptive gradient) methods are the two main techniques to improve the slow convergence of \text…
New algorithm Momentum-QNG improves optimization of quantum circuits.
problem Optimizing variational quantum circuits to avoid local minima.
method Applied Langevin dynamics to QNG, introducing momentum term.
result Momentum-QNG outperforms basic QNG and other optimizers.
While momentum-based accelerated variants of stochastic gradient descent (SGD) are widely used when training machine learning models, there is little theoretical understanding on the generalization error of such methods. In this work, we first show that there exists a convex loss function for which the stability gap fo…
Study accelerates optimization methods in non-convex problems, but doesn't improve the algorithm's performance.
problem Understanding the behavior of momentum-based acceleration methods in non-convex, high-dimensional landscapes.
method Used dynamical mean field theory to describe the average dynamics of heavy-ball momentum and Nesterov acceleration in a non-convex model.
result Accelerated dynamics but did not improve the algorithm's performance with respect to gradient descent.
We introduce Kalman Gradient Descent, a stochastic optimization algorithm that uses Kalman filtering to adaptively reduce gradient variance in stochastic gradient descent by filtering the gradient estimates. We present both a theoretical analysis of convergence in a non-convex setting and experimental results which dem…
In this paper, we aim at providing an introduction to the gradient descent based optimization algorithms for learning deep neural network models. Deep learning models involving multiple nonlinear projection layers are very challenging to train. Nowadays, most of the deep learning model training still relies on the back…
Momentum speeds up evolutionary processes in machine learning.
problem Accelerating convergence in evolutionary dynamics.
method Combining momentum from machine learning with evolutionary dynamics using information divergences as Lyapunov functions.
result Momentum accelerates convergence of evolutionary dynamics, including the replicator equation and Euclidean gradient descent.
Rod flow models Adam's behavior at the edge of stability.
problem Modeling adaptive gradient methods like Adam at the edge of stability.
method Extended rod flow to Adam, considering parameters, first moment, and second moment as variables.
result Rod flow accurately tracks Adam's behavior through the edge-of-stability regime.
Random learning rate improves neural network training without extra cost.
problem Optimizing neural networks with stochastic gradient descent.
method Uniformly-distributed random learning rate in SGD.
result Random learning rate yields better regularization without extra computational cost.
Accelerates MMLE using SVGD with Nesterov acceleration.
problem Maximum Marginal Likelihood Estimation optimization.
method Stein variational gradient descent with Nesterov acceleration.
result Consistently accelerates convergence across various tasks.
Although distributed computing can significantly reduce the training time of deep neural networks, scaling the training process while maintaining high efficiency and final accuracy is challenging. Distributed asynchronous training enjoys near-linear speedup, but asynchrony causes gradient staleness - the main difficult…
Nesterov's momentum trick is famously known for accelerating gradient descent, and has been proven useful in building fast iterative algorithms. However, in the stochastic setting, counterexamples exist and prevent Nesterov's momentum from providing similar acceleration, even if the underlying problem is convex and fin…