OctoInformBeta

OpenAI preprint, September 2026 · §3. Probability bounds for the cells

§3: Proof of Lemma 3.1: Centroid norms, cone translations and Gaussian quantiles give lower and upper bounds for the loss

Deletion loss constrains optimal cell probabilities.

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

Deleting a centroid from an optimal Gaussian partition decreases the support function of its centroid family. The Gaussian average of this decrease is the deletion loss. Its bounds constrain the probability of a cell in terms of its centroid norm.

Let γd\gamma_d be standard Gaussian measure on ℝd\mathbb R^d, with mean zero and identity covariance.✦ A Borel Gaussian partition A=(A1,…,Ak)A=(A_1,\ldots,A_k) is a family of Borel sets such that γd\gamma_d-almost every point belongs to exactly one cell.✦ Empty cells are allowed. The unnormalized Gaussian centroid, cell probability and centroid energy are zi=z(Ai)=∫Aixdγd(x),Pi=γd(Ai),F(A)=∑i=1k∥zi∥2.z_i=z(A_i)=\int_{A_i}x\,d\gamma_d(x),\qquad P_i=\gamma_d(A_i),\qquad F(A)=\sum_{i=1}^k\|z_i\|^2.(1) An active label ii of a Borel Gaussian partition AA is a cell index with Pi>0P_i>0. The active count of AA is the number of its active labels.✦ An optimal Borel Gaussian partition A=(A1,…,Ak)A=(A_1,\ldots,A_k) of ℝd\mathbb R^d is a partition that maximizes FF among Borel Gaussian partitions of ℝd\mathbb R^d with kk labels.✦ A minimal optimal Borel Gaussian partition A=(A1,…,Ak)A=(A_1,\ldots,A_k) of ℝd\mathbb R^d is an optimal partition with the least active count among optimal Borel Gaussian partitions of ℝd\mathbb R^d with kk labels.✦

Write C=F(A)C=F(A). When C>0C>0, the normalized centroid lengths associated with (1) and the propeller constant are ri=∥zi∥C,∑iri2=∑iPi=1,B=322π,B2=98π.r_i=\frac{\|z_i\|}{\sqrt C},\qquad \sum_i r_i^2=\sum_i P_i=1,\qquad B=\frac{3}{2\sqrt{2\pi}},\qquad B^2=\frac{9}{8\pi}.(2) For k≥2k\ge2, put α=k/(k−1)\alpha=k/(k-1). The support function after deletion of ii and the deletion loss are Mi(g)=maxj≠i⟨zj,g⟩,Di=∫ℝdmax⁡{⟨zi,g⟩−Mi(g),0}dγd(g).M_i(g)=\max_{j\ne i}\langle z_j,g\rangle,\qquad D_i=\int_{\mathbb R^d} \max\{\langle z_i,g\rangle-M_i(g),0\}\,d\gamma_d(g).(3)

For an indexed family v=(vj)v=(v_j) in a real inner product space EE, its positive halfspace cone K(v)K(v) consists of the vectors whose inner product with every vjv_j is nonnegative. For a∈Ea\in E, its translated cone K(v)−aK(v)-a consists of the vectors yy for which a+y∈K(v)a+y\in K(v), and its translated Gaussian probability Qv(a)Q_v(a) is the Gaussian measure of that set; (4) writes these definitions for E=ℝdE=\mathbb R^d and γ=γd\gamma=\gamma_d. K(v)={y:⟨vj,y⟩≥0 for every j},K(v)−a={y:a+y∈K(v)},Qv(a)=γd(K(v)−a),Ki=K((zi−zj)j≠i).\begin{aligned} K(v)&=\{y:\langle v_j,y\rangle\ge0\text{ for every }j\},\\ K(v)-a&=\{y:a+y\in K(v)\},\qquad Q_v(a)=\gamma_d(K(v)-a),\\ K_i&=K\bigl((z_i-z_j)_{j\ne i}\bigr). \end{aligned}(4) For such a cone, z(K(v))z(K(v)) denotes its unnormalized Gaussian centroid.

