Sampling Policies, Curriculum, and Hard Examples

Selection probability determines which gradients are observed most often. Every policy in this lesson is judged the way the field eventually judged it: against a control condition that does not use it, on a fixed backbone or a fixed budget, with the numbers reported.

If examples are selected with unequal probabilities and no correction, frequent selections contribute more to the expected update. That may be intentional. It is not the original empirical average.

Importance weights can restore a target expectation under assumptions, yet they may increase variance. State the intended objective before choosing a sampler.

Selecting hard examples and re-weighting them are two different mechanisms, and they have been run against each other. Lin and colleagues held the backbone fixed — one ResNet-101-FPN — and swapped the two, at ICCV in 2017. The focal-loss paper states the difference exactly: “Like the focal loss, OHEM puts more emphasis on misclassified examples, but unlike FL, OHEM completely discards easy examples.” A sweep of the online hard example mining configurations reaches 32.8 AP on COCO at its best. Focal loss reaches 36.0 AP. The paper draws the conclusion in one line: “This is a gap of 3.2 AP, showing FL is more effective than OHEM for training dense detectors”. RetinaNet, the detector built on the re-weighted objective, reached 39.1 AP on COCO test-dev at 5 fps.

Down-weighting the easy examples beat discarding them, on the same network, by 3.2 AP. That is the size of the decision hiding inside the phrase “we mine hard examples”.

A hard-example policy should classify difficulty before amplifying it. It should also ask how much data it has. The correct reading of a difficulty score reverses with dataset size.

That reversal was measured in 2022, in a data-pruning paper that NeurIPS named an Outstanding Paper. Sorscher, Geirhos and colleagues put it in one clause of a figure caption: “when data is abundant (scarce) ... the better pruning strategy is to keep the hard (easy) examples”. The scarce half is spelled out in the text: “If one does not have much data to start with, it is better to keep the easiest examples with largest margins (i.e. the blue regions of Fig. 1B) to avoid overfitting.” They predicted the switch analytically for the perceptron and confirmed it for a ResNet-18 on CIFAR-10.

The same score, the same examples, opposite policies.

Each strategy creates a different learning distribution. And each risk in the table below has a documented instance rather than a hypothetical one: hard-example mining collapsed the FaceNet embedding, prioritized replay survived a 57-game ablation, and the curriculum row is the one that fails its own control.

A useful policy should improve learning efficiency without erasing coverage.

Two of the steps below can live inside the sampler itself. Katharopoulos and Fleuret built them there, at ICML in 2018. Their method estimates the variance reduction importance sampling would achieve before using it, and switches on only when that reduction is real — step 2 as a runtime gate rather than a post-hoc log. They report the payoff the way step 3 demands, per unit wall-clock rather than per epoch: “for a fixed wall-clock time budget, it provides a reduction of the train losses of up to an order of magnitude and a relative improvement of test errors between 5% and 17%”.

A sampler that cannot state its gain at a matched budget has not been evaluated.

Some tasks benefit from broad diversity first, interleaving, or revisiting easier anchors after difficult phases. Difficulty can depend on the model, the target, and the desired representation.

Curriculum learning has a precise origin. Bengio and colleagues named it at ICML in 2009. Their experiments “show that significant improvements in generalization can be achieved”. The mechanism is stated as a hypothesis, not a result: an effect on “the speed of convergence of the training process to a minimum” and on “the quality of the local minima obtained”. Seventeen years on, that caution is still the right posture — because the control condition was eventually run.

Thousands of orderings settled it. Wu and colleagues swept curriculum, anti-curriculum and random-curriculum training, and presented the result at ICLR in 2021 as an Oral: “We find that for standard benchmark datasets, curricula have only marginal benefits, and that randomly ordered samples perform as well or better than curricula and anti-curricula, suggesting that any benefit is entirely due to the dynamic training set size.” Random order — the thing a curriculum is supposed to improve on — matched or beat both directions of ordering. Curriculum helped in two named conditions only: under a limited training-time budget, or with noisy data.

That is the shape of an honest claim. It is available because someone ran the ordering against a control instead of against nothing.

So treat curriculum order as an empirical policy with a control condition. Faster early convergence is not enough if final coverage or robustness suffers.