PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Estimation via Robust Gradient Estimation

Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, Pradeep Ravikumar

arXiv:1802.06485v2stat.MLcs.AIcs.LG

TL;DR

The paper asks how to obtain robust risk-minimization estimators when data contain arbitrary outliers or heavy tails and classical methods rely on restrictive assumptions. It robustifies projected gradient descent by robustly estimating population-risk gradients, and reports a general, computationally tractable framework with guarantees for several canonical models and robustness settings. The discussion identifies gradient-estimation quality and contamination limits as important scope boundaries.

  • Problem

    Classical empirical risk minimization can be unreliable with outliers, while standard analyses often assume clean data and well-controlled tails.

  • Method

    The paper robustifies projected gradient descent by replacing ordinary gradient updates with robust estimates of population-risk gradients, viewed as multivariate means.

  • Results

    The resulting estimators provide robustness guarantees for linear regression, logistic regression, and exponential-family models under Huber contamination and heavy-tailed settings, with strong empirical performance.

  • Takeaways & Limitations

    Robust gradient estimation offers a broadly applicable and computationally tractable alternative to robustifying the risk objective directly.

  • Takeaways & Limitations

    Guarantees depend on gradient-estimation quality and allowable contamination, and the approach can fail above an initialization-dependent contamination bound.

Abstract

from arXiv · show

We provide a new computationally-efficient class of estimators for risk minimization. We show that these estimators are robust for general statistical models: in the classical Huber epsilon-contamination model and in heavy-tailed settings. Our workhorse is a novel robust variant of gradient descent, and we provide conditions under which our gradient descent variant provides accurate estimators in a general convex risk minimization problem. We provide specific consequences of our theory for linear regression, logistic regression and for estimation of the canonical parameters in an exponential family. These results provide some of the first computationally tractable and provably robust estimators for these canonical statistical models. Finally, we study the empirical performance of our proposed methods on synthetic and real datasets, and find that our methods convincingly outperform a variety of baselines.

1 Introduction

The paper addresses robust estimation when classical guarantees rely on unrealistic clean-data and tail assumptions. It introduces computationally tractable robust gradient-based estimators with guarantees across statistical models and robustness settings, supported by empirical studies.

  • Motivation: Classical statistical guarantees often depend on strong model assumptions and fail under arbitrary outliers or other deviations.The paper motivates robust procedures because such assumptions are rarely met in practice.
  • Approach: The proposed estimators robustify projected gradient descent by estimating population-risk gradients robustly rather than defining a robust objective.The framework treats the population-risk gradient as a multivariate mean and uses robust mean estimation methods.
  • Robustness settings: The framework targets both Huber ǫ-contamination, which permits arbitrary outliers, and heavy-tailed distributions under weak moment assumptions.The paper presents these as two canonical robustness settings, with applications including financial and biological data.
  • Empirical investigations: Experiments on real and simulated data compare the estimators with competitive baselines and report strong performance across settings and metrics.The paper also provides guidelines for tuning parameter selection.
  • Statistical guarantees: Rigorous guarantees cover linear regression, logistic regression, and exponential-family models, based on gradient-descent stability with biased or inaccurate gradient estimates.The theory combines stability of projected gradient descent with bounds on the proposed gradient estimators.
  • Implications: The approach aims to combine the broad applicability of ERM or M-estimators with computational practicality and strong robustness guarantees.Related work includes computationally intensive robust methods for some specialized problems.

2 Background and Problem Setup

