Home / Curated / Mathematical Methods / Cone Invertibility Factor Oracle Inequalities and Rate Minimaxity of LASSO and Dantzig Selector in Lq Loss

Cone Invertibility Factor Oracle Inequalities and Rate Minimaxity of LASSO and Dantzig Selector in Lq Loss

Mathematical Methods AIMech:ConeInvertibilityFactorOracleInequalitiesAndRateMinimaxityOfLassoAndDantzigSelectorInLqLoss DRAFT

Aliases: Cone Invertibility Factor (CIF) and Sign-Restricted CIF (SCIF), Ye-Zhang Cone Invertibility Factor and Lq Minimax Oracle Inequalities, Sign-Restricted Cone Invertibility Factor (SCIF) for LASSO and Dantzig Selector, Thresholded LASSO and Thresholded Dantzig Selector via L_infinity CIF Bounds

A sharp non-asymptotic Gram-matrix invertibility and minimax estimation framework (introduced by Fei Ye and Cun-Hui Zhang in 2010) that unifies and sharpens $\ell_q$-loss ($1 \le q \le \infty$) oracle inequalities for the LASSO and Dantzig selector across $\ell_0$ and weak/strong $\ell_r$ balls ($0 \le r \le 1$) via the Cone Invertibility Factor (CIF) $F_q(\xi, S) = \inf\left\{\frac{|S|^{1/q}\|\Sigma u\|_\infty}{\|u\|_q} : u \in \mathscr{C}(\xi, S) \setminus \{0\}\right\}$ and the Sign-Restricted Cone Invertibility Factor (SCIF) $SCIF_q(\xi, S) = \inf\left\{\frac{|S|^{1/q}\|\Sigma u\|_\infty}{\|u\|_q} : u \in \mathscr{C}_-(\xi, S) \setminus \{0\}\right\}$ on the sign-restricted cone $\mathscr{C}_-(\xi, S) = \{u : \|u_{S^c}\|_1 \le \xi\|u_S\|_1,\, u_j(\Sigma u)_j \le 0\, \forall j \notin S\}$ ($\Sigma = X^\top X / n$). Because the KKT and Dantzig score-dominance condition $\|z^*\|_\infty \le \eta$ ($z^* = X^\top(y - X\beta^*)/n$) automatically forces the estimation error $\delta = \hat{\beta} - \beta^*$ of both LASSO (with $\xi = (\lambda + \eta)/(\lambda - \eta)$) and the Dantzig selector (with $\xi = (\lambda_D + \eta)/\lambda_D$) into $\mathscr{C}_-(\xi, S)$ while bounding $\|\Sigma\delta\|_\infty \le \lambda + \eta$, SCIF yields the direct single-factor oracle bound $\|\hat{\beta} - \beta^*\|_q \le \frac{(\lambda + \eta)|S|^{1/q}}{SCIF_q(\xi, S)}$ (Theorem 3, Eq. 20) without squaring a restricted eigenvalue or multiplying two separate Gram invertibility constants, and matches the universal design-independent minimax lower bound $R_q^*(\mathscr{B}_r(\rho)) \asymp \rho^{q(1-1/t)}(\sigma^2\log(p/\tau_*)/n)^{q/(2t)}$ ($1/t = 1 - r/q$) across all $0 \le r \le 1 \le q \le \infty$ alongside thresholded LASSO ($\hat{\beta}^{TL}$) and Gauss-Dantzig ($\hat{\beta}^{GD}$) sign consistency under $q = \infty$.

