Research map / Optimization / Implicit bias and generalization
Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes injecting alpha-stable heavy-tailed noise into SGD for one-hidden-layer mean-field networks, proving that trained weights become provably compressible (column-pruning) as width grows, with propagation-of-chaos and Euler discretization error bounds.
Problem
Obtaining neural network weights that are provably compressible after training; prior compressibility results for SGD rely on unverifiable tail and independence assumptions.
Approach
Perturb SGD iterates with i.i.d. alpha-stable heavy-tailed noise scaled by eta^{1/alpha}; in the mean-field limit the neuron weights become i.i.d. heavy-tailed (via propagation of chaos), so keeping only the largest-norm columns yields small relative error with high probability for any compression ratio.
Key results
- On ECG5000 with n=10K, alpha=1.75 Type-I noise reaches a 60.23% pruning ratio at 90.75% pruned test accuracy, versus 11.44% pruning and 93.53% accuracy for vanilla SGD.
- On MNIST (n=5K), alpha=1.9 doubles the pruning ratio of vanilla SGD (10.58% to 23.82%) with about 1% pruned test accuracy loss.
- Heavy-tailed noise models are reported to be more robust to pruning on CIFAR10 (FCN and VGG-style CNN) and CIFAR100 (4-hidden-layer FCN).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Type-I heavy-tailed noise to SGD (α=1.9) | SGD on ECG5000, n=2K · ECG5000 | pruning ratio: 11.43 \pm 0.04 -> 24.89\pm 9.89 | Helped |
| Add Type-I heavy-tailed noise to SGD (α=1.75) | SGD on ECG5000, n=10K · ECG5000 | pruning ratio: 11.44 \pm 0.02 -> 60.23\pm 17.85 | Helped |
| Decrease α from 1.9 to 1.75 with Type-I noise (ablation) | Heavy-tailed SGD on ECG5000 · ECG5000, n=10K | pruning ratio: 30.05\pm 8.12 -> 60.23\pm 17.85 | Helped |
| Use Type-II instead of Type-I noise (ablation) | Heavy-tailed SGD on ECG5000 · ECG5000, n=10K, α=1.75 | pruning ratio: 60.19 \pm 35.37 vs 60.23\pm 17.85 | No clear effect |
| Use Type-III instead of Type-I noise (ablation) | Heavy-tailed SGD on ECG5000 · ECG5000, n=10K | pruning ratio: 57.34 \pm 15.70 vs 60.23\pm 17.85; 45.24 \pm 24.32 vs 49.63\pm 6.17; 26.35 \pm 18.36 vs 30.05\pm 8.12 | Hurt |
| Add Type-I heavy-tailed noise to SGD (α=1.9) | SGD on MNIST, n=5K · MNIST | pruning ratio: 10.58 \pm 0.01 -> 23.82 \pm5.89 | Helped |
| Add Type-I heavy-tailed noise to SGD (α=1.75) | SGD on CIFAR10, n=5K · CIFAR10 | pruning ratio: 11.60 \pm 0.09 -> 49.67 \pm 2.30 | Helped |
| Add heavy-tailed noise to SGD | FCN on CIFAR10 · CIFAR10, pruning robustness | test accuracy after pruning | Helped |
| Add heavy-tailed noise to SGD | CNN on CIFAR10 · CIFAR10, pruning robustness | test accuracy after pruning | Helped |
| Add heavy-tailed noise to SGD | 4-layer FCN on CIFAR100 · CIFAR100, pruning robustness | test accuracy after pruning | Helped |
| Use Gaussian noise (α=2) instead of heavy-tailed noise (ablation) | SGD in the mean-field network setting · Compression | relative compression error | Hurt |
Surprising findings
- Gaussian (alpha=2) noise in the mean-field limit yields weights that are not compressible in the paper's sense, showing heavy tails are necessary.
- Type-II noise is not uniformly better than Type-I; Type-I gives the best overall compression-accuracy tradeoff in the reported experiments.
Limitations
- Theory covers only mean-field one-hidden-layer networks with fixed second layer and plain (gradient) descent rather than stochastic gradients.
- Compression guarantees hold only asymptotically in n and with small step size; experiments show test accuracy trade-offs with more compression.
- Extension to adaptive optimizers and more sophisticated architectures is left open.
Experimental setup
Datasets: ECG5000 MNIST CIFAR10 CIFAR100
Benchmarks: ECG5000 MNIST CIFAR10 CIFAR100
Metrics: train accuracy test accuracy pruning ratio relative test accuracy under pruning
Baselines: vanilla SGD (no noise)
Builds on: Simsekli et al. heavy-tailed SGD compressibility mean-field neural network analysis (Mei et al.) lottery ticket hypothesis VGG
Closest papers by meaning
- Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks (NeurIPS 2021 · similarity 0.95)
- The Heavy-Tail Phenomenon in SGD (ICML 2021 · similarity 0.89)
- Emergence of heavy tails in homogenized stochastic gradient descent (NeurIPS 2024 · similarity 0.89)
- A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks (ICML 2019 · similarity 0.88)
- High-dimensional Limit of SGD for Diagonal Linear Networks (NeurIPS 2026 · similarity 0.87)
- Benign Oscillation of Stochastic Gradient Descent with Large Learning Rate (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.