Margin Bands on the Simplex for Bags of Instances

A common way to train a classifier is to place each class at one corner of a regular simplex, so every class sits the same distance from every other, and then regress the network's output onto the correct corner with squared error. This recipe has strong theory behind it and holds up well on image benchmarks, where it gives better calibration and robustness than cross-entropy. A separate body of work argues that classifiers generalize better when the whole distribution of margins is controlled, meaning both the average distance of examples from the decision boundary and its spread, and not only the single worst-case example. We point out that these two lines are closer than they appear. Squared error to a simplex corner is itself a margin-distribution objective, but an extreme one: it puts the margin target band at width zero, penalizes confident examples as hard as boundary-hugging ones, and also penalizes output movement toward classes that never compete for the decision.

The proposal is to make that hidden objective explicit, replace the zero-width band with a tunable band and a spread penalty measured in simplex margin coordinates, and test it where margin distributions are hardest to estimate well: multiclass learning over bags of instances, such as histopathology slides cut into patches. In that setting a third question appears, one that database theory answers precisely. When a bag contains duplicate or near-duplicate instances, do they count once (set semantics) or once per copy (bag semantics)? We make that choice an explicit, checkable part of how bag predictions and margin statistics are computed. Current multi-instance learners leave it implicit.

Core Claim

Let $v_1,\dots,v_M \in \mathbb{R}^{M-1}$ be unit-norm vertices of a regular simplex, and let $f(x)\in\mathbb{R}^{M-1}$ be the network output. The simplex margin of an example with label $y$ is

$$\rho(x,y) = \langle f(x), v_y\rangle - \max_{j\neq y}\langle f(x), v_j\rangle ,$$

which equals $M/(M-1)$ exactly when $f(x)=v_y$. Because $\rho$ deviates from that target by an inner product of the residual $f(x)-v_y$ with a vertex difference, the squared error $\|f(x)-v_y\|^2$ upper-bounds the squared margin deviation, up to a constant. Averaged over the data, it therefore bounds both the mean shortfall and the variance of the margins. The objective in Understanding Square Loss in Training Overparametrized Neural Network Classifiers, which proves margin separation for simplex-coded squared loss in the infinite-width regime, is therefore an implicit margin-distribution machine. It has a band of width zero. It also penalizes residuals that change gaps to classes that are not the closest competitor.

We replace it with an explicit banded loss over a weighted multiset of training units (instances or bags):

$$\mathcal{L} = \sum_{i} w_i\Big[\big(r-\theta-\rho_i\big)_+^2 + \mu\,\big(\rho_i-r-\theta\big)_+^2\Big] + \lambda\,\|f\|^2_{\text{reg}},$$

Here $\rho_i$ is the simplex margin of unit $i$, $r$ is the target margin, $\theta$ is the half-width of the zero-loss band, $\mu$ weights the penalty for overshooting the band, $(\cdot)_+$ is the positive part, and $w_i$ is a multiplicity weight explained below. When $M=2$ the simplex is the pair $\pm 1$, and this objective reduces to the binary Optimal Margin Distribution Machine. That gives an exact correctness check against existing results.

What would be new has three parts. The first is a margin-distribution loss defined on simplex geometry, where earlier multiclass versions use $M$ separate hyperplanes. The second is a direct, ablatable test of whether band width matters beyond squared loss. The third is bag-level multiclass learning in which the effect of duplicates on predictions and margin statistics is fixed by a declared semantics, not left to an accident of the pooling layer.

Relation to Prior Work

The margin-distribution side supplies the loss shape. Large margin distribution machine and Optimal Margin Distribution Machine introduced the zero-loss band that penalizes examples outside a target margin interval. Improving generalization of deep neural networks by leveraging margin distribution carried this to deep networks, with a bound in terms of the ratio of margin spread to mean margin. Multi-Class Optimal Margin Distribution Machine (mcODM) handled the multiclass case with $c$ separate weight vectors, a max over competitors, successive convex relaxations, and a block coordinate solver. We keep the band and the spread control. We place them on simplex coordinates with a fixed target geometry, which removes the redundant output dimension and the free shift that mcODM must otherwise control.

