Loss minimization and parameter estimation with heavy tails

Daniel Hsu; Sivan Sabato

Source-linked AI summary

Loss minimization and parameter estimation with heavy tails

Daniel Hsu, Sivan Sabato

arXiv:1307.1827v7Jul 7, 2013cs.LGstat.ML

TL;DR

Heavy-tailed data make high-probability estimation difficult when only low-order moments are bounded. The paper generalizes median-of-means through robust selection in metric spaces and applies it to loss minimization, regression, and covariance estimation. It obtains paper-level guarantees under heavy tails, including matching linear-regression rates up to logarithmic factors, but large constants restrict practical gains to very high-confidence settings.

Problem
Heavy-tailed distributions can make deviations from expected estimator behavior unreliable under bounded-moment assumptions, motivating stronger high-probability estimation guarantees.
Method
The paper splits data into subsamples, independently estimates from each, and selects a candidate through Robust Distance Approximation in a general metric space.
Results
Linear-regression convergence rates match min-max rates up to logarithmic factors, while applications extend to heavy-tailed Lasso noise and low-rank covariance estimation.
Takeaways & Limitations
The generalized median-of-means approach supports high-probability estimation across several heavy-tailed learning and covariance problems without requiring uniformly bounded or subgaussian data.
Takeaways & Limitations
Large constant factors currently restrict empirical improvements mainly to settings requiring very high confidence.

Abstract

from arXiv · show

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/δ))$ random samples to obtain a constant factor approximation to the optimal least squares loss with probability $1-δ$, 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.

1. Introduction

The paper targets reliable estimation under unbounded and heavy-tailed data, where low-order moments may exist but ordinary expected-loss guarantees give weak high-probability control. It generalizes median-of-means ideas to obtain high-probability guarantees for loss minimization and several estimation problems without boundedness or subgaussian assumptions.

Motivation: Heavy-tailed distributions can have only low-order finite moments, making expectation bounds insufficient for reassuring small-failure-probability guarantees.For a risk bound of ǫ, Markov’s inequality yields loss at most ǫ/δ with probability at least 1−δ.
Approach: The work generalizes a technique related to median-of-means estimation to control large deviations with high probability using bounded low-order moments.The method splits samples into groups, computes separate estimates, and selects one candidate so that noticeably better-than-fair candidate quality becomes exponentially reliable.
Applications: The technique applies to smooth and strongly convex loss minimization and yields least-squares regression bounds without bounded or subgaussian covariates or noise.In finite dimensions, a constant-factor approximation to optimal loss uses a sample size independent of the optimal loss value.
Approach: A general metric-space formulation selects a single estimator from candidate points using distances rather than relying on scalar averaging.The paper describes this as a generalization of the scalar median and extends the approach beyond directly observed distributions.
Applications: Further applications cover sparse linear regression under heavy-tailed noise, low-rank covariance approximation under heavy-tailed covariates, and median aggregation in prediction output spaces.The metric formulation is presented as more general than related median-of-means applications to empirical risks.

2. Overview of Main Results

The paper formalizes high-probability excess-loss estimation through repeated subsample-based estimators and robust selection in metric spaces. It applies this framework to convex losses, least-squares regression, sparse regression, and covariance estimation under heavy-tailed distributions, while noting practical costs from large constants.

Preliminaries: The objective is to obtain excess-loss guarantees that depend only logarithmically on 1/δ, rather than relying on weak expectation-to-tail conversions.The guarantee is defined for the confidence parameter δ supplied to the algorithm.
Robust Distance Approximation: Subsampled estimators are combined by Robust Distance Approximation, which returns one point close to any value that a sufficient fraction of candidates approach.The procedure is defined over a metric space and can use direct or noisy distance measurements.
Convex Loss Minimization: Smooth convex loss minimization achieves a constant approximation to optimal loss with sample complexity independent of the optimal loss value.The theorem assumes empirical strong convexity, logarithmic confidence scaling, and per-example smoothness.
Least Squares Linear Regression: Under bounded 4+ǫ moments of the covariates, linear regression uses n≥Cd log(1/δ) samples for a probability-at-least-1−δ guarantee.The regression results require only finite optimal squared loss and minimal covariate assumptions, rather than response-tail or response-range bounds.
Least Squares Linear Regression: The regression result is minimax optimal up to logarithmic factors, while subgaussian covariates yield an O(d log(1/δ)) sample requirement.The paper also gives analogous guarantees for regularized least squares.
Other Applications: The framework extends to Lasso with bounded-variance heavy-tailed noise and low-rank covariance approximation under bounded 4+ǫ covariate moments.These applications contrast with standard results that assume sub-Gaussian noise.
Limitations: Large constant factors currently limit empirical improvements mainly to settings requiring very high confidence, motivating future work on practicality.Suggested directions include greater sample reuse and overlapping groups.

