CounterexampleConstruction: AI-adaptedVerification: AI-generatedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The stated sparse-covariance minimax rate is unbounded for super-exponential dimension

Statement refuted

The claim that, for every fixed $β > 1$ , $p \geq n^{β}$ , $0 \leq q < 1$ , and $c_{n, p} \leq M n^{(1 - q) / 2} (\log p)^{- (3 - q) / 2}$ , the minimax squared operator risk over $P_{q} (τ, c_{n, p})$ is comparable to $c_{n, p}^{2} (\log p / n)^{1 - q} + \log p / n$ is false without an upper restriction on $\log p / n$ or a cap on the risk expression.

Facts & Assumptions

Given: Fix $τ > 0$ and $M > 0$ . For integers $n \geq 1$ , set $p_{n} = ⌈ e^{n^{2}} ⌉$ , $β = 2$ , $q = 0$ , and $c_{n, p_{n}} = M n^{1 / 2} (\log p_{n})^{- 3 / 2}$ .

[F1]

The class $P_{q} (τ, c_{n, p})$ consists of iid laws with covariance in $G_{q} (c_{n, p})$ and the stated directional tail bound; for $q = 0$ , $G_{0} (c)$ limits the number of nonzero off-diagonal entries per column (Weak-lq covariance class with directional sub-Gaussian tails).

[F2]

For nonnegative $T$ , $E T = \int_{0}^{\infty} P (T > u) d u$ (Layer-cake formulas for random variables).

[F3]

The vector covariance matrix is $Σ = E [(X - E X) (X - E X)^{T}]$ (Sample covariance estimators and squared operator loss).

[F4]

For a symmetric matrix, its operator norm is the maximum absolute Rayleigh quotient (A symmetric matrix operator norm is its largest absolute Rayleigh quotient).

[F5]

For an n-observation experiment, minimax squared operator risk is the infimum over measurable sample estimators of the supremum expected squared operator loss under $P^{\otimes n}$ (Minimax squared operator risk).

Proof

1.1F1F2F3F4givenalgebra

Since $\log p_{n} \geq n^{2}$ , $c_{n, p_{n}} \leq M n^{- 5 / 2} < 1$ for all sufficiently large $n$ ; also $p_{n} \geq e^{n^{2}} \geq n^{2}$ . The point mass at zero has zero covariance, zero off-diagonal entries, and directional tail probability zero, so it belongs to $P_{0} (τ, c_{n, p_{n}})$ . Thus this class is nonempty. For any $P$ in it and any unit vector $v$ , set $Y = v^{T} (X - E X)$ . By [F1]–[F2], $v^{T} Σ (P) v = E_{P} Y^{2} = \int_{0}^{\infty} P (Y^{2} > u) d u \leq \int_{0}^{\infty} e^{- u / (2 τ)} d u = 2 τ .$ By [F3], $Σ (P)$ is symmetric and $v^{T} Σ (P) v = E_{P} [(v^{T} (X - E X))^{2}] \geq 0$ . Taking the maximum over unit $v$ and using [F4] gives $∥ Σ (P) ∥_{o p} \leq 2 τ$ .

2.1F5step 1.1algebra

The constant estimator $\hat{Σ} \equiv 0$ is measurable on the n-sample space. By [F5] and step 1.1, $R_{n} (P_{0} (τ, c_{n, p_{n}})) \leq \sup_{P \in P_{0}} E_{P^{\otimes n}} ∥ \hat{Σ} - Σ (P) ∥_{o p}^{2} \leq 4 τ^{2} .$ This bound is independent of $n$ and $p_{n}$ .

3.1step 2.1algebra∎

Since $e^{n^{2}} \leq p_{n} < e^{n^{2}} + 1 \leq 2 e^{n^{2}}$ , we have $n \leq \log p_{n} / n \leq n + (\log 2) / n$ , so $\log p_{n} / n \sim n$ . Hence $c_{n, p_{n}}^{2} \frac{\log p_{n}}{n} + \frac{\log p_{n}}{n} \geq \frac{\log p_{n}}{n} ⟶ \infty .$ No positive comparison constant independent of $n$ can make this diverging expression a lower bound for the uniformly bounded minimax risk in step 2.1. This contradicts the claimed equivalence.

Remarks

This refutes the uncapped rate assertion, independently of the particular thresholded estimator. The current theorem retains the lower dimension condition $p \geq n^{β}$ and caps the risk expression by $\min {1, r_{n, p}}$ , avoiding this obstruction.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

22 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

T. Tony Cai and Harrison H. Zhou, Optimal Rates of Convergence for Sparse Covariance Matrix Estimation, Theorem 1 (standard reference, not scraped)