PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical consistency and asymptotic normality for high-dimensional robust M-estimators

Po-Ling Loh

arXiv:1501.00312v1math.STcs.ITstat.ML

TL;DR

The paper addresses robust high-dimensional regression under heavy-tailed errors and outlier contamination. It analyzes local stationary points using bounded loss derivatives, local restricted curvature, and suitable regularizers, and proposes convex initialization followed by nonconvex optimization. The resulting estimators achieve Lasso-like consistency rates, while appropriate nonconvex penalties yield unique local oracle solutions and support asymptotic normality.

  • Problem

    The paper studies high-dimensional sparse regression when heavy-tailed errors or outliers in errors and covariates challenge ordinary robust and least-squares estimators.

  • Method

    The paper combines local restricted-curvature analysis with bounded-derivative robust losses, amenable regularizers, and a two-step convex-initialized composite gradient method.

  • Results

    Stationary points near the truth are statistically consistent at the Lasso sub-Gaussian rate, while suitable nonconvex regularizers produce unique local oracle solutions and enable asymptotic normality.

  • Takeaways & Limitations

    A convex robust estimator can provide initialization for a nonconvex estimator that improves efficiency while retaining local statistical guarantees.

  • Takeaways & Limitations

    Optimization guarantees are local: initialization outside the restricted-curvature basin can lead to inconsistent stationary points.

Abstract

from arXiv · show

We study theoretical properties of regularized robust M-estimators, applicable when data are drawn from a sparse high-dimensional linear model and contaminated by heavy-tailed distributions and/or outliers in the additive errors and covariates. We first establish a form of local statistical consistency for the penalized regression estimators under fairly mild conditions on the error distribution: When the derivative of the loss function is bounded and satisfies a local restricted curvature condition, all stationary points within a constant radius of the true regression vector converge at the minimax rate enjoyed by the Lasso with sub-Gaussian errors. When an appropriate nonconvex regularizer is used in place of an l_1-penalty, we show that such stationary points are in fact unique and equal to the local oracle solution with the correct support---hence, results on asymptotic normality in the low-dimensional case carry over immediately to the high-dimensional setting. This has important implications for the efficiency of regularized nonconvex M-estimators when the errors are heavy-tailed. Our analysis of the local curvature of the loss function also has useful consequences for optimization when the robust regression function and/or regularizer is nonconvex and the objective function possesses stationary points outside the local region. We show that as long as a composite gradient descent algorithm is initialized within a constant radius of the true regression vector, successive iterates will converge at a linear rate to a stationary point within the local region. Furthermore, the global optimum of a convex regularized robust regression function may be used to obtain a suitable initialization. The result is a novel two-step procedure that uses a convex M-estimator to achieve consistency and a nonconvex M-estimator to increase efficiency.

1 Introduction

The paper develops local theory for regularized robust M-estimators in high-dimensional regression under heavy-tailed errors and outlier contamination. It establishes consistency, oracle behavior, and a two-step optimization strategy for nonconvex estimators.

  • Motivation: Heavy-tailed errors can make least-squares regression lose optimal convergence rates, while outliers in predictors or responses can cause inconsistency.These motivate extending robust low-dimensional regression theory to sparse high-dimensional settings.
  • Statistical consistency: Local restricted strong convexity and bounded loss derivatives yield statistical consistency for stationary points near the true regression vector.The guarantees apply despite heavy-tailed errors and outlier contamination, under conditions tied to the error tails.
  • Statistical consistency: Under weaker distributional assumptions on covariates, the consistency results extend beyond standard high-dimensional robust M-estimation analyses.The paper specifically provides consistency results for local stationary points.
  • Oracle behavior: Suitable nonconvex regularizers make local stationary points unique and equal to a local oracle solution, supporting high-dimensional asymptotic normality.This addresses why nonconvex regression functions can be preferable to convex alternatives for efficiency under heavy-tailed errors.
  • Optimization: A two-step algorithm first optimizes a convex regularized M-estimator, then initializes composite gradient descent for the original nonconvex estimator.The approach is designed for settings where both the loss and regularizer may be nonconvex.
  • Related work: The paper relates its local stationary-point analysis to prior work while treating M-estimators more generally than analyses restricted to the Huber loss.It also distinguishes its rates from sharper results for differently tuned convex losses.

2 Background and problem setup

The paper formulates sparse high-dimensional robust regression as a regularized M-estimation problem and reviews robust losses, generalized estimators, and amenable regularizers. Bounded derivatives limit error-outlier influence, while covariate outliers require leverage-aware weighting.

  • Problem setup: The model uses n independent observations with covariates in R^p, responses in R, and a k-sparse true coefficient vector.The covariates and additive errors are assumed independent and mean zero.
  • Problem setup: The estimator minimizes an empirical loss plus a sparsity-promoting penalty, with an ℓ1 constraint ensuring existence when loss or regularizer terms are nonconvex.The constraint radius is required to contain the true coefficient vector.
  • Robust losses: The Cauchy loss is nonconvex and proportional to the one-degree-of-freedom t-distribution likelihood, suggesting statistical-efficiency advantages for heavy-tailed errors.Its derivative approaches zero asymptotically but it has no finite rejection point.
  • Robust losses: Bounded loss derivatives limit each outlier’s contribution to the estimating equation, reducing the effect of gross additive-error contamination.Redescending losses can eliminate sufficiently large residuals entirely, but are necessarily nonconvex.
  • Generalized M-estimators: Ordinary M-estimators remain non-robust to covariate outliers, motivating generalized M-estimators that downweight observations with high leverage.Mallows and Hill-Ryan estimators use weighting schemes that bound or scale covariate influence.

3 Main statistical results

The paper establishes local statistical consistency for high-dimensional robust M-estimators under bounded loss derivatives and local restricted strong convexity, then shows that suitable nonconvex regularization yields oracle behavior and asymptotic consequences.

  • General statistical theory: The local RSC assumption imposes no requirements on the loss outside the neighborhood of β∗, accommodating robust losses with more nonconvex behavior away from the target.This local focus is stronger than extending a weaker curvature inequality outside the region, but it only supports local conclusions.
  • General statistical theory: Local restricted strong convexity and a µ-amenable regularizer ensure statistical consistency for stationary points within a constant-radius neighborhood of β∗.The theorem is deterministic; distributional assumptions are used to verify its conditions with high probability.
  • General statistical theory: All local stationary points achieve the usual minimax rate associated with ℓ1-penalized least-squares regression with sub-Gaussian data, even for heavy-tailed or contaminated errors.The convergence region shrinks to a radius of order O under the stated sample-size scaling.
  • Establishing sufficient conditions: Bounded loss derivatives support consistency under heavy-tailed errors, while weighting can weaken covariate requirements and reduce finite-sample bias when leverage contamination inflates the sub-Gaussian parameter.The concentration result is largely independent of the error distribution apart from a possible symmetry requirement.
  • Oracle results and asymptotic normality: For suitable nonconvex regularizers and a beta-min condition, every stationary point in the local neighborhood is unique, has support contained in S, and equals the local oracle estimator.The oracle estimator is optimized over the true support, and the loss is strongly convex on the corresponding restricted region.
  • Oracle results and asymptotic normality: Because the local stationary points agree with a k-dimensional oracle solution, low-dimensional asymptotic results can be applied to analyze their asymptotic distribution.The oracle result transfers properties of the lower-dimensional estimator to the high-dimensional stationary points.

4 Optimization

The paper develops local optimization guarantees for regularized robust M-estimators and a two-step procedure that obtains a suitable initialization before optimizing potentially nonconvex objectives.

  • Composite gradient descent: Composite gradient descent converges linearly to a stationary point near β∗ when initialized sufficiently close to β∗.The guarantee applies under local restricted strong convexity and restricted smoothness assumptions.
  • Composite gradient descent: The iterates remain controlled within the local region, where the restricted curvature condition supports the convergence analysis.Because curvature is assumed only locally, the result does not provide general global convergence.
  • Composite gradient descent: Initialization outside the local basin can lead to an inconsistent stationary point outside the region where restricted strong convexity holds.The simulations show that proximity of β0 to β∗ is necessary for reliable optimization of nonconvex robust estimators.
  • Two-step estimators: The two-step algorithm first optimizes a convex robust estimator, then uses its output to initialize composite gradient descent for the desired high-dimensional estimator.The first step uses a convex loss with bounded derivative and a convex ℓ1 penalty.
  • Two-step estimators: Under n ≥ Cr2 · k log p, the first-step estimator enters the local region, enabling the second step’s linear convergence.The first-step error satisfies ∥bβ1 − β∗∥2 ≤ r when the scaling and tuning conditions hold.
  • Two-step estimators: With a (µ, γ)-amenable penalty, the final estimator is statistically consistent and agrees with the local oracle estimator.The method is motivated by the greater efficiency available from nonconvex M-estimators, despite their lack of general fast global convergence.

5 Simulations

Simulations examine statistical consistency, estimator comparisons, and optimization behavior under heavy-tailed errors, outliers, and relaxed covariate assumptions. The results broadly agree with the paper’s theoretical predictions.

  • Statistical consistency: Robust losses improve ℓ2-error over the Lasso by a constant factor for contaminated but sub-Gaussian mixture errors.The Lasso remains ℓ2-consistent in this setting, but robust losses reduce its error prefactor.
  • Statistical consistency: Robust losses yield statistically consistent ℓ1-penalized estimators under heavy-tailed Cauchy errors and contaminated normal-mixture errors.The Cauchy simulations use normal covariates, while the mixture contains a constant fraction of large-variance outliers.
  • Generalized M-estimators: The Mallows estimator is statistically consistent with sub-exponential covariates and Cauchy errors, and outperforms the ℓ1-penalized Huber estimator.The comparison agrees with Theorem 1 and Proposition 3.
  • Optimization: Composite gradient descent shows roughly linear log-error decay for convex Huber loss from random initializations and for suitable Tukey-loss initializations.For Tukey loss, random initializations can converge more slowly to a different stationary point, whereas Huber-based or local initializations reach the local point.
  • Oracle behavior: SCAD-penalized Huber and Cauchy estimators are statistically consistent, with support recovery transitioning sharply from zero to one as sample size increases.The empirical variance remains roughly constant for sufficiently large sample sizes, and the Cauchy loss has uniformly smaller variance than the Huber loss.

6 Discussion

The paper concludes that local curvature supports consistency, oracle behavior, asymptotic normality, and a two-step optimization strategy for high-dimensional robust M-estimators. It also identifies unresolved questions about the side constraint and robustness properties.

  • Discussion: Local-RSC stationary points are statistically consistent under heavy-tailed errors or outlier contamination at the sub-Gaussian-Lasso convergence rate.Appropriate nonconvex regularizers additionally make the local stationary point unique and equal to the local oracle solution.
  • Discussion: Nonconvex regularization transfers oracle properties to high-dimensional local solutions, including asymptotic normality and, in some cases, asymptotic efficiency.The simulations report constant empirical variance for sufficiently large sample sizes.
  • Discussion: A convex robust M-estimator can initialize composite gradient descent for a nonconvex M-estimator through the proposed two-step procedure.The first step obtains a sufficiently close initialization for the second-step nonconvex optimization.
  • Open questions: The proofs require an ℓ1 side constraint, but it remains unclear whether that constraint is necessary when stationary points already lie near β∗.Removing it would leave only the regularization parameter λ to tune.
  • Open questions: Robustness measures for high-dimensional stationary points remain open when the oracle result does not hold, particularly for ℓ1-penalized robust M-estimators.The paper specifically mentions breakdown behavior and influence-function bounds as future directions.

A Measures of robustness

The appendix reviews breakdown points, influence functions, sensitivity curves, and asymptotic variance as measures of robustness. It contrasts classical robustness properties with high-dimensional and nonconvex M-estimation results.

  • Breakdown points: The finite-sample breakdown point measures how much sample contamination is required to drive an estimator beyond a specified bound.For convex M-estimators of the stated type, the breakdown point is reported as 1/n.
  • Influence functions: The influence function measures an estimator’s response to infinitesimal point-mass contamination, while gross-error sensitivity uses its supremum.B-robustness is defined by finite gross-error sensitivity.
  • Influence functions: For fixed covariates and response contamination, a bounded loss derivative yields a bounded influence function for the linear-regression M-estimator.For generalized M-estimators, boundedness also depends on the weighting construction that keeps ∥w(x)x∥2 bounded.
  • Influence functions: Sensitivity curves are finite-sample analogues of influence functions that converge to them under suitable regularity conditions.The appendix notes that influence-function theory for high-dimensional estimators remains relatively sparse.
  • Asymptotic variance: Nonconvex regularization makes local high-dimensional solutions coincide with oracle solutions, allowing them to inherit certain classical optimality properties.Convex-loss high-dimensional M-estimators instead include an additional asymptotic-variance term absent in the fixed-dimensional setting.

B Proofs of main theorems

The appendix provides proofs of the main theorems stated in the paper.

  • Proofs: The appendix contains proofs of the paper’s main theorems.
  • Proofs: The proofs are presented after the main theoretical and empirical sections.
  • Proofs: The appendix’s stated purpose is to establish the main theorem results formally.

B.1 Proof of Theorem 1

The proof establishes existence of a local stationary point by first analyzing any stationary point within radius r and then constructing one inside that region under a sample-size condition.

  • The argument analyzes stationary points eβ satisfying ∥eβ − β∗∥2 ≤ r.
  • The proof combines local restricted curvature with convexity and norm inequalities to control the estimation error.
  • The construction defines bβ and shows it is a stationary point of the constrained program.
  • Provided n ≥ Cr2 · k log p, bβ lies inside the radius-r sphere and is therefore a stationary point of the original program.

B.2 Proof of Theorem 2

