§A.1, Eq. (6) — Gaussian anti-concentration: Pr[g ∈ [t, t + δ]] ≤ δ/(σ√(2π)) for g ∼ N(0, σ²)
ProvedContinualHardness.Linear.eq_6gaussianp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let and let be a centred Gaussian with variance . For every and every ,
The bound follows from the maximum of the Gaussian density; in the soundness proof of the dictatorship test (Lemma A.7) it bounds the probability that a Gaussian approximation of falls in a short interval.
Formalization Note. is Mathlib's gaussianReal 0 (σ²) and the probability is the measure of the closed interval .
Differences from the source:
- reading: δ, t and σ unquantified ('for g ∼ N(0, σ²)') → every σ > 0, t ∈ ℝ and δ ≥ 0; reason: the interval [t, t + δ] needs δ ≥ 0 (for δ < 0 the right side is negative), and N(0, σ²) with σ > 0 is the non-degenerate Gaussian the bound is about
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace ContinualHardness.Linear
/-- §A.1, Eq. (6), p. 16 (Gaussian anti-concentration). For `g ∼ N(0, σ²)` with `σ > 0`, every
`t ∈ ℝ` and every `δ ≥ 0`: `Pr[g ∈ [t, t + δ]] ≤ δ/(σ√(2π))`. -/
theorem eq_6 (σ t δ : ℝ) (hσ : 0 < σ) (hδ : 0 ≤ δ) :
(gaussianReal 0 (σ ^ 2).toNNReal (Set.Icc t (t + δ))).toReal
≤ δ / (σ * Real.sqrt (2 * Real.pi)) := by sorry
end ContinualHardness.Linear
Source
Saket, Intractability of Continual Learning using Parametric Models with Unlimited Replay Buffer, STOC 2027 submission (manuscript sha256 86821df1…), p. 16, §A.1, Eq. (6) (PDF p. 17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.