OctoInformBeta

OpenAI preprint, September 2026 · §6. The range 1 < p < 2

§6 (proof of Theorem 1.1): clipping and the weighted-moment contract: The dimension bound has exponent 2−p2-p for 1<p<21<p<2

Clipped stable gradients control weighted moments.

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

For 1<p<21<p<2, clipping a stable random gradient allows its coordinates to be bounded while controlling the error in their ppth moments with prescribed edge weights. The dimension question concerns realizations of finite subsets of real LpL_p spaces in real coordinate spaces.

For p>1p>1, the coordinate distance ρp\rho_p on ℝd\mathbb R^d is given by (1): ρp(u,v)=(∑a=1d|ua−va|p)1/p.\rho_p(u,v)=\left(\sum_{a=1}^d |u_a-v_a|^p\right)^{1/p}.(1)✦ An admissible dimension dd for nn points and distortion DD is a nonnegative integer such that every injective family x1,…,xnx_1,\ldots,x_n in every real Lp(Ω,μ)L_p(\Omega,\mu) admits y1,…,yn∈ℝdy_1,\ldots,y_n\in\mathbb R^d and a scale s>0s>0 satisfying (2): s∥xi−xj∥p≤ρp(yi,yj)≤Ds∥xi−xj∥p(1≤i,j≤n).s\|x_i-x_j\|_p\le \rho_p(y_i,y_j) \le Ds\|x_i-x_j\|_p\qquad(1\le i,j\le n).(2)✦ The universal dimension dp(n,D)d_p(n,D) for nn points and distortion DD is the infimum in the nonnegative integers of the admissible dimensions for nn points and distortion DD.

Normalized Gradients and Clipping

For the gradient estimates, let UU be a finite vertex set with N=|U|≥2N=|U|\ge2, let EE be a nonempty finite edge set, and let src,dst:E→U\mathrm{src},\mathrm{dst}:E\to U be endpoint maps. Assume that every vertex is incident to an edge and every pair of distinct vertices is joined by an edge in one of the two orientations. Fix positive edge scales δe\delta_e and positive weights λe\lambda_e with ∑e∈Eλe=1\sum_{e\in E}\lambda_e=1.

The incidence matrix B∈ℝE×UB\in\mathbb R^{E\times U} and normalized gradient matrix G∈ℝE×UG\in\mathbb R^{E\times U} are defined in (3); the normalized-gradient space VV is the image of GG: Beu=𝟏{src(e)=u}−𝟏{dst(e)=u},G=diag⁡(δe−1)B,V=GℝU,H=4log⁡N.B_{eu}=\mathbf 1_{\{\mathrm{src}(e)=u\}} -\mathbf 1_{\{\mathrm{dst}(e)=u\}},\qquad G=\operatorname{diag}(\delta_e^{-1})B,\qquad V=G\mathbb R^U,\qquad H=4\log N.(3)

For a scalar probability measure μ\mu on ℝ\mathbb R, write μˆ(t)=∫ℝeitudμ(u)\widehat\mu(t)=\int_{\mathbb R}e^{itu}\,d\mu(u) for its characteristic function. For a scalar probability measure μ\mu on ℝ\mathbb R and a>0a>0, the capped ppth moment bμ(a)b_\mu(a) of μ\mu is the integral in (4): bμ(a)=∫ℝmin⁡{|u|,a}pdμ(u).b_\mu(a)=\int_{\mathbb R}\min\{|u|,a\}^{p}\,d\mu(u).(4)

Definition 1. For real aa, the clipping function clip⁡a:ℝ→ℝ\operatorname{clip}_a:\mathbb R\to\mathbb R is defined by (5): clip⁡a(u)=max⁡{−a,min⁡{u,a}}.\operatorname{clip}_a(u)=\max\{-a,\min\{u,a\}\}.(5)✦ For real aa and y∈ℝEy\in\mathbb R^E, the coordinatewise clipping [y]a[y]_a of yy is the vector [y]a=(clip⁡a(ye))e∈E[y]_a=(\operatorname{clip}_a(y_e))_{e\in E}.

The Claim

Theorem 1. Let μ\mu be a probability measure on ℝ\mathbb R. Suppose p>1p>1, k≥0k\ge0 and a≥1a\ge1, and assume that μ{u:|u|>t}≥kt−p\mu\{u:|u|>t\}\ge kt^{-p} for every t≥1t\ge1. The logarithmic moment lower bound is (6): kplog⁡a≤bμ(a).kp\log a\le b_\mu(a).(6)✦

Suppose now that 1<p<21<p<2 and c>0c>0, with Re⁡μˆ(t)=exp⁡(−c|t|p)\operatorname{Re}\widehat\mu(t)=\exp(-c|t|^p) for every real tt. Let (Ω,ν)(\Omega,\nu) be a probability space and Y:Ω→VY:\Omega\to V a measurable map whose every coordinate has law μ\mu. For every T,a>0T,a>0, there is a measurable map F:Ω→VF:\Omega\to V satisfying the retraction moment bound (7): |Fe(ω)|≤HT(ω∈Ω,e∈E),∑e∈Eλe|∫Ω|Fe|pdν−bμ(a)|≤pap−1H(2c2p)(1+1p−1)T1−p+96cap−2T2−p.\begin{aligned} |F_e(\omega)|&\le HT &&(\omega\in\Omega,\ e\in E),\\ \sum_{e\in E}\lambda_e \left|\int_\Omega |F_e|^p\,d\nu-b_\mu(a)\right| &\le pa^{p-1}H(2c\,2^p) \left(1+\frac1{p-1}\right)T^{1-p} +96c\,a^{p-2}T^{2-p}. \end{aligned}(7)✦

Assume instead that μˆ(t)=exp⁡(−c|t|p)\widehat\mu(t)=\exp(-c|t|^p) for every real tt. Let II be a finite index set and let gi∈Vg_i\in V, for i∈Ii\in I, satisfy ∑i∈I|gi(e)|p=1\sum_{i\in I}|g_i(e)|^p=1 for every e∈Ee\in E. For each T>0T>0, there is a measurable map F:ℝI→VF:\mathbb R^I\to V satisfying the weighted stable gradient bound (8), where μI\mu^I is the product probability measure: |Fe(x)|≤HT(x∈ℝI,e∈E),∑e∈Eλe|∫ℝI|Fe(x)|pdμI(x)−bμ(T/H)|≤[p(2c2p)(1+1p−1)+96c]H2−p.\begin{aligned} |F_e(x)|&\le HT &&(x\in\mathbb R^I,\ e\in E),\\ \sum_{e\in E}\lambda_e \left|\int_{\mathbb R^I}|F_e(x)|^p\,d\mu^I(x)-b_\mu(T/H)\right| &\le\left[p(2c\,2^p)\left(1+\frac1{p-1}\right)+96c\right]H^{2-p}. \end{aligned}(8)✦

For every 1<p<21<p<2 and D>1D>1, there is a real constant CC such that the universal dimension satisfies (9): dp(n,D)≤exp⁡(C(logn)2−p)(n≥2).d_p(n,D)\le\exp\!\left(C(\log n)^{2-p}\right) \qquad(n\ge2).(9)✦

In the paper, the result reads: for an error parameter η\eta and constants cpc_p, CpC_p and Ap,ηA_{p,\eta}, with Hpap=4log⁡(2n)H_{\mathrm{pap}}=4\log(2n), let PP be the controlled retraction and let σe\sigma_e be the paper’s weights; for T>1T>1 let F=P([Y]T)F=P([Y]_T), take a=T/Hpap≥2a=T/H_{\mathrm{pap}}\ge2 and b=𝔼min⁡{|Ye|,a}pb=\mathbb E\min\{|Y_e|,a\}^p; then ∥F∥∞≤HpapT\|F\|_\infty\le H_{\mathrm{pap}}T, b≥cplog⁡ab\ge c_p\log a, and ∑eσe|𝔼|Fe|p−b|≤CpHpap2−p\sum_e\sigma_e|\mathbb E|F_e|^p-b|\le C_pH_{\mathrm{pap}}^{2-p}, while choosing T=exp⁡(Ap,ηHpap2−p)T=\exp(A_{p,\eta}H_{\mathrm{pap}}^{2-p}) gives b≥1b\ge1 and λ\lambda-weighted error at most ηb\eta b, with K=HpapTK=H_{\mathrm{pap}}T and log⁡K=Op,η((log⁡n)2−p)\log K=O_{p,\eta}((\log n)^{2-p}).

What Is Checked

The moment statements concern scalar probability laws and finite normalized-gradient spaces with positive edge scales and positive weights of total mass one, while the universal dimension statement concerns every injective finite family in every real LpL_p space.