Lean statement

Posterior-replica comparisons and sample lower bound

Lean is a language for mathematical statements and proofs that a computer can verify. This page shows one statement file from OpenAI’s release, possible paper matches and independent reports. The code-like names below identify the definitions or theorems selected by the proof-verification settings.

Theorem selected for verification: OAI.PosteriorReplicas.source_main

Lean statement file: PosteriorReplicas.leanShow on the mapFamily 140. OpenAI lists this as a main result in its Lean catalogue.

See the candidate theorem Who ran the proof-verification program Report a comparison with the paper (GitHub issue)

The Lean statement

The lines of the Lean statement that state the theorem, then the definitions in the file that it uses.

theorem source_main : EqualLabelMeasureIdentity ∧ EqualLabelVersions ∧    GaussianReplicaBlock ∧ DistanceReplicaBlock ∧ HaarReplicaBlock ∧    SyntheticReplicaBlock ∧ IncidenceReplicaBlock ∧    PosteriorRegression.KernelSubquadraticMemory.{u} := by  sorry

A Lean statement states the theorem and leaves its proof as sorry on purpose. OpenAI’s proof is in a separate solution module, and a program called Comparator checks that proof against this statement.

Definitions needed to read it

Local definitions the statement names, followed through the definitions they name in turn. The match is by name in the source text, so a name reached only through notation can be missed; the full file is below.

abbreviation OAI.PosteriorReplicas.Vec line 14

abbrev Vec (d : ℕ) := EuclideanSpace ℝ (Fin d)

abbreviation OAI.PosteriorReplicas.Rows line 15
```
abbrev Rows (d k : ℕ) := Fin k → Vec d
```
abbreviation OAI.PosteriorReplicas.Labels line 16
```
abbrev Labels (k : ℕ) := Fin k → ℝ
```

abbreviation OAI.PosteriorReplicas.Data line 17

abbrev Data (d k : ℕ) := Rows d k × Labels k

abbreviation OAI.PosteriorReplicas.Tuple line 18

abbrev Tuple (d m : ℕ) := Fin (m + 1) → Vec d

definition OAI.PosteriorReplicas.sphereLaw line 20

def sphereLaw (d : ℕ) : Measure (Vec d) :=  let σ := (volume : Measure (Vec d)).toSphere  ((σ univ)⁻¹ • σ).map Subtype.val

definition OAI.PosteriorReplicas.gaussianRows line 24

def gaussianRows (d k : ℕ) : Measure (Rows d k) :=  Measure.pi fun _ => stdGaussian (Vec d)

definition OAI.PosteriorReplicas.labels line 31

def labels {d k : ℕ} (A : Rows d k) (s : Vec d) : Labels k :=  fun i => ⟪A i, s⟫

definition OAI.PosteriorReplicas.messageKernel line 39

def messageKernel {d k N : ℕ} (κ : Kernel (Data d k) (Fin N)) :    Kernel (Vec d × Rows d k) (Fin N) :=  κ.comap (fun z => (z.2, labels z.2 z.1)) (by    unfold labels    fun_prop)

definition OAI.PosteriorReplicas.signalMessageLaw line 50

def signalMessageLaw {d k N : ℕ} (p : Measure (Vec d))    (κ : Kernel (Data d k) (Fin N)) : Measure (Vec d × Fin N) :=  ((p.prod (gaussianRows d k)) ⊗ₘ messageKernel κ).map    (fun z => (z.1.1, z.2))

definition OAI.PosteriorReplicas.sideLaw line 61

def sideLaw {d N : ℕ} (ℓ : ℕ) (q : Measure (Vec d × Fin N)) :    Measure (Data d ℓ × (Vec d × Fin N)) :=  ((gaussianRows d ℓ).prod q).map    (fun z => ((z.1, labels z.1 z.2.1), z.2))

definition OAI.PosteriorReplicas.messageEntropy line 71

def messageEntropy {d N : ℕ} (q : Measure (Vec d × Fin N)) : ℝ :=  ∑ w : Fin N, -(q.snd.real {w}) * Real.log (q.snd.real {w})

definition OAI.PosteriorReplicas.conditionalInformation line 74

def conditionalInformation {d ℓ N : ℕ} [NeZero N]    (μ : Measure (Data d ℓ × (Vec d × Fin N))) [IsFiniteMeasure μ] : ℝ≥0∞ :=  klDiv μ (μ.fst ⊗ₘ (μ.condKernel.fst ×ₖ μ.condKernel.snd))

definition OAI.PosteriorReplicas.GaussianReplicaBlock line 78

def GaussianReplicaBlock : Prop :=

Show the remaining 12 lines

  ∃ C : ℝ, 0 < C ∧ ∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d →    let k := 2 * (d / 16)    let t := k + 1    let ℓ := 4 * k    ∀ (p : Measure (Vec d)) [IsProbabilityMeasure p]      (f : Vec d → ℝ) (L : ℝ),      Measurable f → (∀ x, 0 ≤ f x ∧ f x ≤ L) →      p = (sphereLaw d).withDensity (fun x => ENNReal.ofReal (f x)) →      ∀ (N : ℕ) [NeZero N] (κ : Kernel (Data d k) (Fin N)) [IsMarkovKernel κ],        conditionalInformation (sideLaw ℓ (signalMessageLaw p κ)) ≤          ENNReal.ofReal (messageEntropy (signalMessageLaw p κ) / (t : ℝ) +            C * (d : ℝ) + C * Real.log (2 + Real.log L))

inductive type OAI.PosteriorReplicas.BaseLaw line 92

inductive BaseLaw where  | spherical  | gaussian  deriving DecidableEq

definition OAI.PosteriorReplicas.BaseLaw.measure line 97

def BaseLaw.measure (base : BaseLaw) (d : ℕ) : Measure (Vec d) :=  match base with  | .spherical => sphereLaw d  | .gaussian => stdGaussian (Vec d)

definition OAI.PosteriorReplicas.rowGram line 102

def rowGram {d k : ℕ} (A : Rows d k) : Matrix (Fin k) (Fin k) ℝ :=  fun i j => ⟪A i, A j⟫

definition OAI.PosteriorReplicas.liftLabel line 105

def liftLabel {d k : ℕ} (A : Rows d k) (y : Labels k) : Vec d :=  ∑ i, ((rowGram A)⁻¹ *ᵥ y) i • A i

definition OAI.PosteriorReplicas.kernelComponent line 108

def kernelComponent {d k : ℕ} (A : Rows d k) (x : Vec d) : Vec d :=  x - liftLabel A (labels A x)

definition OAI.PosteriorReplicas.baseFiber line 111

def baseFiber {d k : ℕ} (base : BaseLaw) (A : Rows d k) (y : Labels k) :    Measure (Vec d) :=  match base with  | .gaussian => (stdGaussian (Vec d)).map      (fun x => liftLabel A y + kernelComponent A x)  | .spherical => (stdGaussian (Vec d)).map      (fun x => liftLabel A y +        (Real.sqrt (1 - ‖liftLabel A y‖ ^ 2) / ‖kernelComponent A x‖) •          kernelComponent A x)

definition OAI.PosteriorReplicas.baseDensity line 121

