OctoInformBeta

OpenAI preprint, September 2026 · §3. From weighted moments to an embedding

Lemma 3.1: Convex selection and bounded gradient samples under a sufficient tail inequality

From weighted moments to sampled embeddings.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Weighted control of gradient moments concerns averages over pairs of points. Coordinate embeddings require control of every pair at the same time, with a common scale.

Let EE and II be finite sets of edges and vertices. For endpoint maps s,t:E→Is,t:E\to I, the incidence matrix B∈ℝE×IB\in\mathbb R^{E\times I} is defined by (1). Bei=𝟏s(e)=i−𝟏t(e)=i.B_{ei}=\mathbf 1_{s(e)=i}-\mathbf 1_{t(e)=i}.(1)✦ For endpoint maps s,t:E→Is,t:E\to I and real edge scales δ∈ℝE\delta\in\mathbb R^E, the normalized gradient matrix A∈ℝE×IA\in\mathbb R^{E\times I} is obtained by multiplying the incidence matrix BB on the left by the diagonal matrix with entries δe−1\delta_e^{-1}, as in (2). A=diag⁡(δe−1)B.A=\operatorname{diag}(\delta_e^{-1})B.(2)✦ For any real matrix A∈ℝE×IA\in\mathbb R^{E\times I}, write V=AℝIV=A\mathbb R^I for its space of gradients.

For nn labelled points, the standard pair index EnE_n is the set in (3), with endpoints s(i,j)=is(i,j)=i and t(i,j)=jt(i,j)=j. En={(i,j):1≤i<j≤n}.E_n=\{(i,j):1\le i<j\le n\}.(3)✦

For a real exponent pp and vectors x,y∈ℝdx,y\in\mathbb R^d, the coordinate distance ρp(x,y)\rho_p(x,y) is the quantity in (4). ρp(x,y)=(∑a=1d|xa−ya|p)1/p.\rho_p(x,y)=\left(\sum_{a=1}^d|x_a-y_a|^p\right)^{1/p}.(4)✦

A strictly positive probability ww on a nonempty finite set EE is a vector in the set 𝒲E\mathcal W_E of (5). 𝒲E={w∈ℝE:we>0for every e,∑e∈Ewe=1}.\mathcal W_E=\left\{w\in\mathbb R^E: w_e>0\ \text{for every }e,\quad \sum_{e\in E}w_e=1\right\}.(5)

The weighted deviation ℰw(m;b)\mathcal E_w(m;b) of a moment vector m∈ℝEm\in\mathbb R^E from a level b∈ℝb\in\mathbb R, with respect to a strictly positive probability ww on EE, is the real number in (6). ℰw(m;b)=∑e∈Ewe|me−b|.\mathcal E_w(m;b)=\sum_{e\in E}w_e|m_e-b|.(6)

For a measurable map F:Ω→ℝEF:\Omega\to\mathbb R^E on a probability space (Ω,μ)(\Omega,\mu) and a probability measure ν\nu on ℝE\mathbb R^E, the ppth moment vectors mp(F;μ)m_p(F;\mu) and mp(ν)m_p(\nu) are vectors in ℝE\mathbb R^E given by (7) whenever the integrals exist. mp(F;μ)e=∫Ω|F(ω)e|pdμ(ω),mp(ν)e=∫ℝE|ge|pdν(g).m_p(F;\mu)_e=\int_\Omega |F(\omega)_e|^p\,d\mu(\omega), \qquad m_p(\nu)_e=\int_{\mathbb R^E}|g_e|^p\,d\nu(g).(7)

For M≥0M\ge0 and ε>0\varepsilon>0, an admissible sample size for (E,M,ε)(E,M,\varepsilon) is a positive integer dd for which M>0M>0 and the sampling condition (8) holds. 2|E|exp⁡(−(dε)22d(M/2)2)<1.2|E|\exp\left(-\frac{(d\varepsilon)^2}{2d(M/2)^2}\right)<1.(8)

The Claim

Theorem 1. Let EE be a nonempty finite set and let b∈ℝb\in\mathbb R.

Convex selection. Let C⊆ℝEC\subseteq\mathbb R^E be convex and let ε>0\varepsilon>0. Suppose that for every w∈𝒲Ew\in\mathcal W_E there is m∈Cm\in C with ℰw(m;b)≤ε\mathcal E_w(m;b)\le\varepsilon. There is m∈Cm\in C satisfying (9). |me−b|<2ε(e∈E).|m_e-b|<2\varepsilon\qquad(e\in E).(9)✦

Empirical moments. Let M≥0M\ge0, S⊆[0,M]ES\subseteq[0,M]^E and ε>0\varepsilon>0. Suppose that for every w∈𝒲Ew\in\mathcal W_E there is mm in the closed convex hull of SS with ℰw(m;b)≤ε\mathcal E_w(m;b)\le\varepsilon. For every admissible sample size dd for (E,M,ε)(E,M,\varepsilon), there are u1,…,ud∈Su^1,\ldots,u^d\in S satisfying (10). |1d∑a=1duea−b|<3ε(e∈E).\left|\frac1d\sum_{a=1}^d u^a_e-b\right|<3\varepsilon \qquad(e\in E).(10)✦

