How Deep Is Circular Optimal Transport? Exact and Approximate Constant-Depth Circuits for Circular Wasserstein Distances

Comparing two histograms on a circle, such as gradient-orientation histograms in image descriptors, wind directions, or times of day, is harder than comparing them on a line. On a line, the cost of moving one distribution of mass into another, the earth mover's distance, is just the summed gap between the two cumulative curves. On a circle, mass can travel either way around, so the algorithm must first find where to "cut" the circle into a line. For the absolute-distance cost, that cut is given by a median of cumulative differences.

This proposal asks a precise question about that cut: how many sequential steps of arithmetic does it require? We use constant-depth real circuits as the measuring stick. These are networks of addition, multiplication and sign gates whose number of layers does not grow with input size. We conjecture a sharp three-way split. Circular transport with the absolute cost ($p=1$) can be computed exactly in constant depth with no sorting. With the squared cost ($p=2$) it is exact in constant depth once a division gate is added. For $p\ge 3$ it is provably not exactly computable in constant depth, because the answer involves square roots or higher algebraic roots. In that regime Newton iteration recovers $\varepsilon$-accuracy with depth that grows only like $\log\log(1/\varepsilon)$. The split recasts circular transport as a closure question: is a shallow real circuit class closed under taking the roots of polynomials it can already compute? This is the univariate, real-valued analogue of the factorization-closure problem in algebraic complexity.

Core Claim

Our first claim covers $p=1$. Circular earth mover's distance (CEMD) on $n$ bins lies in uniform constant-depth real circuits with $O(n^2)$ gates. Uniform means one fixed rule generates the circuit for every input size.

Circular Earth Mover's Distance for the comparison of local features and Transportation Distances on the Circle show the following. Let $D_k$ be the difference of the two cumulative histograms at bin $k$. Then the circular cost is

$$\mathrm{CEMD}(a,b)=\min_{\mu}\sum_{k=1}^{n}|D_k-\mu| ,$$

and the minimum is attained at a median $\mu^\star$ of the values $D_1,\dots,D_n$. Their algorithm finds the median by selection or sorting.

We instead test "is $D_i$ a median?" directly. We sum the signs of the differences $D_i-D_j$ over all $j$, with ties broken by index. We then select $\mu^\star$ as a sum of indicator-weighted values and compute $|x|$ as $x\cdot\mathrm{sign}(x)$. Every step is a sum, product or sign, so the whole construction fits the logic $FO_{\mathbb R}+SUM_{\mathbb R}+PROD_{\mathbb R}$. A logical characterization of constant-depth circuits over the reals proves that this logic equals uniform constant-depth real circuits, and that the sign gate already gives these circuits majority and threshold power. That paper supplies the method; it never touches transport.

Our second claim covers larger $p$. For the cost $|x-y|^p$, the optimal offset minimizes a function of the offset that is piecewise polynomial of degree $p$. Fast Transport Optimization for Monge Costs on the Circle handles this family algorithmically by searching over the offset. The degree has consequences for depth:

  • $p=2$: each piece has a rational minimizer, so enumerating pieces and taking a sign-based minimum gives a constant-depth circuit with a division gate.
  • $p=3$: the minimizer on a piece is a root of a quadratic, and the optimal cost equals a square-root expression on an open set of inputs. Circuits built from $+,\times,\div,\mathrm{sign}$ compute piecewise rational functions, so no such circuit, of any depth, computes circular $W_3$ exactly.
  • Approximation: sign-based bracketing over a polynomial grid, followed by $t$ Newton steps, achieves error $\varepsilon$ with $t=O(\log\log(1/\varepsilon))$. This holds because Newton's error squares at each step near a simple root.

The resulting theorem has the form "constant-depth real circuits are not closed under real root extraction, but are approximately closed with doubly-logarithmic depth overhead."

Relation to Prior Work

The closure lens comes from algebraic complexity. There, the question is whether the factors of a polynomial computed by small circuits also have small circuits.

All three study multivariate polynomials over fields and exact factors. We study a much smaller object: univariate real roots, inside a class that has sign gates, with approximation allowed. We do not claim progress on their open question. What we offer is a fully worked case where the "below VP" phenomenon can be pinned down: exact closure fails, and approximate closure costs $\log\log(1/\varepsilon)$ depth.

The integer-count side brings in $\#AC^0$, the class of integer functions computed by constant-depth circuits of unbounded fan-in addition and multiplication. A model-theoretic characterization of constant-depth arithmetic circuits and Descriptive Complexity of #AC0 Functions characterize this class logically, by counting winning strategies or Skolem functions. When histograms are integer counts, the cumulative differences and the counts of positive comparisons are all $\#AC^0$ functions. The one step these papers do not cover is the final comparison of two counts. We will show that deciding "is the integer CEMD at most $t$?" lets one compute majority, and so cannot be done in Boolean constant depth. This isolates exactly where the sign gate carries the real-valued result.

Research Program

