New framework limits SGD for multi-index models, addressing SQ framework shortcomings.
problem Limitations of SGD for multi-index models beyond SQ framework.
method Developed a new non-SQ framework to study SGD limitations for single-index and multi-index models.
result Applies to broad settings and architectures, including neural networks.
New insights into SGD and SGD-M in high dimensions.
problem Understanding and comparing SGD and SGD-M in high-dimensional settings.
method Developed high-dimensional scaling limits for SGD-M and online SGD, examining their dynamics and performance.
result SGD-M amplifies high-dimensional effects, potentially degrading performance compared to online SGD.
UD-SGD analysis shows efficient sampling by a few agents can outperform others.
problem Analyzing convergence speed and sampling strategies in UD-SGD.
method Asymptotic analysis of UD-SGD with various communication patterns and sampling strategies.
result Efficient sampling by a few agents can lead to better overall convergence.
Study SGD dynamics in high-dimensional models, revealing consistent behavior across different batch sizes and learning rates.
problem Understanding SGD dynamics in high-dimensional multi-index models.
method Asymptotic analysis of SGD, developing mean-field equations and Gaussian diffusion approximations.
result Consistent SGD dynamics across different batch sizes and learning rates, distinct from gradient flow and online SGD.
Derives effective continuous dynamics for adaptive SGD methods.
problem Analyzing noise in adaptive SGD methods.
method Stochastic modified equations framework and Malladi's scaling rules.
result Sampling-induced noise in SGD limits to independent Brownian motions.
Study on adversarial training dynamics in high dimensions using SGD.
problem Analyzing adversarial training of models in high-dimensional settings.
method Deriving deterministic equivalents for SGD iterates under Gaussian mixtures.
result No constant learning rate guarantees monotone descent in adversarial training.
Derives scaling limits and fluctuations for SGD in high dimensions.
problem Understanding SGD behavior in high-dimensional settings with varying noise levels.
method Interacting particle system approach, treating SGD iterates as such, with covariance structure considered.
result Precise three-step phase transition observed in SGD behavior: ballistic, diffusive, then random.
Analyzes SGD dynamics in two-layer networks, bridging different regimes.
problem Understanding SGD dynamics in high-dimensional and mean-field settings.
method Rigorous analysis via deterministic low-dimensional description of sufficient statistics.
result Infinite-width dynamics remains close to a low-dimensional subspace.
The paper analyzes SGD in high-dimensional networks, revealing new scaling limits.
problem Understanding SGD dynamics in high-dimensional networks.
method Analyzing the effective dynamics of SGD using recent work on the subject.
result A new correction term emerges at the critical scaling regime, changing the phase diagram.
Study on gradient clipping in SGD for high-dimensional problems.
problem Understanding and optimizing gradient clipping in high-dimensional machine learning models.
method Theoretical analysis of streaming SGD with gradient clipping in a least squares problem, focusing on large intrinsic dimensionality.
result Developed a deterministic equation to describe the loss evolution in clipped SGD, showing benefits under certain conditions.
This paper analyzes Local SGD for federated learning, achieving both statistical and communication efficiency.
problem Statistical estimation and inference in federated learning with decentralized data.
method Local SGD, a multi-round estimation procedure using intermittent communication.
result Local SGD achieves both statistical efficiency and communication efficiency.
New CLT for SGD in high-dimensional regression provides online inference.
problem Quantifying uncertainty in SGD for high-dimensional regression.
method Established a high-dimensional CLT for online SGD iterates.
result Developed an online approach for estimating variance in CLT.
Paper shows local SGD outperforms mini-batch SGD under certain conditions.
problem Proving local SGD's superiority in distributed learning with heterogeneous data.
method New lower and upper bounds for local SGD under first-order heterogeneity assumptions.
result Local SGD is min-max optimal under certain conditions, resolving understanding of distributed optimization.
High-dimensional SGD limits show surprising dynamics and phase transitions.
problem Understanding SGD in high dimensions and its scaling limits.
method Proving limit theorems for SGD trajectories in high dimensions, choosing summary statistics, initialization, and step-size.
result Critical scaling regime for step-size, new correction term, and complex diffusive limits.
Stochastic Gradient Descent (SGD) is widely used in machine learning problems to efficiently perform empirical risk minimization, yet, in practice, SGD is known to stall before reaching the actual minimizer of the empirical risk. SGD stalling has often been attributed to its sensitivity to the conditioning of the probl…
CSER improves SGD efficiency by resetting errors and partial synchronization.
problem Limited scalability of Distributed Stochastic Gradient Descent (SGD) due to communication bottlenecks.
method Introduces 'error reset' technique and partial synchronization for gradients and models.
result Proves convergence for smooth non-convex problems and accelerates distributed training significantly.
SGD with constant stepsize converges to a non-Gaussian limit near flat minima.
problem Behavior of SGD near flat minima with convex objectives.
method Analyzes SGD with Markovian noise and contractive driving chain.
result Invariant law concentrates on scale α 1 / m α^{1/m} α 1/ m and converges weakly to a non-Gaussian stationary distribution. Analysis of SGD for Gaussian mixture classification using dynamical mean-field theory.
problem Learning dynamics of SGD for a neural network classifying Gaussian mixture.
method Applying dynamical mean-field theory to track SGD dynamics in high dimensions.
result Reveals how SGD navigates the non-convex loss landscape.
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. Two new covariance estimators for ROOT-SGD improve statistical inference.
problem Uncertainty measurement for ROOT-SGD's normal distribution estimator.
method Developed two covariance estimators: plug-in and Hessian-free.
result Hessian-free estimator is asymptotically consistent and Hessian-free.
Local SGD outperforms conventional methods in LLM training.
problem Training large language models on distributed devices.
method Local SGD algorithm applied to distributed training.
result Local SGD achieves competitive results in LLM training.
Ringmaster ASGD improves Asynchronous SGD's efficiency under varying worker times.
problem Suboptimal performance of Asynchronous SGD under heterogeneous worker computation times.
method Ringmaster ASGD, a novel Asynchronous SGD method with optimal time complexity.
result Ringmaster ASGD achieves optimal time complexity under arbitrary worker heterogeneity.
Homogenized SGD explains SGD dynamics in high dimensions.
problem Understanding SGD dynamics in high-dimensional settings.
method Developed a homogenized SGD model to analyze high-dimensional SGD.
result Convergent high-dimensional SGD to homogenized SGD for quadratic statistics.
New framework analyzes SGD dynamics in large samples and dimensions.
problem Analyzing stochastic gradient descent in large-scale settings.
method Inspired by random matrix theory, new framework for fixed stepsize and finite sum settings.
result SGD dynamics become deterministic in the large sample and dimensional limit, governed by a Volterra integral equation.
SGD learns sparse parities near computational limits with discontinuous phase transitions.
problem Learning sparse parities in deep learning.
method Empirical and theoretical analysis of SGD on sparse parities.
result SGD makes progress on sparse parities via Fourier gap, not Langevin-like mechanism.
Anomalous diffusion in SGD reveals interactions between hyperparameters and Hessian.
problem Understanding the limiting dynamics of SGD in deep neural networks.
method Continuous-time model of SGD as an underdamped Langevin equation, derived for linear regression.
result Anomalous diffusion is explained by modified loss and probability currents in phase space.
Study reveals convergence properties of SGD with random learning rate.
problem Analyzing convergence of SGD with random learning rate in non-convex optimization.
method Introduced Poisson SGD with random learning rate and used stationary distribution analysis.
result Poisson SGD converges to a stationary distribution and finds global minima in non-convex optimization.
The paper analyzes SGD with dropout regularization in linear models, proving asymptotic properties and providing inference tools.
problem Analyzing the behavior of SGD with dropout regularization in linear models.
method Establishing geometric-moment contraction (GMC) and proving quenched central limit theorems (CLT).
result The existence of a unique stationary distribution and asymptotic normality results for SGD with dropout.
Paper proves CLT for quantile SGD with constant learning rate.
problem Quantile estimation via SGD with non-smooth, non-strongly convex loss.
method Viewed as a Markov chain, derived stationary distribution, analyzed MGF, proved CLT.
result Centered and standardized stationary distribution converges to Gaussian as η i g h t a r r o w 0 η
ightarrow0 η i g h t a r r o w 0 . HybridSGD improves SGD performance by balancing computation and communication.
problem Limited scalability and performance of SGD due to communication costs.
method 2D parallel SGD method (HybridSGD) that trades off between 1D s s s -step SGD and 1D Federated SGD (FedAvg). result HybridSGD achieves better convergence than FedAvg at similar processor scales and up to 121x speedup over FedAvg.
Untuned SGD converges but with an exponential dependence on smoothness, adaptive methods prevent this.
problem The exponential dependence on smoothness in untuned SGD's convergence rate.
method Untuned SGD with arbitrary stepsize η, adaptive methods like NSGD, AMSGrad, and AdaGrad.
result Adaptive methods prevent the exponential dependence on smoothness in SGD.
To reduce the long training time of large deep neural network (DNN) models, distributed synchronous stochastic gradient descent (S-SGD) is commonly used on a cluster of workers. However, the speedup brought by multiple workers is limited by the communication overhead. Two approaches, namely pipelining and gradient spar…
With the increase in the amount of data and the expansion of model scale, distributed parallel training becomes an important and successful technique to address the optimization challenges. Nevertheless, although distributed stochastic gradient descent (SGD) algorithms can achieve a linear iteration speedup, they are l…
New bounds for SGD in high dimensions improve inference efficiency.
problem Quantifying uncertainty in high-dimensional SGD.
method Established non-asymptotic Berry--Esseen bounds for online least-squares SGD.
result Gaussian Central Limit Theorem holds for t ≳ d 1 + δ t \gtrsim d^{1+δ} t ≳ d 1 + δ , extending dimensional scaling. The paper provides Gaussian approximations for decentralized Federated Learning.
problem Lack of asymptotic statistical guarantees for local SGD in Federated Learning.
method Two generalized Gaussian approximation results for local SGD trajectories.
result Valid multiplier bootstrap procedures and Gaussian bootstrap-based tests for detecting adversarial attacks.
Analyzes SGD dynamics in high-dimensional settings for GLMs and multi-index models.
problem Understanding SGD learning in high-dimensional settings for generalized linear models and multi-index models.
method Deterministic equivalent of SGD as ODEs and simplified SDE for analysis.
result Obtained learning rate thresholds and convergence guarantees for SGD.
New method for online inference using SGD with random scaling.
problem Efficient online inference for SGD parameters.
method Asymptotic pivotal statistics via random scaling.
result Robust and efficient online inference without resampling.
Mixed-precision CA-SGD for generalized linear models on GPUs
problem SGD communication bottleneck
method Mixed-precision CA-SGD
result Matches FP32 SGD loss within 0.5% on various problems
Study mini-batch SGD noise and its limits, proving complexity guarantees.
problem Analyzing the noise in mini-batch SGD and its impact on optimization.
method Examined the conditional covariance and diffusion limits of SGD under different sampling designs.
result Proved mean-square upper bounds and Fisher van Trees lower bounds for SGD, linking them to effective dimension and condition number.
Paper develops methods for statistical inference in SGD with infinite variance.
problem Challenges in statistical inference for SGD with infinite variance.
method Model-agnostic methodology based on weak convergence and subsampling calibration.
result Asymptotically valid confidence regions for SGD in both finite and infinite variance regimes.
Stochastic gradient descent (SGD) has been widely used in machine learning due to its computational efficiency and favorable generalization properties. Recently, it has been empirically demonstrated that the gradient noise in several deep learning settings admits a non-Gaussian, heavy-tailed behavior. This suggests tha…
Paper develops methods for statistical inference with SGD in nonconvex optimization.
problem Statistical inference for nonconvex optimization problems.
method Proposes two online inferential procedures combining SGD and bootstrap techniques.
result Establishes error convergence rates and asymptotically valid bootstrap confidence intervals.
Analyzes high-dimensional SGD dynamics using DMFT.
problem Understanding the high-dimensional behavior of multi-pass SGD with small batch sizes.
method Derives DMFT equations for high-dimensional SGD dynamics.
result Proves DMFT equations characterize the asymptotic distribution of SGF parameters.
Large-scale distributed training of neural networks is often limited by network bandwidth, wherein the communication time overwhelms the local computation time. Motivated by the success of sketching methods in sub-linear/streaming algorithms, we introduce Sketched SGD, an algorithm for carrying out distributed SGD by c…
Multi-layer neural networks are among the most powerful models in machine learning, yet the fundamental reasons for this success defy mathematical understanding. Learning a neural network requires to optimize a non-convex high-dimensional objective (risk function), a problem which is usually attacked using stochastic g…
Study shows how SGD in large neural networks behaves as neurons increase.
problem Understanding SGD behavior in overparameterized neural networks.
method Probabilistic approach to continuous-time dynamics of SGD, focusing on particle interactions.
result Particles' interactions asymptotically vanish, leading to a mean-field limit.
The paper analyzes two ISGD modes for statistical inference, deriving error bounds and confidence intervals.
problem Statistical inference with implicit SGD for smooth convex functions.
method Proximal Robbins-Monro (proxRM) and proximal Polyak-Ruppert (proxPR) procedures for ISGD.
result Derives non-asymptotic error bounds and confidence interval estimators for model parameters.
ROOT-SGD solves convex optimization problems with optimal nonasymptotic and near-optimal asymptotic performance.
problem Solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms.
method ROOT-SGD: Recursive One-Over-T SGD, averaging past stochastic gradients.
result Achieves state-of-the-art performance in both nonasymptotic and asymptotic senses.