Stochastic heavy ball method achieves linear convergence for general loss minimization.
problem Minimizing generalization error in machine learning models.
method SGD steps with heavy ball momentum, focusing on expected loss, not finite-sum minimization.
result Established the first linear convergence result for the stochastic heavy ball method.
Heavy Ball method speeds up finding global optima in non-convex problems.
problem Finding global optima in non-convex optimization problems.
method Heavy Ball momentum in non-convex optimization.
result Heavy Ball helps iterates enter a benign region faster, containing a global optimal point.
Heavy-ball algorithms can always avoid saddle points with random initialization.
problem Optimizing nonconvex functions with saddle points.
method Developed a new mapping to interpret heavy-ball algorithms as iterations, proving they can escape saddle points.
result Heavy-ball algorithms can escape saddle points with random initialization.
Paper improves Heavy-ball method convergence in convex settings.
problem Convergence analysis of Heavy-ball method in convex optimization.
method Improved convergence complexity results for Heavy-ball method with constant step size.
result First non-ergodic O(1/k) rate result for coercive objective functions.
This paper deals with a natural stochastic optimization procedure derived from the so-called Heavy-ball method differential equation, which was introduced by Polyak in the 1960s with his seminal contribution [Pol64]. The Heavy-ball method is a second-order dynamics that was investigated to minimize convex functions f .…
New method shows stochastic momentum can converge quickly on optimization problems.
problem Improving convergence of stochastic optimization methods.
method Stochastic heavy ball momentum with minibatching.
result Stochastic heavy ball momentum retains fast linear rate on quadratic problems.
New algorithm preserves symplectic structure for faster optimization.
problem Optimization methods in machine learning.
method Structure-preserving discretizations of dissipative Hamiltonian systems.
result Proposes a new algorithm that generalizes Nesterov and heavy ball methods.
New ODEs reveal key differences in accelerated gradient methods.
problem Understanding the acceleration phenomenon in optimization algorithms.
method Developed high-resolution ODEs to distinguish between NAG-SC and Polyak's heavy-ball method.
result Identified a gradient correction term in NAG-SC not present in Polyak's method.
Paper analyzes SHB method for neural networks, proving stability, connectivity, and global convergence.
problem Theoretical understanding of SHB method for neural networks.
method Mean-field analysis of SHB dynamics related to a partial differential equation.
result SHB method converges to global optimum and exhibits stability and connectivity.
This paper analyzes two Lie group momentum optimization algorithms and their convergence rates.
problem Optimizing functions on Lie groups using momentum-based dynamics.
method Investigates Lie Heavy-Ball and Lie NAG-SC algorithms, quantifying their convergence rates under smoothness and convexity assumptions.
result Lie NAG-SC accelerates optimization over the momentumless case, while Lie Heavy-Ball does not.
A new Bayesian filtering method speeds up stochastic Newton optimization.
problem Minimizing log-convex functions using stochastic methods.
method Contextualizes the problem as Bayesian inference, applying Bayesian filtering to update estimates.
result Establishes conditions for diminishing effect of older observations, akin to momentum.
Develops a computationally tractable differentially private mean estimator called the balloon mean.
problem Robust mean estimation in the presence of outliers and heavy-tailed distributions.
method Iterative clipping procedure over Mahalanobis balls.
result Balloon mean is robust to outliers and outperforms existing estimators in contaminated settings.
The paper analyzes convergence rates for SGD and SHB methods.
problem Analyzing convergence rates for stochastic gradient descent and heavy ball methods.
method Stochastic gradient descent and stochastic heavy ball method for general stochastic approximation problems.
result The last iterate of SHB converges almost surely to a minimizer and has faster convergence rates than SGD.
Two new differentially private optimization algorithms derived from accelerated methods.
problem Improving privacy in optimization algorithms while maintaining convergence rates.
method Polyak's heavy ball method and Nesterov's accelerated gradient method with differential privacy.
result The proposed algorithms outperform existing differentially private optimization 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.
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 obtain sharp bounds on the performance of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails. Rather than resorting to a concentration-based argument, the method used her…
Paper proves SHB convergence with biased gradients and approximate step sizes.
problem Establishing convergence of SHB with biased gradients and approximate step sizes.
method Generalizes SHB convergence conditions for biased gradients, approximate step sizes, and block updating.
result Proves convergence of SHB with new conditions for biased gradients and approximate step sizes.
Improved DANE algorithm for faster convergence in distributed machine learning.
problem Challenges in convergence of DANE algorithm for general convex functions.
method Introducing variants of DANE with backtracking line search and heavy-ball method.
result Proved global and local convergence rates for quadratic and non-quadratic strongly convex functions.
Recently, {\it stochastic momentum} methods have been widely adopted in training deep neural networks. However, their convergence analysis is still underexplored at the moment, in particular for non-convex optimization. This paper fills the gap between practice and theory by developing a basic convergence analysis of t…
A novel decentralized deep learning algorithm using gradient-based optimization.
problem Decentralized deep learning in networked systems without a central server.
method Heavy-ball acceleration method and consensus protocol for model and gradient-momentum sharing.
result The proposed algorithm outperforms competing methods in various communication topologies.
Optimizes web page freshness with limited crawling frequencies.
problem Maximize local cache freshness given crawling frequency constraints.
method Three novel online estimation schemes for page change rates.
result Convergent algorithms for estimating page change rates.
Improved SHB method for faster convergence on strongly-convex quadratics.
problem Understanding and improving the theoretical and practical advantages of SHB.
method Noise-adaptive multi-stage algorithm for SHB with accelerated convergence.
result SHB can achieve accelerated convergence with larger mini-batch sizes.
A method for estimating the median of gradients in stochastic optimization.
problem Robust gradient estimation in stochastic optimization for various applications.
method Stochastic Proximal Point Method for median gradient estimation.
result The proposed method can converge even under heavy-tailed, state-dependent noise.
The paper analyzes momentum variants of various stochastic optimization methods.
problem Improving the convergence rates of stochastic optimization methods.
method Stochastic gradient descent, Newton, proximal point, and subspace ascent methods with momentum.
result Global linear convergence rates for various measures of success.
Study shows accelerated convergence of stochastic momentum methods in Wasserstein distances.
problem Performance sensitivity of momentum methods to noise in gradients.
method Stochastic momentum methods under a first-order stochastic oracle model.
result Linear convergence rates for AG and HB methods in Wasserstein metrics, robust to noise.
Optimizes privacy-preserving optimization for heavy-tailed data.
problem Privacy-preserving optimization with heavy-tailed gradients.
method Pure ε-differential privacy framework for Lipschitz extensions.
result Minimax optimal excess-risk rate for pure ε-DP heavy-tailed SCO.
Optimization algorithms help overparameterized neural networks achieve high performance.
problem Understanding the convergence of optimization algorithms on overparameterized neural networks.
method Analyzing a broad class of optimization algorithms using dynamical systems and finite over-parameterized neural networks with ReLU activation.
result The Heavy Ball method converges to global minimum at a linear rate, while NAG converges sublinearly.
In the presence of model risk, it is well-established to replace classical expected values by worst-case expectations over all models within a fixed radius from a given reference model. This is the "robustness" approach. We show that previous methods for measuring this radius, e.g. relative entropy or polynomial diverg…
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.
Study accelerates gradient methods in machine learning, revealing risk and stability connections.
problem Understanding the statistical risk of accelerated gradient methods in machine learning.
method Continuous-time analysis of Nesterov's accelerated gradient method and Polyak's heavy ball method for least squares regression.
result Connections between early stopping, stability, and curvature of loss function are revealed.
Symplectic discretization accelerates optimization of smooth convex functions.
problem Optimizing smooth convex functions efficiently.
method Discretizing Nesterov's and Polyak's methods using Euler and symplectic schemes.
result Symplectic discretization achieves accelerated optimization for smooth convex functions.
Generalizes momentum methods using Hamiltonian dynamics.
problem Optimization in constrained Euclidean and non-Euclidean spaces.
method Hamiltonian perspective to generalize momentum methods.
result Generic and unifying nonasymptotic analysis of convergence.
Paper tackles DP-SCO with heavy-tailed data in high dimensions, improving error bounds.
problem Differentially private stochastic optimization with heavy-tailed data in high-dimensional spaces.
method Proposes methods for DP-SCO with polytope constraints and LASSO, analyzing sparsity constraints.
result Achieved near optimal error bounds for DP-SCO with heavy-tailed data.
We show that accelerated gradient descent, averaged gradient descent and the heavy-ball method for non-strongly-convex problems may be reformulated as constant parameter second-order difference equation algorithms, where stability of the system is equivalent to convergence at rate O(1/n 2), where n is the number of ite…
Acceleration in Hilbert spaces reduces computations but not accuracy.
problem Improving learning accuracy with fewer computations.
method Analysis of Nesterov acceleration and heavy-ball methods in Hilbert spaces.
result Acceleration can reduce computations but not improve accuracy with respect to gradient descent.
Robust CG methods avoid data corruption and solve structured statistical estimation problems.
problem Data corruption and heavy-tailed data in structured statistical estimation.
method Robustification of Conditional Gradient (CG) type methods using Huber's corruption model and robust mean gradient estimation.
result Robust CG methods converge linearly with correct sample complexity, even for high-dimensional problems.
The paper analyzes how momentum affects convergence in stochastic gradient methods.
problem Lack of clear understanding of momentum's impact on convergence and performance.
method Unified analysis of several popular algorithms using the QHM formulation.
result Provides practical guidelines for setting learning rate and momentum parameters.
Derives new optimization methods using variational integrators.
problem Optimization methods in machine learning.
method Variational integrators and principles of Hamilton and Lagrange-d'Alembert.
result Derives two families of optimization methods, including Nesterov's accelerated gradient method.
RAME adapts learning rates using recent first moment of gradients.
problem Training deep neural networks efficiently and adaptively.
method RAME computes individual learning rates using the most recent first moment of gradients.
result RAME outperforms SHB, Adam, and RMSprop in convergence speed and generalization performance.
Extends random feature analysis to spectral methods and improves learning rates.
problem Improving generalization properties of spectral methods in large-scale learning.
method Extends random feature analysis to a broad class of spectral regularization techniques, including gradient descent and Nesterov method.
result Obtains optimal learning rates for regularity classes, including those not in the RKHS.
There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation, a notion made precise in d'Aspremont 2008 and Devolder, Glineur, …
Improved regret bounds for linear bandits with heavy-tailed rewards.
problem Stochastic linear bandits with heavy-tailed rewards.
method Elimination-based algorithm guided by experimental design.
result Regret bound of \(\tilde{\mathcal{O}}(d^\frac{1+3ε}{2(1+ε)} T^\frac{1}{1+ε})\) for \(ε\in (0,1)\).
Optimized method tackles convex optimization with heavy-tailed noise.
problem Convex optimization problems with noisy gradients.
method Vanilla stochastic proximal subgradient method without gradient clipping or normalization.
result Achieves optimal complexity for various convex optimization types under heavy-tailed noise.
Proposes a new distribution for robust time series modeling with heavy tails.
problem Robust modeling of time series with heavy-tailed noise.
method Spliced Binned-Pareto distribution for non-stationary time series.
result Accurately models extreme events and captures time dependencies in higher moments.
Heavy Lasso improves robustness in high-dimensional linear regression with heavy-tailed errors.
problem Challenges of classical Lasso in handling heavy-tailed noise and outliers.
method Data-augmented soft-thresholding with Student's t-distribution loss.
result Heavy Lasso achieves comparable rates to Huber loss under theoretical bounds.
Paper tackles robust offline RL with heavy-tailed rewards.
problem Real-world applications often encounter heavy-tailed rewards, challenging offline RL.
method Proposes ROAM and ROOM algorithms using median-of-means method for robust off-policy evaluation and OPO.
result Demonstrates superior performance on heavy-tailed reward datasets compared to existing methods.
New method improves optimization and DP in FL.
problem Combining strong DP and optimization in FL.
method Combining clipping, momentum, and error feedback.
result Optimal convergence rate and near optimal DP guarantees.