Some learning problems need only a handful of examples, yet finding a model that fits those examples seems to require solving a famously stubborn puzzle. We propose to study one such case in max-plus ("tropical") geometry. Here "addition" means taking a maximum and "multiplication" means ordinary addition. The resulting shapes are piecewise linear and appear in auction markets, phylogenetic trees and ReLU-like models. The simplest classifier in this world is a tropical halfspace: the set of points $x$ where one weighted maximum beats another,
$$ \max_i (a_i + x_i) \;\ge\; \max_j (b_j + x_j), $$
where $a$ and $b$ are learned weight vectors (entries may be $-\infty$ to switch a coordinate off). Our claim has two parts. First, a max-plus version of Radon's theorem bounds the number of examples needed to learn this class at roughly the ambient dimension, as for ordinary linear classifiers. Second, finding a tropical halfspace consistent with labeled data is a tropical linear feasibility problem. That problem is computationally equivalent to mean payoff games: two-player games on weighted graphs that lie in NP ∩ co-NP but have resisted polynomial-time algorithms for decades. If the reverse reduction holds, efficient proper learning of tropical halfspaces is exactly as hard as mean payoff games. That would be a statistical-computational gap of an unusual kind, because its hard side probably cannot be NP-hard: in NP ∩ co-NP, NP-hardness would collapse NP to co-NP.
The algorithmic side matters because it decides what can actually be computed on data. The tropical simplex method pivots directly in max-plus arithmetic, without lifting to formal power series, at $O(n(m+n))$ operations per pivot. Nobody has run it on data-generated instances. We pair it with a sample-compression scheme derived from max-plus Helly-type theorems, so the expensive solver only ever touches small subproblems. We then measure whether the instances that real data produce are easy, which the worst-case theory cannot answer.
Core Claim
The proposal rests on three statements. The first is proved by a short argument. The second is half immediate and half the central research question. The third is empirical.
Statistical side. Carathéodory, Helly and the Others in the Max-Plus World proves max-plus analogues of Radon, Helly and Carathéodory. We supply the method: take a Radon partition $(A,B)$ of a point set. A closed tropical halfspace and its open complement are both tropically convex. So no tropical halfspace can contain $A$ while excluding $B$, which means the set cannot be shattered. The VC dimension, a standard measure of classifier richness, is therefore at most one less than the max-plus Radon number, which is of order $d$. Standard realizable PAC bounds then give a sample complexity of $O((d\log(1/\epsilon)+\log(1/\delta))/\epsilon)$. The same Helly structure suggests a compression scheme of size $O(d)$: every consistent fit is determined by $O(d)$ "basis" examples.
Computational side. The upper bound is immediate. Each labeled point $x$ gives a two-sided tropical linear inequality in the unknowns $(a,b)$, and Tropical Polyhedra are Equivalent to mean Payoff Games shows such feasibility problems reduce to mean payoff games.
The research question is the reverse direction. Every learning constraint has a special structure: the same coefficient vector $x$ appears on both sides, with disjoint variable blocks. We conjecture that this restricted family is still as hard as mean payoff games. The plan is to encode arbitrary two-sided systems through gadget data points whose $-\infty$ or very large coordinates separate the roles of $A$ and $B$. Combining this with the classical argument that an efficient proper PAC learner with $\epsilon < 1/m$ yields a consistent hypothesis would give the main result. Efficient proper learning of tropical halfspaces would then hold if and only if mean payoff games are solvable in randomized polynomial time.
This sits differently from the gaps cited in the file. In Provable benefits of score matching, the hard side is NP-hard via 3-SAT. The same holds in Hardness of Maximum Likelihood Learning of DPPs. Ours would be pinned to an NP ∩ co-NP problem. Known pseudo-polynomial game algorithms do not close this gap, since learnability is measured in the bit-length of the data, not its magnitude.
Empirical side. Tropical simplex pivoting, run inside a compression-based learner, should take few pivots on instances generated by natural data distributions, even though worst-case families exist. This directly probes the open concern in Direction 4 that worst-case reductions may not describe average-case behavior.
Relation to Prior Work
The closest work is Tropical linear regression and mean payoff games. It fits a tropical hyperplane to noisy points, shows the fitting error equals the radius of the largest inscribed ball in a tropical polyhedron, and proves the problem equivalent to mean payoff games. It solves this by Krasnoselskii-Mann value iteration in $O(npW/\epsilon^2)$ operations. It has no sample-complexity analysis, uses no simplex method, and treats regression rather than classification. We take its game equivalence as motivation. We differ by asking the learning-theoretic question: how many samples are needed, and is the computational cost intrinsic to learning rather than just to the optimization formulation.
Two further papers apply tropical estimation without statistical rates. Tropical Fréchet Means computes the set of tropical averages as a polytrope. Tropical gradient descent optimizes tropically quasi-convex losses at an $O(1/\sqrt{m})$ rate. Both supply benchmarks and baselines here, not theory we reuse.
On the algorithmic side, we reuse methods directly. Tropicalizing the Simplex Algorithm gives pivoting on tangent digraphs, which requires genericity assumptions. Combinatorial Simplex Algorithms Can Solve Mean Payoff Games adds symbolic perturbation and a Phase I procedure, which removes those assumptions. Neither paper has been run on data-derived instances.
Two results constrain the design.
- Tropical Carathéodory with Matroids shows two things. Topological arguments break in tropical geometry, since any simplicial complex can be a tropical support complex. Adding selection constraints also turns easy tropical problems NP-complete. We therefore use only Radon/Helly counting arguments, not topology. We also expect the agnostic version, which minimizes misclassifications, to fall into NP-hardness, so the clean MPG characterization is claimed only for the realizable case.
- Approximating the volume of tropical polytopes is difficult warns that likelihood-style estimators involving tropical volume are NP-hard. This is why we target classification consistency rather than density estimation.
Research Program
The theory track has three parts.
- Write out the VC and compression bounds, including the boundary cases with $-\infty$ weights that the max-plus literature flags as delicate.
- Attempt the reverse reduction from general two-sided tropical systems to same-coefficient learning constraints.
- If the reduction fails, identify which special structure makes the learning instances easier. That would itself be a positive algorithmic result, giving a polynomial-time subclass of mean payoff games.
A secondary theorem extends the analysis to a margin version. There, Akian et al.'s inscribed-ball radius plays the role of the margin. We would ask whether margin-dependent, dimension-light rates hold under the Hilbert projective metric.
The algorithm track builds a learner in three layers.
- Clarkson-style sampling. This uses the $O(d)$-size compression: it repeatedly solves the fitting problem on small random subsamples and adds violated examples.
- Basis solver. Each subproblem is solved by the perturbed tropical simplex method with Phase I.
- Certificate. The output is a consistent tropical halfspace together with its basis examples, or an infeasibility certificate. Value iteration cannot provide such exact certificates.
Baselines
Naive reference point. The first reference is the majority-label classifier. Beside it, we report a single-pivot heuristic that takes $a$ and $b$ from coordinate-wise class means. Any learner that fails to beat these on held-out accuracy is not learning tropical structure.
Strongest existing method. This is the projective Krasnoselskii-Mann value iteration of Tropical linear regression and mean payoff games, applied to the same feasibility system. It is the only published solver with guarantees for this exact problem class. On its auction benchmark (3 firms, 100 rounds) it recovered hidden preferences $(1, 0.799, 0.601)$ against ground truth $(1, 0.8, 0.6)$, with distance-to-equilibrium error $2.06\times10^{-2}$. For the classification task proposed here, no reported result was found on Lacuna. For fairness, both methods receive identical constraint systems and wall-clock budget. Value iteration is tuned over step size and stopping tolerance. We count it as beaten if the simplex learner (i) reaches exact consistency in less time once the integer weight bound $W$ is scaled up, and (ii) matches held-out accuracy.
Continuous heuristic. Tropical gradient descent and TrAdamax from Tropical gradient descent are run on a hinge-style loss for the same hypothesis class. They get an equal tuning budget over learning rate and steps. Their published results are 100% correct species-tree topology on coalescent data, about 0.5 seconds per 1000 steps, and log errors "often by a factor of two" lower than classical gradient descent. Beating them means fewer training errors at convergence on separable data, where an exact method should reach zero.
Ablations. Two ablations isolate the key ingredients. The first runs the simplex solver on all $n$ constraints without compression, which tests whether Helly-based compression is what keeps instances small. The second plugs value iteration into the compression loop, which tests whether pivoting itself matters.
Why not just…?
Why not just lift to Puiseux series and call a classical LP solver? Lifting is correct but tracks formal series terms. The file reports that it is computationally heavy and hides the combinatorial structure (Tropicalizing the Simplex Algorithm). We will implement a truncated lifting on the smallest instances as a correctness check. We expect its cost per instance to grow with the required series precision, while tropical pivots stay at $O(n(m+n))$.
Why not just use value iteration, which already works? It is a real competitor on small-weight data. Its cost scales with $W/\epsilon^2$, so it is pseudo-polynomial and yields no exact basis. We settle this by sweeping $W$ over several orders of magnitude on fixed combinatorial instances. If value iteration remains faster at realistic $W$, we will report that the gap is only theoretical in practice.
Why not just learn improperly, for example with a linear classifier on all pairwise differences $x_i - x_j$? This is the most serious threat. A tropical halfspace is a union of $d$ polyhedra whose facets are differences of coordinates. An improper learner might reach low error in polynomial time and sidestep the mean-payoff barrier entirely. Our hardness claim is explicitly about proper learning. We will test improper learners on the same splits: pairwise-difference logistic regression, gradient-boosted trees on differences, and a small max-plus network trained with the noise-injection tricks of Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras. If they match proper accuracy at comparable sample sizes, we will state that the gap is a properness phenomenon. Improper hardness would then become the open problem.
Proposed Experiments
Data. We use four data sources.
- Auction market. We regenerate the simulated market of Akian et al. with log-uniform bids. Bid profiles are labeled by which of two hidden buyer-preference regimes produced them. This yields a planted tropical halfspace with additive noise.
- Tree-like data. We use the branching, coalescent and Gaussian generators from the tropical projective torus suite of Talbut and Monod, in dimensions up to 28. The task is classifying coalescent against branching samples.
- Real-data stress test. MovieLens 1M, used by Kordonis et al. with tropical compression at HR@10 0.743 against 0.731 for linear factorization. Here it serves only to see whether pivot counts stay small on non-synthetic coordinates. Because its labels are not separable, it is run in the agnostic mode with the stated NP-hardness caveat.
- Adversarial instances. Tropical Klee-Minty constructions bound pivot counts from the worst-case side.
Decisive checks. Three outcomes settle the claims.
- The test error of the exact learner as a function of $n$ should flatten at a sample size that scales linearly in $d$, which follows from the VC bound. If the threshold instead grows like $d^2$, the Radon-based bound is loose or the $-\infty$ cases inflate capacity.
- Pivot counts per basis call should grow polynomially in $d$ on data-generated instances while growing exponentially on the adversarial ones. If data instances also blow up, the average-case optimism fails.
- The improper comparison either matches proper accuracy, confining the gap to properness, or falls short at equal samples. Falling short would give the first empirical sign that the mean-payoff barrier bites in learning.
Success criterion. The project succeeds if it delivers the reverse reduction, or a proof that learning instances form an easier subclass, together with these three measurements.
References
- Carathéodory, Helly and the Others in the Max-Plus World
- Tropical Polyhedra are Equivalent to mean Payoff Games
- Provable benefits of score matching
- Hardness of Maximum Likelihood Learning of DPPs
- Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
- Tropical Fréchet Means
- Tropical gradient descent
- Tropicalizing the Simplex Algorithm
- Combinatorial Simplex Algorithms Can Solve Mean Payoff Games
- Tropical Carathéodory with Matroids
- Approximating the volume of tropical polytopes is difficult
- Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras