PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Huber Regression

Qiang Sun, Wenxin Zhou, Jianqing Fan

arXiv:1706.06991v2math.STstat.ME

TL;DR

Heavy-tailed data and asymmetric errors limit conventional regression methods and fixed-parameter Huber regression. The paper develops adaptive Huber regression and shows a sharp, optimal phase transition: with δ≥1 it achieves sub-Gaussian-type concentration, while 0<δ<1 yields slower rates.

  • Problem

    Fixed-parameter Huber regression may be biased and inconsistent under asymmetric distributions, while heavy-tailed data challenge conventional regression methods.

    Source: §1 · p. 2, §2 · p. 5

  • Method

    The paper adapts Huber’s robustification parameter to sample size, dimension, and moment conditions to balance robustness and bias.

    Source: §1 · p. 3, §2 · p. 7, §3.1 · p. 8

  • Results

    When δ≥1, adaptive Huber estimators achieve sub-Gaussian-type concentration, whereas 0<δ<1 yields slower concentration; matching bounds establish a sharp phase transition.

    Source: §1 · p. 3, §2 · pp. 6–7

  • Takeaways & Limitations

    Adaptive Huber regression provides robust, asymptotically unbiased estimation and inference under heavy-tailed errors with only finite (1+δ)-th moments.

    Source: §1 · p. 3

    The paper leaves sharper bounds for regularized estimators under heavy-tailed observation noise to future work.

    Source: §3.2 · p. 11

Abstract

from arXiv · show

Big data can easily be contaminated by outliers or contain variables with heavy-tailed distributions, which makes many conventional methods inadequate. To address this challenge, we propose the adaptive Huber regression for robust estimation and inference. The key observation is that the robustification parameter should adapt to the sample size, dimension and moments for optimal tradeoff between bias and robustness. Our theoretical framework deals with heavy-tailed distributions with bounded $(1+δ)$-th moment for any $δ> 0$. We establish a sharp phase transition for robust estimation of regression parameters in both low and high dimensions: when $δ\geq 1$, the estimator admits a sub-Gaussian-type deviation bound without sub-Gaussian assumptions on the data, while only a slower rate is available in the regime $0<δ< 1$. Furthermore, this transition is smooth and optimal. In addition, we extend the methodology to allow both heavy-tailed predictors and observation noise. Simulation studies lend further support to the theory. In a genetic study of cancer cell lines that exhibit heavy-tailedness, the proposed methods are shown to be more robust and predictive.

1 Introduction

The paper proposes adaptive Huber regression for robust estimation and inference under heavy-tailed, asymmetric data, replacing fixed robustification with a sample-, dimension-, and moment-adaptive choice. It establishes phase-transition guarantees in low and high dimensions while distinguishing this tail-robustness framework from contamination-based and quantile-based robustness.

1 Introduction

  • Heavy-tailed data make sub-Gaussian assumptions and least-squares procedures unreliable, motivating methods robust to heavy-tailed errors and other contamination.Examples include invalid Gaussian assumptions in fMRI, heavy-tailed gene expression levels, and power-law financial returns.Source: §1 · p. 2
  • Unlike fixed 95% asymptotic-efficiency tuning, the adaptive procedure can consistently estimate model-generating parameters when the sample distribution is asymmetric.The paper revisits robust regression initiated by Huber (1973) and argues that fixed robustification can fail under asymmetry.Source: §1 · pp. 2–3
  • Adaptive Huber regression uses an adaptive robustification parameter to achieve exponential-type concentration and asymptotic unbiasedness under only finite (1 + δ)-th error moments, without symmetry or homoscedasticity assumptions.The paper also establishes matching lower bounds, a high-dimensional phase transition, removal of artificial bounded-parameter constraints, and a Bahadur representation when δ ≥ 1.Source: §1 · p. 3

1.1 Related Literature

  • The paper’s tail-based notion of robustness differs from conventional Huber ε-contamination robustness and from quantile-based robust regression.Related work develops robust mean, empirical-risk, matrix, and sparse-regression procedures for heavy-tailed settings, including Catoni (2012) and Fan, Li and Wang (2017).Source: §1.1 · pp. 3–4
  • The paper studies conditional mean regression with heavy-tailed, asymmetric errors, whereas quantile regression generally targets a biased coefficient unless errors are symmetric around zero.The proposed estimators achieve sub-Gaussian deviation bounds with finite second moments and asymptotically attain ordinary least-squares efficiency.Source: §1.1 · p. 4

