mS2GD improves S2GD for large-scale convex optimization.
problem Minimizing a strongly convex function with a large sum of smooth convex functions and a simple nonsmooth convex regularizer.
method mS2GD combines deterministic and stochastic gradient steps with mini-batching.
result mS2GD achieves faster convergence and parallelizable implementation.
Improves SGD for convex functions with mini-batches, proving linear convergence.
problem Minimizing convex functions with constraints.
method Projected semi-stochastic gradient descent with mini-batches.
result Linear convergence under weak strong convexity assumption.
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.
In this paper we study the problem of minimizing the average of a large number ( n n n ) of smooth convex loss functions. We propose a new method, S2GD (Semi-Stochastic Gradient Descent), which runs for one or several epochs in each of which a single full gradient and a random number of stochastic gradients is computed, fo…
We propose a mini-batching scheme for improving the theoretical complexity and practical performance of semi-stochastic gradient descent applied to the problem of minimizing a strongly convex composite function represented as the sum of an average of a large number of smooth convex functions, and simple nonsmooth conve…
New algorithm speeds up recovery of low-rank matrices.
problem Nonconvex low-rank matrix recovery problems.
method Stochastic variance-reduced gradient descent with semi-stochastic gradient.
result Linear convergence rate to unknown low-rank matrix.
New RGraSP framework for efficient non-convex optimization.
problem Large-scale non-convex sparsity-constrained optimization problems.
method Relaxed gradient support pursuit with semi-stochastic gradient hard thresholding.
result Our algorithms converge faster with lower per-iteration cost.
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. Efficient methods for training deep neural networks using subsampled Gauss-Newton and natural gradient.
problem Training deep neural networks with large datasets and variables.
method Subsampled Gauss-Newton and natural gradient methods with subsampled gradient estimates.
result Methods converge to a stationary point and are efficient to implement.
Gradient descent and noisy gradient descent explored on simple functions.
problem Behavior of gradient descent and noisy gradient descent on simple functions.
method Computer experiments with gradient descent and noisy gradient descent on simple functions.
result Noise affects the trajectory of gradient descent on simple functions.
Blind Descent avoids gradient issues, using a different learning approach.
problem Gradient issues like exploding and vanishing gradients.
method Does not use gradients to guide learning; instead, it is a more fundamental learning process.
result Gradient descent is a specific case of Blind Descent.
Study on noisy gradient descent in higher-dimensional minima.
problem Behavior of gradient descent in higher codimension.
method Computer experiments with noisy gradient descent.
result Effects of noise on gradient descent trajectories in higher codimension.
GP-LSTM models sequential data with LSTM inductive biases and scalable training.
problem Capturing recurrent structures in sequential data with standard kernel functions.
method Expressive closed-form kernel functions for Gaussian processes, optimized with semi-stochastic gradient procedure.
result State-of-the-art performance on benchmarks and autonomous driving application.
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.
Adaptive learning rate improves gradient descent for deep models.
problem Difficulty in tuning fixed learning rates for deep models.
method Proposes adaptive learning rates using either first-order or second-order methods.
result Optimized gradient descent leads to better convergence for machine learning algorithms.
Gradient descent optimizes deep ReLU networks with proper initialization.
problem Training deep neural networks with ReLU activation.
method Gradient descent and stochastic gradient descent with proper random weight initialization.
result Gradient descent finds global minima for over-parameterized deep ReLU networks.
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.
Gradient descent implicitly regularizes neural networks by penalizing large loss gradients.
problem How to optimize deep neural networks without explicit regularization.
method Backward error analysis to calculate implicit gradient regularization and demonstrate its effectiveness empirically.
result Implicit gradient regularization biases gradient descent toward flat minima, improving model robustness and test errors.
Gradient descent reliably finds local minima.
problem Finding local minima with gradient descent.
method Applied the Stable Manifold Theorem.
result Gradient descent converges to local minimizers almost surely.
Online gradient descent can simulate complex computations.
problem Understanding the fine-grained behavior of online gradient descent is hard.
method Proving online gradient descent can encode arbitrary polynomial-space computations.
result It is impossible to reason efficiently about the fine-grained behavior of online gradient descent under weak complexity-theoretic assumptions.
Derives Mirror Descent from gradient flow on a Riemannian manifold.
problem No specific problem stated; focuses on derivation.
method Derives Mirror Descent from gradient flow on a Riemannian manifold with a natural discretization.
result Generalizes Mirror Descent to non-Hessian metrics.
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.
Reparameterizes mirror descent as gradient descent for efficient sparse learning.
problem Efficiently training small sparse networks with mirror descent.
method Develops a framework to convert mirror descent updates into gradient descent updates on different parameters.
result Mirror descent can be reparameterized as gradient descent on modified parameters, facilitating standard backpropagation.
Gradient descent dynamics in nonconvex models explained with universality.
problem Understanding long-time behavior of nonconvex gradient descent.
method Developed a state evolution system for tracking gradient descent iterates.
result Gradient descent iterates are approximately independent of data and strongly incoherent with feature vectors.
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.
Unified framework for gradient descent variants in machine learning.
problem Understanding and comparing various gradient descent methods.
method A unified framework interpreting 6 gradient descent variants.
result Some variants coincide under specific conditions.
Gravilon improves gradient descent for neural networks.
problem Improving efficiency and accuracy of gradient descent methods.
method Uses geometric modification of gradient step lengths.
result Promising experimental results on MNIST classification.
Gradient descent on deep linear CNNs converges to a penalty-based solution.
problem Understanding gradient descent convergence in deep linear convolutional networks.
method Gradient descent on full-width linear convolutional networks of varying depth.
result Gradient descent converges to a penalty-based solution, not the hard margin SVM solution.
SGD reduces test error by decorrelating updates.
problem Improving generalization error in machine learning models.
method Derive a formula for generalization gap change due to SGD updates, compare to GD, and show decorrelation effect.
result SGD implicitly regularizes generalization error by decorrelating updates.
Natural gradient descent avoids the magic of model parametrization, leading to different optimization outcomes.
problem Understanding the impact of model parametrization on optimization and generalization in deep learning.
method Characterization of natural gradient flow in deep linear networks and nonlinear neural networks.
result Natural gradient descent fails to generalize in some cases, while gradient descent with the right architecture performs well.
Gradient descent with delayed updates converges faster with noise, even when delays are significant.
problem Analyzing convergence of gradient descent with delayed gradients and stochastic noise.
method Novel technique using generating functions for convergence analysis.
result Convergence bounds show that stochastic noise mitigates the negative effects of delays, improving performance.
Gradient descent biases towards stable rank networks for nearly-orthogonal data.
problem Understanding implicit bias in non-smooth neural networks trained by gradient descent.
method Analysis of two-layer ReLU and leaky ReLU networks trained by gradient descent on nearly-orthogonal data.
result Gradient descent biases towards networks with stable rank and uniform margin for nearly-orthogonal data.
New adaptive step-size method for convex optimization without tuning.
problem Optimizing convex functions efficiently with stochastic gradients.
method Adapted Adaptive Gradient Descent Without Descent to stochastic setting.
result Stochastic gradient descent converges under various assumptions.
Gradient descent converges to max-margin solution for hinge loss.
problem Applying gradient descent to the hinge loss for linear classifiers.
method Homotopic gradient descent applied to the hinge loss.
result Explicit convergence rates to max-margin solution for separable data.
Gradient descent can take exponentially long to escape saddle points in 2D.
problem Worst-case inefficiency of gradient descent in non-convex optimization.
method Analysis of gradient descent's performance on 2D functions.
result Gradient descent can take exponentially long to escape saddle points.
SGD and stochastic gradient descent converge at optimal rates for certain non-convex functions.
problem Optimal convergence rates for non-convex functions under gradient noise.
method Geometric interpretation of the PL-condition to analyze convergence rates.
result Convergence rates of SGD and stochastic gradient descent match those of strongly convex quadratics.
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.
Gradient descent at edge of stability stabilizes implicitly, following projected gradient descent.
problem Gradient descent's stability and sharpness behavior at the edge of instability.
method Cubic Taylor expansion analysis of gradient descent dynamics.
result Gradient descent at edge of stability implicitly follows projected gradient descent.
A new gradient descent method speeds up in flat regions and slows in steep directions.
problem Improving the speed and stability of gradient descent algorithms.
method Introducing a 'power gradient' where each gradient component is replaced by its H H H -th power, with 0 < H < 1 0<H<1 0 < H < 1 . result The new gradient descent methods achieve significantly better performances, especially for Nesterov accelerated gradient and AMSGrad.
This work proposes a new method for variational inference using Wasserstein gradient descent.
problem Optimizing variational parameters to match a true posterior distribution.
method Reinterpreting VI as an optimization problem over a variational parameter space, using Wasserstein gradient descent.
result The proposed Wasserstein gradient descent can be seen as a generalization of existing optimization techniques in VI.
Gradient descent achieves exact linear convergence rate for symmetric matrix completion.
problem Low-rank symmetric matrix completion using gradient descent.
method Local analysis of gradient descent for symmetric matrices without additional assumptions.
result Closed-form expression of exact linear convergence rate matches practice.
Gradient descent efficiently finds global minima in deep neural networks.
problem Training deep neural networks efficiently and reliably.
method Gradient descent, leveraging the stability of the Gram matrix induced by the network architecture.
result Gradient descent achieves zero training loss in polynomial time for deep over-parameterized neural networks with residual connections.
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.
Gradient descent benefits from tangent kernel advantages under specific conditions.
problem Comparing gradient descent with tangent kernel methods in learning.
method Analysis of gradient descent and tangent kernel methods under different conditions.
result Gradient descent can achieve small error only if tangent kernel methods have a non-trivial advantage, but this advantage can be very small.
Gradient descent with logistic loss can make two-layer networks interpolate binary classification data.
problem Training two-layer networks for binary classification.
method Gradient descent with logistic loss applied to two-layer networks.
result Gradient descent can drive training loss to zero under certain conditions.
Accelerates coordinate descent methods for machine learning problems.
problem Slowness of coordinate descent methods in machine learning.
method Extrapolation-based accelerated coordinate descent.
result Significant speed-up in practice compared to existing methods.
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.
Improved stochastic gradient descent analysis for non-smooth convex functions.
problem Minimizing non-smooth, non-differentiable convex functions.
method Stochastic gradient descent with suffix averaging method analysis.
result Error rate of final iterate is O ( log ( T ) / T ) O(\log(T)/T) O ( log ( T ) / T ) with high probability.