# Structured Prediction Theory Based on Factor Graph Complexity

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2016.

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

- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [Learning with Multiclass AUC: Theory and Algorithms](https://mlsanity.com/paper/2107.13171/) (2021)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data](https://mlsanity.com/paper/2502.10381/) (2025)
- [On Learning Latent Models with Multi-Instance Weak Supervision](https://mlsanity.com/paper/2306.13796/) (2023)
- [Improved Balanced Classification with Theoretically Grounded Loss Functions](https://mlsanity.com/paper/2512.23947/) (2025)
- [Generalization for multiclass classification with overparameterized linear models](https://mlsanity.com/paper/2206.01399/) (2022)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Fine-grained Generalization Analysis of Structured Output Prediction](https://mlsanity.com/paper/2106.00115/) (2021)
- [A Theoretical Framework for Modular Learning of Robust Generative Models](https://mlsanity.com/paper/2602.17554/) (2026)
- [On Regularization and Inference with Label Constraints](https://mlsanity.com/paper/2307.03886/) (2023)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Optimized Deferral for Imbalanced Settings](https://mlsanity.com/paper/2604.27723/) (2026)
- [Reducing Class-Wise Performance Disparity via Margin Regularization](https://mlsanity.com/paper/2602.00205/) (2026)
- [Learning Rates for Nonconvex Pairwise Learning](https://mlsanity.com/paper/2111.05232/) (2021)
- [InFi: End-to-End Learning to Filter Input for Resource-Efficiency in Mobile-Centric Inference](https://mlsanity.com/paper/2209.13873/) (2022)
- [Generalization Analysis on Learning with a Concurrent Verifier](https://mlsanity.com/paper/2210.05331/) (2022)
- [Beyond Binary: Continuous State Optimization with Graph-Structured Objectives](https://mlsanity.com/paper/2608.09366/) (2026)

## Abstract (arXiv)

We present a general theoretical analysis of structured prediction with a series of new results. We give new data-dependent margin guarantees for structured prediction for a very wide family of loss functions and a general family of hypotheses, with an arbitrary factor graph decomposition. These are the tightest margin bounds known for both standard multi-class and general structured prediction problems. Our guarantees are expressed in terms of a data-dependent complexity measure, factor graph complexity, which we show can be estimated from data and bounded in terms of familiar quantities. We further extend our theory by leveraging the principle of Voted Risk Minimization (VRM) and show that learning is possible even with complex factor graphs. We present new learning bounds for this advanced setting, which we use to design two new algorithms, Voted Conditional Random Field (VCRF) and Voted Structured Boosting (StructBoost). These algorithms can make use of complex features and factor graphs and yet benefit from favorable learning guarantees. We also report the results of experiments with VCRF on several datasets to validate our theory.