PropositionStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Correct-scale slab bound for multivariate trimming

Statement

Let $X$ be an absolutely continuous random vector in $R^{d}$ with mean $μ$ and finite covariance matrix $Σ$ as defined in Basic finite covariance matrix identities for robust mean bounds. Let $X_{1}, \dots, X_{N}, Y_{1}, \dots, Y_{N}$ be $2 N$ iid clean copies and let their observed replacement sample have at most $⌊ 2 η N ⌋$ changed coordinates in total. Assume $0 \leq η \leq 1 / 10$ , $0 < δ < 1$ , $N \geq 2560 \log (2 / δ)$ , and $ε = \max {10 η, 2560 \log (2 / δ) / N} \leq 1$ . If $tr Σ > 0$ , put

Q_{0} = \max {\frac{256}{ε} \sqrt{\frac{tr Σ}{N}}, 16 \sqrt{\frac{λ_{\max} (Σ)}{ε}}} .

For the slabs and tail intersections in Adaptive multivariate trimmed mean, Every positive real lies below a dyadic scale less than twice as large supplies an integer $i_{0}$ with $2^{i_{0}} \in [2 Q_{0}, 4 Q_{0})$ . Then, with probability at least $1 - δ$ , $K_{i_{0}} = ⋂_{i \geq i_{0}} Γ (2^{i})$ is nonempty and every $z \in K_{i_{0}}$ satisfies $∥ z - μ ∥ \leq 16 ε Q_{0}$ . The positive-trace condition is required to make $Q_{0} > 0$ .

Facts & Assumptions

Given: The clean iid halves, replacement budget and parameter domain in the Statement, with positive covariance trace.

[F1]

A variance-sensitive bound for bounded empirical suprema: for bounded $∣ f ∣ \leq B$ with $P f^{2} \leq s^{2}$ , the centered supremum $Z$ satisfies $Z \leq E Z + 2 \sqrt{(8 E W + 4 N s^{2}) x} + \sqrt{8} B x$ outside probability $e^{- x}$ , where $W = \sup_{f} \sum_{i} f (X_{i})^{2}$ .

[F2]

Independent-process symmetrization for convex moments and One-sided coordinate Rademacher contraction supply ghost-sample symmetrization and coordinate contraction. In the proof below their one-sided forms are derived directly to keep the constants explicit.

[F3]

Basic finite covariance matrix identities for robust mean bounds gives $E ∥ X - μ ∥^{2} = tr Σ$ and $E ⟨ X - μ, v ⟩^{2} \leq λ_{\max} (Σ)$ for unit $v$ . Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs and Markov's inequality for random variables give the norm and tail bounds used below.

[F4]

Adaptive multivariate trimmed mean defines the directional quantiles, clipped centers and slabs; Adversarial sample replacement permits at most $2 η N$ changes in either half, including sample-dependent choices.

[F5]

Dominated convergence passes bounded pointwise limits under integration. The iid finite product law is Independent random elements have product joint law; Every positive real lies below a dyadic scale less than twice as large gives the stated dyadic index.

[F6]

Since $tr Σ > 0$ , $d \geq 1$ , and $Q^{d}$ is countable and dense in $R^{d}$ ( $Q^{n}$ is a countable dense subset of $R^{n}$ , and rational open boxes form a countable basis); normalizing its nonzero elements gives a countable dense subset of $S^{d - 1}$ because normalization is continuous away from zero and every unit vector is nonzero.

Proof

Given: The objects in the Statement. Write $r = \sqrt{tr Σ / N}$ , $λ = λ_{\max} (Σ)$ and $x = ε N / 1280$ .

1.1F2F3F5F6algebra