2 Methodology

The methodology models heteroscedastic regression under finite (1+δ)-th error moments and replaces OLS or fixed-tuning Huber regression with an adaptive Huber estimator. Its robustification parameter adapts to moments, sample size, and dimension, yielding a phase transition between sub-Gaussian and slower concentration regimes.

Model

  • The model assumes i.i.d. observations from heteroscedastic regression, yi = ⟨xi, β∗⟩ + εi, with E(εi|xi) = 0 and finite (1+δ)-th error moments.The framework allows any δ > 0 through the condition E(|εi|^(1+δ)) < ∞.Source: §2 · pp. 5–6

Adaptive Huber estimator

  • Adaptive Huber regression addresses OLS outlier sensitivity and fixed-tuning bias by choosing τ according to sample size, dimension, and moments.The Huber loss is quadratic for small residuals and linear beyond τ, down-weighting outliers while balancing bias and robustness.Source: §2 · pp. 5–6

High-dimensional regression

  • In high dimensions, regularized adaptive Huber regression estimates β∗ in ℓ2-error at order s^1/2{(log d)/n}^min{δ/(1+δ),1/2} with high probability.Here s is the size of the true support, while effective dimension is d in low dimensions and s in high dimensions.Source: §2 · pp. 6–7

Phase transition

  • When δ ≥ 1, the estimator achieves sub-Gaussian-type concentration, whereas 0 < δ < 1 yields the slower rate n^−δ/(1+δ).With fixed effective dimension, Figure 1 reports ||β̂τ − β∗||2 ≍ n^−δ/(1+δ) for δ ≥ 1, using effective sample size neff = n in low dimensions and n/log d in high dimensions.Source: §2 · pp. 6–7, Figure 1 · p. 6

Unified formulation

  • The proposed tuning τ ≍ min{v1/(1+δ), 1} neff^max{1/(1+δ),1/2} unifies the low- and high-dimensional bounds up to logarithmic factors.The resulting upper bound is tight for all δ > 0 and becomes sub-Gaussian when δ ≥ 1.Source: §2 · p. 7

3 Nonasymptotic Theory

The theory establishes nonasymptotic, near-optimal guarantees for adaptive Huber regression under bounded (1+δ)-th moments. It identifies a phase transition at δ=1 and extends the results to sparse high-dimensional estimation.

3.1 Adaptive Huber Regression with Increasing Dimensions

  • Adaptive robustification balances approximation bias, which decreases as τ^-δ, against robustness, so τ must diverge at a data-dependent rate.The total error decomposes into estimation error and approximation bias; larger τ reduces bias but weakens robustness.Source: §3.1 · pp. 7–8
  • The low-dimensional analysis accommodates heteroscedastic errors, supports random designs with relaxed scaling n ≳ d+t, and attains asymptotic efficiency comparable to least squares.For fixed designs, the scaling is roughly n ≳ d^2t; a nonasymptotic Bahadur representation also supports future inference under heavy tails.Source: §3.1 · pp. 8–10
  • With bounded (1+δ)-th moments, matching bounds yield near-optimal error d^1/2 n^-min{δ/(1+δ),1/2}, with a sharp transition at δ=1.The rate is n^-1/2 for δ≥1 and n^-δ/(1+δ) when 0<δ<1, making root-n exponential concentration impossible in the latter regime.Source: §3.1 · p. 9

3.2 Adaptive Huber Regression in High Dimensions

  • In high dimensions, a localized restricted-eigenvalue condition is implied with high probability by the design RE condition under suitable τ, moment, and sample-size requirements.The implication holds when τ ≥ max{8Lr, c1(L^2kvδ)^1/(1+δ)} and n ≥ c2L^4k^2t.Source: §3.2 · pp. 10–11
  • The regularized adaptive Huber estimator achieves s^1/2{(log d)/n}^min{δ/(1+δ),1/2} with overwhelming probability and the optimal ℓ2-error rate.With finite-variance noise it matches Lasso performance under sub-Gaussian errors; fixed-design scaling is n ≳ s^2 log d, while random designs achieve minimax bounds under n ≳ s log d.Source: §3.2 · pp. 11–12

