OpenFrontiers
Join
← Back to the index
OP-1651OpenHigh-dimensional statistics

Mean field asymptotics in high-dimensional statistics From exact results to efficient algorithms · 2018-stat-13

Linear Inference and Regression · ICM 2018: Mean field asymptotics in high-dimensional statistics From exact results to efficient algorithms

MSC 62 · Statistics

Inferred from the community field; finer classification has not been reviewed.

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Fix λ>0\lambda>0 and consider a sequence of high-dimensional linear models

y=Xθ0+w,\boldsymbol y=\boldsymbol X\boldsymbol\theta_0+\boldsymbol w,

where X∈Rn×d\boldsymbol X\in\mathbb R^{n\times d}, n/d→δ∈(0,∞)n/d\to\delta\in(0,\infty), the coordinates of w\boldsymbol w are independent N(0,σ(n)2)N(0,\sigma(n)^2) random variables with σ(n)/n→σ0\sigma(n)/\sqrt n\to\sigma_0, and the empirical distribution d−1∑j=1dδθ0,jd^{-1}\sum_{j=1}^d\delta_{\theta_{0,j}} converges in Wasserstein-kk distance to the law of a random variable Θ\Theta. Define the Lasso estimator

θ^(λ)=argminθ∈Rd{12n∥y−Xθ∥22+λ∥θ∥1},\widehat{\boldsymbol\theta}(\lambda) =\mathop{\rm argmin}_{\boldsymbol\theta\in\mathbb R^d} \left\{\frac{1}{2n}\|\boldsymbol y-\boldsymbol X\boldsymbol\theta\|_2^2 +\lambda\|\boldsymbol\theta\|_1\right\},

the soft-thresholding function

η(u;a)=argminv∈R{12(u−v)2+a∣v∣}=sign⁡(u)(∣u∣−a)+,\eta(u;a)=\mathop{\rm argmin}_{v\in\mathbb R} \left\{\frac12(u-v)^2+a|v|\right\} =\operatorname{sign}(u)(|u|-a)_+,

and, for a>0a>0, the debiased estimator

θ^d(a,λ)=θ^(λ)+anλXT(y−Xθ^(λ)).\widehat{\boldsymbol\theta}^{\rm d}(a,\lambda) =\widehat{\boldsymbol\theta}(\lambda) +\frac{a}{n\lambda}\boldsymbol X^{\mathsf T} (\boldsymbol y-\boldsymbol X\widehat{\boldsymbol\theta}(\lambda)).

For a design matrix with independent standard Gaussian entries, let (α∗,τ∗)∈(0,∞)2(\alpha_*,\tau_*)\in(0,\infty)^2 be the unique solution of

λ=α∗[1−1δP(∣Θ+τ∗Z∣≥α∗)],τ∗2=σ02+1δE[(η(Θ+τ∗Z;α∗)−Θ)2],\lambda=\alpha_*\left[1-\frac1\delta \mathbb P\bigl(|\Theta+\tau_*Z|\geq\alpha_*\bigr)\right], \qquad \tau_*^2=\sigma_0^2+\frac1\delta \mathbb E\left[\bigl(\eta(\Theta+\tau_*Z;\alpha_*)-\Theta\bigr)^2\right],

where Z∼N(0,1)Z\sim N(0,1) is independent of Θ\Theta. In this Gaussian case, for every pseudo-Lipschitz function ψ:R2→R\psi:\mathbb R^2\to\mathbb R of order kk,

1d∑j=1dψ(θ0,j,θ^jd(α∗,λ))→a.s.E[ψ(Θ,Θ+τ∗Z)].\frac1d\sum_{j=1}^d \psi\left(\theta_{0,j},\widehat\theta^{\rm d}_j(\alpha_*,\lambda)\right) \xrightarrow{\rm a.s.} \mathbb E\bigl[\psi(\Theta,\Theta+\tau_*Z)\bigr].

Characterize the random-matrix ensembles with non-independent or non-identically distributed entries for which this same asymptotic characterization remains valid. For ensembles for which the Gaussian prediction is not unchanged, determine the corresponding generalized asymptotic law of the Lasso and its debiased estimator.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗
Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

Let p/n→κ∈(0,∞)p/n\to\kappa\in(0,\infty) and consider linear models Y=Xβ0+ξ\boldsymbol Y=\boldsymbol X\boldsymbol\beta_0+\boldsymbol\xi, where the rows of X∈Rn×p\boldsymbol X\in\mathbb R^{n\times p} are independent, centered, isotropic sub-Gaussian vectors. Suppose that, within each row, the coordinates admit a dependency graph of maximum degree qpq_p: whenever two disjoint sets of coordinates have no edge between them, the corresponding coordinate families are independent. Unlike block dependence, do not assume that this graph is a disjoint union of uniformly small complete subgraphs. Determine growth conditions on qpq_p and suitable moment and regularity assumptions under which the optimal regularized empirical risk and the normalized estimation error of the Lasso have the same high-dimensional limits as for a design matrix with independent Gaussian entries having the same covariance.

