Learning with Symmetric Label Noise: The Importance of Being Unhinged

Brendan van Rooyen; Aditya Krishna Menon; Robert C. Williamson

Source-linked AI summary

Learning with Symmetric Label Noise: The Importance of Being Unhinged

Brendan van Rooyen, Aditya Krishna Menon, Robert C. Williamson

arXiv:1505.07634v1May 28, 2015cs.LG

TL;DR

The paper addresses the apparent failure of convex potentials under symmetric label noise, where linear-function-class minimisation can reduce clean performance to random guessing. It proposes and analyses the negatively unbounded unhinged loss, proving SLN robustness and linking its solution to strongly regularised SVMs. Experiments report perfect unhinged classification at noise rates up to 40%, while the paper notes scope limitations under misspecification and unknown noise rates.

Problem
Long and Servedio showed that convex-potential minimisation over linear scorers can achieve random-guessing performance on clean data under symmetric label noise.
Method
The paper proposes the convex unhinged loss, a hinge modification without zero-clamping, and studies its relation to strongly regularised SVMs and general convex potentials.
Results
At 40% label noise, the unhinged classifier finds a perfect solution, whereas hinge and t-logistic suffer at moderate noise rates; a toy example likewise reports perfect classification regardless of noise.
Takeaways & Limitations
Strong ℓ2 regularisation can make most standard convex-potential learners SLN-robust, while the unhinged loss provides a convex, classification-calibrated robust alternative.
Takeaways & Limitations
The noise-corrected construction depends on the unknown noise rate, and with a misspecified function class neither unhinged nor square loss is generally superior.

Abstract

from arXiv · show

Convex potential minimisation is the de facto approach to binary classification. However, Long and Servedio [2010] proved that under symmetric label noise (SLN), minimisation of any convex potential over a linear function class can result in classification performance equivalent to random guessing. This ostensibly shows that convex losses are not SLN-robust. In this paper, we propose a convex, classification-calibrated loss and prove that it is SLN-robust. The loss avoids the Long and Servedio [2010] result by virtue of being negatively unbounded. The loss is a modification of the hinge loss, where one does not clamp at zero; hence, we call it the unhinged loss. We show that the optimal unhinged solution is equivalent to that of a strongly regularised SVM, and is the limiting solution for any convex potential; this implies that strong l2 regularisation makes most standard learners SLN-robust. Experiments confirm the SLN-robustness of the unhinged loss.

1 Learning with symmetric label noise

Symmetric label noise changes observed labels while the goal remains low clean-distribution error. The paper challenges the apparent impossibility of convex-loss robustness by proposing the negatively unbounded unhinged loss.

Learning with symmetric label noise: Symmetric label noise independently flips labels with constant probability, while evaluation targets the unobserved clean distribution.The instance marginal remains unchanged under the corruption process.
Learning with symmetric label noise: Long and Servedio proved that some linearly separable problems make every convex potential over linear scorers perform like random guessing under any nonzero noise.This result motivated work on non-convex losses.
Learning with symmetric label noise: The paper proposes the unhinged loss, a convex hinge modification that is not clamped at zero and is negatively unbounded.The authors prove that this loss is SLN-robust and uniquely satisfies their strong robustness notion up to scaling and translation.
Learning with symmetric label noise: The classifier from unhinged-loss minimisation is known, but its SLN-robustness and equivalence to highly regularised SVM solutions are presented as novel.The paper also identifies the underlying loss’s claimed uniqueness as novel.

2 Background and problem setup

The paper formalises scorers, losses, risks, classification calibration, and symmetric label noise before defining the clean-versus-corrupted learning objective. These definitions frame SLN robustness as preserving classification performance under label flips.

Classifiers, scorers, and risks: A scorer maps instances to real-valued scores, and a loss maps a label-score pair to a real value.The conditional risk averages the loss over the class-probability η.
Classifiers, scorers, and risks: Restricted Bayes-optimal scorers minimise loss risk within a chosen function class, while unrestricted Bayes-optimal scorers use the full scorer space.Restricted regret measures excess risk relative to a restricted optimum.
Classifiers, scorers, and risks: Classification calibration requires every Bayes-optimal scorer for the loss to also be optimal for zero-one classification.Convex potentials satisfy this property under the stated definition.
Learning with symmetric label noise: SLN learning observes labels independently flipped with probability ρ while preserving the instance marginal, and seeks low clean-distribution zero-one risk.The paper denotes corrupted quantities with bars.