4 Extension to Heavy-tailed Designs

This section extends adaptive Huber regression to high-dimensional settings with heavy-tailed covariates and errors by robustifying both components. The modified estimator achieves exponentially fast concentration under finite fourth-moment covariates, though stronger scaling conditions are required.

Method

  • The method targets d ≫ n with sparse β* and robustifies both heavy-tailed covariates and regression errors.Coordinatewise truncation is used for covariates, complementing Huber loss robustification of response-space outliers.Source: §4 · p. 12

Main result

  • The modified adaptive Huber estimator achieves exponentially fast concentration when covariates have only finite fourth moments, at the cost of stronger scaling conditions.The result is stated under the section’s moment and regularity conditions.Source: §4 · p. 13

Rate

  • Under bounded v3, M4, and ∥β*∥2, the estimator attains a near-optimal convergence rate when t ≍ log d.The precise rate is given in Remark 7 and depends on the displayed result in equation (12).Source: §4 · p. 13

Tuning

  • The theoretically optimal robustification parameter τ differs from the one for subGaussian designs.The comparison is referenced to Theorem B.2 in the supplementary material.Source: §4 · p. 13

5 Algorithm and Implementation

This section develops a scalable LAMM algorithm for regularized adaptive Huber regression, replacing non-scalable generic convex optimizers with locally majorized quadratic updates and an adaptive curvature parameter.

Algorithm motivation

  • LAMM provides a fast, easily implementable approach for regularized adaptive Huber regression when cutting-plane and interior-point methods are not scalable.The unregularized formulation can instead be solved by iteratively reweighted least squares.Source: §5 · p. 14

Local majorization

  • The method iteratively minimizes a locally valid majorizing function, ensuring that the objective value decreases at every MM step.LAMM locally majorizes the loss at the current iterate using an isotropic quadratic function.Source: §5 · p. 14

Quadratic update

  • The isotropic quadratic surrogate yields an analytic unconstrained update implemented through the soft-thresholding operator.The update’s simplicity follows from minimizing the majorized optimization problem without constraints.Source: §5 · p. 14

Parameter adaptation

  • LAMM increases the isotropic parameter φ_k by a factor γ_u>1, such as 2, until the surrogate majorizes the target loss at the proposed update.This backtracking condition makes the target value non-increasing before the algorithm proceeds to the next iteration.Source: §5 · pp. 14–15

Implementation and convergence

  • The implementation repeats updates until ||β^(k+1)−β^(k)||_2≤ε, with ε suggested as 10^-4, then returns the final coefficient estimate.The algorithm alternates soft-thresholding updates and majorization checks before applying this convergence criterion.Source: §5 · p. 15

6 Numerical Studies · Appendix

The numerical studies show that adaptive Huber regression retains near-normal efficiency while improving robustness under heavy-tailed errors, follows the predicted phase-transition and effective-sample-size scaling, and performs best in the NCI-60 application. The appendix also documents tuning choices, heavy-tailed genomic data, and selected models.

6.1 Tuning Parameter and Finite Sample Performance

  • When moment order is unspecified, the studies assume finite variance, set t=log n, and select cτ and cλ by 3-fold cross-validation from {0.5,1,1.5}.For effective-sample-size scaling, cτ=0.5 is fixed to emphasize scaling with n rather than optimal finite-sample performance.Source: §6.1 · p. 15, §6.3 · p. 18
  • Adaptive Huber performs as well as least squares under normal errors and significantly outperforms it under Student’s t or log-normal heavy-tailed errors.These results are averaged over 100 simulations using ℓ2-error and show robustness with almost no efficiency loss at the normal model.Source: §6.1 · p. 16, Table 1 · p. 16