The simplex side motivates the proposal and also constrains it. Multiclass learning with margin: exponential rates with no bias-variance trade-off shows that under a hard margin condition, simplex-coded plug-in classifiers have exponentially decaying excess risk with no bias term. That result depends on the minimum margin. A band that tolerates a few small-margin examples could in principle give up that guarantee, so we monitor it with a synthetic check, described below. Hu et al. supply the strongest deep baseline and the observation our core claim rests on. Their own framing treats squared loss as sufficient, and our ablations are designed to test whether it is.

On the bag side, two papers connect bags to margin distributions, and both treat a bag as a set. Optimal Margin Distribution Machine for Multi-Instance Learning (MI-ODM) optimizes the mean and variance of instance margins for binary bag labels through a saddle-point formulation. Multi-Instance Partial-Label Learning with Margin Adjustment (MIPLMA) adds a margin-distribution loss on softmax probabilities and a temperature-annealed attention layer. The authors also report that their implementation cannot process several bags at once. Neither paper uses simplex outputs, and neither says what a duplicated instance should do.

Database theory answers that question. The Magic of Duplicates and Aggregates ties a fact's multiplicity to the number of ways it is derived. The Bag Semantics of Ontology-Based Data Access separates sum-union, where counts add, from max-union, where counts take the maximum, and shows that the choice changes aggregate results. Verifying SQL queries using theories of tables and relations documents how rewrites that are sound for sets silently corrupt counts and sums under bags. We use these papers as a lens, not as machinery. A bag-level prediction is an aggregate over a multiset, so its semantics should be declared and tested.

Research Program

The first component is the loss and its analysis. We will write out the decomposition of simplex squared error into a part along the closest-competitor margin and a remainder. We will show the bound relating squared error to margin mean shortfall and variance, and we will check that the $M=2$ case recovers ODM exactly. The loss is a differentiable function of $f$ almost everywhere, so it trains with ordinary minibatch gradient descent and needs no relaxation solver. Minibatch estimates of margin spread are noisy, a limitation the file flags for margin-distribution methods. The per-example band form above avoids estimating a batch variance explicitly, which addresses that problem.

The second component carries the method to bags with declared semantics. Each instance $x$ in bag $B$ maps to a simplex-space vector $g(x)$, and the bag score is pooled under one of two semantics, both made explicit. Under sum semantics, the score is the multiplicity-weighted mean $\sum_x m_B(x)\,g(x)/\sum_x m_B(x)$. It is additive over sum-union of bags, which suits labels that mean "which class dominates the composition." Under max semantics, the score is computed over the distinct support of the bag. It is invariant to duplication, which suits labels that mean "which class is present." For candidate-label bags we use $\max$ over candidate vertices minus $\max$ over non-candidate vertices as the margin, mirroring MIPLMA's label-space margin. Multiplicities $m_B(x)$ come from exact duplicates or from near-duplicate clustering of patch features at a fixed threshold.

Separately, the training weights $w_i$ in the loss let us count bags once each or by their multiplicity in the training multiset. This separates two questions: how duplicates affect a bag's prediction, and how they affect the margin statistics. Fixed-size pooling also lets bags be batched, which removes the throughput limitation MIPLMA reports.

The third component is a guarantee check. On the synthetic two-dimensional setups of Vigogna et al., we will measure whether banded training preserves the excess-risk decay they report, and under what band widths it does so.

Baselines

The naive reference point is one-hot cross-entropy with standard attention pooling over instances, run in the same backbone, data splits, and epochs. Any proposed method must beat it clearly on accuracy and calibration, or the added structure is unjustified.

The strongest competitor on the core question is simplex-coded squared loss from Understanding Square Loss in Training Overparametrized Neural Network Classifiers. It already induces margin control, and it reports 79.65% accuracy on CIFAR-100 with a Wide ResNet, against 77.89% for cross-entropy, and an expected calibration error of 0.0097 on CIFAR-10. We will rerun it in our pipeline with the same architecture, augmentation, and hyperparameter search budget as our method, in GPU-hours and number of trials, and will not copy the number. Beating it means higher mean accuracy across at least five seeds, with non-overlapping confidence intervals, under limited-data subsets (5% of CIFAR-10, as in mdNet). It also means no worse calibration on full data.

For margin distributions without simplex geometry, the baseline is mdNet's loss on one-hot outputs, from Improving generalization of deep neural networks by leveraging margin distribution. No reported result was found on Lacuna for mdNet's limited-data CIFAR-10 accuracy, because the file gives it only graphically, so we run it ourselves under the matched budget.

