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

Existing supervised-learning losses span many tasks, but their shared principles and theoretical relationships are not fully unified. The paper introduces Fenchel–Young losses from regularized prediction and convex duality, studies them across domains, and derives algorithms; it connects sparsity with separation margins while recovering existing and enabling new losses.

Problem
Loss functions have been developed across regression, classification, ranking, and structured prediction, motivating a unified understanding of their principles and properties.
Method
The paper uses output regularization and convex duality to construct Fenchel–Young losses for regularized prediction functions over probabilistic and structured domains.
Results
Fenchel–Young losses unify many existing losses, connect sparse distributions with separation margins, and support useful new losses across varied tasks.
Takeaways & Limitations
The framework provides geometric principles for designing losses and computational tools for learning with them in unstructured and structured settings.
Takeaways & Limitations
Consistency of Fenchel–Young losses as surrogates for possibly non-convex losses is not addressed in this paper.

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 develops a unified framework for understanding and constructing loss functions across supervised learning tasks. It connects regularized prediction functions, Fenchel–Young losses, sparsity, separation margins, and structured prediction.

Loss functions underpin regression, classification, ranking, and structured prediction by measuring discrepancies between ground truth and predictions.
Proper composite losses unify many probabilistic classification losses, but separation-margin losses such as hinge loss fall outside that form.
The framework interprets softmax, sparsemax, and marginal inference through output regularization and constructs associated losses using convex duality.
Fenchel–Young losses extend beyond probabilistic classification to structured domains such as convex polytopes and convex cones.
This comprehensive study adds positive-measure losses, primal and dual training algorithms, structured separation-margin results, and new ranking losses.

2. Regularized prediction functions

Regularized prediction replaces direct maximization with a variational problem balancing score affinity and output regularization. The chosen domain and regularizer determine prediction geometry, including density, sparsity, and structured output behavior.

A model maps inputs to scores, and a regularized prediction function maps those scores to outputs, including points in conv(Y) or more general domains.
Regularized prediction balances the affinity term ⟨θ, µ⟩ against a confidence regularizer Ω(µ), with domains and regularizers selected according to desired outputs.
Unlike unregularized maximization, regularization can move predictions away from vertices toward convex combinations, interpretable as means rather than modes.
Indicator regularization recovers the MAP oracle, while allowing domains such as convex hulls and conic hulls.
Argmax concentrates probability on one class, softmax produces dense distributions, and sparsemax can assign exactly zero probability to low-scoring classes.
The regularized prediction is a subgradient of Ω* and, under strict convexity, equals its gradient, enabling associated loss derivations.
For Ω = Ψ + I_C, the dual view trades off the unregularized support function against a proximity term Ψ*(θ − u).

3. Fenchel-Young losses

Fenchel-Young losses associate a convex loss with any regularized prediction function through convex duality. They are nonnegative and convex, recover familiar losses, and connect naturally to Bregman divergences and cost-sensitive learning.

Definition: Fenchel-Young losses are defined from a regularized prediction function using convex conjugacy.The construction yields an associated loss whenever the regularized prediction function can be computed.
Properties: The losses are nonnegative, attain zero under the stated convexity conditions, and have prediction residuals as subgradients.With strictly convex Ω, zero loss occurs exactly when the prediction equals the target; the loss is convex in θ.
Properties: For strictly convex Ω, Fenchel-Young losses are differentiable, with gradient byΩ(θ) − y; strong convexity additionally gives smoothness.The gradient is Lipschitz continuous when Ω is strongly convex.
Examples and extensions: The framework recovers the squared, cross-entropy, sparsemax, and cost-sensitive hinge-family losses, including multiclass hinge, softmax-margin, and cost-augmented sparsemax.Cost vectors may depend on the ground truth, enabling margin-like cost-sensitive constructions.
Relation with Bregman divergences: Fenchel-Young losses remain convex in unconstrained score space, unlike Bregman divergences composed with prediction mappings, which may be non-convex.When θ and µ are a dual pair, the loss equals a mixed-space Bregman divergence; the paper does not require Legendre-type assumptions generally.

4. Probabilistic prediction with Fenchel-Young losses

On the probability simplex, generalized entropies generate probabilistic Fenchel-Young losses and prediction functions. This view explains convexity, Fisher consistency, sparsity, and a continuous family linking softmax, sparsemax, and argmax.

Simplex prediction: On the probability simplex, the regularized prediction function maps score vectors to generalized exponential-family distributions.Its regularizer is defined over the simplex, and sparse outputs can assign zero probability to some classes.
Generalized entropies: A generalized entropy H is a concave uncertainty function, with assumptions ensuring nonnegativity and a uniquely uniform maximum.Under assumptions A.1–A.3, the uniform distribution is the maximum-entropy distribution.
Induced losses: Fenchel-Young losses use the conjugate of −H and remain convex even when maximizing the predicted ground-truth probability is non-concave.For Shannon entropy, the conjugate is the log-partition function and the loss corresponds to a likelihood-based formulation; this equivalence does not generally extend to other entropies.
Risk and consistency: The pointwise Bayes risk equals the generalized entropy generating the loss, and the Bayes optimum is achieved exactly when the prediction matches the true distribution.Thus, these losses are Fisher-consistent estimators of probabilities.
Examples: Tsallis entropies form a continuous family whose α = 1, 2, and ∞ cases yield softmax, sparsemax, and argmax prediction functions.The α = 2 case also recovers the Gini index and sparsemax loss, while the ∞ case gives the perceptron loss.
Binary classification: The framework connects binary margin losses with regularization and identifies sparsemax loss as the multiclass extension of modified Huber loss.The binary construction represents symmetric margin losses through a regularization function on binary probabilities.

5. Separation margin of Fenchel-Young losses

The paper characterizes when Fenchel-Young losses have a positive separation margin, linking this property to subdifferentials, entropy geometry, and sparsity. It also provides an analytic margin formula under twice-differentiability assumptions.

Examples: The multiclass hinge loss has margin 1, sparsemax has a separation margin, and logistic loss has none.The logistic loss lacks a margin because it remains strictly positive, equivalently because ∂(−Hs)(ek) is empty.
Conditions for existence of margin: A loss has a separation margin when a positive multiple of each vertex belongs to the corresponding subdifferential of −H.This condition is necessary and sufficient, and the smallest valid multiple gives the margin.
Margin computation: The ∞-norm entropy provides an upper bound for convex losses with unit margin, as illustrated in the binary case.The entropy ratio formulation identifies a distribution maximizing the ratio between H(p) and Hn∞(p).
Relationship between sparsity and margins: For uniformly separable entropies, a loss has a margin exactly when its regularized prediction function can reach the simplex boundary and produce sparse probabilities.For general entropies satisfying A.1–A.3, sparsity is sufficient but not necessarily necessary.
Relationship between sparsity and margins: Essentially smooth entropies map only to the simplex interior, preventing sparse predictions and, in the separable case, preventing a margin.Shannon entropy is essentially smooth because its derivative diverges at zero; Tsallis entropies with α > 1 do not have this issue.
Margin computation: Under twice-differentiability, the margin has a closed-form expression determined only by the endpoint slopes of the separable entropy component h.This replaces a generally non-convex optimization formula with a compact geometric characterization.

6. Positive measure prediction with Fenchel-Young losses

Fenchel-Young losses over positive measures recover one-vs-all reductions through coordinate-wise regularized prediction. Their separability supports parallel training and connects binary instances to sigmoid and logistic losses.

