PaperlayerView exact revision on arXiv

Source-linked AI summary

High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing

David Donoho, Andrea Montanari

arXiv:1310.7320v3math.STcs.IT

TL;DR

The paper addresses why classical M-estimation theory can fail when the numbers of parameters and observations grow together. It rigorously analyzes the phenomenon with an AMP algorithm and State Evolution, showing that high-dimensional M-estimators contain persistent extra Gaussian noise and exhibit variance inflation. The paper also identifies scope boundaries in its current design assumptions.

  • Problem

    Classical formulas and Fisher-information-based inference may not describe M-estimators when p and n grow at the same rate.

  • Method

    The paper introduces AMP for M-estimation and uses State Evolution to characterize its iterations and asymptotic operating characteristics.

  • Results

    Variance inflation is at least (1 − 1/δ)^−1 when δ = n/p < ∞, and it diverges as δ → 1.

  • Takeaways & Limitations

    The rigorous AMP analysis explains extra Gaussian noise, effective noise, and effective scores in high-dimensional M-estimation, connecting them to related regularized least-squares phenomena.

  • Takeaways & Limitations

    The discussion identifies generalizing beyond Gaussian designs and the paper’s current design model as directions for future work.

Abstract

from arXiv · show

In a recent article (Proc. Natl. Acad. Sci., 110(36), 14557-14562), El Karoui et al. study the distribution of robust regression estimators in the regime in which the number of parameters p is of the same order as the number of samples n. Using numerical simulations and `highly plausible' heuristic arguments, they unveil a striking new phenomenon. Namely, the regression coefficients contain an extra Gaussian noise component that is not explained by classical concepts such as the Fisher information matrix. We show here that that this phenomenon can be characterized rigorously techniques that were developed by the authors to analyze the Lasso estimator under high-dimensional asymptotics. We introduce an approximate message passing (AMP) algorithm to compute M-estimators and deploy state evolution to evaluate the operating characteristics of AMP and so also M-estimates. Our analysis clarifies that the `extra Gaussian noise' encountered in this problem is fundamentally similar to phenomena already studied for regularized least squares in the setting n<p.

1 M-Estimation under high dimensional asymptotics

The paper studies M-estimation when parameters and observations grow together, a regime where classical variance formulas can fail. It rigorously characterizes the resulting extra Gaussian noise using AMP and State Evolution.

  • Motivation: When p and n grow at the same rate, M-estimator distributions need not follow classical fixed-p asymptotic formulas.This high-dimensional regime arises in applications with many explanatory variables, including bioinformatics, machine learning, imaging, and signal processing.
  • Main phenomenon: The effective error distribution equals the original noise convolved with an additional Gaussian component whose behavior depends on ψ, F_W, and δ.The effective score also differs from the original score under high-dimensional asymptotics, while both effective quantities recover their classical counterparts as δ tends to infinity.
  • Motivation: Classical maximum likelihood scoring and Fisher-information bounds can be inefficient or unattainable under high-dimensional asymptotics.The paper states that existing formulas are inadequate for confidence statements about high-dimensional M-estimates.
  • Proof strategy: The paper rigorously explains this phenomenon by introducing AMP, tracking its iterations with State Evolution, and linking its limit to the M-estimator.State Evolution is exact for each fixed iteration in the large-n limit, and AMP convergence transfers its asymptotic variance to the M-estimator.
  • Algorithm: The proposed AMP algorithm is a low-complexity first-order method for computing M-estimators in the random-design setting.Its fixed point is the M-estimator, and its converged score function is the effective score.
  • Interpretation: The extra noise remains nonzero at convergence and reflects cross-parameter estimation noise leakage between iterations.The analysis provides a unified interpretation connected to related high-dimensional regularized least-squares phenomena.

2 Approximate Message Passing (AMP)

The paper introduces AMP as an iterative algorithm for M-estimation, using effective score functions and adjusted residuals to connect AMP fixed points with M-estimator solutions. Under its stated assumptions, AMP converges rapidly to the M-estimator and supports state-evolution analysis.

  • Score functions: AMP uses a family of effective score functions Ψ(·; b), whose properties include strict monotonicity and contraction for b > 0.The effective score belongs to a family derived from the loss through a particular parameter choice.
  • AMP algorithm: The AMP iteration updates parameter estimates through adjusted residuals, effective-score calibration, and a scoring step.Adjusted residuals add Ψ(Rt−1; bt−1) to the ordinary residuals Y − Xbθt, while bt is selected to control the empirical average slope.
  • AMP algorithm: AMP fixed points correspond to minimizers of the M-estimation problem, and every minimizer corresponds to one or more AMP fixed points with b∗ > 0.The connection follows by showing that the fixed-point equations coincide with the M-estimator’s stationarity condition.
  • Example: 20 iterations in the example produced rapid convergence to the M-estimator, with RMSE(bθt; θ0) approaching 1.6182 and RMSE(bθt; bθ) approaching 0.The example used n = 1000, p = 200, Huber loss with λ = 3, and a contaminated-normal error distribution.
  • Relation to traditional methods: High-dimensional AMP requires numerous iterations and memory terms, unlike classical fixed-p asymptotics where a single step can suffice.The memory terms are required by the statistical assumptions on the random design for state-evolution analysis.

