Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results

1 Introduction

• Random-matrix and concentration ideas, implemented through leave-one-out, martingale, and concentration arguments, rigorously justify claims from El Karoui et al. (2012) and El Karoui et al. (2013).The proof also draws on tools used in random-matrix spectral analysis.Source: §1 · p. 2
• Concentration assumptions permit some results without entrywise i.i.d. designs, but the main result requires i.i.d. entries that need not be Gaussian.This differs from the cited Donoho and Montanari approach, which assumes an i.i.d. Gaussian design.Source: §1 · p. 2

1.1 Focus of the paper

• Under the theorem’s assumptions with τ > 0, the asymptotic results include convergence of ||βhat|| to rρ(κ).The theorem considers p, n tending to infinity with p/n → κ ∈ (0, ∞).Source: §1.1 · p. 3

Remarks on the assumptions

• The error-tail assumptions are somewhat restrictive, and understanding how heavy-tailed errors can be while retaining the result is left for future work.The authors describe their growth conditions on ρ and ψ as relatively unrestrictive and note that stronger growth restrictions could allow fewer error moments.Source: Remarks on the assumptions · p. 4
• Assumption O4 is stronger than needed; considering weaker concentration bounds was omitted because extra bookkeeping would not sufficiently expand the distributions covered.The authors state that many natural distributions satisfy O4.Source: Remarks on the assumptions · p. 4

Notations

• The notation defines polyLog(n) as a power of log(n), λmax(M) as the largest eigenvalue, and |||M|||2 as the largest singular value.The text also defines βhat(i) as the estimate obtained after omitting observation i.Source: Notations · p. 4

2.1 General remarks

• Strong convexity with modulus C gives the comparison matrix a lower bound of Cλmin(Σhat) + τ, supporting control of differences between estimator vectors.Convexity alone gives the lower bound τ; strong convexity supplies the additional curvature term.Source: §2.1 · p. 5
• Strong convexity is a restrictive condition in statistics, and some situations may permit relaxing it for the unpenalized estimator.The text points to sufficient ψ′ over a set of indices as a possible route.Source: §2.1 · p. 6

2.2 Boundedness of ∥bβ∥

• The preliminaries develop multiple bounds on ||βhat||, with the bound based on Equation (9) particularly helpful when errors may be heavy-tailed and ψ is bounded, as with Huber functions.A similar result in L2k holds when the entries of Xi have cumulants of order 2k.Source: §2.2 · p. 6

3 Approximating bβ by bβ(i): leave-one-observation-out

• When 1/c_n=polyLog(n), the leave-one-out approximation is accurate to order polyLog(n)/n in Euclidean norm.The paper introduces the leave-one-out estimate and motivates the approximation using probabilistic heuristics developed in earlier work.Source: §3 · p. 7

3.1.1 On Ri

• Under the stated Lipschitz assumption on ψ′, the argument obtains a bound for ∥R_i∥.The authors note that the Lipschitz condition could be replaced by a modulus-of-continuity condition with a growth constraint.Source: §3.1.1 · pp. 9–10

3.2.2 Control of the residuals Ri and ˜ri,(i)

• For |ψ(x)|=O(|x|^m), the residual bound is related to the leave-one-out residual bound, but the authors call this estimate coarse.The bound also relies on control of the predictor norms under the stated assumptions.Source: §3.2.2 · p. 12

3.3 Asymptotically deterministic character of ∥bβ∥2

• The squared norm ∥bβ∥² has a deterministic equivalent in probability and in L2.The proof uses the Efron–Stein inequality.Source: §3.3 · p. 14

4.2 Probabilistic aspects

• Formalizing the predictor-deletion heuristics requires independent design entries, whereas the leave-one-observation analysis does not require that condition.The paper limits this analysis to the null case β0=0.Source: §4 · p. 15, §4.2 · p. 18

4 Leaving out a predictor

• The predictor-leaving-out estimator eb is a √n-consistent approximation of bβ in Euclidean norm, enabling insights about its last coordinate to transfer to bβ_p.The last coordinate has a simpler probabilistic structure, and the approximation is sufficiently accurate for this transfer.Source: §4 · p. 15

4.1 Deterministic aspects

• The proof approximates f(eb) by g(bγ), where bγ is fitted using the design with the p-th predictor omitted.The strategy first controls f(eb) through this reduced-model quantity.Source: §4 · p. 15, §4.1 · p. 16

4.2.1 On bp

• With the p-th design column independent of the remaining predictors and errors, the paper controls the reduced-model coefficient bp.The section uses this independence in its probabilistic analysis of bp.Source: §4.2 · p. 18, §4.2.1 · p. 19

4.2.2 On ξn; 4.2.4 Control of ξn and bp

• The analysis establishes ξ_n≥0 and uses this property in controlling ξ_n and bp.The positivity follows from the matrix argument in the section.Source: §4.2.1 · p. 19, §4.2.2 · p. 20, §4.2.4 · p. 22

