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

Hellinger contraction with arbitrary Boolean output bias

For every n≥1n \ge 1, every Boolean function f:{−1,1}n→{−1,1}f : \{-1, 1\}^n \to \{-1, 1\}, and every ρ∈[−1,1]\rho \in [-1, 1], writing m=Efm = \mathbb{E}f and H(t)=1−t2H(t) = \sqrt{1 - t^2}, one has H(m)−EH(Tρf)≤1−H(ρ)H(m) - \mathbb{E}H(T_\rho f) \le 1 - H(\rho), with equality for signed coordinates f(x)=±xif(x) = \pm x_i.

For every Boolean function f:{−1,1}n→{−1,1}f : \{-1, 1\}^n \to \{-1, 1\} with m=Efm = \mathbb{E}f and 0<ρ<10 < \rho < 1, if s=1−ρ2≤.84s = \sqrt{1 - \rho^2} \le .84, then EH(Tρf)≥H(m)−1+s\mathbb{E}H(T_\rho f) \ge H(m) - 1 + s.

For a nonconstant Boolean function ff, 0<ρ<10 < \rho < 1, s≥.84s \ge .84, and 0≤m≤r2/20 \le m \le r^2/2, if b=h−1+sb = h - 1 + s and E(d)≤K=r/s\mathcal{E}(d) \le K = r/s, then ff is a signed coordinate.

For a nonconstant Boolean function ff with r2/2≤m≤37/50r^2/2 \le m \le 37/50 and 21/25≤s<121/25 \le s < 1, if b=h−1+sb = h - 1 + s, then E(d)>r/s\mathcal{E}(d) > r/s.

If f:{−1,1}n→{−1,1}f : \{-1, 1\}^n \to \{-1, 1\} has 0.74≤m<10.74 \le m < 1 and 0.84≤s≤10.84 \le s \le 1, then h−b≤1−sh - b \le 1 - s.

For XX uniform on {−1,1}n\{-1, 1\}^n, ff Boolean, and Yi=XiZiY_i = X_i Z_i with Pr⁡(Zi=−1)=ε∈[0,1/2]\Pr(Z_i = -1) = \varepsilon \in [0, 1/2], the mutual information satisfies I(f(X);Y)≤1−h2(ε)I(f(X); Y) \le 1 - h_2(\varepsilon), with equality for signed coordinates.

Methods

Asymmetric profile and dimension induction: compressing Boolean functions to increasing functions and inducting on the number of active coordinates using an asymmetric concave profile GG and polynomial lower bound B(m)B(m).

Source excerpts

“For s ≤ .84, we compress to increasing Boolean functions and induct in dimension. For each fixed s we choose a concave function G : [0, 1] → [0, ∞) and a nonnegative polynomial B on [−1, 1], and prove the stronger bound EG((1 + Tρf)/2) ≥ sB(m).” · Show in paper

“Lemma 3.2 (Compression). For every Boolean function f there is an increasing Boolean function ˜f with the same mean such that EH(Tρ ˜f) ≤ EH(Tρf).” · Show in paper

Semigroup continuation criterion: expressing the noise-semigroup derivative of EH(Tρf)\mathbb{E}H(T_\rho f) as an edge energy E(d)\mathcal{E}(d) and reducing the inequality for s>.84s > .84 to excluding a first crossing b=h−1+sb = h - 1 + s with E(d)≤r/s\mathcal{E}(d) \le r/s.

Source excerpts

“Lemma 4.1 (Crossing criterion). Suppose Equation (1.1) is known for s ≤ .84. If it fails for some s > .84, then for the same function there is a parameter .84 ≤ s < 1 for which b = h − 1 + s, E(d) ≤ K. (4.4)” · Show in paper

Calibrated energy comparison: using the change of variable F(0)=0,F′=H−3/2F(0)=0, F'=H^{-3/2} and a calibrated edge cost Φ(v)\Phi(v) to lower-bound E(d)\mathcal{E}(d) and control the spread of the first Fourier level.

Source excerpts

“Lemma 5.2 (Calibrated edge comparison). For every coordinate edge, Did Di (d/H(d)) ≥ (Dig)2 + Φ((Dig)2). (5.5)” · Show in paper

Even–odd Fourier decomposition and angular coordinates: separating even and odd parts of d=Tρfd = T_\rho f and g=F(d)g = F(d) and using angular coordinates β=arcsin⁡m\beta = \arcsin m, t=(arcsin⁡d−β)/2t = (\arcsin d - \beta)/2 to certify pointwise bounds.

Source excerpts

“These are the projections onto the even and odd Fourier degrees. Every nonconstant even degree is at least two, whereas an odd degree other than one is at least three.” · Show in paper

“Introduce the midpoint and signed half-difference of the two angles: β = arcsin m, t = (arcsin d − β)/2, c = t + β.” · Show in paper

Forward and reverse cube norm inequalities: deriving hypercontractive moment bounds from the cube logarithmic Sobolev inequality via Gross's semigroup method to bound EU\mathbb{E}\sqrt{U} and EUk+1/2\mathbb{E}U^{k+1/2}.

Source excerpts

“The forward inequality belongs to the classical hypercontractive theory of Bonami and Beckner [Bon70, Bec75]; the reverse inequality is due to Borell [Bor82]. We derive both from the cube logarithmic Sobolev inequality using Gross’s semigroup method [Gro75].” · Show in paper

Exact rational and interval arithmetic certification: using tensor Bernstein basis enclosures and outward-rounded integer interval arithmetic with derivative enclosures to certify fixed-dimension scalar inequalities.

Source excerpts

“All constants in the certificates are rational; a terminating decimal denotes the corresponding rational number exactly. This appendix explains the common sign-certification rules.” · Show in paper