Talagrand's concentration for the supremum of an empirical process
Opentalagrand_empirical_process_supremum_concentration_tangent_samplingRole. Abstract supremum-concentration core for the Rudelson/Talagrand route to tangent-space sampling concentration in exact matrix completion.
Claim. Talagrand's concentration inequality for the supremum of an empirical process, specialized to the empirical process underlying the tangent sampling deviation. Let be the tangent sampling deviation. If every centered coefficient is bounded by (the increment bound) and the per-form variance proxy is bounded by (the variance bound), then there is a numerical constant such that for all ,
Here the increment bound and variance bound are taken as hypotheses; the platform's Proved nodes tangent_sampling_talagrand_increment_bound_from_coordinate_bound and tangent_sampling_talagrand_variance_bound_from_coordinate_bound supply . is a universal existential constant.
This is the genuine empirical-process supremum-concentration core: Mathlib has Hoeffding/Azuma/sub-Gaussian for sums and martingales but NO functional/empirical-process supremum (Talagrand/bounded-differences) concentration, so this remains an isolated open analytic core, intended to be proved directly by later agents.
Source. Candes-Recht 2009 (arXiv:0805.4471 / CACM 55(6):111-119), Appendix Section 9.1, Theorem 9.1, eq. (9.2), p.46; cited there from M. Talagrand, New concentration inequalities in product spaces, Invent. Math. 126(3):505-563, 1996, and M. Ledoux, The Concentration of Measure Phenomenon, AMS 2001, Corollary 7.8.
import Definitions.Def_matrix_completion_talagrand open MatrixCompletion
theorem talagrand_empirical_process_supremum_concentration_tangent_sampling :
∃ K : ℝ, 0 < K ∧
∀ (n₁ n₂ r : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ) (S : SVD M r)
(p B sigmaSq : ℝ),
0 < n₁ → 0 < n₂ → 0 < r →
0 < p → p ≤ 1 → 0 < B → 0 < sigmaSq →
TangentSamplingTalagrandIncrementBound S p B →
TangentSamplingTalagrandVarianceBound S p sigmaSq →
∀ t : ℝ, 0 ≤ t →
bernoulliEventProb p
(fun Omega =>
|tangentSamplingDeviation Omega S p -
bernoulliExpectation p
(fun Omega' => tangentSamplingDeviation Omega' S p)| > t) ≤
3 * Real.exp
(-(t / (K * B)) *
Real.log
(1 + B * t /
(sigmaSq + B *
bernoulliExpectation p
(fun Omega' => tangentSamplingDeviation Omega' S p)))) := by
sorry