VibeMathedMath problems solved with AI
Sign in

The Sharan-Sidford-Valiant precision question: do learners with o(d2)o(d^2) memory need Ω(dlog⁡(1/ϵ))\Omega(d\log(1/\epsilon)) samples for linear regression?

A streaming learner sees pairs (xt,yt)(x_t,y_t) with independent rows xt∼N(0,Id)x_t\sim N(0,I_d) and labels yt=⟨xt,s⟩y_t=\langle x_t,s\rangle for an unknown unit vector ss, reads each pair once and keeps at most MM bits between samples. With enough memory to store the equations, about dd samples determine ss; with real registers, Kaczmarz projection reaches accuracy ϵ\epsilon after about dlog⁡(1/ϵ)d\log(1/\epsilon) samples. Building on Raz's memory-sample lower bounds for parity, Sharan, Sidford and Valiant (STOC 2019) showed that d2/4d^2/4 bits force Ω(dlog⁡log⁡(1/ϵ))\Omega(d\log\log(1/\epsilon)) samples in a noisy version of this experiment, and asked (Section 1.1) whether the first-order dependence of the sample count on the precision is optimal under bounded memory. Must every learner with o(d2)o(d^2) (or at most Ad2Ad^2) bits of memory use Ω(dlog⁡(1/ϵ))\Omega(d\log(1/\epsilon)) samples to estimate ss to accuracy ϵ\epsilon?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Learning theory; memory-sample tradeoffs
Posed by
Vatsal Sharan, Aaron Sidford and Gregory Valiant (Memory-sample tradeoffs for linear regression with small error, STOC 2019, Section 1.1)
Year posed
2019
Years open
7y
Solved
2026-09-27
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
17 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Main theorem: for fixed A>0A>0 there are cA,dAc_A,d_A such that any learner with M≤Ad2M\le Ad^2 bits, d≥dAd\ge d_A, 0<ϵ≤1/100<\epsilon\le1/10 and uniform-prior success at least 2/32/3 in reaching angular error ϵ\epsilon needs horizon T≥cAdlog⁡(1/ϵ)T\ge c_A d\log(1/\epsilon); for M=o(d2)M=o(d^2) the constant is absolute, and the bound also holds under an every-signal guarantee. Transitions may use unbounded computation and randomness; the output uses only the terminal state, stopping index and fresh randomness, with a deterministic horizon. It implies an ΩA(drlog⁡d)\Omega_A(dr\log d) bound in the noisy experiment of Sharan-Sidford-Valiant at Euclidean accuracy d−rd^{-r} in their range. No matching finite-memory upper bound is proved, and memory well above d2d^2 is not treated.

What the AI did

The release README says all results in the release were produced by an unreleased internal OpenAI model with one fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This family is not among the README's exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region whose write-up was human-edited). The manuscripts are authored 'OpenAI' and name no human author. The family has six manuscripts of the same date: the principal one proves the lower bound for memory up to Ad2Ad^2, and five companions give alternative proofs or supporting estimates (posterior replicas, subsphere methods, projection moments and cap domination, Gaussian replacement, localization and information growth). Most are partly formalized in Lean.

Verification

No independent mathematician has checked this yet. Checked here: the main theorem, its two corollaries and the predecessors section of the principal manuscript were read against the Sharan-Sidford-Valiant question as the manuscript cites it. Lean: lean/docs/140.md lists eight challenges. ComparatorChallenges/NoiselessRegression (theorem OAI.NoiselessRegression.main, solution module OAI.Probability.GaussianRegression.Main, file exists at the pinned commit) is not in formalization.yaml; its statement was read here: for M=o(d2)M=o(d^2) an absolute cc with T≥c dlog⁡(1/ϵ)T\ge c\,d\log(1/\epsilon) under uniform-prior or every-signal success 2/32/3, and for M≤Ad2M\le Ad^2 a constant cAc_A, for finite-state randomized learners with exact Gaussian observations and angular error. That is the headline. MemoryPrecision.main (in formalization.yaml) covers supporting estimates and the M≤d2M\le d^2 case. Not rebuilt here. The model is exact (noiseless) observations; the noisy consequence is derived in the paper, not formalized.

Sources

Changelog1 change

Discussion