The paper frames statistical estimation as convex population-risk minimization from samples, then motivates robustness because ERM relies on assumptions that fail under outliers and heavy tails. It introduces Huber contamination and heavy-tailed settings, alongside linear, logistic, and exponential-family examples.

  • Risk Minimization: Risk minimization estimates θ∗, the population-risk minimizer, from n samples using a differentiable loss over a convex parameter set.Convexity supports tractable minimization, while strong convexity and smoothness provide identifiability and regularity.
  • Illustrative Examples: The risk-minimization framework covers linear regression, logistic regression, and canonical-parameter estimation in exponential-family models.These examples impose model-specific conditions, including bounded parameter spaces for logistic regression and Hessian bounds for exponential families.
  • Empirical Risk Minimization: ERM substitutes empirical risk for population risk, but outliers can distort sample means and produce sub-optimal estimates.Robust M-estimators address this by replacing the loss with a robust counterpart, though such estimators are often computationally intractable.
  • Projected Gradient Descent: Projected gradient descent is a standard ERM solver, yet ordinary gradient descent is not robust to deviations for general convex losses.The paper instead motivates robustifying the gradient updates used to optimize population risk.
  • Robustness Settings: The framework studies Huber’s ǫ-contamination and heavy-tailed models, where the latter assumes only finite second moments for gradient distributions.In heavy-tailed settings, empirical risk need not be uniformly close to population risk, so classical analyses fail.

3 Robust Gradient Descent via Gradient Estimation

The paper embeds robust gradient estimators within projected gradient descent, reducing gradient estimation to robust multivariate mean estimation. The resulting framework is computationally practical, theoretically analyzable, and instantiated for contamination and heavy-tailed settings.

  • Gradient Estimation: The population-risk gradient is a multivariate mean, so robust gradient estimation reduces to robust mean estimation.The framework then studies gradient accuracy and the stability of descent under estimation error.
  • Guarantees: The framework provides sufficient conditions under which inaccurate gradient estimates still yield accurate risk-minimization estimates.Its computational and statistical consequences include practical algorithms and robustness guarantees for biased, inexact iterates.
  • Robust Gradient Descent: The method replaces the population-risk gradient with a robust gradient estimator and performs projected gradient descent using iterative updates.For theoretical analysis, each iteration uses a fresh sample batch to avoid complex statistical dependencies.
  • Practical Considerations: Sample-splitting is used for theoretical convenience and may be removable through more complex uniform arguments.The paper also discusses tuning challenges because corruption and confidence parameters are unknown and standard validation is unreliable with outliers.
  • Huber Contamination: The Huber gradient estimator uses truncation and recursive SVD to separate a clean subspace from a potentially contaminated subspace.It applies a sample mean in the clean subspace and recurses on the other subspace, with a non-asymptotic analysis.
  • Heavy Tails: The heavy-tailed gradient estimator uses Gmom, which partitions samples into blocks and aggregates block means through a median-of-means procedure.The estimator is based on robust mean-estimation methods designed for weak moment assumptions.

4 Experiments

Experiments evaluate the proposed robust gradient-descent estimators on contaminated linear and logistic regression, face reconstruction, and heavy-tailed linear regression. Across these settings, the method generally degrades gracefully with contamination and outperforms the reported baselines.

  • Synthetic Experiments: Linear Regression: The proposed linear-regression estimator maintains error close to 0.1, roughly matching the corruption level, under the simulated contamination setting.The experiment uses ε = 0.1 and scales sample size with dimension to keep uncontaminated minimax error near 0.001.
  • Synthetic Experiments: Linear Regression: The linear-regression experiment evaluates parameter error under Huber contamination, using OLS, TORRENT, Huber-loss M-estimation, RANSAC, and a plugin estimator as baselines.The metric is the ℓ2 parameter error, with contamination affecting both covariates and responses.
  • Synthetic Experiments: Linear Regression: As dimension p increases, the proposed algorithm avoids the poor error scaling observed for the other estimators, while its parameter error grows linearly with contamination ε.TournamentGD has roughly the same performance as OracleGD, and its final error does not scale with p.
  • Synthetic Experiments: Logistic Regression: The logistic-regression MLE reaches 0/1 error close to 1 as dimension increases, whereas the linear SVM flips labels for roughly half the dataset.Both baselines perform poorly with increasing dimension in the reported experiment.
  • Synthetic Experiments: Logistic Regression: In logistic regression, the proposed estimator's 0/1 error degrades gracefully and grows linearly with ε, while its gradient-descent iterates converge linearly.The comparison includes logistic-regression MLE and a linear SVM.
  • Robust Face Reconstruction: For heavily occluded Yale face images, the proposed gradient-descent method achieves the best mean RMSE and usually reconstructs images closer to the unoccluded originals.The setup uses 20 eigenfaces and randomly places ten 30 × 30 occlusion blocks per test image.
  • Synthetic Experiments: Simple Linear Regression: In heavy-tailed linear regression, RobustGD has lower parameter error after convergence and remains better than other baselines even when n is 12 times p.Its relative improvement in excess risk decreases as the Pareto moment bound increases and the tails become lighter.

