By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

Memory and precision in noiseless Gaussian regression

For every fixed finite A>0A > 0, there are constants cA>0c_A > 0 and dAd_A such that for d≥dAd \geq d_A, integer 0≤M≤Ad20 \leq M \leq Ad^2, and 0<ϵ≤1/100 < \epsilon \leq 1/10, any learner in Definition 1.1 that draws S∼σdS \sim \sigma_d independently of the rows and data-independent randomness and achieves P{arccos⁡⟨s^,S⟩≤ϵ}≥2/3\mathbb{P}\{\arccos\langle \widehat{s}, S\rangle \leq \epsilon\} \geq 2/3 must have prescribed horizon T≥cAdlog⁡(1/ϵ)T \geq c_A d \log(1/\epsilon).

For any integer-valued memory sequence M(d)=o(d2)M(d) = o(d^2) and any accuracy sequence 0<ϵ(d)≤1/100 < \epsilon(d) \leq 1/10, a family of learners in Definition 1.1 with uniform-sphere average success at least 2/32/3 satisfies T(d)≥cdlog⁡(1/ϵ(d))T(d) \geq c d \log(1/\epsilon(d)) for all sufficiently large dd, where c>0c > 0 is an absolute constant.

The conclusions of Theorem 1.2 and Corollary 1.3 also hold when the uniform-sphere average-success assumption is replaced by P{arccos⁡⟨s^,s⟩≤ϵ}≥2/3\mathbb{P}\{\arccos\langle \widehat{s}, s\rangle \leq \epsilon\} \geq 2/3 for every s∈Sd−1s \in S^{d-1}.

Theorem 1.2 implies an ΩA(drlog⁡d)\Omega_A(dr \log d) sample lower bound in the noisy Gaussian experiment of Sharan, Sidford, and Valiant [12] for every fixed finite A>0A > 0, memory M≤Ad2M \leq Ad^2, and Euclidean accuracy e=d−re = d^{-r} in their fine-accuracy range, for sufficiently large dd.

Under the assumptions that μ\mu is a finite nonnegative Borel measure supported on B(z,R)B(z, R) satisfying μ(B(x,r))≤Hrβ\mu(B(x, r)) \leq H r^\beta for all x∈Rd,r>0x \in \mathbb{R}^d, r > 0 with β>m+p−2\beta > m + p - 2, the image measure ημ\eta_\mu of γm(dA)μ(ds)\gamma_m(dA)\mu(ds) under (A,s)↦(A,As)(A, s) \mapsto (A, As) has a nonnegative jointly Borel density FF with respect to λm\lambda_m vanishing outside Ez,R\mathcal{E}_{z,R} and satisfying ∥F∥Lp(λm)≤B\|F\|_{L^p(\lambda_m)} \leq \mathcal{B}.

For d≥d0d \geq d_0, M≤d2M \leq d^2, and 0<ϵ≤1/100 < \epsilon \leq 1/10, every learner in Definition 1.1 has angular success probability under the paired-coordinate cube prior s=ι(u)s = \iota(u), u∼duu \sim du, at most min⁡{1,Dn(m+1)ϵn/4}\min\{1, D^{n(m+1)}\epsilon^{n/4}\} where m=⌈T/k0⌉m = \lceil T/k_0\rceil, k0=⌊n/4⌋k_0 = \lfloor n/4\rfloor. If that same learner has angular success probability at least 2/32/3 for every s∈Sd−1s \in S^{d-1}, then T≥cdlog⁡(1/ϵ)T \geq c d \log(1/\epsilon).

For all sufficiently large dd and integer 0≤T≤d/40 \leq T \leq d/4, any possibly randomized estimator W∈RdW \in \mathbb{R}^d based on the entire pair (X,Y)(X, Y) where XX is T×dT \times d standard Gaussian and Y=XSY = XS for S∼σdS \sim \sigma_d satisfies P{∥W−S∥≤ϵ}≤13+(25)3d/4−1<23\mathbb{P}\{\|W - S\| \leq \epsilon\} \leq \frac{1}{3} + (\frac{2}{5})^{3d/4 - 1} < \frac{2}{3} for every 0<ϵ≤1/100 < \epsilon \leq 1/10, so T>d/4T > d/4 is required even with unlimited memory.

For d≥2d \geq 2, z∈Sd−1z \in S^{d-1}, and r>0r > 0, σd(B(z,r))≤rd−1\sigma_d(B(z, r)) \leq r^{d-1}, and any probability law QQ on Sd−1S^{d-1} independent of the signal has local mass at scale R=ϵR = \epsilon: ∫B(z,r)h dσd≤(ϵr)(d−1)/2\int_{B(z,r)} h \, d\sigma_d \leq (\epsilon r)^{(d-1)/2}.

