Learning with Fenchel-Young Losses

Mathieu Blondel; André F. T. Martins; Vlad Niculae

Source-linked AI summary

Learning with Fenchel-Young Losses

Mathieu Blondel, André F. T. Martins, Vlad Niculae

arXiv:1901.02324v2Jan 8, 2019stat.MLcs.LG

TL;DR

Loss functions have been developed for many supervised tasks, and understanding their principles matters for choosing and designing them. This paper introduces Fenchel-Young losses, a generic construction of convex losses for regularized prediction functions, and shows they unify many existing losses while connecting sparsity with separation margins.

Problem
Understanding shared principles across losses for different supervised tasks and their associated prediction models matters for choosing and designing losses.
Source: §1 · pp. 1–2
Method
The paper uses output regularization and convex duality to construct a loss associated with any regularized prediction function.
Source: §1 · p. 2
Results
Fenchel-Young losses unify many existing losses across tasks; sparse distributions are tightly connected to losses with separation margins, precisely those not expressible as proper composite losses.
Source: §11 · p. 46
Takeaways & Limitations
The paper provides computational tools for efficiently learning with Fenchel-Young losses in unstructured and structured settings.
Source: §11 · p. 47
The paper does not address whether Fenchel-Young losses are consistent surrogates for possibly non-convex losses.
Source: §10.1 · p. 46

Abstract

from arXiv · show

Over the past decades, numerous loss functions have been been proposed for a variety of supervised learning tasks, including regression, classification, ranking, and more generally structured prediction. Understanding the core principles and theoretical properties underpinning these losses is key to choose the right loss for the right problem, as well as to create new losses which combine their strengths. In this paper, we introduce Fenchel-Young losses, a generic way to construct a convex loss function for a regularized prediction function. We provide an in-depth study of their properties in a very broad setting, covering all the aforementioned supervised learning tasks, and revealing new connections between sparsity, generalized entropies, and separation margins. We show that Fenchel-Young losses unify many well-known loss functions and allow to create useful new ones easily. Finally, we derive efficient predictive and training algorithms, making Fenchel-Young losses appealing both in theory and practice.

1. Introduction

The paper introduces Fenchel–Young losses as a principled way to construct losses from regularized prediction functions, unifying existing losses and enabling new ones across diverse prediction domains. It develops this framework in response to gaps in existing loss theory and the ad hoc derivation of sparsemax.

Introduction

Loss functions serve regression, classification, ranking, and structured prediction, but not every loss fits the proper-composite framework for probabilistic classification.The hinge loss is a notable exception, and any loss enjoying a separation margin cannot be written as a composite proper loss.Source: §1 · pp. 1–2
The framework addresses sparsemax, introduced by Martins and Astudillo (2016), whose sparse probability outputs can aid interpretability or computational efficiency but were derived ad hoc and remain poorly understood.The paper asks whether sparsemax can be generalized in a principled way.Source: §1 · p. 2
Fenchel–Young losses use convex duality to automatically construct a loss for any regularized prediction function, recovering many existing losses and extending to structured domains.The framework also encourages geometric design of outputs, including over convex polytopes and cones.Source: §1 · p. 2
This paper provides a comprehensive study beyond Niculae et al. (2018) and Blondel et al. (2019), adding positive-measure losses, training algorithms, Fenchel-Youngization, and ranking losses.It also unifies structured prediction losses through a geometric treatment of convex polytopes and proves the unit separation margin of SparseMAP (Proposition 8).Source: §1 · pp. 2–3

2. Regularized prediction functions

Regularized prediction functions map model scores to outputs by optimizing over a chosen domain with an output regularizer. Their examples and properties connect output structure, score ordering, and dual optimization.

2.1 Definition

A model maps x to scores θ, and regularized prediction maps scores to outputs; its domain may be arbitrary, including convex hulls and conic hulls.The framework also permits other domains beyond convex hulls.Source: §2.1 · pp. 4–6
Regularization acts on outputs, balancing score affinity against a confidence penalty; domain and penalty choices shape output form, sparsity, prior or cost use, and computational tractability.The framework is designed so users can choose and compute a regularized prediction function, then construct an associated loss.Source: §2.1 · pp. 4–6

