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.
Gradient descent achieves fast convergence for approximating functions with two-layer neural networks.
problem Approximating continuous functions with two-layer neural networks.
method Gradient descent combined with generic chaining technique from probability theory.
result Gradient descent yields an exponential convergence rate for two-layer neural networks without needing a large width relative to the number of data points.
Gradient descent trains shallow neural networks to approximate functions in 1D.
problem Approximating functions in 1D with shallow neural networks trained by gradient descent.
method Gradient descent optimization of non-convex weight space for finite width networks in 1D.
result Gradient descent can approximate functions in 1D with a minimal number of weights, balancing practical performance and theoretical capabilities.
Disputes the empirical Fisher approximation for natural gradient descent.
problem The empirical Fisher approximation fails to capture second-order information in general.
method Comparison of empirical Fisher and Fisher information matrices.
result The empirical Fisher does not generally approximate the Fisher or Hessian.
Stochastic gradient descent optimizes Nyström samples for kernel matrix approximation.
problem Optimizing Nyström samples for kernel matrix approximation.
method Stochastic gradient descent applied to multisets of landmark points (Nyström samples) using a surrogate criterion (radial SKD).
result Local minimization of the radial SKD yields improved Nyström approximation accuracy.
ErasureHead speeds up distributed GD with approximate gradient coding.
problem Mitigating delays in distributed gradient descent.
method Approximate gradient coding to tolerate delays.
result ErasureHead converges as quickly as GD and has faster runtime under probabilistic delays.
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.
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.
Riemannian stochastic gradient descent approximates a diffusion process called Riemannian stochastic modified flow.
problem Improving convergence rate of Riemannian stochastic gradient descent.
method Using stochastic differential geometry, the paper shows RSGD can be approximated by the Riemannian stochastic modified flow (RSMF).
result RSGD can be approximated by the solution to the RSMF driven by an infinite-dimensional Wiener process, increasing the order of approximation.
Continuous-time SGD converges under certain conditions, useful for deep learning.
problem Minimizing population expected loss in learning problems.
method Continuous-time approximation of stochastic gradient descent.
result Establishes sufficient conditions for convergence, applicable to overparametrized neural networks.
Continuous time analysis of momentum methods in neural networks.
problem Understanding the role of momentum in training neural networks.
method Deriving continuous time approximations of discrete algorithms to expose mechanisms.
result Fixed momentum methods approximate a time-rescaled gradient descent flow asymptotically.
New learning algorithm for real analytic functions without gradient descent.
problem Learning real analytic functions without gradient descent.
method Taylor approximation and sampling data distribution.
result Nonuniform learning result for real analytic functions.
Gradient descent struggles to achieve zero loss in deep learning models due to non-generic data distributions.
problem Achieving zero loss minimizers in deep learning networks.
method Analysis of gradient descent algorithm in deep learning, focusing on underparametrized networks.
result Zero loss minimization cannot be achieved generically in deep learning networks.
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.
Variational inference approximates the posterior distribution of a probabilistic model with a parameterized density by maximizing a lower bound for the model evidence. Modern solutions fit a flexible approximation with stochastic gradient descent, using Monte Carlo approximation for the gradients. This enables variatio…
Gradient descent recovers principal components of overparametrized asymmetric matrices without explicit regularization.
problem Asymmetric matrix factorization under overparametrization with minimal rank assumptions.
method Vanilla gradient descent with small random initialization and proper early stopping.
result Gradient descent produces the best low-rank approximation without explicit regularization.
Adapting functional gradients improves FGD's practicality and theoretical guarantees.
problem Implementing FGD in practice due to infinite-dimensional functional gradients.
method Adapting the representation of functional gradients.
result Establishes convergence to a stationary point for smooth losses and a global minimizer under smoothness + Polyak-Lojasiewicz condition.
Uniform diffusion approximation for SGD in non-convex settings.
problem Finite-time diffusion approximation for SGD.
method Establishing uniform-in-time diffusion approximation with strong convexity and mild conditions.
result Uniform-in-time diffusion approximation of SGD without convexity of each loss function.
LOSSGRAD automatically adjusts learning rates in neural networks.
problem Finding optimal learning rates in gradient descent.
method LOSSGRAD uses quadratic approximation to find locally optimal step-size.
result LOSSGRAD achieves comparable results to other methods while being insensitive to initial learning rate.
Deep neural networks struggle with numerical instability during training.
problem Numerical instability in gradient descent training of deep neural networks.
method Analysis of floating-point arithmetic and gradient descent in ReLU neural networks.
result It is highly unlikely for ReLU networks to maintain a superlinear number of affine pieces during training.
Paper improves confidence set construction for SGD using multiplier bootstrap.
problem Constructing accurate confidence sets for SGD.
method Multiplier bootstrap procedure for non-asymptotic validity.
result Derives approximation rates up to 1 / n 1/\sqrt{n} 1/ n for convex distance. Stochastic NGD approximates Bayesian posterior samples near local minima.
problem Approximating Bayesian uncertainty in model parameters near local minima.
method Develops minibatch natural gradient descent (NGD) and introduces stochastic NGD to preserve Bayesian properties.
result Minibatch NGD's stationary distribution approaches a Bayesian posterior near local minima with small learning rates.
In reinforcement learning, temporal difference (TD) is the most direct algorithm to learn the value function of a policy. For large or infinite state spaces, exact representations of the value function are usually not available, and it must be approximated by a function in some parametric family. However, with \emph{no…
Paper approximates risk measures using SGD with Langevin dynamics.
problem Approximating arbitrary law invariant risk measures.
method Stochastic Gradient Langevin Dynamics (SGD-Langevin) for general risk measures.
result Non-asymptotic convergence rates of the approximation algorithm.
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…
Stochastic gradient descent approximates Gaussian process posteriors efficiently.
problem Efficiently sampling from Gaussian process posteriors with limited computational resources.
method Developed stochastic gradient optimization objectives for sampling from Gaussian process posteriors.
result Stochastic gradient descent produces accurate predictive distributions, even in non-convergent cases.
Optimization algorithms that leverage gradient covariance information, such as variants of natural gradient descent (Amari, 1998), offer the prospect of yielding more effective descent directions. For models with many parameters, the covariance matrix they are based on becomes gigantic, making them inapplicable in thei…
Examines challenges and proposes new approaches in machine learning theory.
problem Challenges in machine learning as a function approximation and optimization.
method Mathematical analysis of gradient descent, fixed network limitations, and RNNs.
result New insights and mathematical approaches to improve machine learning.
This study explains why approximate NGD works well in wide neural networks.
problem Understanding why NGD with approximate Fisher information converges fast in wide neural networks.
method Analyzing asymptotic training dynamics in function space via the neural tangent kernel.
result NGD with approximate Fisher information achieves the same fast convergence as exact NGD under specific conditions.
The paper provides approximation guarantees for neural networks trained with gradient flow.
problem Approximating neural networks trained with gradient flow in continuous L 2 ( S d − 1 ) L_2(\mathbb{S}^{d-1}) L 2 ( S d − 1 ) -norm. method NTK argument for non-convex second but last layer, under-parametrized regime.
result Gradient flow convergence guarantees for neural networks under Sobolev smoothness assumptions.
Unified analysis of EG and OGDA for saddle point problems using proximal point method.
problem Solving saddle point problems in bilinear and strongly convex-strongly concave settings.
method Unified analysis as approximations of the proximal point method.
result Unified analysis of EG and OGDA for saddle point problems.
The paper analyzes the variance of different shuffling methods in stochastic gradient descent.
problem Understanding the variance of different shuffling methods in stochastic gradient descent.
method Power spectral density analysis to study the noise sequences of stochastic gradients.
result The stationary variances of iterates decrease in the order of SGD, SGD-RR, and SGD-SO.
Deep networks are mathematically equivalent to kernel machines learned by gradient descent.
problem Understanding the learned representations of deep learning models.
method Using gradient descent to learn deep networks, showing they are equivalent to kernel machines.
result Deep network weights are a superposition of training examples, revealing the learned function.
New Banach spaces for ReLU networks enable better function approximation and gradient dynamics analysis.
problem Function approximation and gradient dynamics in multi-layer ReLU networks.
method Developed Banach spaces for ReLU networks, defined new function representations, and analyzed gradient flow dynamics.
result Gradient flow dynamics of the new representation is the continuous analog of gradient descent for ReLU networks.
Meta-descent improves online prediction in non-stationary settings.
problem Non-stationary online prediction problems.
method Meta-gradient descent to adapt step-size parameters.
result Meta-descent methods outperform other approaches in non-stationary prediction.
Study Markov chain gradient descent in Hilbert spaces for quadratic loss.
problem Approximating optimal solutions for quadratic loss functions.
method Developed a Markov chain-based stochastic gradient algorithm in Hilbert spaces.
result Established probabilistic upper bounds on convergence.
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.
KSD Descent uses KSD to sample from a target distribution efficiently.
problem Sampling from complex target distributions efficiently.
method Wasserstein gradient flow of KSD, using L-BFGS optimization.
result KSD Descent can sample from a target distribution using a set of particles.
The paper interprets diffusion models as gradient descent and proposes a new sampler.
problem Improving the efficiency and quality of diffusion models.
method Interprets diffusion models as gradient descent and proposes a new sampler.
result The new sampler achieves state-of-the-art FID scores and generates high quality samples.
Second-order optimization methods such as natural gradient descent have the potential to speed up training of neural networks by correcting for the curvature of the loss function. Unfortunately, the exact natural gradient is impractical to compute for large models, and most approximations either require an expensive it…
Riemannian gradient descent escapes some spurious critical points on low-rank matrix manifold.
problem Spurious critical points on the boundary of low-rank matrix manifold.
method Riemannian gradient descent with dynamical low-rank approximation and rescaled gradient flow.
result Riemannian gradient descent escapes some spurious critical points on the boundary of the manifold.
Heavy-tailed distributions emerge in SGD's parameter evolution.
problem Understanding heavy-tailed distributions in SGD parameter evolution.
method Continuous diffusion approximation of SGD (homogenized SGD) analysis.
result Explicit upper and lower bounds on tail-index of homogenized SGD.
We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and the number of training examples. The time complexity of our algorithm to find an approximate local minimum is even faster than that of gradie…
A new stochastic algorithm approximates optimal distributions without requiring propagation of chaos.
problem Optimizing functionals over probability distributions using finite particle systems.
method Virtual particle stochastic approximation, viewed as a form of stochastic gradient descent in the Wasserstein space.
result The algorithm's output converges to the optimal distribution and produces i.i.d. samples.
This paper optimizes functions of probability measures using particle gradient descent for displacement convex functions.
problem Optimizing functions of probability measures with displacement convex properties.
method Particle gradient descent applied to displacement convex functions with theoretical guarantees.
result Finite number of particles and computations are sufficient to find optimal solutions for displacement convex functions.
Proposes a continuous flow model to understand and control instability in gradient descent for deep learning.
problem Understanding and controlling the instability of gradient descent in deep learning.
method Introduces the Principal Flow (PF), a continuous time flow that approximates gradient descent dynamics.
result The PF captures divergent and oscillatory behaviors of gradient descent, including escaping local minima and saddle points.
Improved learning bounds for corrupted data using thresholded gradient descent.
problem Learning from corrupted data with adversarial noise.
method Thresholded gradient descent for sigmoidal, leaky-ReLU, and ReLU activations.
result Improved approximation bounds for various activation functions.
New tools extend weak approximation of SGD algorithms to infinite time horizon.
problem Weak approximation of stochastic gradient descent algorithms in infinite time horizon.
method Backward error analysis of numerical stochastic differential equations and truncated formal power expansion.
result Characterization of asymptotic behavior of SGD algorithms for strongly convex functions.