4.2.3 Control of Kn

• The coordinate-specific quantities satisfy sup_i |c_i−c_τ|=O(n^-1/2 polyLog(n)).The paper identifies c_i as analogous to c_τ,p when all predictors are used.Source: §4.2.3 · p. 22

5.1 On the asymptotic distribution of ˜ri,(i)

• Leave-one-out residuals ˜ri,(i) and ˜rj,(j) are asymptotically independent because their shared dependence runs through an asymptotically deterministic norm.Source: §5.1 · pp. 25–26
• The empirical distribution of the residuals Ri is asymptotically non-random.Source: §5.1 · p. 26

. Call as before

• Under F1, Δn(x) = 0 has a unique solution, making cτ asymptotically deterministic and yielding the first equation of Theorem 1.1.The second equation comes from Equation (35).Source: . Call as before · pp. 29–30

6 From the ridge-regularized to the un-regularized problem

• When lim sup p/n < 1, the unregularized estimator’s norm is asymptotically deterministic and can be computed via the theorem’s system.Source: §6 · p. 31
• As τ → 0, the ridge-regularized estimator converges in probability to the unregularized estimator under the paper’s assumptions.Source: §6 · p. 32

6.1 Other extensions

• The analysis does not fully work out elliptical designs of the form ˜Xi = λiXi, citing added notational burden.The authors describe this extension as conceptually straightforward to adapt.Source: §6.1 · p. 32
• Weighted regression and models combining elliptical designs with potentially different loss functions are presented as extensions within reach of the method.Source: §6.1 · p. 32

• For twice-differentiable convex ρ, the appendix states a bound for the proximal mapping when c > 0.The supplied passage introduces Lemma A-2 but does not include the bound itself.Source: A Notes on the prox · p. 33
• When ψ changes sign at zero as its argument does, c ↦ ρ(prox_c(ρ)(x)) is decreasing in c.Source: A Notes on the prox · p. 33
• For any u, x ↦ [xψ(prox_x(ρ)(u))]^2 is increasing on R+.Source: A Notes on the prox · p. 34

• Under the stated concentration property for independent Xi, Lemma B-1 provides a bound for convex 1-Lipschitz functions of Xi.Source: B On convex Lipschitz functions of… · pp. 34–35
• When Cn is bounded independently of n, Fn/un is bounded by a constant with overwhelming probability.Source: B On convex Lipschitz functions of… · p. 34
• The techniques can extend to tails of the form P(|Fi(Xi)−mi| ≥ t) ≤ Cn exp(−cnt^α), with the bounds’ orders changing.Source: B On convex Lipschitz functions of… · p. 34

On the spectral norm of covariance matrices

• An adapted epsilon-net argument, following Talagrand (2003), Appendix A.4, yields the stated control.The argument handles u in R^n and v in R^p.Source: On the spectral norm of covariance… · p. 38
• The lemma controls the spectral norm of the sample covariance matrix for independent, mean-zero vectors with identity covariance satisfying O4 concentration assumptions.The proof studies the largest singular value of X/√n.Source: On the spectral norm of covariance… · p. 38
• The results also hold in Lk.The text says this follows simply from the proof.Source: On the spectral norm of covariance… · p. 38
• When cn ≠ 1, the moment-generating function of u′Xv is smaller than that of a Gaussian with variance 1/cn; when cn = 1, u′Xv is itself subGaussian with variance 1.Source: On the spectral norm of covariance… · p. 38

An analytic remark

• The authors present the uniqueness condition as applying to problems of interest to statisticians.They describe the conditions on W's density as mild.Source: An analytic remark · p. 38
• The uniqueness result assumes W has a smooth density decreasing away from zero and ψ preserves the sign of its argument.The lemma also assumes lim|t|→∞ tf(t) = 0.Source: An analytic remark · p. 38
• F(x) = 0 has a unique root because F is decreasing, F(0) = p/n, and F(x) tends to −∞ as x grows.The text gives F′(x) = −τ + G′(x) < 0.Source: An analytic remark · p. 39
• The density conditions include W = ε + rZ when ε is symmetric and log-concave, Z is standard Gaussian, and r > 0.The text says similar results hold under weaker assumptions on ε.Source: An analytic remark · p. 39

A linear algebraic remark

• The cited lemma assumes a positive semi-definite p × p matrix A; for strictly positive real τ, it defines Γτ = Γ + τIdp−1.Source: A linear algebraic remark · p. 39
• For positive definite A, the Schur complement gives a ≥ v′Γ−1v > v′Γ−1_τv.The proof also invokes block inversion and the Sherman-Morrison-Woodbury formula.Source: A linear algebraic remark · p. 39
• The positive-semidefinite case follows from the positive-definite case by replacing A with A + εIdp and letting ε tend to zero.Source: A linear algebraic remark · p. 39