One-vs-all reductions: Positive-measure Fenchel-Young losses theoretically justify one-vs-all reductions and recover classical one-vs-all loss functions.They also justify interpreting the predicted positive measures as class-membership scores, possibly after normalization.
Binary classification: Learning over the simplex and unit cube are equivalent for binary classification, up to a constant 2 factor, for uniformly separable regularizers.
Coordinate-wise prediction: For separable regularizers, prediction is coordinate-wise, with each output interpreted as an unnormalized probability for its class.The corresponding loss is separable over classes.
Coordinate-wise prediction: Class-wise separability allows the models producing each score θ_j to be trained in an embarrassingly parallel fashion.
Binary classification: In the binary case with θ = [s, −s], the regularized prediction becomes the sigmoid function and the loss becomes the one-vs-all logistic function.
Binary classification: A generalized-entropy choice yields a “sparse sigmoid” as another positive-measure prediction function.

7. Structured prediction with Fenchel-Young losses

Structured prediction is framed over convex hulls of structured objects, where regularized prediction functions support distributional or mean-based inference and Fenchel–Young losses. The framework recovers established structured losses and provides computational, geometric, and margin-based analysis across several structured domains.

Prediction over convex hulls: Regularized prediction over conv(Y) outputs an expected structured representation under an underlying distribution, typically reducing an exponential structured space to a d-dimensional optimization.The distribution need not be unique under mean regularization, while Carathéodory’s theorem guarantees a representation using at most d structures.
Distribution regularization: Probability-space regularization maximizes generalized entropy under score-based optimization, yielding structured distributions whose gradients provide mean predictions.With Shannon entropy, the unique optimizer is the Gibbs distribution, and the resulting Fenchel–Young loss is the CRF loss.
Mean regularization: Mean regularization computes predictions directly in conv(Y), often through Bregman projection, and can use MAP oracles when direct projection algorithms are unavailable.This replaces a |Y|-dimensional distributional problem with a d-dimensional one, improving computational tractability while sacrificing distributional uniqueness.
Examples and margins: Structured Fenchel–Young losses recover familiar models while exposing computational boundaries, including CRF losses, SparseMAP, and convex losses over the Birkhoff polytope.Marginal inference for permutation matrices is #P-complete, whereas MAP inference is solvable in O(n^3) time; structured SparseMAP has a separation margin of 1.
Examples: The framework constructs losses for diverse structured objects, including alignments, spanning trees, permutations, and permutation matrices.For permutations, MAP inference is sorting with computational cost O(d log d); permutation-matrix losses remain convex and can model instance similarity.
Structured separation margins: A structured separation margin exists exactly when every structured label y admits some m > 0 with my ∈ ∂Ω(y).The smallest such m gives the margin, linking the geometry of the regularizer to loss separation.

8. Algorithms for learning with Fenchel-Young losses

The section develops generic primal and dual training algorithms for Fenchel-Young losses, together with computational methods for regularized prediction functions and proximity operators. These components separate prediction, loss, and parameter regularization, enabling modular implementations across linear and structured models.

Training algorithms: Generic primal and dual algorithms train models with Fenchel-Young losses for arbitrary output regularizers.The framework also covers computation of regularized prediction functions and proximity operators.
Primal training: Fenchel-Young objectives support linear models and neural networks; with linear models and convex parameter regularization, the objective is convex.If the output regularizer is strongly convex, the loss is smooth and proximal gradient methods can solve the objective globally.
Dual training: Dual training centers output regularization, interpreting dual variables as regularized predictions in the same domain as the prediction function.For quadratic parameter regularization, the dual objective depends on the training data through the Gram matrix.
Dual training: Block coordinate ascent converges to an optimal solution, at a linear rate when the Fenchel-Young loss is smooth.Sparse proximity operators induce sparse dual variables, which can make kernelized prediction more efficient.
Prediction oracles: Conditional-gradient algorithms avoid difficult projections by accessing the output domain through a linear maximization oracle and maintain sparse convex combinations.This is especially useful when the domain is the convex hull of a combinatorial set of structured objects.
Prediction oracles: For uniformly separable regularizers over the probability simplex, the regularized prediction function reduces to one-dimensional root finding and can be computed in linear time.Bisection finds an approximate root in O(1/log ϵ) time.

9. Experiments

The experiments evaluate Fenchel-Young losses for sparse label proportion estimation and structured dependency parsing. Results show benefits from tuning the Tsallis parameter, sparse losses on higher-dimensional label proportions, and efficient root-finding solvers.