6.2 Phase Transition

  • Figure 2’s empirical curves closely resemble the theoretical curve, validating adaptive Huber’s phase transition in both low- and high-dimensional settings.The study uses 200 repetitions, with (n,d)=(500,5) and (500,1000), and varies Student’s t degrees of freedom.Source: §6.2 · pp. 16–17, Figure 2 · p. 17
  • Figure 3 shows adaptive Huber’s significant advantage over OLS when δ is small, while OLS gradually catches up as δ increases.The comparison uses t-distributed errors with varying degrees of freedom and ℓ2-error.Source: Figure 3 · p. 17, §6.2 · p. 18

6.3 Effective Sample Size

  • Figure 4 shows that ℓ2-error decreases with sample size and that curves for different dimensions nearly align when plotted against effective sample size n/log d.The alignment empirically confirms the scaling predicted by Theorem 3; curves shift right as d increases.Source: §6.3 · pp. 18–19, Figure 4 · p. 18

6.4 A Real Data Example: NCI-60 Cancer Cell Lines

  • The NCI-60 data are strongly heavy-tailed: 145 of 162 protein expressions have kurtosis above 3, 49 exceed 9, and 36.5% of gene expressions exceed t5 kurtosis.These findings motivate robust modeling despite normalization and log2 transformation.Source: §6.4 · p. 19, Figure 5 · p. 20
  • TAHuber achieves the smallest KRT19 prediction MAE, followed by AHuber and Lasso, while Lasso selects a comparatively large model.Table 2 reports leave-one-out MAE, model size, and selected genes for the three methods.Source: §6.4 · p. 20, Table 2 · p. 21
  • TAHuber selects 7 genes and AHuber 11 including KRT19, whereas Lasso selects 42 genes but excludes KRT19.The methods compare adaptive Huber regression, truncated-covariate adaptive Huber regression, and Lasso with ten-fold cross-validation.Source: §6.4 · pp. 19–20

A A Lepski-type method · B Random Design Analysis

The paper adapts Huber regression to an unknown variance through a Lepski-type data-driven choice, then formulates random-design counterparts under sub-Gaussian covariates and heavy-tailed errors.

A A Lepski-type method

  • The Lepski-type procedure selects among Huber estimators computed over a geometric grid of robustification scales, producing a data-driven final estimator.The grid uses σ_j = σ_min a^j and τ_j = σ_j(n/t)^1/2, with cardinality bounded by 1 + log_a(σ_max/σ_min).Source: A A Lepski-type method · pp. 26–27
  • Theorem 6 gives a high-probability bound for the adaptive estimator when n ≥ 8 max(4eL^2d, eL^4d^2)t.The stated probability is at least 1 − (2d + 1) log_a(aσ_max/σ_min)e^−t.Source: A A Lepski-type method · p. 27
  • The construction requires crude preliminary upper and lower bounds on v_1^1/2, whose unknown sharp constants can limit practical effectiveness.Suggested implementation uses σ_min = σ̂/K and σ_max = Kσ̂, with a = 1.5 and t = log n or log(nd), but sharp constants remain open.Source: A A Lepski-type method · p. 27

B Random Design Analysis

  • The random-design analysis assumes i.i.d. covariates that are sub-Gaussian after covariance normalization, with positive-definite covariance matrix Σ.The normalized tail condition is imposed for all y and u, with sub-Gaussian constant A_0.Source: B Random Design Analysis · p. 28
  • Regression errors are independent, conditionally mean-zero, and have finite conditional (1+δ)-th moments for some δ > 0.The section simplifies to homoscedastic errors, while conditional heteroscedasticity is allowed with slight modifications.Source: B Random Design Analysis · p. 28
  • Under positive-definite Σ, the random-design results use a covariance-rescaled ℓ2 norm and the derivative ψ_τ of the Huber loss.These definitions establish the geometry and robust score notation used in the random-design analysis.Source: B Random Design Analysis · p. 29

B.1 Huber regression in low dimensions

In low dimensions, adaptive Huber regression uses a calibrated robustification parameter to obtain concentration under finite (1+δ)-th moments and a nonasymptotic Bahadur representation when errors have finite variance. It remains robust to heavy-tailed errors while becoming highly efficient as the robustification parameter diverges.

Theorem 7

  • Theorem 7 provides exponential-type concentration for the estimator under finite (1+δ)-th moments and a nonasymptotic Bahadur representation when regression errors have finite variance.The concentration result applies with properly calibrated τ, while the representation approximates the estimator by a linear stochastic term plus a higher-order remainder.Source: §B.1 · pp. 29–30

Bahadur representation

  • The estimator’s distribution is governed, up to a higher-order remainder with sub-exponential tails, by a linear stochastic term that is easier to analyze than the nonlinear estimator.Unlike least squares, adaptive Huber regression lacks an explicit closed-form representation, motivating the Bahadur approximation.Source: §B.1 · p. 30

Efficiency and robustness

  • Proposition 2 shows that truncation-induced differences between the first two moments of ψτ(ε) and ε shrink faster with τ when ε has higher moments.Together with Theorem 7, this explains why the estimator combines heavy-tail robustness with high efficiency as τ→∞.Source: §B.1 · p. 30

Adaptive calibration

  • With t=log n and n ≳ d, choosing τ ≍ √(n/(d+log n)) yields nonasymptotic robustness with probability at least 1−O(n^-1).This adaptive choice balances robustness and efficiency under the low-dimensional scaling.Source: §B.1 · p. 30

Asymptotic approximation

  • For suitable dimension growth, linear contrasts of the estimator are asymptotically close to sums of independent random vectors involving ψτ(εi) and Σ^-1xi.Under independent errors with variance σ^2 and an additional finite (2+κ)-th moment, the contrast admits the stated stochastic approximation.Source: §B.1 · p. 30

B.2 Huber regression in high dimensions … C.2 Proof of Proposition 1

In high dimensions, the ℓ1-regularized Huber estimator achieves sparse-regression rates under heavy-tailed errors, while the proofs establish localized restricted strong convexity and phase-specific bias controls. The random-design sample-size requirement is optimal up to constants and improves on the fixed-design scaling described here.

B.2 Huber regression in high dimensions

  • For d ≫ n and sparse support size s ≪ n, the ℓ1-regularized Huber estimator uses robustification parameter τ and regularization parameter λ under Condition 5.Source: §B.2 · p. 31
  • When δ = 1, properly tuned ℓ1-regularized Huber regression has ℓ1- and ℓ2-errors scaling as s√(log d/n) and √(s log d/n), respectively, under n ≳ s log d.These are the minimax rates of standard Lasso with Gaussian/sub-Gaussian errors.Source: §B.2 · p. 31
  • The random-design sample-size scaling O(s log d) is better than the fixed-design scaling O(s^2 log d), because it ensures restricted strong convexity of Huber loss near β∗.Source: §B.2 · pp. 31–32
  • Theorem 8 also yields a prediction-error bound for the ℓ1-regularized Huber estimator with probability at least 1−5d^-1.Source: §B.2 · p. 32

C Proofs of Main Theorems

  • The proof framework defines the rescaled norm ∥u∥Σ,2 = ∥Σ^1/2u∥2 and develops auxiliary localized analyses for Huber loss.The auxiliary lemmas establish restricted strong convexity locally under both fixed and random designs.Source: C Proofs of Main Theorems · p. 32, §C.1 · pp. 32–33

C.1 Auxiliary Lemmas

  • For sparse high-dimensional analysis, the adaptive Huber loss satisfies restricted strong convexity over a localized ellipsoid intersected with an ℓ1-cone, with high probability.The proof controls the relevant empirical process using smoothing, Gaussian comparison, concentration, and union bounds.Source: §C.1 · pp. 38–39

C.2 Proof of Proposition 1

  • The proof of Proposition 1 separately controls Huber bias for 0 < δ < 1 and δ ≥ 1, using truncated-moment bounds and requiring sufficiently large τ.For 0 < δ < 1, the argument concludes the stated claim after bounding the two sides of the Huber-risk comparison; for δ ≥ 1 it uses finite variance and the same strategy.Source: §C.2 · pp. 41–42

C.3 Proof of Theorem 1 · C.4 Proof of Theorem 2

Theorem 1 is proved by localizing an intermediate Huber estimator and combining gradient concentration with curvature to recover the original estimator. Theorem 2 establishes the corresponding lower-bound transition using a paired-distribution construction, yielding the stated result for δ≤1 and completing δ>1 via finite second moments.

