OctoInformBeta

OpenAI preprint, September 2026 · §2. Constructing the signed walk · §2.2

§2.2 (displayed): unclipped coordinates (unclipped-coordinates) and cancellation (feedback-cancellation): Points of good bodies whose coordinates are predictions plus signs, and contraction steps along which such points have Rtx=Rx+∑i<tεibiR_t x = Rx + \sum_{i<t}\varepsilon_i b_i

Feedback signs in good bodies and prefix cancellation.

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

Vectors b0,…,bn−1b_0, \dots, b_{n-1} in ℝd\mathbb{R}^d and signs ε0,…,εn−1∈{−1,1}\varepsilon_0, \dots, \varepsilon_{n-1} \in \{-1, 1\} give the signed walk of prefix sums ∑i<tεibi\sum_{i<t} \varepsilon_i b_i, for 0≤t≤n0 \le t \le n. Here the signs are read off one point xx of the coefficient space ℝΛ\mathbb{R}^\Lambda, the Euclidean space of real vectors indexed by a finite set Λ\Lambda. Each vector bib_i owns a coordinate ji∈Λj_i \in \Lambda, and its sign is the difference between xjix_{j_i} and a prediction mixm_i x, where mim_i is a linear functional on ℝΛ\mathbb{R}^\Lambda that vanishes on the standard basis vectors ejle_{j_l} with l≥il \ge i.

The point is sought in a convex body KK on which every prediction stays in the slab |mix|<1/4|m_i x| < 1/4. It is then fed to a linear filter started from a real matrix RR with dd rows and columns indexed by Λ\Lambda, whose state RtR_t after tt vectors changes once per vector, and the question is what RtxR_t x is.

Clipping and Good Bodies

The clip at 1/41/4 is the function clip:ℝ→ℝ\mathrm{clip}\colon \mathbb{R} \to \mathbb{R} given by clip(u)=max⁡(−14,min⁡(u,14)).\mathrm{clip}(u) = \max\bigl(-\tfrac14, \min(u, \tfrac14)\bigr).(1)✦

Let EE be a Euclidean space, L2(E)L^2(E) the complex space of square-integrable functions for Lebesgue measure, and ℱ\mathcal{F} the unitary Fourier transform on it. For a measurable real function φ\varphi on EE with |φ|≤1|\varphi| \le 1, the Fourier multiplier with multiplier φ\varphi is the bounded operator Tφ=ℱ−1MφℱT_\varphi = \mathcal{F}^{-1} M_\varphi \mathcal{F} on L2(E)L^2(E), with MφM_\varphi the multiplication by φ\varphi.✦ The heat operator of a measurable function w≥0w \ge 0 on EE is the Fourier multiplier Hw=Te−wH_w = T_{e^{-w}}.✦ The compressed heat operator of a measurable set D⊆ED \subseteq E and such a function ww is the operator PDHwPDP_D H_w P_D on L2(E)L^2(E), where PDP_D is the multiplication by the indicator of DD.✦

For nonnegative weights v=(vk)k∈Λv = (v_k)_{k \in \Lambda}, the Gaussian symbol of vv is the function on ℝΛ\mathbb{R}^\Lambda given by σv(ξ)=12∑k∈Λvk(2πξk)2.\sigma_v(\xi) = \frac12 \sum_{k \in \Lambda} v_k (2\pi \xi_k)^2 .(2)✦ A measurable set D⊆ℝΛD \subseteq \mathbb{R}^\Lambda satisfies the diagonal heat bound with constant cc if, for all nonnegative weights vv, the operator norm on L2(ℝΛ)L^2(\mathbb{R}^\Lambda) obeys ∥PDHσvPD∥≥e−(c/2)∑k∈Λvk.\bigl\| P_D H_{\sigma_v} P_D \bigr\| \ge e^{-(c/2) \sum_{k \in \Lambda} v_k} .(3)✦ A good convex body KK in ℝΛ\mathbb{R}^\Lambda is a nonempty, open, bounded, convex subset of ℝΛ\mathbb{R}^\Lambda that is symmetric, with −x∈K-x \in K for every x∈Kx \in K, and satisfies the diagonal heat bound with constant κ2=1/10000\kappa^2 = 1/10000.✦

Filter Steps

