New optimizer G-AdaGrad improves upon AdaGrad for non-convex machine learning problems.
problem Solving non-convex machine learning problems efficiently.
method Proposes a new optimizer G-AdaGrad and analyzes its convergence using state-space models.
result Empirical results show G-AdaGrad performs better than AdaGrad and Adam.
AdaGrad on linear problems converges to SVM direction.
problem Understanding AdaGrad's implicit bias on linear classification.
method Characterizing AdaGrad's convergence direction as a quadratic optimization problem.
result AdaGrad converges to a direction similar to SVM's solution.
Efficient approximations for AdaGrad reduce computation while maintaining performance.
problem Training deep neural networks efficiently in high dimensions.
method Ada-LR and RadaGrad use random projections to approximate full-matrix AdaGrad.
result Regret of Ada-LR is close to full-matrix AdaGrad, achieving similar performance with less computation.
Simpler, parameter-free AdaGrad and Adam variants with convergence guarantees.
problem Inefficiencies in ad-hoc learning rate tuning for optimization algorithms.
method Developed AdaGrad++ and Adam++ without predefined learning rates and proved their convergence.
result AdaGrad++ and Adam++ achieve comparable convergence rates to AdaGrad and Adam respectively.
AdaGrad converges to stationary points in nonconvex optimization with robust stepsize.
problem Convergence guarantees for AdaGrad in nonconvex optimization.
method AdaGrad with stepsize update based on gradient norms.
result AdaGrad-Norm converges at optimal rates in both stochastic and batch settings.
AdaGrad fails to adapt to Hölder-smoothness in composite optimization problems.
problem AdaGrad's convergence rate is suboptimal for composite objectives.
method Exhibited a simple one-dimensional convex problem to highlight AdaGrad's limitations.
result AdaGrad does not achieve the classical convergence rate for Hölder-smooth objectives.
This study analyzes AdaGrad's stability and convergence in non-convex optimization.
problem Lack of theoretical analysis for AdaGrad in non-convex optimization.
method Novel stopping time-based techniques from probability theory.
result Established stability and derived convergence rates for AdaGrad.
AdaGrad converges under heavy-tailed noise without extra operations.
problem Optimizing with heavy-tailed noise in machine learning.
method Investigation of AdaGrad convergence under heavy-tailed noise.
result First provable convergence rate for AdaGrad in non-convex optimization.
Proposes a new adaptive gradient method based on gradient differences.
problem Manual tuning of stepsize in vanilla gradient methods.
method Adaptation driven by cumulative squared norms of gradient differences.
result More robust than AdaGrad in various settings.
Unified AdaGrad with momentum accelerates stochastic optimization in non-convex settings.
problem Theoretical gaps in convergence for AdaGrad and related algorithms in non-convex stochastic settings.
method Proposes AdaUSM, a unified momentum scheme for AdaGrad with adaptive learning rates.
result AdaUSM achieves a convergence rate of O ( log ( T ) / T ) \mathcal{O}(\log(T)/\sqrt{T}) O ( log ( T ) / T ) in non-convex stochastic settings. We provide a simple convergence proof for Adam and Adagrad.
problem Smooth objective functions with bounded gradients.
method Simple proof covering Adam and Adagrad.
result Explicit upper-bound on the squared norm of the objective gradient.
AdaGrad outperforms SGD in non-convex optimization problems by a factor of d.
problem Finding near-stationary points in stochastic non-convex optimization.
method Refined assumptions on smoothness and gradient noise variance, l 1 l_1 l 1 -norm stationarity measure. result AdaGrad achieves a convergence rate favorable over SGD in certain non-convex settings.
Improved private AdaGrad achieves faster convergence rates for convex functions.
problem Private empirical risk minimization with differential privacy.
method Noisy AdaGrad with knowledge of gradient subspace geometry.
result Faster convergence rates for convex functions, bypassing traditional bounds.
Efficient optimization method reduces Full AdaGrad complexity.
problem Computational challenges in Full AdaGrad for large-scale applications.
method Recursive method and streaming variant for parameter updates.
result Significant reduction in complexity and resource demands.
AdaGrad-Norm achieves linear convergence for certain functions.
problem Proving linear convergence for specific types of functions.
method Introducing RUIG, a measure of gradient balance; developing a two-stage framework.
result AdaGrad-Norm achieves linear convergence for certain functions.
Study revisits AdaGrad convergence with relaxed noise assumptions.
problem Non-convex smooth optimization problems with general noise.
method General noise model with function value gap and gradient magnitude control.
result Probabilistic convergence rate of ( ilde{\mathcal{O}}(1/\sqrt{T})) under general noise.
GradaGrad adapts learning rate non-monotonically, overcoming AdaGrad's step size decrease.
problem Fixed learning rate in AdaGrad leads to step size decrease over time.
method Introduces GradaGrad, which grows or shrinks the learning rate based on a different accumulation in the denominator.
result GradaGrad achieves similar convergence rates as AdaGrad and demonstrates non-monotone adaptation.
Improved SGD with AdaGrad stepsizes adapts to unknown parameters and unbounded gradients.
problem Adaptive optimization with unknown parameters and unbounded gradients.
method Stochastic Gradient Descent with AdaGrad stepsizes, without assuming problem parameters or strong global Lipschitz conditions.
result Sharp rates of convergence in both low-noise and high-noise regimes, supporting an affine variance noise model.
This paper addresses convergence issues in non-convex optimization problems using stagewise learning.
problem Theoretical gaps in convergence for non-convex problems and lack of adaptive step size theories.
method Proposes a stagewise optimization framework for non-smooth non-convex problems using adaptive step sizes.
result Demonstrates adaptive convergence of stagewise AdaGrad and improved generalization performance.
CompAdaGrad improves AdaGrad's performance without its computational cost.
problem Improving AdaGrad's performance without its high computational cost.
method CompAdaGrad combines full-matrix and diagonal regularization in a low-dimensional subspace.
result CompAdaGrad achieves better results than diagonal AdaGrad with linear computational complexity.
Private adaptive methods improve on traditional SGD for convex optimization.
problem Differential privacy constraints in gradient optimization.
method Differentially private variants of SGD and AdaGrad with adaptive stepsizes and non-isotropic clipping.
result Private AdaGrad outperforms private SGD in high-dimensional problems.
AdaGrad-Norm achieves optimal convergence rates for non-convex objectives without tuning.
problem Optimal convergence rates for non-convex, smooth objectives with adaptive step sizes.
method Adaptive SGD (AdaGrad-Norm) with self-tuning step sizes, analyzing under unbounded gradients and affine variance scaling.
result AdaGrad-Norm achieves order optimal convergence rate of $\mathcal{O}\left(\frac{\mathrm{poly}\log(T)}{\sqrt{T}}
ight)$ under optimal assumptions.
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.
Paper analyzes and improves adaptive gradient methods for optimization.
problem Improving optimization methods for deep neural networks.
method Analyzes and proposes variants of RMSProp and Adagrad for online convex optimization.
result Proposes SC-Adagrad and SC-RMSProp with logarithmic regret bounds for strongly convex functions.
Paper analyzes convergence of adaptive gradient methods for nonconvex optimization.
problem Lack of convergence guarantees for adaptive gradient methods in nonconvex optimization.
method Fine-grained convergence analysis of adaptive gradient methods including AMSGrad, RMSProp, and AdaGrad.
result Proves adaptive gradient methods converge to first-order stationary points for smooth nonconvex functions.
New method shows AdaGrad converges globally to neural network minima.
problem Convergence of adaptive gradient methods for neural networks.
method Proposed adaptive gradient method for over-parameterized neural networks.
result Converges to global minimum in polynomial time for two-layer networks.
New matrix approximation method speeds up optimization for deep learning.
problem Efficient computation of matrix inverse and square root for high-dimensional optimization.
method Divide matrix into blocks and represent each block by one or two numbers.
result Improved performance of AdaGrad in training deep neural networks compared to diagonal approximation.
This work provides formal guarantees for heuristic optimization methods in machine learning.
problem Lack of theoretical understanding of heuristic optimization methods in machine learning.
method Analysis and formal guarantees for AdaGrad, SGD with exponential and cosine step sizes, and momentum methods.
result First formal guarantees for AdaGrad and SGD variants, including convergence and adaptivity to noise.
AdaSVRG combines adaptive gradient with SVRG for robust optimization.
problem Variance reduction in finite-sum minimization with unknown constants.
method AdaSVRG uses AdaGrad in SVRG's inner loop to make it robust.
result AdaSVRG achieves optimal gradient evaluations with no need for problem-dependent constants.
Algorithm reduces regret in online learning with varying norms.
problem Online convex optimization with changing norms.
method Adaptive online learning algorithm that adjusts to varying norms without tuning.
result Achieves improved regret bounds for full-matrix AdaGrad.
The paper analyzes adaptive stepsizes for stochastic gradient descent, proving convergence guarantees.
problem The variability and dependence on stepsizes in stochastic gradient descent.
method Theoretical analysis of generalized AdaGrad stepsizes in convex and non-convex settings.
result Proves almost sure asymptotic convergence of gradients to zero for generalized AdaGrad stepsizes in the non-convex setting.
This paper proves AdaGrad and Adam converge linearly under PL inequality.
problem Understanding the convergence of adaptive gradient methods.
method Unified approach proving AdaGrad and Adam converge linearly under PL inequality.
result AdaGrad and Adam converge linearly when the cost function is smooth and satisfies PL inequality.
A parameter-free PGD algorithm for convex optimization.
problem Minimizing convex functions over convex sets.
method A fully adaptive AdaGrad variant of PGD without parameters or restarts.
result Optimal convergence rates for cumulative regret.
Bayesian Adam method improves neural network uncertainty estimation.
problem Improving uncertainty estimation in neural networks.
method Probabilistic interpretation of adaptive optimisation algorithms.
result Bayesian Adam method correctly relates learnt uncertainties to weights' predictive capabilities.
The paper introduces various gradient descent algorithms for training deep learning models.
problem Training deep neural networks is challenging due to their complexity.
method Gradient descent and its variants are discussed for optimizing deep learning models.
result Gradient descent and its variants improve the training performance of deep learning models.
Dropout and other feature noising schemes control overfitting by artificially corrupting the training data. For generalized linear models, dropout performs a form of adaptive regularization. Using this viewpoint, we show that the dropout regularizer is first-order equivalent to an L2 regularizer applied after scaling t…
DoWG optimizer automatically adapts to convex and nonsmooth problems without tuning.
problem Optimizing machine learning models efficiently and adaptively.
method DoWG uses a distance-based weighted version of gradient averaging for optimization.
result DoWG achieves convergence rates similar to optimally tuned gradient descent.
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.
New adaptive methods for constrained convex optimization and variational inequalities.
problem Optimization of constrained convex problems and variational inequalities.
method AdaACSA and AdaAGD+ are accelerated methods that achieve nearly-optimal convergence rates for smooth and non-smooth functions.
result Achieve nearly-optimal convergence rates for both smooth and non-smooth functions, even with stochastic gradients.
New adaptive importance samplers improve stability and accuracy.
problem Improving the stability and accuracy of importance sampling estimators.
method Introducing AdaOAIS, a new adaptive importance sampler using adaptive optimisers to address the instability of OAIS.
result AdaOAIS leads to stable importance sampling estimators in practice.
This study explains how different training methods affect the minimizer of neural networks.
problem How training methods influence the minimizer of neural networks.
method Explains how initialization size, adaptive optimization (AdaGrad), and stochastic mini-batch training affect the minimizer.
result Different training methods lead to different minimizers, even in overparameterized networks.
Prodigy estimates learning rate without tuning, improving convergence.
problem Estimating optimal learning rate in adaptive methods.
method Prodigy modifies D-Adaptation to estimate distance to solution D D D . result Prodigy improves convergence rate by a factor of O ( log ( D / d 0 ) ) O(\sqrt{\log(D/d_0)}) O ( log ( D / d 0 ) ) . Adaptive methods often find worse generalization than SGD in overparameterized problems.
problem The performance of adaptive methods in overparameterized problems.
method Adaptive methods (AdaGrad, RMSProp, Adam) compared to gradient descent (GD) and stochastic gradient descent (SGD).
result Adaptive methods often generalize worse than SGD, even when they have better training performance.
A new method for uncertainty estimation in neural networks using existing optimization steps.
problem Uncertainty quantification in deep neural networks.
method L2M: Practical posterior Laplace approximation with optimization-driven second moment estimation.
result L2M method yields reasonable results without requiring changes in models or extra computational steps.
Relativistic Monte Carlo improves HMC for better sampling.
problem HMC's sensitivity to time discretization and mismatched spatial geometry.
method Introducing relativistic dynamics with a maximum velocity.
result Relativistic algorithms outperform classical Newtonian variants and Adam.
AdaOja improves Oja's algorithm for streaming PCA with adaptive learning rates.
problem Lack of standardized learning rates in Oja's algorithm for streaming PCA.
method Proposes AdaOja, a novel learning rate scheme for Oja's method.
result AdaOja outperforms common learning rate choices and performs comparably to state-of-the-art algorithms.
adaQN improves training RNNs with low cost and good performance.
problem Training RNNs is computationally difficult due to vanishing/exploding gradient issues.
method Stochastic quasi-Newton algorithm with L-BFGS updating, low per-iteration cost.
result adaQN is competitive with popular RNN training algorithms on language modeling tasks.
The paper analyzes Adam-type algorithms for non-convex optimization and proves their convergence rate.
problem The convergence of Adam-type algorithms for non-convex optimization problems.
method The paper studies a class of adaptive gradient-based momentum algorithms that update search directions and learning rates simultaneously.
result The Adam-type methods can achieve a convergence rate of order O ( log T / T ) O(\log{T}/\sqrt{T}) O ( log T / T ) for nonconvex stochastic optimization.