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

Distortion of countably branching diamonds from midpoint and tree energies

For every integer k≥0k \ge 0, every distortion-DD embedding of the normalized depth-kk countably branching diamond Dk\mathcal{D}_k into either the finite-height segment forest dual X=J∗X = J^* or the infinite-height coordinate predual B∞B_\infty satisfies D2≥1+k/4D^2 \ge 1 + k/4.

In the finite-height segment forest dual XX and the infinite-height closed coordinate span B∞B_\infty, every infinite ε\varepsilon-separated symmetric RR-lens satisfies ∥x∥2+ε2/16≤R2\|x\|^2 + \varepsilon^2/16 \le R^2.

Every embedding of Dk\mathcal{D}_k into the finite-height segment forest dual XX with distortion at most DD satisfies k≤256D2k \le 256 D^2, proved directly without invoking the companion midpoint inequality.

Every noncontracting DD-Lipschitz embedding of Dk\mathcal{D}_k into XX satisfies D>k/144D > \sqrt{k}/144 for k≥1k \ge 1, proved directly by balancing dyadic prefix sums along a random descent.

For the finite-height segment forest dual XX, no finite DD admits distortion-DD embeddings of Dk\mathcal{D}_k for all k≥1k \ge 1.

In the linear path-cost space XlinX_{\mathrm{lin}}, every distortion-DD embedding of Dk\mathcal{D}_k satisfies D2≥1+k/16D^2 \ge 1 + k/16.

In the quadratic path-cost space XquadX_{\mathrm{quad}}, every distortion-DD embedding of Dk\mathcal{D}_k satisfies D2≥1+k/49D^2 \ge 1 + k/49.

In the prescribed start-cost space XstartX_{\mathrm{start}}, every distortion-DD embedding of Dk\mathcal{D}_k satisfies D2≥1+k/64D^2 \ge 1 + k/64.

In the incomparable-segments space XI=YI∗X_I = Y_I^*, every distortion-DD embedding of Dk\mathcal{D}_k satisfies k≤K2D(D−1)k \le K^2 D(D - 1) with K=2+6K = \sqrt{2} + \sqrt{6}.

In the recursive upper-array space XvX_{\mathrm{v}}, every distortion-DD embedding of Dk\mathcal{D}_k satisfies c6k8≤D6−D4\frac{c_6 k}{8} \le D^6 - D^4 with c6=2exp⁡(−(e−1))4−6c_6 = 2\exp(-(e-1))4^{-6}, as well as c3k22≤D3−D\frac{c_3 k}{2\sqrt{2}} \le D^3 - D with c3=(6e)−3c_3 = (6e)^{-3}.

In the free-root joined-tree norm XJX_J, every distortion-DD embedding of Dk\mathcal{D}_k satisfies D−1≤(1−η(2/D))kD^{-1} \le (1 - \eta(2/D))^k for some η(2/D)∈(0,1)\eta(2/D) \in (0, 1), and in the fixed-zero-root norm X0X_0, every distortion-DD embedding satisfies k≤4608D3(1−D−1)k \le 4608 D^3(1 - D^{-1}).

Methods

Finite-dimensional pair selection using total boundedness of bounded subsets in finite-rank coordinate projections PP or finite-dimensional quotients X/FX/F to extract two separated deviations zi,zjz_i, z_j whose half-difference w=(zi−zj)/2w = (z_i - z_j)/2 has arbitrarily small projection or distance to FF.

Source excerpts

“In the first selection, the bounded sequence (Pzi) has two distinct members at distance less than 2η, because bounded subsets of a finite-dimensional space are totally bounded. This gives the first inequality in (2.4) and hence the second.” · Show in paper

Primal-test correction at the first fresh roots outside a finite ancestral head AA to control the extra squared-norm cost of segments crossing the head boundary.

Source excerpts

“The correction controls the extra squared cost of segments crossing the head boundary. Its value is placed at each first exterior vertex. For crossings with a large head sum, the proof either makes the cross term nonpositive or controls it by splitting the head portion.” · Show in paper

Balancing dyadic prefix sums along a random descent by decomposing finite blocks into connected tree components, binning by dyadic sizes BCB_C, and maintaining ∣SB(v)∣≤B|S_B(v)| \le B via opposite-sign orientations.

Source excerpts

“The invariant is |SB(v)| ≤ B for every v. Before adding a new component C, the sum of earlier bin-BC contributions above its root rC is fixed; choose a weak sign opposite to this sum, with either choice at zero.” · Show in paper

Atomic prediction energy with finite binary slope martingales, representing terminal slopes as conditional expectations of a finitely valued random atom and bounding layer norms via endpoint-interval counting or start-interval counting with refining active/inactive status partitions.

Source excerpts

“The lemma supplies the same finite martingale for two different energy arguments. In either argument a large child layer is decomposed into three terms: segments charged to the chosen interval, coefficients already predicted from the parent, and the change in their prediction.” · Show in paper

Weakly null paired differences obtained by diagonalizing evaluations of a bounded deviation sequence on a countable norm-dense subset of the dual space and pairing successive terms wj=(z2j−z2j−1)/2w_j = (z_{2j} - z_{2j-1})/2.

Source excerpts

“For a parent with child bound R in the noncontracting normalization, the bounded sequence of deviations zi has a weakly Cauchy subsequence. Indeed, diagonalize its evaluations on a countable norm-dense subset of X∗lin, then use boundedness to approximate every other functional. Relabel this subsequence and set wj = (z2j − z2j−1)/2.” · Show in paper