# A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2020.

## Built on by (most cited first, 30 of 35)

- [Sharp Spectral Rates for Koopman Operator Learning](https://mlsanity.com/paper/2302.02004/) (2023)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [PSD Representations for Effective Probability Models](https://mlsanity.com/paper/2106.16116/) (2021)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm](https://mlsanity.com/paper/2312.07186/) (2023)
- [AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation](https://mlsanity.com/paper/2409.20398/) (2024)
- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [Size-invariance Matters: Rethinking Metrics and Losses for Imbalanced Multi-object Salient Object Detection](https://mlsanity.com/paper/2405.09782/) (2024)
- [Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms](https://mlsanity.com/paper/2405.14778/) (2024)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimal](https://mlsanity.com/paper/2411.19653/) (2024)
- [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)
- [Operator World Models for Reinforcement Learning](https://mlsanity.com/paper/2406.19861/) (2024)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Vector-Valued Least-Squares Regression under Output Regularity Assumptions](https://mlsanity.com/paper/2211.08958/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Overcoming Saturation in Density Ratio Estimation by Iterated Regularization](https://mlsanity.com/paper/2402.13891/) (2024)
- [Disambiguation of weak supervision with exponential convergence rates](https://mlsanity.com/paper/2102.02789/) (2021)
- [A randomized algorithm to solve reduced rank operator regression](https://mlsanity.com/paper/2312.17348/) (2023)
- [Active Labeling: Streaming Stochastic Gradients](https://mlsanity.com/paper/2205.13255/) (2022)
- [Proper losses regret at least 1/2-order](https://mlsanity.com/paper/2407.10417/) (2024)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [Structured Prediction in Online Learning](https://mlsanity.com/paper/2406.12366/) (2024)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularization](https://mlsanity.com/paper/2106.08855/) (2021)
- [A Structured Prediction Approach for Robot Imitation Learning](https://mlsanity.com/paper/2309.14829/) (2023)
- [Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein Distance](https://mlsanity.com/paper/2309.16604/) (2023)
- [Bandit and Delayed Feedback in Online Structured Prediction](https://mlsanity.com/paper/2502.18709/) (2025)
- [A Kernel-based Stochastic Approximation Framework for Nonlinear Operator Learning](https://mlsanity.com/paper/2509.11070/) (2025)

## Abstract (arXiv)

We propose and analyze a novel theoretical and algorithmic framework for structured prediction. While so far the term has referred to discrete output spaces, here we consider more general settings, such as manifolds or spaces of probability measures. We define structured prediction as a problem where the output space lacks a vectorial structure. We identify and study a large class of loss functions that implicitly defines a suitable geometry on the problem. The latter is the key to develop an algorithmic framework amenable to a sharp statistical analysis and yielding efficient computations. When dealing with output spaces with infinite cardinality, a suitable implicit formulation of the estimator is shown to be crucial.