bernoulli_pair_decoupling_spectral_tail_bound_offdiag
ProvedFaithful (corrected) order-2 de la Peña–Montgomery-Smith pair decoupling tail bound for the spectral norm over the Bernoulli powerset sampling model, carrying the EXACT tetrahedral / off-diagonal hypothesis the theorem requires. There exist universal constants (the order-2 decoupling constant ) such that for every matrix-valued bilinear sampling kernel that admits an off-diagonal bilinear representation (centered indicators , the guard being de la Peña–Montgomery-Smith's tetrahedral constraint ), the tail of the diagonal (coupled) statistic under the single-sample measure is controlled by the tail of the decoupled statistic under the independent-pair measure: if then . This is the order-2 case of de la Peña–Montgomery-Smith, Decoupling Inequalities for the Tail Probabilities of Multivariate U-Statistics, Ann. Probab. 23 (1995), no. 2, 806–816 (arXiv:math/9309211), Theorem 1: , summed over the tetrahedral index set . NOTE: this replaces the earlier under-specified node bernoulli_pair_decoupling_spectral_tail_bound (3b904726), which dropped the tetrahedral hypothesis and quantified over an arbitrary ; decoupling is FALSE for kernels with a diagonal part, so the off-diagonal representation hypothesis is essential.
import Definitions.Def_matrix_completion_neumann open MatrixCompletion open scoped BigOperators Classical
theorem bernoulli_pair_decoupling_spectral_tail_bound_offdiag :
∃ K L : ℝ, 0 < K ∧ 0 < L ∧
∀ {n₁ n₂ : ℕ}
(G : Finset (Fin n₁ × Fin n₂) →
Finset (Fin n₁ × Fin n₂) → RealMatrix n₁ n₂)
(p Cdec cdec failureScale thresholdScale : ℝ),
0 ≤ p → p ≤ 1 → 0 < Cdec → 0 < cdec →
-- Tetrahedral / off-diagonal representation hypothesis (de la Peña–
-- Montgomery-Smith Theorem 1: the U-statistic is summed over the
-- off-diagonal index set `w₁ ≠ w₂`, with `Ω₁, Ω₂` the independent
-- copies and `a` the index-coefficient family).
(∃ a : (Fin n₁ × Fin n₂) → (Fin n₁ × Fin n₂) → RealMatrix n₁ n₂,
∀ Omega1 Omega2 : Finset (Fin n₁ × Fin n₂),
G Omega1 Omega2 =
∑ w1 : Fin n₁ × Fin n₂, ∑ w2 : Fin n₁ × Fin n₂,
(if w1 = w2 then (0 : RealMatrix n₁ n₂)
else
(centeredIndicator Omega1 p w1.1 w1.2 *
centeredIndicator Omega2 p w2.1 w2.2) • a w1 w2)) →
bernoulliPairEventProb p
(fun Omega1 Omega2 =>
spectralNorm (G Omega1 Omega2) ≤ Cdec * thresholdScale) ≥
1 - cdec * failureScale →
bernoulliEventProb p
(fun Omega =>
spectralNorm (G Omega Omega) ≤ (K * Cdec) * thresholdScale) ≥
1 - (L * cdec) * failureScale := by
sorry