New algorithms reduce regret in online convex optimization with heavy-tailed gradients.
problem Challenges in online convex optimization with heavy-tailed gradients.
method Examined and analyzed old algorithms for online convex optimization in the heavy-tailed setting.
result Established new regret bounds for classical methods without algorithmic modification.
Paper examines the structure of stochastic gradients in deep learning.
problem Exploring the structure and heavy tails of stochastic gradients in deep learning.
method Conducted formal statistical tests on stochastic gradients and gradient noise.
result Stochastic gradients and gradient noise do not exhibit power-law heavy tails, but their covariance spectra do.
Privacy-preserving SGD with heavy-tailed noise achieves differential privacy guarantees.
problem Privacy preservation in noisy SGD with heavy-tailed noise.
method Differential privacy guarantees for SGD with heavy-tailed noise.
result SGD with heavy-tailed perturbations achieves ( 0 , O ( 1 / n ) ) (0, O(1/n)) ( 0 , O ( 1/ n )) -DP. Stochastic gradient methods can converge in expectation under heavy-tailed noise.
problem Convergence of stochastic gradient methods under heavy-tailed noise.
method Comprehensive study of stochastic optimization under heavy-tailed noise for e x t s f S G D extsf{SGD} e x t s f S G D , e x t s f S M D extsf{SMD} e x t s f S M D , e x t s f A S M D extsf{ASMD} e x t s f A S M D , e x t s f S G D M extsf{SGDM} e x t s f S G D M in convex and nonconvex optimization. result Established in-expectation convergence results for various stochastic gradient methods.
A scalable method for heavy-tailed gradients using cheap stochastic sub-processes.
problem Scalability issues with robust gradient descent under heavy-tailed gradients.
method Cheap stochastic sub-processes for a single pass over partitioned data.
result Improved scalability and robustness to perturbations.
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.
Paper explores whether gradient normalization can replace clipping for SGD in heavy-tailed noise.
problem Ensuring convergence of SGD in heavy-tailed noise.
method Revisits gradient clipping and normalization, proving their sufficiency and effectiveness.
result Gradient normalization alone is sufficient for nonconvex SGD convergence under smoothness assumptions.
Improved scalable machine learning under heavy-tailed data.
problem Machine learning scalability under heavy-tailed data without strong convexity.
method Simple robust validation sub-routine to boost confidence in gradient-based sub-processes.
result Substantial improvement in dimension dependence without strong convexity.
PPO's gradients are heavy-tailed, affecting learning; a robust estimator improves performance.
problem Heavy-tailedness of PPO gradients causing learning issues.
method Characterized heavy-tailed gradients, identified likelihood ratios and advantages as sources, proposed GMOM as a robust estimator.
result GMOM improves PPO performance without clipping tricks.
Truncated SGD with heavy-tailed noise eliminates sharp local minima.
problem Avoiding sharp local minima in deep learning models.
method Truncated SGD with heavy-tailed gradient noise.
result Truncated SGD can eliminate sharp local minima entirely from its training trajectory.
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.
Is AdamW effective under heavy-tailed noise?
problem Stochastic gradient noise in LLM pretraining is typically heavy-tailed.
method Formulate as an open problem, prove a positive weighted-metric benchmark, and give a corridor lower-bound mechanism.
result No rigorous convergence theory for AdamW established in heavy-tailed regime.
New algorithm improves heavy-tailed statistical estimation in streaming data.
problem Heavy-tailed statistical estimation in streaming data.
method Clipped stochastic gradient descent algorithm with improved analysis.
result Guarantees exponential concentration with O ( 1 ) O(1) O ( 1 ) batch size for mean estimation and linear regression. Work on SGDm under heavy-tailed noise, revealing its generalization properties.
problem Understanding generalization of SGDm under heavy-tailed noise.
method Analysis of continuous-time limit (SDE) and discrete-time SGDm, establishing generalization bounds.
result SGDm can have worse generalization in the presence of heavy-tailed noise for quadratic loss functions.
New method makes reinforcement learning robust to heavy-tailed rewards.
problem Heavy-tailed rewards cause statistical outliers in reinforcement learning.
method Dynamic gradient clipping in TD learning and NAC.
result Provably robust TD and NAC achieve optimal sample complexities.
New RDP guarantees for heavy-tailed SDEs and SGD.
problem Characterizing differential privacy for heavy-tailed noise in learning algorithms.
method Rényi flow computations and fractional Poincaré inequalities.
result First RDP guarantees for heavy-tailed SDEs with weaker dependence on dimension.
New algorithm finds critical points in non-convex optimization with heavy-tailed gradients.
problem Non-convex stochastic optimization with heavy-tailed gradient estimates.
method Gradient clipping, momentum, and normalized gradient descent.
result High-probability convergence to critical points with best-known rates.
Study on SA with heavy-tailed and LRD noise, establishing finite-time bounds.
problem Analyzing stochastic approximation under heavy-tailed and LRD noise.
method Noise-averaging argument to regularize impact of non-classical noise.
result Established first finite-time moment bounds for SA under heavy-tailed and LRD noise.
New method targets deep learning optima with heavy-tailed noise.
problem Heavy-tailed gradient noise biases SGDm optima.
method Fractional Underdamped Langevin Dynamics (FULD) for heavy-tailed noise.
result FULD targets Gibbs distribution matching optima of cost function.
Adam outperforms gradient descent on language models due to handling heavy-tailed class imbalance.
problem Heavy-tailed class imbalance in language tasks.
method Comparing Adam and gradient descent on various architectures and data types, focusing on the impact of class imbalance.
result Class imbalance causes slow convergence for gradient descent, while Adam and sign-based methods are less affected.
New method improves convergence of SGD for heavy-tailed noise.
problem Heavy-tailed noise in machine learning applications.
method Normalized SGD (NSGD) to handle heavy-tailed noise.
result Improved sample complexity and high-probability convergence.
A scalable method for heavy-tailed data using robust aggregation.
problem Scalability issues with robust gradient descent under heavy-tailed data.
method Robustly choosing a strong candidate from parallel sub-processes.
result Improved scalability with robustness to perturbations.
Researchers study heavy-tail properties of SGD using stochastic recurrence equations.
problem Analyzing heavy-tail properties of Stochastic Gradient Descent (SGD).
method Modeling SGD iterations as multivariate affine stochastic recursions and applying the theory of irreducible-proximal (i-p) matrices.
result Extended results of Gürbüzbalaban et al. (2020) by using the theory of i-p matrices.
New approach achieves optimal rates for differentially private stochastic convex optimization with heavy-tailed gradients.
problem Differentially private stochastic convex optimization with heavy-tailed gradients.
method Reduction-based approach to achieve optimal rates.
result Achieved optimal rates up to logarithmic factors, nearly matching a lower bound.
New learning algorithm for heavy-tailed data using CVaR.
problem Learning with potentially heavy-tailed losses.
method Estimator of CVaR for heavy-tailed data, robust learning algorithm.
result High-probability excess CVaR bounds and empirical tests.
New theory explains why normalization is preferred in SGD under heavy-tailed noise.
problem Understanding why normalization is preferred in stochastic gradient descent (SGD) under heavy-tailed noise.
method Developed a worst-case complexity theory for stochastically preconditioned SGD and its variants.
result Normalization guarantees convergence at optimal rates, while clipping may fail in the worst case.
New convergence rates for SGD under heavy-tailed noise with infinite variance.
problem Convergence analysis of SGD under heavy-tailed noise with infinite variance.
method Identifying a condition on the Hessian and providing a convergence rate for the distance to the global optimum.
result SGD can converge to the global optimum under heavy-tailed noise with infinite variance.
Studied how heavy-tailed behavior affects SGD's generalization in quadratic optimization.
problem Link between heavy-tailed behavior and generalization in SGD.
method Used heavy-tailed stochastic differential equation and proved stability bounds.
result Stability of SGD depends on the loss function's tail behavior.
New algorithm robustly optimizes data streams with heavy-tailed or infinite variance samples.
problem Optimizing data streams with heavy-tailed or infinite variance samples.
method Gradient quantile clipping for SGD, leveraging Markov chain connections.
result Algorithm converges to a concentrated distribution with high probability bounds.
Improved Clipped-SGD achieves near-optimal heavy-tailed statistical estimation in streaming settings.
problem High-dimensional heavy-tailed statistical estimation in streaming with memory constraints.
method Stochastic convex optimization with Clipped-SGD, proving near-optimal sub-Gaussian statistical rates.
result Clipped-SGD achieves an error of T r ( Σ ) + T r ( Σ ) ∥ Σ ∥ 2 log ( log ( T ) δ ) T \sqrt{\frac{\mathsf{Tr}(Σ)+\sqrt{\mathsf{Tr}(Σ)\|Σ\|_2}\log(\frac{\log(T)}δ)}{T}} T Tr ( Σ ) + Tr ( Σ ) ∥Σ ∥ 2 l o g ( δ l o g ( T ) ) with probability 1 − δ 1-δ 1 − δ . Investigates spectral properties of neural networks, showing invariance under certain conditions.
problem Understanding the spectral evolution and invariance in linear-width neural networks.
method Empirical and theoretical analysis of spectra of weight matrices in high-dimensional settings.
result Spectra of weight matrices are invariant under certain training conditions, with implications for feature learning.
Optimizes privacy-preserving optimization for heavy-tailed data.
problem Privacy-preserving optimization with heavy-tailed gradients.
method Pure ε-differential privacy framework for Lipschitz extensions.
result Minimax optimal excess-risk rate for pure ε-DP heavy-tailed SCO.
Optimized method tackles convex optimization with heavy-tailed noise.
problem Convex optimization problems with noisy gradients.
method Vanilla stochastic proximal subgradient method without gradient clipping or normalization.
result Achieves optimal complexity for various convex optimization types under heavy-tailed noise.
This paper analyzes bias-variance trade-off for clipped SFOMs, improving complexity guarantees for heavy-tailed noise.
problem Improving complexity guarantees for stochastic optimization methods with heavy-tailed noise.
method Novel analysis of bias-variance trade-off in gradient clipping for clipped SFOMs.
result Improved complexity guarantees for clipped SFOMs across various tail indices, including infinite mean noise.
Accelerated optimization methods improve robustness and privacy in estimation.
problem Improving robustness and privacy in estimation methods.
method Accelerated gradient methods based on Frank-Wolfe and projected gradient descent, with tailored learning rates and Nesterov's momentum.
result Reduction in iteration complexity, leading to stronger statistical guarantees.
GNIs induce asymmetric heavy-tailed noise in SGD, affecting network performance.
problem The effect of Gaussian noise injections on SGD dynamics and network performance.
method Developed a Langevin-like SDE driven by asymmetric heavy-tailed noise to model the modified SGD dynamics.
result GNIs induce an implicit bias that varies with noise heaviness and asymmetry, affecting network performance.
We consider the problem of sparsity-constrained M M M -estimation when both explanatory and response variables have heavy tails (bounded 4-th moments), or a fraction of arbitrary corruptions. We focus on the k k k -sparse, high-dimensional regime where the number of variables d d d and the sample size n n n are related through $…
Recently, the study of heavy-tailed noises in first-order nonconvex stochastic optimization has gotten a lot of attention since it was recognized as a more realistic condition as suggested by many empirical observations. Specifically, the stochastic noise (the difference between the stochastic and true gradient) is con…
Gradient descent with chaotic perturbations improves generalization.
problem Improving generalization of gradient descent.
method Introducing chaotic perturbations to gradient descent to achieve improved generalization.
result Gradient descent with chaotic perturbations converges to a heavy-tailed SDE, leading to improved generalization.
New method approximates CVaR with less data for heavy-tailed risks.
problem Lack of data for accurate CVaR approximation in heavy-tailed distributions.
method Importance sampling based extrapolation for heavy-tailed distributions.
result Statistically consistent approximations with reduced data requirements.
New framework controls generalization for heavy-tailed data in RLHF and SGLD.
problem Heavy-tailed data in modern learning pipelines.
method Tail-dependent information-theoretic framework for sub-Weibull data.
result Sharp generalization bounds for heavy-tailed data.
New bounds link SGD's generalization to heavy tails without topological assumptions.
problem Linking SGD's generalization error to heavy tails without additional assumptions.
method Developed Wasserstein stability bounds for heavy-tailed SDEs and their discretizations, converting to generalization bounds.
result Generalization bounds for a broader class of objective functions, including non-convex functions, without topological assumptions.
Improved privacy-preserving methods for convex optimization with heavy-tailed data.
problem Privacy-preserving optimization of convex functions with heavy-tailed data.
method Developed algorithms for private mean estimation and convex optimization under concentrated differential privacy constraints.
result Achieved improved upper bounds on excess population risk for convex and strongly convex loss functions.
The paper explores how benign overfitting occurs in heavy-tailed input distributions.
problem Understanding overfitting in heavy-tailed input distributions.
method Analysis of maximum margin classifiers on unregularized logistic loss with gradient descent.
result Linear classifiers trained under certain conditions can asymptotically achieve the noise level as misclassification error.
Heavy-tailed regularization improves deep neural network performance.
problem Improving generalization of deep neural networks.
method Introducing Heavy-Tailed Regularization, using differentiable penalty terms and Bayesian statistics.
result Heavy-tailed regularization outperforms conventional regularization techniques.
Improved analysis for clipped gradient methods in nonsmooth convex optimization under heavy-tailed noise.
problem Optimization under heavy-tailed noise in nonsmooth convex problems.
method Refined analysis of Clipped Stochastic Gradient Descent (Clipped SGD) with new rates and improved utilization of Freedman's inequality.
result New rates O ( σ l d m e f f − 1 / 2 p ln 1 − 1 / p ( 1 / δ ) T 1 / p − 1 ) {\cal O}(σ_{\frak l}d_{
m eff}^{-1/2{\frak p}}\ln^{1-1/{\frak p}}(1/δ)T^{1/{\frak p}-1}) O ( σ l d m e f f − 1/2 p ln 1 − 1/ p ( 1/ δ ) T 1/ p − 1 ) and O ( σ l 2 d m e f f − 1 / p ln 2 − 2 / p ( 1 / δ ) T 2 / p − 2 ) {\cal O}(σ_{\frak l}^2d_{
m eff}^{-1/{\frak p}}\ln^{2-2/{\frak p}}(1/δ)T^{2/{\frak p}-2}) O ( σ l 2 d m e f f − 1/ p ln 2 − 2/ p ( 1/ δ ) T 2/ p − 2 ) for nonsmooth convex and strongly convex problems, respectively. RS-NSGD improves SGD convergence for heavy-tailed noise.
problem Nonconvex optimization with heavy-tailed noise.
method Integrates direction normalization into subspace updates.
result Achieves better oracle complexity than full-dimensional normalized SGD.
New algorithm guarantees performance on noisy data.
problem Learning with noisy data and heavy-tailed distributions.
method Anytime online-to-batch conversion for smooth objectives.
result Stochastic gradient-based algorithm with sub-Gaussian error bounds.