Experimental scope: Fenchel-Young losses are evaluated on label proportion estimation and non-projective dependency parsing.The experiments include Tsallis losses, sparsemax, softmax, CRF, and structured SVM comparisons.
Label proportion estimation: On seven multi-label benchmarks, tuning α gives the best averaged rank overall for sparse label proportion estimation.The evaluation reports test-set Jensen-Shannon divergence and mean squared error.
Label proportion estimation: When the number of classes is 10, Tsallis and sparsemax perform almost identically and both outperform softmax; with 50 classes, Tsallis outperforms both.The synthetic experiments evaluate Jensen-Shannon divergence, with similar results for mean squared error.
Solver comparison: Brent’s root-finding method outperforms FISTA by one to two orders of magnitude in the solver comparison.The comparison measures time to reach ∥p − p⋆∥2 < 10^-5 for 1.5-Tsallis predictions.
Dependency parsing: SparseMAP outperforms CRF and is competitive with structured SVM for dependency parsing, with substantial gains over structured SVM on Chinese.The parsing evaluation uses a bi-LSTM model across five languages.

10. Related work

The related-work discussion distinguishes Fenchel-Young losses from proper and proper composite losses while situating their use of convex duality and conditional-gradient algorithms. It emphasizes broader convexity and representation flexibility, alongside an unaddressed consistency question.

Proper losses: Proper losses are minimized at the true probability distribution, and strictly proper losses uniquely identify that distribution.They induce Fisher-consistent probability estimators.
Proper losses: Proper losses admit a Bregman-divergence representation, while Fenchel-Young losses can be viewed as mixed-space Bregman divergences.This distinction underlies differences in convexity and domain constraints.
Proper composite losses: Fenchel-Young losses are always convex in the prediction scores, whereas proper losses need not be convex in probability forecasts.Their first argument is unconstrained, unlike the simplex-constrained first argument of proper losses.
Proper composite losses: Fenchel-Young and proper composite losses coincide up to a constant under suitable conditions, but Fenchel-Young losses require neither invertible links nor Legendre-type assumptions.This permits losses such as hinge and sparsemax that are not expressible in composite form.
Open questions: The paper does not address consistency of Fenchel-Young losses as surrogates for possibly non-convex losses.Later work established sufficient conditions for subsets of the framework, with strong convexity of the output regularizer playing a crucial role.
Optimization methods: Conditional-gradient algorithms are presented as tools for computing regularized prediction functions over potentially complex output domains.Earlier work used them for approximate marginal inference and sampling from intractable distributions.

11. Conclusion

The conclusion presents output regularization and Fenchel duality as principles that unify and extend loss design across tasks. It links sparse distributions to separation margins and summarizes computational tools for efficient learning.

Main conclusions: Output regularization and Fenchel duality unify existing loss functions and support the construction of new losses across a broad range of tasks.The conclusion frames these as simple core principles for loss design.
Main conclusions: Sparse distributions are tightly connected to losses with a separation margin, which cannot be written in proper composite loss form.This connects sparsity, margin structure, and representational limitations within the framework.
Computational contributions: The paper establishes computational tools for efficient Fenchel-Young learning in both unstructured and structured settings.The broader framework includes proximity-operator methods for generalized entropies and root-finding procedures for specific regularizers.
Computational contributions: For uniformly separable generalized entropies, proximity operators reduce to one-dimensional root finding, with closed-form inverses derived for important entropies.The treatment includes the Shannon and α = 1.5 Tsallis cases.

A.2 Loss “Fenchel-Youngization”

Fenchel–Youngization constructs a convex loss from a general loss through its induced entropy, preserving useful margin behavior while enabling probabilistic prediction. Pairwise hinge choices yield explicit entropies, including new strictly concave forms whose predictions are typically sparse.

