PaperlayerView exact revision on arXiv

Source-linked AI summary

A General Theory for Structured Prediction with Smooth Convex Surrogates

Alex Nowak-Vila, Francis Bach, Alessandro Rudi

arXiv:1902.01958v2cs.LGcs.AIstat.ML

TL;DR

Direct minimization of discrete structured losses can be intractable, and the paper develops a smooth-convex-surrogate framework based on loss structure, a Bregman divergence, and a link function. It derives calibration and learning guarantees, including exact calibration results for quadratic surrogates and a lower bound for CRFs.

  • Problem

    Discrete structured task losses can be intractable to minimize directly, motivating practical continuous surrogate losses for structured prediction.

    Source: §1 · p. 1

  • Method

    The paper characterizes task-loss structure with affine decompositions and builds smooth convex surrogates whose excess risk is represented by a Bregman divergence composed with a link.

    Source: §1 · p. 2, §3.1 · p. 5

  • Results

    The framework provides an exact calibration-function formula and a quadratic lower bound for strongly convex potentials, with specific-method guarantees including exact quadratic-surrogate calibration and a CRF lower bound.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework derives learning guarantees for specific methods across multiple tasks, while also recovering existing results.

    Source: §1 · p. 2

    Exact computation of the calibration function can be hard when embeddings are difficult to work with or the problem lacks symmetries.

    Source: §4.2 · p. 9

Abstract

from arXiv · show

In this work we provide a theoretical framework for structured prediction that generalizes the existing theory of surrogate methods for binary and multiclass classification based on estimating conditional probabilities with smooth convex surrogates (e.g. logistic regression). The theory relies on a natural characterization of structural properties of the task loss and allows to derive statistical guarantees for many widely used methods in the context of multilabeling, ranking, ordinal regression and graph matching. In particular, we characterize the smooth convex surrogates compatible with a given task loss in terms of a suitable Bregman divergence composed with a link function. This allows to derive tight bounds for the calibration function and to obtain novel results on existing surrogate frameworks for structured prediction such as conditional random fields and quadratic surrogates.

1. Introduction

Structured prediction uses discrete structured outputs whose task losses can be intractable to minimize directly, motivating continuous surrogate losses. The paper develops smooth convex surrogates for these losses and derives calibration and learning guarantees, including results for quadratic surrogates and CRFs.

1. Introduction

  • Directly minimizing discrete structured task losses is intractable even for binary 0-1 loss, motivating continuous surrogate losses and decoding back to discrete outputs.Structured outputs include sequences, images, and graphs.Source: §1 · p. 1
  • The framework generalizes conditional-probability estimation methods to general discrete losses by combining affine loss decompositions with Bregman-divergence characterizations.The paper relates the construction to proper composite losses for multiclass classification.Source: §1 · p. 2
  • The theory gives an exact calibration-function formula and a quadratic lower bound for strongly convex potentials, relating surrogate risk to task risk.The calibration function depends on the surrogate through its potential.Source: §1 · p. 2
  • Learning guarantees distinguish the roles of the potential and link: excess-risk relations depend on the potential, while approximation error depends crucially on the link.The paper discusses benefits of logistic-type over quadratic-type surrogates.Source: §1 · p. 2
  • For specific methods across multiple tasks, the paper derives learning guarantees while recovering existing results, including exact quadratic-surrogate calibration and a quadratic lower bound for CRFs.These are identified as the most significant novel results in this direction.Source: §1 · p. 2

2. Setting

The setting measures predictions by expected task loss and excess risk, then represents discrete losses through embeddings and an associated marginal polytope. The decomposition applies to both multiclass 0-1 loss and multilabel Hamming loss.

2.1. Supervised Learning

  • Supervised learning predicts an output from an input using a loss, with the goal of minimizing expected risk and evaluating estimators by excess risk.The framework allows the prediction space to differ from the observation space.Source: §2.1 · pp. 2–3
  • For a label distribution q, the Bayes risk is the expected task loss, and excess Bayes risk measures the gap from the best prediction.Source: §2.1 · p. 3

2.2. Affine Decomposition of Discrete Losses and Marginal Polytope

  • An affine decomposition represents the loss using output and label embeddings; the expected label embedding gives moments, and their convex hull forms the marginal polytope.The decomposition always exists but need not be unique, and the polytope can have lower dimension than the embedding space.Source: §2.2 · p. 3
  • Multiclass 0-1 loss has a simplex marginal polytope of dimension k−1, while multilabel Hamming loss has a full-dimensional cube marginal polytope.Source: §2.2 · pp. 3–4

3. Surrogate Framework

The framework estimates task-relevant moments with smooth convex surrogate losses and decodes predictions through a link function. Surrogate excess risk has a Bregman-divergence representation, and extending that representation across the surrogate space defines ϕ-calibrated losses with consistency and risk guarantees.

3.1. Estimation of the Bayes Risk with Surrogate Losses

  • Estimating the conditional moment vector with a surrogate loss yields a Bayes-risk estimate, and decoding converts the surrogate estimator into a task prediction.The surrogate method consists of the loss and its decoding map; inference complexity can depend on the task loss.Source: §3.1 · pp. 4–5
  • A link maps moments to surrogate predictions, while smoothness relates to link injectivity and convexity supports tractable risk minimization.The link also encodes the constrained geometry of the marginal polytope so the decoding rule can operate on surrogate outputs.Source: §3.1 · pp. 4–5

3.2. Bregman Divergence Representation

  • Any continuous surrogate satisfying the moment-link condition with a continuous injective link has a Bregman-divergence representation on t(M).The representation uses a strictly convex differentiable potential and an invertible link.Source: §3.2 · pp. 5–6

3.3. ϕ-Calibrated Surrogates

  • A surrogate is ϕ-calibrated when its Bregman-divergence representation extends from t(M) to the whole surrogate space, enabling decoding there.Not every surrogate satisfying the moment-link condition admits such an extension.Source: §3.3 · p. 6
  • A ϕ-calibrated loss is Fisher consistent for losses with the corresponding label embedding, and changing the inference embedding can adapt it to different cost-sensitive losses.When ϕ(y)=e_y, the framework can estimate the Bayes risk for any loss with labels Y.Source: §3.3 · p. 7
  • The potential supplies the excess-risk guarantees, whereas inference uses the inverse link to estimate moments and otherwise depends on the task embedding.The paper gives a procedure for checking calibration by testing the moment-link condition and whether the Bregman representation extends.Source: §3.3 · p. 7
  • For Legendre-type potentials, the canonical link is the potential gradient, whose inverse is the gradient of the Fenchel conjugate; quadratic surrogates and CRFs are key examples.Their associated domains are respectively the embedding space and the marginal polytope.Source: §3.3 · pp. 7–8

4. Theoretical Analysis

The section uses calibration functions to quantify how surrogate-risk minimization controls true-risk error, then develops sharper guarantees under low-noise assumptions and analyzes stochastic surrogate minimization.

4.1. Calibrating Risks with the Calibration Function

  • The calibration function is the infimum surrogate excess Bayes risk among cases whose true excess Bayes risk is at least ε; convex lower bounds transfer this relation to overall risks.Its tightest convex lower bound is the lower convex envelope, and positivity of that envelope for every ε>0 characterizes Fisher consistency.Source: §4.1 · pp. 8–9

4.2. Calibration Function for ϕ-Calibrated Losses

  • The calibration function for ϕ-calibrated losses has an exact geometric formula in terms of Bregman divergences between calibration sets.The formula depends on the surrogate through its potential h; the sets encode predictions with optimal versus ε-near-optimal Bayes risk.Source: §4.2 · p. 9
  • For strongly convex potentials, the paper gives a user-friendly lower bound, while twice differentiability ensures ζh(ε)=O(ε^2) near zero.Exact computation can remain difficult because the minimization may be nonconvex, especially when embeddings are complex or symmetries are absent.Source: §4.2 · p. 9

4.3. Improved Calibration under Low Noise Assumption

  • Under the p-noise condition (22), ¯ζ(p) satisfies Eq. (18) and ¯ζ(p) ≳ ¯ζ; condition (22) holds iff ∥1/γ∥Lp(ρX)=γp<∞.If γ(x)≥δ>0 ρX-a.s. and δv(bg(x),ρ(·|x))<ζ(δ) ρX-a.s., then E(d◦bg)=E(f⋆).Source: §4.3 · p. 10
  • As the noise exponent p increases, the calibration lower bound moves from quadratic behavior with no noise assumption toward linear behavior near the decision boundary.The p=0 case imposes no noise assumption, while p→∞ corresponds to a positive hard margin.Source: §4.3 · p. 10

4.4. Minimizing the Surrogate Loss with Averaged Stochastic Gradient Descent (ASGD)

  • The ASGD analysis bounds expected true excess risk at order n^-1/4 under the stated RKHS and strong-convexity conditions.The bound depends on quantities associated with the task loss, potential, domain, and link.Source: §4.4 · pp. 11–12
  • The link affects approximation complexity: logistic-type links can smooth conditional means near the marginal-polytope boundary and reduce the norm required of the RKHS predictor.Quadratic-type methods estimate the conditional mean directly, so their hypothesis space must model the marginal-polytope constraint.Source: §4.4 · p. 12

5. Analysis of Existing Surrogate Methods

The section applies the framework to generic surrogates and supervised-learning tasks, deriving calibration guarantees for existing methods across classification, ordinal prediction, ranking, and graph matching.

5.1. Optimizing generic losses: Quadratic surrogate vs. CRFs

  • The quadratic surrogate has an exact calibration function when M is full-dimensional, recovers a comparison inequality from [15], and can extend to continuous losses using kernel ridge regression.Its potential is 1-strongly convex in the Euclidean norm, yielding the stated quadratic lower bound.Source: §5.1 · pp. 12–13
  • The proposed decoder calibrates CRFs to losses decomposing with the model's cliques, unlike MAP decoding; for linear chains, it handles any loss depending on neighbors.Proposition 5.2 provides a lower bound on the CRF calibration function.Source: §5.1 · p. 13

Binary Classification.

  • Logistic, exponential, and square margin losses are ϕ-calibrated under sign decoding for binary classification.The passage introduces margin losses of the form S(v, y) = Φ(yv).Source: Binary Classification · p. 13

Multiclass Classification.

  • For one-vs-all, ζh(ε) = 2 · ζ¯h(ε) when ¯h′′ is non-decreasing on ¯D ∩ [1/2, +∞); multinomial logistic has ζh(ε) ≥ ε2/8.The assumption holds for logistic, exponential, and square binary margin losses; both methods use argmax decoding.Source: Multiclass Classification · pp. 13–14
  • For independent multilabel classifiers, the calibration function is exactly k · ζ¯h(ε), linear in the number of labels.The potential is a sum of the individual classifier potentials, and decoding applies the sign function label by label.Source: Multiclass Classification · p. 14

Ordinal Regression.

  • For ordinal absolute error, the bounds scale as ε2/(k − 1) for all-threshold methods and ε2/(k − 1)2 for cumulative-link methods; the paper connects this to stronger empirical calibration for all-threshold methods.The cumulative-link potential is negative entropy on the k-dimensional simplex.Source: Ordinal Regression · p. 14
  • For NDCG ranking, the paper recovers existing guarantees for learning permutations.The passage identifies the loss as NDCG.Source: Ordinal Regression · p. 14

Graph matching.

  • For graph matching with row-wise multinomial logistic regression, the calibration function satisfies ζh(ε) ≥ m2ε2/8.The setup treats each row as a multiclass problem; its row-stochastic domain strictly includes the doubly stochastic marginal polytope.Source: Graph matching · p. 14

D. General Results for the Calibration Function

The appendix develops a Bregman-divergence representation for surrogate risks and supports differentiability of the associated potential through continuity arguments.

A. Bregman Divergence Representation of Surrogate Losses

  • A loss eliciting a linear function of a distribution admits a strictly convex potential, and the excess risk can be expressed as a Bregman divergence.The divergence uses a selection of subgradients in the tangent space of the marginal polytope.Source: A. Bregman Divergence Representation… · p. 20
  • Continuity of the surrogate risk makes the excess risk and associated affine terms continuous in the moment argument.The proof uses these continuity properties to establish differentiability of the potential.Source: A. Bregman Divergence Representation… · p. 21
  • The proof rules out distinct subgradients at a point by constructing a segment along which the associated function would fail to be continuous.The argument derives a contradiction at the segment parameter t = 1/2.Source: A. Bregman Divergence Representation… · p. 21

B. Functions of Legendre-type and Canonical Link

The paper uses Legendre-type potentials and their Fenchel conjugates to construct smooth convex surrogate losses, then relates surrogate and task risks through calibration bounds.

B. Functions of Legendre-type and Canonical Link

  • Legendre-type functions are strictly convex in their interior and essentially smooth; the paper highlights the quadratic and negative maximum-entropy examples.The quadratic domain is H, while the negative maximum-entropy potential is defined over the marginal polytope.Source: B. Functions of Legendre-type and… · p. 21
  • Fenchel conjugacy preserves the Legendre-type property, and the gradients of h and h∗ are inverse maps on their stated domains.The conjugate of negative maximum-entropy is log-sum-exp.Source: B. Functions of Legendre-type and… · p. 22
  • The construction associates a surrogate loss to a Legendre-type potential and uses its gradient as the link; the resulting loss is convex and its excess risk is a Bregman divergence.The divergence representation holds in both D and dom(h∗).Source: B. Functions of Legendre-type and… · pp. 21–22
  • The framework's examples include quadratic-surrogate and CRF losses, corresponding respectively to quadratic and negative-entropy potentials.Both are identified as Legendre-type surrogate losses.Source: B. Functions of Legendre-type and… · pp. 21–22

C. Calibration of Risks

  • A convex lower bound on the calibration function bounds task excess risk by surrogate excess risk; a low-noise assumption at the decision boundary improves calibration between risks.The appendix identifies Jensen's inequality in the proof of the no-noise comparison.Source: C. Calibration of Risks · p. 22, §C.1 · p. 23

C.2. Calibration of Risks with Low Noise Assumption

The low-noise analysis extends margin-based risk calibration to general discrete losses, while the calibration-function results express surrogate guarantees through Bregman divergence and decision-region geometry.

C.2. Calibration of Risks with Low Noise Assumption

  • The p-noise condition generalizes Tsybakov’s binary condition to general discrete losses and is equivalent to 1/γ∈Lp(ρX).Source: §C.2 · p. 23
  • When 1/γ∈Lp(ρX), Lemma C.2 bounds the probability of the error set by a power of excess risk.Source: §C.2 · p. 23
  • The risk proof splits inputs into low- and high-noise regions, controlling them respectively with the p-noise assumption and a convex lower bound on the calibration function.Source: §C.2 · p. 24

D.1. Exact Formula for the Calibration Function

  • For ϕ-calibrated surrogates, ζ_h is a constrained minimum of h’s Bregman divergence, and Theorem 4.3 recasts it as a divergence between decision regions.Source: §D.1 · pp. 25–26

D.2. Lower Bounds on the Calibration Function

The section develops lower bounds on the calibration function under strong convexity, an upper-bound argument near the marginal polytope’s relative interior, and then turns to quadratic surrogates and CRFs.

D.2. Lower Bounds on the Calibration Function

  • Theorem D.4 gives a tighter calibration-function lower bound under Euclidean strong convexity than Theorem 4.4’s bound.Source: §D.2 · p. 28

D.3. Upper bound on the Calibration Function

  • The upper-bound proof constructs a path inside the marginal polytope’s relative interior, where the Hessian stays bounded; it notes that the Hessian may explode at the boundary.Source: §D.3 · pp. 28–29

E. Generic Methods for Structured Prediction

E.1. Quadratic Surrogate

For a full-dimensional marginal polytope, the paper derives an exact calibration formula for the quadratic surrogate and compares its framework with a different quadratic construction.

E.1. Quadratic Surrogate

  • For full-dimensional M, Theorem E.1 gives the exact calibration function for the quadratic surrogate.Source: §E.1 · p. 30
  • For the Hamming-loss comparison, the two calibration functions are equal when F is the identity; for other F, they are not comparable.Source: §E.1 · p. 31
  • The compared surrogate of [16] is larger by construction, since it is defined in R^Y while the paper’s surrogate is defined in R^k.Source: §E.1 · p. 32
  • The paper says its surrogates are used in practice, whereas the compared construction requires summation over |Y| elements, which is generally exponentially large in structured prediction.Source: §E.1 · p. 32

E.2. Conditional Random Fields

For CRFs, the proposed decoding changes MAP assignment to calibrate the method to discrete losses with an affine loss decomposition. The section also presents a calibration lower bound.

E.2. Conditional Random Fields

  • Changing CRF decoding from MAP assignment to the proposed rule makes CRFs calibratable to any discrete loss with an affine decomposition using the CRF’s sufficient statistics.Source: §E.2 · p. 32
  • The section also proves a convex calibration lower bound for CRFs, using the Euclidean strong-convexity constant of the negative maximum-entropy potential.Source: §E.2 · pp. 32–33
  • MAP assignment does not calibrate CRFs to any discrete loss in general, whereas the corresponding decoding for multinomial logistic regression and multiclass 0-1 loss is exactly MAP.Source: §E.2 · p. 32

F. Binary Classification

The binary-classification examples examine how margin losses yield Bregman-divergence representations and calibration guarantees, including where those representations do not extend beyond the link’s image. The section also sets up multiclass 0-1 loss and its calibration sets.

