Theorem 7 — individual versus average protection
OpenPreservePast.Supplement.theorem_7communication-complexitycontinual-learninginformation-theorymemory-lower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider histories of regression tasks with and , at radius , accuracy , fit tolerance and failure probability . There is an absolute such that, for all sufficiently large , all and all ,
The constants do not depend on . The upper bounds are deterministic; the lower bounds allow arbitrary joint randomized messages.
Protecting each old task separately forbids cross-task compensation and costs a factor more memory than protecting their average.
Formalization Note Individual protection is the published contract (PreservePast.RandAchieves, PreservePast.DetAchieves) for a -tuple of tasks; average protection is RandAchievesAvg, DetAchievesAvg. The statement holds for every public checkpoint .
Differences from the source:
- encoding: B = Θ(·) with constants independent of K, n, m, r, for all sufficiently large n → absolute γ, c, C > 0 and N₀ chosen first; for n ≥ N₀, c·X ≤ B for every randomized achieving width and a deterministic code of width B ≤ C·X; reason: spells out Θ and "sufficiently large", and avoids the junk value of an infimum over an empty set
Preamble
import Mathlib import Definitions.Def_PreservePast_RandAchieves import Definitions.Def_PreservePast_DetAchieves import Definitions.Def_PreservePast_Supplement_RandAchievesAvg open MeasureTheory
Formal statement
namespace PreservePast.Supplement
/-- **Theorem 7 (Individual versus average protection).** P. Xu, *Information Required to Preserve Past Learning*, STOC 2027 submission (held version,
PDF sha256 48013ceb…d00fa), Theorem 7, p.9 (PDF p.11), eq. (20).
There are absolute `γ, c, C > 0` and `N₀` such that for all `n ≥ N₀`, `1 ≤ r ≤ m ≤ n`,
`1 ≤ K ≤ exp(γ n)` and every public checkpoint `W₀`, at `R = √2`, `ε = 201/20000`,
`ξ = 1/20000`, `β = 1/3`: every randomized protocol protecting each of the `K` tasks
individually uses `B ≥ c K n` bits and a deterministic code does so with `B ≤ C K n` bits; every
randomized protocol protecting the average uses `B ≥ c n` bits and a deterministic code does so
with `B ≤ C n` bits.
**Formalization Note.** `B = Θ(·)` is stated in the two-part form of the published goal
(a lower bound for every achieving width and an achieving code for the upper bound), which
avoids `sInf ∅`. "For all sufficiently large n" is `∃ N₀, ∀ n ≥ N₀`; the constants `γ, c, C, N₀`
are chosen before `K, n, m, r, W₀` ("The constants do not depend on K, n, m, r"). Individual
protection is the published contract `RandAchieves`/`DetAchieves` with a `K`-tuple history
(`max_i f_i(H) ≤ ε`); the tasks satisfy `𝔼_i‖X‖² ≤ 2`, `𝔼_i‖W₀X − Y‖² ≤ 1` by the definition of
`Task`. Coin spaces live in `Type`. -/
theorem theorem_7 :
∃ γ : ℝ, 0 < γ ∧ ∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∃ N₀ : ℕ,
∀ (m n r K : ℕ) (W₀ : Matrix (Fin m) (Fin n) ℝ),
N₀ ≤ n → 1 ≤ r → r ≤ m → m ≤ n → 1 ≤ K → (K : ℝ) ≤ Real.exp (γ * n) →
(∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω)
(enc : (Fin K → Task W₀) → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → (Fin n → ℝ) → (Fin m → ℝ) → Matrix (Fin m) (Fin n) ℝ),
RandAchieves P enc dec r (201 / 20000) (1 / 20000) (Real.sqrt 2) (1 / 3) →
c * K * n ≤ (B : ℝ)) ∧
(∃ B : ℕ, (B : ℝ) ≤ C * K * n ∧
∃ (enc : (Fin K → Task W₀) → Fin (2 ^ B))
(dec : Fin (2 ^ B) → (Fin n → ℝ) → (Fin m → ℝ) → Matrix (Fin m) (Fin n) ℝ),
DetAchieves enc dec r (201 / 20000) (1 / 20000) (Real.sqrt 2)) ∧
(∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω)
(enc : (Fin K → Task W₀) → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → (Fin n → ℝ) → (Fin m → ℝ) → Matrix (Fin m) (Fin n) ℝ),
RandAchievesAvg P enc dec r (201 / 20000) (1 / 20000) (Real.sqrt 2) (1 / 3) →
c * n ≤ (B : ℝ)) ∧
∃ B : ℕ, (B : ℝ) ≤ C * n ∧
∃ (enc : (Fin K → Task W₀) → Fin (2 ^ B))
(dec : Fin (2 ^ B) → (Fin n → ℝ) → (Fin m → ℝ) → Matrix (Fin m) (Fin n) ℝ),
DetAchievesAvg enc dec r (201 / 20000) (1 / 20000) (Real.sqrt 2) := by sorry
end PreservePast.Supplement
Source
P. Xu, Information Required to Preserve Past Learning, STOC 2027 submission (held version, PDF sha256 48013ceb55cb5da782f256c3a4d1c95195bee48a2f4d0b2ed1e22bccd96d00fa), Theorem 7, p.9 (PDF p.11), eq. (20)