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

Sharp binary-information contraction on the discrete cube

For every finite n≥0n \ge 0, every soft binary channel u:Ωn→[−1,1]u: \Omega_n \to [-1, 1], and −1≤ρ≤1-1 \le \rho \le 1, I(Tρu)≤ψ(∣ρ∣ψ−1(I(u)))I(T_\rho u) \le \psi(|\rho| \psi^{-1}(I(u))), where ψ−1\psi^{-1} is the nonnegative increasing branch on [0,L][0, L], and for n≥1n \ge 1, every soft coordinate u(x)=axiu(x) = a x_i with ∣a∣≤1|a| \le 1 attains equality.

For every finite n≥0n \ge 0, ρ∈[−1,1]\rho \in [-1, 1], and Boolean function f:Ωn→{−1,1}f: \Omega_n \to \{-1, 1\} with m=Efm = \mathbb{E}f and rm=ψ−1(H(m))r_m = \psi^{-1}(H(m)), I(f(X);Y)≤ψ(∣ρ∣rm)≤ψ(∣ρ∣)I(f(X); Y) \le \psi(|\rho| r_m) \le \psi(|\rho|), with signed coordinate functions attaining the bound at m=0m = 0 for n≥1n \ge 1, and strict inequality below ψ(∣ρ∣)\psi(|\rho|) if 0<∣m∣<10 < |m| < 1 and 0<∣ρ∣≤10 < |\rho| \le 1; in bits, I2(f(X);Y)≤ψ(ρ)/L=1−h2(ε)I_2(f(X); Y) \le \psi(\rho)/L = 1 - h_2(\varepsilon), resolving the Courtade–Kumar conjecture.

For every finite n≥0n \ge 0 and every g:{−1,1}n→(−1,1)g: \{-1, 1\}^n \to (-1, 1) with m=Egm = \mathbb{E}g, D(g)≥B^m(I(g))=max⁡{Bm(I(g)),F(I(g))}≥F(I(g))D(g) \ge \widehat{\mathcal{B}}_m(I(g)) = \max\{\mathcal{B}_m(I(g)), F(I(g))\} \ge F(I(g)).

For every 0<e≤emax⁡0 < e \le e_{\max}, a three-point law of the form λδ(x,y)+π+δ(1,1)+π−δ(−1,−1)\lambda \delta_{(x,y)} + \pi_+ \delta_{(1,1)} + \pi_- \delta_{(-1,-1)} attains the common-budget joining cost K(m,δ,e)\mathcal{K}(m, \delta, e) and has average entropy exactly ee.

For any joint law (A,B)(A, B) on [−1,1]2[-1, 1]^2 with ea=EH(A)>0e_a = \mathbb{E}H(A) > 0 and eb=EH(B)>0e_b = \mathbb{E}H(B) > 0, Ec(A,B)≥Bm(I)−Ba(Ia)+Bb(Ib)2\mathbb{E}c(A, B) \ge \mathcal{B}_m(I) - \frac{\mathcal{B}_a(I_a) + \mathcal{B}_b(I_b)}{2}.

For the common-output path (6.2) with core (ac,bc)(a_c, b_c) and mass λ∈(0,1]\lambda \in (0, 1], F(ν+J)−F(ν)≤λF(Jc)F(\nu + J) - F(\nu) \le \lambda F(J_c).

For any joint law (A,B)(A, B) on [−1,1]2[-1, 1]^2 with ea=EH(A)>0e_a = \mathbb{E}H(A) > 0 and eb=EH(B)>0e_b = \mathbb{E}H(B) > 0, Ec(A,B)≥B^m(I)−B^a(Ia)+B^b(Ib)2\mathbb{E}c(A, B) \ge \widehat{\mathcal{B}}_m(I) - \frac{\widehat{\mathcal{B}}_a(I_a) + \widehat{\mathcal{B}}_b(I_b)}{2}.

At every fixed m∈(0,1)m \in (0, 1), Bm(H(m)−h)∼1−m22log⁡1h\mathcal{B}_m(H(m) - h) \sim \frac{1 - m^2}{2} \log \frac{1}{h} while Cm(H(m)−h)∼1−m2log⁡1hC_m(H(m) - h) \sim \frac{1 - m}{2} \log \frac{1}{h} as h↓0h \downarrow 0, so the hybrid production profile CmC_m of Chen et al. does not dominate Bm\mathcal{B}_m (their ratio tends to 1+m>11 + m > 1).

Methods

Local-to-global differential method: prove a local entropy-production inequality on coupled pairs, lift it to arbitrary dimension by induction on the cube coordinates, and integrate along the noise semigroup in the inverse entropy deficit coordinate r(s)=ψ−1(I(gs))r(s) = \psi^{-1}(I(g_s)).

Source excerpts

“Chen, Gohari, and Nair [6] developed the differential approach that we use: prove a local entropy-production inequality, lift it by induction on the cube dimension, and integrate along the noise semigroup.” · Show in paper

“The appropriate coordinate for this comparison is the inverse entropy deficit, rather than information itself. In that coordinate the comparison flow is simply exponential decay.” · Show in paper

Common-entropy-budget joining minimization: minimize the joining cost Ec(A,B)\mathbb{E}c(A, B) over all coupled pair laws with prescribed means and bounded average conditional entropy, solved explicitly by a three-point optimizer (one interior pair and two equal-output corners) certified by a priced affine lower bound.

Source excerpts

“We minimize the joining cost over all coupled pair laws with the same child means and average conditional entropy, extending c by zero at the equal corners and by +∞ at every other boundary pair. The exact optimizer has one interior pair (ac, bc) and possibly the two equal-output corners (1, 1) and (−1, −1).” · Show in paper

“We now turn this constrained minimum into an affine lower bound in the pair values, valid for every coupled law.” · Show in paper

Two-capacity allocation and common-output thinning: decompose the mean-dependent reserve profile Bm(I)\mathcal{B}_m(I) into linear and coordinate capacities, and bound the information-rate increment along a common-output mixture path via an Euler derivative and an entropy-interval estimate.

Source excerpts

“Its construction can be read as an allocation of information between two capacities. Set α = 1 − m2 and cm = H(m) − αL ≥ 0.” · Show in paper

“We prove this by showing that [F(ν +J)−F(ν)]/λ increases with λ. This normalization matches the mixture’s cost λc(ac, bc). We first compute its derivative and identify the entropy-interval estimate that makes it nonnegative.” · Show in paper