Source reference: Samriddha Lahiry and Pragya Sur, “Universality in Block Dependent Linear Models With Applications to Nonlinear Regression,” IEEE Transactions on Information Theory 70(12) (2024), 8975–9000, Section VIII (Discussion), second proposed direction for future work. DOI: 10.1109/TIT.2024.3481956; arXiv:2401.00344.

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

The problem is unresolved. It asks for a characterization of all non-i.i.d. design ensembles for which the i.i.d.-Gaussian Lasso/debiased-Lasso limit remains valid, together with the correct generalized law whenever it does not. The literature establishes universality or exact asymptotics for several important, but non-exhaustive, classes. No known theorem gives necessary and sufficient conditions covering arbitrary dependent or non-identically distributed designs, and the existing generalized laws depend on additional structural hypotheses.

  • “Universality of Regularized Regression Estimators in High Dimensions,” Qiyang Han and Yandi Shen, Annals of Statistics 51(4), 2023, DOI: 10.1214/23-AOS2309. Theorems 2.3–2.5 give a Lindeberg-type structural universality principle for convex regularized regression with independent, moment-matched design entries. Theorems 3.6, 3.8, and 3.9 apply it to Lasso risk and structural properties of the Lasso optimizer under tail, regularization, and localization assumptions. This rigorously extends Gaussian predictions to broad non-Gaussian independent-entry designs, but not to general dependence among entries.

  • “The Lasso with General Gaussian Designs with Applications to Hypothesis Testing,” Michael Celentano, Andrea Montanari, and Yuting Wei, Annals of Statistics 51(5), 2023, DOI: 10.1214/23-AOS2327; arXiv:2007.13716. This paper gives a precise high-dimensional characterization of the Lasso for Gaussian rows with a general nonsingular covariance matrix and derives the corresponding degrees-of-freedom-corrected debiased-Lasso distribution. It supplies a genuine generalization of the i.i.d.-Gaussian formula for correlated Gaussian designs, but it does not establish universality over arbitrary non-Gaussian designs with that covariance.

  • “Spectral Universality in Regularized Linear Regression With Nearly Deterministic Sensing Matrices,” Rishabh Dudeja, Subhabrata Sen, and Yue M. Lu, IEEE Transactions on Information Theory 70(11), 2024, 7923–7951, DOI: 10.1109/TIT.2024.3458953; arXiv:2208.02753. The paper defines spectral universality classes and proves identical asymptotic first-order-method dynamics across matrices in a class. Under additional strong-convexity or spectral-gap hypotheses it also proves universality of convex regularized least-squares estimators. The classes include rotationally invariant matrices, randomly signed incoherent frames, subsampled Hadamard-type transforms, and other strongly correlated or nearly deterministic designs. The required genericity and sign-invariance conditions are sufficient rather than a complete characterization, and the estimator theorem does not cover every non-strongly-convex Lasso regime.

  • “Universality in Block Dependent Linear Models With Applications to Nonlinear Regression,” Samriddha Lahiry and Pragya Sur, IEEE Transactions on Information Theory 70(12), 2024, 8975–9000, DOI: 10.1109/TIT.2024.3481956; arXiv:2401.00344. Theorem 4.1 and its corollaries prove universality of the optimal regularized empirical risk and estimation risk for Lasso and ridge under sub-Gaussian block-dependent designs, initially with a restricted covariance structure. This goes beyond independent entries and rotational invariance, but it primarily identifies risk limits rather than the full coordinatewise law of the Lasso and debiased estimator in the statement.

  • “Universality of Estimators for High-Dimensional Linear Models with Block Dependency,” Toshiki Tsuda and Masaaki Imaizumi, Bernoulli 32(3), 2026, 2001–2021, DOI: 10.3150/25-BEJ1941; arXiv:2410.19244. Theorems 1 and 3 establish universality of convex empirical-risk minimizers under block dependence and general covariance by comparison with a moment-matched Gaussian design; the applications include Lasso and ridge estimation-error limits. This resolves important covariance-plus-block-dependence cases left open by earlier work, but still assumes a specific block structure and does not classify general local, global, or adversarial dependence, nor does it derive the full debiased-Lasso empirical law for every such ensemble.

Thus, substantial universality and generalized-asymptotic results are known for independent entries, correlated Gaussian rows, block-dependent covariates, rotationally invariant designs, and several structured spectral ensembles. What remains open is the requested exhaustive characterization beyond these classes and a unified generalized limiting law, especially for broad dependence structures and for the full coordinatewise joint law of the Lasso and its debiased version.

References
  1. [1]ICM Conjectures · 2018-stat-13 link
  2. [2]ICM 2018: Mean field asymptotics in high-dimensional statistics From exact results to efficient algorithms link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.