5 Theoretical Preliminaries

The paper develops convergence theory for projected gradient descent with biased, inexact gradient estimates, then analyzes robust gradient estimators under contamination and heavy tails.

  • General framework: The convergence analysis allows gradient estimators to be biased and inconsistent, as occurs under Huber contamination.The analysis instead studies stability of projected gradient descent with inexact gradients.
  • Stability of Gradient Descent: Theorem 1 establishes convergence when the gradient estimator satisfies the estimation condition and is stable for the risk function.The prescribed step size is η = 2/(τℓ+τu), with contraction parameter κ < 1.
  • Stability of Gradient Descent: Linear convergence means that typically a logarithmic number of iterations suffices for an accurate estimate.The iteration count balances a decreasing optimization term against an increasing estimation-error term.
  • General framework: The framework embeds robust gradient estimation within projected gradient descent for general risk minimization.The gradient of population risk is treated as a multivariate mean and estimated robustly.
  • Robust gradient estimators: Under bounded fourth moments, the Huber gradient estimator has vanishing error as n →∞ and only weak dependence on dimension p.The heavy-tailed gradient estimator provides exponential concentration under bounded second moments.
  • Robust gradient estimators: These gradient-estimation guarantees yield robust multivariate mean estimates that can support subsequent robust parametric estimation.The heavy-tailed guarantee is obtained under a bounded-second-moment assumption on the gradient distribution.

6 Consequences for Estimation under ǫ-Contaminated Model

The theory yields robust estimation guarantees for linear regression, generalized linear models, and exponential families under Huber contamination, with dependence shaped by gradient variance and conditioning.

  • Robust linear regression: Robust linear regression uses projected gradient descent with the Huber gradient estimator under bounded covariate eighth moments and noise fourth moments.The resulting theorem applies when sample size and contamination satisfy stated conditions.
  • Robust linear regression: The asymptotic maximum contamination level for linear regression increases when the covariance matrix is better conditioned.The paper relates this tolerance to the conditioning of Σ.
  • Robust linear regression: Unlike plugin estimation, the asymptotic error of robust gradient estimation is independent of ∥θ∗∥2.Plugin error can become vacuous when ∥θ∗∥2 scales with dimension p.
  • Generalized linear and exponential-family models: For logistic regression and exponential-family models, the proposed algorithm returns contracting iterates under a constant contamination bound.The same projected-gradient framework and Huber gradient estimator are used in both settings.
  • Generalized linear and exponential-family models: The logistic-regression guarantee extends to general covariate distributions, unlike the cited plugin approach restricted to Gaussian covariates.The plugin estimator’s error also scales with ∥θ∗∥2, which the robust gradient method avoids.
  • Discussion and limitations: In the asymptotic setting, the estimation error scales as O(√(ǫ log p)), giving logarithmic dimension dependence.The paper attributes differences in maximum contamination across models largely to differing gradient variances.

7 Consequences for Heavy-Tailed Estimation

The paper extends its robust gradient-descent guarantees to heavy-tailed linear, generalized linear, logistic, and exponential-family estimation under weak moment and smoothness assumptions.

  • Heavy-tailed linear regression: Heavy-tailed linear regression assumes bounded fourth moments for covariates and bounded second moments for noise.These assumptions are used to control gradient-estimation error.
  • Heavy-tailed linear regression: The heavy-tailed linear-regression theorem uses projected gradient descent with the heavy-tailed gradient estimator and contraction parameter κ < 1.The algorithm uses η = 2/(τu+τℓ).
  • Heavy-tailed generalized linear models: Heavy-tailed generalized linear models require bounded fourth covariate moments plus smoothness and moment conditions on the link function.Under these conditions, the method returns contracting iterates.
  • Heavy-tailed generalized linear models: The heavy-tailed framework provides a logistic-regression corollary using the same projected-gradient procedure and Algorithm 3.The result is stated under the theorem’s sample and moment conditions.
  • Heavy-tailed exponential families: For heavy-tailed exponential families, bounded second moments of the sufficient-statistics vector support a projected-gradient guarantee with κ < 1.The heavy-tailed gradient estimator is used as the gradient oracle.