Gradient maps. Let A∈ℝE×IA\in\mathbb R^{E\times I}, p>0p>0, K≥0K\ge0 and ε>0\varepsilon>0. Fix a probability space (Ω,μ)(\Omega,\mu). Suppose that for every w∈𝒲Ew\in\mathcal W_E there is a measurable map Fw:Ω→VF_w:\Omega\to V such that |Fw(ω)e|≤K|F_w(\omega)_e|\le K for every ω,e\omega,e and ℰw(mp(Fw;μ);b)≤ε\mathcal E_w(m_p(F_w;\mu);b)\le\varepsilon. For every admissible sample size dd for (E,Kp,ε)(E,K^p,\varepsilon), there are vertex labels x1,…,xd∈ℝIx^1,\ldots,x^d\in\mathbb R^I satisfying (11). |1d∑a=1d|(Axa)e|p−b|<3ε(e∈E).\left|\frac1d\sum_{a=1}^d |(Ax^a)_e|^p-b\right|<3\varepsilon \qquad(e\in E).(11)✦

Gradient measures. Under the same conditions on A,p,K,εA,p,K,\varepsilon, suppose that for every w∈𝒲Ew\in\mathcal W_E there is a probability measure νw\nu_w on ℝE\mathbb R^E such that a vector gg drawn according to νw\nu_w satisfies g∈Vg\in V and |ge|≤K|g_e|\le K for every ee, almost surely, and ℰw(mp(νw);b)≤ε\mathcal E_w(m_p(\nu_w);b)\le\varepsilon. For every admissible sample size dd for (E,Kp,ε)(E,K^p,\varepsilon), there are x1,…,xd∈ℝIx^1,\ldots,x^d\in\mathbb R^I satisfying (12). |1d∑a=1d|(Axa)e|p−b|<3ε(e∈E).\left|\frac1d\sum_{a=1}^d |(Ax^a)_e|^p-b\right|<3\varepsilon \qquad(e\in E).(12)✦

Sampled vertex labels. For any nn, take E=EnE=E_n and let AA be the normalized gradient matrix for positive lengths δe\delta_e. Let p>0p>0, D≥0D\ge0, b−3ε>0b-3\varepsilon>0 and b+3ε≤Dp(b−3ε)b+3\varepsilon\le D^p(b-3\varepsilon). Suppose that d≥1d\ge1 and that x1,…,xd∈ℝnx^1,\ldots,x^d\in\mathbb R^n satisfy the moment bound in (11). The coordinate map ff from the nn labelled vertices to ℝd\mathbb R^d is defined by f(i)=(xia)a=1df(i)=(x_i^a)_{a=1}^d. There is σ>0\sigma>0 such that (13) holds. σδij≤ρp(f(i),f(j))≤Dσδij(1≤i<j≤n).\sigma\delta_{ij}\le\rho_p(f(i),f(j))\le D\sigma\delta_{ij} \qquad(1\le i<j\le n).(13)✦

Sampling probability. Let M>0M>0, ε≥1\varepsilon\ge1 and let n,Nn,N be integers with n≥2n\ge2 and 1≤N≤n21\le N\le n^2. Set H=4log⁡nH=4\log n and d=⌈M2(H+1)⌉+1d=\lceil M^2(H+1)\rceil+1. The estimate is (14). 2Nexp⁡(−(dε)22d(M/2)2)<1.2N\exp\left(-\frac{(d\varepsilon)^2}{2d(M/2)^2}\right)<1.(14)✦

In the paper, the result reads: in the finite coordinate setting, if 0<η<1/30<\eta<1/3 and b,K≥1b,K\ge1, and every w∈𝒲Enw\in\mathcal W_{E_n} admits a random normalized gradient F∈VF\in V with ∥F∥∞≤K\|F\|_\infty\le K almost surely and ∑ewe|𝔼|Fe|p−b|≤ηb\sum_e w_e|\mathbb E|F_e|^p-b|\le\eta b, with the same b,Kb,K for every ww, then the points embed into ℓpd\ell_p^d with distortion at most ((1+3η)/(1−3η))1/p((1+3\eta)/(1-3\eta))^{1/p} and d≤⌈Cmax⁡{1,K2p/(η2b2)}log⁡(2n)⌉d\le\lceil C\max\{1,K^{2p}/(\eta^2b^2)\}\log(2n)\rceil for an absolute constant CC.

What Is Checked

The convex selection and sampling statements concern finite real coordinate spaces and probability moments; the embedding statement concerns positive pairwise lengths and the coordinate distance (4).