2.2 Examples

Argmax yields a one-class vertex, softmax a dense simplex distribution, sparsemax can assign exact zeros in O(d), and coordinate-wise sigmoid yields an unnormalized positive measure.Sparsemax may reach the simplex boundary, unlike softmax, which lies in its relative interior.Source: Figure 2 · p. 7, §2.2 · p. 7

2.3 Gradient mapping and dual objective

A prediction is a subgradient of Ω* (and its gradient when Ω is strictly convex); decomposing Ω=Ψ+Φ yields a dual trade-off between support-function fit and proximity to θ.For Ω=Ψ+I_C, the support function of C captures the unregularized prediction objective.Source: §2.3 · p. 8

2.4 Properties

For symmetric Ω, predictions preserve coordinate permutations and score ordering; with strictly convex Ω, temperature t rescales scores by 1/t and tends to unregularized prediction as t→0, while classification argmax is preserved.The order-preservation property ensures that scores and predictions select the same highest-scoring class.Source: §2.4 · pp. 8–9

3. Fenchel-Young losses

The section defines Fenchel-Young losses for models with regularized prediction functions and develops their properties, links to Bregman divergences and Bayes risk, and cost-sensitive extensions.

3.1 Definition and properties

A regularized prediction function automatically defines a Fenchel-Young loss, and the prediction function also returns the prediction minimizing that loss.The loss can be written using the regularized prediction objective.Source: §3.1 · p. 9
Fenchel-Young losses are nonnegative and convex; under lower semi-continuous proper convexity they attain zero, and strict convexity makes zero loss equivalent to predicting the target.With strict convexity the loss gradient is the prediction residual; strong convexity makes the loss smooth. Non-negativity, convexity, and constant invariance also hold when Ω is not convex.Source: Properties · pp. 10–11
Temperature scaling rescales a Fenchel-Young loss as LtΩ(θ; y) = tLΩ(θ/t; y).Adding a constant to Ω leaves its associated loss unchanged.Source: Properties · p. 11

3.2 Relation with Bregman divergences

Fenchel-Young losses are not generally Bregman divergences composed with the regularized prediction, but form a mixed-space Bregman divergence using dual argument θ.Unlike a Bregman divergence, the loss allows an unrestricted left argument θ and remains convex in θ.Source: §3.2 · p. 12
For Legendre-type regularizers restricted to a convex set, prediction reduces to a Bregman projection, and the loss upper-bounds a composite Bregman divergence, including the sparsemax squared-error bound.The sparsemax case gives 1/2||y − sparsemax(θ)||² ≤ LΩ(θ; y).Source: §3.2 · pp. 13–14

3.3 Expected loss, Bayes risk and Bregman information

When the expected label lies in dom(Ω), the pointwise Bayes risk of a Fenchel-Young loss equals the Bregman information of the label distribution.Bregman information is the expected divergence from the random label to its mean.Source: §3.3 · pp. 14–15

3.4 Cost-sensitive losses

A fixed cost vector that may depend on ground-truth label y yields a cost-sensitive Fenchel-Young classification loss, recovering multiclass hinge, softmax-margin, and cost-augmented sparsemax losses.The 0/1 cost c_y = 1 − y can be used to impose a margin.Source: §3.4 · p. 15

4. Probabilistic prediction with Fenchel-Young losses

For multiclass classification over the probability simplex, Fenchel–Young prediction functions form generalized exponential families parameterized by scores and a regularizer. The section connects entropy-generated losses to their Bayes risks, probability consistency, and binary margin losses.

4.1 Fenchel-Young loss generated by a generalized entropy

Under A.1–A.3, generalized entropy is nonnegative and uniquely maximized by the uniform distribution; Fenchel–Young losses use its conjugate cumulant, with Shannon entropy yielding the log-partition function.Source: §4.1 · pp. 16–17
Strongly concave entropy yields a smoothed upper bound on perceptron loss, while Fenchel–Young losses remain convex even when maximizing the generalized prediction likelihood is non-concave.Source: §4.1 · p. 17

