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

An Almost-Linear Approximation Scheme for Edit Distance

There is one uniform randomized algorithm that, given explicitly stored strings x,yx, y of total length NN over polynomially bounded integer alphabets and a rational ε∈(0,1)\varepsilon \in (0, 1), returns a nonnegative integer D^\widehat{D} such that Pr⁡[ED(x,y)≤D^≤(1+ε)ED(x,y)]≥2/3\Pr[\mathrm{ED}(x, y) \le \widehat{D} \le (1 + \varepsilon)\mathrm{ED}(x, y)] \ge 2/3, with worst-case expected running time N1+o(1)N^{1+o(1)} as N→∞N \to \infty on the logarithmic-word RAM for every fixed rational ε\varepsilon, and returns zero deterministically on equal strings.

There is a lazily evaluated random table U(0)(I,q)U^{(0)}(I, q) of integers in [0,N][0, N] such that, with probability at least 0.990.99, simultaneously at every state c(I,q)≤U(0)(I,q)≤Ainitc(I,q)c(I, q) \le U^{(0)}(I, q) \le A_{\mathrm{init}} c(I, q), every zero-cost state has value zero on every execution, and conditional on any first request and previously exposed randomness, its expected evaluation cost is at most (1+∣I∣)2o(H)(1 + |I|)2^{o(H)} uniformly in the state.

Given a power of two 1≤A≤Ainit1 \le A \le A_{\mathrm{init}} and an integer table UU with 0≤U(I,q)≤N0 \le U(I, q) \le N and c(I,q)≤U(I,q)≤Ac(I,q)c(I, q) \le U(I, q) \le A c(I, q), setting a=max⁡{1,A/F}a = \max\{1, A/F\}, there is a randomized, finitely executable refinement table dSd_S such that dS(I,q)≥c(I,q)/ad_S(I, q) \ge c(I, q)/a for every outcome, E[(dS(I,q)−c(I,q))+]≤c(I,q)/ℓ\mathbb{E}[(d_S(I, q) - c(I, q))_+] \le c(I, q)/\ell conditionally on UU, and zero-cost states return zero for every outcome.

Given a nonempty finite list of rational probability vectors in Rd\mathbb{R}^d whose convex hull Q\mathcal{Q} has every coordinate positive in at least one listed vector, a rational vector vv, and an integer H≥4H \ge 4, a rational algorithm constructs a mixture of the listed vectors whose mean ρ\rho satisfies ∥ρ−ρt∥1≤H−3\|\rho - \rho_t\|_1 \le H^{-3}, where ρt\rho_t is the unique maximizer of H(ρ)+⟨v,ρ⟩\mathcal{H}(\rho) + \langle v, \rho \rangle on Q\mathcal{Q}, with bit operations, stored mixture size, and exact sampling expected cost polynomial in G0=H+d+2G_0 = H + d + 2, the list size, and the maximum input rational bit length.

The large-input algorithm has worst-case expected running time N1+o(1)N^{1+o(1)} on the logarithmic-word RAM over its internal randomness, including all input processing, preprocessing, table calculations, rational arithmetic, sampling, and data-structure operations, with workspace bounded by a fixed polynomial in NN on every execution.

For any partition of II into I1,…,ImI_1, \dots, I_m and any list α=(s1,…,sm)\alpha = (s_1, \dots, s_m) of valid child states, c(I,r)≤∑ic(Ii,si)+connr(α)c(I, r) \le \sum_i c(I_i, s_i) + \mathrm{conn}_r(\alpha) and ∣z(I,r)∣≤∑i∣z(Ii,si)∣+connr(α)|z(I, r)| \le \sum_i |z(I_i, s_i)| + \mathrm{conn}_r(\alpha), including for finite target intervals in any extension of yy.

On the fixed comparison tree, the total curvature and mass discrepancy satisfy ∑nonterminal(K+G)≤5000F(1+J/P+J/T)D\sum_{\mathrm{nonterminal}} (K + G) \le 5000 F(1 + J/P + J/T)D.

