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 FPRAS for Cell-Bounded Contingency Tables

There exists a randomized algorithm (FPRAS) that, given binary-encoded margins r∈Z≥0mr \in \mathbb{Z}_{\ge 0}^m, c∈Z≥0nc \in \mathbb{Z}_{\ge 0}^n with equal total, cell bounds b∈Z≥0m×nb \in \mathbb{Z}_{\ge 0}^{m \times n} (allowing bij=0b_{ij}=0 and with both m,nm,n part of the input), and rational ε,δ∈(0,1)\varepsilon, \delta \in (0,1), outputs a nonnegative rational Z^\widehat{Z} satisfying P((1−ε)Z(r,c,b)≤Z^≤(1+ε)Z(r,c,b))≥1−δ\mathbb{P}((1-\varepsilon)Z(r,c,b) \le \widehat{Z} \le (1+\varepsilon)Z(r,c,b)) \ge 1-\delta, outputs 00 on every execution if Ω(r,c,b)\Omega(r,c,b) is empty, uses only independent unbiased random bits, requires no counting or sampling oracle, and has total bit operations bounded on every execution by a fixed polynomial in L,ε−1,log⁡(δ−1)L, \varepsilon^{-1}, \log(\delta^{-1}), where LL is the total binary input length.

For any explicitly listed finite directed multigraph G=(V,E)G=(V,E) (allowing loops) with binary-encoded finite integer arc bounds ℓe,ue∈Z\ell_e, u_e \in \mathbb{Z} and vertex balances βv∈Z\beta_v \in \mathbb{Z}: (i) there is an FPRAS outputting a nonnegative rational Z^flow\widehat{Z}_{\mathrm{flow}} within (1±ε)∣F∣(1 \pm \varepsilon)|\mathcal{F}| with probability at least 1−δ1-\delta (and 00 on every execution if F=∅\mathcal{F}=\emptyset) using at most a fixed polynomial in L,ε−1,log⁡(δ−1)L, \varepsilon^{-1}, \log(\delta^{-1}) bit operations on every execution; (ii) there is a sampling algorithm that reports infeasibility iff F=∅\mathcal{F}=\emptyset and otherwise outputs f^∈F\widehat{f} \in \mathcal{F} on every execution with TV(L(f^),Unif(F))≤τ\mathrm{TV}(\mathcal{L}(\widehat{f}), \mathrm{Unif}(\mathcal{F})) \le \tau using at most a fixed polynomial in L,τ−1L, \tau^{-1} bit operations on every execution.

For the feasible tightened instance, the final softened partition function C(H)C(H) satisfies Z≤C(H)≤(1+ε/32)ZZ \le C(H) \le (1 + \varepsilon/32)Z.

Under balanced summation of disjoint coordinate pairs of capacity at least one in a laminar log-concave integer model, the two-removal and two-addition matrices of the remaining-coordinate weight have at most one positive eigenvalue (Lemma 3.1), which implies the same signature properties for hj(x,y)h_j(x,y) (Corollary 3.2) and log-concavity of the tree-cell marginals at(k)a_t(k) under C(H)C(H) (Lemma 3.3).

The two factorial lifts fjf_j and f~j\widetilde{f}_j agree on transversals (summing to C(j)C(j)), satisfy q−1fj(S)≤f~j(S)≤qfj(S)q^{-1}f_j(S) \le \widetilde{f}_j(S) \le q f_j(S) with q=W2q = W^2 on A∪⋃i≠lAil\mathcal{A} \cup \bigcup_{i \ne l} \mathcal{A}_{il}, have the omission property (fjf_j) and addition property (f~j\widetilde{f}_j) on all pp-subsets (preserved under fixing elements and summing pairs at occupancy one), and yield the defect-mass inequalities 4c~ilσc~liσ≤zσ24\widetilde{c}_{il}^\sigma \widetilde{c}_{li}^\sigma \le z_\sigma^2 and c~ilσc~lkσ≤zσc~ikσ\widetilde{c}_{il}^\sigma \widetilde{c}_{lk}^\sigma \le z_\sigma \widetilde{c}_{ik}^\sigma.

When the multipliers satisfy the goodness condition C/(4cil)≤wil≤4C/cilC/(4c_{il}) \le w_{il} \le 4C/c_{il}, the enlarged Metropolis chain satisfies CVarμ(g)≤CpD(g)C\mathrm{Var}_\mu(g) \le C_{\mathrm{p}}\mathfrak{D}(g) (Proposition 5.2), Varπ(Qg)≤KobsE(g)\mathrm{Var}_\pi(\mathcal{Q}g) \le K_{\mathrm{obs}}\mathcal{E}(g) (Proposition 5.4), a finite-time MSE bound 2UKobsVarπ(G)/N2UK_{\mathrm{obs}}\mathrm{Var}_\pi(G)/N for time averages of Q\mathcal{Q}-invariant observables from a UπU\pi-dominated initial law (Lemma 5.5), and an inverse spectral gap at most 2p2Cp≤Kobs2p^2 C_{\mathrm{p}} \le K_{\mathrm{obs}} and expected return time at most U/π(A)U/\pi(\mathcal{A}) for the transversal trace PtrP_{\mathrm{tr}} (Lemma 5.6).