Identity Notes & Concept Scope Resolved against all 442 pinned AIO concepts and 659 maintained AIMech concepts. Distinct from `AIMech:RestrictedEigenvalueConditionAndBickelRitovTsybakovSimultaneousLassoDantzigOracleBounds` (Bickel, Ritov, & Tsybakov 2009, which defines the $\ell_2$ quadratic-form Restricted Eigenvalue $\kappa(s, c_0) = \min_{\delta \in \mathscr{C}(c_0, S)} \|X\delta\|_2 / (\sqrt{n}\|\delta_S\|_2)$ whose $\ell_q$ error bounds scale with $1/\kappa^2$ and an extra $(1+c_0)^{2-2/q}$ factor, whereas Ye & Zhang 2010 introduce the $\ell_\infty$-score-to-$\ell_q$ Cone Invertibility Factor $F_q(\xi, S)$ and Sign-Restricted Cone Invertibility Factor $SCIF_q(\xi, S)$ on $\mathscr{C}_-(\xi, S)$, proving $SCIF_2(\xi, S) \ge \psi(\xi, S)^2 \ge \kappa^2$ and eliminating the two-factor product gap as well as establishing universal design-free minimax lower bounds in $\ell_r$ balls for $0 \le r \le 1 \le q \le \infty$), distinct from `AIMech:CompatibilityConditionAndOracleInequalitiesForLassoInHighDimensionalGeneralizedLinearModels` (van de Geer 2007/2008, which introduces the $\ell_1$ compatibility constant $\phi_{\mathrm{comp}}(S)$ for empirical-process excess risk and $\ell_1$ loss), and distinct from `AIMech:DantzigSelectorLinearProgrammingSparseEstimator` (Candes & Tao 2007, which relies on uniform uncertainty principle / restricted isometry constants $\delta_{2s} + \theta_{s,2s} < 1$).

Claims & Grounded Evidence

3 Claims

Mechanism #universal-design-free-minimax-lower-bounds-in-l0-and-lr-balls

For any design matrix $X \in \mathbb{R}^{n \times p}$ normalized to $\max_{j \le p} \|X_j\|_2^2 / n \le 1$ under $\varepsilon \sim \mathcal{N}(0, \sigma^2 I_n)$, the minimax $\ell_q$ risk ($1 \le q \le \infty$) over the $\ell_0$ ball $\mathscr{B}_0(k) = \{\beta : \|\beta\|_0 \le k\}$ ($1 \le k < p/2$) is bounded below for every $X$ by $\inf_{\hat{\beta}} \sup_{\beta \in \mathscr{B}_0(k)} \mathbb{E}_{\beta}\|\hat{\beta} - \beta\|_q^q \ge a_q k(\sigma^2\log(p/k - 1)/n)^{q/2}$ with explicit constant $a_q = \sup_{0 < \varepsilon < 1} \left[(1 - \varepsilon)(1 - \sqrt{\varepsilon})^q / 2^{q/2 + 1}\right]$ ($a_2 = 1/4$ at $\varepsilon = 1/4$), and over $\ell_r$ balls $\mathscr{B}_r(\rho) = \{\beta : \|\beta\|_r \le \rho\}$ ($0 < r \le 1$) by $\inf_{\hat{\beta}} \sup_{\beta \in \mathscr{B}_r(\rho)} \mathbb{E}_{\beta}\|\hat{\beta} - \beta\|_q^q \ge a_q\min\left\{\rho^{q(1-1/t)}(\sigma^2\log(p/\tau_* - 1)/n)^{q/(2t)} + o(1),\, \rho^q\right\}$ where $1/t = 1 - r/q$ and $\tau_* = \rho^r(\sigma^2\log p / n)^{-r/2}$ (Theorem 1, Eqs. 7-8, p. 3522; Corollary 1, Eqs. 9-10, p. 3523; Appendix A, pp. 3532-3535).

supports Source: Rate Minimaxity of the Lasso and Dantzig Selector for the l_q Loss in l_r Balls · Locator: Section 2, pp. 3521-3523, Equations (7)-(10), Theorem 1 and Corollary 1; Appendix A, pp. 3532-3535, Lemma 1 and Proof of Theorem 1

Mechanism #sign-restricted-cone-invertibility-factor-and-unified-lasso-dantzig-oracle-inequalities

