Structured Prediction with Stronger Consistency Guarantees
We present an extensive study of surrogate losses for structured prediction supported by *$H$-consistency bounds*. These are recently introduced guarantees that are more relevant to learning than Bayes-consistency, since they are not asymptotic and since they take into account the hypothesis set $H$ used. We first show that no non-trivial $H$-consistency bound can be derived for widely used surrogate structured prediction losses. We then define several new families of surrogate losses, including *structured comp-sum losses* and *structured constrained losses*, for which we prove $H$-consistency bounds and thus Bayes-consistency. These loss functions readily lead to new structured prediction algorithms with stronger theoretical guarantees, based on their minimization. We describe efficient algorithms for minimizing several of these surrogate losses, including a new *structured logistic loss*.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On Structured Prediction Theory with Calibrated Convex Surrogate Losses
We provide novel theoretical insights on structured prediction in the context of efficient convex surrogate loss minimization with consistency guarantees. For any task loss, we construct a convex surrogate that can be op…
PredictionStructured PredictionRisk Guarantees for End-to-End Prediction and Optimization Processes
Prediction models are often employed in estimating parameters of optimization models. Despite the fact that in an end-to-end view, the real goal is to achieve good optimization performance, the prediction performance is …
Learning TheoryPortfolio OptimizationPredictionTop-$k$ Classification and Cardinality-Aware Prediction
We present a detailed study of top-$k$ classification, the task of predicting the $k$ most probable classes for an input, extending beyond single-class prediction. We demonstrate that several prevalent surrogate loss fun…
ClassificationMulti-class ClassificationPredictionSublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions
Over the past decade, deep neural networks (DNNs) have achieved remarkable success on complex machine-learning tasks, yet the theoretical foundations of their performance remain incomplete. From a statistical viewpoint, …
Image ClassificationEfficient and Consistent Adversarial Bipartite Matching
Many important structured prediction problems, including learning to rank items, correspondence-based natural language processing, and multi-object tracking, can be formulated as weighted bipartite matching optimiza…
Computational EfficiencyLearning-To-RankMulti-Object TrackingObject Tracking+1