Residual-Margin Curricula for Reconstruction Classifiers

A reconstruction classifier keeps one small model per class, such as a dictionary of basis vectors, a subspace, or a small network. It labels a new input by asking which class model redraws it with the least error. This design is fast and interpretable, and in class-incremental learning it forgets nothing, because old class models are never touched. Its weakness is training. Every sample labeled "class $c$" is used to shape class $c$'s model, including mislabeled faces, occluded frames and outliers. A mislabeled sample does double damage: it bends its assigned class model toward the wrong data, and it corrupts the "reject this" signal for its true class.

Curriculum learning is the obvious remedy: train on easy samples first and admit hard ones later. The standard automatic version, self-paced learning, ranks samples by how badly the current model fits them. This note argues that for reconstruction classifiers that ranking uses the wrong signal. It confuses two very different kinds of sample. A mislabeled sample is poorly fit by its own class but well fit by some other class. A hard but correctly labeled sample, such as a face under a scarf, is poorly fit by every class. Plain self-paced learning treats both as "hard" and admits them on the same schedule. We propose instead to schedule training by the residual margin: how much worse the best competing class reconstructs a sample than its assigned class does. Negative-margin samples are held back as probable label errors. Hard samples whose error is high everywhere are admitted gradually, so they widen the class model without distorting it early. The per-class residuals that reconstruction classifiers already compute supply this signal at almost no cost.

Core Claim

In reconstruction-based classifiers, a self-paced curriculum should gate samples on the competitive margin between class residuals, not on the sample's own-class residual alone. Under label noise this should beat three alternatives: uniform training, own-residual self-paced learning, and one-shot residual-based filtering. The margin gate should also cost nothing when labels are clean. The contribution is a specific difficulty signal that separates "wrong label" from "rare variation." This distinction only makes sense when every class has its own reconstruction model. We test the claim on linear dictionary-pair models and carry it to deep per-class prediction-error models.

Relation to Prior Work

The mechanism comes from self-paced learning. Self-Paced Learning for Latent Variable Models selects low-loss samples first and relaxes a threshold over training. On DNA motif finding this cut bad local minima from 18 in 100 runs to 1. Self-Paced Learning for Matrix Factorization replaces hard selection with soft weights on matrix entries according to their reconstruction error. On the Dinosaur structure-from-motion sequence this reduced RMSE from 5.43 to 1.98. That paper is the closest existing work, because it already uses reconstruction error as a pacing signal. It differs from our proposal in two ways. It factorizes a single matrix with no classes, so the only error available is the error of the one model. It also cannot define a margin against competing models. We reuse its soft-weighting schedule and change what the schedule reads.

The classifiers we train come from the reconstruction literature. Projective dictionary pair learning for pattern classification (DPL) learns, for each class $k$, an encoder $P_k$ and a decoder $D_k$. The encoder is trained to map other classes' samples near zero. DPL is fast (11.3 s training on AR) and accurate (98.3% on AR), but it optimizes all samples at once. Any mislabeled sample therefore enters both its assigned class's fit and its true class's rejection term. Sparse representation or collaborative representation: Which helps face recognition? shows that closed-form ridge-regularized reconstruction (CRC) matches sparse coding at a fraction of the cost. We use CRC as a cheap initial scorer and as a baseline. Prediction Error-based Classification for Class-Incremental Learning (PEC) trains one small student network per class to imitate a frozen random network, then classifies by lowest imitation error. It trains each student uniformly and in isolation. We add a margin curriculum that reads the frozen earlier students. This is a form of cross-class information that does not break PEC's zero-forgetting guarantee, because the earlier students are only read, never updated.

Two papers motivate the premise that residuals indicate label reliability. Dictionary Learning from Ambiguously Labeled Data and Solving the Partial Label Learning Problem: An Instance-Based Approach use class residuals as static confidence scores to disambiguate candidate labels. Neither one re-estimates those scores as the class models improve, and neither schedules admission over training. That static use is exactly the one-shot filtering baseline our method must beat.

Method

For class $c$, let $r_c(x) = \|x - D_c P_c x\|_2^2$ be the reconstruction error of sample $x$ under the current dictionary pair. The PEC analogue is the student's imitation error. For training sample $x_i$ with assigned label $y_i$, define the residual margin $$m_i = \min_{c \neq y_i} r_c(x_i) - r_{y_i}(x_i),$$ which is positive when the assigned class reconstructs the sample better than any rival. The weight used in both the fitting term and the rejection terms is $$w_i = \sigma(m_i/\tau)\, s_\lambda\big(r_{y_i}(x_i)\big),$$ with the two factors defined as follows. The margin gate $\sigma$ is a logistic function with temperature $\tau$; it suppresses probable label errors regardless of the curriculum stage. The pacing factor $s_\lambda$ is the soft self-paced weight from the matrix-factorization work, where the "age" parameter $\lambda$ grows during training so that high-residual samples are admitted progressively.

Training alternates between two steps. With weights fixed, we run the ordinary DPL update, where each sample's contribution is scaled by $w_i$. This scaling applies both to the fit of its assigned class and to the rejection term of every other class, including the sample's true class. Then, with dictionaries fixed, we recompute all $w_i$ in closed form. The CRC residuals initialize the weights before any dictionary exists.

