Source-linked AI summary
Common Geodesics Do Not Guarantee Fisher Consistency of the Structured SVM: Minimal Counterexamples and a Tree-Metric Classification
Jintao Fei, Jiangying Luo
TL;DR
The paper asks whether a common-geodesic metric condition suffices for canonical SSVM argmax consistency, then tests it with exact counterexamples and optimality certificates. It finds minimal boundary and full-support failures, classifies tree metrics, and isolates a gap between calibrated embeddings and prescribed argmax decoding.
Problem
The paper investigates whether the common-geodesic condition, known to be necessary for structured SSVM Fisher consistency, is also sufficient for canonical coordinate-wise argmax decoding.
Method
The paper constructs exact SSVM counterexamples, classifies positively weighted tree metrics, and uses surrogate level sets plus primal-dual optimality certificates.
Results
The common-geodesic condition is insufficient: four outputs are minimally needed for a counterexample, paths are exactly the consistent tree metrics, and five outputs suffice for a full-support obstruction.
Takeaways & Limitations
Embedding a target loss does not by itself validate a prescribed coordinate-wise argmax link on every surrogate-risk minimizer.
Takeaways & Limitations
The sharp cardinality under the additional requirements of a unique Bayes output and disjoint argmax remains open.
Abstract
from arXiv · showhide
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; $K_{2,3}$ is the smallest member of an infinite $K_{m,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.
1 Introduction
The paper shows that the common-geodesic condition is not sufficient for canonical argmax consistency, despite prior embedding-based guarantees. It provides minimal counterexamples, classifies tree metrics, and identifies the decoder condition separating calibrated embeddings from prescribed argmax decoding.
- Counterexamples: A four-output unit star disproves sufficiency of the common-geodesic condition, and no three-output counterexample exists.The star has a unique Bayes center, while every score maximizer is a non-Bayes leaf.
- Tree-metric classification: The canonical argmax rule is Fisher consistent for weighted tree metrics exactly when the tree is a path.Branching trees exhibit the obstruction, while weighted paths remain consistent for every distribution and surrogate-risk minimizer.
- Tree-metric classification: Every tree is pointwise consistent at full-support distributions, so branching-tree failure is confined to the simplex boundary.This distinguishes the boundary obstruction from the separate full-support failures found for non-tree metrics.
- Full-support obstructions: Five outputs are necessary for a full-support counterexample among common-geodesic metrics; K2,3 attains the threshold, and the three-dimensional Hamming cube also fails.The K_m,n family shows that the complete-bipartite example is not isolated.
- Decoder gap: Surrogate level sets expose the missing condition between a polyhedral embedding and a prescribed coordinate-wise decoder.Embedding theory can supply a calibrated link without validating argmax on every surrogate-risk minimizer.
- Certification: Exact optimality certificates use rational probabilities, elementary scores, telescoping cycle bounds, or optimal-transport dual certificates.The conclusions do not rely on floating-point computation or finite-instance experimentation.
2 Setting and exact optimality certificates
The paper formulates conditional SSVM and target risks for finite metric losses and uses metric intervals to state the common-geodesic condition. A finite optimal-transport representation and duality provide exact certificates for surrogate-risk optimality.
- Risk and consistency setup: For a finite output space, the loss is a metric and consistency compares the conditional surrogate and target Bayes risks using set-valued argmax.The target and surrogate risks are minimized over outputs and score vectors, respectively.
- Common-geodesic condition: The metric interval I(x, y) contains points z satisfying L(x, y) = L(x, z) + L(z, y).The common-geodesic condition requires the three pairwise metric intervals for every output triple to have a nonempty intersection.
- Common-geodesic condition: Every tree metric satisfies the common-geodesic condition, Hamming cubes are median, and complete bipartite graph metrics are modular but generally not median.Modular metrics guarantee a common point, whereas median metrics impose uniqueness.
- Transport formulation: The conditional SSVM Bayes risk has a finite linear-programming and optimal-transport representation.The proof uses epigraph variables, coupling constraints, and strong duality.
- Transport formulation: Dual feasibility requires coupling row and column marginals to equal q, with complementary slackness characterizing optimal score vectors.Nonnegative multipliers form a coupling, and positive coupling entries impose tight score constraints.
- Transport formulation: The supported-coupling criterion reduces existence to neighborhood inequalities via the max-flow–mincut theorem and permits symmetrization when marginals and support are symmetric.Averaging a feasible coupling with its transpose preserves both marginals and support.
3 A complete classification for tree metrics
For positively weighted tree metrics whose vertices are exactly the outputs, argmax consistency holds precisely for paths: branching creates boundary counterexamples, while full-support distributions remain consistent.
- Tripod obstruction: A tripod obstruction makes the max-margin loss not argmax Fisher consistent, with every score maximizer non-Bayes.The construction uses a distribution supported equally on three leaves and an exactly optimal score vector whose maximizers are leaves rather than the Bayes center.
- Tripod obstruction: Every branching vertex in a positively weighted tree supplies the tripod obstruction by selecting one vertex from each resulting component.The smallest instance is the four-output unit star.
- Weighted paths: Every positively weighted path satisfies the argmax property for every distribution, including boundary distributions and Bayes ties.The proof uses the ordered path structure and transport couplings across the median or median plateau.
- Classification: Argmax Fisher consistency for finite positively weighted tree metrics holds if and only if the tree is a path.Paths are consistent, whereas every non-path tree has a branching vertex and therefore a tripod obstruction.
- Full-support distributions: For every full-support distribution on any finite positively weighted tree, every surrogate-risk score maximizer lies in the Bayes set.The proof handles both a unique tree median and a two-vertex median plateau using supported couplings and complementary slackness.
4 Sharp lower bounds on output cardinality
Among metrics satisfying the common-geodesic condition, four outputs are the minimum for unrestricted inconsistency, while five are necessary and sufficient for a full-support counterexample.
- Three-point classification: Every three-point admissible metric is a positively weighted path with distances L(1,2)=A, L(2,3)=B, and L(1,3)=A+B.This establishes consistency for the three-point case through the path result.
- Unrestricted counterexamples: Four outputs are the minimum cardinality of an argmax Fisher-inconsistency counterexample among metrics satisfying the common-geodesic condition.All admissible three-point metrics are consistent, while the four-point unit star is inconsistent.
- Four-point classification: Weighted rectangles satisfy the argmax property at every full-support distribution.Their metric has coordinate-wise form L(x,y)=A|x1−y1|+B|x2−y2| with A,B>0.
- Full-support threshold: Every metric with 3 ≤|Y| ≤4 satisfying the common-geodesic condition has the argmax property at every full-support distribution.The four-point classification reduces the possibilities to stars, paths, and weighted rectangles, each full-support consistent.
5 Full-support counterexamples
Full-support counterexamples show that the common-geodesic condition is not sufficient: five outputs are minimal, with K_{2,3} providing the smallest complete-bipartite example, and the three-dimensional Hamming cube also fails.
- The complete-bipartite family K_{m,n}, with 2 ≤ m < n, satisfies the common-geodesic condition but fails argmax Fisher consistency at the uniform full-support distribution.The smallest member is K_{2,3}.
- For the bipartite construction, an exactly optimal score assigns −1 to A and 0 to B, while the Bayes set is A and arg max v is B.A directed-cycle dual coupling certifies primal optimality.
- Five outputs are necessary and sufficient for a full-support counterexample among metrics satisfying the common-geodesic condition.The lower bound is attained by the K_{2,3} construction.
- The three-dimensional Hamming cube provides a full-support counterexample with a unique Bayes output 100 and an argmax set disjoint from it.Even-parity vertices receive score zero and odd-parity vertices receive score −1; the cube satisfies the common-geodesic condition.
6 Where the embedding-to-argmax implication fails
The embedding-to-argmax implication fails because optimal surrogate reports can lie outside the embedding image. Consistency therefore requires a level-set condition over all surrogate minimizers, not merely decoder inversion on embedded reports.
- A prescribed decoder is consistent exactly when every surrogate-risk minimizer decodes only to outputs in the corresponding Bayes region.For the canonical decoder, D(v) = arg max_y v_y.
- Embedding verifies compatibility only on the finite set ϕ(Y), whereas polyhedral embedding theory constructs a calibrated link on all reports.It does not establish calibration for an arbitrary preassigned link such as coordinate-wise argmax.
- The unit-star example contains an additional optimal report outside ϕ(Y) that coordinate-wise argmax decodes only to non-Bayes leaves.Thus inversion of the embedding on ϕ(Y) cannot ensure consistency on the entire optimal set.
- Bayes-risk equality and a scaled embedding do not by themselves imply consistency under coordinate-wise argmax.Branching trees consequently fail under the canonical decoder, while their Bayes-risk and embedding statements remain valid.
7 Discussion
The paper establishes that embedding and Bayes-risk agreement do not ensure consistency for a prescribed argmax decoder, and identifies both exact tree-metric boundaries and unresolved extensions.
- Within tree metrics, weighted paths are exactly the argmax-consistent class, although every tree remains pointwise consistent at full-support distributions.Thus branching is the obstruction globally, but not in the simplex interior.
- The four-point star and five-point K2,3 examples separate boundary and full-support failures under the common-geodesic condition.The star is minimal but uses a boundary distribution; K2,3 is the smallest full-support obstruction, while Km,n provides an infinite family.
- A classification beyond tree metrics, such as finite median metric spaces, remains open.The paper identifies this as a direction for determining when the common-geodesic condition becomes sufficient.
- An explicit calibrated link for tree and median-type metrics could potentially preserve efficient loss-augmented inference while repairing prediction.This is presented as a possible future direction rather than an established result.
- The decoder must be checked on every conditional optimal set, including nonembedded faces caused by polyhedral degeneracy.Matching Bayes risks guarantees optimal loss values and embedded optimal reports, but not correct decoding of every surrogate minimizer.