Heavy-tailed Streaming Statistical Estimation
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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionStochastic OptimizationSimilar Papers 제목 키워드 기반
Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD
We consider the problem of high-dimensional heavy-tailed statistical estimation in the streaming setting, which is much harder than the traditional batch setting due to memory constraints. We cast this problem as stochas…
Heavy-tailed Contamination is Easier than Adversarial Contamination
A large body of work in the statistics and computer science communities dating back to Huber (Huber, 1960) has led to statistically and computationally efficient outlier-robust estimators. Two particular outlier models h…
Mean estimation and regression under heavy-tailed distributions--a survey
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 …
regressionSurveyDiffusion Models with Heavy-Tailed Targets: Score Estimation and Sampling Guarantees
Score-based diffusion models have become a powerful framework for generative modeling, with score estimation as a central statistical bottleneck. Existing guarantees for score estimation largely focus on light-tailed tar…
Density EstimationHigh Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization
In this paper, we propose a uniformly dithered 1-bit quantization scheme for high-dimensional statistical estimation. The scheme contains truncation, dithering, and quantization as typical steps. As canonical examples, t…
compressed sensingLow-Rank Matrix CompletionMatrix CompletionQuantization+1