If measurable functions h1,…,hN:Sd−1→[0,1]h_1, \dots, h_N : S^{d-1} \to [0, 1] have local mass at a common scale R>0R > 0 and gjg_j are Borel routing probabilities with ∑j=1Ngj≤1\sum_{j=1}^N g_j \leq 1, then h(s)=∑j=1Nhj(s)∫gj(A,As) dγm(A)h(s) = \sum_{j=1}^N h_j(s) \int g_j(A, As) \, d\gamma_m(A) has local mass at scale R′=Rexp⁡(Cd/a)N1/(aq)R' = R \exp(Cd/a) N^{1/(aq)}.

For d≥d0d \geq d_0, every learner in Definition 1.1 with M≥0M \geq 0 bits and deterministic horizon T≥0T \geq 0 satisfies P{arccos⁡⟨s^,S⟩≤ϵ}≤min⁡{1,[2ϵexp⁡(C(1+M/d2)⌈T/q⌉)]a}\mathbb{P}\{\arccos\langle \widehat{s}, S\rangle \leq \epsilon\} \leq \min\{1, [2\epsilon \exp(C(1 + M/d^2)\lceil T/q\rceil)]^a\} for S∼σS \sim \sigma and 0<ϵ≤1/100 < \epsilon \leq 1/10.

If a learner in Definition 1.1 has uniform-sphere average angular success at least 2/32/3 at accuracy 0<ϵ≤1/100 < \epsilon \leq 1/10, then its deterministic horizon must satisfy T>d/4T > d/4.

Methods

Finite-state Gaussian regression model with a data-independent shared seed, at most 2M2^M persistent states, deterministic horizon TT, fresh-row observations xt∼N(0,Id),yt=⟨xt,s⟩x_t \sim N(0, I_d), y_t = \langle x_t, s\rangle, and joint/per-seed measurability.

Source excerpts

“Fix integers d ≥ 2, M ≥ 0, and T ≥ 0. A data-independent shared seed may choose the learner’s rules; the descriptions of its transitions and output below are conditional on that seed. A signal s ∈ Sd−1 is chosen before sampling. At sample index t ∈ {1, . . . , T}, the observation is xt ∼ N(0, Id), yt = ⟨xt, s⟩, where the rows x1, . . . , xT are independent.” · Show in paper

Backward induction on the local mass ∫B(z,r)h dσd≤(Rr)a\int_{B(z,r)} h \, d\sigma_d \leq (Rr)^a of future success functions from prescribed states under the fixed original prior, avoiding conditioning on singular hyperplane sections.

Source excerpts

“We instead keep the original prior fixed and study the probability of future success from a prescribed state. Start the learner at a chosen state and index, whether or not the state was reached in an actual run. Let h(s) be its success probability with signal s, using fresh future samples. For a closed Euclidean ball B(z, r), our invariant is ∫B(z,r) h dσd ≤ (Rr)(d−1)/2 (z ∈ Sd−1, r > 0).” · Show in paper

Exact Gaussian projection density estimation via Frostman-type affine-distance bounds, a Gaussian difference identity, Gaussian smoothing, and compact-test LpL^p duality.

Source excerpts

“We prove the theorem by controlling inverse affine distances, expanding a smoothed density moment, and then removing the smoothing on matrix–label space.” · Show in paper

Common projected support volume estimation using the exact image ellipsoid Ez,R\mathcal{E}_{z,R} and Hadamard's inequality to cancel the radius power lost in the LqL^q density bound.

Source excerpts

“In singular-value coordinates, AB(0, R) is an ellipsoid whose semiaxes are R times the m singular values of A. Its volume is therefore exactly vmRm√det(AAT). Hadamard’s inequality bounds the square root by the product of the row norms” · Show in paper

Seedwise replacement of completed-measurable transition and stopping kernels by everywhere-defined Borel versions under a dominated sample law.

Source excerpts

“There are everywhere-defined Borel transition and stopping kernels, with the same state sets and terminal output laws, whose π-prior joint law of the signal, state path, stopping index and output is the same as for the original rules.” · Show in paper

Reflection of the uniform spherical signal across the row span of observed Gaussian rows to obtain memory-independent constant-accuracy lower bounds.

Source excerpts

“Conditional on A, reflection across U sends S = u + v to u − v. It preserves uniform spherical measure and the data (A, AS), because Av = 0, so the output kernel is the same at both signals.” · Show in paper

Paired-coordinate embedding of a lower-dimensional cube Q=[−1/2,1/2]nQ = [-1/2, 1/2]^n onto Sd−1S^{d-1} to transfer local mass bounds to ambient Euclidean balls.

Source excerpts

“Define ι(u) = 1/√n (u1, . . . , un, √(1 − u1^2), . . . , √(1 − un^2), 0, . . . , 0) ∈ Rd, (37) with d − 2n zero coordinates. Each coordinate pair contributes 1/n to the squared norm, so ι(Q) ⊂ Sd−1.” · Show in paper