A.2 Loss “Fenchel-Youngization”: Fenchel–Youngization approximates losses that cannot themselves be written in Fenchel–Young form.The construction is presented as a natural approximation method for arbitrary losses ℓ: R^d × {e_i}^d.
A.2 Loss “Fenchel-Youngization”: The resulting loss is convex even when the original loss is not, and its regularized prediction function supports probabilistic prediction.These are identified as the two main advantages of the construction.
A.2 Loss “Fenchel-Youngization”: The entropy generated by a loss is concave, even when the original loss is not convex.This follows because the entropy is an infimum of linear functions of p.
A.2 Loss “Fenchel-Youngization”: Pairwise hinge losses admit a computable entropy characterization, with hinge, smoothed-hinge, and squared-hinge choices producing explicit forms.The hinge case recovers prior work, while the last two entropy forms are new.
A.2 Loss “Fenchel-Youngization”: For smoothed and squared hinge choices, the entropy is strictly concave and the associated prediction function is typically sparse.The paper notes that no closed-form expression is known for the prediction function in these cases.
A.2 Loss “Fenchel-Youngization”: The constructed loss is upper-bounded by a tightest family of cost-augmented hinge losses, and its margin is bounded by the original loss bound m.If the margin is no larger than the original loss margin, zero constructed loss implies zero original loss.

B.2 Proof of Proposition 3

The proof derives the composite Fenchel–Young representation through Bregman projection geometry. Jensen’s inequality establishes non-negativity and identifies the uniform distribution as the unique entropy maximizer under strict concavity.

B.2 Proof of Proposition 3: The regularized prediction is the Bregman projection of ∇Ψ*(θ) onto the feasible set C.When C equals dom(Ψ), the projection coincides with ∇Ψ*(θ) and the Bregman divergence vanishes.
B.2 Proof of Proposition 3: The entropy is non-negative and maximized by the uniform distribution through Jensen’s inequality.Strict concavity makes p = 1/d the unique maximizer.

B.4 Proof of Proposition 5

The proof connects separation margins to subgradients of the negative entropy and characterizes when regularized prediction maps cover the simplex. For separable entropies, the margin reduces to endpoint derivatives.

B.4 Proof of Proposition 5: Subgradients at a simplex vertex characterize zero loss under sufficiently separated scores.For e_1, any θ with θ_1 ≥ m + max_i≠1 θ_i belongs to the relevant subdifferential and yields zero loss.
B.4 Proof of Proposition 5: The separation margin is the smallest m such that m e_1 belongs to the subdifferential of the negative entropy at e_1.This follows from the subgradient characterization over the simplex.
B.4 Proof of Proposition 5: Every simplex point has a dual score under the non-empty-subdifferential assumption, so the prediction map can cover the entire simplex.The proof chooses zero inequality multipliers and obtains p = ∇Ω*(θ).
B.4 Proof of Proposition 5: For separable entropies, a separation margin is equivalent to the existence of a vertex subgradient with finite slope.The proof establishes equivalence among the stated conditions using separability and subdifferential arguments.

B.6 Proof of Proposition 7

The proof develops one-dimensional procedures for computing regularized predictions and closed-form entropies for pairwise hinge losses. Strict convexity gives uniqueness, while monotonicity and bracketing support globally optimal root-finding algorithms.

B.6 Proof of Proposition 7: The separation-margin optimization can be reduced to a one-dimensional problem whose objective is decreasing.This identifies the supremum, and hence the margin, at the boundary limit t → 0+.
B.6 Proof of Proposition 7: For strictly convex separable regularizers, stationarity yields a unique prediction for each threshold τ through the inverse derivative (g′)^−1.Thresholding handles coordinates below g′(0).
B.6 Proof of Proposition 7: The infeasibility function φ(τ) is decreasing, so a sign-changing interval contains a unique feasible root.The endpoint signs follow from bounding the sum by its largest term.
B.6 Proof of Proposition 7: The resulting root satisfies the KKT conditions and therefore gives the globally optimal solution.Bisection is one example of an algorithm for locating the root, while more advanced root-finding methods are also possible.