3. The Core Techniques

The paper builds exponential-confidence estimation from median-of-means by selecting a representative candidate in a metric space, including when distances are estimated noisily.

3.1 Median-of-Means: The median-of-means estimator partitions data into groups, computes one mean per group, and returns their median.The number of groups scales as Θ(log(1/δ)) for confidence δ.
3.2 Generalization to Arbitrary Metric Spaces: The method generalizes median selection to arbitrary metric spaces by returning the candidate whose smallest majority-containing ball has minimum radius.This Robust Distance Approximation procedure has constant C0 = 3.
3.2 Generalization to Arbitrary Metric Spaces: If more than half of the independent candidates are within ε of the target, the selected candidate is within 3ε with probability at least 1−e−k/18.The confidence improves exponentially with the number of independent candidate queries.
3.3 Noisy Metrics: When the metric is not directly computable, a metric-estimation oracle supports a noisy-distance variant that returns a point within 9ε with probability at least 1−2e−k/648.This setting covers metrics depending on population quantities that must be estimated.

4. Minimizing Strongly Convex Losses

The paper applies robust candidate selection to approximately minimize smooth and strongly convex losses, using independent subsampled empirical minimizers. It obtains logarithmic dependence on confidence and applies the framework to heavy-tailed estimation settings.

4.2 Subsampled Empirical Loss Minimization: Subsampled empirical loss minimization partitions the sample into k non-overlapping groups and uses each group’s loss minimizer as an independent candidate.Independence satisfies the framework’s requirement for separately generated candidate solutions.
4.2 Subsampled Empirical Loss Minimization: Under the stated sample-size and smoothness conditions, Algorithm 2 achieves its loss-minimization guarantee with probability at least 1−δ using k = 18⌈log(1/δ)⌉.Each subsample must have size at least nα.
4.3 Smooth Losses: For smooth losses, a constant-factor approximation to the optimal loss requires max{nα, γβ¯β/α^2}·O(log(1/δ)) samples.The stated sample size has no dependence on the optimal loss L(w⋆).
4.4 Estimated Metrics: The framework also provides a noisy-metric variant with essentially the same guarantee when the metric-estimation oracle succeeds on sufficiently large i.i.d. samples.Algorithm 3 uses subsampled empirical minimization together with the assumed distance implementation.
4.5 Further Applications: The paper extends the approach to sparse linear regression with heavy-tailed noise and low-rank covariance approximation with heavy-tailed covariates.These applications retain bounded low-order-moment allowances rather than requiring bounded or subgaussian variables.

5. Least Squares Linear Regression

The paper applies a robust, metric-space generalization of median-of-means estimation to least squares regression, obtaining high-probability loss guarantees under bounded low-order moments. Its regression procedures achieve constant-factor approximations without requiring bounded or subgaussian covariates or noise.

Algorithm: Algorithm 4 forms k independently regularized regressors, estimates covariance matrices from the same samples, and selects one regressor using the estimated covariances.The confidence parameter is incorporated through k = C log(1/δ).
Least-squares guarantee: O(d log(1/δ)) samples suffice for the stated least-squares guarantee with probability at least 1 − δ under Condition 1.Condition 1 is a bounded low-order moment condition that applies to various heavy-tailed distributions.
Assumptions and comparison: The estimator uses bounded low-order moments of X and Y rather than bounded loss, bounded approximation error, or subgaussian noise assumptions.Prior empirical-loss analyses required almost-sure boundedness conditions that preclude multiplicative approximations when losses or approximation errors are unbounded.
Ordinary least squares: O(d log(d) log(1/δ)) samples suffice for a constant-factor approximation under bounded leverage, and O(d log(1/δ)) suffice under a subgaussian covariate assumption.The bounded-leverage rate is minimax optimal up to logarithmic factors.
Regularization and covariance control: The approach extends to regularized regression, with covariance concentration expressed through the comparison 2⟨a,(Σ + λ Id)a⟩X ≤ ⟨a,(ΣT + λ Id)a⟩X ≤ 2⟨a,(Σ + λ Id)a⟩X.This norm equivalence supports selecting a regressor using empirical covariance information.

6. Other Applications

The robust estimation technique is extended beyond ordinary least squares to sparse regression and low-rank covariance estimation. These applications retain high-probability guarantees while allowing heavy-tailed noise or covariates under stated design and moment conditions.

