Talagrand–Bennett upper-tail bound for the tangent sampling deviation
Disprovedtalagrand_tangent_sampling_upper_tail_boundTalagrand-Bennett two-sided upper-tail bound for the tangent sampling deviation about its Bernoulli mean. Given the Candes-Recht Appendix 9.1 increment bound (|coefficient| <= B = 2 mu0 max(n1,n2) r / m) and variance bound (sum p(1-p) coeff^2 <= sigma^2 = 2 mu0 max(n1,n2) r / m), plus the expectation budget E[Z] <= scale(Cexpect), there are universal Ctail, c > 0 such that for every beta > 2, P( |Z - E[Z]| > tangentSamplingDeviationScale(Ctail) ) <= c * max(n1,n2)^(-beta), where Z = tangentSamplingDeviation. This is the genuine empirical-process supremum concentration core (the modified-LSI / self-bounding for the bespoke Frobenius-norm sup remains the open analytic wall).
Preamble
import Definitions.Def_matrix_completion_talagrand open MatrixCompletion
Formal statement
theorem talagrand_tangent_sampling_upper_tail_bound
(Cexpect : ℝ) :
0 < Cexpect →
∃ Ctail c : ℝ, 0 < Ctail ∧ 0 < c ∧
∀ (β : ℝ), 2 < β →
∀ (n₁ n₂ r m : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₀ μ₁ : ℝ) (S : SVD M r),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
1 ≤ μ₀ → 1 ≤ μ₁ →
A0 S μ₀ → A1 S μ₁ →
TangentSamplingTalagrandIncrementBound S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) →
TangentSamplingTalagrandVarianceBound S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) →
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
tangentSamplingDeviation Omega S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) ≤
tangentSamplingDeviationScale Cexpect β μ₀ (max n₁ n₂) r m →
bernoulliEventProb ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
abs (tangentSamplingDeviation Omega S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) -
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega' =>
tangentSamplingDeviation Omega' S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))))) >
tangentSamplingDeviationScale Ctail β μ₀ (max n₁ n₂) r m) ≤
c * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorrySource
Candes-Recht, Exact matrix completion via convex optimization (arXiv:0805.4471 / CACM 2012), Section 9.1 Appendix, Theorem 9.1 eq (9.2), p.46 (Talagrand empirical-process supremum concentration), combined with the eq (4.10) absorption; Talagrand, Invent. Math. 126 (1996); Ledoux, Concentration of Measure, Corollary 7.8; Bousquet 2002 (C.R.Acad.Sci.Paris 334:495-500) Theorem 2.1; Klein-Rio 2005 (Ann.Probab. 33:1060-1077).