A filter step p=(C,b,j)p = (C, b, j) is a triple of a real d×dd \times d matrix CC, a vector b∈ℝdb \in \mathbb{R}^d and a column index j∈Λj \in \Lambda✦; it acts on a real matrix RR with dd rows and columns indexed by Λ\Lambda by p(R)=CR+bej𝖳,p(R) = CR + b e_j^{\mathsf T},(4)✦ where the column insertion bej𝖳b e_j^{\mathsf T} is the matrix with bb in column jj and zeros elsewhere. The run of steps p0,…,pn−1p_0, \dots, p_{n-1} on RR applies them in order, R0=RR_0 = R and Rt+1=pt(Rt)R_{t+1} = p_t(R_t).✦ The matrix RR acts on ℝΛ\mathbb{R}^\Lambda as the linear map x↦Rxx \mapsto Rx into ℝd\mathbb{R}^d✦, and a row rr indexed by Λ\Lambda acts as the linear functional x↦rx=∑k∈Λrkxkx \mapsto rx = \sum_{k \in \Lambda} r_k x_k✦.

The mass of a vector b∈ℝdb \in \mathbb{R}^d is |b|2=∑ibi2|b|^2 = \sum_i b_i^2.✦ The normalizer η(b)\eta(b) and the symmetric contraction CbC_b of a vector b∈ℝdb \in \mathbb{R}^d are the real number and the d×dd \times d matrix given by η(b)=11+1−|b|2,Cb=I−η(b)bb𝖳.\eta(b) = \frac{1}{1 + \sqrt{1 - |b|^2}}, \qquad C_b = I - \eta(b)\, b b^{\mathsf T}.(5) The raw predictor row of a matrix RR against bb is the row indexed by Λ\Lambda ρb(R)=η(b)b𝖳R.\rho_b(R) = \eta(b)\, b^{\mathsf T} R .(6)✦

The Claim

Theorem 1. (a) Let KK be a good convex body in ℝΛ\mathbb{R}^\Lambda, let j0,…,jn−1j_0, \dots, j_{n-1} be distinct coordinates in Λ\Lambda, and let m0,…,mn−1m_0, \dots, m_{n-1} be linear functionals on ℝΛ\mathbb{R}^\Lambda with mi(ejl)=0m_i(e_{j_l}) = 0 whenever i≤li \le l and with |mix|<1/4|m_i x| < 1/4 for every x∈Kx \in K and every ii. Then there are signs ε0,…,εn−1∈{−1,1}\varepsilon_0, \dots, \varepsilon_{n-1} \in \{-1, 1\} and a point x∈Kx \in K with xk=0x_k = 0 for every k∈Λk \in \Lambda outside {j0,…,jn−1}\{j_0, \dots, j_{n-1}\} and xji=mix+εi(0≤i<n).x_{j_i} = m_i x + \varepsilon_i \qquad (0 \le i < n).(7)✦

(b) Let p=(Cb,b,j)p = (C_b, b, j) be a filter step whose matrix is the symmetric contraction of its vector, let RR be a real matrix with dd rows and columns indexed by Λ\Lambda, and let x∈ℝΛx \in \mathbb{R}^\Lambda and a real number ε\varepsilon satisfy xj=ρb(R)x+εx_j = \rho_b(R)\, x + \varepsilon. Then p(R)x=Rx+εb.p(R)\, x = Rx + \varepsilon b .(8)✦

(c) Let p0,…,pn−1p_0, \dots, p_{n-1} be filter steps pi=(Cbi,bi,ji)p_i = (C_{b_i}, b_i, j_i), each with the symmetric contraction of its vector as matrix, let RR be a real matrix with dd rows and columns indexed by Λ\Lambda, with run R0,…,RnR_0, \dots, R_n, and let x∈ℝΛx \in \mathbb{R}^\Lambda and real numbers ε0,…,εn−1\varepsilon_0, \dots, \varepsilon_{n-1} satisfy xji=ρbi(Ri)x+εix_{j_i} = \rho_{b_i}(R_i)\, x + \varepsilon_i for every ii. Then, for every t≤nt \le n, Rtx=Rx+∑i<tεibi.R_t x = Rx + \sum_{i<t} \varepsilon_i b_i .(9)✦

In the paper, the result reads: the clipped shifts of the predictions mixm_i x are inactive, xji=mix+εix_{j_i} = m_i x + \varepsilon_i, and then Rtx=∑i<tεibiR_t x = \sum_{i<t} \varepsilon_i b_i for every tt.

What Is Checked

The item defines the clip (1), and its claim is stated over good convex bodies, with the diagonal heat bound (3) built from the Gaussian symbol (2), the Fourier multiplier, the heat operator and the compressed heat operator, and over filter steps (4) with their column insertion and run, the mass, the normalizer and the symmetric contraction (5), and the raw predictor row (6).

The library also proves that the Gaussian symbol is nonnegative✦, and that multiplication by a measurable function bounded by CC almost everywhere maps L2L^2 into itself with norm at most CC.