Put $D = {q / ∥ q ∥_{2} : q \in Q^{d} ∖ {0}}$ and include the zero vector. By [F6], $D$ is countable and dense in $S^{d - 1}$ : rational vectors approximate every unit vector, and normalization is continuous at nonzero vectors. For each bounded continuous scalar map used below, the sample sums and their population expectations are continuous in direction, the latter by [F5]. Thus their suprema over $D \cup {0}$ equal the full directional suprema and are measurable. For any such class $g_{v}$ , use the independent clean half $Y_{1}, \dots, Y_{N}$ as the ghost copy of $X_{1}, \dots, X_{N}$ ; its product law and independence follow from [F5] and the iid hypothesis. When the same argument is applied to the $Y$ half, swap the roles of the two clean halves. Jensen gives $E \sup_{v} \sum_{i} (g_{v} (X_{i}) - P g_{v}) \leq E \sup_{v} \sum_{i} (g_{v} (X_{i}) - g_{v} (Y_{i}))$ . Pair swapping inserts independent signs; separating the two halves gives at most $2 E \sup_{v} \sum_{i} σ_{i} g_{v} (X_{i})$ . For an $L$ -Lipschitz scalar map $ψ$ , averaging one sign with arbitrary remaining offsets $A_{v}$ gives $\frac{1}{2} \sup_{v, w} (A_{v} + A_{w} + ψ (t_{v}) - ψ (t_{w})) \leq \frac{1}{2} \sup_{v, w} (A_{v} + A_{w} + L ∣ t_{v} - t_{w} ∣)$ . Swapping $v, w$ shows that the final supremum equals the one with $L (t_{v} - t_{w})$ ; successive coordinate replacements prove one-sided contraction with factor $L$ . Countable limits follow by monotone convergence after subtracting one fixed candidate, or bounded convergence on the finite sign space for a fixed sample. Finally set $S = \sum_{i} σ_{i} (X_{i} - μ)$ . Independence of the signs gives $E ∥ S ∥^{2} = N tr Σ$ . Since $u \leq 1 + u^{2}$ for $u \geq 0$ , $E ∥ S ∥ < \infty$ ; then $0 \leq E (∥ S ∥ - E ∥ S ∥)^{2} = E ∥ S ∥^{2} - (E ∥ S ∥)^{2}$ gives $E ∥ N^{- 1} S ∥ \leq r$ .

2.1F1F3step 1.1algebra

Put $h (t) = \min {1, (2 ∣ t ∣ / Q_{0} - 1)_{+}}$ . It is $2 / Q_{0}$ -Lipschitz, vanishes at zero and majorizes $1_{{∣ t ∣ \geq Q_{0}}}$ . By [F3], $P h (⟨ X - μ, v ⟩) \leq 4 λ / Q_{0}^{2} \leq ε / 64$ . For its centered supremum, step 1.1 gives $E Z / N \leq 4 r / Q_{0} \leq ε / 64$ . Since $h^{2} \leq h$ , $E W / N \leq ε / 32$ , and its second moment is at most $ε / 64$ . Apply [F1] separately to each clean half with $B = 1$ . Except on probability $e^{- x}$ for each half, its maximal empirical $h$ average is at most $ε / 32 + 2 \sqrt{5 ε x / (16 N)} + \sqrt{8} x / N = ε / 16 + \sqrt{8} ε / 1280 < ε / 8$ . Thus each clean half has fewer than $ε N / 8$ projections of centered absolute value at least $Q_{0}$ , uniformly in direction.

2.2F1F3step 1.1algebra

Fix $Q = 2^{i_{0}} \in [2 Q_{0}, 4 Q_{0})$ . Put $g_{v} (z) = ϕ_{- Q, Q} (⟨ z - μ, v ⟩)$ and $W_{Q} (v) = N^{- 1} \sum_{i} g_{v} (X_{i})$ . Antipodal directions and odd clipping make the absolute centered supremum equal its one-sided counterpart. Step 1.1 gives $E Z / N \leq 2 r$ . The square of clipping is $2 Q$ -Lipschitz and vanishes at zero, so the same symmetrization/contraction argument yields $E W / N \leq λ + 4 Q r$ for the squared-class supremum. Here $∣ g_{v} ∣ \leq Q$ and $P g_{v}^{2} \leq λ$ . Since $r \leq ε Q / 512$ and $λ \leq ε Q^{2} / 1024$ , [F1] bounds $\sup_{v} ∣ W_{Q} (v) - P W_{Q} (v) ∣$ outside probability $e^{- x}$ by $2 r + 2 \sqrt{19 ε Q^{2} x / (256 N)} + \sqrt{8} Q x / N < ε Q / 32$ . Also $∣ P g_{v} ∣ \leq E [∣ ⟨ X - μ, v ⟩ ∣ 1_{{∣ ⟨ X - μ, v ⟩ ∣ > Q}}] \leq λ / Q \leq ε Q / 1024$ , since the unclipped projection is centered.

