Papers › Consistent Structured Prediction with Max-Min Margin Markov Networks
Consistent Structured Prediction with Max-Min Margin Markov Networks
Alex Nowak-Vila, Francis Bach, Alessandro Rudi
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 (M³N), 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 (M⁴N). We prove consistency and finite sample generalization bounds for M⁴N 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 M³N). Experiments on multi-class classification, ordinal regression, sequence prediction and ranking demonstrate the effectiveness of the proposed method.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections