Contents
Where this sits
The step draws on five ideas (left) and feeds the three channels, the Python reference and the proofs page (right). Click any box to go to its explainer.
polystep’s step
polystep improves a set of particles (candidate parameter vectors) without gradients. One step, for one particle \(x \in \mathbb{R}^d\):
- Corners. Take the \(2d\) corners of the orthoplex, \(u_k = \pm e_i\). Turn them by a random rotation \(R\) (Haar on \(SO(d)\)) and scale by the step radius \(r\): \(V_k = x + r\,R\,u_k\).
- Probes and costs. Score the loss at probe points along each direction, \(x + s_j\,\rho\,R\,u_k\), and average: \(C_k\). With the defaults (one probe, \(\rho = 2r\)) the probe sits on the corner.
- Weights. \(w = \operatorname{softmax}(-C/\varepsilon)\), or Sinkhorn, which also balances the weights across particles.
- Move. \(x' = \sum_k w_k V_k\), the weighted barycentre of the corners.
Because the corners are a finite distance away, the step crosses flat regions of losses built from thresholds, rounding or argmax, where gradients are zero or undefined. That is why it trains spiking and quantized networks.
Its paper (TMLR 2026) proves a convergence theorem under stated conditions. polystep’s experiments call this setting theory mode: a square-summable, non-summable step radius \(r_t = r_0 (t+1)^{-(1/2+\gamma)}\) (its PowerDecay, \(0 < \gamma \le 1/2\)), a flat ε and a small probe-radius jitter. Its default settings (adaptive radii, quadratic models, momentum) are outside that theorem. Its README says they “do not inherit classical direct-search or trust-region guarantees”, and they are judged by experiment. Specialised solvers beat it on MAX-SAT, and backpropagation is faster on differentiable models.
Whether the theorem carries over to the hyperbolic step is an open question of this project (ledger row T1). It is not assumed here.
The step on the hyperboloid
Hyperbolic space as the upper sheet of a hyperboloid in Minkowski space, with the Lorentz form
$$\langle a,b\rangle = -a_0b_0 + a_1b_1 + \dots + a_db_d,\qquad \mathbb{H}^d = \{\,y : \langle y,y\rangle = -1,\ y_0 > 0\,\},\qquad \cosh d(y,z) = -\langle y,z\rangle.$$Its isometries are Lorentz matrices. The origin is \(o = (1,0,\dots,0)\), and the boost that carries \(o\) to a point \(x\) is
$$L_x = \begin{pmatrix} x_0 & \bar x^{\top} \\ \bar x & I + \dfrac{\bar x\,\bar x^{\top}}{1+x_0}\end{pmatrix},\qquad \bar x = (x_1,\dots,x_d).$$- Corners along geodesics. Turn the orthoplex at the origin and walk a distance \(r\) along each direction, then carry the result to \(x\): $$V_k = L_x\begin{pmatrix}\cosh r\\ \sinh r\;R\,u_k\end{pmatrix}.$$ Each \(V_k\) is at hyperbolic distance exactly \(r\) from \(x\). Probes are the same with \(s_j\rho\) in place of \(r\).
- Costs. Decode each probe into an answer (a colour, a truth assignment, a network’s weights; see the decoders) and score it as a black box. Nothing here needs a gradient.
- Weights. Unchanged: \(w = \operatorname{softmax}(-C/\varepsilon)\) or Sinkhorn. The solvers only ever see the cost matrix, so polystep’s own solvers are reused as they are.
- Centroid. Average in Minkowski space and return to the sheet: $$s = \sum_k w_k V_k,\qquad x' = \frac{s}{\sqrt{-\langle s,s\rangle}}.$$ In the Klein model, where a point is \(\kappa(y) = \bar y / y_0\) and geodesics are straight, the normalisation cancels and the centroid is a plain convex combination: $$\kappa(x') = \sum_k \lambda_k\,\kappa(V_k),\qquad \lambda_k = \frac{w_k\,V_{k,0}}{\sum_j w_j\,V_{j,0}} \ \ge 0,\quad \sum_k\lambda_k = 1.$$
Look around in every direction of a turned cross, the same distance along straight hyperbolic paths. Score what you see. Move to a weighted middle of the corners. In the Klein picture that middle is an ordinary weighted average, so it can never land outside the corners, and never further than one step away.
Live diagram
One particle in the hyperbolic plane (\(d = 2\), four corners), drawn twice: in the Poincaré disk, where angles are true and geodesics are arcs, and in the Klein disk, where geodesics are straight. The loss is a staircase of the distance to the gold target, so it has no useful gradient. Click either disk to move the target.
Poincaré disk
Klein disk
White: the particle x and the circle of radius r around it. Coloured: the four corners and their geodesics, sized by weight. Cyan: the hyperbolic centroid x′. Grey ring (Poincaré only): the plain average of the corners’ Poincaré coordinates, which is not the hyperbolic centroid.
- Push ε to the left. The weights pile onto the best corner and x′ lands on it (H6).
- Push ε to the right. The weights even out and x′ stays near x. On the Klein side it is always inside the polygon of corners, so the readout’s d(x, x′) never exceeds r (H2).
- Move the target near the rim and run 10 steps. Near the rim the same hyperbolic radius covers less and less of the disk: that is the shrinking-step effect of conjecture C2.
The exact route
The search runs in floating point (track A). The certificates run in exact rationals (track B), and the paper supplies a rational version of every ingredient.
| Ingredient | Float (track A) | Exact rational (track B) | Source |
|---|---|---|---|
| Walk a distance r | \(\cosh r,\ \sinh r\) | Choose \(t = \tanh(r/2) \in \mathbb{Q}\): \(\cosh r = \frac{1+t^2}{1-t^2},\ \sinh r = \frac{2t}{1-t^2}\) | The ghost map in one dimension (§3.2) |
| Rotation R | Haar-random, polystep’s get_random_rotation_matrices | Cayley map \(R = (I-A)(I+A)^{-1}\), \(A\) skew with rational entries; exactly orthogonal. In three dimensions, the rational quaternions of the existing core | Fifteen Lemmas; cayleyMap in the core |
| Boost \(L_x\) | As above | Rational whenever \(x\) is a rational point of the sheet | §4.2 |
| A point of the sheet | Any | \(G(p) = ((1+|p|^2),\,2p)/(1-|p|^2)\) for rational \(p\) in the unit ball | Prop 3.3 |
| Centroid | \(s/\sqrt{-\langle s,s\rangle}\) | The Klein point \(\kappa(x')\) is rational; returning to the sheet needs one square root, so the state is snapped: its Poincaré point is rounded to a declared grid \(2^{-k}\) and lifted by \(G\). The snap’s distance is logged on track C | §8.10, the exact-first convention |
So every corner, probe and stored state is an exact rational point of the hyperboloid, checkable by \(\langle y,y\rangle = -1\) in exact arithmetic. The only approximation is the snap, it is declared, and its size is recorded every step. This is the same convention the tri-engine pages use when they rationalise at \(2^{-24}\).
The paper’s {4,3,5} cell gives a natural exact radius: its face-neighbour boost has \(\tanh(\vartheta/2) = a = \varphi^{-3/2}\), entries in \(\mathbb{Z}[\sqrt\varphi]\) (Prop 4.3). A step radius of one cell inradius is available exactly in that ring, an option for later, not part of the first build.
Correspondence with polystep
What changes, function by function, in polystep 1.1.1.
| polystep | Does | Hyperbolic version |
|---|---|---|
| geometry.get_orthoplex_vertices | \(\pm e_i\) | Unchanged, in the tangent space at the origin |
| geometry.get_random_rotation_matrices | Haar rotations | Unchanged for track A; Cayley rotations for track B |
| _compiled._rotate_and_translate | \(x + rRu\) | \(L_x(\cosh r, \sinh r\,Ru)\) |
| _compiled._compute_probe_points | \(x + s\rho Ru\) | \(L_x(\cosh s\rho, \sinh s\rho\,Ru)\) |
| costs.compute_cost_matrix | Average over probes | Unchanged, after decoding |
| solvers.SoftmaxSolver, SinkhornSolver | Weights from costs | Reused as they are |
| _compiled._barycentric_projection | \(\sum w_k V_k\) | Lorentzian centroid (Klein convex combination), then the snap |
| epsilon.CosineEpsilon, LinearEpsilon | Schedules for ε and radii | Reused; radii are now hyperbolic lengths |
| blockwise, subspaces | Search a few coordinates at a time | A product of small hyperbolic factors \((\mathbb{H}^{d})^m\), one polytope per factor |
| PolyStepOptimizer, train() | Network training loop | The Euclidean baseline, run from the library itself |
polystep is Apache-2.0. The reference imports it; anything ported to the browser carries its notice and credits An T. Le, Training Non-Differentiable Networks via Optimal Transport, TMLR 2026.
Properties H1–H7
What can honestly be proved about the step. Each has a proof sketch here. The full proofs, with live checks on the browser core, are on the proofs page: hence PROVEN. Each is also tested by the Python reference on random instances, in exact arithmetic where the claim is exact (the test table).
H1 · Everything stays on the sheet PROVEN
\(L_x\) preserves the Lorentz form, and \((\cosh r, \sinh r\,Ru)\) lies on the sheet because \(\cosh^2 r - \sinh^2 r\,|Ru|^2 = 1\) for a unit \(u\). With rational \(t\), a Cayley \(R\) and a rational \(x\), every coordinate is rational and \(\langle V,V\rangle = -1\) holds exactly. The snapped state is \(G(p)\) of a rational \(p\), so it is on the sheet exactly too.
H2 · One step moves at most r PROVEN
Apply \(L_x^{-1}\), an isometry: \(x\) goes to the origin and every corner to Klein radius \(\tanh r\). Seen from the origin, the Klein ball of Euclidean radius \(\tanh r\) is exactly the hyperbolic ball of radius \(r\), because \(d(o, y) = \operatorname{artanh}|\kappa(y)|\). The centroid’s Klein point is a convex combination of the corners’ and so lies in that ball, and the centroid commutes with Lorentz maps. Hence \(d(x, x') \le r\). The snap adds at most its logged residual.
In a product of factors, each factor moves at most r: its corners are within r of it, and its centroid is a Klein convex combination of them. Every factor is also kept inside a ball of radius 8 about the origin, the declared horizon; a point outside is moved radially back to the ball’s nearest point. That projection onto a convex set never lengthens a move, so H2 survives it (why the horizon exists).
H3 · The centroid is the best compromise PROVEN
With the squared Lorentzian distance \(d_L^2(y,z) = -2 - 2\langle y,z\rangle\), the weighted sum \(\sum_k w_k\,d_L^2(y, V_k) = -2\sum w_k - 2\langle y, s\rangle\) is smallest when \(\langle y, s\rangle\) is largest. For future timelike vectors, the reversed Cauchy–Schwarz inequality gives \(\langle y, s\rangle \le -\sqrt{-\langle s,s\rangle}\), with equality only when \(y\) is parallel to \(s\). So \(x' = s/\sqrt{-\langle s,s\rangle}\) is the unique minimiser (Law, Liao, Snell and Zemel, ICML 2019).
H4 · Any chart gives the same step PROVEN
For a Lorentz map \(g\), the boost \(L_{gx}\) equals \(g L_x Q\) for a rotation \(Q\) fixing the origin. \(Q\) is absorbed into the random rotation, whose Haar law it does not change. The objective seen through \(g\) gives the same costs, hence the same weights, and the centroid is equivariant: the step at \(gx\) is \(g\) applied to the step at \(x\). With the rotation fixed rather than random, this is an exact identity, and the reference tests it with rational Lorentz maps.
H5 · Flat space gives polystep back PROVEN
At curvature \(-c\), distances scale by \(\sqrt c\). As \(c \to 0\): \(\cosh(\sqrt c\,r) \to 1\), \(\sinh(\sqrt c\,r)/\sqrt c \to r\), the Klein chart becomes the Euclidean chart, and \(\lambda_k \to w_k\) because every \(V_{k,0} \to 1\). The step tends to \(\sum_k w_k(x + rRu_k)\), polystep’s step. So the hyperbolic version is a curvature-one deformation of polystep, not a different algorithm.
H6 · Small ε picks the best corner PROVEN
As \(\varepsilon \to 0\), \(\operatorname{softmax}(-C/\varepsilon)\) concentrates on the corners of least cost, and the centroid of one corner is that corner. Keeping the best answer seen (an elitist incumbent) gives a cost that never increases. The particle itself can move to a worse cost when \(\varepsilon > 0\); no descent is claimed for it.
H7 · The register’s holonomy is exact PROVEN
After the snap, consecutive states are rational points, so each step’s displacement \(\Delta q_n = L_{x_n}L_{x_{n-1}}^{-1}\) is a rational Lorentz matrix. The paper’s pump (Prop 3.9) is pure group algebra and holds without commutativity: over each 720-frame register \(H = Q^{(8)}Q^{(10)}P = P^{-1}\) exactly. This certifies the exact bookkeeping of every trajectory. It says nothing about whether the trajectory is making progress.
What it does not promise
- No convergence guarantee yet. H1–H7 are about where the step lands, not about reaching an optimum. Whether polystep’s convergence theorem transfers to the hyperboloid under its theory-mode conditions is open (T1); the reference implements theory mode so the question can be tested.
- No free search. A step costs \(2d\) evaluations per particle per probe. Against a yes/no objective, no step rule beats the volume of the space (paper, Prop 5.13).
- Curvature is a hypothesis, not a gift. In one dimension the hyperbolic line is isometric to the real line, so curvature only matters for factors of dimension two or more. Whether it helps is conjecture C1, decided by the preregistered benchmarks.