The proof uses a primal-dual witness construction, restricted optimization, and concentration arguments to establish oracle behavior and support properties for stationary points.

  • The proof adapts a primal-dual witness construction to connect the restricted estimator with the full program.
  • All stationary points within the local radius are supported on S, as implied by the dual-feasibility argument.
  • The oracle estimator satisfies a lemma-specific error bound and lies in the interior of the feasible region under the theorem’s conditions.
  • A covering argument and concentration for products and polynomials of sub-Gaussian variables control the empirical quantities used in the proof.
  • Under scaling n ≥ max{k2, k log p} and a suitable λ, strict dual feasibility ∥bzSc∥∞ < 1 is obtained.
  • Restricted strong convexity and smoothness are used inductively to show linear convergence of successive iterates under the stated initialization and scaling conditions.

C Proofs of propositions in Section 3.2

The appendix proves technical propositions for local restricted curvature by controlling truncation, expectation, and empirical-process terms under sub-Gaussian or related covariate assumptions.

  • The appendix develops sufficient conditions for statistical consistency of stationary points in Section 3.2.
  • Truncation functions and localized sets are introduced to control Taylor remainders and differences in expectations.
  • Concentration bounds are obtained for quadratic forms and averages of sub-exponential variables, with probability controlled by sample size and k log p.
  • A peeling argument extends localized bounds uniformly over the parameter domain and yields the RSC condition.
  • Gaussian-process and bounded-difference arguments control the remaining empirical terms in the proof.
  • The same proof structure extends to weighted covariates because w(xi)xi has controlled sub-Gaussian or sub-exponential behavior.

C.4 Proof of Proposition 4

The proof of Proposition 4 replaces covariates with weighted covariates and derives the required curvature bound using their boundedness and concentration properties.

  • On the relevant event, the proof replaces xi with w(xi)xi in the truncation and Taylor-remainder arguments.
  • Because |w(xi)xT i v| ≤ b0 for every unit vector v, w(xi)xi is sub-Gaussian regardless of the distribution of xi.
  • The resulting curvature inequality has the form T(β1, β2) ≥ (αT + κ2) · f(β1, β2) − κ2 · ef(β1, β2).
  • The remainder of the argument follows the earlier proposition’s proof with the weighted covariates substituted throughout.

D Proof of Corollary 1

The corollary follows by applying Theorem 2 together with a result of He and Shao under local convexity, uniqueness, and regularity conditions. The argument verifies these conditions over the restricted region defined by the RSC condition and transfers the conclusion from the oracle estimator to the target estimator.

  • Proof strategy: The proof combines Theorem 2 with Lemma 11, attributed to Corollary 2.1 of He and Shao.The cited lemma assumes i.i.d. observations from the usual linear regression model and regularity conditions on the loss and estimator.
  • Conditions: Lemma 11 assumes a convex, smooth loss with bounded second and third derivatives and positive expected curvature.These requirements appear in condition (ii), including E[ℓ′′(ε_i)] ∈ (0, ∞).
  • Local argument: The argument extends the lemma to the restricted region S_r, where the loss is convex and the estimator is uniquely minimized under the RSC condition.The passage identifies this region using Lemma 1 and condition (13).
  • Probability bound: For k ≥ C log n, the relevant probability expression is bounded above by c_1 exp(−c′…).The supplied passage gives the threshold and exponential upper-bound form, but not the complete exponent.
  • Conclusion: The desired results are first established for the oracle estimator bβ^O and then transferred by Theorem 2 to eβ.The proof closes by invoking the theorem after verifying the auxiliary conditions.

E.2 Proof of Lemma 2

This section analyzes heavy-tailed covariates and errors in the Lasso setting, using stable-distribution properties and sub-exponential concentration. It concludes that the relevant bound can fail with high probability for α-stable errors when α < 2, while the Lasso is inconsistent in the stated setting.

  • Stable distributions: For i.i.d. α-stable covariates with γ = 1, w^T X is α-stable with scale parameter ∥w∥_α.The stable-family calculation is used to characterize weighted sums of covariates.
  • Concentration: For sub-Gaussian Z and α ∈ (0, 2], |Z|^α is sub-exponential, supporting concentration arguments for covariate moments.The passage attributes the result to sub-Gaussianity and derives sub-exponential behavior.
  • Concentration: The relevant covariate quantity exhibits sub-exponential concentration around E[|X_ij|^α].This concentration statement applies for each coordinate j.
  • Failure under heavy tails: When α < 2 and n^(1−1/α)λ → 0, the lower bound remains at least a constant c_α, so the stated bound does not hold with high probability.The passage identifies this regime through the scale-parameter calculation and inequality (102).
  • Lasso consequence: In ordinary least-squares regression with the Lasso, the analysis establishes inconsistency with high probability in the heavy-tailed setting.The conclusion is stated directly after the Lasso argument.
Loading 1501.00312v1…