4.2 Expected loss, Bayes risk and Fisher consistency

The pointwise Bayes risk equals the generating entropy H(p), and the loss is Fisher consistent precisely when its predicted distribution equals p.Source: §4.2 · pp. 17–18

4.3 Examples

Several generalized entropies yield new losses; Shannon gives logistic loss, while Tsallis entropy connects α=1, 2, and ∞ to softmax, sparsemax, and argmax predictions, respectively.Source: §4.3 · pp. 18–19
For q>1, norm entropies satisfy A.1–A.3; their q→∞ limit is the Berger-Parker dominance index used to measure species diversity.Source: §4.3 · p. 19
Rényi entropies satisfy A.1–A.3 for β∈[0,1], whereas for β>1 they fail concavity but remain pseudo-concave.Source: §4.3 · p. 19

4.4 Binary classification case

Binary regularization induces symmetric margin losses; Shannon entropy gives logistic loss, and sparsemax loss extends modified Huber loss to multiclass classification.Source: §4.4 · p. 21

5. Separation margin of Fenchel-Young losses

Under A.1–A.3, the section characterizes when Fenchel–Young losses have a separation margin, connects margins to sparse predictive probabilities, and gives an analytic margin computation for twice-differentiable entropies.

Examples

The multiclass hinge loss has margin 1, sparsemax loss has a margin, and logistic loss does not.The logistic loss is strictly positive, while the hinge loss’s margin follows directly from its definition.Source: §5 · p. 22

Conditions for existence of margin

The loss L−H has a separation margin iff some m > 0 satisfies mek ∈ ∂(−H)(ek); when it does, the margin is the smallest such m.Source: §5 · p. 22

Relationship between sparsity and margins

Sparsity of the regularized predictor, meaning it can reach the simplex boundary, suffices for a margin and is necessary when H is uniformly separable.For general H, the result gives sufficiency but not necessity.Source: §5 · p. 23
Essentially smooth entropies such as Shannon reach only the simplex interior, preventing sparse predictions and margins; Tsallis entropies with α > 1 meet the stated boundary condition.For separable entropies, finite derivatives at the boundary allow predictions to attain boundary points.Source: §5 · p. 23

Margin computation

For twice-differentiable separable entropies, the margin has a closed-form characterization determined only by h’s slopes at 0 and 1.The section presents a simple closed-form expression for twice-differentiable generalized entropies.Source: §5 · p. 24

6. Positive measure prediction with Fenchel-Young losses

For positive-measure predictions, Fenchel–Young losses recover one-vs-all reductions and admit concrete loss instantiations. Uniformly separable regularizers yield coordinate-wise predictions and class-separable losses.

6.1 Uniformly separable regularizers and one-vs-all loss functions

Uniformly separable regularizers make predictions and losses coordinate-wise and class-separable, allowing the models for each class to be trained embarrassingly in parallel.Each coordinate can be interpreted as an unnormalized probability of its class.Source: §6.1 · p. 25
Fenchel–Young losses theoretically justify one-vs-all and using predictions as class-membership measures, as implemented in software packages.The loss is zero exactly when the regularized prediction equals the target.Source: §6.1 · p. 25
In binary classification, using scores [s, −s] recovers the same loss up to a factor of 2, making learning over the simplex equivalent to learning over the unit cube.Source: §6.1 · p. 25

6.2 Examples

The sigmoid prediction function yields the one-vs-all logistic loss.The associated regularizer is the negative binary entropy.Source: §6.2 · p. 26
Another example is a function described as a “sparse sigmoid.”Source: §6.2 · p. 26

7. Structured prediction with Fenchel-Young losses

For structured outputs represented in the convex hull of possible structures, the paper develops distribution- and mean-regularized prediction, illustrates Fenchel-Young losses across structured polytopes, and extends separation margins to structured outputs.

7.1 Distribution regularization, marginal inference and structured sparsemax

Distribution regularization yields marginal inference, the structured softmax counterpart, and structured sparsemax; maximum-entropy moment matching makes the underlying distribution unique and identifiable.For marginal inference, the maximum-Shannon-entropy distribution is Gibbs, and the resulting Fenchel-Young loss is the CRF loss; when Ω* is twice differentiable, its Hessian corresponds to the second moment.Source: §7.1 · pp. 26–27

7.2 Mean regularization and SparseMAP

Mean regularization replaces distribution-space optimization with a d-dimensional problem computable to arbitrary precision using a MAP oracle, and yields a representation supported on at most d structures.The representing distribution need not be unique.Source: §7.2 · p. 29

7.3 Examples

For sequences, Viterbi computes MAP inference in O(nm^2), while forward-backward computes marginal inference at the same cost; soft-DTW extends alignment prediction through entropic regularization over alignments.DTW computes alignment MAP inference in O(mn); replacing the hard minimum with a soft one gives marginal inference.Source: §7.3 · pp. 30–31
For directed spanning trees, MAP inference takes O(n^2) and marginal inference O(n^3); for ranking permutations, MAP inference sorts scores in O(d log d).The ranking construction includes simplex-based probabilistic classification, k-subsets, full rankings, and partial rankings.Source: §7.3 · pp. 31–32
For permutation matrices, marginal inference is #P-complete, but mean-regularized prediction uses efficient Birkhoff-polytope projections; the resulting Fenchel-Young loss is convex and can model instance similarities.With Ω(µ) = ⟨µ, log µ⟩, Sinkhorn computes the prediction; other regularizers can use Dykstra’s algorithm or dual approaches.Source: §7.3 · pp. 33–34

7.4 Structured separation margins

Under the sphere-radius assumption, a Fenchel-Young loss has a structured separation margin exactly when m y ∈ ∂Ω(y) for every output y; SparseMAP has unit margin.The margin is the smallest such m, and the structured margin framework includes losses such as the structured hinge loss.Source: §7.4 · pp. 34–35

8. Algorithms for learning with Fenchel-Young losses

The section presents generic primal and dual training algorithms for Fenchel–Young losses, alongside computational methods for regularized prediction functions and proximity operators. Together, these provide unified training procedures for existing and new losses.

8.1 Primal training

When the model is linear and parameter regularization is convex, primal training is convex; strongly convex Ω also makes the loss smooth, enabling global solution by proximal gradient methods.The method applies to linear models and neural networks; with homogeneous parameter regularization, temperature can be set to 1 during linear-model training, though test-time tuning may improve accuracy or control sparsity.Source: §8.1 · p. 36

8.2 Dual training

Dual training centers output regularization Ω and can be more efficient for linear models when n ≪ p; sparse proximity operators yield sparse dual variables useful for efficient kernelized prediction.Randomized block coordinate ascent converges to an optimum, linearly when the loss is smooth; for compact dom(Ω), block Frank–Wolfe avoids proximity operators.Source: §8.2 · pp. 36, 38

8.3 Regularized prediction functions

For regularized prediction, projected gradient may require difficult domain projections, while conditional gradient uses a linear maximization oracle and maintains sparse convex combinations of domain vertices.Conditional gradient converges sublinearly; variants can achieve linear rates, and for quadratic Ω an active-set method with approximate correction can converge finitely. For uniformly separable strictly convex Ω over the simplex, prediction can instead be computed in linear time by root finding.Source: §8.3 · p. 39

8.4 Proximity operators

Proximity operators can be computed by first-order methods through the Moreau decomposition using the regularized prediction function; the section also derives closed-form examples for perceptron and multiclass hinge losses.For Shannon negative entropy, the regularized prediction function has a softmax solution, whereas its proximity operator does not have a closed form.Source: §8.4 · pp. 40–41

9. Experiments

Experiments test Fenchel–Young losses’ ability to induce sparse probability distributions in label-proportion estimation and dependency parsing.

9.1 Label proportion estimation experiments