On the noise domination event $\|z^*\|_\infty \le \eta$ ($z^* = X^\top(y - X\beta^*)/n$), the estimation error $u = \hat{\beta} - \beta^*$ of both the LASSO ($\lambda > \eta$, $\xi = (\lambda + \eta)/(\lambda - \eta)$) and the Dantzig selector ($\lambda_D > 0$, $\xi = (\lambda_D + \eta)/\lambda_D$) belongs to the sign-restricted cone $\mathscr{C}_-(\xi, S) = \{u : \|u_{S^c}\|_1 \le \xi\|u_S\|_1,\, u_j(\Sigma u)_j \le 0\, \forall j \notin S\}$ and satisfies $\|\Sigma u\|_\infty \le \lambda + \eta$ (for LASSO) or $\lambda_D + \eta$ (for Dantzig), yielding the unified $\ell_q$ oracle inequality $\|\hat{\beta} - \beta^*\|_q \le \frac{(\lambda + \eta)|S|^{1/q}}{SCIF_q(\xi, S)}$ (Theorem 3, Eq. 20, p. 3526). Because $SCIF_q(\xi, S) \ge F_q(\xi, S)$ for all $q \ge 1$ and $SCIF_2(\xi, S) \ge \psi(\xi, S)^2$ where $\psi(\xi, S) = \inf_{u \in \mathscr{C}_-(\xi, S)} \sqrt{|S| u^\top \Sigma u}/(\|u_S\|_1 \|u\|_2)^{1/2}$ exceeds the Bickel-Ritov-Tsybakov restricted eigenvalue $\kappa(S, \xi)$ (Proposition 1, Eq. 18, p. 3525), Theorem 3 strictly improves upon two-factor RE bounds and extends to weak/strong $\ell_r$ balls with many small nonzero entries via the interpolation function $g_q(u; \xi) = \frac{(1 - u_S^\top \Sigma u / \|u\|_\Sigma^2)_+}{(\xi\|u_S\|_1/\|u_{S^c}\|_1 - 1)_+}$ and $CIF_q^*(\xi, S)$ (Theorem 4, Eqs. 33-34, p. 3529; Theorem 5, Eqs. 36-39, p. 3530).

supports Source: Rate Minimaxity of the Lasso and Dantzig Selector for the l_q Loss in l_r Balls · Locator: Section 3.1-3.2, pp. 3523-3527, Equations (11)-(26), Proposition 1, Theorems 2-3; Section 4, pp. 3528-3531, Equations (29)-(39), Theorems 4-5; Appendix B, pp. 3535-3538, Proofs of Proposition 1 and Theorems 3-4

Mechanism #linfinity-cif-variable-selection-consistency-of-thresholded-lasso-and-gauss-dantzig

Setting $q = \infty$ in Theorem 3 yields the $\ell_\infty$ error bound $\|\hat{\beta} - \beta^*\|_\infty \le \frac{\lambda + \eta}{SCIF_\infty(\xi, S)}$ without assuming the strong irrepresentable condition $\|\Sigma_{S^c, S}\Sigma_{S,S}^{-1}\operatorname{sign}(\beta_S^*)\|_\infty < 1$. Consequently, for any threshold level $t_* \ge \frac{\lambda + \eta}{SCIF_\infty(\xi, S)}$ and minimum signal strength $\min_{j \in S} |\beta_j^*| > t_* + \frac{\lambda + \eta}{SCIF_\infty(\xi, S)}$, both the Thresholded LASSO ($\hat{\beta}_j^{TL} = \hat{\beta}_j^L\mathbf{1}_{|\hat{\beta}_j^L| > t_*}$), the Thresholded Dantzig Selector ($\hat{\beta}_j^{TD} = \hat{\beta}_j^D \mathbf{1}_{|\hat{\beta}_j^D| > t_*}$), and the two-step Gauss-Dantzig estimator ($\hat{\beta}^{GD} = \arg\min_{\beta : \beta_j = 0 \forall j \notin \hat{S}^{TD}} \|y - X\beta\|_2^2$) achieve exact sign recovery $\operatorname{sign}(\hat{\beta}) = \operatorname{sign}(\beta^*)$ and exact oracle OLS refitting on $S$ (Section 3.3, Corollary 2, Eqs. 27-28, pp. 3527-3528).

