From an observation to a theorem

The paper is A Theoretical Bridge Between Long-Tailed Recognition and Continual Learning (NeurIPS 2026). In a long-tailed dataset a few Head classes have most of the images and many Tail classes have few. The imbalance factor \(\mathrm{IF}\) is the ratio of the largest class size to the smallest.

The starting point was experimental: a model trained on long-tailed data behaves much like a model trained on the Head alone, and its training loss stays close to the Head loss. That is an observation, not yet a claim. The first job is to decide what kind of statement would explain it.

The observation compares where two training runs end up: one on the full long-tailed dataset \(D\), one on the Head \(D_H\) alone. On the guide's tree that is Question 1, "Where does training end up?", and within it the sub-case "Nearby optimum?", whose first tools are strong convexity and perturbation arguments.

Making the claim precise means naming the quantity and the rate. With \(\theta^\star\) trained on \(D\) and \(\theta^\star_H\) on \(D_H\), the claim is

The first algebraic move is to write the full loss as a mixture. If \(\gamma = \lvert D_H \rvert / \lvert D \rvert\), the average loss is

where \(k_H\) and \(k_T\) count the Head and Tail classes when classes within each group have equal size. So the Tail enters with a weight of order \(1/\mathrm{IF}\). The question is now exactly the perturbation question of Question 1: how far does a small extra term move the minimizer?

The first theorem makes two simplifying assumptions (Assumption 3.2 in the paper):

• Equal sizes within Head and within Tail. A didactic simplification that gives the closed form for \(1 - \gamma\) above.
• A convex loss with \(L^2\) regularization \(\tfrac{\mu}{2}\lVert \theta \rVert^2\), which makes both objectives \(\mu\)-strongly convex.

The proof then takes three steps.

1. The losses are uniformly close.
   \[\lvert L(\theta) - L_H(\theta) \rvert = (1 - \gamma)\lvert L_T(\theta) - L_H(\theta) \rvert \le (1 - \gamma) M = \mathcal{O}(1/\mathrm{IF}),\]
   where \(M\) bounds the gap between the Tail and Head losses. This is an assumption too, and the paper states it: the loss is bounded or clipped, or the parameters stay in a bounded region.
2. Close losses force close minimizers. For two \(\mu\)-strongly convex functions that differ by at most \(\delta\), the minimizers are within \(\sqrt{2\delta/\mu}\) of each other. This is the second route on the Question 1 proof.
3. Combine. \(\lVert \theta^\star - \theta^\star_H \rVert^2 \le 2\delta/\mu = \mathcal{O}(1/\mathrm{IF})\), so the distance is \(\mathcal{O}(1/\sqrt{\mathrm{IF}})\).

Notice the choice made in step 2. Comparing gradients instead of loss values would give a sharper \(\mathcal{O}(1/\mathrm{IF})\) in this convex case. But that route relies on strong monotonicity of the gradient around a single isolated Head minimizer, and on a convex Tail loss or a Tail-gradient bound over a region, which is exactly what fails for deep networks with a whole set of minimizers. Comparing loss values only needs \(M\), and, as Step 5 shows, it is the version that survives when convexity goes.

A theorem about convex losses explains the mechanism, but the observation was about deep networks, and their training losses are not convex. The assumptions field guide files convexity under "Justify it": fine for linear models and convex surrogates, a mismatch when the claim is about the models people actually train.

The useful question is not "can I defend convexity?" but "what did the proof actually use it for?". Here, only step 2: turning a small loss gap into a small distance. So the relaxation should replace exactly that step and leave the rest alone.

Assumption 3.4 describes a feedforward network with piecewise-analytic activations such as ReLU and a standard loss such as cross-entropy. What the proof actually needs from it is a local error bound near the set \(S_H\) of Head minimizers:

This is the geometric assumption that replaces global strong convexity, and it is an assumption: standard architectures and weight decay do not guarantee it on their own. The paper motivates it in two ways. The Kurdyka–Łojasiewicz property with exponent \(\tfrac12\) at the minimizers implies it, and Milne (2019) shows that for ReLU networks with weight decay the regularized loss is piecewise strongly convex on an open set that, under some conditions, contains all of its global minimizers. Neither holds everywhere for free: for a two-layer scalar linear network with logit \(ab\), cross-entropy and a weak weight decay \(\tfrac{\lambda}{2}(a^2 + b^2)\) with \(\lambda < \tfrac12\), the loss is not even convex at the origin.

This is step 2 of the clean proof without convexity: a small loss gap still forces a small distance, now to a set of minimizers instead of a single point. Steps 1 and 3 barely change. Since \(\theta^\star\) minimizes \(L\), adding and subtracting \(L\) at \(\theta^\star\) and at any \(\theta^\star_H \in S_H\) gives

because the middle term \(L(\theta^\star) - L(\theta^\star_H)\) is not positive. The error bound then gives \(\mathrm{dist}(\theta^\star, S_H) = \mathcal{O}(1/\sqrt{\mathrm{IF}})\), the same rate as before. This also needs \(\theta^\star\) to lie in the neighborhood where the error bound holds, an assumption worth stating explicitly.

Read the new statement carefully, because it says less than the old one in one respect: deep networks have many Head minimizers, each with its own basin, so the theorem places \(\theta^\star\) near one of them, not near a particular one. Saying so plainly is part of the result.

A rate is a prediction you can test. The paper measures \(\lVert \theta^\star - \theta^\star_H \rVert\) against \(1/\sqrt{\mathrm{IF}}\): for logistic regression on MNIST-LT, where the convex theorem applies, and for ResNet-18 on CIFAR-100, with and without weight decay, where only the relaxed one does. In both cases a straight line fits with \(R^2 \ge 0.97\), consistent with the predicted bound. A fit like this cannot by itself tell \(1/\sqrt{\mathrm{IF}}\) from a faster rate, and it does not verify the assumptions; it checks that the prediction holds where it matters.

The deep-network check matters most. It is evidence that the predicted scaling holds in the regime the claim is about, deep networks, which is what the reviewer's objection was really asking for.

If long-tailed training lands near the Head solution, then learning the Tail afterwards without losing the Head is a continual-learning problem: Head first, Tail second, avoid forgetting. That reformulation (Proposition 3.9) motivates the method, and it calls for a different kind of theorem: is the continual-learning objective a valid stand-in for the balanced loss we actually care about? That is Question 3, and Theorem 3.12 answers it with an upper bound,

near the Head solution, once the penalty weight passes a threshold. The paper then estimates that threshold on a trained network instead of only asserting it is met, and is explicit that an upper bound is not equality: it shows the two objectives share their minimizers in a special convex case (Appendix C.8) and claims no more in general.