3 State evolution description of AMP

State Evolution tracks AMP through scalar variance and score-parameter recursions, predicting finite-iteration and limiting operating characteristics in high-dimensional Gaussian designs. The tracked variance represents extra Gaussian noise that remains nonzero at convergence and supports predictions for coefficient and residual observables.

  • State Evolution framework: State Evolution computes AMP operating characteristics at fixed iterations and in the high-dimensional limit n, p →∞ with n/p →δ.It assigns predictions to observables involving coefficient errors and adjusted residuals.
  • State Evolution framework: AMP adjusted residuals are modeled as W + τ_t Z, where τ_t^2 quantifies extra Gaussian noise beyond the error distribution.The Gaussian variable Z is independent and standard normal under the formal procedure.
  • State Evolution recursion: A stable fixed point τ* exists, and the example's variance trajectory converges to a nonzero value near 0.472.The fixed point is associated with a map derivative below 1 and is shown as the limit of the iteration history.
  • Predicted observables: State Evolution predicts MSE, MAE, and limiting ordinary-residual distributions from the AMP state, including η(W + τ*Z; b*).For the running example, ten simulations produced empirical observable averages very close to the theoretical predictions.
  • Validation: The formal predictions are rigorously validated for pseudo-Lipschitz observables at fixed iteration t under the stated random Gaussian design assumptions.The validation concerns independent W∼F_W and Z∼N(0,1).

4 Convergence and characterization of M-estimators

Under strongly convex losses and δ>1, AMP converges to the M-estimator, allowing State Evolution to characterize its effective error distribution and asymptotic variance. The resulting variance is inflated relative to the classical information bound in high-dimensional asymptotics.

  • Convergence: AMP iterates converge to the M-estimator in the high-dimensional limit under strongly convex ρ and δ>1, for suitable initial conditions.The paper notes that convergence from arbitrary independent initial conditions is expected but not proved.
  • Estimator characterization: The M-estimator's effective error distribution is the original noise distribution convolved with an extra Gaussian component of nonzero variance.The extra variance depends on ψ, F_W, and δ and is characterized by the fixed-point equations.
  • Asymptotic variance: The high-dimensional asymptotic variance obeys V(˜Ψ, ˜F) ≥ (1 − 1/δ)^−1 · 1/I(F_W), rather than the classical information bound alone.The factor is a lower-bound inflation relative to 1/I(F_W).
  • Asymptotic variance: For finite δ, the classical information bound is unattainable; the minimum variance inflation is n/(n−p), which diverges as δ→1.This conclusion follows from the positive equilibrium noise level.
  • Finite-iteration performance: The analysis also bounds finite-iteration AMP suboptimality by comparing the asymptotic MSE of AMP at iteration t with that of the converged M-estimator.The stated result applies under strong convexity and δ>1.
  • General Gaussian designs: The characterization extends to general Gaussian designs with covariance Σ, where a scalar random variable T_n converges almost surely to the State Evolution limit τ*.The extension assumes strongly convex ρ and δ>1.

5 Discussion

The discussion positions the proof strategy within AMP and high-dimensional convex-optimization work while identifying several directions for extending the theory. These include broader designs, less restrictive losses, regularization, and alternative proof approaches.

  • Open extensions: Potential extensions include randomly scaled Gaussian rows, removal of smoothness and strong convexity, and convex regularization such as ℓ1 penalties.The paper lists these as generalizations of increasing difficulty.
  • Open extensions: The authors expect suitable universality results for non-Gaussian designs with i.i.d. entries under moment conditions, but this remains a proposed extension.A related universality result is cited for compressed sensing.
  • Alternative approaches: Alternative statistical-mechanics and Bayesian AMP proof perspectives are identified as worthwhile directions for studying the minimizer and related regression models.The statistical-mechanics approach discussed estimates a partition function, while the Bayesian work considers a similar regression model.