3.1F4step 2.1algebra

Each observed half has at most $2 η N \leq ε N / 5$ changes. On both events of step 2.1, fewer than $13 ε N / 40 < ε N / 2$ projections in either observed half are outside $[⟨ μ, v ⟩ - Q_{0}, ⟨ μ, v ⟩ + Q_{0}]$ . Both directional quantile ranks $k = ⌈ ε N / 2 ⌉$ and $k = ⌈ (1 - ε / 2) N ⌉$ satisfy $k \geq ε N / 2$ and $N - k + 1 \geq ε N / 2$ ; in the potentially integral boundary the strict count inequality suffices. Hence both quantiles lie in that interval, including at $ε = 1$ . Write $a_{v} = α_{v} - ⟨ μ, v ⟩$ and $b_{v} = β_{v} - ⟨ μ, v ⟩$ , so $- Q_{0} \leq a_{v} \leq b_{v} \leq Q_{0}$ .

4.1F4step 2.1step 3.1step 2.2algebra

For any clean centered projection $t$ , the data-dependent clipping $ϕ_{a_{v} - Q, b_{v} + Q} (t)$ differs from $ϕ_{- Q, Q} (t)$ by at most $Q_{0}$ and agrees with it when $∣ t ∣ < Q - Q_{0}$ . Since $Q - Q_{0} \geq Q_{0}$ , step 2.1 bounds the average difference by $ε Q_{0} / 8 \leq ε Q / 16$ . The data-dependent clipping interval has length at most $2 Q + 2 Q_{0} \leq 3 Q$ , so first-half replacements change its average by at most $6 η Q \leq 3 ε Q / 5$ . Combining these bounds with step 2.2 gives $\sup_{v} ∣ U_{Q} (v) - ⟨ μ, v ⟩ ∣ \leq (3 / 5 + 1 / 16 + 1 / 32 + 1 / 1024) ε Q = 3557 ε Q / 5120 < ε Q$ . Thus $μ \in Γ (Q)$ and every $z \in Γ (Q)$ has $∥ z - μ ∥ \leq 3 ε Q < 12 ε Q_{0} \leq 16 ε Q_{0}$ .

5.1F4step 2.1step 2.2step 3.1step 4.1algebra∎

On the same events, for every $R \geq Q$ the clips at expanded intervals $[a_{v} - R, b_{v} + R]$ and $[a_{v} - 2 R, b_{v} + 2 R]$ differ by at most $R$ . They differ only on observed centered projections with absolute value at least $R - Q_{0} \geq Q_{0}$ . Their observed number is less than $13 ε N / 40$ by step 3.1, so $∣ U_{2 R} (v) - U_{R} (v) ∣ \leq 13 ε R / 40 < 2 ε R$ . Consequently $Γ (R) \subseteq Γ (2 R)$ , and $K_{i_{0}} = Γ (Q)$ is nonempty with the required radius. The three exceptional events in steps 2.1 and 2.2 have total probability at most $3 e^{- x} \leq 3 (δ / 2)^{2} \leq δ$ , because $ε N \geq 2560 \log (2 / δ)$ and $0 < δ < 1$ . This proves the proposition simultaneously for every admissible replacement of the clean samples.

Remarks

The constant $4 ε Q_{0}$ in the former statement and source Proposition 1 is false because the slab width scales with the chosen dyadic $Q$ , not $Q_{0}$ . The four-Q0 trimming slab radius is false gives an explicit continuous counterexample. The corrected bound preserves the main theorem's universal-constant rate. The zero-trace branch is Exact recovery by the multivariate trimmed mean at zero covariance.

Depends on

Used by

Multivariate trimmed-mean bound under sample replacement Theorem

Dependency tree · two levels

89 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

Gábor Lugosi and Shahar Mendelson, Robust Multivariate Mean Estimation: The Optimality of Trimmed Mean, Proposition 1, Lemma 1, Lemma 2 and proof (standard reference, not scraped)
Gábor Lugosi, Mean Estimation in High Dimension, §3.2 (standard reference, not scraped)