A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Heavy Ball method speeds up finding global optima in non-convex problems.
Nonconvex optimization algorithms with random initialization have attracted increasing attention recently. It has been showed that many first-order methods always avoid saddle points with random starting points. In this paper, we answer a question: can the nonconvex heavy-ball algorithms with random initialization avoi…
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 .…
In this work we establish the first linear convergence result for the stochastic heavy ball method. The method performs SGD steps with a fixed stepsize, amended by a heavy ball momentum term. In the analysis, we focus on minimizing the expected loss and not on finite-sum minimization, which is typically a much harder p…
New method shows stochastic momentum can converge quickly on optimization problems.
In this paper, we revisit the convergence of the Heavy-ball method, and present improved convergence complexity results in the convex setting. We provide the first non-ergodic O(1/k) rate result of the Heavy-ball algorithm with constant step size for coercive objective functions. For objective functions satisfying a re…
Arguably, the two most popular accelerated or momentum-based optimization methods in machine learning are Nesterov's accelerated gradient and Polyaks's heavy ball, both corresponding to different discretizations of a particular second order differential equation with friction. Such connections with continuous-time dyna…
Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distinguish between two fundamentally different algorithms---Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) and Po…
Paper analyzes SHB method for neural networks, proving stability, connectivity, and global convergence.
This paper analyzes two Lie group momentum optimization algorithms and their convergence rates.
A new Bayesian filtering method speeds up stochastic Newton optimization.
Develops a computationally tractable differentially private mean estimator called the balloon mean.
Two new differentially private optimization algorithms derived from accelerated methods.
The paper analyzes convergence rates for SGD and SHB methods.
Proposes momentum methods for Lie groups, improving on classical algorithms.
Study accelerates optimization methods in non-convex problems, but doesn't improve the algorithm's performance.
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.
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.
Optimizes web page freshness with limited crawling frequencies.
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…
Improved SHB method for faster convergence on strongly-convex quadratics.
A method for estimating the median of gradients in stochastic optimization.
Optimizes privacy-preserving optimization for heavy-tailed data.
Optimization algorithms help overparameterized neural networks achieve high performance.
We study first-order optimization methods obtained by discretizing ordinary differential equations (ODEs) corresponding to Nesterov's accelerated gradient methods (NAGs) and Polyak's heavy-ball method. We consider three discretization schemes: an explicit Euler scheme, an implicit Euler scheme, and a symplectic scheme.…
We take a Hamiltonian-based perspective to generalize Nesterov's accelerated gradient descent and Polyak's heavy ball method to a broad class of momentum methods in the setting of (possibly) constrained minimization in Euclidean and non-Euclidean normed vector spaces. Our perspective leads to a generic and unifying non…
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…
Study accelerates gradient methods in machine learning, revealing risk and stability connections.
Fine-grained analysis of gradient descent with momentum provides modified loss equations.
We study learning properties of accelerated gradient descent methods for linear least-squares in Hilbert spaces. We analyze the implicit regularization properties of Nesterov acceleration and a variant of heavy-ball in terms of corresponding learning error bounds. Our results show that acceleration can provides faster …
The use of momentum in stochastic gradient methods has become a widespread practice in machine learning. Different variants of momentum, including heavy-ball momentum, Nesterov's accelerated gradient (NAG), and quasi-hyperbolic momentum (QHM), have demonstrated success on various tasks. Despite these empirical successe…
Paper tackles DP-SCO with heavy-tailed data in high dimensions, improving error bounds.
Adaptive gradient methods such as Adam have been shown to be very effective for training deep neural networks (DNNs) by tracking the second moment of gradients to compute the individual learning rates. Differently from existing methods, we make use of the most recent first moment of gradients to compute the individual …
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…
Robust CG methods avoid data corruption and solve structured statistical estimation problems.
Derives new optimization methods using variational integrators.
Extends random feature analysis to spectral methods and improves learning rates.
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, …
Optimized method tackles convex optimization with heavy-tailed noise.
Proposes a new distribution for robust time series modeling with heavy tails.
Improved regret bounds for linear bandits with heavy-tailed rewards.
Heavy Lasso improves robustness in high-dimensional linear regression with heavy-tailed errors.
Stochastic momentum methods have been widely adopted in training deep neural networks. However, their theoretical analysis of convergence of the training objective and the generalization error for prediction is still under-explored. This paper aims to bridge the gap between practice and theory by analyzing the stochast…
Paper tackles robust offline RL with heavy-tailed rewards.
New method bounds stochastic subgradient methods with heavy-tailed noise.
Two major momentum-based techniques that have achieved tremendous success in optimization are Polyak's heavy ball method and Nesterov's accelerated gradient. A crucial step in all momentum-based methods is the choice of the momentum parameter which is always suggested to be set to less than . Although the choice…