For any box-valid small-count profile (x,y)(x,y) with total pp, 0≤j≤H0 \le j \le H, and rational 0<ξin,θ<1/40 < \xi_{\mathrm{in}}, \theta < 1/4, there is a randomized procedure returning a positive rational h^\widehat{h} such that P[(1−ξin)hj(x,y)≤h^≤(1+ξin)hj(x,y)]≥1−θ\mathbb{P}[(1-\xi_{\mathrm{in}})h_j(x,y) \le \widehat{h} \le (1+\xi_{\mathrm{in}})h_j(x,y)] \ge 1-\theta, with bit cost on every execution bounded by a fixed polynomial in L,ε−1,ξin−1,θ−1L, \varepsilon^{-1}, \xi_{\mathrm{in}}^{-1}, \theta^{-1} and parameter encoding lengths, and with Mf2−j/16≤h^≤8MfM_f 2^{-j}/16 \le \widehat{h} \le 8M_f on every execution.

The capped reference annealing experiment succeeds with probability at least 1−1/501 - 1/50 with ∣log⁡(Zref/C(H))∣≤4Hη|\log(Z_{\mathrm{ref}}/C(H))| \le 4H\eta (Proposition 7.2), and the fair-bit implemented run can be coupled to it with disagreement probability at most 10J∗ξ10 J_* \xi while having bit operations and output bit length bounded on every execution by a fixed polynomial in LL and ε−1\varepsilon^{-1} (Lemma 7.3).

Methods

Deterministic preprocessing of cell-bounded contingency tables via Edmonds–Karp flow feasibility, binary search for exact cell extrema [l_s, u_s], capacity tightening b_s = u_s - l_s, and separation of remaining cells at threshold W into small cells and a maximum-capacity spanning forest T with free cells F.

Source excerpts

“For feasibility, form a directed network with a source, the row and column vertices, and a sink. Give the source-to-row arcs capacities ri, the row-to-column arcs capacities bij , and the column-to-sink arcs capacities cj . An integral flow of value N = P i ri = P j cj is exactly a feasible table” · Show in paper

“Replace each cell value Xs by Xs − ℓs, replace its upper bound by bs = us − ℓs, and subtract all incident minima from each margin.” · Show in paper

“In each connected component choose a spanning tree of maximum total capacity, and choose a root. An isolated vertex constitutes a component with an empty tree. The union of these trees is denoted by T ; the large cells outside T form the set F of free cells.” · Show in paper

Softened counting via root-margin and tree-bound penalty D(x, y, z) and two-view small-cell profiles (x_s, y_s), defining C(j) as the sum of h_j(x, y) over balanced profiles.

Source excerpts

“D(x, y, z) = A ( sum_{v a root} |δv| + sum_{t in T} dist(zt, [0, bt]) / bt ). (4)” · Show in paper

“hj (x, y) = sum_{z in prod_{e in F} {0,...,be}} 2^{-jD(x,y,z)/H}, (x, y) ∈ P. (8)” · Show in paper

Two-lift binary encoding on 2p elements (transversals A and one-defect classes AilA_{il}) with factorial weights f_j and ef_j, and an enlarged Metropolis chain with learned defect multipliers wilw_{il}.

Source excerpts

“fj (S) = hj (x, y) prod_{s small} xs! ys! / bs! , efj (S) = hj (x, y) prod_{s small} (bs − xs)! (bs − ys)! / bs! . (22)” · Show in paper

“The chain holds with probability 1/2. Otherwise it independently chooses one uniform element of S and one uniform element of its complement and proposes to exchange them. A proposal outside X is rejected. A proposal S′ in X is accepted with probability min{1, λ(S′)/λ(S)}.” · Show in paper

Weighted bin Metropolis walk with dyadic weights V_a(v) = 2^{-floor(a D(v)/H)}, population-correction factor α_v, and bisection rounding of 2^{-j D(s)/H}/V_j(v) to estimate h_j(x, y).

Source excerpts

“Va(v) = 2^{-floor(aD(v)/H)}, ϱa(w) = 2^{-aD(w)/H} (w ∈ [0, B]e).” · Show in paper

“T(v, z) = αv 2^{-jD(s)/H} / Vj (v) . (53)” · Show in paper

Capped-restart annealing over j = 0, ..., H - 1 with warm transversal trace restarts, finite-bit uniform integer draws (Lemma 6.4), dyadic acceptance thresholds, and median-of-runs amplification.

Source excerpts

“1. Restart on transversals. Draw a fresh state from µ0. For a = 1, . . . , j, run τ successive trace steps of Pa,w(a) , continuing from the transversal reached at the preceding stage.” · Show in paper

“For every finite-choice draw from {0, . . . , v − 1}, apply Lemma 6.4 with M = v and ζ = ξ. This uses a fixed number of fair bits and has total variation error at most ξ.” · Show in paper

Flow-to-table bijection via arc subdivision with private vertices and self-reduction by bisecting cell intervals with exact feasibility tests for counting and sampling bounded integral flows.

Source excerpts

“For each original arc e = (u, v) introduce a private new vertex we and replace the arc by u → we → v, giving both arcs cap ce and giving we balance zero.” · Show in paper

“We use the self-reduction principle connecting approximate counting and almost-uniform generation [18, Theorem 6.3], implemented here by bisecting binary cell intervals.” · Show in paper