6 Duality between robust regression and regularized least squares

The section establishes a duality between robust M-estimation with p<n and a related regularized least-squares problem with more predictors than observations. In the Huber-Lasso case, the correspondence is exact and interprets sparse penalized regression as identifying outliers.

  • General duality: M-estimation with p<n can be reformulated as a related penalized regression problem in an underdetermined regime.The construction sets ˜n=n−p and ˜p=n, then links the transformed data and design matrix to the original regression problem.
  • General duality: An orthonormal-row matrix eX with eXX=0 and transformed response eY=eXY establishes the dual pair.The null-space and image conditions connect the original design matrix to the transformed underdetermined problem.
  • The Lasso-Huber connection: For J(x)=λ|x|, the regularized problem is the Lasso and its associated robust loss is the Huber loss.The optimal values of the Lasso and Huber problems are identical, and their solutions are in one-to-one relation.
  • The Lasso-Huber connection: The Lasso solution can be viewed as finding outliers, after which robust regression becomes least squares on data adjusted to remove them.This interpretation connects sparse coefficient recovery in compressed sensing with identifying contaminated observations in robust regression.
  • General duality: The regularized least-squares and robust-regression solutions correspond one-to-one under the stated convex-loss and matrix assumptions.The mappings are bβ=Y−Xbθ−u and bθ=(XTX)^−1XT(Y−bβ), with u constrained by the null space and subgradient.
  • The Lasso-Huber connection: The Huber state-evolution recursion is very close to the compressed-sensing recursion for reconstructing sparse signals from underdetermined measurements.The analogy is suggestive because compressed sensing locates nonzero coefficients whereas robust regression identifies outliers.

A Properties of the functions Prox, Ψ

This appendix establishes regularity properties of the proximal and residual nonlinearities used in the AMP analysis. Under smooth convexity assumptions, both functions are differentiable, increasing, and Lipschitz, with derivative bounds for Ψ.

  • Assumptions: The appendix assumes a convex, bounded-below function ρ with bounded second derivative.These assumptions support differentiability and continuity arguments for Prox and Ψ.
  • Prox properties: For b>0, Prox(z;b) is uniquely defined and differentiable because its defining optimization objective is strongly convex.The implicit-function theorem supplies differentiability over the domain.
  • Prox properties: For fixed b, Prox(z;b) is strictly increasing and Lipschitz continuous in z.Its regularity is controlled by the uniform bound on ρ′′.
  • Ψ properties: For fixed b, Ψ(z;b) is strictly increasing and Lipschitz continuous.Its derivative is bounded between expressions involving the infimum and supremum of ρ′′.
  • Existence result: The state-evolution parameter b_t has at least one positive solution for each fixed τ.The proof uses continuity of an auxiliary function and its limits as b approaches zero and infinity.

B Proof of correctness of State Evolution (Theorem 3.9)

The proof of State Evolution correctness reduces the AMP recursion to a generalized AMP system already covered by prior theory. Variable correspondences and recentering then transfer the established state-evolution result to the algorithm studied here.

  • Recursion setup: The proof defines b_t recursively and represents the AMP updates through vector nonlinearities applied coordinatewise.The system uses vectors q_t and m_t together with scalar parameters and a rectangular Gaussian design matrix.
  • Recursion setup: Recentering the data and iterates converts the AMP trajectory into variables centered around the true parameter and noise.The transformed trajectory satisfies a corresponding recentered recursion.
  • Reduction to known AMP theory: A modified recursion differs only through the coefficient q_t, while its benefit is that State Evolution is already known to be correct for that form.The reduction introduces iterates approximating the recentered AMP iterates.
  • Reduction to known AMP theory: The generalized AMP framework provides the correctness result after establishing correspondence between the paper’s variables and the earlier recursion.The cited theorem includes the transformed recursion as a special case.
  • Conclusion: Theorem 3.9 follows from equivalence between the two recursive systems.The proof identifies the nonlinearities and parameters so the state-evolution conclusions transfer directly.

B.1 Proof of Lemma B.2 (Equivalence of recursions)

