Loss minimization and parameter estimation with heavy tails

Abstract

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.

Final version as published in JMLR

References in corpus (4)

• Composite quantile regression and the oracle Model Selection Theory
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Geometric median and robust estimation in Banach spaces
• Empirical entropy, minimax regret and minimax risk

Cited by in corpus (27)

• Robust Aggregation for Federated Learning
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Geometric median and robust estimation in Banach spaces
• Simpler PAC-Bayesian Bounds for Hostile Data
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• Distributed High-dimensional Regression Under a Quantile Loss Function
• Active Regression via Linear-Sample Sparsification
• Learning with Non-Convex Truncated Losses by SGD
• Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs
• When OT meets MoM: Robust estimation of Wasserstein Distance
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• Distribution-Free Robust Linear Regression
• Robust descent using smoothed multiplicative noise
• From low probability to high confidence in stochastic convex optimization
• Outlier Robust Online Learning
• Convergence rates of least squares regression estimators with heavy-tailed errors
• Exponential Concentration for Geometric-Median-of-Means in Non-Positive Curvature Spaces
• Efficient learning with robust gradient descent
• Taming heavy-tailed features by shrinkage
• Generalization Bounds in the Presence of Outliers: a Median-of-Means Study
• Heavy-tailed Streaming Statistical Estimation
• Improved scalability under heavy tails, without strong convexity
• Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
• Do we need to estimate the variance in robust mean estimation?
• Realizable Learning is All You Need
• Posterior concentration and fast convergence rates for generalized Bayesian learning