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

Approximate counting of common bases of two matroids

There is a single randomized oracle algorithm that, given independence oracles for arbitrary rank-rr matroids M1,M2M_1, M_2 on [n][n] and rational ϵ,δ∈(0,1)\epsilon, \delta \in (0, 1), outputs a nonnegative rational Z^\widehat{Z} such that P[(1−ϵ)Z(M1,M2)≤Z^≤(1+ϵ)Z(M1,M2)]≥1−δ\mathbb{P}[(1 - \epsilon)Z(M_1, M_2) \le \widehat{Z} \le (1 + \epsilon)Z(M_1, M_2)] \ge 1 - \delta, always outputs 00 if Z(M1,M2)=0Z(M_1, M_2) = 0, and on every execution has oracle calls and other bit operations bounded by a fixed polynomial in n,ℓ,ϵ−1,log⁡δ−1n, \ell, \epsilon^{-1}, \log \delta^{-1} (where ℓ\ell is the binary encoding length of n,r,ϵ,δn, r, \epsilon, \delta), using only independent unbiased random bits and no representation of either matroid.

For arbitrary matroids M1,M2M_1, M_2 on [n][n] (possibly of different ranks) supplied by independence oracles, each family F∈{Ck,C,Cmax⁡}\mathcal{F} \in \{\mathcal{C}_k, \mathcal{C}, \mathcal{C}_{\max}\} (common independent sets of size kk, all sizes, or maximum size) admits an FPRAS (with an exact emptiness pretest and polynomial bounds on every execution) and an almost-uniform sampler (deciding emptiness exactly, returning S∈FS \in \mathcal{F} on every execution when nonempty, with dTV(L(S),Unif(F))≤θd_{\mathrm{TV}}(\mathcal{L}(S), \mathrm{Unif}(\mathcal{F})) \le \theta and polynomial bounds in n,ℓ,θ−1n, \ell, \theta^{-1} on every execution).

For any q∈(0,1]q \in (0, 1], partition of VV into B,C,p,dB, C, p, d, and mm ordinary two-element slots E1,…,EmE_1, \dots, E_m with ∣B∣+1+m=n|B| + 1 + m = n, and any H:X→RH: \mathcal{X} \to \mathbb{R}, the squared difference of ff-weighted means on Xp\mathcal{X}_p and Xd\mathcal{X}_d satisfies (H‾p−H‾d)2≤(1spWp+1sdWd+2spsd∑t=1mvtWt)DX(H)(\overline{H}_p - \overline{H}_d)^2 \le \left(\frac{1}{s_p W_p} + \frac{1}{s_d W_d} + \frac{2}{s_p s_d} \sum_{t=1}^m \frac{v_t}{W_t}\right) D_{\mathcal{X}}(H).

For good multipliers and every H:Ω→RH: \Omega \to \mathbb{R}, Varπ(QH)≤KobsE(H)\mathrm{Var}_\pi(\mathsf{Q}H) \le K_{\mathrm{obs}}\mathcal{E}(H) with Kobs=2000n6K_{\mathrm{obs}} = 2000n^6, where Q\mathsf{Q} retains values on Ω0\Omega_0 and replaces values on each defect class Ωij\Omega_{ij} by its conditional mean.

With good multipliers, the trace chain PAP_A on A=Ω0A = \Omega_0 is reversible with stationary law μ\mu, irreducible, and lazy, with inverse spectral gap at most 18n418n^4, satisfying ∣PAs(x,y)μ(y)−1∣≤exp⁡(−s/(18n4))min⁡z∈Aμ(z)\left|\frac{P_A^s(x,y)}{\mu(y)} - 1\right| \le \frac{\exp(-s/(18n^4))}{\min_{z\in A}\mu(z)} for all s≥0s \ge 0, and expected underlying transitions per trace step at most U/π(A)≤5Un2U/\pi(A) \le 5Un^2 from a UU-warm start.

With good multipliers, if G=QGG = \mathsf{Q}G and a trajectory (Xt)(X_t) of PP starts with law ν≤Uπ\nu \le U\pi, then for every integer N≥1N \ge 1, Eν[(1N∑t=0N−1G(Xt)−EπG)2]≤2UKobsVarπGN\mathbb{E}_\nu\left[\left(\frac{1}{N}\sum_{t=0}^{N-1} G(X_t) - \mathbb{E}_\pi G\right)^2\right] \le \frac{2UK_{\mathrm{obs}}\mathrm{Var}_\pi G}{N}.

Methods

Paired-ground-set reduction encoding common bases of M1,M2M_1, M_2 on [n][n] as transversal bases of K=M1⊕M2∗K = M_1 \oplus M_2^* on V={x1,y1,…,xn,yn}V = \{x_1, y_1, \dots, x_n, y_n\}, with rank-deficiency weights fq(S)=qn−rkK(S)f_q(S) = q^{n - \mathrm{rk}_K(S)} on transversals Ω0\Omega_0 and single-defect sets Ωij\Omega_{ij}.

Source excerpts

“Make two copies of [n], with corresponding elements denoted xi, yi, and use the paired reduction of Anari, Oveis Gharan, and Vinzant [AOV21, arXiv version 2, Section 7, Equation (13)]: V = {x1, y1, . . . , xn, yn}, K = M1 ⊕ M∗2.” · Show in paper

“For 0 < q ≤ 1 and every S ∈ (V choose n), define d(S) = n − rkK(S), fq(S) = q^d(S).” · Show in paper

Lazy Metropolis chain on Ω=Ω0∪⋃i≠jΩij\Omega = \Omega_0 \cup \bigcup_{i \neq j} \Omega_{ij} with one-element exchange proposals and learned defect multipliers wijw_{ij}.

Source excerpts

“The Metropolis chain. At a state S, stay put with probability 1/2. Otherwise choose uniformly and independently a ∈ S and b ∈ V \ S, and propose S' = S \ {a} ∪ {b}. Reject if S' ∉ Ω; otherwise accept with probability min{1, λ(S')/λ(S)}.” · Show in paper

Annealing schedule with fresh independent warm restarts via the trace chain on Ω0\Omega_0 and empirical ratio and multiplier updates.

Source excerpts

“Each phase therefore generates a fresh starting transversal from the known law µ0, through the stored parameter levels and with independent randomness.” · Show in paper

Bounded-bit rational arithmetic and rejection-sampling bit-cap coupling to guarantee polynomial worst-case oracle and bit-operation bounds on every execution.

Source excerpts

“Allow at most Dbits trials in each uniform-integer call; if all fail, abort the run and return zero. The cap is O(1 + log M). Couple this procedure with the unrestricted-trial one using the same random bits up to an abort.” · Show in paper

Truncation and self-reduction via contraction/restriction minors with exact matroid-intersection feasibility pretests for counting and almost-uniformly sampling common independent sets.

Source excerpts

“For 0 < k ≤ h, define the truncation Tk(Mi) by declaring J independent exactly when it is independent in Mi and |J| ≤ k.” · Show in paper

“Define Ni on R by declaring, for J ⊆ R, J independent in Ni ⇐⇒ A ∪ J independent in Mi.” · Show in paper