Heavy-tailed Streaming Statistical Estimation

Abstract

We consider the task of heavy-tailed statistical estimation given streaming $p$-dimensional samples. This could also be viewed as stochastic optimization under heavy-tailed distributions, with an additional $O(p)$ space complexity constraint. We design a clipped stochastic gradient descent algorithm and provide an improved analysis, under a more nuanced condition on the noise of the stochastic gradients, which we show is critical when analyzing stochastic optimization problems arising from general statistical estimation problems. Our results guarantee convergence not just in expectation but with exponential concentration, and moreover does so using $O(1)$ batch size. We provide consequences of our results for mean estimation and linear regression. Finally, we provide empirical corroboration of our results and algorithms via synthetic experiments for mean estimation and linear regression.

References in corpus (6)

• Large Batch Training of Convolutional Networks
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection
• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• A Unified Approach to Robust Mean Estimation
• High-Dimensional Robust Mean Estimation via Gradient Descent

Cited by in corpus (1)

• Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation