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 optimized via
stochastic gradient descent and we prove tight bounds on the so-called
"calibration function" relating the excess surrogate risk to the actual risk.
In contrast to prior related work, we carefully monitor the effect of the
exponential number of classes in the learning guarantees as well as on the
optimization complexity. As an interesting consequence, we formalize the
intuition that some task losses make learning harder than others, and that the
classical 0-1 loss is ill-suited for general structured prediction.

本文提出一种新颖的理论框架，利用凸代理损失函数最小化，探讨结构化预测的相关问题，并提供一些保证与监测措施，同时说明了某些任务损失导致学习难度增加，因此普适性最强的 0-1 损失函数并不适用于一般化的结构化预测。

关于带有校准凸代理损失的结构化预测理论

On Structured Prediction Theory with Calibrated Convex Surrogate Losses

We develop an approach to risk minimization and stochastic optimization that
provides a convex surrogate for variance, allowing near-optimal and
computationally efficient trading between approximation and estimation error.
Our approach builds off of techniques for distributionally robust optimization
and Owen's empirical likelihood, and we provide a number of finite-sample and
asymptotic results characterizing the theoretical performance of the estimator.
In particular, we show that our procedure comes with certificates of
optimality, achieving (in some scenarios) faster rates of convergence than
empirical risk minimization by virtue of automatically balancing bias and
variance. We give corroborating empirical evidence showing that in practice,
the estimator indeed trades between variance and absolute performance on a
training sample, improving out-of-sample (test) performance over standard
empirical risk minimization for a number of classification problems.

通过使用分布鲁棒优化和 Owen 的经验似然的技术，我们开发了一种风险最小化和随机优化的方法，提供了一个凸代理来实现方差的降低，实现了近乎最优和计算效率之间的权衡，我们给出了一些有限样本和渐近结果来表征估计器的理论性能。