Sparse parameter estimation with Lasso: Algorithm 2 achieves Lasso’s fast convergence rates for sparse parameter estimation with heavy-tailed noise under a random subgaussian design.The result uses subsampled empirical minimization with the empirical Lasso loss.
Sparse parameter estimation with Lasso: The Lasso analysis assumes a sparse target, mean-zero finite-variance noise, and design regularity through a Restricted Eigenvalue condition.The sparsity level is s = |supp(w⋆)|, assumed small relative to d.
Sparse parameter estimation with Lasso: The fixed-design extension additionally requires the Restricted Eigenvalue condition and roughly O(1/(ks log d)) leverage scores for relevant submatrices.Under these conditions, the same subsampled empirical-loss implementation can be used.
Low-rank covariance approximation: Low-rank covariance estimation treats matrices as predictors under the spectral norm, while using Frobenius and trace norms to describe the approximation problem.The target is Σ = E[XX⊤], assumed to be approximately low rank.
Low-rank covariance approximation: An empirical covariance matrix from n′ samples approximates Σ within ε with probability at least 2/3 under the moment condition.Median aggregation then returns an estimate within 3ε with probability at least 1 − exp(−k/18).

7. A Comparison of Robust Distance Approximation Methods

The section compares set-based and space-based robust distance procedures across metric, Banach, and Hilbert spaces. It establishes approximation guarantees, matching lower bounds in several settings, and trade-offs involving computational cost and procedure choice.

Minimizing the Median Distance: The median-distance procedure achieves approximation factor 3 when minimizing over input points, and this bound is tight even in Hilbert spaces.Theorem 27 gives a real-line instance attaining distance 3ε.
Minimizing the Median Distance: A sample-based procedure improves the approximation factor to 2, and this factor is tight even in Hilbert spaces.The corresponding lower-bound construction attains distance 2ε on the real line.
Procedure types: Set-based procedures are simpler, while space-based procedures may require computationally intensive convex approximation.Space-based procedures can also face statistical challenges when distances are estimated from samples.
The Geometric Median: For geometric medians, set-based procedures have tight approximation factor 2 + 1/(2α) in general metric and Banach spaces.The lower bound applies to general k and extends to Banach spaces through metric embedding.
The Geometric Median: For space-based procedures, the geometric median has approximation factor 1 + 1/(2α), while general metric-space upper bounds are shown tight.The comparison states that median distance is generally superior, except that geometric median is superior in Hilbert spaces.

8. Predicting Without a Metric on Predictors

The paper replaces a metric-based candidate-selection step with median aggregation in prediction space. Under convex losses, this preserves a loss guarantee when most candidate predictors have low loss, while requiring many predictor evaluations per prediction.

Prediction without a metric: Median aggregation computes every candidate prediction for an input and returns their median, avoiding any metric between predictors.This directly generalizes the candidate-selection technique to scalar prediction outputs.
Prediction without a metric: Unlike usual regression bagging, this procedure aggregates predictions by their median rather than by averaging classifier outputs.The comparison concerns the aggregation rule, not the candidate-generation process.
Prediction without a metric: For convex link functions, the median prediction inherits a loss bound when a sufficient majority of candidate predictors have loss at most a threshold.The lemma assumes the loss decomposes through a convex link applied to the prediction and label.
Prediction without a metric: Each aggregate prediction requires many applications of the candidate predictors, creating a computational drawback.With unlimited unlabeled data, the paper suggests distilling aggregate predictions into a single predictor through a training set.

9. Conclusion

The conclusion presents generalized median-of-means estimation as a framework for heavy-tailed regression and covariance problems. Its applications include near-minimax linear regression, Lasso parameter estimation, and low-rank covariance approximation under stated heavy-tailed conditions.

Conclusion: The paper applies a generalized median-of-means approach to several estimation problems.The conclusion frames the applications as instances of one general estimation strategy.
Conclusion: Linear regression achieves convergence rates matching min-max rates up to logarithmic factors for heavy-tailed distributions.The conclusion states this rate guarantee at the paper level without specifying a particular estimator dimension or sample bound.
Conclusion: The paper identifies conditions for Lasso parameter estimation under heavy-tailed noise and low-rank covariance approximation under heavy-tailed distributions.These are presented as further applications beyond the main linear-regression result.

Appendix A. Proof of Theorem 25

The proof derives a structural constraint on the estimation error and combines it with a dual-norm bound. It then obtains coordinate-wise consequences for the largest entries and their complement.

Proof of Theorem 25: The proof uses the minimizer definition to establish an initial inequality for the estimation error.The displayed derivation begins from the fact that the estimator is defined as a minimizer.
Proof of Theorem 25: Hölder’s inequality bounds the cross term by the infinity norm of ε^⊤Ψ times the l1 norm of the estimator error.The passage gives the bound 2ε^⊤Ψ(ŵ − w⋆) ≤ λ∥ŵ − w⋆∥1.
Proof of Theorem 25: The derivation places the estimator error in the cone E_s, after which δ denotes the difference between the estimator and the target.This reparameterizes the proof around δ = ŵ − w.
Proof of Theorem 25: For δ in E_s, the l1 norm outside the largest s coordinates is at most three times the l1 norm inside them.The same step also bounds the complement’s infinity norm by the inside l1 norm divided by s.