Spectral-energy histories , the excess , -bit response protocols and the rate
DefinitionPreservePast_Supplement_SpectralAchievescommunication-complexitycontinual-learninginformation-theorymemory-lower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1
For and the history class is
After is encoded, a query reveals with and a rank budget . For the response must have rank at most and Frobenius norm at most one, and its excess is
A -bit retained-state protocol achieves tolerance with failure probability if, for every fixed history in and every query, the response is feasible on every outcome and has excess at most with probability at least . is the least such width.
With the rate is
Formalization Note The output dimension and the rank budget are fixed parameters of a protocol, as in Theorem 20. The logarithm in is base two. The comparator minimum and the maximum in are an infimum and a supremum over nonempty sets on which they are attained (for : when , , ).
Definition code
import Mathlib
import Definitions.Def_LowRankMEG_frobNorm
import Definitions.Def_WainwrightHDS_NucNorm_opNorm2
open MeasureTheory Matrix
namespace PreservePast.Supplement
/-- **The spectral-energy history class** (240), p.66 (PDF p.68):
`𝓗_E(K, d) = {Z ∈ ℝ^{K×d} : ‖Z‖_op ≤ 1, ‖Z‖_F² ≤ E}`. P. Xu, *Information Required to Preserve Past Learning*, STOC 2027 submission (held version,
PDF sha256 48013ceb…d00fa), Appendix N. -/
def spectralClass (E : ℝ) (K d : ℕ) : Set (Matrix (Fin K) (Fin d) ℝ) :=
{Z | WainwrightHDS.NucNorm.opNorm2 Z ≤ 1 ∧ LowRankMEG.frobNorm Z ^ 2 ≤ E}
/-- **The excess** (241), p.66 (PDF p.68):
`D_r(Y, W) = ‖Y − W‖_F² − min_{rank V ≤ r, ‖V‖_F ≤ 1} ‖Y − V‖_F²`.
**Formalization Note.** The minimum is a real `⨅` over the subtype of comparators; the set
contains `V = 0` and is compact, so the infimum is attained. -/
noncomputable def spectralExcess {m d : ℕ} (r : ℕ) (Y W : Matrix (Fin m) (Fin d) ℝ) : ℝ :=
LowRankMEG.frobNorm (Y - W) ^ 2 -
⨅ V : {V : Matrix (Fin m) (Fin d) ℝ // V.rank ≤ r ∧ LowRankMEG.frobNorm V ≤ 1},
LowRankMEG.frobNorm (Y - V.1) ^ 2
/-- **A B-bit retained-state protocol for future linear responses** (the contract of `B*` in
Theorem 20). P. Xu, *Information Required to Preserve Past Learning*, STOC 2027 submission (held version,
PDF sha256 48013ceb…d00fa), Appendix N, pp.66–67 (PDF pp.68–69): "After encoding Z, a query reveals
L ∈ ℝ^{m×K} with ‖L‖_F ≤ 1 and a rank budget r ≥ 1. For Y = LZ, the response must have rank at
most r and norm at most one. … Let B* be the least register width giving excess at most α with
probability 1 − δ for each fixed history and query. Feasibility is required on every outcome."
**Formalization Note.** One coin space `Ω`; the encoder sees `Z` and the coins, the decoder the
message, the coins and `L`. The output dimension `m` and the rank budget `r` are fixed
parameters of the protocol, as in the statement of Theorem 20 ("m, r ≥ 1"). Rank and norm
feasibility hold for every coin value; the excess bound holds with probability `≥ 1 − δ`. -/
def SpectralAchieves {K d m B : ℕ} {Ω : Type*} [MeasurableSpace Ω] (E : ℝ) (r : ℕ) (α δ : ℝ)
(P : Measure Ω) (enc : Matrix (Fin K) (Fin d) ℝ → Ω → Fin (2 ^ B))
(dec : Fin (2 ^ B) → Ω → Matrix (Fin m) (Fin K) ℝ → Matrix (Fin m) (Fin d) ℝ) : Prop :=
IsProbabilityMeasure P ∧ (∀ Z, Measurable (enc Z)) ∧
(∀ M L, Measurable (fun ω => Matrix.of.symm (dec M ω L))) ∧
∀ Z ∈ spectralClass E K d, ∀ L : Matrix (Fin m) (Fin K) ℝ, LowRankMEG.frobNorm L ≤ 1 →
(∀ ω, (dec (enc Z ω) ω L).rank ≤ r ∧ LowRankMEG.frobNorm (dec (enc Z ω) ω L) ≤ 1) ∧
ENNReal.ofReal (1 - δ) ≤ P {ω | spectralExcess r (L * Z) (dec (enc Z ω) ω L) ≤ α}
/-- **The rate** (242), p.67 (PDF p.69): with `λ_j = min{1, E/j}`,
`Φ(E, K, d, α) = max_{1 ≤ j ≤ K : λ_j > α} j[1 + d log(λ_j/α)]`.
**Formalization Note.** A real `⨆` over the finite set of admissible `j`, which contains `j = 1`
when `1 ≤ E`, `1 ≤ K` and `α < 1` (the range of Theorem 20). The logarithm is base two (§N.1:
"logarithms below are base two"); another base changes `Φ` by a bounded factor only. -/
noncomputable def spectralPhi (E : ℝ) (K d : ℕ) (α : ℝ) : ℝ :=
⨆ j : {j : ℕ // 1 ≤ j ∧ j ≤ K ∧ α < min 1 (E / j)},
(j.1 : ℝ) * (1 + d * Real.logb 2 (min 1 (E / j.1) / α))
end PreservePast.Supplement
Source
P. Xu, Information Required to Preserve Past Learning, STOC 2027 submission (held version, PDF sha256 48013ceb55cb5da782f256c3a4d1c95195bee48a2f4d0b2ed1e22bccd96d00fa), Appendix N, pp.66–67 (PDF pp.68–69), eqs. (240)–(242)