Root finding scales better than FISTA, with Brent’s method outperforming FISTA by one to two orders of magnitude.Solver times measure reaching a solution p with ∥p − p⋆∥2 < 10−5 over 200 sampled θ values.Source: Figure 9 · p. 42, §9.1 · p. 42
On real multi-label benchmarks, tuning α yields the best averaged rank overall among the tested Tsallis losses.The study reports test-set Jensen-Shannon divergence and mean squared error across seven standard datasets, selecting λ and α against validation data.Source: §9.1 · p. 42, Table 4 · p. 43
For 10 classes, Tsallis and sparsemax perform almost identically and both outperform softmax; for 50 classes, Tsallis losses outperform both.Results are reported for Jensen-Shannon divergence as document length varies; mean squared error results were described as entirely similar.Source: §9.1 · p. 42, Figure 10 · p. 43

9.2 Dependency parsing experiments

Across five languages, SparseMAP outperforms CRF and is competitive with structured SVM, substantially beating it on Chinese.The comparison uses structured SVM, CRF, and SparseMAP on arborescence-polytope models with gold tokenization and part-of-speech tags in a shared bi-LSTM parser. SparseMAP and structured SVM have margin 1, while SparseMAP and CRF are differentiable.Source: §9.2 · pp. 43–44, Table 5 · p. 44

10. Related work

The related work positions Fenchel–Young losses alongside proper losses and other convex-loss constructions, highlighting differences in convexity, links, and scope. It also relates the framework to prior uses of Fenchel duality and conditional-gradient inference, while noting that consistency was not addressed in this paper.

10.1 Loss functions

A regularization function Ω generates a proper loss with a Bregman-divergence representation; strictly proper losses uniquely recover the true probability and induce Fisher-consistent probability estimators.Sparsemax loss and the Brier score share the Gini index as their generating function.Source: §10.1 · pp. 44–45
Fenchel–Young losses are convex in unconstrained θ, unlike proper losses, and need neither an invertible link nor Legendre-type regularization, allowing losses such as hinge and sparsemax.Proper losses are not necessarily convex in their probability argument; Legendre-type regularization also precludes sparse probability distributions and margin losses.Source: §10.1 · p. 45
For Legendre-type Ω, Fenchel–Young and proper composite losses coincide up to a constant under the canonical inverse link, while composite losses can also use non-canonical links, as in AdaBoost’s exponential loss (Nowak-Vila et al., 2019).Composing a proper loss with an invertible link is not necessarily convex in θ; the canonical link ensures convexity.Source: §10.1 · p. 45
Related work includes simplex Fenchel–Young classification losses and entropy-based calibration, Tsallis-divergence losses for label-noise robustness (Amid and Warmuth, 2017), and f-divergence connections to surrogate losses.Earlier binary constructions based on Legendre transformations preclude non-invertible mappings (Nock and Nielsen, 2009).Source: §10.1 · p. 45
This paper leaves surrogate consistency of Fenchel–Young losses unaddressed; later sufficient conditions for composite and projection-based subsets show that Ω’s strong convexity is crucial.The passage situates this question within earlier multiclass and structured-prediction consistency research.Source: §10.1 · p. 46

10.2 Fenchel duality in machine learning

Earlier Fenchel-duality work addressed risk bounds, regret bounds, boosting, and representer theorems but did not propose losses; prior smoothing was per-loss and not linked to induced probabilities.This paper proposes a generic loss construction connecting smoothing or regularization to the probability distribution produced by regularized prediction functions.Source: §10.2 · p. 46

10.3 Approximate inference with conditional gradient algorithms

The paper uses conditional-gradient algorithms to compute regularized prediction functions and Fenchel–Young losses over complex output domains, building on their use for approximate marginal inference and distribution sampling.Combined with reproducing kernel Hilbert spaces, these methods are closely related to maximum mean discrepancy.Source: §10.3 · p. 46

11. Conclusion · A. Additional materials · A.1 Computing proximity operators by root finding

The conclusion presents output regularization and Fenchel duality as principles that unify existing losses and support new ones, while the appendix shows how proximity operators for uniformly separable generalized entropies can be computed by root finding.

11. Conclusion

Output regularization and Fenchel duality unify many existing losses and enable new losses across a broad range of tasks.Source: §11 · p. 46
Sparse distributions are tightly connected to losses with a separation margin, which are precisely the losses that cannot be written in proper composite loss form.Source: §11 · p. 46
The paper establishes computational tools for learning with Fenchel-Young losses in unstructured and structured settings, and anticipates further losses from other convex polytopes and regularizers.Source: §11 · p. 47