Conditioning on the complete child tables at a non-bad comparison node with ∣v^∣≤1−τ|\widehat{v}| \le 1 - \tau, the expected sum of clipped parent regrets satisfies E[∑t=1SRt∣child tables]≤hΣ(ln⁡dCη+2κ+SH−3)+2δc+2SH−4Fc\mathbb{E}\left[\sum_{t=1}^S \mathcal{R}_t \mid \text{child tables}\right] \le h_\Sigma\left(\frac{\ln d_{\mathcal{C}}}{\eta} + 2\kappa + SH^{-3}\right) + 2\delta c + 2SH^{-4}Fc.

Conditional on any fixed good preceding seed, the next seed constructed by taking the upper middle order statistic of H2H^2 independent refinement copies (scaled by aa and clamped to [0,N][0, N]) is good for factor 4a4a except with probability at most exp⁡(10H−H2)\exp(10H - H^2).

Methods

Uniform access to the rational accuracy input via bounded prefix inspection (at most H^2 + O(1) bits) and exact dynamic programming fallback below accuracy-dependent input-length thresholds.

Source excerpts

“Inspect at most H2 + O(1) bits of the accuracy input. If its complete encoding has not been obtained, use exact alignment dynamic programming. The unread suffix is neither copied nor addressed.” · Show in paper

Lazily evaluated initial coarse estimator using a deterministic B-ary shift tree and nonuniform additive precision sampling with private random streams per entry.

Source excerpts

“At a node with allowance aw, independently for its children draw Ri uniformly from {1, . . . , B} and set ti = awRi/(BQ0), awi = λti.” · Show in paper

“Finally, assign a separate random stream to every initial entry, keyed by its labeled main-tree node and endpoint pair, and cache the completed answer.” · Show in paper

Cost-cone lower envelopes on multi-scale dyadic grids and Bellman propagation over wide actions to construct warmup tables and cost proxies.

Source excerpts

“At a nonleaf I, consider all cones q |-> Ue(I, r) + L0|q − r|1 whose centers are grid states at some scale b with b/2 ≤ U(I, r) ≤ 4Ab.” · Show in paper

“Define the warmup tables at nonleaves by wj(I, q) = BI(wj−1)(q) (1 ≤ j ≤ T), m = (1/T) sum_{j=0}^{T-1} wj, d0 = wT.” · Show in paper

Prefix-cost-predicted alignment bands with velocity tests and rounded canonical actions.

Source excerpts

“Let Cb,r be the following set of shared-endpoint actions on the scale-b grid. The outside endpoints are exactly r, consecutive child endpoints agree, all endpoint shifts are within 6b of p0 = r− − l, and the shift p at every internal cut satisfies |p − p0 − vbΦj(p)| ≤ τθb/M.” · Show in paper

Entropy-regularized online action selection implemented via a finite-mixture Frank-Wolfe optimizer with smoothed entropy, rational arithmetic, and exact integer rejection sampling.

Source excerpts

“With entropy H(ρ) = − sum_k ρk ln ρk, using 0 ln 0 = 0, let ρt maximize H(ρ) + η <sum_{j<t} uj + gbt, ρ> over ρ ∈ Q.” · Show in paper

“Set σ = G0^-50 and smooth the objective by replacing −x ln x with −(x + σ) ln(x + σ) in each coordinate.” · Show in paper

Shared group sampling across whole cells with rounded child states and clipped parent updates.

Source excerpts

“For each node I, scale b, cell from Lemma 4.3, and time 1 ≤ t ≤ S, group all unskipped representatives in that whole cell.” · Show in paper

Lazy evaluation order with caching by complete keys and balanced search dictionary lookups for gathered recursive inputs.

Source excerpts

“Every table dependency strictly decreases the lexicographic triple (pass, index, remaining tree height).” · Show in paper

“Use a balanced search dictionary for gathered and globally stored inputs.” · Show in paper