For PEC in the one-class-per-task setting, only earlier classes exist when class $t$ is trained. The competing residuals therefore come from the frozen earlier students. For the first few tasks we fall back to the pacing factor alone and report this limitation explicitly. The expected overhead is one residual evaluation per sample per outer iteration, which is cheap for DPL. We will report wall-clock time, since the SPL paper found roughly 50% extra convergence time for its own schedule.

Research Program

The work has three parts. The first is the linear study, which is the main test. Here we add controlled symmetric label noise at 10%, 20% and 40%, and structured corruption (block occlusion on a fraction of training faces), to AR, Extended Yale B and UCF50. We then compare the method against the baselines below across many seeds; DPL's speed makes hundreds of runs affordable.

The second part is diagnostic. We plot every training sample on two axes, own-class residual against best-rival residual. We then check whether injected label errors and injected occlusions separate as the premise predicts. We measure how well the final weights $w_i$ detect label errors (area under the ROC curve) and how often corrupted-but-correct samples are wrongly suppressed. If the two populations do not separate, the method has no basis, and that outcome is itself informative.

The third part carries the method to PEC on CIFAR-10 and CIFAR-100 with noisy labels. The question is whether margins against only-earlier classes still help in the incremental setting.

Baselines

The naive reference points are uniform DPL and uniform PEC, trained exactly as published on the same noisy data. On clean data, the file reports 98.3% on AR and 62.9% on UCF50 for DPL. For PEC under one class per task, it reports 26.54% on CIFAR-100 and 58.94% on CIFAR-10. There is no reported result on Lacuna for DPL or PEC under injected label noise, so we will produce those numbers ourselves. We will also include closed-form CRC, which reached 90.5% on AR with scarf occlusion in the collaborative representation paper, as the no-training reconstruction reference.

The strongest competitor is one-shot residual filtering. It fits CRC once, drops or downweights samples whose best-reconstructing class disagrees with their label, and then trains DPL uniformly on the remainder. This is the static residual-confidence idea of the ambiguous-label papers applied to our setting. It captures most of our intuition without any schedule, which is why it is the real threat.

The key ablation is own-residual self-paced DPL, in which $\sigma$ is set to 1. This is the SPMF weighting transplanted to classification, and it isolates the contribution of the margin. A second ablation removes pacing but keeps the margin gate, with $s_\lambda = 1$. This separates the value of re-estimating the gate from the value of an easy-to-hard ordering.

For discriminative feature pipelines, PCANet with a linear SVM is included for reference. PCANet: A Simple Deep Learning Baseline for Image Classification? reports 99.58% on Extended Yale B.

For fairness, every method sees identical noisy splits. Every method receives the same hyperparameter search budget on a held-out validation split that shares the training noise level, so no method gets clean validation labels. Outer-iteration counts are matched so total training passes are equal. Beating the strongest baseline means a mean clean-test accuracy gain of at least two points over one-shot filtering at 20% and 40% noise, with non-overlapping seed intervals. It also means no loss relative to uniform DPL at 0% noise.

Why not just…?

Why not just filter once with CRC residuals and train normally? When noise is light, this may work as well as our method, and the experiments are designed to show it if it does. Our argument for iteration is that at high noise the initial CRC dictionary is built from contaminated samples. Its residuals are then least reliable exactly when they matter most. Re-estimating margins with progressively cleaner dictionaries should recover label errors that one-shot filtering misses. The noise sweep settles this question. If the gap closes at 40% noise, the honest conclusion is that the schedule is unnecessary and the margin signal alone is the contribution.

Why not just use a robust loss such as an L1 or Huber residual in DPL? A robust loss downweights samples that fit their own class poorly. A mislabeled sample drawn from a nearby class may fit its wrong class tolerably well, so a robust loss can keep it. Such a loss also leaves the sample's pollution of its true class's rejection term untouched. The SPMF results show robust-loss baselines such as CWM (RMSE 0.1359) being beaten by self-paced weighting (0.0632) on outlier-heavy data. That comparison is from factorization, though, not classification. We therefore include an L1-residual DPL under the same tuning budget.

Why not just apply standard self-paced learning with own-class loss? This is precisely our margin-free ablation. Our prediction is that on occlusion-corrupted but correctly labeled data it will match our method, and that under label noise it will fall behind. The reason is that it admits a mislabeled sample once the threshold passes that sample's residual, whereas the margin gate never admits it. If the ablation matches our method under label noise as well, the core claim is falsified.

Decisive Checks

The proposal stands or falls on four results. The first is the two-axis diagnostic: injected label errors must concentrate at negative margin, and occluded but correctly labeled faces must sit at high residual with positive margin. The second is the noise sweep on AR, Extended Yale B and UCF50, where the method must beat own-residual self-paced DPL under label noise and beat one-shot filtering at 20% and 40% noise. The third is the clean-label control, where the method must not lose accuracy relative to uniform DPL. The fourth is the PEC transfer: on noisy CIFAR-100 with one class per task, margins computed only against frozen earlier students must improve on the 26.54% uniform-PEC figure measured under the same noise. They must do so without touching earlier students, which preserves zero forgetting. We will also report seed-to-seed variance, following the local-minima counts of the original self-paced paper, and wall-clock overhead. A curriculum that helps only on average, while doubling the training time of a method prized for speed, would be a weak result.