Training Non-Differentiable Networks via Optimal Transport

Hard thresholds, quantization, and discrete routing can produce training losses with flat regions and jumps, where ordinary gradients vanish or are undefined. We introduce PolyStep, a forward-only optimizer that evaluates rotated polytope probes and moves parameter blocks along weighted averages of the probe directions. We derive the weights from one-sided entropic transport and use its uncoupled softmax solution in our primary experiments. Our analysis explains when variation among probe costs produces motion and when that motion decreases the loss. On a regular simplex, nonconstant costs always give a nonzero direction. For monotone ridge losses, the softmax update cannot increase the loss at any positive temperature; a perturbation bound gives sufficient conditions for descent near curved jumps. For bounded measurable losses, we randomize the probe radii and identify an exact smoothing whose gradient equals the expected linear cost-weighted direction up to scale. This identity yields a stationarity bound for an idealized fixed-temperature variant: under regularity and sampling assumptions stronger than those met by our trained configurations, the bound has an O(T-1/2) term and a persistent bias floor. We evaluate the practical method on networks with hard operations, discrete optimization, and policy search. On MNIST with hard-threshold spiking neurons, PolyStep reaches 93.0 ± 0.2%, compared with 79.6 ± 5.2% for the best-tuned gradient-free baseline at matched evaluations. These gains come with a query cost proportional to the search dimension per fresh step, which limits the number of updates available at a fixed budget.