8 Discussion

The paper presents robust gradient descent as a broadly applicable estimator class that combines robust mean estimation with iterative risk minimization and obtains guarantees across robustness settings.

  • Discussion: The proposed estimators robustify iterative risk-minimization updates rather than replacing the risk objective with a robust objective.They use robust estimates of risk gradients inside projected gradient descent.
  • Discussion: The approach is computationally practical and broadly applicable across parametric statistical models.The paper reports strong robustness guarantees under Huber contamination and heavy-tailed distributions.
  • Future work: Improving robust mean estimation would immediately improve the guarantees of the robust gradient-descent estimators.The paper identifies this dependency as a direction for future work.

A Proof of Theorem 1

The proof analyzes projected gradient descent with an inexact gradient estimator, establishing contraction under a stability condition and extending the result to linear regression under bounded covariate moments.

  • Probability control: A probability bound holding at each iteration is extended to all T iterations by a union bound, retaining probability at least 1 − δ.The analysis then conditions on this joint event.
  • Projected gradient descent: The noisy gradient is written as g(θk) = ∇R(θk) + ek, with error bounded by α∥θk − θ∗∥2 + β.The update applies projection after a gradient step.
  • Projected gradient descent: Projection contraction reduces the next-iterate error to the distance between the noisy and population gradient updates.The proof compares PΘ[θk − ηg(θk)] with PΘ[θ∗ − η∇R(θ∗)].
  • Stability condition: Choosing η = 2/(τu + τℓ) and assuming α < τℓ yields a contraction factor κ < 1.The resulting induction controls the optimization error across iterations.
  • Linear regression consequence: For linear regression with Gaussian noise, bounded eighth moments of covariates provide the smoothness parameters used to obtain the theorem’s result.Theorem 2 follows from the generalized linear-model result, with linear regression as a special case.

C Proof of Theorem 4

The proof of Theorem 4 establishes gradient-moment bounds for generalized linear models and uses them to control a Huber gradient estimator. Stability then follows when sample size and contamination satisfy the stated conditions.

  • Gradient distribution: Gradient distributions are analyzed through moment and covariance bounds derived from smoothness and exponential-family cumulant assumptions.Bounded derivatives through order eight imply bounded fourth moments of the gradient.
  • Gradient distribution: The C_r inequality and exponential-family cumulant identities control moments of the gradient loss.The proof also invokes smoothness to relate the loss and its expectation.
  • Robust gradient estimation: The Huber Gradient Estimator converts the gradient-moment bounds into a high-probability estimation guarantee at each point.The estimator is applied with failure probability δ/T.
  • Stability and conclusion: Gradient descent is stable when α(en, eδ) < τℓ, requiring sufficiently large n and contamination below the stated bound.Substituting the resulting estimator error parameters into Theorem 1 recovers Theorem 4.

D Proof of Corollary 3

The proof of Corollary 3 studies fourth moments of the linear-regression gradient under Gaussian covariates and noise, then applies a robust mean-estimation oracle to recover the stated result.

  • Moment analysis: The regression variable xy is decomposed into covariate and noise terms to analyze its covariance and fourth moments.The covariance is expressed using the Gaussian design structure.
  • Gaussian specialization: Lemma 5 specializes the argument to x ∼ N(0, Ip) and w ∼ N(0, 1), supplying universal-constant bounds for the Gaussian model.These assumptions define the model used in the corollary proof.
  • Moment analysis: Cauchy–Schwarz, independence, and Gaussian projection properties bound the component terms in the fourth-moment calculation.The proof separately controls terms A and C.
  • Moment analysis: The resulting bounds scale with ∥θ∗∥2^4, establishing that xy has bounded fourth moments.Both sides of the relevant inequality have this scaling.
  • Robust estimation: Because xy has bounded fourth moments, a robust mean-estimation oracle produces an estimate of E[xy] with high probability.The oracle guarantee is then substituted to recover Corollary 3.

