A Consistent Regularization Approach for Structured Prediction

Abstract

We propose and analyze a regularization approach for structured prediction problems. We characterize a large class of loss functions that allows to naturally embed structured outputs in a linear space. We exploit this fact to design learning algorithms using a surrogate loss approach and regularization techniques. We prove universal consistency and finite sample bounds characterizing the generalization properties of the proposed methods. Experimental results are provided to demonstrate the practical usefulness of the proposed approach.

39 pages, 2 Tables, 1 Figure

Cited by in corpus (15)

• Consistent Multitask Learning with Nonlinear Output Relations
• On Fast Leverage Score Sampling and Optimal Learning
• A General Theory for Structured Prediction with Smooth Convex Surrogates
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings
• Kernel Instrumental Variable Regression
• Disambiguation of weak supervision with exponential convergence rates
• Geometric Losses for Distributional Learning
• Structured and Localized Image Restoration
• Structured Prediction with Partial Labelling through the Infimum Loss
• Fast rates in structured prediction
• Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels
• Structured Output Learning with Abstention: Application to Accurate Opinion Prediction
• Quantifying Learning Guarantees for Convex but Inconsistent Surrogates
• Learning Output Embeddings in Structured Prediction
• Distributionally Robust Graphical Models