F. Binary Classification

  • For cost-sensitive binary classification, the decoding rule is d(v) = sign(2q − c), with q = P(Y = 1) and 0 < c ≤ 1.The link is t(q) = 2q − 1, with inverse t−1(v) = (v + 1)/2.Source: F. Binary Classification · pp. 33–34
  • For binary margin losses, logistic, exponential, and square losses are ϕ-calibrated; squared hinge and modified Huber have a Bregman representation only on t(∆2), while hinge fails the required condition because its link is not injective.The squared-hinge and modified-Huber representations cannot be extended to V = R.Source: F. Binary Classification · pp. 33–35
  • For the non-cost-sensitive binary 0-1 loss, the calibration function simplifies to ζh(ε) = h((1 + ε)/2) − h(1/2) when h is symmetric around 1/2.The section gives the general cost-sensitive formula as a minimum of two Bregman divergences.Source: F. Binary Classification · pp. 34–35

G. Multiclass Classification

  • The multiclass 0-1 loss uses the simplex as its marginal polytope, and Figure 4 illustrates its calibration sets for three labels.The loss is expressed as L(z, y) = 1 − ⟨ez, ey⟩.Source: G. Multiclass Classification · p. 36

G.1. One-vs-all Method

The one-vs-all construction builds multiclass potentials and links from coordinate-wise margin-loss components, and inherits calibration when the margin loss is ϕ-calibrated. The section also presents multinomial logistic regression and begins the Hamming-loss setup.

G.1. One-vs-all Method

  • A ϕ-calibrated margin loss yields a ϕ-calibrated one-vs-all multiclass method, with coordinate-wise potential and link and decoding d(v) = arg maxj vj.Its marginal polytope ∆k is a strict subset of the domain D = ¯Dk.Source: §G.1 · p. 36
  • The one-vs-all calibration function reduces by symmetry to a Bregman-divergence minimization comparing two coordinates, with a minimizing pair supported on those coordinates.The stated minimizers are q⋆ = (1/2, 1/2, 0, …, 0) and p⋆ = ((1 + ε)/2, (1 − ε)/2, 0, …, 0).Source: §G.1 · p. 36

G.2. Multinomial Logistic

  • For multinomial logistic regression, entropy is 1-strongly convex with respect to the ∥·∥1 norm on the simplex, allowing the framework’s theorem to give a calibration-function lower bound.Source: §G.2 · p. 37

H. Multilabel Classification with Hamming Loss

H.1. Independent Classifiers

The paper applies its surrogate framework to independent multilabel classifiers, ordinal regression, ranking, and graph matching. Across these settings, it derives calibration results and identifies how loss structure, embedding geometry, and inference requirements shape the guarantees.

H.1. Independent Classifiers

  • For independent classifiers under Hamming loss, the calibration function is exactly k times the calibration function of the underlying margin loss.The proof establishes that the lower bound is tight.Source: §H.1 · p. 38

I. Ordinal Regression

  • An embedding of ordinal outputs into [−1, 1]k−1 gives calibration sets with the same structure as Hamming loss on k − 1 labels, although the ordinal marginal polytope is a strict subset of the cube.Source: §I · p. 39

I.1. All thresholds (AT)

  • All-threshold methods use an independent classifier on the ordinal embedding, yielding a calibration bound based on the Hamming-loss calibration function and the ordinal loss’s (k − 1) scaling.The method’s marginal polytope is contained in the cube, so the bound’s minimization is over a smaller domain.Source: §I.1 · p. 39

I.2. Cumulative link (CL)

  • For cumulative-link methods, the exact calibration function is difficult to calculate, and the strongly-convexity lower bound has factor (k − 1)^-2 rather than the AT bound’s (k − 1)^-1.The cited comparison says prior experiments found the AT calibration function larger than the CL calibration function.Source: §I.2 · p. 40

J. Ranking with NDCG Measure

  • For NDCG ranking, the framework recovers existing surrogate guarantees, including Fisher consistency by construction and the same calibration lower bound and low-noise improvement as the cited method.The passage attributes those latter guarantees to.Source: J. Ranking with NDCG Measure · p. 41

K. Graph Matching

  • For graph matching, canonical-link CRFs require inference corresponding to computing the permanent, a #P-complete problem; a proposed workaround estimates rows independently and then applies linear assignment.Source: K. Graph Matching · pp. 41–42
Loading 1902.01958v2…