A.1 Computing proximity operators by root finding

For uniformly separable generalized entropies, the proximity operator reduces to unidimensional root finding.Source: §A.1 · p. 47
Because g(t) remains strictly convex even when h is only concave, Proposition 9 can be applied to compute the inverse proximity operator.Source: §A.1 · p. 47
For the first illustrated entropy, the inverse is expressed using the omega function after rearranging its defining equation.Source: §A.1 · pp. 47–48
For Tsallis entropy with α = 1.5, the derivation rules out t > x and rejects the solution t+ because t+ > x.Source: §A.1 · p. 48

A.2 Loss “Fenchel-Youngization” · B. Proofs · B.1 Proof of Proposition 1

The section constructs Fenchel–Young losses from entropies generated by general losses, yielding convex losses and potentially probabilistic prediction functions. It also gives pairwise-hinge entropy results and proves properties of the regularized prediction function.

A.2 Loss “Fenchel-Youngization”

A natural construction approximates any loss with a Fenchel–Young loss, which is convex and can support probabilistic prediction even when the original loss is not.The passage introduces the construction as a way to address losses that cannot themselves be written in Fenchel–Young form.Source: §A.2 · p. 48
The entropy generated by a loss is concave, including when the original loss is nonconvex.For zero-one loss, the generated entropy is 1 − max_j p_j, the Berger–Parker dominance index.Source: §A.2 · pp. 48–49
The section computes generated entropies for pairwise hinge, smoothed hinge, and squared hinge losses; the latter two results are new.The ordinary hinge result recovers Duchi et al. (2018, Example 5) with a simpler proof.Source: §A.2 · p. 49
For smoothed and squared hinge choices, the generated entropy is strictly concave, and its associated prediction function is typically sparse.The passage notes that a closed-form expression for the prediction function is not known.Source: §A.2 · p. 49
The constructed loss is bounded above by the tightest cost-augmented hinge loss in a family parametrized by θ′.This construction assumes the original loss achieves its minimum at 0.Source: §A.2 · pp. 49–50
If the original loss is bounded above by m, the constructed loss has margin at most m; if that margin is no larger than the original margin, zero constructed loss implies zero original loss.Source: §A.2 · p. 50

B.1 Proof of Proposition 1

For symmetric Ω, the proof establishes permutation symmetry of Ω* and shows that coordinate order in θ is preserved weakly by ∇Ω*(θ).It also shows that equal coordinates in θ yield equal coordinates in ∇Ω*(θ).Source: §B.1 · p. 50
When Y is contained in dom(Ω) and Ω is γ-strongly convex with range bounded by U − L, the proof bounds the approximation error using γ and U − L.The proof also notes that temperature scaling and constant invariance follow from properties of argmax.Source: §B.1 · p. 51

B.2 Proof of Proposition 3 · B.3 Proof of Proposition 4

The proofs characterize regularized predictions through Bregman projections, derive the composite Fenchel–Young form in a special case, and establish non-negativity and uniform maximization of H.

B.2 Proof of Proposition 3

When dom(Ψ*) = R^d and Ψ is Legendre type, ∇Ψ(∇Ψ*(θ)) = θ for every θ.This identity is used in the proof of Proposition 3.Source: §B.2 · p. 51
The regularized prediction is the Bregman projection of ∇Ψ*(θ) onto C ⊆ dom(Ψ).Source: §B.2 · p. 51
When C = dom(Ψ), the prediction is ∇Ψ*(θ) and the corresponding Bregman divergence is zero, yielding the composite Fenchel–Young form.Source: §B.2 · p. 51
The bound uses the Pythagorean theorem for Bregman divergences at the projection p = byΩ(θ) [Banerjee et al. (2005, Appendix A)].Source: §B.2 · p. 51

B.3 Proof of Proposition 4

Jensen’s inequality establishes that H is non-negative for every p ∈ △d.Source: §B.3 · p. 52
Jensen’s inequality also shows that H is maximized by the uniform distribution p = 1/d.Strict concavity makes p = 1/d the unique maximizer.Source: §B.3 · p. 52

