Develops mathematical framework for analyzing stochastic gradient algorithms.
problem Analyzing the dynamics of stochastic gradient algorithms.
method Stochastic modified equations (SME) framework to approximate stochastic gradient algorithms as stochastic differential equations.
result Proves that the approximation leads to precise results on SGD, momentum SGD, and Nesterov's accelerated gradient method.
Paper introduces a new multi-kernel algorithm for better gradient approximation.
problem Improving gradient approximation in high-dimensional problems.
method Develops a multi-kernel passive stochastic gradient algorithm with variance reduction.
result The multi-kernel algorithm performs better in high-dimensional problems.
This paper analyzes adaptive gradient algorithms for better performance in ill-conditioned problems.
problem Poor performance of standard stochastic gradient algorithms in ill-conditioned problems.
method Non-asymptotic analysis of adaptive gradient algorithms (Adagrad and Stochastic Newton) for strongly convex objectives.
result Theoretical analysis and adaptation to practical applications like linear regression and regularized GLM.
Overview of non-stochastic-gradient SA algorithms in signal processing and ML.
problem Dealing with large data sets and uncertainties in signal processing and machine learning.
method General framework of SA algorithms using Lyapunov functions.
result Unified convergence properties of non-stochastic-gradient algorithms.
SGBD algorithm improves robustness in Bayesian sampling.
problem Inefficiency of existing MCMC algorithms in large datasets.
method Extends Barker MCMC to stochastic gradient framework, introducing bias-corrected version.
result SGBD is more robust to hyperparameter tuning and gradient noise.
Stochastic approximation algorithms show exponential progress bounds.
problem Analyzing the convergence of stochastic approximation algorithms.
method Developed geometric ergodicity proofs to establish exponential concentration bounds.
result Proved faster convergence rates for specific algorithms.
In this paper, we study and analyze the mini-batch version of StochAstic Recursive grAdient algoritHm (SARAH), a method employing the stochastic recursive gradient, for solving empirical loss minimization for the case of nonconvex losses. We provide a sublinear convergence rate (to stationary points) for general noncon…
SAGD uses Langevin algorithm for efficient gradient descent.
problem Efficiently approximating gradients in complex models.
method Langevin algorithm for biased but asymptotically accurate gradients.
result Theoretical convergence guarantee for SAGD.
We develop the method of stochastic modified equations (SME), in which stochastic gradient algorithms are approximated in the weak sense by continuous-time stochastic differential equations. We exploit the continuous formulation together with optimal control theory to derive novel adaptive hyper-parameter adjustment po…
Unified framework connects stochastic optimization to Bayesian inference.
problem Stochastic optimization algorithms and their theoretical underpinnings.
method Latent variational problem and Forward Backward Stochastic Differential Equations (FBSDE).
result Recovery of various adaptive stochastic gradient descent methods.
Algorithm improves stochastic gradient optimization with normalized steps.
problem Stochastic and finite sum minimization problems.
method Trust region algorithm with normalized steps.
result Algorithm converges similarly to traditional stochastic gradient under certain conditions.
A new hybrid algorithm reduces stochastic gradient evaluations for nonconvex optimization.
problem Solving stochastic composite nonconvex optimization problems efficiently.
method Proposes a new hybrid variance-reduced proximal gradient method with a stochastic gradient estimator.
result Achieves optimal stochastic oracle complexity bound with one less gradient evaluation.
Stochastic gradient algorithms estimate the gradient based on only one or a few samples and enjoy low computational cost per iteration. They have been widely used in large-scale optimization problems. However, stochastic gradient algorithms are usually slow to converge and achieve sub-linear convergence rates, due to t…
Kalman Gradient Descent optimizes machine learning models by reducing variance in stochastic optimization.
problem Reducing variance in stochastic gradient descent to improve optimization performance.
method Uses Kalman filtering to adaptively reduce gradient variance in stochastic gradient descent.
result Improved performance on various machine learning tasks including neural networks and black box variational inference.
New algorithm reduces variance in nonconvex optimization problems.
problem Finite-sum nonconvex optimization problems.
method Stochastic gradient descent with nested variance reduction.
result Converges to an ε-stationary point with improved complexity.
Proposes a new algorithm for k k k -means clustering using stochastic backward Euler.
problem Improving k k k -means clustering performance and robustness. method Implicit gradient descent with stochastic backward Euler iteration.
result The algorithm provides better clustering results compared to traditional k k k -means. Langevin algorithms enhance training of deep neural networks for stochastic control problems.
problem Training acceleration for deep neural networks in stochastic control problems.
method Application of Langevin algorithms to minimize the loss of deep neural networks in stochastic control problems.
result Langevin algorithms improve training on various stochastic control problems.
The paper studies stochastic gradient descent with infinite variance gradients.
problem Theoretical properties of SGD with infinite variance gradients.
method Establish asymptotic behavior of SGD with infinite variance gradients.
result Asymptotic distribution of SGD is characterized as a stationary distribution of an Ornstein-Uhlenbeck process driven by a stable Lévy process.
The paper analyzes gradient descent algorithms using stochastic differential equations.
problem Understanding the asymptotic behaviors of gradient descent algorithms in statistical and computational contexts.
method Modeling gradient descent algorithms as stochastic differential equations and applying gradient flow central limit theorems.
result Identifies four factors affecting the local minima found by stochastic gradient descent.
A new tamed stochastic gradient Hamiltonian Monte Carlo algorithm for superlinearly growing stochastic gradients.
problem Sampling and stochastic optimization problems with superlinearly growing stochastic gradients.
method Tamed Stochastic Gradient Hamiltonian Monte Carlo (tSGHMC) algorithm.
result Established a non-asymptotic error bound in Wasserstein-2 distance with a convergence rate of 1 / 4 1/4 1/4 . Optimal algorithms for online convex optimization with missing sub-gradient observations.
problem Online convex optimization with noisy or missing sub-gradient observations.
method Adaptive algorithms using sub-gradient descent with minimax optimal regret guarantees.
result Achieves tight minimax optimal regret bounds with empirical property estimation.
New method for zeroth-order stochastic gradient algorithms provides confidence intervals.
problem Lack of inferential capabilities for zeroth-order stochastic gradient algorithms.
method Established central limit theorem and provided online estimators for asymptotic covariance matrix.
result Asymptotically valid confidence sets for parameter estimation and prediction.
A new method for stochastic optimization using virtual gradients.
problem Stochastic optimization challenges in computational efficiency and memory usage.
method Inspired by dynamic programming, SVGD uses a computational graph and automatic differentiation for efficient optimization.
result Experimental results show SVGD outperforms other methods on multiple datasets and network models.
Unified algorithm for stochastic optimization with time-varying momentum converges under general conditions.
problem Optimizing functions with time-varying gradients and biases.
method Unified algorithm using a time-varying momentum term.
result Convergence of the unified algorithm under general conditions.
New algorithm finds local minima faster than SGD for nonconvex functions.
problem Finding local minima in nonconvex optimization efficiently.
method Stochastic cubic regularization of Newton method.
result Matches best-known result for local minima without acceleration.
Improved SVRC algorithm reduces complexity for nonconvex optimization.
problem Finding local minima for nonconvex finite-sum optimization with improved complexity.
method Stochastic Recursive Variance-Reduced Cubic regularization (SRVRC) using recursively updated semi-stochastic gradient and Hessian estimators.
result SRVRC achieves improved gradient and Hessian complexities to find ( ε , ε ) (ε, \sqrtε) ( ε , ε ) -approximate local minimum. Gradient descent variants improve phase retrieval accuracy.
problem Phase retrieval problem in high-dimensional spaces.
method Gradient descent, stochastic gradient descent, Langevin algorithm, dynamical mean-field theory.
result Stochastic variants of gradient descent achieve better generalization in phase retrieval.
Analysis of a stochastic system showing convergence to an averaged model with Gaussian deviations.
problem Convergence analysis of a perturbed compositional gradient flow system.
method Separation of scales and averaging principle applied to stochastic differential equations.
result The slow motion of the system can be approximated by a standard perturbed gradient flow or SCGD algorithm.
STORM-PG uses momentum for faster policy gradient updates.
problem Improving policy gradient methods for reinforcement learning.
method Introduces STORM-PG, a SARAH-based algorithm with exponential moving average.
result Achieves O ( 1 / ε 3 ) O(1/ε^3) O ( 1/ ε 3 ) sample complexity, matching best-known rate. New convergence guarantees for learning with unknown nuisance parameters.
problem Learning problems with unknown nuisance parameters.
method Stochastic gradient optimization with Neyman orthogonality and approximately orthogonalized updates.
result Stochastic gradient algorithms can converge under conditions of nuisance parameters.
Stochastic gradient algorithms have been the main focus of large-scale learning problems and they led to important successes in machine learning. The convergence of SGD depends on the careful choice of learning rate and the amount of the noise in stochastic estimates of the gradients. In this paper, we propose a new ad…
A new algorithm SRG-DQN reduces variance in deep Q-learning.
problem Inaccurate estimation of anchor points in SVRG for deep Q-learning.
method Introduces recursive gradient variance reduction for stochastic gradient updates.
result Demonstrates improved efficiency and effectiveness of SRG-DQN on reinforcement learning tasks.
New oracles improve stochastic optimization with noisy or biased measurements.
problem Optimizing functions with noisy or biased measurements.
method Introduced biased gradient oracles for stochastic optimization, analyzed RSG and SGD algorithms with these oracles.
result Derived non-asymptotic bounds for convergence rates of algorithms with biased gradient oracles.
Analyzes the asymptotic bias of stochastic gradient search algorithms.
problem Understanding the long-term behavior of stochastic gradient search algorithms.
method Dynamic system theory and differential geometry to derive bounds on asymptotic bias.
result Tight bounds on the asymptotic bias of stochastic gradient search algorithms are derived.
New algorithm optimally minimizes convex functions with noisy gradients.
problem Minimizing strongly convex, smooth functions with noisy gradient estimates.
method A multistage accelerated stochastic gradient method with restarts.
result Achieves optimal convergence rate in deterministic and stochastic cases.
Unified view of gradient-based algorithms for stochastic convex composite optimization.
problem Optimization of stochastic convex composite functions.
method Extend the concept of estimate sequence to cover various gradient-based methods.
result Generic convergence proof and new adaptive SVRG variant.
Improves stochastic gradient methods for faster convergence.
problem Low asymptotic convergence of stochastic gradient methods in nonconvex optimization.
method Predictive Local Smoothness (PLS) method to adaptively adjust learning rates based on local smoothness predictions.
result New variants of SGD, AccSGD, and AMSGrad achieve faster linear convergence.
A new method improves stochastic gradient descent for faster and more efficient estimation.
problem Efficient and fast parametric estimation methods.
method Projected stochastic gradient descent corrected by Fisher scoring.
result The method is faster and more efficient than traditional methods.
Stochastic gradient descent on manifolds improves low-rank approximation.
problem Efficiently approximate large matrices with lower rank.
method Stochastic gradient descent on a manifold.
result Algorithm outperforms Euclidean space methods on Netflix Prize data.
RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments c…
A new algorithm for reinforcement learning using SVRPG.
problem Solving Markov Decision Processes (MDPs) with policy gradient methods.
method Stochastic variance-reduced policy gradient (SVRPG) algorithm.
result SVRPG achieves linear convergence under increasing batch sizes.
Adaptive algorithm improves convergence rate of Langevin dynamics.
problem Improving convergence rate of Langevin dynamics.
method Adaptive non-reversible stochastic gradient Langevin dynamics algorithm.
result Improved convergence rate of the algorithm.
New SAGA algorithm with decreasing step for stochastic optimization.
problem Analysis of SAGA algorithm and its convergence properties.
method Introducing a new λ-SAGA algorithm with decreasing step, investigating convergence and establishing a central limit theorem.
result Established convergence and central limit theorem for λ-SAGA algorithm.
The paper analyzes SW-SGD for MSE in biased and variance-reduced gradient estimators.
problem Analyzing MSE of SW-SGD in biased and variance-reduced gradient estimators.
method Using asymptotic normality, the paper characterizes SW-SGD's mean and variance, proving convergence and showing SW-SGD's superiority over SGD.
result SW-SGD incurs lower MSE than SGD on quadratic and convex problems.
Paper analyzes stochastic gradient for PCA in streaming data.
problem Complexity analysis of stochastic gradient for PCA in online settings.
method Studied stochastic gradient algorithm with online learning rate selection.
result Practical relevance of plain stochastic gradient confirmed; learning rate improvement possible.
Stochastic gradient descent is a simple approach to find the local minima of a cost function whose evaluations are corrupted by noise. In this paper, we develop a procedure extending stochastic gradient descent algorithms to the case where the function is defined on a Riemannian manifold. We prove that, as in the Eucli…
New method efficiently computes gradients for stochastic differential equations.
problem Computing gradients for stochastic differential equations efficiently.
method Generalized adjoint sensitivity method to stochastic differential equations.
result Time-efficient and memory-efficient computation of gradients with high-order solvers.
DMGD algorithm solves large-scale ML problems in costly sampling settings.
problem Large-scale machine learning problems with costly or impossible independent sampling.
method Decentralized Markov chain gradient descent (DMGD) algorithm.
result Nonergodic and ergodic convergence rates established for DMGD.