PolyStep: Training the "Un-trainable" with Optimal Transport and Polytope Probing

TL;DR

PolyStep is a groundbreaking gradient-free optimizer that enables training for models containing genuinely non-differentiable layers—such as hard-threshold spiking neurons and INT8 quantized weights. By replacing backpropagation with structured geometric probing and Optimal Transport (OT), it achieves SOTA results on architectures where traditional gradients simply do not exist.

The "Zero-Gradient" Dead End

Modern deep learning is built on the assumption of differentiability. However, as we push toward "green AI" (quantized models) and "brain-inspired AI" (spiking networks), we encounter hard thresholds. Functions like sign(x), round(x), or argmax(x) have zero derivatives almost everywhere.

When backpropagation hits these layers, it dies. Researchers usually "hack" this with Surrogate Gradients or Straight-Through Estimators (STE), but these are biased approximations. PolyStep asks a radical question: Can we train these models using only the forward pass, without any gradient proxies at all?

Methodology: Probing the Polytope

PolyStep treats the neural network as a black-box cost oracle. Instead of trying to find a slope, it probes the surrounding parameter landscape using a structured geometry.

1. Subspace Compression

Optimization in a million-dimensional space is impossible without gradients. PolyStep uses HybridSubspace projections, decomposing parameters into low-rank layers to keep the number of "test probes" manageable.

2. The Orthoplex Probe

For each parameter "particle," the algorithm samples vertices of a rotated polytope (an orthoplex). It evaluates the loss at these vertices—entirely via vectorized forward passes.

3. Optimal Transport Update

The core "magic" lies in how it moves. It doesn't just pick the best vertex; it computes a transport plan. Using a Softmax (which the authors prove is a specific limit of entropic Optimal Transport), the model slides toward low-cost vertices via barycentric projection.

Experimental Breakthroughs

The results confirm that PolyStep succeeds where traditional evolution strategies (ES) and gradient-based methods fail.

• Spiking Neural Networks (SNN): On hard-LIF spikes (no smooth approximation), PolyStep reached 93.4% accuracy. Compare this to OpenAI-ES at 33.1% or SPSA at 29.4%.
• Sub-linear Memory: Because it doesn't store a gradient tape, it achieved a 29.8x reduction in VRAM compared to BPTT for long-horizon recurrent tasks.
• Scaling to 1 Million Variables: In discrete MAX-SAT problems, PolyStep maintained >92% satisfaction while other generic optimizers collapsed as the dimensionality increased.

Deep Insight: The Value of "Forward-Only"

The academic significance of PolyStep is twofold. First, it provides a rigorous convergence proof on piecewise-smooth losses, showing that stochastic rotations can "dodge" discontinuity sets.

Second, it aligns with a future of inference-optimized hardware. Most modern AI accelerators are designed for fast forward passes, not complex backward-pass gradient storage. PolyStep turns the training process into a sequence of batched inferences, potentially allowing us to train models directly on edge devices or neuromorphic chips that lack backprop support.

Conclusion & Perspectives

PolyStep isn't here to replace Adam on differentiable tasks—gradients are still more efficient when they exist. Instead, it is a specialized tool for the "Non-Differentiable Frontier." It provides a principled, OT-grounded way to bridge the gap between discrete logic and continuous optimization.

Limitations: The main hurdle remains the "zeroth-order penalty." Training takes significantly more forward passes (3 orders of magnitude more for MNIST) than a standard backprop run. However, for models where gradients are literally undefined, PolyStep is currently the most robust path forward.