Multiclass Margin Losses That Are Proper Only Where Decisions Are Made

Support vector machines (SVMs, classifiers that place a boundary as far as possible from the nearest training points) are sparse because their loss stops caring about a training point once it is classified with enough room to spare. That indifference is also why their scores are not probabilities. Losses that do yield honest probabilities, such as cross-entropy, are strictly proper: their expected value is minimized only when the predicted class probabilities equal the true ones. Strict properness rules out flat regions in the loss, so every training point keeps pulling on the model and sparsity is lost. This note proposes a resolution for the multiclass case. The loss should be strictly proper on a chosen band of the probability simplex (the set of all probability vectors over $K$ classes) and flat outside it. The band surrounds the decision boundaries of a family of misclassification-cost matrices, which is the only part of the simplex where a cost-sensitive decision depends on the exact probabilities. Points whose predictions lie confidently beyond the band on the side of their own class contribute nothing, as non-support vectors do in an SVM. Points inside the band receive exactly calibrated probabilities.

In short, we replace "proper everywhere or nowhere" with "proper exactly where the downstream cost-sensitive decision needs it," and build the resulting family of multiclass margin losses. The family has a single geometric knob, the band, which runs from a multiclass hinge loss (band shrunk onto the plain decision boundaries) to a fully proper loss (band equal to the whole simplex). Temperature-smoothed losses offer a different knob. They trade sparsity against properness everywhere at once. The band keeps exact properness inside and exact flatness outside.

Where the existing work stops

Three groups of prior work frame the problem.

The probabilistic reading of margin classifiers motivates it. A Probabilistic Interpretation of SVMs with an Application to Unbalanced Classification shows that the binary hinge loss is the negative log-likelihood of a semi-parametric model. That model deliberately ignores the probability density wherever the classifier is confident, and this indifference is the source of support-vector sparsity. Our proposal reuses this idea and moves it to the multiclass simplex. The size of the region that is ignored becomes an explicit design choice tied to decision costs, rather than a by-product of a hinge placed at $yf=1$.

Two results constrain the design. Consistency and Finite Sample Behavior of Binary Class Probability Estimation shows that losses with flat regions are not strictly proper and have many minimizers. We therefore claim properness only on the band, never globally. Composite Multiclass Losses proves that the binary recipe of building proper losses by integrating cost-weighted 0-1 losses over a threshold fails once $K>2$. That rules out the obvious construction, which would integrate over a family of cost matrices. The same paper also supplies two tools we reuse. A multiclass loss is proper if and only if it is proper on every one-dimensional slice of the simplex. A continuous loss is strictly proper if and only if it is classification-calibrated for every cost matrix. Our central theorem target is a localized version of the second fact.

The closest constructive work bridges pairs of directions but not all three. Risk minimization, probability elicitation, and cost-sensitive SVMs derives a cost-sensitive hinge loss from probability elicitation. Its loss keeps a cost-dependent margin even on separable data and remains a quadratic program, but it is strictly binary and handles one fixed cost pair. Coherence functions with applications in large-margin classification methods and its multiclass extension Coherence Functions for Multicategory Margin-based Classification Methods interpolate between hinge and logistic losses with a temperature. For any positive temperature the loss is smooth everywhere, so sparsity has to come from an added penalty that shrinks many weights to exactly zero (an $\ell_1$ penalty). The multiclass paper fixes $T=1$ in experiments and never analyzes properness. LegendreTron: Uprising Proper Multiclass Loss Learning learns a globally proper multiclass loss, but it has no margin or sparsity mechanism. Calm Composite Losses recovers probabilities from improper losses through a Bregman projection, a projection onto a set measured by the loss's own divergence rather than by Euclidean distance. Our minimizer turns out to be the same kind of projection, now onto the band. Bayesian Multicategory Support Vector Machines obtains multiclass SVM uncertainty only through slow Markov chain Monte Carlo sampling and offers no closed-form proper loss.

Core Claim

Fix a strictly concave Bayes risk $H$ on the simplex $\Delta_K$, for example the entropy behind cross-entropy. Fix a closed convex region $R \subseteq \Delta_K$, the band. The band-restricted risk is built from tangent planes of $H$ at points of $R$:

$$H_R(p) = \inf_{q \in R} \big[ H(q) + \nabla H(q)^\top (p - q) \big],$$

