Heavy Tail

Heavy-tailed distributions, characterized by infrequent but extreme values, are increasingly recognized as a significant feature in various machine learning contexts, particularly within the weight matrices of deep neural networks and the gradients during stochastic gradient descent (SGD) optimization. Current research focuses on understanding the emergence and impact of these heavy tails, investigating their relationship to generalization performance, algorithmic stability, and the effectiveness of privacy-preserving techniques like differentially private SGD (DPSGD). This research is crucial for improving the theoretical understanding of deep learning algorithms and developing more robust and efficient training methods, particularly in high-dimensional settings and when dealing with noisy or non-convex optimization problems.

Papers

June 17, 2024

ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data
Kevin Luo, Yufan Li, Pragya Sur
High Dimensional Rotation Invariance Heavy Tail Regularization Strength

June 7, 2024

Crafting Heavy-Tails in Weight Matrix Spectrum without Gradient Noise
Vignesh Kothapalli, Tianyu Pang, Shenyang Deng, Zongmin Liu, Yaoqing Yang
Deep Neural Network Two Layer Neural Network Weight Matrix Large Learning Rate Gradient Noise Full Batch Gradient Descent Heavy Tail

June 4, 2024

Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
Hilal Asi, Daogao Liu, Kevin Tian
Near Optimality Constructive Reduction Private Algorithm Heavy Tailed Private Gradient Heavy Tail Approximate Differential Privacy Lipschitz Continuity Assumption

May 27, 2024

Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tails
Haichao Sha, Yang Cao, Yong Liu, Yuncheng Wu, Ruixuan Liu, Hong Chen
Single CLIP Gradient Norm Heavy Tailed Private Stochastic Gradient Descent Thin Tail Clipped Stochastic Gradient Descent Heavy Tail High Probability Guarantee

March 20, 2024

Analysing heavy-tail properties of Stochastic Gradient Descent by means of Stochastic Recurrence Equations
Ewa Damek, Sebastian Mentemeier
Stochastic Gradient Descent Multiple Meaning Heavy Tail Stochastic Matrix

February 15, 2024

Negative impact of heavy-tailed uncertainty and error distributions on the reliability of calibration statistics for machine learning regression tasks
Pascal Pernot
Regression Task Prediction Uncertainty Error Distribution Heavy Tail Calibration Statistic

February 2, 2024

Emergence of heavy tails in homogenized stochastic gradient descent
Zhe Jiao, Martin Keller-Ressel
Gradient Descent Stochastic Gradient Descent Path Breaking Emergence Heavy Tailed Loss Minimization Heavy Tail

October 27, 2023

Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent
Krunoslav Lehman Pavasovic, Alain Durmus, Umut Simsekli
Stochastic Gradient Descent Action Free Offline Heavy Tailed Heavy Tail Offline Training

October 25, 2022

Parameter-free Regret in High Probability with Heavy Tails
Jiujia Zhang, Ashok Cutkosky
Online Convex Optimization High Probability Heavy Tail Free Regret

June 28, 2022

Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning
Dieqiao Feng, Carla Gomes, Bart Selman
Domain Specific Monte Carlo Tree Search Search Space Health Policy Recommendation NP Complete Planning Pipeline Efficient Search Heavy Tail Value Network

June 2, 2022

Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares
Anant Raj, Melih Barsbey, Mert Gürbüzbalaban, Lingjiong Zhu, Umut Şimşekli
Stochastic Gradient Descent Least Square Generalization Property Heavy Tailed Algorithmic Stability Heavy Tail

May 17, 2022

Deep neural networks with dependent weights: Gaussian Process mixture limit, heavy tails, sparsity and compressibility
Hoil Lee, Fadhel Ayed, Paul Jung, Juho Lee, Hongseok Yang, François Caron
Deep Neural Network Sparsity Increase Non Gaussian Random Weight Infinite Width Neural Network Heavy Tail Infinite Width

May 13, 2022

Heavy-Tail Phenomenon in Decentralized SGD
Mert Gurbuzbalaban, Yuanhan Hu, Umut Simsekli, Kun Yuan, Lingjiong Zhu
Stochastic Gradient Descent Stochastic Optimization Decentralized SGD Decentralized Stochastic Gradient Descent Heavy Tail Centralized Stochastic Gradient Descent

April 26, 2022

An Empirical Study of the Occurrence of Heavy-Tails in Training a ReLU Gate
Sayar Karmakar, Anirbit Mukherjee
Empirical Study Deep Learning Algorithm Stochastic Way Rare Event Hypothesis Class Heavy Tail

Heavy Tail

Papers

ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data

Crafting Heavy-Tails in Weight Matrix Spectrum without Gradient Noise

Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tails

Analysing heavy-tail properties of Stochastic Gradient Descent by means of Stochastic Recurrence Equations

Negative impact of heavy-tailed uncertainty and error distributions on the reliability of calibration statistics for machine learning regression tasks

Emergence of heavy tails in homogenized stochastic gradient descent

Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent

Parameter-free Regret in High Probability with Heavy Tails

Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning

Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squares

Deep neural networks with dependent weights: Gaussian Process mixture limit, heavy tails, sparsity and compressibility

Heavy-Tail Phenomenon in Decentralized SGD

An Empirical Study of the Occurrence of Heavy-Tails in Training a ReLU Gate