E Proof of Theorem 6

The proof of Theorem 6 derives gradient moment and covariance properties for an exponential-family model, then applies robust gradient estimation. Fisher consistency identifies the target parameter, and α(en, eδ) = 0 makes stability automatic when τℓ > 0.

  • Gradient distribution: The proof begins by studying the gradient distribution to obtain the moment bounds needed for robust estimation.The sufficient statistics are assumed to have bounded fourth moments.
  • Exponential-family structure: Fisher consistency gives the population gradient structure, while the covariance is controlled through the Hessian of the log-normalization function.The true parameter can be obtained by inverting the ∇A operator whenever possible.
  • Stability and conclusion: α(en, eδ) = 0 means the stability condition is always satisfied whenever τℓ > 0, leaving only the stated ε bound.Substituting β(en, eδ) into Theorem 1 yields the required result.
  • Exponential-family structure: Strong/smooth duality is used to control the Lipschitz smoothness of the convex conjugate A∗.The proof invokes the equivalence between smoothness and strong convexity of convex conjugates.
  • Robust gradient estimation: The covariance identity ∥Cov[∇L(θ)]∥2 = ∥∇2A(θ∗)∥2 supports the robust gradient-estimator guarantee.The same gradient-estimation argument is used to recover the corollary result.
  • Stability and conclusion: The generalized robust-gradient proof uses the same stability criterion for additional models, requiring α(en, eδ) < τl before applying Theorem 1.The theorem proofs conclude by substituting the corresponding β(en, eδ).

J Upper bound on Contamination Level

The analysis gives a contamination threshold beyond which robust gradient descent can fail, even with infinitely many samples. It also compares the resulting rate with a minimax lower bound and develops the robust mean-estimation machinery underlying the analysis.

  • Upper bound on contamination: Above an initialization-dependent contamination threshold, an adversarial distribution can make Algorithm 1 remain stuck at θ0 even as n →∞.The failure occurs when gradient-estimation error can include the zero vector, forcing the estimated gradient to vanish.
  • Upper bound on contamination: The contamination threshold is analyzed for linear regression with x ∼N(0, Ip) in the asymptotic regime n →∞.The stated complementary analysis specializes to Gaussian covariates and examines the dependence on the initialization point θ0.
  • Statistical rate: The method’s O(√(ǫ log p)) accuracy is weaker than the Ω(ǫ) minimax rate for estimating the gradient mean, so the procedure is not minimax optimal.Despite this gap, the paper characterizes the approach as the only practical algorithm for robust estimation of general statistical models.
  • Robust mean analysis: The supporting robust mean analysis assumes bounded fourth moments and uses interval-based one-dimensional filtering, concentration inequalities, and matrix tools for higher dimensions.The cited development includes Chebyshev, Hoeffding, VC theory, Bernstein, and matrix Bernstein arguments.

K.2 The case when p = 1

For p = 1, the robust mean estimator selects a short interval containing most observations and averages the retained points. Its analysis separates contamination, sampling, and conditioning errors before extending the framework to higher dimensions.

  • K.2 The case when p = 1: The one-dimensional error bound combines the contribution of retained noise with the deviation of the retained clean-point mean from the conditional mean.The latter is controlled using bounded fourth moments and concentration of the conditional distribution.
  • K.2 The case when p = 1: The estimator returns a high-probability mean estimate under a distribution with finite variance and bounded fourth moments.The proof obtains the final guarantee by combining the intermediate high-probability events with a union bound.
  • K.2 The case when p = 1: The selected interval contains most clean observations while restricting the distance of retained noise points from the true mean.The proof uses interval overlap and concentration arguments to bound the interval length and the displacement of selected noise.
  • Higher-dimensional extension: For p > 1, the analysis extends filtering through covariance control, projection onto low-variance subspaces, and repeated sample splitting.The higher-dimensional proof bounds both the retained mean and covariance after outlier removal.
Loading 1802.06485v2…