def baseDensity {d k : ℕ} (base : BaseLaw) (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=

Show the remaining 11 lines

  if LinearIndependent ℝ A then    match base with    | .gaussian => ENNReal.ofReal        ((2 * Real.pi) ^ (-(k : ℝ) / 2) *          Real.exp (-‖liftLabel A y‖ ^ 2 / 2) / Real.sqrt (rowGram A).det)    | .spherical => if ‖liftLabel A y‖ < 1 then ENNReal.ofReal        (Real.Gamma ((d : ℝ) / 2) /          (Real.pi ^ ((k : ℝ) / 2) * Real.Gamma (((d : ℝ) - k) / 2)) *          (1 - ‖liftLabel A y‖ ^ 2) ^ (((d : ℝ) - k - 2) / 2) /          Real.sqrt (rowGram A).det) else 0  else 0

definition OAI.PosteriorReplicas.tiltMass line 134

def tiltMass {d k : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=  ∫⁻ x, f x ∂baseFiber base A y

definition OAI.PosteriorReplicas.projectedDensity line 138

def projectedDensity {d k : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=  baseDensity base A y * tiltMass base f A y

definition OAI.PosteriorReplicas.tiltedFiber line 142

def tiltedFiber {d k : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (A : Rows d k) (y : Labels k) : Measure (Vec d) :=  if tiltMass base f A y = 0 then Measure.dirac 0  else (tiltMass base f A y)⁻¹ • (baseFiber base A y).withDensity f

44 more definitions are reached the same way; the full file lists them.

Possible paper match, with no recorded review

Atlas selected this possible match by comparing words in the Lean statement with every statement in the family. No review of whether the statements mean the same thing is recorded.

Words of the Lean statement, its names split into words, that also appear in the theorem: affine, error, initial, output, unit, rules, laws, samples and 15 more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: bound, sufficiently and large.

Statements in Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression come first because the release’s name for this Lean statement shares words with that paper’s title.

Proposition 7.1 of Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression

Proposition (All-affine suffix bound)

For all sufficiently large d, consider a Borel learner padded to k blocks of m exact Gaussian samples, of width at most W, and with target-independent unit output laws at the last layer. The randomized experiment, shared seed, initialization, and fresh randomness satisfy the joint measurability, independence, and information restrictions of Definition s:model. Here 0<\epsilon\le1/10, and success means angular error at most \epsilon. Assume

n_0+2k\le d,\qquad W^{1/p}\le2^d.

For each fixed shared seed whose rules satisfy these assumptions, and for a state v at layer (k-\ell)m, let g_v(s) be the success probability of the suffix started in that state. For 0\le\ell\le k, every affine subsphere (s:affine-sphere) with \dim H=n\ge n_0+2\ell satisfies

\int g_v(z+r\xi)\,d\sigma_H(\xi) \le (R_\ell/r)^a,\qquad R_\ell=16C_*^\ell\epsilon.

The assertion is uniform in the fixed seed and includes states unreachable from the initial layer.

Section 7, An affine invariant with explicit constants Read it in the paper TeX source, line 17

Show the TeX

For all sufficiently large \(d\), consider a Borel learner padded to
\(k\) blocks of \(m\) exact Gaussian samples, of width at most \(W\),
and with target-independent unit output laws at the last layer.
The randomized experiment, shared seed, initialization, and fresh
randomness satisfy the joint measurability, independence, and
information restrictions of Definition~\ref{s:model}. Here
\(0<\epsilon\le1/10\), and success means angular error at most
\(\epsilon\).
Assume
\begin{equation}
 n_0+2k\le d,\qquad W^{1/p}\le2^d.
\end{equation}
For each fixed shared seed whose rules satisfy these assumptions, and
for a state \(v\) at layer \((k-\ell)m\), let \(g_v(s)\) be the
success probability of the suffix started in that state. For
\(0\le\ell\le k\), every affine subsphere \eqref{s:affine-sphere}
with \(\dim H=n\ge n_0+2\ell\) satisfies
\begin{equation}
 \int g_v(z+r\xi)\,d\sigma_H(\xi)
 \le (R_\ell/r)^a,\qquad R_\ell=16C_*^\ell\epsilon.
\end{equation}
The assertion is uniform in the fixed seed and includes states
unreachable from the initial layer.

Other possible paper matches, closest wording first

Theorem 1.1 of Posterior replicas and conditional information in Gaussian regression. Words of the Lean statement, its names split into words, that also appear in the theorem: replica, d/16, message, kernel, experiment, density and six more. Found in the paper’s title, which its main theorem states: posterior, regression, conditional and information. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: prior, bound, large and sufficiently.
Proposition 8.1 of Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression. Words of the Lean statement, its names split into words, that also appear in the theorem: vector, output, norm, rules, d/2, samples and 14 more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: bound.
Theorem 3.3 of Posterior replicas and conditional information in Gaussian regression. Words of the Lean statement, its names split into words, that also appear in the theorem: reference, identities, fiber, tilt, base, equal and 17 more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: using, resulting, lower and bounded.
Proposition 11.1 of Localization costs and information growth for exact Gaussian observations. Words of the Lean statement, its names split into words, that also appear in the theorem: constrained, fiber, base, equal, null, spherical and eleven more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: outside and bounded.
Theorem 1.2 of Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression. Words of the Lean statement, its names split into words, that also appear in the theorem: natural, arccos, 2/3, rows, memory, uniform and five more. Found in the paper’s title, which its main theorem states: regression and sample. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: threshold and bound.
Theorem 6.1 of Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression. Words of the Lean statement, its names split into words, that also appear in the theorem: nonempty, range, d/16, estimate, d/2, pi and nine more.

How Atlas selects possible matches: it compares words in the Lean statement with every statement in the family. It also splits Lean names into words. The release’s label and note receive less weight; a main theorem wins a close match. If the Lean wording yields no clear match, Atlas uses the catalogue description. This selects passages to compare; it does not establish that they mean the same thing.

Reported Comparator runs

two independent groups report that Comparator accepted runs for this Lean statement file: Carlos Toledo’s cert-machine; MathVet. Each group reports its own Comparator run for this statement file. Atlas has not repeated the runs.

For a configured theorem, Comparator tests whether OpenAI’s proof proves the exact Lean statement. Some files instead configure definitions for comparison by name and type. Acceptance does not establish that the statement means the same thing as the paper’s theorem.

Carlos Toledo’s cert-machine

How they ran it, in their words

Every Comparator challenge re-run on Linux with nanoda switched on, decided by a preregistered rule; every family’s challenge statements read against OpenAI’s headline, clause by clause. Decider: Comparator (leanprover/comparator d03acab1 = tag v4.34.0, built with the release’s toolchain v4.34.1), lean4export 076e8e57, landrun 811cfff5, nanoda_lib 3a240721 — on GitHub’s Linux runners (.github/workflows/openai-math-kernel.yml), one j…

Accepted Their term: “CERTIFIED”.
Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.
Reported 10 October 2026, at the release version shown here. Original verification report

MathVet

How they ran it, in their words

An independent, model-assisted, pre-referee reading of each family’s challenge statements against its headline claim under a published rubric (PROTOCOL.md), with its own Comparator runs per challenge. Its protocol describes a planned error-rate study; this import does not establish that the study has been completed.

Accepted Their term: “comparator-sandboxed-pass”.
Re-run through Comparator in a sandboxed virtual machine: accepted.
Reported 8 October 2026, at the release version shown here. Original verification report

What an accepted Comparator run would establish

If Comparator is run under this configuration and accepts, the solution proves the configured theorem using only the allowed axioms, and the Lean kernel accepts every step.

This configuration lists no definition holes, so every definition the statement uses is compared as it is written in this file.

Allowed axioms: propext, Quot.sound, Classical.choice

Acceptance leaves open whether the Lean statement means the same thing as the paper’s theorem, whether the paper’s other claims are correct, and whether the result is new. Those questions require comparing the definitions and statements, reviewing the paper’s arguments, and reading the earlier literature.

Do family 140’s Lean statements express the advertised result?

These assessments compare all the family’s Lean statements with the whole result OpenAI describes in its catalogue. They do not assess this statement alone. Each group uses its own published rules.

MathVet and cert-machine agree on how much of the advertised result the Lean statements express.

MathVet
Finds the whole advertised result stated or implied Their term: “full”.
The challenge statements imply the headline claim after unpacking definitions or one routine step. Their record
Their note: None for the headline; supporting results are in separate files. The learner model gives the learner a free shared seed at every step (a stronger model, so the lower bound is stronger).
Definitions the group asks readers to compare with the paper: Bespoke finite-memory learner model (Learner, RunStatus, Admissible bundling several AEMeasurable hypotheses, angularError := arccos ⟪ŝ, s⟫, uniformSphere via Measure.toSphere); GaussianInformation.lean also introduces local instance ambientSub/ambientInner re-defining Sub/Inner on EuclideanSpace (supporting file)
Carlos Toledo’s cert-machine
Finds the whole advertised result stated or implied Their term: “MATCHES”.
The challenge statements state the headline as OpenAI wrote it. Their record

Read the complete assessments on the family page.

OpenAI’s own note on what this Lean statement covers

“For a learner using $M(d)=o(d^2)$ bits of memory, the resulting bound says that, for sufficiently large $d$ and $0<\varepsilon\le1/10$, success probability at least $2/3$ under the uniform unit-sphere prior requires $T\ge c d\log(1/\varepsilon)$ observations, where $c>0$ is universal. The formalized streaming result uses the $2/3$ threshold; the stronger $3/5$ variant is outside this scope.”
Quoted from OpenAI’s Lean note for this family

An AI agent drafted an interpretation of that note, classifying this statement as “states a paper’s theorem as the paper does”. No human review of the draft is recorded.

Supporting material

The complete Lean statement file

455 lines, copied from release version fd4aeeb. A name defined in this file links to its line; pointing at the name shows its definition.

Declared in this fileOpenAI’s library at fd4aeebOther linked names open the current documentation for Mathlib, Lean’s mathematical library.

Links in the file: 326 to its own declarations, 276 to Mathlib’s documentation. 70 declared names also link to the same declaration in OpenAI’s library. OpenAI uses Mathlib version d13f23b. The linked documentation describes the current version, so names that have since changed may be missing there.

import Mathlibnamespace OAIsectionopen MeasureTheory ProbabilityTheory InformationTheory Set Matrixopen scoped ENNReal NNReal RealInnerProductSpace Classicalnoncomputable sectionnamespace PosteriorReplicasabbrev Vec (d : ℕ) := EuclideanSpace ℝ (Fin d)abbrev Rows (d k : ℕ) := Fin k → Vec dabbrev Labels (k : ℕ) := Fin k → ℝabbrev Data (d k : ℕ) := Rows d k × Labels kabbrev Tuple (d m : ℕ) := Fin (m + 1) → Vec ddef sphereLaw (d : ℕ) : Measure (Vec d) :=  let σ := (volume : Measure (Vec d)).toSphere  ((σ univ)⁻¹ • σ).map Subtype.valdef gaussianRows (d k : ℕ) : Measure (Rows d k) :=  Measure.pi fun _ => stdGaussian (Vec d)instance (d k : ℕ) : IsProbabilityMeasure (gaussianRows d k) := by  unfold gaussianRows  infer_instancedef labels {d k : ℕ} (A : Rows d k) (s : Vec d) : Labels k :=  fun i => ⟪A i, s⟫lemma measurable_labels {d k : ℕ} :    Measurable (fun z : Rows d k × Vec d => labels z.1 z.2) := by  unfold labels  fun_propdef messageKernel {d k N : ℕ} (κ : Kernel (Data d k) (Fin N)) :    Kernel (Vec d × Rows d k) (Fin N) :=  κ.comap (fun z => (z.2, labels z.2 z.1)) (by    unfold labels    fun_prop)instance {d k N : ℕ} (κ : Kernel (Data d k) (Fin N)) [IsMarkovKernel κ] :    IsMarkovKernel (messageKernel κ) := by  unfold messageKernel  infer_instancedef signalMessageLaw {d k N : ℕ} (p : Measure (Vec d))    (κ : Kernel (Data d k) (Fin N)) : Measure (Vec d × Fin N) :=  ((p.prod (gaussianRows d k)) ⊗ₘ messageKernel κ).map    (fun z => (z.1.1, z.2))instance {d k N : ℕ} (p : Measure (Vec d)) [IsProbabilityMeasure p]    (κ : Kernel (Data d k) (Fin N)) [IsMarkovKernel κ] :    IsProbabilityMeasure (signalMessageLaw p κ) := by  unfold signalMessageLaw  infer_instancedef sideLaw {d N : ℕ} (ℓ : ℕ) (q : Measure (Vec d × Fin N)) :    Measure (Data d ℓ × (Vec d × Fin N)) :=  ((gaussianRows d ℓ).prod q).map    (fun z => ((z.1, labels z.1 z.2.1), z.2))instance {d N : ℕ} (ℓ : ℕ) (q : Measure (Vec d × Fin N)) [IsProbabilityMeasure q] :    IsProbabilityMeasure (sideLaw ℓ q) := by  unfold sideLaw  infer_instancedef messageEntropy {d N : ℕ} (q : Measure (Vec d × Fin N)) : ℝ :=  ∑ w : Fin N, -(q.snd.real {w}) * Real.log (q.snd.real {w})def conditionalInformation {d ℓ N : ℕ} [NeZero N]    (μ : Measure (Data d ℓ × (Vec d × Fin N))) [IsFiniteMeasure μ] : ℝ≥0∞ :=  klDiv μ (μ.fst ⊗ₘ (μ.condKernel.fst ×ₖ μ.condKernel.snd))def GaussianReplicaBlock : Prop :=  ∃ C : ℝ, 0 < C ∧ ∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d →    let k := 2 * (d / 16)    let t := k + 1    let ℓ := 4 * k    ∀ (p : Measure (Vec d)) [IsProbabilityMeasure p]      (f : Vec d → ℝ) (L : ℝ),      Measurable f → (∀ x, 0 ≤ f x ∧ f x ≤ L) →      p = (sphereLaw d).withDensity (fun x => ENNReal.ofReal (f x)) →      ∀ (N : ℕ) [NeZero N] (κ : Kernel (Data d k) (Fin N)) [IsMarkovKernel κ],        conditionalInformation (sideLaw ℓ (signalMessageLaw p κ)) ≤          ENNReal.ofReal (messageEntropy (signalMessageLaw p κ) / (t : ℝ) +            C * (d : ℝ) + C * Real.log (2 + Real.log L))inductive BaseLaw where  | spherical  | gaussian  deriving DecidableEqdef BaseLaw.measure (base : BaseLaw) (d : ℕ) : Measure (Vec d) :=  match base with  | .spherical => sphereLaw d  | .gaussian => stdGaussian (Vec d)def rowGram {d k : ℕ} (A : Rows d k) : Matrix (Fin k) (Fin k) ℝ :=  fun i j => ⟪A i, A j⟫def liftLabel {d k : ℕ} (A : Rows d k) (y : Labels k) : Vec d :=  ∑ i, ((rowGram A)⁻¹ *ᵥ y) i • A idef kernelComponent {d k : ℕ} (A : Rows d k) (x : Vec d) : Vec d :=  x - liftLabel A (labels A x)def baseFiber {d k : ℕ} (base : BaseLaw) (A : Rows d k) (y : Labels k) :    Measure (Vec d) :=  match base with  | .gaussian => (stdGaussian (Vec d)).map      (fun x => liftLabel A y + kernelComponent A x)  | .spherical => (stdGaussian (Vec d)).map      (fun x => liftLabel A y +        (Real.sqrt (1 - ‖liftLabel A y‖ ^ 2) / ‖kernelComponent A x‖) •          kernelComponent A x)def baseDensity {d k : ℕ} (base : BaseLaw) (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=  if LinearIndependent ℝ A then    match base with    | .gaussian => ENNReal.ofReal        ((2 * Real.pi) ^ (-(k : ℝ) / 2) *          Real.exp (-‖liftLabel A y‖ ^ 2 / 2) / Real.sqrt (rowGram A).det)    | .spherical => if ‖liftLabel A y‖ < 1 then ENNReal.ofReal        (Real.Gamma ((d : ℝ) / 2) /          (Real.pi ^ ((k : ℝ) / 2) * Real.Gamma (((d : ℝ) - k) / 2)) *          (1 - ‖liftLabel A y‖ ^ 2) ^ (((d : ℝ) - k - 2) / 2) /          Real.sqrt (rowGram A).det) else 0  else 0def tiltMass {d k : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=  ∫⁻ x, f x ∂baseFiber base A ydef projectedDensity {d k : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=  baseDensity base A y * tiltMass base f A ydef tiltedFiber {d k : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (A : Rows d k) (y : Labels k) : Measure (Vec d) :=  if tiltMass base f A y = 0 then Measure.dirac 0  else (tiltMass base f A y)⁻¹ • (baseFiber base A y).withDensity fdef differences {d m : ℕ} (u : Tuple d m) : Fin m → Vec d :=  fun i => u i.succ - u 0def differenceSpan {d m : ℕ} (u : Tuple d m) : Submodule ℝ (Vec d) :=  Submodule.span ℝ (Set.range (differences u))def affineVolume {d m : ℕ} (u : Tuple d m) : ℝ :=  Real.sqrt (Matrix.gram ℝ (differences u)).detdef constrainedRows {d m : ℕ} (k : ℕ) (u : Tuple d m) : Measure (Rows d k) :=  (gaussianRows d k).map    (fun A i => (differenceSpan u)ᗮ.starProjection (A i))def equalLabelLeft {d k m : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (H : Rows d k × Labels k × Tuple d m → ℝ≥0∞) : ℝ≥0∞ :=  ∫⁻ A, ∫⁻ y, (projectedDensity base f A y) ^ (m + 1) *    ∫⁻ u, H (A, y, u) ∂Measure.pi (fun _ : Fin (m + 1) => tiltedFiber base f A y)      ∂volume ∂gaussianRows d kdef equalLabelRight {d k m : ℕ} (base : BaseLaw) (f : Vec d → ℝ≥0∞)    (H : Rows d k × Labels k × Tuple d m → ℝ≥0∞) : ℝ≥0∞ :=  ENNReal.ofReal ((2 * Real.pi) ^ (-(k * m : ℝ) / 2)) *    ∫⁻ u, (ENNReal.ofReal (affineVolume u))⁻¹ ^ k *      ∫⁻ A, H (A, labels A (u 0), u) ∂constrainedRows k u      ∂Measure.pi (fun _ : Fin (m + 1) => (base.measure d).withDensity f)def EqualLabelMeasureIdentity : Prop :=  ∀ (d k m : ℕ), 1 ≤ k → 1 ≤ m → k + m ≤ d - 2 →    ∀ (base : BaseLaw) (f : Vec d → ℝ≥0∞), Measurable f →      (∃ L : ℝ≥0∞, L ≠ ∞ ∧ ∀ x, f x ≤ L) →      equalLabelLeft (k := k) (m := m) base f (fun _ => 1) < ∞ ∧      ∀ H : Rows d k × Labels k × Tuple d m → ℝ≥0∞,        Measurable H → equalLabelLeft base f H = equalLabelRight base f Hdef DistanceReplicaBlock : Prop :=  ∃ C : ℝ, 0 < C ∧ ∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d →    ∀ (p : Measure (Vec d)) [IsProbabilityMeasure p]      (f : Vec d → ℝ) (b : ℝ),      0 ≤ b → Measurable f → (∀ x, 0 ≤ f x ∧ f x ≤ Real.exp b) →      p = (sphereLaw d).withDensity (fun x => ENNReal.ofReal (f x)) →      ∀ (N : ℕ) [NeZero N] (κ : Kernel (Data d (d / 16)) (Fin N)) [IsMarkovKernel κ],        conditionalInformation (sideLaw (d / 2) (signalMessageLaw p κ)) ≤          ENNReal.ofReal (messageEntropy (signalMessageLaw p κ) / ((d / 8 : ℕ) : ℝ) +            C * ((d : ℝ) + b / (d : ℝ)))def SyntheticReplicaBlock : Prop :=  ∃ C : ℝ, 0 < C ∧ ∀ d : ℕ, 16 ≤ d →    ∀ (p : Measure (Vec d)) [IsProbabilityMeasure p]      (f : Vec d → ℝ) (L : ℝ),      1 ≤ L → Measurable f → (∀ x, 0 ≤ f x ∧ f x ≤ L) →      p = (sphereLaw d).withDensity (fun x => ENNReal.ofReal (f x)) →      ∀ (N : ℕ) [NeZero N] (z : Data d (d / 8) → Fin N) (hz : Measurable z),        conditionalInformation          (sideLaw (d / 2) (signalMessageLaw p (Kernel.deterministic z hz))) ≤          ENNReal.ofReal (Real.log (N : ℝ) / ((d / 8 : ℕ) : ℝ) +            C * ((d : ℝ) + Real.log (1 + Real.log L)))def IncidenceReplicaBlock : Prop :=  ∃ C : ℝ, 0 < C ∧ ∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d →    ∀ (p : Measure (Vec d)) [IsProbabilityMeasure p]      (f : Vec d → ℝ) (F : ℝ),      1 ≤ F → Measurable f → (∀ x, 0 ≤ f x ∧ f x ≤ F) →      p = (sphereLaw d).withDensity (fun x => ENNReal.ofReal (f x)) →      ∀ (N : ℕ) [NeZero N] (κ : Kernel (Data d (d / 16)) (Fin N)) [IsMarkovKernel κ],        conditionalInformation (sideLaw (d / 4) (signalMessageLaw p κ)) ≤          ENNReal.ofReal (Real.log (N : ℝ) / ((d / 16 : ℕ) : ℝ) +            C * (d : ℝ) + C * Real.log (1 + Real.log F))def labelNorm {k : ℕ} (y : Labels k) : ℝ := ‖WithLp.toLp 2 y‖def ballDensityVersion {d k : ℕ} (ν : Measure (Vec d))    (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=  Filter.liminf (fun n : ℕ =>    ((volume : Measure (Labels k)) {v | labelNorm v < (n + 1 : ℝ)⁻¹})⁻¹ *      ν {x | labelNorm (labels A x - y) < (n + 1 : ℝ)⁻¹}) Filter.atTopdef gaussianDensityVersion {d k : ℕ} (ν : Measure (Vec d))    (A : Rows d k) (y : Labels k) : ℝ≥0∞ :=  Filter.liminf (fun n : ℕ => ∫⁻ x,    ENNReal.ofReal ((2 * Real.pi * ((n + 1 : ℝ)⁻¹)^2) ^ (-(k : ℝ) / 2) *      Real.exp (-(labelNorm (labels A x - y))^2 / (2 * ((n + 1 : ℝ)⁻¹)^2))) ∂ν)    Filter.atTopdef EqualLabelVersions : Prop :=  ∀ (d k m : ℕ), 1 ≤ k → 1 ≤ m → k + m ≤ d - 2 →    ∀ (base : BaseLaw) (f : Vec d → ℝ≥0∞), Measurable f →      (∃ L : ℝ≥0∞, L ≠ ∞ ∧ ∀ x, f x ≤ L) →      let ν := (base.measure d).withDensity f      (Measurable (fun z : Rows d k × Labels k => projectedDensity base f z.1 z.2)) ∧      (Measurable (fun z : Rows d k × Labels k => ballDensityVersion ν z.1 z.2)) ∧      (Measurable (fun z : Rows d k × Labels k => gaussianDensityVersion ν z.1 z.2)) ∧      (∀ A : Rows d k, LinearIndependent ℝ A →        ν.map (labels A) = volume.withDensity (projectedDensity base f A) ∧        projectedDensity base f A =ᵐ[volume] ballDensityVersion ν A ∧        projectedDensity base f A =ᵐ[volume] gaussianDensityVersion ν A) ∧      (∀ᵐ u ∂Measure.pi (fun _ : Fin (m + 1) => ν),        LinearIndependent ℝ (differences u) ∧        ∀ᵐ A ∂constrainedRows k u,          LinearIndependent ℝ A ∧          (∀ i, labels A (u i) = labels A (u 0)) ∧          (base = .spherical → ‖liftLabel A (labels A (u 0))‖ < 1) ∧          0 < projectedDensity base f A (labels A (u 0)) ∧          projectedDensity base f A (labels A (u 0)) ≠ ∞ ∧          projectedDensity base f A (labels A (u 0)) =            ballDensityVersion ν A (labels A (u 0)) ∧          projectedDensity base f A (labels A (u 0)) =            gaussianDensityVersion ν A (labels A (u 0)))def haarRows (d ℓ : ℕ) : Measure (Rows d ℓ) :=  (gaussianRows d ℓ).map (InnerProductSpace.gramSchmidtNormed ℝ)def cmi {Z X Y : Type*} [MeasurableSpace Z] [MeasurableSpace X] [MeasurableSpace Y]    [StandardBorelSpace X] [StandardBorelSpace Y] [Nonempty X] [Nonempty Y]    (μ : Measure (Z × (X × Y))) [IsFiniteMeasure μ] : ℝ≥0∞ :=  klDiv μ (μ.fst ⊗ₘ (μ.condKernel.fst ×ₖ μ.condKernel.snd))def finiteEntropy {J : Type*} [Fintype J] [MeasurableSpace J] (μ : Measure J) : ℝ :=  ∑ j, - μ.real {j} * Real.log (μ.real {j})def stateMessageKernel {d k V W : ℕ} (κ : Kernel (Fin V × Data d k) (Fin W)) :    Kernel ((Vec d × Fin V) × Rows d k) (Fin W) :=  κ.comap (fun z => (z.1.2, (z.2, labels z.2 z.1.1))) (by unfold labels; fun_prop)instance {d k V W : ℕ} (κ : Kernel (Fin V × Data d k) (Fin W)) [IsMarkovKernel κ] :    IsMarkovKernel (stateMessageKernel κ) := by  unfold stateMessageKernel  infer_instancedef stateMessageLaw {d k V W : ℕ} (q : Measure (Vec d × Fin V))    (κ : Kernel (Fin V × Data d k) (Fin W)) : Measure ((Vec d × Fin V) × Fin W) :=  (((q.prod (gaussianRows d k)) ⊗ₘ stateMessageKernel κ).map    (fun z => (z.1.1, z.2)))instance {d k V W : ℕ} (q : Measure (Vec d × Fin V)) [IsProbabilityMeasure q]    (κ : Kernel (Fin V × Data d k) (Fin W)) [IsMarkovKernel κ] :    IsProbabilityMeasure (stateMessageLaw q κ) := by  unfold stateMessageLaw  infer_instancedef stateHaarSideLaw {d V W : ℕ} (ℓ : ℕ)    (q : Measure ((Vec d × Fin V) × Fin W)) :    Measure ((Fin V × Data d ℓ) × (Vec d × Fin W)) :=  ((haarRows d ℓ).prod q).map    (fun z => ((z.2.1.2, (z.1, labels z.1 z.2.1.1)), (z.2.1.1, z.2.2)))instance {d V W : ℕ} (ℓ : ℕ)    (q : Measure ((Vec d × Fin V) × Fin W)) [IsFiniteMeasure q] :    IsFiniteMeasure (stateHaarSideLaw ℓ q) := by  unfold stateHaarSideLaw haarRows  infer_instancedef terminalConditionalEntropy {d V W : ℕ}    (q : Measure ((Vec d × Fin V) × Fin W)) : ℝ :=  finiteEntropy (q.map (fun z => (z.1.2, z.2))) - finiteEntropy (q.map (fun z => z.1.2))def HaarReplicaBlock : Prop :=  ∃ C : ℝ, 0 < C ∧ ∀ d : ℕ, 64 ≤ d →    ∀ (V W : ℕ) [NeZero V] [NeZero W]      (q : Measure (Vec d × Fin V)) [IsProbabilityMeasure q],      q.fst = sphereLaw d →      ∀ (κ : Kernel (Fin V × Data d (d / 16)) (Fin W)) [IsMarkovKernel κ],        cmi (stateHaarSideLaw (d / 4) (stateMessageLaw q κ)) ≤          ENNReal.ofReal (terminalConditionalEntropy (stateMessageLaw q κ) /            ((d / 16 + 1 : ℕ) : ℝ) + C * (d : ℝ) +            Real.log (1 + C * (d : ℝ) + finiteEntropy q.snd) +            C * (finiteEntropy q.snd + Real.log (d : ℝ)) / (d : ℝ)^2)end PosteriorReplicasendendopen MeasureTheory ProbabilityTheory Set Filteropen scoped ENNReal NNReal RealInnerProductSpacenoncomputable sectionuniverse unamespace PosteriorRegressionabbrev Vector (d : ℕ) := EuclideanSpace ℝ (Fin d)abbrev UnitSphere (d : ℕ) := Metric.sphere (0 : Vector d) 1abbrev State (M : ℕ) := Fin (2 ^ M)abbrev Samples (d T : ℕ) := Fin T → Vector ddef uniformSphere (d : ℕ) : Measure (UnitSphere d) :=  let σ := (volume : Measure (Vector d)).toSphere  (σ Set.univ)⁻¹ • σdef sampleLaw (d T : ℕ) : Measure (Samples d T) :=  Measure.pi fun _ => stdGaussian (Vector d)def observationReference (d : ℕ) : Measure (Vector d × ℝ) :=  (stdGaussian (Vector d)).prod volumenamespace Learnerabbrev RunStatus (M : ℕ) := Sum (State M) (ℕ × State M)def angularError {d : ℕ} (s ŝ : UnitSphere d) : ℝ :=  Real.arccos ⟪ŝ.val, s.val⟫end Learnerend PosteriorRegressionopen MeasureTheory ProbabilityTheory InformationTheory Set Matrixopen scoped ENNReal NNReal RealInnerProductSpace Classicalnoncomputable sectionnamespace PosteriorRegressionabbrev CompletedObservation (d : ℕ) := NullMeasurableSpace (Vector d × ℝ) (observationReference d)abbrev Destination (M : ℕ) := Bool × State Mstructure CompletedKernelLearner (d M : ℕ) where  initial : Measure (Destination M)  initial_probability : IsProbabilityMeasure initial  transition : ℕ → State M → Kernel (CompletedObservation d) (Destination M)  transition_markov : ∀ t a, IsMarkovKernel (transition t a)  output : ℕ → State M → Measure (UnitSphere d)  output_probability : ∀ t a, IsProbabilityMeasure (output t a)attribute [instance] CompletedKernelLearner.initial_probability  CompletedKernelLearner.transition_markov CompletedKernelLearner.output_probabilitynamespace CompletedKernelLearneropen Learnerdef destStatus {M : ℕ} (n : ℕ) (v : Destination M) : RunStatus M :=  if v.1 then Sum.inr (n,v.2) else Sum.inl v.2def finishState {M : ℕ} (T : ℕ) : RunStatus M → ℕ × State M  | .inl a => (T,a)  | .inr done => donedef stepMeasure {d M T : ℕ} (K : CompletedKernelLearner d M)    (s : UnitSphere d) (x : Samples d T) (i : Fin T) : RunStatus M → Measure (RunStatus M)  | .inr done => Measure.dirac (.inr done)  | .inl a => (K.transition (i.val+1) a (x i,⟪x i,s.val⟫)).map (destStatus (i.val+1))def runMeasure {d M T : ℕ} (K : CompletedKernelLearner d M)    (s : UnitSphere d) (x : Samples d T) : ℕ → Measure (RunStatus M)  | 0 => K.initial.map (destStatus 0)  | n+1 => if hn : n<T then (K.runMeasure s x n).bind (K.stepMeasure s x ⟨n,hn⟩)      else K.runMeasure s x ndef terminalLaw {d M T : ℕ} (K : CompletedKernelLearner d M)    (s : UnitSphere d) (x : Samples d T) : Measure (ℕ × State M) :=  (K.runMeasure s x T).map (finishState T)def estimateLaw {d M T : ℕ} (K : CompletedKernelLearner d M)    (s : UnitSphere d) (x : Samples d T) : Measure (UnitSphere d) :=  (K.terminalLaw s x).bind (fun a => K.output a.1 a.2)end CompletedKernelLearnerstructure JointKernelExperiment (d M T : ℕ) (Ω : Type u) [MeasurableSpace Ω]    (ρ : Measure Ω) where  rules : Ω → CompletedKernelLearner d M  outputKernel : Kernel (Ω × (UnitSphere d × Samples d T)) (UnitSphere d)  output_markov : IsMarkovKernel outputKernel  conditional_output : ∀ᵐ ω ∂ρ, ∀ᵐ z ∂((uniformSphere d).prod (sampleLaw d T)),    outputKernel (ω,z) = (rules ω).estimateLaw z.1 z.2attribute [instance] JointKernelExperiment.output_markovnamespace JointKernelExperimentopen Learnerdef law {d M T : ℕ} {Ω : Type u} [MeasurableSpace Ω] {ρ : Measure Ω}    (E : JointKernelExperiment d M T Ω ρ) : Measure ((Ω × (UnitSphere d × Samples d T)) × UnitSphere d) :=  (ρ.prod ((uniformSphere d).prod (sampleLaw d T))) ⊗ₘ E.outputKerneldef uniformSuccess {d M T : ℕ} {Ω : Type u} [MeasurableSpace Ω] {ρ : Measure Ω}    (E : JointKernelExperiment d M T Ω ρ) (ε : ℝ) : ℝ≥0∞ :=  E.law {z | angularError z.1.2.1 z.2 ≤ ε}end JointKernelExperimentdef KernelSubquadraticMemory : Prop :=  ∃ c : ℝ, 0 < c ∧ ∀ M : ℕ → ℕ,    Asymptotics.IsLittleO atTop (fun d => (M d : ℝ)) (fun d => (d : ℝ)^2) →    ∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d → ∀ T : ℕ, ∀ ε : ℝ,    0<ε → ε≤1/10 →    ∀ (Ω : Type u) [MeasurableSpace Ω] (ρ : Measure Ω), IsProbabilityMeasure ρ →    ∀ E : JointKernelExperiment d (M d) T Ω ρ,    (2/3 : ℝ≥0∞) ≤ E.uniformSuccess ε →    c * (d : ℝ) * Real.log (1/ε) ≤ (T : ℝ)end PosteriorRegressionnamespace PosteriorReplicasend PosteriorReplicasendendnamespace PosteriorReplicasuniverse utheorem source_main : EqualLabelMeasureIdentity ∧ EqualLabelVersions ∧    GaussianReplicaBlock ∧ DistanceReplicaBlock ∧ HaarReplicaBlock ∧    SyntheticReplicaBlock ∧ IncidenceReplicaBlock ∧    PosteriorRegression.KernelSubquadraticMemory.{u} := by  sorryend PosteriorReplicasend OAI

Every extracted statement of the accompanying papers

The statements the atlas extracted automatically from each accompanying paper’s TeX source, with links to the full sources.

Memory and precision in noiseless Gaussian regression

Theorem (Memory and precision)

For every fixed finite A>0, there are constants c_A>0 and d_A such that the following holds. Let d\ge d_A, let 0\le M\le Ad^2 be an integer, and let 0<\epsilon\le1/10. For any learner in Definition h:model, draw S\sim\sigma_d independently of the rows and the learner’s data-independent randomness. If

\Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}\ge\frac23,

then its prescribed horizon satisfies

T\ge c_A\,d\log(1/\epsilon).

Section 1, Exact observations and finite memory Read it in the paper TeX source, line 59

Show the TeX

For every fixed finite \(A>0\), there are constants \(c_A>0\) and
\(d_A\) such that the following holds. Let \(d\ge d_A\), let
\(0\le M\le Ad^2\) be an integer, and let \(0<\epsilon\le1/10\).
For any learner in Definition~\ref{h:model}, draw
\(S\sim\sigma_d\) independently of the rows and the learner's
data-independent randomness. If
\[
 \Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}\ge\frac23,
\]
then its prescribed horizon satisfies
\[
 T\ge c_A\,d\log(1/\epsilon).
\]

Corollary (Subquadratic memory)

Let M(d)\ge0 be integer-valued with M(d)=o(d^2), and let 0<\epsilon(d)\le1/10 be any accuracy sequence. A family of learners in Definition h:model with uniform-sphere average success at least 2/3 satisfies

T(d)\ge c\,d\log(1/\epsilon(d))

for all sufficiently large d, where c>0 is absolute. The dimension threshold may depend on the memory sequence.

Section 1, Exact observations and finite memory Read it in the paper TeX source, line 81

Show the TeX

Let \(M(d)\ge0\) be integer-valued with \(M(d)=o(d^2)\), and let
\(0<\epsilon(d)\le1/10\) be any accuracy sequence. A family of learners
in Definition~\ref{h:model} with uniform-sphere average success at
least \(2/3\) satisfies
\[
 T(d)\ge c\,d\log(1/\epsilon(d))
\]
for all sufficiently large \(d\), where \(c>0\) is absolute. The
dimension threshold may depend on the memory sequence.

Corollary (A guarantee for every signal)

The conclusions of Theorem h:main and Corollary h:subquadratic also hold when their average-success assumption is replaced by

\Prob\{\arccos\ip{\widehat s}{s}\le\epsilon\}\ge\frac23 \qquad\text{for every }s\in S^{d-1},

where this probability is over the rows and the learner’s randomness.

Section 1, Exact observations and finite memory Read it in the paper TeX source, line 93

Show the TeX

The conclusions of Theorem~\ref{h:main} and
Corollary~\ref{h:subquadratic} also hold when their average-success
assumption is replaced by
\[
 \Prob\{\arccos\ip{\widehat s}{s}\le\epsilon\}\ge\frac23
 \qquad\text{for every }s\in S^{d-1},
\]
where this probability is over the rows and the learner's randomness.

Posterior replicas and conditional information in Gaussian regression

Theorem (Gaussian replica block bound)

For all sufficiently large d, set

k=2\lfloor d/16\rfloor,\qquad m=k,\qquad t=m+1,\qquad \ell=4k.

Suppose p=f\sigma_d is a probability with 0\le f\le L<\infty. In the block experiment above, let A have k rows and let B have \ell rows. There is an absolute constant C such that

I(S;W\mid B,BS) \le \frac{H(W)}{t}+Cd+C\log(2+\log L).

The bound is uniform over the prior, the density bound L, and the message kernel. The labels used to produce W are the exact values AS.

Section 1, Introduction Read it in the paper TeX source, line 81

Show the TeX

For all sufficiently large $d$, set
\[
 k=2\lfloor d/16\rfloor,\qquad m=k,\qquad t=m+1,\qquad \ell=4k.
\]
Suppose $p=f\sigma_d$ is a probability with $0\le f\le L<\infty$.
In the block experiment above, let $A$ have $k$ rows and let $B$ have
$\ell$ rows. There is an absolute constant $C$ such that
\begin{equation}
 I(S;W\mid B,BS)
 \le \frac{H(W)}{t}+Cd+C\log(2+\log L).
\end{equation}
The bound is uniform over the prior, the density bound $L$, and the message
kernel. The labels used to produce $W$ are the exact values $AS$.

Theorem (Uniform-prior sample lower bound)

Let M(d)=o(d^2) be nonnegative integer-valued, and let 0<\epsilon(d)\le1/10. Suppose a family of learners in Definition def:streaming-model satisfies

\Prob\{\arccos\langle\widehat S,S\rangle\le\epsilon(d)\}\ge\frac23 \qquad\text{when }S\sim\sigma_d,

where the probability includes the signal, samples, and learner randomness. Then there is an absolute c>0 such that

T(d)\ge c\,d\log\frac1{\epsilon(d)}

for all sufficiently large d. The eventual threshold may depend on the memory sequence.

Section 1, Introduction Read it in the paper TeX source, line 147

Show the TeX

Let $M(d)=o(d^2)$ be nonnegative integer-valued, and let
$0<\epsilon(d)\le1/10$. Suppose a family of learners in
Definition~\ref{def:streaming-model} satisfies
\[
 \Prob\{\arccos\langle\widehat S,S\rangle\le\epsilon(d)\}\ge\frac23
 \qquad\text{when }S\sim\sigma_d,
\]
where the probability includes the signal, samples, and learner randomness.
Then there is an absolute $c>0$ such that
\[
 T(d)\ge c\,d\log\frac1{\epsilon(d)}
\]
for all sufficiently large $d$. The eventual threshold may depend on the
memory sequence.

Localization costs and information growth for exact Gaussian observations

Theorem (Repeated localization)

There is an absolute constant c>0 with the following property. For any fixed C_0>0, consider the experiment above with t\ge0 blocks and N\ge1 possible message values, and suppose

\bigl(2/m+e^{-ck}\bigr)\log N\le C_0d.

One can reveal nested dyadic cells Q_0\supset Q_1\supset\cdots\supset Q_t containing Z, where Q_i is a finite-valued measurable function of Z, the preceding revelations, and W_1,\ldots,W_i, so that the augmented transcript

\Pi_t=(W_1,Q_1,\ldots,W_t,Q_t)

satisfies

I(Z;\Pi_t)\le Cdt.

Here C is a constant depending only on C_0. If J_t is the level of Q_t, the construction also gives \E J_t\le Ct.

Section 3, Dyadic localization and its information cost Read it in the paper TeX source, line 54

Show the TeX

There is an absolute constant $c>0$ with the following property.
For any fixed $C_0>0$, consider the experiment above with $t\ge0$
blocks and $N\ge1$ possible message values, and suppose
\begin{equation}
 \bigl(2/m+e^{-ck}\bigr)\log N\le C_0d.
\end{equation}
One can reveal nested dyadic cells
$Q_0\supset Q_1\supset\cdots\supset Q_t$ containing $Z$, where $Q_i$
is a finite-valued measurable function of $Z$, the preceding revelations,
and $W_1,\ldots,W_i$, so that the augmented transcript
\[
 \Pi_t=(W_1,Q_1,\ldots,W_t,Q_t)
\]
satisfies
\begin{equation}
 I(Z;\Pi_t)\le Cdt.
\end{equation}
Here $C$ is a constant depending only on $C_0$. If $J_t$ is the level of $Q_t$, the
construction also gives $\E J_t\le Ct$.

Theorem (Precision lower bound from likelihood truncation)

Let M(d)=o(d^2) be a nonnegative integer-valued memory bound, and let 0<\epsilon(d)\le1/10. Suppose a family of learners in the model above satisfies

\mathbb P\!\left\{\arccos\langle\widehat s,s\rangle \le\epsilon(d)\right\}\ge\frac23 \qquad\text{for every }s\in S^{d-1}.

There is an absolute c>0 such that, for all sufficiently large d,

T(d)\ge c\,d\log_2\frac1{\epsilon(d)}.

The eventual dimension threshold may depend on the memory sequence.

Section 7, Likelihood truncation and selected dyadic cells Read it in the paper TeX source, line 34

Show the TeX

Let $M(d)=o(d^2)$ be a nonnegative integer-valued memory bound, and let
$0<\epsilon(d)\le1/10$.  Suppose a family of learners in the model
above satisfies
\[
 \mathbb P\!\left\{\arccos\langle\widehat s,s\rangle
              \le\epsilon(d)\right\}\ge\frac23
 \qquad\text{for every }s\in S^{d-1}.
\]
There is an absolute $c>0$ such that, for all sufficiently large $d$,
\[
 T(d)\ge c\,d\log_2\frac1{\epsilon(d)}.
\]
The eventual dimension threshold may depend on the memory sequence.

Theorem (The sample bound by separated-tuple localization)

Let M(d)=o(d^2) be integer-valued and let 0<\epsilon(d)\le1/10. Every learner of Section l:model with uniform-sphere angular success probability at least 2/3 must satisfy

T(d)\ge c\,d\log(1/\epsilon(d))

for all sufficiently large d, with an absolute c>0. The eventual dimension threshold may depend on the memory sequence. Success at least 2/3 for every fixed signal implies the same conclusion by averaging.

Section 10, Localization by separated tuples Read it in the paper TeX source, line 727

Show the TeX

Let \(M(d)=o(d^2)\) be integer-valued and let
\(0<\epsilon(d)\le1/10\).  Every learner of
Section~\ref{l:model} with uniform-sphere angular success probability
at least \(2/3\) must satisfy
\[
 T(d)\ge c\,d\log(1/\epsilon(d))
\]
for all sufficiently large \(d\), with an absolute \(c>0\).
The eventual dimension threshold may depend on the memory sequence.
Success at least \(2/3\) for every fixed signal implies the same
conclusion by averaging.

Projection moments, positive cap domination, and Riesz estimates on the sphere

Theorem (Finite-memory precision bound)

Let M(d)=o(d^2) be a sequence of nonnegative integers and let 0<\epsilon(d)\le1/10. There is an absolute c>0 such that, for all sufficiently large d, every learner in the experiment above whose uniform-sphere average success satisfies

\Prob\{\arccos\inner{\widehat S}{S}\le\epsilon(d)\}\ge\frac23

must use

T(d)\ge c\,d\log\frac1{\epsilon(d)}.

The dimension threshold may depend on the memory sequence. In particular, the conclusion holds when the same success probability is required separately for every s\in S^{d-1}.

Section 2, Spherical probabilities and exact observations Read it in the paper TeX source, line 175

Show the TeX

Let \(M(d)=o(d^2)\) be a sequence of nonnegative integers and let
\(0<\epsilon(d)\le1/10\). There is an absolute \(c>0\) such that, for
all sufficiently large \(d\), every learner in the experiment above whose
uniform-sphere average success satisfies
\[
 \Prob\{\arccos\inner{\widehat S}{S}\le\epsilon(d)\}\ge\frac23
\]
must use
\[
 T(d)\ge c\,d\log\frac1{\epsilon(d)}.
\]
The dimension threshold may depend on the memory sequence. In particular,
the conclusion holds when the same success probability is required
separately for every \(s\in S^{d-1}\).

Theorem (Integrated orthonormal-projection moment)

Let d,k,q be integers and \beta a real number with k\ge1, q\ge2, and

k+q\le d,\qquad 0<\beta\le d,\qquad \beta-k-(q-2)\ge1.

Let \nu be a finite positive Borel measure supported in B(z,R), R>0, satisfying (p:all-ball-mass) for some K\ge0. Assume that P_\#\nu is absolutely continuous with respect to Lebesgue measure for \vartheta_{d,k}-almost every P. There is a jointly measurable version g(P,u) of its density such that

\left(\int_{\mathcal V_{d,k}}\int_{\R^k}g(P,u)^q\,du\, d\vartheta_{d,k}(P)\right)^{1/q} \le C^d(C\sqrt d)^{k(1-1/q)} K R^{\beta-k(1-1/q)}.

For every P, this version vanishes when \norm{u-Pz}>R.

Section 3, Integrated moments of orthonormal projections Read it in the paper TeX source, line 168

Show the TeX

Let \(d,k,q\) be integers and \(\beta\) a real number with
\(k\ge1\), \(q\ge2\), and
\begin{equation}
 k+q\le d,\qquad 0<\beta\le d,\qquad
 \beta-k-(q-2)\ge1.
\end{equation}
Let \(\nu\) be a finite positive Borel measure supported in
\(B(z,R)\), \(R>0\), satisfying \eqref{p:all-ball-mass} for some
\(K\ge0\). Assume that \(P_\#\nu\) is absolutely continuous with
respect to Lebesgue measure for \(\vartheta_{d,k}\)-almost every \(P\).
There is a jointly measurable version \(g(P,u)\) of its density such that
\begin{equation}
 \left(\int_{\mathcal V_{d,k}}\int_{\R^k}g(P,u)^q\,du\,
 d\vartheta_{d,k}(P)\right)^{1/q}
 \le C^d(C\sqrt d)^{k(1-1/q)}
 K R^{\beta-k(1-1/q)}.
\end{equation}
For every \(P\), this version vanishes when \(\norm{u-Pz}>R\).

Theorem (Normalized moment for unit-ball measures)

For sufficiently large d, put

k=p=\lfloor d/16\rfloor,\qquad \lambda=(d-1)/2.

Let X be a k-by-d standard Gaussian matrix and define

H=(XX^{\mathsf T})^{1/2},\qquad P=H^{-1}X

on its probability-one full-row-rank event, and set P to a fixed frame on the null complement. Let m_k be uniform probability on the unit ball of \R^k. Suppose \nu is a finite positive Borel measure fixed independently of X, of mass at most one, supported in the unit ball of \R^d, such that for a fixed D>0,

\nu(B(b,t))\le D^d t^\lambda \qquad(b\in\R^d,\ t>0).

Assume P_\#\nu is absolutely continuous for almost every X. There is a jointly measurable nonnegative g_X(z) such that, for almost every X, P_\#\nu(dz)=g_X(z)\,dz/v_k. This version vanishes when \norm z>1 and satisfies

\E_X\int g_X(z)^p\,dm_k(z)\le \exp(C_Ddp).

Section 3, Integrated moments of orthonormal projections Read it in the paper TeX source, line 288

Show the TeX

For sufficiently large \(d\), put
\[
 k=p=\lfloor d/16\rfloor,\qquad \lambda=(d-1)/2.
\]
Let \(X\) be a \(k\)-by-\(d\) standard Gaussian matrix and define
\[
 H=(XX^{\mathsf T})^{1/2},\qquad P=H^{-1}X
\]
on its probability-one full-row-rank event, and set \(P\) to a fixed frame
on the null complement. Let \(m_k\) be uniform
probability on the unit ball of \(\R^k\). Suppose \(\nu\) is a finite
positive Borel measure fixed independently of \(X\), of mass at most one, supported in the unit ball
of \(\R^d\), such that for a fixed \(D>0\),
\[
 \nu(B(b,t))\le D^d t^\lambda
 \qquad(b\in\R^d,\ t>0).
\]
Assume \(P_\#\nu\) is absolutely continuous for almost every \(X\).
There is a jointly measurable nonnegative \(g_X(z)\) such that, for almost
every \(X\), \(P_\#\nu(dz)=g_X(z)\,dz/v_k\). This version vanishes when
\(\norm z>1\) and satisfies
\begin{equation}
 \E_X\int g_X(z)^p\,dm_k(z)\le \exp(C_Ddp).
\end{equation}

Replacing Gaussian observations in memory-constrained inference

Theorem (Mixed projection moment and exact density version)

Let n=d-1, let m,r,q\ge1 be integers, and put \ell=m+r. Suppose

\ell<n,\qquad \ell-m-(q-1)\ge1.

Let \rho be a finite nonnegative Borel measure on S^{d-1}. Suppose that B,D>0 and, for every z\in\R^d and t>0,

\rho(B(z,t))\le Bt^\ell,\qquad \rho(B(z,t))\le Dt^n.

Let X\sim\gamma_m and Z\sim\gamma_r be independent, and set G=(X;Z). For \delta>0, define the cube average

p_{\rho,\delta}(g,y) =(2\delta)^{-\ell}\int \ind_{\{\norm{gu-y}_\infty\le\delta\}}\,d\rho(u).

There is an absolute C such that, for every fixed s\in S^{d-1} and every \delta>0,

\left[\E_X \left(\E_Z p_{\rho,\delta}((X;Z),(X;Z)s)\right)^q \right]^{1/q} \le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).

If in addition \rho\ll\sigma, use the jointly Borel density p_\rho in (eq:r-density-version). There is a measurable set E_\rho\subset S^{d-1}, with \rho(E_\rho)=0, such that for every s\notin E_\rho the cube averages converge to p_\rho(G,Gs) for \gamma_\ell-almost every G, and

\left[\E_X \left(\E_Zp_\rho((X;Z),(X;Z)s)\right)^q \right]^{1/q} \le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).

When \rho\ne0, E_\rho may also be chosen so that 0<p_\rho(G,Gs)<\infty for \gamma_\ell-almost every G and every s\notin E_\rho.

Section 3, A projection moment with shared and fresh rows Read it in the paper TeX source, line 23

Show the TeX

Let \(n=d-1\), let \(m,r,q\ge1\) be integers, and put
\(\ell=m+r\).  Suppose
\begin{equation}
 \ell<n,\qquad \ell-m-(q-1)\ge1.
\end{equation}
Let \(\rho\) be a finite nonnegative Borel measure on \(S^{d-1}\).
Suppose that \(B,D>0\) and, for every \(z\in\R^d\) and \(t>0\),
\begin{equation}
 \rho(B(z,t))\le Bt^\ell,\qquad
 \rho(B(z,t))\le Dt^n.
\end{equation}
Let \(X\sim\gamma_m\) and \(Z\sim\gamma_r\) be independent, and set
\(G=(X;Z)\).  For \(\delta>0\), define the cube average
\[
 p_{\rho,\delta}(g,y)
   =(2\delta)^{-\ell}\int
       \ind_{\{\norm{gu-y}_\infty\le\delta\}}\,d\rho(u).
\]
There is an absolute \(C\) such that, for every fixed
\(s\in S^{d-1}\) and every \(\delta>0\),
\begin{equation}
 \left[\E_X
       \left(\E_Z p_{\rho,\delta}((X;Z),(X;Z)s)\right)^q
 \right]^{1/q}
 \le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).
\end{equation}

If in addition \(\rho\ll\sigma\), use the jointly Borel density
\(p_\rho\) in \eqref{eq:r-density-version}.  There is a measurable
set \(E_\rho\subset S^{d-1}\), with \(\rho(E_\rho)=0\), such that
for every \(s\notin E_\rho\) the cube averages converge to
\(p_\rho(G,Gs)\) for \(\gamma_\ell\)-almost every \(G\), and
\begin{equation}
 \left[\E_X
       \left(\E_Zp_\rho((X;Z),(X;Z)s)\right)^q
 \right]^{1/q}
 \le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).
\end{equation}
When \(\rho\ne0\), \(E_\rho\) may also be chosen so that
\(0<p_\rho(G,Gs)<\infty\) for \(\gamma_\ell\)-almost every \(G\)
and every \(s\notin E_\rho\).

Theorem (Critical-radius comparison)

In the two experiments of Subsection subsec:r-two-experiments, use the dimensions (eq:r-critical-parameters). Thus S\sim\sigma, A\sim\gamma_m is independent of S, and W is countable with an arbitrary joint dependence on (S,A). The aligned law retains (S,A,W) and appends independent r-row C, whereas the independent law retains (S,W) and draws an independent \ell-row matrix G. If H(W)\le d^2, then, for an absolute constant K,

I_0(S;W\mid G,GS)\le I_1(S;W\mid G,GS)+Kd.

Section 4, A critical radius makes the density terms cancel Read it in the paper TeX source, line 22

Show the TeX

In the two experiments of Subsection~\ref{subsec:r-two-experiments},
use the dimensions \eqref{eq:r-critical-parameters}.  Thus
\(S\sim\sigma\), \(A\sim\gamma_m\) is independent of \(S\), and
\(W\) is countable with an arbitrary joint dependence on \((S,A)\).
The aligned law retains \((S,A,W)\) and appends independent
\(r\)-row \(C\), whereas the independent law retains \((S,W)\)
and draws an independent \(\ell\)-row matrix \(G\).
If \(H(W)\le d^2\), then, for an absolute constant \(K\),
\begin{equation}
 I_0(S;W\mid G,GS)\le I_1(S;W\mid G,GS)+Kd.
\end{equation}

Theorem (Streaming consequence of the critical radius)

Let M(d) be a nonnegative integer sequence with M(d)=o(d^2), and let 0<\epsilon(d)\le1/10. For each d, consider a learner in Definition def:r-streaming-model with deterministic finite horizon T(d). If its uniform-sphere angular success probability, including all learner randomness, is at least 3/5, then

T(d)\ge c\,d\log\frac1{\epsilon(d)}

for an absolute c>0 and all sufficiently large d. The eventual dimension threshold may depend on the memory sequence.

Section 8, From row comparisons to streaming lower bounds Read it in the paper TeX source, line 284

Show the TeX

Let \(M(d)\) be a nonnegative integer sequence with \(M(d)=o(d^2)\),
and let \(0<\epsilon(d)\le1/10\).  For each \(d\), consider a learner
in Definition~\ref{def:r-streaming-model} with deterministic finite
horizon \(T(d)\).  If its uniform-sphere angular success probability,
including all learner randomness, is at least \(3/5\), then
\[
 T(d)\ge c\,d\log\frac1{\epsilon(d)}
\]
for an absolute \(c>0\) and all sufficiently large \(d\).  The
eventual dimension threshold may depend on the memory sequence.

Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression

Theorem (Explicit noiseless precision bound)

Let M:\mathbb N\to\mathbb Z_{\ge0} satisfy M(d)=o(d^2). There is a dimension threshold depending only on this memory sequence such that, for every larger d, every 0<\epsilon\le1/10, and every learner in Definition s:model, the following implication holds. If S is uniform on S^{d-1}, independently of the Gaussian rows and learner randomness, and

\Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}\ge\frac23,

then

T\ge 2^{-16}d\log_2(1/\epsilon).

Section 1, Introduction Read it in the paper TeX source, line 53

Show the TeX

Let \(M:\mathbb N\to\mathbb Z_{\ge0}\) satisfy \(M(d)=o(d^2)\).
There is a dimension threshold depending only on this memory sequence
such that, for every larger \(d\), every \(0<\epsilon\le1/10\), and
every learner in Definition~\ref{s:model}, the following implication
holds. If \(S\) is uniform on \(S^{d-1}\), independently of the
Gaussian rows and learner randomness, and
\[
 \Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}\ge\frac23,
\]
then
\begin{equation}
 T\ge 2^{-16}d\log_2(1/\epsilon).
\end{equation}

Corollary (Guarantees for every signal)

Under the memory assumption of Theorem s:main, suppose a learner satisfies

\Prob_s\{\arccos\ip{\widehat s}{s}\le\epsilon\}\ge\frac23 \qquad\text{for every }s\in S^{d-1},

where \Prob_s averages its observations and randomness at the fixed signal s. Then (s:main-bound) holds at the same dimension threshold.

Section 1, Introduction Read it in the paper TeX source, line 69

Show the TeX

Under the memory assumption of Theorem~\ref{s:main}, suppose a learner
satisfies
\[
 \Prob_s\{\arccos\ip{\widehat s}{s}\le\epsilon\}\ge\frac23
 \qquad\text{for every }s\in S^{d-1},
\]
where \(\Prob_s\) averages its observations and randomness at the fixed
signal \(s\). Then \eqref{s:main-bound} holds at the same dimension
threshold.

Configuration and file facts

File: lean/ComparatorChallenges/PosteriorReplicas.lean
OpenAI’s Lean catalogue: OpenAI lists this as a main result in its Lean catalogue.
Solution module: OAI/Probability/PosteriorReplicas/Main.lean
Allowed axioms: propext, Quot.sound, Classical.choiceThe axioms this configuration allows a proof to use. A replay shows which of them a proof uses.
Imports: Mathlib
Imports from outside Mathlib: None
Local vocabulary: 75 local vocabulary declarations
Lines of Lean, without comments or blank lines: 323
Second proof-verification program (nanoda): Off in OpenAI's configuration.

A shareable summary of this page: the proposed paper match, what the Lean statement expresses, and which reviews are recorded.

Plectis Atlas