Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma C.2 — adaptive Gaussian Gram diagonal lower bound

Open
SketchAttr.LOO.Supplement.lemma_C_2

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

gaussian-matricesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity

There are universal constants b,β>0b,\beta>0b,β>0 and an integer L≥1L\ge1L≥1. For every n≥1n\ge1n≥1, draw a matrix G∈RLn×nG\in\mathbb R^{Ln\times n}G∈RLn×n with independent standard real Gaussian entries, independently of a procedure's arbitrary random seed. Any randomized adaptive procedure using a worst-case budget of q≤bnq\le bnq≤bn real matrix-vector queries to G⊤GG^\top GG⊤G satisfies

Pr⁡G,seed ⁣(∑i=1n∣L^i−(G⊤G)ii∣2<βn2)≤14.\Pr_{G,\mathrm{seed}}\!\left(\sum_{i=1}^n|\widehat L_i-(G^\top G)_{ii}|^2<\beta n^2\right)\le\frac14.G,seedPr​(i=1∑n​∣Li​−(G⊤G)ii​∣2<βn2)≤41​.

The procedure sees only its seed and oracle answers, and has unrestricted computation between queries. This is the hard-distribution ingredient for Lemma 5.2.

Differences from the source:

  • encoding: indices in [n] and probabilities over random seeds → indices in Fin n and an arbitrary measurable seed probability space; reason: zero-based labels and explicit probability laws change no instance
  • encoding: at most bn adaptive real matrix-vector queries, with seed independent of G → a q-step measurable transcript with q at most bn and the product of the Gaussian matrix law and seed law; reason: padding permits early stopping and the product law states independence explicitly
Preamble
import Mathlib
import Definitions.Def_SketchAttr_LOO_Supplement_Quadratic

open MeasureTheory
open scoped ENNReal
Formal statement
namespace SketchAttr.LOO.Supplement

theorem lemma_C_2 :
    ∃ b β : ℝ, 0 < b ∧ 0 < β ∧ ∃ L : ℕ, 1 ≤ L ∧
      ∀ (n : ℕ), 1 ≤ n → ∀ (Seed : Type) [MeasurableSpace Seed]
        (μ : Measure Seed) [IsProbabilityMeasure μ] (q : ℕ)
        (P : MatrixProcedure Seed n q), (q : ℝ) ≤ b * n →
      ((realGaussianMatrix (L*n) n).prod μ)
        {Gs | squaredDiagonalError (matrixEstimate P (gram Gs.1) Gs.2) (gram Gs.1) <
          β * (n : ℝ)^2} ≤ (1/4 : ℝ≥0∞) := by sorry

end SketchAttr.LOO.Supplement
Source
Chris Liaw, Aranyak Mehta, Grigoris Velegkas, Felix Zhou, Sketching Language Models for Context Attribution, STOC 2027 submission #9 (October 2026), PDF sha256 86af2569e45c55b1009e7453d4f53047b5820d44868a7f528bdb6fed1a2ef0e2, p. 29, Lemma C.2

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me