Robust Losses Pay in Effective Batch Size

Losses that resist wrong labels, such as mean absolute error (MAE) and generalized cross-entropy (GCE), are known to underfit badly when a task has many classes. The usual fix is to change the loss or the network's starting outputs. This note proposes a different reading. These losses work by giving each example a weight equal to the model's current confidence in that example's label. Mislabeled examples get low confidence, so they are ignored, and that is the source of the robustness. Hard but correctly labeled examples also get low confidence, though, and as training goes on most of each mini-batch's gradient comes from a few already-easy examples. The mini-batch then acts like a much smaller batch than its nominal size. If that is right, part of the underfitting is a gradient-noise problem. The tools for that problem come from optimization: moving along the dial from small noisy batches toward full-batch, deterministic gradients.

The proposal has two parts. First, we use the stochastic–deterministic dial as a measuring instrument. Running the same robust loss with small batches, growing batches, and exact full-batch gradients separates three possible causes of underfitting: gradients that are too small, gradients that are too noisy, and gradients that point the wrong way on average. Second, if noise turns out to be a large share of the cause, we build a batch-size schedule that grows the batch just enough to keep the robust gradient's effective sample count at a target level. We then compare this schedule against the logit-bias fix of Enhancing Noise-Robust Losses for Large-Scale Noisy Data Learning at equal compute.

Core Claim

For a softmax classifier with logits $z$ and predicted probability $p_y$ on the labeled class, GCE with parameter $q$ has the logit gradient $p_y^{\,q}\,(p - e_y)$, where $(p - e_y)$ is the ordinary cross-entropy gradient and $e_y$ is the one-hot label. MAE is the case $q=1$, up to a factor of 2. Every bounded loss in this family is therefore cross-entropy with a per-example weight $w_i = p_{y_i}^{\,q}$. The number of examples in a batch $B$ that actually contribute is governed by the standard effective-sample-size formula:

$$\mathrm{ESS}(B) = \frac{\left(\sum_{i\in B} w_i\right)^2}{\sum_{i\in B} w_i^2}.$$

It equals $|B|$ when all weights are equal and approaches 1 when a single example dominates.

At initialization $p_y \approx 1/K$ for every example, where $K$ is the number of classes. The weights are then nearly uniform, so the gradient is small but not noisy. That is the regime the logit-bias work targets. Once early learning separates easy examples ($p_y \to 1$) from hard ones ($p_y$ still near $1/K$), the weights span a range of roughly $K^q$. ESS can then collapse by a factor that grows with $K$.

Our claim is that this mid-training collapse is a measurable, $K$-dependent contributor to bounded-loss underfitting that the initialization explanation does not cover. Growing the batch fixes the noise part of it. Growing the batch does nothing for the bias part, which is that hard clean examples are down-weighted even in expectation. The decomposition experiment below is designed to show how large each part is. The schedule is worth building only if the noise share turns out to be large.

Research Program

The diagnostic part uses three optimization regimes for the same loss, architecture, and data. The first is mini-batch SGD at the standard batch size. The second is a batch that grows on a schedule, following Hybrid Deterministic-Stochastic Methods for Data Fitting, which proves that geometrically growing samples recover the linear rate of full gradients on smooth problems. The third is exact full-batch gradient descent on class-subsampled versions of each dataset small enough to make this affordable.

Full-batch runs remove sampling noise entirely. Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD gives grounds to expect full-batch descent to behave well on smooth non-convex losses, which these bounded losses are. Within each regime we also run a step-size-normalized variant: SGD whose step size is scaled by the running mean of $w_i$. This variant cancels the uniform shrinkage of the gradient by a factor of about $1/K$.

These runs give a three-way attribution of the training-accuracy gap between MAE and cross-entropy:

  • The gap that normalization closes is a magnitude problem.
  • The gap that full-batch closes beyond that is a noise problem.
  • The gap that remains under normalized full-batch descent is the weighting bias.

We log ESS per step, separately for examples we know to be clean and examples we know to be mislabeled. We have this ground truth under synthetic noise.

The method part is a batch controller in the spirit of Friedlander and Schmidt. It is triggered by measured ESS rather than by a fixed geometric rate. Whenever the running ESS drops below a target $m$, the next batch is enlarged by the factor $m / \mathrm{ESS}$, capped by memory. Larger logical batches are formed by gradient accumulation. The learning rate follows the mean-weight normalization above.

The target $m$ is set once: it is the batch size that cross-entropy uses well on the same architecture. So the controller adds no noise-dependent hyperparameter. Logit bias does add one, and Enhancing Noise-Robust Losses for Large-Scale Noisy Data Learning reports that its analytic version can overshoot and erode robustness.

We also check a robustness question. Mislabeled examples carry small weights, so growing the batch should improve the signal from confident clean examples much more than it amplifies noisy ones. We verify this from the clean versus noisy ESS logs rather than assuming it.

Baselines

The naive reference points are plain cross-entropy and plain MAE or GCE, trained with the standard SGD recipe used in Symmetric Cross Entropy for Robust Learning with Noisy Labels. That paper reports cross-entropy at 78.70% accuracy on CIFAR-10 with 40% noise. These runs anchor how much any intervention helps over doing nothing.

The strongest competitor on our specific question is MAE* and its sibling bounded losses with logit bias, from Enhancing Noise-Robust Losses for Large-Scale Noisy Data Learning. It targets exactly the same symptom, bounded-loss underfitting at large $K$, and its authors show it makes MAE, genCE, NCE-AGCE and NF-MAE learn on 1,000-class WebVision. The file gives no exact accuracy: no reported result was found on Lacuna for MAE* on WebVision or CIFAR, so we will rerun it. Its bias $\epsilon$ is tuned on the same held-out clean validation split and with the same number of trials that our controller's single target $m$ receives.

The strongest loss-level competitors with published numbers are these:

As a ceiling that uses roughly twice the compute, we cite DivideMix at 74.76% on Clothing1M (DivideMix: Learning with Noisy Labels as Semi-supervised Learning) and AUGDESC at 75.11% (Augmentation Strategies for Learning With Noisy Labels). We do not claim to beat these filtering pipelines.

All runs share data, architecture, augmentation, and a fixed budget of per-example gradient evaluations. The batch controller spends that budget unevenly over time but not in larger total. We report wall-clock time too.

Ablations isolate the key ingredient:

  • A static large batch of the same total cost, with the linear-scaling learning-rate rule. This tests whether adaptivity matters.
  • A batch schedule that grows geometrically, ignoring ESS. This tests whether the ESS signal matters.
  • Our controller plus logit bias together. This tests whether the two fixes address separate failures.

Beating MAE* means one of two things. Either we match its clean-test accuracy without the $\epsilon$ search, or we exceed it at high noise rates where an overshooting $\epsilon$ would be expected to hurt, with non-overlapping confidence intervals over three seeds.

Why not just…?

Why not just use a large static batch? The file's argument against this is that averaging vanishing gradients still vanishes. That argument concerns magnitude, which step-size normalization handles, so by itself it does not rule out static large batches. Friedlander and Schmidt's stronger point is that large batches waste computation early, when even small batches point the right way (Hybrid Deterministic-Stochastic Methods for Data Fitting). Our account predicts the ESS collapse only after early learning, so a static batch overpays in exactly the phase where it is not needed. This is a real threat, and the equal-budget static-batch ablation settles it. If static batches match the controller, we report that the useful lesson is simply "bounded losses need bigger batches," which is still a new and practical finding.

Why not just add the logit bias? Logit bias fixes the initial vanishing-gradient window. Our analysis says the weights are nearly uniform at that point, so logit bias should not address the later spread in confidence. The method also comes with a documented overshoot risk (Enhancing Noise-Robust Losses for Large-Scale Noisy Data Learning). If the decomposition finds the gap is almost entirely magnitude, logit bias is the right answer and our controller is unnecessary. The combined ablation shows whether the two are complementary.

Why not warm up with cross-entropy, then switch to the bounded loss? This is the alternative that most plausibly matches us, because it fixes the early weighting entirely. Its risk is memorizing noisy labels during warm-up. Symmetric Cross Entropy for Robust Learning with Noisy Labels shows easy classes begin fitting noise under cross-entropy before hard classes are learned. Can Cross Entropy Loss Be Robust to Label Noise? reports that cross-entropy fails to learn effectively at 80% symmetric noise. We include warm-up with the switch epoch tuned on the same budget. We expect it to compete at 20–40% noise and to lose at 80%. If it wins everywhere, we will say so.

Why not use variance-reduced estimators like SAG or SVRG instead of bigger batches? SAG stores one gradient per example (A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets), which is infeasible for deep networks. SVRG-style anchors require periodic full passes. Under label noise, both would anchor on mislabeled examples' gradients, which is an open question in its own right. We leave this for a follow-up and restrict ourselves to batching, which has no memory cost.

Proposed Experiments

The first decisive check is the $K$-sweep. We take nested class subsets of CIFAR-100 ($K$ = 10, 25, 50, 100) and of WebVision ($K$ = 50, 200, 1,000), with 40% and 80% symmetric noise on the CIFAR subsets. On each, we measure the MAE versus cross-entropy training-accuracy gap and its three-way decomposition. Our hypothesis predicts two things. Minimum ESS during mid-training should fall with $K$. The noise share of the gap, meaning the part closed by full-batch descent beyond normalization, should rise with $K$. If full-batch descent closes almost none of the gap, the noise hypothesis is false, and the paper becomes a negative result that strengthens the initialization account.

The second check is the head-to-head comparison at equal gradient budget. It runs on CIFAR-10 and CIFAR-100 with symmetric and asymmetric noise at 20–80%, on Clothing1M, and on WebVision. We compare MAE and GCE plus the controller against MAE*, symmetric cross-entropy, Taylor cross-entropy, warm-up-then-switch, and the static and geometric batch ablations. The metrics are clean test accuracy, accuracy on held-out examples whose training labels were corrupted, and wall-clock time. The published reference points are 85.34% for symmetric cross-entropy on CIFAR-10 at 40% noise and 71.02% for symmetric cross-entropy on Clothing1M.

The third check tests the robustness side of the tradeoff. Using ground-truth noise masks, we confirm that growing the batch raises clean-example ESS more than noisy-example ESS. We also confirm that held-out accuracy on mislabeled training examples does not fall late in training, which would signal memorization. If larger batches turn out to help memorize noisy labels, the exchange rate between robustness and effective batch size is not favorable, and we report that limit.