Loss Minimization and Parameter Estimation with Heavy Tails

By Daniel J. Hsu, Sivan Sabato. 2013

200 citations recorded by the source corpus.

This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded low-order moments. We show that the technique can be used for approximate minimization of smooth and strongly convex losses, and specifically for least squares linear regression. For instance, our $d$-dimensional estimator requires just $\tilde{O}(d\log(1/\delta))$ random samples to obtain a constant factor approximation to the optimal least squares loss with probability $1-\delta$, without requiring the covariates or noise to be bounded or subgaussian. We provide further applications to sparse linear regression and low-rank covariance matrix estimation with similar allowances on the noise and covariate distributions. The core technique is a generalization of the median-of-means estimator to arbitrary metric spaces.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Robust Aggregation for Federated Learning (2019, methodology): “Robust median-of-means were introduced in [70], with follow ups in [39, 53, 60, 61, 67].”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “…et al. (2015), Nemirovskii et al. (1983), and has been applied to bandit and least square regression problems (Bubeck et al., 2013, Kogler and Traxler, 2016, Lugosi and Mendelson, 2016) as well as problems involving heavy-tailed distributions (Hsu and Sabato, 2016, Lugosi and Mendelson, 2017).”
Fast, Compact, and High Quality LSTM-RNN Based Statistical Parametric Speech Synthesizers for Mobile Devices (2016, methodology): “Using robust regression techniques such as linear regression with a heavy-tailed distribution [32] or minimum density power divergence estimator [33] can relax the effect of outliers.”
Geometric median and robust estimation in Banach spaces (2013, methodology): “A closely related independent recent work [18] applies original ideas of Nemirovski and Yudin to general convex loss minimization.”
Finite-sample Analysis of M-estimators using Self-concordance (2018, methodology): “These light-tailed assumptions can further be relaxed to fourth-moment assumption, using the generalized median-of-means estimator (see [21]).”
Robust estimation via robust gradient estimation (2018, methodology): “(a) Error versus number of iterations: in Figs 3(a) and 3(b) we plot the excess risk of various approaches against the number of iterations (for OLS, the lasso, ridge regression and the method of Hsu and Sabato (2016) we plot only the excess risk of the final iterate).”
Distributed Statistical Estimation and Rates of Convergence in Normal Approximation (2017, background): “This approach has been proposed and investigated by Minsker (2015) and Hsu and Sabato (2016). However, existing results for the median-based approach have several pitfalls related to the convergence rates, and in most cases known guarantees are suboptimal. In particular, these guarantees suggest tha”
Random Design Analysis of Ridge Regression (2011, unknown): “Indeed, the works of [3] and [13] propose estimators that require considerably weaker moment conditions on x and y to obtain optimal rates.”
Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries (2016, background): “An approach which often yields “dimension - free” bounds was proposed in [HS16] and [Min15] (using generalizations of the median in higher dimensions); however, to the best of our knowledge, results of these papers are still not sufficient to obtain deviation guarantees in the operator norm that we ”
Risk minimization by median-of-means tournaments (2016, background): “Note that for the special case of linear regression described above, Hsu and Sabato [19] achieve slightly (by a factor logarithmic in n ) weaker bounds than (1.3) under slightly stronger ((4 + ǫ )-th moment) assumptions.”
Convergence rates of least squares regression estimators with heavy-tailed errors (2017, background): “t on the errors, we refer the reader to [7]. It is worthwhile to note that the shortcomings of the LSE quantiﬁed here also rigorously justify the motivation of developing other robust procedures (cf. [4, 14, 15, 18, 19, 24, 35, 36, 45, 46, 47, 57]). Remark 9. Our Theorems 3 and 4 show that the momen”
Sub-Gaussian estimators of the mean of a random vector (2017, background): “…multivariate case by replacing the median by its natural multivariate extension, the so-called “ge-ometric (or spatial) median” (i.e., the point that minimizes the sum of the Euclidean distances to the sample means within each block) see Lerasle and Oliveira [14], Hsu and Sabato [9], Minsker [16].”
Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices (2019, background): “Risk bounds in probability are obtained, among others, by [5, 33, 34, 53, 49, 41].”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “This estimator was proposed byMinsker [65] and independently byHsu and Sabato [36] (see also Lerasle andOliveira [53]).”
Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible (2017, methodology): “The tail properties are guaranteed in the following lemma: Lemma 4 (Proposition 9 in [17]) .”