C.3 Proof of Theorem 1

  • Theorem 1 introduces an intermediate estimator constrained to a prescribed radius, then shows that sufficient control forces it into the ball’s interior and hence identifies it with the original Huber estimator.The construction uses bβτ,η = β∗ + η(bβ − β∗), with η chosen so the error is at most the target radius.Source: §C.3 · pp. 43–44
  • Theorem 1 combines the Karush-Kuhn-Tucker condition, the vector-valued mean value theorem, and coordinatewise control of the robust score to derive the estimator bound.The score vector is bounded through its coordinate maximum, with the dimension dependence entering via ∥ξ∗∥2 ≤ d^1/2∥ξ∗∥∞.Source: §C.3 · p. 43
  • For 0 < δ ≤ 1, the proof bounds each score coordinate by exponential tails when τ ≥ (vδn/t)^(1/(1+δ)).The argument applies Markov’s inequality after controlling the robust score’s moment-generating expression, obtaining one-sided bounds of the form e^(-vδnz/2).Source: §C.3 · pp. 43–44
  • Combining the concentration and curvature conditions gives the theorem’s high-probability conclusion with probability at least 1 − (2d + 1)e^−t.The proof invokes Lemma 3 to verify the required local condition with a0 = c_l/2.Source: §C.3 · p. 44

C.4 Proof of Theorem 2

  • Theorem 2 constructs paired response distributions that are usually zero but take opposite values with probability γ, while preserving a controlled (1 + δ)-th central moment.The construction uses independent pairs (y1i, y2i) and a sign vector u satisfying the design condition n^−1∥X^Tu∥min ≥ α.Source: §C.4 · p. 45
  • The lower-bound construction selects γ = log{1/(2ξ)}/(2n) and parameters aligned with u so the two models induce difficult-to-distinguish responses while separating their regression targets.The parameter choice sets c = c u, Xβ∗1 = cγ, and β∗2 = −β∗1.Source: §C.4 · p. 45
  • Taking log{1/(2ξ)} = 2t yields the stated lower-bound result for δ ∈ (0,1], while δ > 1 follows because the second moment exists and v1 is finite.The final step explicitly separates the heavy-tailed regime from the finite-second-moment case.Source: §C.4 · p. 46

C.5 Proof of Theorem 3 · C.6 Proof of Theorem 4

The proofs establish Theorem 3 through uniform Hessian control, an ℓ1-cone argument, and gradient concentration, while Theorem 4 uses a two-point construction to derive a heavy-tail lower bound.

C.5 Proof of Theorem 3

  • Uniform Hessian control follows from Hoeffding’s inequality under τ ≳ (1 + γ)2/(1+δ)κ−1/(1+δ) and n ≳ L4k2t, with an upper bound ⟨u, Hτu⟩ ≤ κu.These calculations complete the proof of the supporting Hessian lemma used in Theorem 3.Source: §C.5 · pp. 46–47
  • The estimator satisfies the ℓ1-cone condition ∥(bβ − β∗)Ec∥1 ≤ 3∥(bβ − β∗)E∥1 whenever ∥∇Lτ(β∗)∥∞ ≤ λ/2.This cone property is attributed to Fan et al. (2018) with a slight modification.Source: §C.5 · p. 47
  • Theorem 3’s proof reduces the claim to δ ∈ (0, 1] using an intermediate estimator constrained to an ℓ1-radius and cone.The construction sets bβη = β∗ + η(bβ − β∗), with η chosen so ∥bβη − β∗∥1 ≤ r.Source: §C.5 · p. 47
  • Gradient concentration uses τ = τ0(n/t)1/(1+δ), yielding P{∥∇Lτ(β∗)S∥∞ ≥ 2Lτn−1t} ≤ 2se−t.Taking t = (1 + c) log d gives probability at least 1 − (2s + 1)d−1−c and establishes the stated bound.Source: §C.5 · pp. 47–48

