# Structured Prediction with Projection Oracles

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2019.

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [H-Consistency Guarantees for Regression](https://mlsanity.com/paper/2403.19480/) (2024)
- [Enhanced H-Consistency Bounds](https://mlsanity.com/paper/2407.13722/) (2024)
- [Surrogate Regret Bounds for Polyhedral Losses](https://mlsanity.com/paper/2110.14031/) (2021)
- [Sparse Continuous Distributions and Fenchel-Young Losses](https://mlsanity.com/paper/2108.01988/) (2021)
- [Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming](https://mlsanity.com/paper/2301.11260/) (2023)
- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [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)
- [Proper losses regret at least 1/2-order](https://mlsanity.com/paper/2407.10417/) (2024)
- [On the inconsistency of separable losses for structured prediction](https://mlsanity.com/paper/2301.10810/) (2023)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Trading off Consistency and Dimensionality of Convex Surrogates for the Mode](https://mlsanity.com/paper/2402.10818/) (2024)
- [Bandit and Delayed Feedback in Online Structured Prediction](https://mlsanity.com/paper/2502.18709/) (2025)
- [Consistency Conditions for Differentiable Surrogate Losses](https://mlsanity.com/paper/2505.13760/) (2025)
- [Non-Stationary Online Structured Prediction with Surrogate Losses](https://mlsanity.com/paper/2510.07086/) (2025)

## Abstract (arXiv)

We propose in this paper a general framework for deriving loss functions for structured prediction. In our framework, the user chooses a convex set including the output space and provides an oracle for projecting onto that set. Given that oracle, our framework automatically generates a corresponding convex and smooth loss function. As we show, adding a projection as output layer provably makes the loss smaller. We identify the marginal polytope, the output space's convex hull, as the best convex set on which to project. However, because the projection onto the marginal polytope can sometimes be expensive to compute, we allow to use any convex superset instead, with potentially cheaper-to-compute projection. Since efficient projection algorithms are available for numerous convex sets, this allows us to construct loss functions for a variety of tasks. On the theoretical side, when combined with calibrated decoding, we prove that our loss functions can be used as a consistent surrogate for a (potentially non-convex) target loss function of interest. We demonstrate our losses on label ranking, ordinal regression and multilabel classification, confirming the improved accuracy enabled by projections.