# Consistent Structured Prediction with Max-Min Margin Markov Networks

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2020.

## Built on by (most cited first, 9 of 9)

- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [Sparse Continuous Distributions and Fenchel-Young Losses](https://mlsanity.com/paper/2108.01988/) (2021)
- [Federated Asymptotics: a model to compare federated learning algorithms](https://mlsanity.com/paper/2108.07313/) (2021)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [On the Consistency of Max-Margin Losses](https://mlsanity.com/paper/2105.15069/) (2021)
- [On the inconsistency of separable losses for structured prediction](https://mlsanity.com/paper/2301.10810/) (2023)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [Some Robustness Properties of Label Cleaning](https://mlsanity.com/paper/2509.11379/) (2025)
- [Common Geodesics Do Not Guarantee Fisher Consistency of the Structured SVM: Minimal Counterexamples and a Tree-Metric Classification](https://mlsanity.com/paper/2608.27203/) (2026)

## Abstract (arXiv)

Max-margin methods for binary classification such as the support vector machine (SVM) have been extended to the structured prediction setting under the name of max-margin Markov networks (M3N), or more generally structural SVMs. Unfortunately, these methods are statistically inconsistent when the relationship between inputs and labels is far from deterministic. We overcome such limitations by defining the learning problem in terms of a "max-min" margin formulation, naming the resulting method max-min margin Markov networks (M4N). We prove consistency and finite sample generalization bounds for M4N and provide an explicit algorithm to compute the estimator. The algorithm achieves a generalization error of O(1/√n) for a total cost of O(n) projection-oracle calls (which have at most the same cost as the max-oracle from M3N). Experiments on multi-class classification, ordinal regression, sequence prediction and ranking demonstrate the effectiveness of the proposed method.