The unnormalized Gaussian density ρ\rho, its upper tail TT and the Gaussian normalizing constant cc are ρ(x)=e−x2/2,T(x)=∫x∞ρ(t)dt,c=(2π)−1/2.\rho(x)=e^{-x^2/2},\qquad T(x)=\int_x^\infty\rho(t)\,dt,\qquad c=(2\pi)^{-1/2}.(5) The standard Gaussian density φ\varphi, distribution Φ\Phi and upper tail pp associated with (5) are φ(x)=cρ(x),Φ(x)=∫−∞xφ(t)dt,p(x)=cT(x)=Φ(−x).\varphi(x)=c\rho(x),\qquad \Phi(x)=\int_{-\infty}^x\varphi(t)\,dt,\qquad p(x)=cT(x)=\Phi(-x).(6) The Gaussian quantile qq is the inverse of the Gaussian cumulative distribution function (CDF) Φ\Phi on interior probabilities, extended by zero outside that interval: q(t)={Φ−1(t),0<t<1,0,t∉(0,1).q(t)= \begin{cases} \Phi^{-1}(t),&0<t<1,\\ 0,&t\notin(0,1). \end{cases}(7) The inverse Mills ratio λ\lambda is the ratio of the Gaussian density to its upper tail, as given in (8). With GG in the paper’s convention and qq a real quantile value, the reflected argument is x=−qx=-q, and the scalar Gaussian loss is λ(x)=ρ(x)T(x)=φ(x)Φ(−x),G(q)=φ(q)(qΦ(q)+φ(q))Φ(q)2,G(−x)=λ(x)(λ(x)−x),loss⁡(x)=p(x)2G(−x).\begin{aligned} \lambda(x)&=\frac{\rho(x)}{T(x)}=\frac{\varphi(x)}{\Phi(-x)},\\ G(q)&=\frac{\varphi(q)\bigl(q\Phi(q)+\varphi(q)\bigr)}{\Phi(q)^2}, \qquad G(-x)=\lambda(x)\bigl(\lambda(x)-x\bigr),\\ \operatorname{loss}(x)&=p(x)^2G(-x). \end{aligned}(8) The function GG in (8) is the inverse Mills derivative in the paper’s convention.

The Claim

Theorem 1. Let k≥2k\ge2 and let AA be an optimal Borel Gaussian partition of ℝd\mathbb R^d. Its deletion loss from (3) satisfies C−CC−α∥zi∥2≤Di(1≤i≤k).C-\sqrt C\sqrt{C-\alpha\|z_i\|^2}\le D_i \qquad(1\le i\le k).(9)✦

Let (y1,…,ym)(y_1,\ldots,y_m) be a finite family in a finite-dimensional real Euclidean space with sum zero and ⟨yi,yj⟩<0\langle y_i,y_j\rangle<0 for distinct indices. For each ii there is a unit gap translation direction satisfying h∈span⁡{y1,…,ym},⟨h,yi−yj⟩=1(j≠i),⟨h,yi⟩=m−1m.\begin{gathered} h\in\operatorname{span}\{y_1,\ldots,y_m\},\\ \langle h,y_i-y_j\rangle=1\quad(j\ne i),\qquad \langle h,y_i\rangle=\frac{m-1}{m}. \end{gathered}(10)✦

For the cone probability in (4) and every h∈ℝdh\in\mathbb R^d, the probability along the translated line has derivative dduQv(−uh)|u=0=−⟨h,z(K(v))⟩.\left.\frac{d}{du}Q_v(-uh)\right|_{u=0} =-\langle h,z(K(v))\rangle.(11)✦ Suppose there is e∈ℝde\in\mathbb R^d with ⟨vj,e⟩>0\langle v_j,e\rangle>0 for every jj. The quantile probability is concave: q(Qv((1−t)a+tb))≥(1−t)q(Qv(a))+tq(Qv(b))(a,b∈ℝd,0≤t≤1).q\bigl(Q_v((1-t)a+tb)\bigr) \ge (1-t)q(Q_v(a))+tq(Q_v(b)) \quad(a,b\in\mathbb R^d,\ 0\le t\le1).(12)✦ For every h∈ℝdh\in\mathbb R^d and u∈ℝu\in\mathbb R, its supporting tangent gives Qv(−uh)≤Φ(q(Qv(0))−⟨h,z(K(v))⟩φ(q(Qv(0)))u).Q_v(-uh)\le \Phi\!\left(q(Q_v(0))- \frac{\langle h,z(K(v))\rangle}{\varphi(q(Q_v(0)))}u\right).(13)✦

Suppose now that AA is minimal optimal, C>0C>0, and every cell has positive probability. Set qi=q(Pi)q_i=q(P_i), using (7). Then Di≤αφ(qi)(qiPi+φ(qi)).D_i\le\alpha\varphi(q_i) \bigl(q_iP_i+\varphi(q_i)\bigr).(14)✦ If C>B2C>B^2, the normalization (2) and the scalar loss (8) satisfy each of the following constraints: ∃x≥0:p(x)=Pi,Cri21+1−αri2≤loss⁡(x),\exists x\ge0:\quad p(x)=P_i,\qquad \frac{Cr_i^2}{1+\sqrt{1-\alpha r_i^2}} \le\operatorname{loss}(x),(15)✦ ∃x≥0:p(x)=Pi,B2ri21+1−ri2≤loss⁡(x).\exists x\ge0:\quad p(x)=P_i,\qquad \frac{B^2r_i^2}{1+\sqrt{1-r_i^2}} \le\operatorname{loss}(x).(16)✦

In the paper, the result reads: for the extremizer with kk active cells, fix ii, let Xj=⟨zj,g⟩X_j=\langle z_j,g\rangle and α=k/(k−1)\alpha=k/(k-1); the deletion loss is at least C(1−1−αri2)C(1-\sqrt{1-\alpha r_i^2}); there is hh in the centroid span with ⟨h,zi−zj⟩=1\langle h,z_i-z_j\rangle=1 for all j≠ij\ne i and ⟨h,zi⟩=1/α\langle h,z_i\rangle=1/\alpha; if pi(u)=γd(Ki+uh)p_i(u)=\gamma_d(K_i+uh), then pi′(0)=−1/αp_i'(0)=-1/\alpha and Φ−1(pi(u))\Phi^{-1}(p_i(u)) is concave; integrating its supporting tangent gives deletion loss at most αφ(qi)(qiΦ(qi)+φ(qi))\alpha\varphi(q_i)(q_i\Phi(q_i)+\varphi(q_i)), where qi=Φ−1(Pi)q_i=\Phi^{-1}(P_i); hence Pi2G(qi)≥Cri2/(1+1−αri2)≥B2ri2/(1+1−ri2)P_i^2G(q_i)\ge Cr_i^2/(1+\sqrt{1-\alpha r_i^2}) \ge B^2r_i^2/(1+\sqrt{1-r_i^2}).

What Is Checked

The partition bounds (9), (14), (15) and (16) are stated over Borel Gaussian partitions, with minimal optimality and positive cell probabilities where specified. The translation statement (10) concerns a finite family with negative pairwise inner products and zero sum. The cone statements (11), (12) and (13) concern intersections of positive halfspaces, with a common strictly positive direction for the quantile and tangent bounds.

The Gaussian CDF in (6) is strictly increasing✦ and has range (0,1)(0,1).✦