3 SLN-robustness: formalisation

The formalisation exposes a failure of convex potentials with linear scorers and motivates changing either the loss or the function class. The paper then identifies a convex, negatively unbounded alternative that retains computational advantages while avoiding the stated failure.

3.1 SLN-robust learners: a formal definition: SLN robustness is formalised by considering all corrupted versions of a clean distribution generated by unknown label-flip probabilities.The learner must preserve clean-distribution classification performance across these corruptions.
3.2 Convex potentials with linear function classes are not SLN-robust: Convex-potential learners with linear scorers include linear SVM and logistic regression, but Long and Servedio show they are not SLN-robust.Their corrupted-risk minimiser can have clean performance equivalent to random guessing.
3.2 Convex potentials with linear function classes are not SLN-robust: This negative result motivates searching for alternative learners, either by changing the loss or by changing the function class.The two approaches alter different components of the learner.
3.3 The fallout: what learners are SLN-robust?: Non-convex losses avoid the proposition’s conditions but are not thereby guaranteed to be SLN-robust with linear scorers.The paper reports evidence that some such losses fail robustness in that setting.
3.3 The fallout: what learners are SLN-robust?: A sufficiently rich function class containing the Bayes-optimal scorer, such as the full scorer space, makes any classification-calibrated loss SLN-robust.This route can use convex potential losses.
3.3 The fallout: what learners are SLN-robust?: The two existing routes suggest a computational-statistical tradeoff: non-convex optimisation costs computation, whereas rich function classes require more data.The paper presents these as drawbacks of the respective approaches.
3.3 The fallout: what learners are SLN-robust?: The paper instead seeks a convex, non-potential loss that preserves convex-risk and linear-scorer advantages while remaining SLN-robust.It identifies square loss as one example and introduces the simpler unhinged alternative.

4 SLN-robustness: a noise-corrected loss perspective

The paper reframes SLN robustness through noise-corrected losses and order equivalence. This yields a characterisation of strong robustness and supports the unhinged loss as a convex solution that must be negatively unbounded.

4.1 Reformulating SLN-robustness via noise-corrected losses: Noise correction replaces reasoning about one loss across clean and corrupted distributions with reasoning about two losses on the same distribution.This reformulation is used to characterise SLN-robust losses.
4.1 Reformulating SLN-robustness via noise-corrected losses: The noise-corrected loss depends on the unknown noise rate ρ, so it cannot directly design an SLN-robust learner.It remains useful theoretically because the corresponding risks are equivalent across clean and corrupted settings.
4.2 Characterising a stronger notion of SLN-robustness: The paper defines strong robustness by requiring a loss and its noise-corrected counterpart to be order equivalent for every ρ.Order equivalence gives the same restricted minimisers and therefore supports robustness over arbitrary function classes.
4.2 Characterising a stronger notion of SLN-robustness: Under the stronger requirement, the previously sufficient loss condition is also necessary for strong SLN-robustness.This establishes a characterisation rather than only a one-way test.
5.1 The unhinged loss is strongly SLN-robust: The unhinged loss is strongly SLN-robust, so pairing it with any function class yields an SLN-robust learner.The result follows from the paper’s strong-robustness characterisation.
4.2 Characterising a stronger notion of SLN-robustness: A nonconstant convex loss bounded below by zero cannot satisfy the admissibility condition, whereas removing boundedness permits a convex admissible loss.This motivates the negatively unbounded unhinged construction.

5 The unhinged loss: a convex, classification-calibrated, strongly SLN-robust loss

The unhinged loss is a negatively unbounded modification of hinge loss that is strongly SLN-robust and classification-calibrated, while bounded scorers address its unbounded-risk difficulty.