This proof compares the original recentered AMP recursion with an auxiliary recursion and controls their discrepancy using Lipschitz bounds. Iteration and State Evolution then yield the required asymptotic equivalence.

  • Recursion comparison: The auxiliary recursion is compared term by term with the recentered AMP iterates.The comparison uses the Lipschitz continuity of Ψ and triangular-inequality bounds.
  • Recursion comparison: Iterating the discrepancy bounds gives a finite constant A=A(δ) controlling the approximation error.The bound uses the aligned initial condition of the two recursions.
  • State-evolution transfer: State Evolution supplies almost-sure limits for the auxiliary recursion under the assumptions of Theorem 3.9.The argument applies the established lemma to the relevant nonlinear function, including a bounded noncontinuous derivative case.
  • State-evolution transfer: Random-matrix spectral-norm control completes the limit passage and bounds the remaining error term.The operator norm of X converges to a finite constant C(δ), while the residual term is controlled by the earlier discrepancy estimate.

C Proof that AMP converges to the M-estimator (Theorem 4.1)

The proof establishes convergence by tracking the AMP iterates through a recursively defined covariance matrix and controlling the loss gradient using strong convexity and concentration. Gaussian covariance identities then connect the recursion to the required limiting claim.

  • Covariance structure: The proof defines a doubly infinite matrix Γ recursively from the fixed-point solution (τ∗, b∗).Γ is symmetric, has Γt,t = τ∗^2, and satisfies Γ0,t = Γt,0 = 0 for t > 0.
  • Gaussian characterization: Lemma C.1 characterizes Γt,s through expectations over jointly Gaussian variables with covariance determined by Γ.The result is applied to the AMP recursion to obtain the needed asymptotic identities.
  • Gradient control: Strong convexity and Wishart singular-value concentration provide constants controlling the loss geometry when δ > 1.The argument uses the minimum non-zero singular value of X and applies Cauchy–Schwarz to bound the relevant terms.
  • Convergence argument: The final step rewrites the AMP update using Ψ(z; b∗) = z − Prox(z; b∗) and bounds successive residual differences using smoothness.The bound combines the iteration difference, the residual difference, and the operator norm of X before identifying the result with the loss gradient.
  • Convergence argument: The resulting limit is equivalent to the target claim because ∇θL(θ) = −Xρ′(Y − Xθ).This completes the proof of Theorem 4.1.

C.1 Proof of Lemma C.1

The proof reduces the AMP iteration to a separable vector recursion with a symmetric Gaussian matrix, then invokes an established state-evolution characterization. This identifies empirical limits through Gaussian test variables with the covariance specified by the recursion.

  • Reduction to state evolution: The proof uses an alternative reduction to the framework of [JM12], paralleling a characterization previously used for the Lasso.The reduction is applied after fixing an even vector dimension q and a finite time horizon T.
  • Vector construction: The AMP variables are assembled into vectors zt ∈ (R^q)^N whose entries encode the iteration coordinates for samples and parameters.The construction separates the first n sample-related entries from the remaining p parameter-related entries.
  • Vector construction: A symmetric matrix A with Gaussian off-diagonal entries represents the design interaction, making the AMP iteration equivalent to a vector recursion.The matrix has zero diagonal and embeds the rectangular design matrix X in its cross-block entries.
  • Separable recursion: The recursion is separable because its update map acts coordinatewise as f(z; t) = (f1(z1; t), …, fN(zN; t)).The component maps differ for sample indices and parameter indices, as specified by the corresponding Ψ and linear terms.
  • State evolution: The established recursion theorem gives almost-sure empirical limits for pseudo-Lipschitz functions of the iterates, represented by Gaussian vectors Zt.The proof finishes by comparing the covariance formulas from [JM12] with those in the lemma.

C.2 Proof of Lemma C.2

The proof analyzes a scalar Gaussian expectation function to establish monotonicity and strict convexity properties, then uses these properties to characterize the long-run covariance behavior of the AMP recursion.

  • Gaussian scalar analysis: The proof studies H(q) using a centered Gaussian pair with unit variances and correlation q, independent of W.This scalar function is used to derive the required covariance properties.
  • Convexity: H(q) is strictly convex on [0, 1].The proof establishes this by showing that H is strictly increasing and convex for each fixed W, then averaging over W.
  • Boundary behavior: H(q) equals 1 at q = 1 because the fixed-point parameters b∗ and τ∗ satisfy Eq. (24).At q = 1, the two Gaussian variables coincide.
  • Convexity: Strict convexity follows from the Ornstein–Uhlenbeck representation when hW is nonlinear, because at least one coefficient cℓ is nonzero for some ℓ ≥ 2.This supplies the nonlinearity condition needed for strictness.
  • Long-run covariance: The proof concludes that limt→∞ qt = 1, with the corresponding neighboring covariance converging to τ∗^2.The final inequality uses Ψ′(z; b) ∈ (0, 1), so (Ψ′)^2 ≤ Ψ′, together with the fixed-point equation.
Loading 1310.7320v3…