# Common Geodesics Do Not Guarantee Fisher Consistency of the Structured SVM: Minimal Counterexamples and a Tree-Metric Classification

arXiv: https://arxiv.org/abs/2608.27203 · HTML: https://mlsanity.com/paper/2608.27203/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 17 references that are in the map.
- First posted on arXiv 27 Aug 2026.

## Builds on (most cited first, 6 of 6)

- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [Convex Calibration Dimension for Multiclass Loss Matrices](https://mlsanity.com/paper/1408.2764/) (2014)
- [An Embedding Framework for Consistent Polyhedral Surrogates](https://mlsanity.com/paper/1907.07330/) (2019)
- [An Embedding Framework for the Design and Analysis of Consistent Polyhedral Surrogates](https://mlsanity.com/paper/2206.14707/) (2022)
- [Consistent Structured Prediction with Max-Min Margin Markov Networks](https://mlsanity.com/paper/2007.01012/) (2020)
- [On the Consistency of Max-Margin Losses](https://mlsanity.com/paper/2105.15069/) (2021)

## Abstract (arXiv)

A known necessary condition for Fisher consistency of the structured support vector machine requires the task loss to be a metric for which every output triple has a common geodesic point. We show that this condition is not sufficient for the canonical coordinate-wise argmax decoder. A four-output unit star admits an exactly optimal score vector whose maximizers are all strictly non-Bayes, and four outputs are minimal among metrics satisfying the condition. We then completely classify positively weighted tree metrics whose vertex set is the output space: argmax consistency holds if and only if the tree is a path. The failure on branching trees is confined to boundary distributions; every tree retains the argmax property at every full-support distribution. Among metrics satisfying the common-geodesic condition, five outputs are necessary and sufficient for a full-support counterexample; K2,3 is the smallest member of an infinite Km,n family. We additionally give a full-support counterexample for the three-dimensional Hamming cube. All optimality claims have exact primal-dual certificates. The counterexamples expose a concrete decoder gap: in this polyhedral setting, an embedding can guarantee the existence of a calibrated link without validating a prescribed argmax link on every surrogate-risk minimizer.