Here $p$ is the true class-probability vector and $q$ ranges over predictions allowed inside the band. On $R$, $H_R$ coincides with $H$, because tangent planes lie above a concave function and touch it at $q=p$. Off $R$, $H_R$ is a lower envelope of planes.

The proper loss associated with $H_R$, written $L_R$, charges a prediction $q \in R$ the value of its tangent plane at the observed one-hot label. Its conditional minimizer is the Bregman projection of $p$ onto $R$. That projection equals $p$ whenever $p\in R$, so the loss is strictly proper on the band.

For a cost matrix $C$, where $C_{jk}$ is the cost of predicting class $k$ when the truth is $j$, the Bayes decision $\arg\min_k \sum_j C_{jk} p_j$ depends on $p$ only through which side of a few hyperplanes it lies on. We choose $R$ to contain a neighbourhood of every such hyperplane for all $C$ in a family $\mathcal{C}$ of cost matrices the practitioner expects to face.

The margin loss itself is a composite. It combines $L_R$ with a link (the map from real-valued scores to probabilities) that saturates at the faces of $R$. Past those faces we extend it by its convex continuation. That continuation is flat beyond the face of $R$ nearest the labeled class and linear in every other direction, exactly as the hinge loss is flat past $yf=1$ and linear before it.

We will prove three properties of this loss. First, it is calibrated for every cost matrix in $\mathcal{C}$ and returns exact probabilities on $R$; this is the localized form of the result in Composite Multiclass Losses. Second, training points whose predictions saturate toward their own class get zero weight in the kernel dual, which gives support-vector sparsity. Third, the family reduces to a multiclass hinge loss as $R$ shrinks onto the boundaries and to the full proper loss as $R$ grows to $\Delta_K$.

Research Program

The first step is construction. We will write the convex continuation explicitly for entropy and for the Brier (squared-error) risk, using the slice theorem of Vernet et al. to check properness on each slice of $R$. The binary case must reproduce two known objects. With $R=\{1/2\}$ it should give the hinge loss. With $R$ an interval $[a,b]$ around a cost-shifted threshold, it should give a loss whose dual matches the cost-sensitive SVM of Masnadi-Shirazi and Vasconcelos.

The second step is theory. We need four results: the localized calibration theorem; a bound on expected-cost regret that is uniform over $\mathcal{C}$ and depends on the width of the band; a characterization of which training points have zero dual weight; and a counterexample to the obvious wrong design, in which the link saturates symmetrically and wrongly classified points also lose their gradient.

The third step is optimization. Inside the band the loss is strictly convex, so the dual is no longer a pure quadratic program. We will solve it with an active-set Newton method that only touches points currently inside or behind the band. For deep models we will use the primal composite directly.

The fourth step is band design. Given $\mathcal{C}$, $R$ is the union of slabs of width $\varepsilon$ around the decision hyperplanes, intersected with the simplex and convexified. Choosing $\varepsilon$ is the analogue of choosing the margin. It can be set by validating expected cost, or, in a later step, fit from data.

Baselines

The naive reference point is a standard multiclass SVM with Platt-style sigmoid scaling of its scores, plugged into the Bayes cost rule. The research file describes this two-stage recipe as heuristic, with no link to the training objective. It is the cheapest thing a practitioner would try, and it keeps sparsity.

The strongest probability-centred competitor is multinomial logistic regression with a kernel or neural feature map, trained with cross-entropy and plugged into the cost rule for each $C$. Its multiclass coherence variant at $T=1$ from Coherence Functions for Multicategory Margin-based Classification Methods is the same model in a boosting form. That paper reports a Vowel test error of 47.62% for GentleBoost.C against 49.13% for MulLogitBoost. GentleBoost.C was lowest on five of six UCI multicategory datasets. These are error rates, not cost or calibration numbers. I found no reported result on Lacuna for multiclass cost-sensitive expected cost on these datasets, so we will compute those numbers ourselves for every method.

The strongest sparsity-centred competitor is the coherence loss at small temperature with an $\ell_1$ penalty, the route of Coherence functions with applications in large-margin classification methods. On Leukemia it reports a 2.55% error against 2.77% for the hybrid Huberized SVM.

