Lean statement

Projection, cap, and Riesz estimates with regression bounds

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.ProjectionMoments.main

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

See the closest candidates 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 main : MainStatement.{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.NoiselessRegression.Vector line 17

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

abbreviation OAI.NoiselessRegression.UnitSphere line 19

abbrev UnitSphere (d : ℕ) := Metric.sphere (0 : Vector d) 1

abbreviation OAI.NoiselessRegression.State line 21
```
abbrev State (M : ℕ) := Fin (2 ^ M)
```

abbreviation OAI.NoiselessRegression.Samples line 23

abbrev Samples (d T : ℕ) := Fin T → Vector d

definition OAI.NoiselessRegression.uniformSphere line 25

def uniformSphere (d : ℕ) : Measure (UnitSphere d) :=  let σ := (volume : Measure (Vector d)).toSphere  (σ Set.univ)⁻¹ • σ

definition OAI.NoiselessRegression.sampleLaw line 29

def sampleLaw (d T : ℕ) : Measure (Samples d T) :=  Measure.pi fun _ => stdGaussian (Vector d)

definition OAI.NoiselessRegression.observationReference line 32

def observationReference (d : ℕ) : Measure (Vector d × ℝ) :=  (stdGaussian (Vector d)).prod volume

structure OAI.NoiselessRegression.Learner line 35

structure Learner (d M T : ℕ) (Ω : Type u) where  initialChoice : Ω → Bool × State M  transition : ℕ → Ω → State M → (Vector d × ℝ) → Bool × State M  output : ℕ → Ω → State M → UnitSphere d

abbreviation OAI.NoiselessRegression.Learner.RunStatus line 42

abbrev RunStatus (M : ℕ) := Sum (State M) (ℕ × State M)

definition OAI.NoiselessRegression.Learner.start line 44

def start {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω) (ω : Ω) :    RunStatus M :=  let a := L.initialChoice ω  if a.1 then .inr (0, a.2) else .inl a.2

definition OAI.NoiselessRegression.Learner.run line 49

def run {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω)    (s : UnitSphere d) (ω : Ω) (x : Samples d T) : ℕ → RunStatus M  | 0 => L.start ω  | n + 1 =>

Show the remaining 8 lines

    match L.run s ω x n with    | .inr done => .inr done    | .inl state =>      if hn : n < T then        let row := x ⟨n, hn⟩        let a := L.transition (n + 1) ω state (row, ⟪row, s.val⟫)        if a.1 then .inr (n + 1, a.2) else .inl a.2      else .inl state

definition OAI.NoiselessRegression.Learner.terminal line 62

def terminal {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω)    (s : UnitSphere d) (ω : Ω) (x : Samples d T) : ℕ × State M :=  match L.run s ω x T with  | .inl state => (T, state)  | .inr done => done

definition OAI.NoiselessRegression.Learner.estimate line 68

def estimate {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω)    (s : UnitSphere d) (ω : Ω) (x : Samples d T) : UnitSphere d :=  let a := L.terminal s ω x  L.output a.1 ω a.2

structure OAI.NoiselessRegression.Learner.Admissible line 73

structure Admissible {d M T : ℕ} {Ω : Type u} [MeasurableSpace Ω]    (L : Learner d M T Ω) (ρ : Measure Ω) : Prop where

Show the remaining 9 lines

  initialChoice : AEMeasurable L.initialChoice ρ  transition : ∀ t a, AEMeasurable (fun z : Ω × (Vector d × ℝ) =>    L.transition t z.1 a z.2) (ρ.prod (observationReference d))  output : ∀ t a, AEMeasurable (fun ω => L.output t ω a) ρ  fixed_experiment : ∀ s, AEMeasurable (fun z : Ω × Samples d T =>    L.estimate s z.1 z.2) (ρ.prod (sampleLaw d T))  uniform_experiment : AEMeasurable    (fun z : UnitSphere d × (Ω × Samples d T) => L.estimate z.1 z.2.1 z.2.2)    ((uniformSphere d).prod (ρ.prod (sampleLaw d T)))

definition OAI.NoiselessRegression.Learner.angularError line 85

def angularError {d : ℕ} (s ŝ : UnitSphere d) : ℝ :=  Real.arccos ⟪ŝ.val, s.val⟫

definition OAI.NoiselessRegression.Learner.uniformSuccess line 88

def uniformSuccess {d M T : ℕ} {Ω : Type u} [MeasurableSpace Ω]    (L : Learner d M T Ω) (ρ : Measure Ω) (ε : ℝ) : ℝ≥0∞ :=  ((uniformSphere d).prod (ρ.prod (sampleLaw d T)))    {z | angularError z.1 (L.estimate z.1 z.2.1 z.2.2) ≤ ε}

definition OAI.NoiselessRegression.sphereLaw line 106

def sphereLaw : Measure (Metric.sphere (0 : E) 1) :=  let σ := (volume : Measure E).toSphere  (σ Set.univ)⁻¹ • σ

definition OAI.NoiselessRegression.ambientSphereLaw line 117

def ambientSphereLaw : Measure E := (sphereLaw (E := E)).map Subtype.val

abbreviation OAI.NoiselessRegression.Learner.TaggedState line 127

abbrev Learner.TaggedState (M T : ℕ) := Sum (State M) (Fin (T+1) × State M)

definition OAI.NoiselessRegression.Learner.taggedStart line 131

def Learner.taggedStart (a : Bool × State M) : TaggedState M T :=  if a.1 then .inr (⟨0,by omega⟩,a.2) else .inl a.2

structure OAI.NoiselessRegression.Learner.MeasurableRules line 142

structure Learner.MeasurableRules (L : Learner d M T Ω) : Prop where  initial : Measurable L.initialChoice  transition : ∀ t j, Measurable (fun z : Ω × (Vector d × ℝ) => L.transition t z.1 j z.2)  output : ∀ t j, Measurable (fun ω => L.output t ω j)

structure OAI.NoiselessRegression.FiniteKernelLearner line 153

structure FiniteKernelLearner (d M T : ℕ) where  initial : Measure (Bool × State M)  initial_probability : IsProbabilityMeasure initial  transition : ℕ → State M → (Vector d × ℝ) → Measure (Bool × State M)  transition_probability : ∀ t j obs, IsProbabilityMeasure (transition t j obs)  output : ℕ → State M → Measure (UnitSphere d)  output_probability : ∀ t j, IsProbabilityMeasure (output t j)

structure OAI.NoiselessRegression.FiniteKernelLearner.CompletedRules line 165

structure CompletedRules (K : FiniteKernelLearner d M T) : Prop where  transition : ∀ t j a, AEMeasurable (fun obs => K.transition t j obs {a}) (observationReference d)

definition OAI.NoiselessRegression.kernelRun line 177

def kernelRun (P : ℕ → J → O → Measure J) : (n : ℕ) → J → (Fin n → O) → Measure J  | 0, j, _ => Measure.dirac j  | n+1, j, obs => (kernelRun P n j (Fin.init obs)).bind (fun a => P (n+1) a (obs (Fin.last n)))

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

No confident match with a paper statement

No paper theorem is paired with this Lean statement.

Why none: no paper statement matches the Lean text clearly enough to pair, so the closest candidates are listed below.

Statements in Projection moments, positive cap domination, and Riesz estimates on the sphere come first because the release’s name for this Lean statement shares words with that paper’s title.

Other possible paper matches, closest wording first

Theorem 3.5 of Projection moments, positive cap domination, and Riesz estimates on the sphere. Words of the Lean statement, its names split into words, that also appear in the theorem: normalized, frame, continuous, d/16, mass, unit and 13 more.
Theorem 3.3 of Projection moments, positive cap domination, and Riesz estimates on the sphere. Words of the Lean statement, its names split into words, that also appear in the theorem: integrated, sqrt, orthonormal, continuous, mass, moment and nine more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: projection.
Proposition 7.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: last, error, restrictions, started, initial, output and 20 more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: information.
Proposition 4.1 of Projection moments, positive cap domination, and Riesz estimates on the sphere. Words of the Lean statement, its names split into words, that also appear in the theorem: parent, domination, cap, exp, positive, kernels and four more.
Proposition 4.4 of Projection moments, positive cap domination, and Riesz estimates on the sphere. Words of the Lean statement, its names split into words, that also appear in the theorem: stopping, inner, observation, restrictions, exp, arccos and six more. Shared only with the release’s name for the Lean statement or OpenAI’s note on it: information.

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

three independent groups report that Comparator accepted runs for this Lean statement file: Carlos Toledo’s cert-machine; MathVet; Neal McBurnett’s openai-math-lean-tooling. 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

Neal McBurnett’s openai-math-lean-tooling

How they ran it, in their words

Each challenge’s solution is built and checked by Comparator at the pinned release, on Lean leanprover/lean4:v4.34.1, recording the verdict, the check time and the peak memory; the run was still in progress at this snapshot (192 accepted, 224 pending).

Accepted Their term: “accepted”.
Re-run through Comparator with Lean’s kernel: accepted (the check took 202 s; peak memory 6.5 GiB).
Reported 11 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

“The paper uses projection moments and domination by positive spherical caps to bound the information carried by exact Gaussian observations of an unknown unit vector. The formalization covers integrated frame and sphere moments, cap domination, Riesz-density estimates with fixed offsets, and bounds valid at every radius. It also covers probability bounds for finite-memory learners at a fixed stopping time and after summing over stopping times.”
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

714 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: 266 to its own declarations, 414 to Mathlib’s documentation. 91 declared names also link to the same declaration in OpenAI’s library. 2 identifiers stay plain because they resolve to no single declaration: variables Lean binds automatically, notation, or names the scan of the pinned sources did not find. OpenAI uses Mathlib version d13f23b. The linked documentation describes the current version, so names that have since changed may be missing there.

import Mathlibnamespace OAInoncomputable sectionopen MeasureTheory ProbabilityTheory Set Filter InnerProductSpaceopen scoped ENNReal NNReal RealInnerProductSpace Topologyuniverse unamespace NoiselessRegressionsectionabbrev 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 volumestructure Learner (d M T : ℕ) (Ω : Type u) where  initialChoice : Ω → Bool × State M  transition : ℕ → Ω → State M → (Vector d × ℝ) → Bool × State M  output : ℕ → Ω → State M → UnitSphere dnamespace Learnerabbrev RunStatus (M : ℕ) := Sum (State M) (ℕ × State M)def start {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω) (ω : Ω) :    RunStatus M :=  let a := L.initialChoice ω  if a.1 then .inr (0, a.2) else .inl a.2def run {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω)    (s : UnitSphere d) (ω : Ω) (x : Samples d T) : ℕ → RunStatus M  | 0 => L.start ω  | n + 1 =>    match L.run s ω x n with    | .inr done => .inr done    | .inl state =>      if hn : n < T then        let row := x ⟨n, hn⟩        let a := L.transition (n + 1) ω state (row, ⟪row, s.val⟫)        if a.1 then .inr (n + 1, a.2) else .inl a.2      else .inl statedef terminal {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω)    (s : UnitSphere d) (ω : Ω) (x : Samples d T) : ℕ × State M :=  match L.run s ω x T with  | .inl state => (T, state)  | .inr done => donedef estimate {d M T : ℕ} {Ω : Type u} (L : Learner d M T Ω)    (s : UnitSphere d) (ω : Ω) (x : Samples d T) : UnitSphere d :=  let a := L.terminal s ω x  L.output a.1 ω a.2structure Admissible {d M T : ℕ} {Ω : Type u} [MeasurableSpace Ω]    (L : Learner d M T Ω) (ρ : Measure Ω) : Prop where  initialChoice : AEMeasurable L.initialChoice ρ  transition : ∀ t a, AEMeasurable (fun z : Ω × (Vector d × ℝ) =>    L.transition t z.1 a z.2) (ρ.prod (observationReference d))  output : ∀ t a, AEMeasurable (fun ω => L.output t ω a) ρ  fixed_experiment : ∀ s, AEMeasurable (fun z : Ω × Samples d T =>    L.estimate s z.1 z.2) (ρ.prod (sampleLaw d T))  uniform_experiment : AEMeasurable    (fun z : UnitSphere d × (Ω × Samples d T) => L.estimate z.1 z.2.1 z.2.2)    ((uniformSphere d).prod (ρ.prod (sampleLaw d T)))def angularError {d : ℕ} (s ŝ : UnitSphere d) : ℝ :=  Real.arccos ⟪ŝ.val, s.val⟫def uniformSuccess {d M T : ℕ} {Ω : Type u} [MeasurableSpace Ω]    (L : Learner d M T Ω) (ρ : Measure Ω) (ε : ℝ) : ℝ≥0∞ :=  ((uniformSphere d).prod (ρ.prod (sampleLaw d T)))    {z | angularError z.1 (L.estimate z.1 z.2.1 z.2.2) ≤ ε}end Learneropen scoped Topologyopen InnerProductSpacesection SphereBoundsopen scoped Pointwisevariable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]def sphereLaw : Measure (Metric.sphere (0 : E) 1) :=  let σ := (volume : Measure E).toSphere  (σ Set.univ)⁻¹ • σend SphereBoundsopen scoped Pointwisevariable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]def ambientSphereLaw : Measure E := (sphereLaw (E := E)).map Subtype.valendsectionsectionvariable {d M T : ℕ} {Ω : Type u}abbrev Learner.TaggedState (M T : ℕ) := Sum (State M) (Fin (T+1) × State M)instance Learner.taggedMeasurableSpace : MeasurableSpace (TaggedState M T) := ⊤def Learner.taggedStart (a : Bool × State M) : TaggedState M T :=  if a.1 then .inr (⟨0,by omega⟩,a.2) else .inl a.2endopen MeasureTheory ProbabilityTheory Set Filteropen scoped ENNReal NNReal RealInnerProductSpacevariable {d M T : ℕ} {Ω : Type u} [MeasurableSpace Ω]structure Learner.MeasurableRules (L : Learner d M T Ω) : Prop where  initial : Measurable L.initialChoice  transition : ∀ t j, Measurable (fun z : Ω × (Vector d × ℝ) => L.transition t z.1 j z.2)  output : ∀ t j, Measurable (fun ω => L.output t ω j)endopen MeasureTheory ProbabilityTheory Set Filteropen scoped ENNReal NNReal RealInnerProductSpacestructure FiniteKernelLearner (d M T : ℕ) where  initial : Measure (Bool × State M)  initial_probability : IsProbabilityMeasure initial  transition : ℕ → State M → (Vector d × ℝ) → Measure (Bool × State M)  transition_probability : ∀ t j obs, IsProbabilityMeasure (transition t j obs)  output : ℕ → State M → Measure (UnitSphere d)  output_probability : ∀ t j, IsProbabilityMeasure (output t j)namespace FiniteKernelLearnervariable {d M T : ℕ}structure CompletedRules (K : FiniteKernelLearner d M T) : Prop where  transition : ∀ t j a, AEMeasurable (fun obs => K.transition t j obs {a}) (observationReference d)end FiniteKernelLearneropen MeasureTheory ProbabilityTheory Set Filter unitIntervalsection CoinRunvariable {J O : Type*} [Fintype J] [MeasurableSpace J] [MeasurableSingletonClass J]  [MeasurableSpace O]def kernelRun (P : ℕ → J → O → Measure J) : (n : ℕ) → J → (Fin n → O) → Measure J  | 0, j, _ => Measure.dirac j  | n+1, j, obs => (kernelRun P n j (Fin.init obs)).bind (fun a => P (n+1) a (obs (Fin.last n)))end CoinRunsectionsectionopen Learnervariable {d M T : ℕ}abbrev FiniteKernelLearner.Tape (M T : ℕ) := (Bool × State M) × ((Fin T → I) × I)def FiniteKernelLearner.destination (t : ℕ) (h : t ≤ T) (a : Bool × State M) : TaggedState M T :=  if a.1 then .inr (⟨t,by omega⟩,a.2) else .inl a.2def FiniteKernelLearner.taggedKernel (K : FiniteKernelLearner d M T) (t : ℕ) :    TaggedState M T → (Vector d × ℝ) → Measure (TaggedState M T)  | .inr a, _ => Measure.dirac (.inr a)  | .inl j, obs => if ht : t ≤ T then (K.transition t j obs).map (destination t ht)    else Measure.dirac (.inl j)def FiniteKernelLearner.terminalOutput (K : FiniteKernelLearner d M T) : TaggedState M T → Measure (UnitSphere d)  | .inl j => K.output T j  | .inr (t,j) => K.output t jendopen MeasureTheory ProbabilityTheory Set Filter unitIntervalopen scoped ENNReal NNReal RealInnerProductSpaceopen Learnervariable {d M T : ℕ}abbrev FiniteKernelLearner.Result (d M : ℕ) := (ℕ × State M) × UnitSphere ddef FiniteKernelLearner.terminalTag : TaggedState M T → ℕ × State M  | .inl j => (T,j)  | .inr (t,j) => (t,j)def FiniteKernelLearner.terminalJointOutput (K : FiniteKernelLearner d M T) (j : TaggedState M T) : Measure (Result d M) :=  (K.terminalOutput j).map (fun y => (terminalTag j,y))def FiniteKernelLearner.jointExperimentLaw (K : FiniteKernelLearner d M T) (obs : Fin T → (Vector d × ℝ)) : Measure (Result d M) :=  K.initial.bind (fun a => (kernelRun K.taggedKernel T (taggedStart a) obs).bind K.terminalJointOutput)def FiniteKernelLearner.uniformSuccess (K : FiniteKernelLearner d M T) (ε : ℝ) : ℝ≥0∞ :=  ∫⁻ z : UnitSphere d × Samples d T,    K.jointExperimentLaw (fun i => (z.2 i,⟪z.1.val,z.2 i⟫))      {r | angularError z.1 r.2 ≤ ε} ∂((uniformSphere d).prod (sampleLaw d T))def FiniteKernelLearner.uniformFixedSuccess (K : FiniteKernelLearner d M T) (ε : ℝ) (t : ℕ) : ℝ≥0∞ :=  ∫⁻ z : UnitSphere d × Samples d T,    K.jointExperimentLaw (fun i => (z.2 i,⟪z.1.val,z.2 i⟫))      {r | r.1.1 = t ∧ angularError z.1 r.2 ≤ ε} ∂((uniformSphere d).prod (sampleLaw d T))endsectionopen MeasureTheory ProbabilityTheory Set Filteropen scoped ENNReal NNReal RealInnerProductSpacevariable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E] [Nontrivial E]variable {d M T : ℕ} {Ω : Type u}def Learner.uniformFixedSuccess [MeasurableSpace Ω] (L : Learner d M T Ω) (ρ : Measure Ω)    (ε : ℝ) (t : ℕ) : ℝ≥0∞ :=  ((uniformSphere d).prod (ρ.prod (sampleLaw d T)))    {z | (L.terminal z.1 z.2.1 z.2.2).1 = t ∧ angularError z.1 (L.estimate z.1 z.2.1 z.2.2) ≤ ε}endsectionvariable {d M T : ℕ}def FiniteKernelLearner.seededSuccess {Ξ : Type u} [MeasurableSpace Ξ]    (K : Ξ → FiniteKernelLearner d M T) (ρ : Measure Ξ) (ε : ℝ) : ℝ≥0∞ :=  ∫⁻ ξ, (K ξ).uniformSuccess ε ∂ρdef FiniteKernelLearner.seededFixedSuccess {Ξ : Type u} [MeasurableSpace Ξ]    (K : Ξ → FiniteKernelLearner d M T) (ρ : Measure Ξ) (ε : ℝ) (t : ℕ) : ℝ≥0∞ :=  ∫⁻ ξ, (K ξ).uniformFixedSuccess ε t ∂ρdef FiniteKernelLearner.FixedQuadraticMemory : Prop :=  ∀ A₀ : ℝ, 0 < A₀ → ∃ c : ℝ, 0 < c ∧ ∃ d₀ : ℕ,    ∀ d : ℕ, d₀ ≤ d → ∀ M T : ℕ, (M : ℝ) ≤ A₀ * (d : ℝ)^2 →    ∀ ε : ℝ, 0 < ε → ε ≤ 1/10 →    ∀ (Ξ : Type u) [MeasurableSpace Ξ] (ρ : Measure Ξ), IsProbabilityMeasure ρ →    ∀ K : Ξ → FiniteKernelLearner d M T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →    (2/3 : ℝ≥0∞) ≤ seededSuccess K ρ ε →    c*(d:ℝ)*Real.log (1/ε) ≤ (T:ℝ)endopen MeasureTheory ProbabilityTheory Set Filteropen scoped ENNReal NNReal RealInnerProductSpacevariable {d M T : ℕ} {Ξ : Type u} [MeasurableSpace Ξ]def FiniteKernelLearner.conditionalSuccess (K : FiniteKernelLearner d M T) (ε : ℝ)    (s : UnitSphere d) (x : Samples d T) : ℝ≥0∞ :=  K.jointExperimentLaw (fun i => (x i,⟪s.val,x i⟫)) {r | Learner.angularError s r.2 ≤ ε}def FiniteKernelLearner.seededPointwiseSuccess (K : Ξ → FiniteKernelLearner d M T) (ρ : Measure Ξ)    (ε : ℝ) (s : UnitSphere d) : ℝ≥0∞ :=  ∫⁻ z : Ξ × Samples d T, (K z.1).conditionalSuccess ε s z.2 ∂ρ.prod (sampleLaw d T)def FiniteKernelLearner.JointSuccessMeasurable (K : Ξ → FiniteKernelLearner d M T) (ρ : Measure Ξ) (ε : ℝ) : Prop :=  AEMeasurable (fun z : UnitSphere d × (Ξ × Samples d T) =>    (K z.2.1).conditionalSuccess ε z.1 z.2.2)    ((uniformSphere d).prod (ρ.prod (sampleLaw d T)))def FiniteKernelLearner.SubquadraticMemoryWithPointwise : 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 ρ →    ∀ K : Ξ → FiniteKernelLearner d (M d) T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →    ((2/3 : ℝ≥0∞) ≤ seededSuccess K ρ ε ∨      (JointSuccessMeasurable K ρ ε ∧ ∀ s, (2/3 : ℝ≥0∞) ≤ seededPointwiseSuccess K ρ ε s)) →    c*(d:ℝ)*Real.log (1/ε) ≤ (T:ℝ)end NoiselessRegressionnamespace ProjectionMomentsopen NoiselessRegression NoiselessRegression.FiniteKernelLearnersectionsection GaussianGraphvariable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]def vectorSmoothing (ν : Measure E) (m : ℕ) (φ : (Fin m → ℝ) → ℝ≥0∞)    (z : (Fin m → E) × (Fin m → ℝ)) : ℝ≥0∞ :=  ∫⁻ t, φ (fun j => z.2 j - ⟪t, z.1 j⟫) ∂νabbrev Label (m : ℕ) := EuclideanSpace ℝ (Fin m)def ballKernel (m : ℕ) (η : ℝ) (y : Fin m → ℝ) : ℝ≥0∞ :=  (Metric.closedBall (0 : Label m) η).indicator    (fun _ => (volume (Metric.closedBall (0 : Label m) η))⁻¹) (WithLp.toLp 2 y)def rowMap {m : ℕ} (A : Fin m → E) : E →L[ℝ] Label m :=  (PiLp.continuousLinearEquiv 2 ℝ (fun _ : Fin m => ℝ)).symm.toContinuousLinearMap.comp    (ContinuousLinearMap.pi (fun j => innerSL ℝ (A j)))def ballAverage (ν : Measure E) (m : ℕ) (η : ℝ)    (z : (Fin m → E) × Label m) : ℝ≥0∞ :=  vectorSmoothing ν m (ballKernel m η) (z.1, WithLp.ofLp z.2)def lowerDensity (ν : Measure E) (m : ℕ) (z : (Fin m → E) × Label m) : ℝ≥0∞ :=  liminf (fun n : ℕ => ballAverage ν m ((n : ℝ) + 1)⁻¹ z) atTopdef AllBallMass (ν : Measure E) (K a : ℝ) : Prop :=  ∀ b : E, ∀ t : ℝ, 0 < t → ν (Metric.closedBall b t) ≤ ENNReal.ofReal (K * t ^ a)end GaussianGraphopen MeasureTheory ProbabilityTheory Set Filter InnerProductSpaceopen scoped ENNReal NNReal RealInnerProductSpace Topologysection Rotationsvariable (E : Type*) [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E]abbrev Rotation := unitary (E →L[ℝ] E)instance rotationMeasurableSpace : MeasurableSpace (Rotation E) := borel (Rotation E)instance rotationBorelSpace : BorelSpace (Rotation E) := ⟨rfl⟩instance rotationCompact : CompactSpace (Rotation E) := by  apply isCompact_iff_compactSpace.mp  apply Metric.isCompact_of_isClosed_isBounded isClosed_unitary  apply (Metric.isBounded_closedBall (x := (0 : E →L[ℝ] E)) (r := 1)).subset (s := (unitary (E →L[ℝ] E) : Set (E →L[ℝ] E)))  intro U hU  rw [Metric.mem_closedBall, dist_zero_right]  by_cases h : Subsingleton E  · have := h    simp  · have : Nontrivial E := not_subsingleton_iff_nontrivial.mp h    exact (CStarRing.norm_of_mem_unitary hU).ledef rotationLaw : Measure (Rotation E) :=  ((Measure.haar : Measure (Rotation E)) Set.univ)⁻¹ • Measure.haarvariable {E}variable [MeasurableSpace E] [BorelSpace E]def rotateRows {ι : Type*} (O : Rotation E) (v : ι → E) : ι → E :=  fun i => (O : E →L[ℝ] E) (v i)end Rotationssection Triangularvariable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E]  [MeasurableSpace E] [BorelSpace E]def coordinateMap {m : ℕ} (A : Fin m → E) : E →ₗ[ℝ] (Fin m → ℝ) :=  (WithLp.linearEquiv 2 ℝ (Fin m → ℝ)) ∘ₗ (rowMap A).toLinearMapdef coordinateDensity (ν : Measure E) (m : ℕ) (z : (Fin m → E) × (Fin m → ℝ)) : ℝ≥0∞ :=  lowerDensity ν m (z.1, WithLp.toLp 2 z.2)def frameLaw {m : ℕ} (u : Fin m → E) : Measure (Fin m → E) :=  (rotationLaw E).map (fun O => rotateRows O u)open MeasureTheory ProbabilityTheory Set Filter InnerProductSpaceopen scoped ENNReal NNReal RealInnerProductSpace Topologydef rieszKernel (α : ℝ) (z s : E) : ℝ≥0∞ := (ENNReal.ofReal ‖s-z‖)^(-α)def rieszPotential (α : ℝ) (h : E → ℝ≥0∞) : ℝ≥0∞ :=  ⨆ z : E, ∫⁻ s, h s*rieszKernel α z s ∂NoiselessRegression.ambientSphereLawopen MeasureTheory ProbabilityTheory Set Filter InnerProductSpace Matrixopen scoped ENNReal NNReal RealInnerProductSpace Topology MatrixOrder Matrix.Norms.L2Operatordef mixRows {k : ℕ} (M : Matrix (Fin k) (Fin k) ℝ) (X : Fin k → E) : Fin k → E :=  fun i => ∑ j, M i j • X jdef polarRadial {k : ℕ} (X : Fin k → E) : Matrix (Fin k) (Fin k) ℝ :=  CFC.sqrt (Matrix.gram ℝ X)def rawPolarRows {k : ℕ} (X : Fin k → E) : Fin k → E :=  mixRows (polarRadial X)⁻¹ Xdef polarRows {k : ℕ} (u X : Fin k → E) : Fin k → E := by  classical  exact if LinearIndependent ℝ X then rawPolarRows X else uopen MeasureTheory ProbabilityTheory Set Filter InnerProductSpaceopen scoped ENNReal NNReal RealInnerProductSpace Topologydef unitBallVolume (k : ℕ) : ℝ≥0∞ := (volume : Measure (Label k)) (Metric.closedBall 0 1)def unitBallLaw (k : ℕ) : Measure (Label k) :=  (unitBallVolume k)⁻¹ • volume.restrict (Metric.closedBall 0 1)def normalizedDensity (ν : Measure E) (k : ℕ) (u : Fin k → E)    (z : (Fin k → E) × Label k) : ℝ≥0∞ :=  unitBallVolume k * lowerDensity ν k (polarRows u z.1,z.2)open MeasureTheory ProbabilityTheory Set Filter InnerProductSpaceopen scoped ENNReal NNReal RealInnerProductSpace Topologydef sphereWeightedRestriction (h : E → ℝ≥0∞) (H : Set E) : Measure E :=  (NoiselessRegression.ambientSphereLaw.withDensity h).restrict Hend Triangularsectionopen MeasureTheory ProbabilityTheory Set Filter InnerProductSpaceopen scoped ENNReal NNReal RealInnerProductSpace Topologyvariable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]def capMeasure (c : E) (r : ℝ) : Measure E :=  (NoiselessRegression.ambientSphereLaw (Metric.closedBall c r))⁻¹ •    NoiselessRegression.ambientSphereLaw.restrict (Metric.closedBall c r)structure CapDictionary (c : E) (r α : ℝ) where  I : Type u  countable : Countable I  center : I → E  radius : I → ℝ  center_norm : ∀ i, ‖center i‖ = 1  radius_pos : ∀ i, 0 < radius i  radius_le : ∀ i, radius i ≤ r  parent : I  parent_center : center parent = c  parent_radius : radius parent = r  proper : ∀ R : ℝ, {i | (r/radius i)^α ≤ R}.Finite  cover : ∀ (s : E), ‖s‖ = 1 → ∀ t : ℝ, 0 < t → t ≤ 1/4 →    ∃ i, 4*r*t ≤ radius i ∧ radius i < 8*r*t ∧ dist s (center i) ≤ radius i/2endsectionopen MeasureTheory ProbabilityTheory Set Filter InnerProductSpace Matrixopen scoped ENNReal NNReal RealInnerProductSpace Topologyvariable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]def radialLabel {k : ℕ} (X : Fin k → E) (y : Label k) : Label k :=  WithLp.toLp 2 (polarRadial X *ᵥ y.ofLp)def capKernelValue {k : ℕ} (K : (Fin k → E) × Label k → ℝ≥0∞) (s : E) : ℝ≥0∞ :=  ∫⁻ X, K (X,rowMap X s) ∂Measure.pi (fun _ => stdGaussian E)def capReferenceLabel {k : ℕ} (c : E) (r : ℝ) (X : Fin k → E) (z : Label k) : Label k :=  rowMap X c + r • radialLabel X zdef capReference {k : ℕ} (K : (Fin k → E) × Label k → ℝ≥0∞) (c : E) (r : ℝ) : ℝ≥0∞ :=  ∫⁻ X, ∫⁻ z, K (X,capReferenceLabel c r X z) ∂unitBallLaw k ∂Measure.pi (fun _ => stdGaussian E)endvariable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]  [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]def fractionalBlock {J : Type*} [Fintype J] {k : ℕ}    (Q : J → (Fin k → E) × Label k → ℝ≥0∞) (f : J → E → ℝ≥0∞) (s : E) : ℝ≥0∞ :=  ∫⁻ X, ∑ j, Q j (X,rowMap X s)*f j s ∂Measure.pi (fun _ => stdGaussian E)enddef IntegratedFrameMoment : Prop :=    ∃ C : ℝ, 1 ≤ C ∧ ∀ (d k q : ℕ) (β K R : ℝ)      (ν : Measure (EuclideanSpace ℝ (Fin d))) [IsFiniteMeasure ν]      (z : EuclideanSpace ℝ (Fin d)) (u : Fin k → EuclideanSpace ℝ (Fin d)),      1 ≤ k → 2 ≤ q → k+q ≤ d → 0 < β → β ≤ d →      1 ≤ β-k-((q:ℝ)-2) → 0 ≤ K → 0 < R →      ν.support ⊆ Metric.closedBall z R → AllBallMass ν K β →      Orthonormal ℝ u →      (∀ᵐ A ∂frameLaw u, ν.map (coordinateMap A) ≪ (volume : Measure (Fin k → ℝ))) →      Measurable (coordinateDensity ν k) ∧      (∀ᵐ A ∂frameLaw u,        (volume : Measure (Fin k → ℝ)).withDensity (fun y => coordinateDensity ν k (A,y)) =          ν.map (coordinateMap A)) ∧      (∀ (A : Fin k → EuclideanSpace ℝ (Fin d)), Orthonormal ℝ A →        ∀ y : Fin k → ℝ,          R < ‖WithLp.toLp 2 (y-coordinateMap A z)‖ → coordinateDensity ν k (A,y) = 0) ∧      (∫⁻ A, ∫⁻ y : Fin k → ℝ, coordinateDensity ν k (A,y)^q ∂volume ∂frameLaw u) ^ (1/(q:ℝ)) ≤        ENNReal.ofReal (C^d * (C*Real.sqrt d)^((k:ℝ)*(1-1/(q:ℝ))) *          K * R^(β-(k:ℝ)*(1-1/(q:ℝ))))def NormalizedUnitBallMoment : Prop :=  ∀ D : ℝ, 0 < D →    ∃ C_D : ℝ, 0 < C_D ∧ ∀ d : ℕ, 32 ≤ d →      let k := d/16      let lam : ℝ := ((d:ℝ)-1)/2      ∀ (ν : Measure (EuclideanSpace ℝ (Fin d))) [IsFiniteMeasure ν]        (u : Fin k → EuclideanSpace ℝ (Fin d)),        ν Set.univ ≤ 1 → ν.support ⊆ Metric.closedBall 0 1 →        AllBallMass ν (D^d) lam → Orthonormal ℝ u →        (∀ᵐ X ∂Measure.pi (fun _ : Fin k => stdGaussian (EuclideanSpace ℝ (Fin d))),          ν.map (rowMap (polarRows u X)) ≪ (volume : Measure (Label k))) →        Measurable (normalizedDensity ν k u) ∧        (∀ᵐ X ∂Measure.pi (fun _ : Fin k => stdGaussian (EuclideanSpace ℝ (Fin d))),          ((unitBallVolume k)⁻¹ • (volume : Measure (Label k))).withDensity            (fun y => normalizedDensity ν k u (X,y)) = ν.map (rowMap (polarRows u X))) ∧        (∀ X y, 1 < ‖y‖ → normalizedDensity ν k u (X,y) = 0) ∧        (∫⁻ X, ∫⁻ y, normalizedDensity ν k u (X,y)^k ∂unitBallLaw k          ∂Measure.pi (fun _ => stdGaussian (EuclideanSpace ℝ (Fin d)))) ≤          ENNReal.ofReal (Real.exp (C_D*d*k))def AllRadiiSphereMoment : Prop :=    ∃ C : ℝ, 1 ≤ C ∧ ∀ d : ℕ, 16 ≤ d →      let k := d/4      let β : ℝ := (d:ℝ)-1-k      ∀ f : EuclideanSpace ℝ (Fin d) → ℝ≥0∞,      Measurable f → (∀ s, f s ≤ 1) →      ∀ K : ℝ, 0 ≤ K →      AllBallMass (NoiselessRegression.ambientSphereLaw.withDensity f) K β →      ∀ z : EuclideanSpace ℝ (Fin d), ∀ R : ℝ, 0 < R →      ∀ u : Fin k → EuclideanSpace ℝ (Fin d), Orthonormal ℝ u →      let μ := sphereWeightedRestriction f (Metric.closedBall z R)      Measurable (coordinateDensity μ k) ∧      (∀ A : Fin k → EuclideanSpace ℝ (Fin d), Orthonormal ℝ A →        (volume : Measure (Fin k → ℝ)).withDensity (fun y => coordinateDensity μ k (A,y)) =          μ.map (coordinateMap A)) ∧      (∀ A : Fin k → EuclideanSpace ℝ (Fin d), Orthonormal ℝ A →        ∀ y : Fin k → ℝ, R < ‖WithLp.toLp 2 (y-coordinateMap A z)‖ →          coordinateDensity μ k (A,y) = 0) ∧      (∫⁻ A, ∫⁻ y : Fin k → ℝ, coordinateDensity μ k (A,y)^k ∂volume ∂frameLaw u) ^ (1/(k:ℝ)) ≤        ENNReal.ofReal (C^d*(C*Real.sqrt d)^((k:ℝ)*(1-1/(k:ℝ)))*          K*R^(β-(k:ℝ)*(1-1/(k:ℝ))))def PositiveCapDomination : Prop :=    ∃ C : ℝ, 0 < C ∧ ∀ d : ℕ, 32 ≤ d →      let k := d/16      let α : ℝ := ((d:ℝ)-1)/2      ∀ (c : EuclideanSpace ℝ (Fin d)), ‖c‖ = 1 →      ∀ r : ℝ, 0 < r → r ≤ 2 → ∀ N : ℕ,      ∀ K : Fin N → (Fin k → EuclideanSpace ℝ (Fin d)) × Label k → ℝ≥0∞,      (∀ j, Measurable (K j)) → (∀ z, ∑ j, K j z ≤ 1) →      (∑ j, capReference (K j) c r) ≤ 1 ∧      ∀ j, ∃ D : CapDictionary c r α, ∃ a : D.I → ℝ,        (∀ i, 0 ≤ a i) ∧ Summable (fun i => a i*(r/D.radius i)^α) ∧        (∑' i, a i*(r/D.radius i)^α) ≤ Real.exp (C*d)*(capReference (K j) c r).toReal^(1-1/(k:ℝ)) ∧        (capMeasure c r).withDensity (capKernelValue (K j)) ≤          Measure.sum (fun i => ENNReal.ofReal (a i) • capMeasure (D.center i) (D.radius i)) ∧        (Measure.sum (fun i => ENNReal.ofReal (a i) • capMeasure (D.center i) (D.radius i))) Set.univ < ∞def DeterministicOffsetDensity : Prop :=    ∃ C : ℝ, 1 ≤ C ∧ ∀ d : ℕ, 16 ≤ d →      let k := d/8      let α : ℝ := (d:ℝ)/2      ∀ h : EuclideanSpace ℝ (Fin d) → ℝ≥0∞, Measurable h → (∀ s, h s ≤ 1) →      ∀ z : EuclideanSpace ℝ (Fin d), ∀ ρ : ℝ, 0 < ρ →      ∀ H : Set (EuclideanSpace ℝ (Fin d)), MeasurableSet H → H ⊆ Metric.closedBall z ρ →      rieszPotential α h < ∞ ∧      Measurable (lowerDensity (sphereWeightedRestriction h H) k) ∧      (∀ A : Fin k → EuclideanSpace ℝ (Fin d), LinearIndependent ℝ A →        volume.withDensity (fun y => lowerDensity (sphereWeightedRestriction h H) k (A,y)) =          (sphereWeightedRestriction h H).map (rowMap A)) ∧      (∀ b : Label k, (∫⁻ A, (lowerDensity (sphereWeightedRestriction h H) k (A,rowMap A z+b))^k          ∂Measure.pi (fun _ => stdGaussian (EuclideanSpace ℝ (Fin d))))^(1/(k:ℝ)) ≤        ENNReal.ofReal (C^d) * rieszPotential α h * ENNReal.ofReal (ρ^(α-k))) ∧      (∀ A y, ‖rowMap A‖*ρ < ‖y-rowMap A z‖ →        lowerDensity (sphereWeightedRestriction h H) k (A,y) = 0)def AllRadiiBlockBound : Prop :=    ∃ C : ℝ, 1 ≤ C ∧ ∀ d : ℕ, 16 ≤ d →      let k := d/4      let β : ℝ := (d:ℝ)-1-k      ∀ N : ℕ, ∀ f : Fin N → EuclideanSpace ℝ (Fin d) → ℝ≥0∞,      (∀ j, Measurable (f j)) → (∀ j s, f j s ≤ 1) →      ∀ K : ℝ, 0 ≤ K →      (∀ j, AllBallMass (NoiselessRegression.ambientSphereLaw.withDensity (f j)) K β) →      ∀ Q : Fin N → (Fin k → EuclideanSpace ℝ (Fin d)) × Label k → ℝ≥0∞,      (∀ j, Measurable (Q j)) → (∀ z, ∑ j, Q j z ≤ 1) →      AllBallMass (NoiselessRegression.ambientSphereLaw.withDensity (fractionalBlock Q f))        (C^d*(N:ℝ)^(1/(k:ℝ))*K) βdef HaarStreamingCost : Prop :=    ∃ C : ℝ, 1 ≤ C ∧ ∀ d M T : ℕ, 16 ≤ d → ∀ ε : ℝ,      0 < ε → ε ≤ 1/10 →      ∀ (Ξ : Type u) [MeasurableSpace Ξ] (ρ : Measure Ξ), IsProbabilityMeasure ρ →      ∀ K : Ξ → FiniteKernelLearner d M T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →      let k := d/4      let Nstar : ℝ := ((k:ℝ)+2)*2^M      seededSuccess K ρ ε ≤ ENNReal.ofReal        (C^d*ε^k*(C^d*Nstar^(1/(k:ℝ)))^((T+k-1)/k))def RieszStreamingCost : Prop :=    ∃ C₀ : ℝ, 1 ≤ C₀ ∧ ∀ d M T : ℕ, 16 ≤ d → ∀ ε : ℝ,      0 < ε → ε ≤ 1/10 →      ∀ (Ξ : Type u) [MeasurableSpace Ξ] (ρ : Measure Ξ), IsProbabilityMeasure ρ →      ∀ K : Ξ → FiniteKernelLearner d M T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →      let q := d/8      let W : ℝ := ((T:ℝ)+2)*2^M      seededSuccess K ρ ε ≤ ENNReal.ofReal        (C₀^d*ε^((d:ℝ)/2-1)*(1+C₀^d*(1+Real.log (1/ε))*W^(1/(q:ℝ)))^((T+q-1)/q))def CapFixedStoppingCost : Prop :=    ∃ C : ℝ, 0 < C ∧ ∀ d M T : ℕ, 32 ≤ d → ∀ ε : ℝ,      0 < ε → ε ≤ 1/10 →      ∀ (Ξ : Type u) [MeasurableSpace Ξ] (ρ : Measure Ξ), IsProbabilityMeasure ρ →      ∀ K : Ξ → FiniteKernelLearner d M T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →      ∀ t : ℕ, t ≤ T →      let k := d/16      let α : ℝ := ((d:ℝ)-1)/2      seededFixedSuccess K ρ ε t ≤ ENNReal.ofReal        (Real.exp (C*d)*(ε/2)^α*(Real.exp (C*d)*(2:ℝ)^((M:ℝ)/k))^((t+k-1)/k))def CapTotalStoppingCost : Prop :=    ∃ C : ℝ, 0 < C ∧ ∀ d M T : ℕ, 32 ≤ d → ∀ ε : ℝ,      0 < ε → ε ≤ 1/10 →      ∀ (Ξ : Type u) [MeasurableSpace Ξ] (ρ : Measure Ξ), IsProbabilityMeasure ρ →      ∀ K : Ξ → FiniteKernelLearner d M T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →      let k := d/16      let α : ℝ := ((d:ℝ)-1)/2      seededSuccess K ρ ε ≤ ENNReal.ofReal        (((T:ℝ)+1)*Real.exp (C*d)*(ε/2)^α*          (Real.exp (C*d)*(2:ℝ)^((M:ℝ)/k))^((T+k-1)/k))def CapFixedStoppingAsymptotic : 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 ρ →      ∀ K : Ξ → FiniteKernelLearner d (M d) T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →      ∀ t : ℕ, t ≤ T →      let k := d/16      let α : ℝ := ((d:ℝ)-1)/2      seededFixedSuccess K ρ ε t ≤ ENNReal.ofReal        (Real.exp (C*d*(1+((t+k-1)/k:ℕ)))*(ε/2)^α)def CapTotalStoppingAsymptotic : Prop :=    ∃ C₁ C₂ : ℝ, 0 < 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 ρ →      ∀ K : Ξ → FiniteKernelLearner d (M d) T, (∀ᵐ ξ ∂ρ, (K ξ).CompletedRules) →      seededSuccess K ρ ε ≤ ENNReal.ofReal        (((T:ℝ)+1)*Real.exp (C₁*d+C₂*T-(d:ℝ)*Real.log (1/ε)/3))def KernelModelBridge : Prop :=  ∀ d M T : ℕ, 3 ≤ d → ∀ K : FiniteKernelLearner d M T, K.CompletedRules →    ∃ (ρ : Measure (Tape M T)) (L : Learner d M T (Tape M T)),      IsProbabilityMeasure ρ ∧ L.MeasurableRules ∧ L.Admissible ρ ∧      (∀ ε, L.uniformSuccess ρ ε = K.uniformSuccess ε) ∧      (∀ ε t, L.uniformFixedSuccess ρ ε t = K.uniformFixedSuccess ε t)def MainStatement : Prop :=  IntegratedFrameMoment ∧ NormalizedUnitBallMoment ∧ AllRadiiSphereMoment ∧  PositiveCapDomination ∧ DeterministicOffsetDensity ∧ AllRadiiBlockBound ∧  HaarStreamingCost.{u} ∧ RieszStreamingCost.{u} ∧ CapFixedStoppingCost.{u} ∧  CapTotalStoppingCost.{u} ∧ CapFixedStoppingAsymptotic.{u} ∧  CapTotalStoppingAsymptotic.{u} ∧ KernelModelBridge ∧  NoiselessRegression.FiniteKernelLearner.SubquadraticMemoryWithPointwise.{u} ∧  NoiselessRegression.FiniteKernelLearner.FixedQuadraticMemory.{u}open MeasureTheory ProbabilityTheory Set Filter InnerProductSpaceopen scoped ENNReal NNReal RealInnerProductSpace Topologytheorem main : MainStatement.{u} := by  sorryend ProjectionMomentsendend 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/ProjectionMoments.lean
OpenAI’s Lean catalogue: OpenAI lists this as a main result in its Lean catalogue.
Solution module: OAI/Probability/ProjectionMoments/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: 90 local vocabulary declarations
Lines of Lean, without comments or blank lines: 425
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