B.4 Proof of Proposition 5 · B.5 Proof of Proposition 6

The proofs characterize the separation margin of LΩ through subgradients of Ω=−H at simplex vertices, then relate margin existence to simplex-wide subdifferentiability and conjugate-gradient coverage. For separable −H, these three conditions are equivalent.

B.4 Proof of Proposition 5

A subgradient θ∈∂Ω(e1) satisfies θ1=Ω*(θ)≥sup_{p∈△d}(⟨θ,p⟩−Ω(p)).The proof uses order preservation to consider e1 without loss of generality.Source: §B.4 · p. 52
LΩ(θ;e1)=0 exactly when θ1≥m+max_{j≠1}θj, provided me1∈∂Ω(e1).The proof obtains this equivalence from Proposition 2 and the subgradient property in Lemma 1.Source: §B.4 · pp. 52–53
The smallest margin m is determined by requiring −Ω(p)/(1−p1)≤m for every p∈△d, with p1=∥p∥∞ without loss of generality.This follows by requiring me1∈∂Ω(e1) and selecting the smallest m satisfying the resulting inequalities.Source: §B.4 · p. 53

B.5 Proof of Proposition 6

Nonempty ∂Ω(p) at every p∈△d is equivalent to ∇Ω*(Rd)=△d.Fenchel–Young duality and Danskin’s theorem give one direction; the KKT conditions establish the converse.Source: §B.5 · p. 53
Nonempty subdifferentials throughout △d imply a separation margin: at a vertex, a subgradient can be shifted to a positive multiple of that vertex.The proof uses Lemma 1 and shift invariance of Ω* to obtain the vertex subgradient, then invokes Proposition 5.Source: §B.5 · p. 53
When −H is separable, existence of a separation margin also implies nonempty ∂Ω(p) throughout △d.The proof writes H as a sum of coordinatewise concave functions and constructs a subgradient at points with zero coordinates.Source: §B.5 · pp. 53–54

B.6 Proof of Proposition 7 … B.9 Proof of Proposition 10

The appendix proofs characterize separation margins through entropy-based optimization and subgradient conditions, establish a scalar-root method for computing regularized predictions, and derive loss forms for specific choices of a shift-invariant function.

B.6 Proof of Proposition 7

The margin supremum is attained in the limit as t approaches zero, after the proof reduces it to a one-dimensional optimization and shows the objective is decreasing.For separable Ω, the margin is h′(0) − h′(1), equivalently −∫_0^1 h′′(t)dt.Source: §B.6 · pp. 54–55

B.7 Proof of Proposition 8

The proof connects the separation-margin property to my ∈ ∂Ω(y), then characterizes the smallest valid margin through a subgradient inequality over conv(Y).The forward direction yields zero loss when θ = my; conversely, the subgradient condition implies zero loss for qualifying θ.Source: §B.7 · pp. 55–56

B.8 Proof of Proposition 9

For separable regularizers with strictly convex differentiable g, computing ∇(Ω)* reduces to finding the root of a monotonic scalar function.The coordinate solution uses (g′)⁻¹ with thresholding at g′(0).Source: §B.8 · pp. 56–57
The proof shows the infeasibility function decreases and changes sign across [τmin, τmax], so its unique root satisfies the KKT conditions and gives the global solution.Strict convexity gives a unique optimal p and τ; bisection is one example of an approximate root-finding method.Source: §B.8 · p. 57

B.9 Proof of Proposition 10

The derivation rewrites the loss as a sum of shift-invariant φ terms on centered scores, then applies a lemma to obtain forms for specific choices of φ.One choice recovers the result of Duchi et al. (2018, Example 5, §A.6) with a simpler proof.Source: §B.9 · p. 59
For the smoothed hinge loss, quadratic regularization of the conjugate leads to a boundary optimum for τ, which yields the claimed expression of Hℓ.The proof also treats a conjugate constrained to τ ≤ 0 and simplifies the resulting optimization.Source: §B.9 · pp. 59–60