The unhinged loss removes hinge-loss clamping at zero, making it negatively unbounded and strongly SLN-robust.Its negative unboundedness avoids the obstruction identified for convex potentials bounded below by zero.
Up to scaling and translation, the unhinged loss is the only convex loss that is strongly SLN-robust.
The unhinged loss is classification-calibrated because every restricted Bayes-optimal scorer has the same sign as the 0-1-loss Bayes-optimal classifier.This holds for every finite scorer bound B, with the unrestricted optimum interpreted over the extended reals.
Its unrestricted Bayes risk is −∞, so every non-optimal scorer has infinite regret, complicating consistency analysis.
Restricting scorers to a bounded class preserves SLN-robustness and classification calibration while enabling surrogate regret bounds and consistency results.For linear scorers, regularisation provides boundedness; the resulting class remains SLN-robust for every λ > 0.

6 Learning with the unhinged loss and kernels

With kernelised scorers, unhinged-loss minimisation yields a centroid-like solution whose clean and corrupted optima differ only by scaling. Strong l2 regularisation connects this solution to SVMs and general convex potentials.

6.1 The centroid classifier optimises the unhinged loss: The optimal kernelised unhinged scorer is based on the difference between aggregate similarity to positive and negative instances.This is equivalent to a nearest centroid classifier.
6.1 The centroid classifier optimises the unhinged loss: Under symmetric label noise, the optimal clean and corrupted kernelised scorers differ only by a scaling factor.
6.2 Practical usage with kernels: The regularisation constant changes score magnitude but not sign, so λ = 1 suffices for classification and crossvalidation is unnecessary.
6.3 Equivalence to a highly regularised SVM and other convex potentials: The unhinged solution is equivalent to a highly regularised SVM solution under the stated bounded-feature assumptions.
6.3 Equivalence to a highly regularised SVM and other convex potentials: Strong l2 regularisation makes the hinge loss SLN-robust when the feature map is bounded and regularisation is sufficiently large.
6.3 Equivalence to a highly regularised SVM and other convex potentials: With sufficiently strong regularisation, the limiting solution of any twice differentiable convex potential is the unhinged, or centroid, classifier.Near zero, such potentials are approximated by their linearisation, which corresponds to the unhinged loss.
6.4 Equivalence to Fisher Linear Discriminant with whitened data: With a misspecified function class, neither unhinged nor square loss is universally superior, and both may underperform.

7 SLN-robustness of unhinged loss: empirical illustration

Experiments show that the unhinged loss remains effective under symmetric label noise, including on the Long–Servedio dataset and UCI benchmarks, while competing losses degrade under noise.

Experimental purpose: The experiments test whether unhinged-loss SLN-robustness is empirically manifest, rather than claiming that unhinged loss is better than other losses.With high regularisation, the unhinged solution is equivalent to an SVM and, in the limit, to any classification-calibrated loss.
Long–Servedio dataset: On the Long–Servedio dataset, the unhinged minimiser perfectly classifies all three points regardless of label-noise level.The hinge minimiser is perfect without noise but reaches 50% error with even a small noise rate.
Training-sample experiment: At 40% label noise, the unhinged classifier finds a perfect solution, whereas hinge and t-logistic minimisers suffer at moderate noise rates.The experiment uses 800 noisy training instances, 1000 test instances, linear scorers, and λ = 10^-16.
UCI datasets: On four UCI datasets, the unhinged loss is sometimes outperformed at low noise but is generally more robust at high noise.Even near 50% noise, it often learns classifiers with some discriminative power.

8 Conclusion and future work

The paper concludes that the unhinged loss is a convex, classification-calibrated, SLN-robust loss with a unique strong-robustness property and a nearest-centroid optimum.

Conclusion: The paper proves that the unhinged loss is convex, classification-calibrated, and robust to symmetric label noise.It also establishes strong SLN-robustness uniqueness and characterises the optimiser.
Conclusion: The unhinged solution is optimised by the nearest centroid classifier.The conclusion also relates highly regularised convex potentials, including the SVM, to SLN robustness.
Future work: Future work includes robustness to asymmetric noise and outliers.

A Proofs of results in main body

The appendix proves the paper’s robustness, uniqueness, calibration, and regularisation results, including the connection between unhinged loss and highly regularised SVMs.

