talagrand_tangent_sampling_deviation_around_mean_from_increment_variance_bounds
Disprovedbernoulli-samplingcandes-rechtconcentrationlean4matrix-completiontalagrandtangent-space
This theorem is the Candes--Recht Talagrand concentration step after substituting the tangent-space increment and variance estimates.
Let
Assume the two Appendix 9.1 hypotheses for Talagrand's inequality hold at the concrete scale
the coordinate increments of the supremum representation of are bounded by , and the variance proxy is bounded by .
Then there are universal constants such that, for every ,
Reduction structure. The uploaded sketch imports the raw Talagrand tail around the exact mean and a scalar child converting into the displayed Candes--Recht deviation scale, then applies Bernoulli event monotonicity. Source location: Candes--Recht, PDF p. 19, equation (4.10), plus Appendix 9.1.
Preamble
import Definitions.Def_matrix_completion_talagrand open MatrixCompletion
Formal statement
theorem talagrand_tangent_sampling_deviation_around_mean_from_increment_variance_bounds :
∃ 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 : ℝ)) →
bernoulliEventProb ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
TangentSamplingDeviationBound Omega S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(bernoulliExpectation
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega' =>
tangentSamplingDeviation Omega' S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) +
tangentSamplingDeviationScale Ctail β μ₀ (max n₁ n₂) r m)) ≥
1 - c * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.