For bags, the strongest existing method is MIPLMA. It reports 91.5% on FMNIST-MIPL (ELIMIPL, 90.3%) and 68.5% on CRC-MIPL with ResNet-34 features. Beating it means exceeding those numbers using the same features and splits, while also running MIPLMA in our harness so the comparison does not rest on reported values alone.

In the binary multi-instance case, MI-ODM reports 89.8% on Musk2 and 76.80% key-instance identification on CBIR Castle, against 64.74% for Ins-KI-SVM. Our method at $M=2$ should match MI-ODM, which is a correctness check more than a contest.

Three ablations isolate the ingredients. Setting $\theta=0$ and $\mu=1$ recovers a margin-only squared loss, which tests whether the band matters. Swapping simplex outputs for $M$-dimensional one-hot outputs, with everything else fixed, tests whether the geometry matters. Swapping sum and max semantics, and bag-weighted and set-weighted $w_i$, tests whether the declared semantics matters.

Why not just…?

Why not just use simplex squared loss, since it already controls margins? This is the real threat, and the core claim concedes half of it. If the zero-width band ($\theta=0$) and the tuned band perform the same across limited-data and label-noise conditions, we will report that squared loss is already the right margin-distribution machine. That outcome is itself worth knowing. The reason to expect a difference is that mdNet's evidence shows unconstrained squared-type objectives do not settle margins into the shape that generalizes best when data is scarce. A band lets confidently correct examples stop pulling on the network. The $\theta$ sweep under 0–40% symmetric label noise settles this question directly.

Why not just apply mdNet or MIPLMA's margin loss to ordinary softmax outputs? Softmax probabilities have a free logit shift and $M$ outputs for $M-1$ degrees of freedom. Probability margins also saturate, so their variance shrinks for reasons unrelated to the boundary. The one-hot-versus-simplex ablation, with the same loss shape, tests whether the geometry contributes anything. If it does not, the simplex part of the proposal should be dropped.

Why not just deduplicate instances, or trust attention to sort out duplicates? Deduplication hard-codes set semantics, which is wrong for composition labels. Attention gives duplicated instances equal scores, so their combined weight grows with the copy count. That makes it an undeclared, renormalized form of bag semantics. We test this with a controlled duplication experiment, replicating random instances $k$ times within test bags. A max-semantics model should be exactly invariant. A sum-semantics model should shift predictably. Attention models will be measured to see which, if either, they match.

Why not predict multisets directly by regressing counts onto simplex directions? We considered this, since it is the obvious combination, and rejected it. Vertex sums lose the total count, because the vertices sum to zero. Adding the total back makes the map an invertible rotation of plain per-class count regression, so under squared error it is the same method. It would add nothing beyond the count-based alternatives to Loss Functions for Multiset Prediction.

Proposed Experiments

On single-instance data, we train ResNet-18 and Wide ResNet-16-10 on CIFAR-10 and CIFAR-100, on full data, on 5% subsets, and under injected label noise. We report accuracy, expected calibration error, and PGD-100 robust accuracy, plus the empirical margin mean, spread, and lower-tail quantiles. These test the claim that the band changes the margin shape and not just the average.

On bags, we use FMNIST-MIPL, MNIST-MIPL, Birdsong-MIPL, and CRC-MIPL with matched features, and the five classic multi-instance sets and CBIR categories for the binary check. We also add a composition-labeled variant of MNIST-MIPL, with the label set to the majority digit, so that sum semantics has a task it should win.

The decisive checks are four. The $\theta$ sweep must show a non-zero optimum that beats $\theta=0$ under limited data or noise; otherwise the core claim fails. At $M=2$, the method must reproduce MI-ODM on Musk2 within seed variance. In the duplication test, the declared semantics must behave as specified while attention baselines drift. On CRC-MIPL, where overlapping patches make duplicates natural, the multiplicity-aware variant must beat both the set-weighted variant and MIPLMA's 68.5%. Finally, on the synthetic setups, banded training must preserve the excess-risk decay; Vigogna et al. report an observed log-log slope of −0.35 against a predicted −0.5 for soft-margin data. If banded training fails this check, we will state the band widths at which the minimum-margin guarantee is lost.