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

Average sensitivity of polynomial threshold functions

For every integer n≥1n \ge 1 and 1≤d≤n1 \le d \le n, if pp is a real multilinear polynomial of degree at most dd and f:{−1,1}n→{−1,1}f : \{-1, 1\}^n \to \{-1, 1\} is defined by f(x)=sgn⁡(p(x))f(x) = \operatorname{sgn}(p(x)) with sgn⁡(0)=1\operatorname{sgn}(0) = 1, then the average sensitivity of ff under the uniform law satisfies I(f)≤8dnI(f) \le 8d\sqrt{n}.

If U,VU, V are real random variables with the same distribution, finite mean mm, and finite variance σ2\sigma^2 such that V−U≤aV - U \le a almost surely for some a≥0a \ge 0, then E(U−V)2≤8aσ\mathbb{E}(U - V)^2 \le 8a\sigma.

For n≥1n \ge 1, Ω={−1,1}n\Omega = \{-1, 1\}^n, any positive weight w:Ω→(0,∞)w : \Omega \to (0, \infty), centered grading operator MM constructed from ww, and multiplication operator HH by h:Ω→{−1,1}h : \Omega \to \{-1, 1\}, the number of ordered equal-sign neighbor pairs Eh={(x,y)∈Ω2:ρ(x,y)=1,h(x)=h(y)}\mathcal{E}_h = \{(x, y) \in \Omega^2 : \rho(x, y) = 1, h(x) = h(y)\} satisfies ∣Eh∣≤2∥MH+HM∥HS2|\mathcal{E}_h| \le 2\|MH + HM\|_{\mathrm{HS}}^2.

For integers n≥1n \ge 1 and d≥0d \ge 0, if f=sgn⁡(p)f = \operatorname{sgn}(p) on {−1,1}n\{-1, 1\}^n for a real polynomial pp of degree at most dd with sgn⁡(0)=1\operatorname{sgn}(0) = 1, then the Boolean noise sensitivity satisfies NSη(f)≤Cdη\mathrm{NS}_\eta(f) \le C d \sqrt{\eta} for 0<η≤1/20 < \eta \le 1/2, where CC is an absolute constant.

For integers n,d≥1n, d \ge 1, let Cn,d\mathcal{C}_{n,d} be the class of degree-dd polynomial threshold functions on {−1,1}n\{-1, 1\}^n. For any distribution DD on {−1,1}n×{−1,1}\{-1, 1\}^n \times \{-1, 1\} with uniform first marginal, there is an absolute constant AA such that for 0<α,δ<10 < \alpha, \delta < 1, a learner using independent labeled samples from DD returns, with probability at least 1−δ1 - \delta, a Boolean hypothesis hh with P(X,Y)∼D{h(X)≠Y}≤OPT+α\mathbb{P}_{(X,Y)\sim D}\{h(X) \ne Y\} \le \mathrm{OPT} + \alpha in running time and sample size polynomial in (n+1)k(n+1)^k, 1/α1/\alpha, and log⁡(1/δ)\log(1/\delta), where k=min⁡{n,⌈Ad2α−2log⁡(4/α)⌉}k = \min\{n, \lceil A d^2 \alpha^{-2} \log(4/\alpha)\rceil\}.

Methods

Constructing a centered self-adjoint grading operator M = ∑_{k=0}^n (k − n/2)Π_k from nested polynomial subspaces K_k = √w V_k orthogonalized in the counting inner product, which preserves fixed squared Hilbert-Schmidt norm n2^n/4 and restricts coordinate multiplication to equal or adjacent grades.

Source excerpts

“Form the nested subspaces Kk = DVk, K−1 = {0}, Ek = Kk ∩ K⊥_{k−1} (0 ≤ k ≤ n).” · Show in paper

“Define the grading operator and its centered version by L = ∑_{k=0}^n kΠk, M = L − (n/2)Id.” · Show in paper

“ΠsZiΠr = 0 whenever |s − r| > 1.” · Show in paper

Random-bucketing reduction that maps an n-variable Boolean function f to a q-variable function g(z) = f(a_1 zb(1)z_{b(1)}, ..., a_n zb(n)z_{b(n)}) using independent uniform signs a_i and buckets b(i) ∈ {1, ..., q} to relate noise sensitivity NS_{1/q}(f) to average sensitivity I(g).

Source excerpts

“For an integer q ≥ 2, use the random-bucketing reduction of Diakonikolas, Raghavendra, Servedio, and Tan [3, Section 7.1, equation (14)]: choose independent uniform signs ai and independent uniform buckets b(i) ∈ {1, . . . , q}, and set g(z) = f(a1zb(1), . . . , anzb(n)), z ∈ {−1, 1}q.” · Show in paper

L1 polynomial regression over characters of degree at most k = min(n, ⌈A d^2 α−2α^{-2} log(4/α)⌉) via linear programming to minimize empirical absolute loss, followed by sorting-based thresholding, independent repetition, and validation.

Source excerpts

“On a training sample Z of size m, fit a polynomial P in these features by minimizing empirical absolute loss, then choose t ∈ [−1, 1] to minimize the empirical error of h = sgn(P − t). The fit is a linear program, and the threshold is found by sorting the fitted values.” · Show in paper