Limiting solution: As regularisation increases, the normalised optimum of any convex potential approaches the normalised unhinged solution.The proof makes the corresponding unit vectors arbitrarily close by decreasing the norm bound.
Negative result: Long and Servedio’s construction shows that any convex potential over a linear class can fail SLN robustness, yielding random-guessing performance on the clean distribution.The proof assumes a linear scorer without a bias term.
Strong robustness: Strong SLN robustness requires the loss and its noise-corrected version to be affine transformations, preserving risk ordering under label noise.The proof derives this through order-equivalent utility functions and affine relationships.
Uniqueness: The uniqueness proof shows that a convex loss whose positive- and negative-label losses sum to a constant must be affine.Both the loss and its negative are then convex, which is possible only for an affine function.
Calibration: For the unhinged loss, conditional risk is linear in the score, with L(η,v) = (1−2η)·v.This supports the loss’s classification-calibration analysis.
Unhinged robustness: The unhinged loss is its own noise-corrected loss up to the scaling factor 1/(1−2ρ), so clean and corrupted regrets coincide up to scaling.
SVM connection: When λ ≥ R^2, the hinge loss’s flat region is inactive, making the SVM objective equivalent to regularised unhinged-loss minimisation.Thus unhinged minimisation corresponds to learning a highly regularised SVM.

B Evidence that non-convex losses and linear scorers may not be SLN-robust

Experiments on the Long and Servedio dataset show that two non-convex losses can produce poor classifiers under symmetric label noise, while the paper also develops theory connecting noise robustness to preserved kernel mean maps and unhinged-loss generalisation bounds.

Non-convex losses: A grid search on the Long and Servedio dataset with γ = 1/60 and 30% noise found TangentBoost’s minimiser at w∗ = (0.2, 1.3), yielding error rate 1/2 on D.The same solution was recovered by L-BFGS from 100 random initialisations as w∗ = (0.2122, 1.3031).
Non-convex losses: The t-logistic minimiser was w∗ = (1.025, 5.1), also yielding error rate 1/2 on D.L-BFGS similarly converged to w∗ = (1.0372, 5.0873) from each of 100 initialisations, with accuracy 1/2.
Conjectured limitation: Strictly proper composite losses with link range R are conjectured not to be SLN-robust with linear scorers.The conjecture argues that label noise makes the problem misspecified when |X| > 3, potentially preventing perfect classification.
Conjectured limitation: The restriction that the link function have range R is necessary to exclude cases such as square loss, whose link range is [−1, 1].The paper also states that strictly proper composite losses cannot satisfy its strong SLN-robustness condition, while ordinary SLN-robustness remains open with linear scorers.
Theoretical evidence: Under symmetric label noise, the kernel mean map is preserved up to a scale factor, supporting noise robustness for methods based on this representation.The clean expectation E[Y · Φ(X)] is a scaled version of the noisy distribution’s kernel mean map.
Theoretical evidence: The unhinged loss has a Rademacher-complexity generalisation bound that also applies when training on corrupted samples.For bounded scorers, the proof uses ||(ℓunh)′||∞ = 1 and ||ℓunh||∞ = B; corrupted-sample regret is related to clean-distribution regret by Proposition 6.

H Additional experimental results

Additional experiments compare losses across synthetic and UCI datasets using error and one-minus-AUC, finding dataset-dependent winners but generally strong unhinged performance at high noise on UCI data.

Long and Servedio dataset: On the Long and Servedio dataset, Table 4 reports mean and standard deviation of 0-1 error over 125 trials across a range of losses.The unhinged loss generally finds a good classifier, while square and TanBoost can perform relatively poorly.
Synthetic dataset: On the Mease and Wyner dataset, t-logistic generally performs best across the reported noise levels.The dataset uses X = [0, 1]^20 with a sparse separating hyperplane, and Table 5 reports performance under various symmetric-noise rates.
UCI datasets: At high noise rates of 40% on UCI datasets, the unhinged loss generally has superior AUC relative to the other losses.AUC is emphasized because several UCI datasets are imbalanced, making 0-1 error less informative than this ranking-based measure.
UCI datasets: Tables 6–7 report 0-1 error and one-minus-AUC results for the iris and ionosphere datasets, while Tables 8–9 report corresponding results for housing and car.Each table reports mean and standard deviation of performance over 125 trials.
Additional datasets: The appendix reports additional results for usps 0 vs 7, splice, and spambase, with means and standard deviations over 125 trials.Grayed cells denote the best performer at each noise rate.