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.
INF-clip optimizes heavy-tailed MAB problems with improved performance.
problem Optimizing multi-armed bandit problems with heavy-tailed rewards.
method INF-clip algorithm for adversarial and stochastic heavy-tailed MAB settings.
result INF-clip is optimal for linear and non-linear heavy-tailed stochastic MAB problems.
Efficiently estimates sparse linear regression with heavy-tailed and outlier-contaminated data.
problem Estimating sparse linear regression coefficients with heavy-tailed and outlier-contaminated data.
method Efficient computation of estimators with sharp error bounds.
result Sharp error bounds for efficient estimators.
New algorithm reduces worst-case regret for heavy-tailed bandits.
problem Stochastic Multi-Armed Bandit problem with heavy-tailed rewards.
method Modified minimax policy MOSS with saturated empirical mean.
result Worst-case regret matching lower bound for heavy-tailed distributions.
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.
Study on error probability for classification of heavy-tailed renewal processes.
problem Error probability in classification of heavy-tailed renewal processes.
method Asymptotic expressions for Bhattacharyya bound on misclassification error probabilities.
result Obtained asymptotic expressions for misclassification error probabilities.
Study improves ERM for heavy-tailed data with dependent inputs.
problem Empirical Risk Minimization with dependent and heavy-tailed data.
method Extending risk bounds for ERM with heavy-tailed, dependent data.
result Established risk bounds for ERM with dependent and heavy-tailed data.
A new algorithm reduces regret in cooperative multi-agent bandits with heavy-tailed data.
problem Cooperative multi-agent bandits with heavy-tailed data.
method MP-UCB algorithm incorporating robust estimation with message-passing protocol.
result Optimal regret bounds for MP-UCB in various settings.
Sharp sample complexity for learning bounded L p L_p L p subsets.
problem Learning bounded subsets of L p L_p L p with p > 4 p > 4 p > 4 . method Heavy-tailed learning procedure.
result Sharp sample complexity estimate for any p > 4 p > 4 p > 4 . 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. TTF improves performance of normalizing flows for heavy-tailed distributions.
problem Improving performance of normalizing flows for heavy-tailed distributions.
method Uses a Gaussian base distribution and a final transformation layer to produce heavy tails.
result Experimental results show TTF outperforms current methods, especially in high-dimensional or heavy-tailed scenarios.
New bounds for heavy-tailed SDEs without info-theory terms.
problem Understanding generalization of heavy-tailed stochastic optimization.
method Fractional Fokker-Planck equation to estimate entropy flows.
result High-probability bounds with better dimension dependence.
New methods solve optimization problems with heavy-tailed noise, improving upon existing complexity bounds.
problem Optimization problems with heavy-tailed noise and weakly average smoothness.
method Normalized stochastic first-order methods with Polyak, multi-extrapolated, and recursive momentum.
result First-order oracle complexity results for finding approximate stochastic stationary points under heavy-tailed noise.
Paper solves robust convex problems with heavy-tailed noise.
problem Solving convex compositional problems with heavy-tailed noise.
method Sub-Gaussian confidence bounds under weak heavy-tailed noise assumptions, using boosting strategy.
result Achieves nearly optimal high probability convergence result.
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.
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.
In this paper, we consider the problem of linear regression with heavy-tailed distributions. Different from previous studies that use the squared loss to measure the performance, we choose the absolute loss, which is capable of estimating the conditional median. To address the challenge that both the input and output c…
Unified approach for robust and heavy-tailed mean estimation in high dimensions.
problem Estimating mean in high dimensions with adversarial corruption or heavy-tailed distributions.
method Unified meta-problem and duality theorem leading to Filter algorithm and QUE scheme.
result Unified and efficient algorithms for both robust and heavy-tailed mean estimation.
Markov chain decoders improve generative models' ability to produce heavy-tailed data.
problem Generative models struggle with heavy-tailed distributions.
method Replaced Gaussian decoder with Markov chain-based Phase-Type distributions.
result Significantly reduced tail Kolmogorov-Smirnov distance and extreme quantile error.
Study shows heavy-tailed distributions affect reliability of machine learning calibration statistics.
problem Reliability of calibration statistics for machine learning regression tasks is affected by heavy-tailed uncertainty and error distributions.
method Examined two calibration error estimation methods (CE and ZMS) and found ZMS to be less sensitive to heavy-tailed distributions.
result Heavy-tailed distributions make MSE and MV unreliable, but ZMS remains a reliable approach.
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.
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.
We survey some of the recent advances in mean estimation and regression function estimation. In particular, we describe sub-Gaussian mean estimators for possibly heavy-tailed data both in the univariate and multivariate settings. We focus on estimators based on median-of-means techniques but other methods such as the t…
Geometric approach solves maximum likelihood for Cauchy-like distributions.
problem Estimating center and scatter robustly from heavy-tailed data.
method Geodesic convexity and symmetry spaces of noncompact type.
result Efficient numerical solution for robust estimates of location and spread.
Study uses spectral risk for learning with heavy-tailed data.
problem Learning with heavy-tailed loss distributions.
method Spectral risk with Lipschitz-continuous density, derivative-free learning.
result Excess risk guarantees and improved performance over traditional methods.
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.
Heavy-tailed outliers are more resilient to robust estimation than adversarial ones.
problem Developing robust estimators for data with outliers.
method Analyzing the relationship between adversarial and heavy-tailed outlier models.
result Optimal estimators for heavy-tailed outliers are also optimal for adversarial settings, but not vice versa.
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.
Conditional Value-at-Risk (CVaR) is a widely used risk metric in applications such as finance. We derive concentration bounds for CVaR estimates, considering separately the cases of light-tailed and heavy-tailed distributions. In the light-tailed case, we use a classical CVaR estimator based on the empirical distributi…
Proposes resilience metrics for large blackout costs with logarithmic resilience.
problem Large variations in blackout costs make estimating risk impractical.
method Uses mean of log of large blackout costs, tail slope index, and frequency.
result Solves problems of heavy tail and large variations in blackout costs.
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.
Paper tackles robust batched bandits for heavy-tailed rewards.
problem Clinical trials and other applications with heavy-tailed rewards.
method Proposes robust batched bandit algorithms for heavy-tailed rewards in finite-arm and Lipschitz-continuous settings.
result Heavier-tailed rewards require fewer batches for near-optimal regret in the instance-independent regime and Lipschitz setting.
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.
Improved robust regression for heavy-tailed and contaminated data.
problem Linear regression with heavy-tailed and adversarially contaminated covariates and responses.
method Applying a filtering algorithm to covariates and then using Huber regression, least trimmed squares, or least absolute deviation estimators on the remaining data.
result Near-optimal error rates achieved for the Huber regression estimator.
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.
The paper investigates heavy-tailed behavior in offline SGD, showing it approximates power-law tails.
problem Understanding heavy-tailed behavior in offline (multi-pass) SGD with finite data.
method Proves nonasymptotic Wasserstein convergence bounds for offline SGD to online SGD.
result Offline SGD exhibits approximate power-law tails as the number of data points increases.
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 − δ . New algorithms achieve high-probability parameter-free regret in online convex optimization with heavy-tailed data.
problem Achieving high-probability parameter-free regret in online convex optimization with heavy-tailed data.
method Developed new regularization techniques to handle exponentially large iterates and heavy-tailed subgradients.
result Achieved regret bound of O ( ∥ u ∥ T 1 / p log ( 1 / δ ) ) O(\| \mathbf{u} \| T^{1/\mathfrak{p}} \log (1/δ)) O ( ∥ u ∥ T 1/ p log ( 1/ δ )) with high probability for subgradients with bounded p t h p^{th} p t h moments. Optimal algorithm for minimizing regret in heavy-tailed bandits.
problem Minimizing regret in stochastic multi-armed bandits with heavy-tailed distributions.
method Proposes an optimal algorithm under the assumption of uniformly bounded moments of order (1+ε).
result Matches the lower bound exactly in the first-order term and provides a finite-time bound on its regret.
Many real-world prediction tasks have outcome variables that have characteristic heavy-tail distributions. Examples include copies of books sold, auction prices of art pieces, demand for commodities in warehouses, etc. By learning heavy-tailed distributions, "big and rare" instances (e.g., the best-sellers) will have a…
Paper quantizes heavy-tailed data for near optimal estimation rates.
problem Estimating parameters from heavy-tailed data with quantization.
method Truncate and dither data, then uniformly quantize; achieves near minimax rates.
result Near optimal estimation rates achievable with quantized data.
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.
A regularized risk minimization procedure for regression function estimation is introduced that achieves near optimal accuracy and confidence under general conditions, including heavy-tailed predictor and response variables. The procedure is based on median-of-means tournaments, introduced by the authors in [8]. It is …
New MCMC methods map high-dimensional problems to spheres for better mixing.
problem Mixing issues in high-dimensional distributions, especially heavy-tailed ones.
method Stereographic Markov Chain Monte Carlo (MCMC) methods that map high-dimensional problems to spheres.
result Uniformly ergodic samplers for various distributions, including heavy-tailed ones, with faster convergence in higher dimensions.
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.
Unified framework for generating heavy-tailed distributions.
problem Extending SGMs to heavy-tailed targets.
method Combining early stopping with initialization for diffusion, and normalizing flows for generation.
result Unified generative framework with theoretical guarantees for heavy-tailed distributions.
Independent Component Analysis (ICA) is the problem of learning a square matrix A A A , given samples of X = A S X=AS X = A S , where S S S is a random vector with independent coordinates. Most existing algorithms are provably efficient only when each S i S_i S i has finite and moderately valued fourth moment. However, there are practical appli…
Self-regulating annealing improves sampling from heavy-tailed datasets.
problem Sampling from heavy-tailed distributions using diffusion models.
method Proposed an SDE-based sampler with a state-dependent diffusion coefficient.
result State dependence induces a self-regulating annealing mechanism.