Theory. The theory has three parts:

  1. Write the uniform $FO_{\mathbb R}+SUM_{\mathbb R}+PROD_{\mathbb R}$ sentence for CEMD and for the multi-histogram descriptor sum.
  2. Prove the $p=2$ upper bound with division, and the $p\ge3$ impossibility via the piecewise-rational argument.
  3. Prove the bracketing-plus-Newton approximation bound and the majority reduction for integer inputs.

Practice. The point of a constant-depth circuit is that it maps onto data-parallel hardware with no data-dependent control flow. We will implement:

  • the sign-count CEMD as a batched tensor kernel with no sort;
  • the Newton-based circular $W_p$ with a fixed number of steps;
  • both as drop-in slice routines inside Spherical Sliced-Wasserstein, which projects data on a sphere onto random great circles and applies circular transport on each.

Baselines

Bin-to-bin reference. The naive reference is $L_1$ and $\chi^2$ distance on the raw bins, which ignores circular geometry. Rabin et al. report that CEMD beats these in ROC curves on their descriptor set (Circular Earth Mover's Distance for the comparison of local features), but give no exact numbers. Our kernel must match CEMD's matching accuracy exactly while closing part of the speed gap to these bin-to-bin metrics.

Exact CEMD. The strongest exact competitor is the sort- or selection-based median of Rabin et al. It computes the same quantity, so we expect agreement to floating-point tolerance. We will run it on identical descriptors, on the same GPU, in the same framework, using the best batched sort available. Beating it means higher descriptors-per-second at quantization levels $N=8,12$ and at larger $N$. We will also report the crossover $N$ where the $O(n^2)$ gate count loses.

Circular $W_p$ for $p\ge2$. The competitor is the offset-search method of Delon, Salomon and Sobolevski, run to the same tolerance. Beating it means equal error with fewer sequential steps and higher throughput.

Learning pipelines. Here the competitors are standard SSW with sorting and stereographic slicing from Stereographic Spherical Sliced Wasserstein Distances. That paper reports 79.97% CIFAR-10 linear classification accuracy for RI-S3W; no reported result was found on Lacuna for SSW's exact CIFAR-10 accuracy or FID. We will rerun both under identical encoders, epochs and projection counts $L$. Success means matching SSW accuracy, since the computation is exact, while reducing wall-clock time toward S3W's reported "nearly an order of magnitude" advantage.

Ablations. The first ablation replaces Newton with sign-based bisection, which needs $\log(1/\varepsilon)$ sequential steps. This isolates the doubly-logarithmic claim. The second replaces the sign-count median with sorting while holding everything else fixed.

Why not just…?

Why not just sort? GPU sorting of 8 or 12 bins is already trivial. This is a real threat to any practical claim. At SIFT-scale $N$, both methods may be memory-bound and indistinguishable. The theoretical contribution does not depend on speed: it is the placement in constant depth and the $p\ge3$ impossibility. The throughput experiment across $N$ will report the outcome honestly either way. We will claim practical benefit only in regimes where it is measured.

Why not just bisect on the offset? Bisection is simple and also fits in shallow real circuits per step. But it needs $\Theta(\log(1/\varepsilon))$ sequential rounds, against Newton's $O(\log\log(1/\varepsilon))$ once a bracket is found. The ablation's error-versus-depth curve settles this directly: bisection should show a straight line on a log-error plot, while Newton's error should collapse after a few steps.

Why not just use stereographic projection or bin-to-bin metrics and avoid circular transport entirely? Bonet et al. report that stereographic projection distorts geometry near the pole and gives worse likelihoods on geospatial data. Rabin et al. report that bin-to-bin metrics lose matching accuracy. Our SSW experiment keeps S3W as a baseline, so any accuracy cost of exact geometry will be visible.

Why not just cite Boolean results that sorting needs threshold circuits? Those results concern bits. Barlag and Vollmer show that real constant-depth circuits already have threshold power through the sign gate, so Boolean lower bounds do not transfer. Our majority reduction for integer histograms is precisely the experiment that marks where the transfer fails.

Proposed Experiments

Exactness and speed of CEMD. On the SIFT-like benchmark of 732 images and 3.1 million descriptors from Rabin et al., we will first verify bitwise-tolerant agreement between the sign-count kernel and sort-based CEMD. We will then measure throughput at $N\in\{8,12,36,72,360\}$.

Depth versus error for circular $W_p$. On synthetic circular histograms with $p\in\{2,3,4\}$, we will plot error against the number of sequential steps for Newton, bisection and the exact search. The decisive check is that $W_3$ error under Newton falls doubly exponentially in the step count, while a piecewise-rational fit to the true $W_3$ cost leaves a nonzero residual. The residual is the empirical shadow of the impossibility theorem.

Learning pipelines. We will run CIFAR-10 spherical self-supervised learning and the earth-science density tasks used by SSW and S3W. Each run will use matched compute and report accuracy, negative log-likelihood and wall-clock time.

What would falsify the program. Two outcomes would force a rethink. One is a found exact constant-depth formula for $W_3$, which would refute the theorem. The other is sort-based CEMD dominating at every $N$, which would reduce the work to its theoretical half.