The structured-reduction competitor is one-versus-rest cost-sensitive SVMs from Risk minimization, probability elicitation, and cost-sensitive SVMs, each trained against a pairwise cost. On binary German Credit that paper reports a total cost of \$550 for its cost-sensitive SVM against \$878 for both the standard and biased-penalty SVMs, a 37.36% reduction. That figure is our sanity target in the binary case. For learned global properness we include LegendreTron with a linear model, matching its own evaluation regime.

The ablation that isolates the key ingredient keeps our loss but sets $R=\Delta_K$, which makes it fully proper with no sparsity. It also includes a version with a band of the same width placed at random rather than on the cost boundaries. All methods share the same features, kernels and splits. Each receives the same hyperparameter budget: the same number of validation trials over regularization, kernel width, and the method-specific knob (temperature, $\varepsilon$, or Platt fitting).

Beating the baselines means two things. Against cross-entropy, we need lower expected cost averaged over held-out cost matrices from $\mathcal{C}$ together with no worse calibration inside the band. Against Platt-scaled multiclass SVMs, we need a comparable or smaller support-vector fraction together with lower in-band calibration error.

Why not just…?

Why not just train cross-entropy and plug in any cost matrix? This is the real threat. A fully proper loss is calibrated for every cost matrix, so it covers $\mathcal{C}$ automatically. Our argument rests on two claims. The first is sparsity, which matters for kernel models at test time. The second, more important, is capacity: under a misspecified model, a globally proper loss spends fitting effort on the corners of the simplex, where no decision in $\mathcal{C}$ depends on the probabilities. Grandvalet et al. give this argument in the binary case. If the band loss does not beat cross-entropy on expected cost when the model is deliberately underpowered (linear models on Vowel and Satimage), the capacity claim fails. In that case the contribution shrinks to the sparsity result and we will report it that way. The $R=\Delta_K$ ablation settles the question directly.

Why not just Platt-scale a multiclass SVM? The scaling is fit after training, and the hinge loss has many minimizers (Consistency and Finite Sample Behavior of Binary Class Probability Estimation). Nothing forces the SVM's score ordering near a cost boundary to match the true probabilities. A single sigmoid cannot repair a ranking that is wrong. The synthetic three-class experiment with known probabilities measures this as in-band KL divergence.

Why not just anneal the coherence temperature toward zero? Temperature changes the whole loss surface at once. A small temperature gives near-sparsity but blurs probabilities everywhere, including at the boundaries that matter, while a large temperature restores probabilities and loses sparsity. Annealing was left untested in the multicategory coherence paper. We will run a full temperature sweep and plot calibration against sparsity for both families. The band loss should dominate that curve, and if it does not, the idea is not worth its extra machinery.

Why not just train one cost-weighted model per cost matrix? This needs a separate model for every cost matrix and cannot serve a cost revealed at test time. The binary analysis of the biased-penalty SVM also shows that class weights drop out of the objective on separable data. We include it as a per-cost oracle upper bound for small $\mathcal{C}$.

Proposed Experiments

The decisive first experiment uses the synthetic three-class simplex setting of Calm Composite Losses, where true probabilities are known. We will measure KL divergence between predicted and true probabilities separately inside and outside $R$, the support-vector fraction, and expected cost over 1,000 cost matrices sampled from $\mathcal{C}$. The prediction is near-zero in-band KL with deliberately poor out-of-band KL, and a support-vector fraction that grows with $\varepsilon$.

Second, the UCI multicategory suite (Vowel, Waveform, Segmentation, Optdigits, Pendigits, Satimage) plus Wine, Glass and Vehicle, with RBF kernels. We sample cost families with off-diagonal costs spread across one, two, and three orders of magnitude, train on one half of each family, and report average and worst-case expected cost on held-out matrices, in-band expected calibration error, test error, and support-vector count. Error rates should match the reported 47.62% Vowel figure and the 0.0169 Wine figure from Bayesian Multicategory Support Vector Machines. Those reproductions establish that the probability gain does not cost accuracy.

Third, German Credit as a binary check against the reported \$550.

Fourth, a scale test on Sector (105 classes) with a linear model against LegendreTron and multinomial logistic regression. This tests whether a band built from many pairwise boundaries stays small enough to keep the loss sparse as $K$ grows. If the band covers most of the simplex at large $K$, the method's value is limited to moderate class counts, and we will report it as such.