C.6 Proof of Theorem 4

  • Theorem 4’s proof constructs two response distributions P+ and P− from opposite s-sparse regression parameters, reducing estimation to distinguishing nearby alternatives.The alternatives satisfy β∗2 = −β∗1 and are linked through an s-sparse sign-ball construction.Source: §C.6 · p. 48
  • The lower-bound argument covers 0 < δ ≤ 1 by taking t = d−A/2, while δ > 1 follows because the second moment exists and v1 < ∞.The final step completes the proof across both moment regimes.Source: §C.6 · pp. 48–49
  • For any s-sparse estimator, the two-point construction bounds its performance through a testing inequality after choosing γ = log{1/(2t)}/(2n) with t ≥ e−n/2.The construction ensures 1 − γ ≥ 1/2.Source: §C.6 · pp. 48–49

C.7 Proof of Theorem 5

The proof follows Theorem 3, introducing truncated-predictor residual notation and deriving the required probability bound through Bernstein’s inequality and a union bound over S.

C.7 Proof of Theorem 5

  • The argument is almost identical to the proof of Theorem 3 and reduces the task to bounding the event involving ξ∗.The passage states that only this probability bound remains to be derived.Source: §C.7 · p. 49
  • The proof defines truncated covariates z_i and combines the original errors with their regression contribution as ϵ_i = ε_i + ⟨z_i, β∗⟩.It also introduces the restricted vector z_iS and expresses ξ∗ using this notation.Source: §C.7 · p. 49
  • For each fixed coordinate j, the proof applies Bernstein’s inequality to obtain the required concentration bound.The argument then considers all k ≥3.Source: §C.7 · p. 50
  • A union bound over j ∈ S yields probability at least 1 − 2se^−t for the stated bound, completing the proof.The final passage confirms that this is the theorem’s stated result.Source: §C.7 · p. 50

C.8 Proof of Theorem 7 … C.11 Proof of Corollary 1

These sections establish the stated results through deviation bounds, restricted strong convexity, Huber-bias control, cone arguments for sparse estimation, and a sub-Gaussian design specialization.

C.8 Proof of Theorem 7

  • Theorem 7 follows by combining gradient deviation inequalities and restricted strong convexity to control the intermediate estimator with probability at least 1 − 2e^−t when n ≥ C1(d + t).The proof obtains ||bβτ,η − β*||Σ,2 ≤ 4r0 < r under the stated sample-size condition.Source: §C.8 · pp. 50–51
  • To bound the supremum of the empirical process, the argument treats B(β) − E{B(β)} and E{B(β)} separately, applies Theorem A.3 in Spokoiny (2013), and combines the resulting bound with (61).Source: §C.8 · pp. 51–52

C.9 Proof of Proposition 2

  • Proposition 2 bounds the Huber score bias using tail moments, while integrating the tail contribution yields the stated second inequality involving τ^−κ E(η^(2+κ)).The score calculation applies for 2 ≤ q ≤ 2 + κ and uses E(ε) = 0.Source: §C.9 · pp. 52–53

C.10 Proof of Theorem 8

  • Theorem 8 uses an intermediate estimator and the optimality conditions of the ℓ1-penalized problem to place the estimation error in an ℓ1 cone.The cone argument relies on λ ≥ 2||∇Lτ(β*)||∞ and relates the error on the support of β* to its complement.Source: §C.10 · pp. 53–54
  • Theorem 8 calibrates λ and r using gradient concentration and restricted strong convexity, obtaining λ proportional to max_j σ_jj^1/2 τ0{(log d)/n}^{δ/(1+δ)} with probability at least 1 − 2d^−1.The proof then combines these calibrations with the construction of the intermediate estimator to conclude η = 1 on the stated event.Source: §C.10 · pp. 54–55

C.11 Proof of Corollary 1

  • For Corollary 1, the sub-Gaussian design is standardized so that the restricted-eigenvalue framework applies with s0 = s, k0 = 3, and K(s0, k0, A) = κ_l^−1/2.The argument invokes Theorem 16 of Rudelson and Zhou (2013) with δ = 1.Source: §C.11 · p. 55
  • The resulting high-probability design bound, together with inequalities (65) and (71), proves the stated corollary.The conclusion holds with probability at least 1 − 2d^−1 under the displayed bound involving max_j σ_jj and s log d.Source: §C.11 · p. 55

Related papers

Loading 1706.06991v2…