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

Counterexamples to the duality conjecture for metric entropy

For every a,b≥1a, b \ge 1, there are a positive integer nn and an origin-symmetric convex body K⊂RnK \subset \mathbb{R}^n such that, with L=[−1,1]nL = [-1, 1]^n, log⁡N(K,L)>blog⁡N(L∘,a−1K∘)\log N(K, L) > b \log N(L^\circ, a^{-1} K^\circ), disproving Pietsch's dimension-free duality conjecture for metric entropy.

For every A,C≥1A, C \ge 1, there are an integer n≥1n \ge 1 and an origin-symmetric convex body K⊂RnK \subset \mathbb{R}^n such that, with L=[−1,1]nL = [-1, 1]^n, log⁡N(K,L)>Clog⁡M^(K,L/A)\log N(K, L) > C \log \widehat{M}(K, L/A), separating ordinary covering entropy from convexified-packing entropy.

Given finite nonempty sets X,YX, Y and real functions gy:X→Rg_y: X \to \mathbb{R} (y∈Yy \in Y) such that ∥Rx−Rx′∥∞≥1\|R_x - R_{x'}\|_\infty \ge 1 for all distinct x,x′∈Xx, x' \in X and F={fλ:∥λ∥1≤1}\mathcal{F} = \{f_\lambda : \|\lambda\|_1 \le 1\} has a uniform ε\varepsilon-approximation list of size MM, for any t>0t > 0 the bodies K=3absconv⁡{Rx:x∈X}+tB∞YK = 3 \operatorname{absconv}\{R_x : x \in X\} + t B_\infty^Y and L=B∞YL = B_\infty^Y are origin-symmetric compact convex bodies with nonempty interior in RY\mathbb{R}^Y satisfying N(K,L)≥∣X∣N(K, L) \ge |X| and N(L∘,(6ε+2t)K∘)≤MN(L^\circ, (6\varepsilon + 2t) K^\circ) \le M.

Under the partition hypotheses (3.1)-(3.3), there is a finite list A\mathcal{A} of real-valued functions on XX of cardinality QQ with log⁡Q≤hslog⁡q+Ch,θ,u\log Q \le h s \log q + C_{h,\theta,u} such that every f∈F+f \in \mathcal{F}_+ has an approximant A∈AA \in \mathcal{A} satisfying ∥f−A∥∞,X≤3θ\|f - A\|_{\infty, X} \le 3\theta.

With the notation of Proposition 3.2, F=absconv⁡{gy:y∈Y}\mathcal{F} = \operatorname{absconv}\{g_y : y \in Y\} has a uniform 6θ6\theta-approximation list of at most Q2Q^2 functions.

For 0<θ<10 < \theta < 1, positive integers r,hr, h, w=2Dhw = 2 D_h, u=⌈hw/θ⌉u = \lceil h w / \theta \rceil, and prime p>max⁡{h,h2u2h}p > \max\{h, h^2 u^{2h}\}, there exist t1,…,tu∈E=Fprt_1, \dots, t_u \in E = \mathbb{F}_p^r such that for every nonzero Z∈Sym⁡h(E∗)Z \in \operatorname{Sym}^h(E^*), there is a set T⊆[u]T \subseteq [u] with ∣[u]∖T∣≤θu|[u] \setminus T| \le \theta u for which Z(ti1,…,tih)≠0Z(t_{i_1}, \dots, t_{i_h}) \neq 0 for all (i1,…,ih)∈Th(i_1, \dots, i_h) \in T^h.

With the parameters and directions of Proposition 4.2, X=Sym⁡h(E∗)X = \operatorname{Sym}^h(E^*), Li(x)=x(ti,⋅,…,⋅)L_i(x) = x(t_i, \cdot, \dots, \cdot), and T={T⊆[u]:∣[u]∖T∣≤θu}\mathcal{T} = \{T \subseteq [u] : |[u] \setminus T| \le \theta u\}, we have ∣X∣=m=pDh|X| = m = p^{D_h}, each LiL_i has at most q=pDh−1q = p^{D_{h-1}} realized labels, every pair of distinct x,y∈Xx, y \in X has some T∈TT \in \mathcal{T} with dT(x,y)>hd_T(x, y) > h, and consequently ∥Rx−Ry∥∞=1\|R_x - R_y\|_\infty = 1 for x≠yx \neq y.

Methods

Matrix-to-body conversion: constructing origin-symmetric convex bodies K=3absconv⁡{Rx:x∈X}+tB∞YK = 3 \operatorname{absconv}\{R_x : x \in X\} + t B_\infty^Y and L=B∞YL = B_\infty^Y from a real matrix with sup-norm separated rows and a small uniform approximation list for its absolutely convex column hull.

Source excerpts

“For t > 0, set K = 3 absconv{R_x : x in X} + t B_\infty^Y, L = B_\infty^Y.” · Show in paper

Uniform compression from partitions: approximating convex combinations of logarithmic graph-distance profiles by selecting a common partition index, greedily choosing boundedly many pivots at each distance level, replacing pivots by fixed label representatives, and rounding grouped weights.

Source excerpts

“For a pivot z = zj,kz_{j,k}, retain only its label Li0L_{i_0}(z), and replace it by z' = \rho_{i_0}(Li0L_{i_0}(z)).” · Show in paper

“Round each weight down to a multiple of \delta = \theta / M_0, writing \tilde{w}_{j,k,T} = \delta \lfloor wj,k,Tw_{j,k,T} / \delta \rfloor.” · Show in paper

Finite-field partition construction: using contractions of symmetric hh-linear forms over Fpr\mathbb{F}_p^r along probabilistically chosen directions to obtain partitions with few labels whose graphs separate all pairs of forms.

Source excerpts

“With the parameters and directions of Proposition 4.2, let X = Sym^h(E^*), L_i(x) = x(t_i, ., ..., .), and let T = {T subset [u] : |[u] \setminus T| <= \theta u}.” · Show in paper