supports Source: Rate Minimaxity of the Lasso and Dantzig Selector for the l_q Loss in l_r Balls · Locator: Section 3.3, pp. 3527-3528, Equations (27)-(28), Corollary 2

⚠️ Curated Limitations & Negative Results

Computing the exact Cone Invertibility Factor $F_q(\xi, S)$ or Sign-Restricted Cone Invertibility Factor $SCIF_q(\xi, S)$ over all subsets $S$ of cardinality $k$ is combinatorial in $p$, and for $q > 2$ the quantity $SCIF_q(\xi, S)$ can depend on $|S|$ for strongly correlated designs unless the Gram matrix $\Sigma = X^\top X / n$ has bounded off-diagonal coherence or sparse $\ell_\infty$ invertibility.
For weak/strong $\ell_r$ balls ($0 < r \le 1$) with many small nonzero coefficients where the threshold level is smaller than the universal $\sigma\sqrt{2\log p / n}$ threshold ($\tau_* = \rho^r(\sigma^2\log p / n)^{-r/2} \ge 2$), rate minimaxity in Theorem 5 requires the stronger interpolation condition $CIF_q^*(\xi, S) > 0$ (Eq. 34) together with a sparse maximal eigenvalue upper bound $\varphi_{\max}(m) \le C_{\max} < \infty$ on sub-Gram blocks of size $m \asymp \tau_*$.
Primary-source typographical audit of Ye & Zhang (2010, *JMLR* 11:3519-3540): (1) Section 3.3 heading (p. 3527) prints `'3.3 Vaiable Selection'` instead of `'3.3 Variable Selection'`; (2) Section 5 line 2 (p. 3531) cites `'Greenshtein and Rotiv, 2004'` instead of `'Greenshtein and Ritov, 2004'`; (3) Appendix A line 2 (p. 3532) prints `'Lemms are stated and proved as needed'` instead of `'Lemmas'`; and (4) Appendix A Proof of Theorem 1 after Eq. (57) (p. 3533, line 15) writes `$\{k/(1-\varepsilon)^r\}\mu^p/\lambda_{mm}^p = k(1-\varepsilon)^{q-r} \le k$' with exponent $p$ instead of $q$ in $\mu^q/\lambda_{mm}^q$.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LassoRegression` Lasso Regression	related_match	Establishes sharp Cone Invertibility Factor (CIF) and Sign-Restricted CIF (SCIF) l_q oracle inequalities and rate minimaxity in l_r balls for LASSO and Thresholded LASSO.
`AIO:LinearRegression` Linear Regression	broad_match	Characterizes minimax l_q estimation risk and Gram-matrix cone invertibility in high-dimensional linear regression models.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`yz2010-cif-pdf`	Rate Minimaxity of the Lasso and Dantzig Selector for the l_q Loss in l_r Balls Fei Ye, Cun-Hui Zhang	primary paper full_text	ID: https://jmlr.org/papers/v11/ye10a.html sha256:e876a15a32e5…
`yz2010-cif-abs`	Rate Minimaxity of the Lasso and Dantzig Selector for the l_q Loss in l_r Balls Fei Ye, Cun-Hui Zhang	primary paper abstract_only	ID: https://jmlr.org/papers/v11/ye10a.html sha256:a01c667f3e61…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T03:45:00Z

Updated: 2026-10-19T03:45:00Z

Source File: data/curated/ConeInvertibilityFactorOracleInequalitiesAndRateMinimaxityOfLassoAndDantzigSelectorInLqLoss.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories