summaries: Gradient clipping has been studied as an optimization technique and also as a tool for privacy preserving, but in this paper, it studies the robustness properties of gradient clipping.  More specifically, the main question of the paper is: Can gradient clipping mitigate label noise?  The paper reveals that the answer is no, but further proposes a simple variant of gradient clipping is robust and has nice property of classification calibration.  Experiments show that the proposed variant works under label noise. This paper studies the relationship between gradient clipping in stochastic gradient descent and robustness to label noise. Theoretical results show that gradient clipping in general is not robust to symmetric label noise. The paper then proposes a variant of gradient clipping (cl-clipping) that induces label noise robustness. Experiments support these claims on synthetic datasets and typical classification benchmarks.
abstractText: Gradient clipping is a widely-used technique in the training of deep networks, and is generally motivated from an optimisation lens: informally, clipping controls the dynamics of iterates, thus enhancing the rate of convergence to a local minimum. This intuition has been made precise in a line of recent works, which show that suitable clipping can yield significantly faster convergence than vanilla gradient descent. In this paper, we propose a new lens for studying gradient clipping, namely, robustness: informally, one expects clipping to mitigate the effects of noise, since one does not overly trust any single sample. Surprisingly, we prove that for the common problem of label noise in classification, standard gradient clipping does not in general provide robustness. On the other hand, we show that a simple variant of gradient clipping is robust, and is equivalent to suitably modifying the underlying loss function. As a special case, this yields a simple, noise-robust modification of the standard cross-entropy loss which performs well empirically.
authors.name: MITIGATE LABEL NOISE
authors.name: Aditya Krishna Menon
authors.name: Ankit Singh Rawat
authors.name: Sashank J. Reddi
authors.name: Sanjiv Kumar
references.authors: Martin Abadi Andy Chu Ian Goodfellow H. Brendan McMahan Ilya Mironov Kunal Talwar Li Zhang
references.title: Deep learning with differential privacy
references.venue: In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS
references.authors: Ehsan Amid Manfred K. Warmuth Rohan Anil Tomer Koren
references.title: Robust bi-tempered logistic loss based on Bregman divergences
references.venue: CoRR, abs/1906.03361,
references.authors: Ehsan Amid Manfred K. Warmuth Sriram Srinivasan
references.title: Two-temperature logistic regression based on the Tsallis divergence
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019,
references.authors: D.F. Andrews P.J. Bickel F.R. Hampel P.J. Huber W.H. Rogers J.W. Tukey
references.title: Robust Estimates of Location
references.authors: Peter L Bartlett Michael I Jordan Jon D McAuliffe
references.title: Convexity, classification, and risk bounds
references.venue: Journal of the American Statistical Association,
references.authors: Y. Bengio P. Simard P. Frasconi
references.title: Learning long-term dependencies with gradient descent is difficult
references.venue: Trans. Neur. Netw.,
references.authors: Kush Bhatia Prateek Jain Purushottam Kar
references.title: Robust regression via hard thresholding
references.venue: In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1,
references.authors: Christian Brownlees Emilien Joly Gábor Lugosi
references.title: Empirical risk minimization for heavy-tailed losses
references.venue: Ann. Statist., 43(6):2507–2536,
references.authors: Andreas Buja Werner Stuetzle Yi Shen
references.title: Loss functions for binary class probability estimation and classification: Structure and applications
references.venue: Technical report, UPenn,
references.authors: Olivier Catoni
references.title: Challenging the empirical mean and empirical variance: A deviation study
references.venue: Ann. Inst. H. Poincaré Probab. Statist., 48(4):1148–1185,
references.authors: Nontawat Charoenphakdee Jongyeong Lee Masashi Sugiyama
references.title: On symmetric losses for learning from corrupted labels
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: Jesús Cid-Sueiro Darío García-García Raúl
references.title: Santos-Rodríguez. Consistency of losses for learning from weak labels
references.venue: Machine Learning and Knowledge Discovery in Databases,
references.authors: J.B. Copas
references.title: Binary regression models for contaminated data
references.venue: Journal of the Royal Statistical Society. Series B (Methodological),
references.authors: Nan Ding
references.title: Statistical machine learning in the t-exponential family of distributions
references.venue: PhD thesis, Purdue University,
references.authors: Nan Ding S.V.N. Vishwanathan
references.title: t-logistic regression
references.venue: Advances in Neural Information Processing Systems
references.authors: John Duchi Hongseok Namkoong
references.title: Variance-based regularization with convex objectives
references.venue: Journal of Machine Learning Research,
references.authors: Cynthia Dwork Frank McSherry Kobbi Nissim Adam Smith
references.title: Calibrating noise to sensitivity in private data analysis
references.venue: In Proceedings of the Third Conference on Theory of Cryptography,
references.authors: Anders Ekholm Juni Palmgren
references.title: A model for a binary response with misclassifications
references.venue: GLIM 82: Proceedings of the International Conference on Generalised Linear Models,
references.authors: Jiashi Feng Huan Xu Shie Mannor Shuicheng Yan
references.title: Robust logistic regression and classification
references.venue: Advances in Neural Information Processing Systems
references.authors: Jonas Gehring Michael Auli David Grangier Denis Yarats Yann N. Dauphin
references.title: Convolutional sequence to sequence learning
references.venue: In Proceedings of the 34th International Conference on Machine Learning - Volume 70,
references.authors: Aritra Ghosh Naresh Manwani P.S. Sastry
references.title: Making risk minimization tolerant to label noise
references.authors: Aritra Ghosh Himanshu Kumar P.S. Sastry
references.title: Robust loss functions under label noise for deep neural networks
references.venue: In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence,
references.authors: Tilmann Gneiting Adrian E. Raftery
references.title: Strictly proper scoring rules, prediction, and estimation
references.venue: Journal of the American Statistical Association,
references.authors: I.M. Gross John W. Tukey
references.title: The estimators of the Princeton robustness study
references.venue: Technical report,
references.authors: F.R. Hampel E.M. Ronchetti P.J. Rousseeuw W.A. Stahel
references.title: Robust Statistics: the Approach Based on Influence Functions
references.authors: Bo Han Quanming Yao Xingrui Yu Gang Niu Miao Xu Weihua Hu Ivor W. Tsang Masashi Sugiyama
references.title: Co-teaching: Robust training of deep neural networks with extremely noisy labels
references.venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,
references.authors: Elad Hazan Kfir Y. Levy Shai Shalev-Shwartz
references.title: Beyond convexity: Stochastic quasi-convex optimization
references.venue: In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1,
references.authors: K. He X. Zhang S. Ren J. Sun
references.title: Deep residual learning for image recognition
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Matthew Holland Kazushi Ikeda
references.title: Better generalization with less data using robust gradient descent
references.venue: In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning,
references.authors: Daniel Hsu Sivan Sabato
references.title: Loss minimization and parameter estimation with heavy tails
references.venue: Journal of Machine Learning Research,
references.authors: Weihua Hu Gang Niu Issei Sato Masashi Sugiyama
references.title: Does distributionally robust supervised learning give robust classifiers
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: Peter J. Huber
references.title: Robust estimation of a location parameter
references.venue: Ann. Math. Statist., 35(1):73–101,
references.authors: Peter J. Huber
references.title: Robust Statistics
references.authors: Hung Hung Zhi-Yu Jou Su-Yun Huang
references.title: Robust mislabel logistic regression without modeling mislabel
references.venue: probabilities. Biometrics,
references.authors: Julian Katz-Samuels Gilles Blanchard Clayton Scott
references.title: Decontamination of mutual contamination models
references.venue: Journal of Machine Learning Research,
references.authors: A. Krizhevsky G. Hinton
references.title: Learning multiple layers of features from tiny images
references.venue: Master’s thesis,
references.authors: Guillaume Lecué Matthieu Lerasle Timothée Mathieu
references.title: Robust classification via MOM minimization
references.venue: arXiv e-prints, art
references.authors: Y. Lecun L. Bottou Y. Bengio P. Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: M. Lerasle R.I. Oliveira
references.title: Robust empirical mean Estimators
references.venue: arXiv e-prints, art
references.authors: Kfir Y. Levy
references.title: The power of normalization: Faster evasion of saddle points
references.authors: Tongliang Liu Dacheng Tao
references.title: Classification with noisy labels by importance reweighting
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: Philip M. Long Rocco A. Servedio
references.title: Random classification noise defeats all convex potential boosters
references.venue: Machine Learning,
references.authors: Gabor Lugosi Shahar Mendelson
references.title: Risk minimization by median-of-means tournaments
references.venue: arXiv e-prints, art
references.authors: Eran Malach Shai Shalev-Shwartz
references.title: Decoupling "when to update" from "how to update
references.venue: In Proceedings of the 31st International Conference on Neural Information Processing Systems,
references.authors: R.A. Maronna D. Martin V.J. Yohai
references.title: Robust Statistics: Theory and Methods
references.authors: Hamed Masnadi-Shirazi Nuno Vasconcelos
references.title: On the design of loss functions for classification: theory, robustness to outliers, and SavageBoost
references.venue: Advances in Neural Information Processing Systems
references.authors: Aditya Krishna Menon Robert C. Williamson
references.title: A loss framework for calibrated anomaly detection
references.venue: Advances in Neural Information Processing Systems
references.authors: Aditya Krishna Menon Brendan van Rooyen Cheng Soon Ong Bob Williamson
references.title: Learning from corrupted binary labels via class-probability estimation
references.venue: In International Conference on Machine Learning (ICML),
references.authors: Aditya Krishna Menon Brendan van Rooyen Nagarajan Natarajan
references.title: Learning from binary labels with instance-dependent noise
references.venue: Machine Learning,
references.authors: Stephen Merity Nitish Shirish Keskar Richard Socher
references.title: Regularizing and optimizing LSTM language models
references.venue: In International Conference on Learning Representations,
references.authors: Tomáš Mikolov
references.title: Statistical Language Models Based on Neural Networks
references.venue: PhD thesis, Brno University of Technology,
references.authors: Stanislav Minsker
references.title: Geometric median and robust estimation in banach spaces
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A. Rusu Joel Veness Marc G. Bellemare Alex Graves Martin Riedmiller Andreas K. Fidjeland Georg Ostrovski Stig Petersen Charles Beattie Amir Sadik Ioannis Antonoglou Helen King Dharshan Kumaran Daan Wierstra Shane Legg Demis Hassabis
references.title: Human-level control through deep reinforcement learning
references.venue: Nature, 518(7540):529–533,
references.authors: H. Namkoong J. Duchi
references.title: Variance regularization with convex objectives
references.venue: In Advances in Neural Information Processing Systems (NeurIPS),
references.authors: Hongseok Namkoong John C Duchi
references.title: Stochastic gradient methods for distributionally robust optimization with f-divergences
references.venue: Advances in Neural Information Processing Systems
references.authors: Nagarajan Natarajan Inderjit S Dhillon Pradeep D Ravikumar Ambuj Tewari
references.title: Learning with noisy labels
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: Nagarajan Natarajan Inderjit S. Dhillon Pradeep Ravikumar Ambuj Tewari
references.title: Cost-sensitive learning with noisy labels
references.venue: Journal of Machine Learning Research,
references.authors: Richard Nock Frank Nielsen
references.title: On the efficient minimization of classification calibrated surrogates
references.venue: Advances in Neural Information Processing Systems
references.authors: Razvan Pascanu Tomas Mikolov Yoshua Bengio
references.title: Understanding the exploding gradient problem
references.venue: CoRR, abs/1211.5063,
references.authors: Razvan Pascanu Tomas Mikolov Yoshua Bengio
references.title: On the difficulty of training recurrent neural networks
references.venue: In Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume
references.authors: Giorgio Patrini Frank Nielsen Richard Nock Marcello Carioni
references.title: Loss factorization, weakly supervised learning and label noise robustness
references.venue: In International Conference on Machine Learning (ICML),
references.authors: Giorgio Patrini Alessandro Rozza Aditya Krishna Menon Richard Nock Lizhen Qu
references.title: Making deep neural networks robust to label noise: a loss correction approach
references.venue: In Computer Vision and Pattern Recognition (CVPR),
references.authors: Matthew Peters Mark Neumann Mohit Iyyer Matt Gardner Christopher Clark Kenton Lee Luke Zettlemoyer
references.title: Deep contextualized word representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)
references.authors: Venkatadheeraj Pichapati Ananda Theertha Suresh Felix X. Yu Sashank J. Reddi Sanjiv Kumar
references.title: AdaCliP: Adaptive Clipping for Private SGD
references.venue: arXiv e-prints, art
references.authors: Adarsh Prasad Arun Sai Suggala Sivaraman Balakrishnan Pradeep Ravikumar
references.title: Robust Estimation via Robust Gradient Estimation
references.venue: arXiv e-prints, art
references.authors: Daryl Pregibon
references.title: Resistant fits for some commonly used logistic models with medical applications
references.venue: Biometrics, 38(2):485–498,
references.authors: Mark D. Reid Robert C. Williamson
references.title: Composite binary losses
references.venue: Journal of Machine Learning Research,
references.authors: Saharon Rosset Ji Zhu
references.title: Piecewise linear regularized solution paths
references.venue: Ann. Statist.,
references.authors: Peter J. Rousseeuw Annik M. Leroy
references.title: Robust Regression and Outlier Detection
references.authors: Leonard J. Savage
references.title: Elicitation of personal probabilities and expectations
references.venue: Journal of the American Statistical Association,
references.authors: Mark J. Schervish
references.title: A general method for comparing probability assessors
references.venue: Ann. Statist.,
references.authors: Clayton Scott Gilles Blanchard Gregory Handy
references.title: Classification with asymmetric label noise: consistency and maximal denoising
references.venue: In Conference on Learning Theory (COLT),
references.authors: Soroosh Shafieezadeh-Abadeh Peyman Mohajerin Esfahani Daniel Kuhn
references.title: Distributionally robust logistic regression
references.venue: In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1,
references.authors: Yanyao Shen Sujay Sanghavi
references.title: Learning with bad training data via iterative trimmed loss minimization
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: Georgy Shevlyakov Stephan Morgenthaler Alexander
references.title: Shurygin. Redescending m-estimators
references.venue: Journal Of Statistical Planning And Inference,
references.authors: Aman Sinha Hongseok Namkoong John C. Duchi
references.title: Certifying some distributional robustness with principled adversarial training
references.venue: In 6th International Conference on Learning Representations,
references.authors: Hwanjun Song Minseok Kim Jae-Gil Lee
references.title: SELFIE: Refurbishing unclean samples for robust deep learning
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: T. Sypherd M. Diaz L. Sankar P. Kairouz
references.title: A tunable loss function for binary classification
references.venue: IEEE International Symposium on Information Theory (ISIT),
references.authors: Takashi Takenouchi Shinto Eguchi
references.title: Robustifying AdaBoost by adding the naive error rate
references.venue: Neural Computation,
references.authors: Sunil Thulasidasan Tanmoy Bhattacharya Jeff Bilmes Gopinath Chennupati Jamal Mohd-Yusof
references.title: Combating label noise in deep learning using abstention
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: J.W. Tukey
references.title: A survey of sampling from contaminated distributions
references.venue: Contributions to probability and statistics,
references.authors: Brendan van Rooyen Robert C. Williamson
references.title: A theory of learning with corrupted labels
references.venue: Journal of Machine Learning Research,
references.authors: Brendan van Rooyen Aditya Krishna Menon Robert C. Williamson
references.title: Learning with symmetric label noise: the importance of being unhinged
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: Robert C. Williamson Elodie Vernet Mark D. Reid
references.title: Composite multiclass losses
references.venue: Journal of Machine Learning Research,
references.authors: Eunho Yang Aurélie C. Lozano Aleksandr Aravkin
references.title: A general family of trimmed estimators for robust high-dimensional data analysis
references.venue: Electron. J. Statist.,
references.authors: Min Yang Linli Xu Martha White Dale Schuurmans Yao liang Yu
references.title: Relaxed clipping: A global training method for robust regression and classification
references.venue: Advances in Neural Information Processing Systems
references.authors: Jingzhao Zhang Tianxing He Suvrit Sra Ali Jadbabaie
references.title: Analysis of gradient clipping and adaptive scaling with a relaxed smoothness condition
references.venue: arXiv e-prints, art
references.authors: Tong Zhang
references.title: Statistical behavior and consistency of classification methods based on convex risk minimization
references.venue: Annals of Statistics,
references.authors: Tong Zhang David Johnson
references.title: A robust risk minimization based named entity recognition system
references.venue: In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL
references.authors: Tong Zhang Fred Damerau David Johnson
references.title: Text chunking based on a generalization of winnow
references.venue: J. Mach. Learn. Res.,
references.authors: Zhilu Zhang Mert R. Sabuncu
references.title: Generalized cross entropy loss for training deep neural networks with noisy labels
references.venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,
references.authors: van Rooyen
references.title: Risk minimiser for the partially Huberised logistic loss. Proof of Proposition 7. Let Rτ (f) denote the risk on the clean distribution of a predictor f with respect to the partially Huberised loss φ̃τ with parameter τ . Similarly, let R̄τ (f) denote the risk on the noisy distribution
sections.heading: 1 INTRODUCTION: TWO FACES OF GRADIENT CLIPPING
sections.text: Gradient clipping is a widely-used technique in the training of deep networks (Mikolov, 2012; Pascanu et al., 2012; 2013; Mnih et al., 2015; Gehring et al., 2017; Merity et al., 2018; Peters et al., 2018), and in its simplest form, involves capping the global parameter gradient norm at a specified threshold. Constraining the gradient norm is paramount in training models such as recurrent neural networks, which may otherwise suffer from an “exploding gradient” problem (Bengio et al., 1994). Clipping has seen broader value in other neural models, and is abstractly understood as being valuable from an optimisation lens: intuitively, by ensuring that the gradient norm is not too large, the dynamics of iterates are more well-behaved (Hazan et al., 2015; Levy, 2016; Zhang et al., 2019). A distinct line of work has also explored the value of gradient clipping from a privacy lens (Abadi et al., 2016; Pichapati et al., 2019): intuitively, it prevents any single instance from overly influencing parameter updates, which is a core requirement in ensuring differential privacy (Dwork et al., 2006).
  In this paper, we propose a new lens with which to study gradient clipping, namely, robustness: intuitively, clipping the gradient prevents over-confident descent steps, which is plausibly beneficial in the presence of noise. Given this intuition, our interest is whether gradient clipping can mitigate the problem of label noise in classification, which has received significant recent interest (Scott et al., 2013; Natarajan et al., 2013; Menon et al., 2015; Liu & Tao, 2016; Patrini et al., 2017; Ghosh et al., 2017; Han et al., 2018; Zhang & Sabuncu, 2018; Song et al., 2019; Thulasidasan et al., 2019; Charoenphakdee et al., 2019). We study this question, and provide three main contributions:
  (a) we show that gradient clipping alone does not endow label noise robustness to even simple models. Specifically, we show that under stochastic gradient descent with linear models, gradient clipping is related to optimising a “Huberised” loss (Lemma 1, 2). While such Huberised losses preserve classification calibration (Lemma 3), they are not robust to label noise (Proposition 4).
  (b) we propose composite loss-based gradient clipping, a variant that does have label noise robustness. Specifically, for losses comprising a base loss composed with a link function, (e.g., softmax crossentropy), we only clip the contribution of the base loss. The resulting partially Huberised loss preserves classification calibration (Lemma 6), while being robust to label noise (Proposition 7).
  (c) we empirically verify that on both synthetic and real-world datasets, partially Huberised versions of standard losses (e.g., softmax cross-entropy) perform well in the presence of label noise (§5).
  To illustrate the difference between standard and composite loss-based gradient clipping in (a) and (b), consider the pervasive softmax cross-entropy loss, viz. the logistic loss for binary classification. In (a), we relate gradient clipping to loss “Huberisation”, which linearises the logistic loss when it exceeds a fixed threshold. In (b), we introduce composite loss-based gradient clipping, which is equivalent to a “partial loss Huberisation” that linearises only the cross-entropy loss but leaves the sigmoid link untouched. Figure 1 illustrates the Huberised and partially Huberised logistic loss.
sections.heading: 2 BACKGROUND AND RELATED WORK
sections.text: We provide background on gradient clipping, loss functions for classification, and label noise.
  Gradient clipping. Consider a supervised learning task over instances X and labels Y, where we have a family of models indexed by θ ∈ Θ, and the quality of a particular model is measured by a loss function `θ : X× Y→ R. The gradient for a mini-batch {(xn, yn)}Nn=1 is
  g(θ) . =
  1
  N N∑ n=1 ∇`θ(xn, yn). (1)
  One may instead compute the clipped gradient, which for user-specified threshold τ > 0 is
  ḡτ (θ) . = clipτ (g(θ)) clipτ (w) . = { τ · w||w||2 if ||w||2 ≥ τ w else.
  (2)
  Employing ḡτ (θ) for optimisation corresponds to clipped gradient descent. This is closely related to normalised gradient descent (NGD) (Hazan et al., 2015), wherein one employs g̃(θ) .= g(θ)||g(θ)||2 . Hazan et al. (2015) showed that NGD can lead to convergence for a wider class of functions than standard gradient descent. Levy (2016) showed that NGD can escape saddle points for non-convex problems. Zhang et al. (2019) showed that gradient clipping can lead to accelerated convergence over gradient descent. Gradient clipping has also been explored for privacy (Abadi et al., 2016; Pichapati et al., 2019), motivated by it preventing any single instance from dominating parameter updates.
  Loss functions. In binary classification, one observes samples from a distribution D over X× {±1}, and seeks a predictor f : X→ R with low risk R(f) .= E `(y, f(x)) according to a loss which, in an overload of notation, we denote ` : {±1} × R→ R+. For the zero-one loss `01(y, f) = Jy · f < 0K, R(f) is known as the misclassification risk. Rather than directly using `01, for computational convenience one often employs a margin loss `(y, f) = φ(y · f), for convex φ : R→ R+. We say that φ is classification calibrated (Zhang, 2004; Bartlett et al., 2006) if driving the excess risk over the Bayes-optimal predictor for φ to zero also drives the excess risk for `01 to zero; that is,
  minimising the φ-risk is statistically consistent for classification. A canonical example is the hinge loss φ(z) = [1 − z]+. We call φ admissible if it is “well-behaved” in the sense of being bounded from below, strictly convex, continuously differentiable, non-increasing, and classification calibrated.
  We say that φ is proper composite (Reid & Williamson, 2010; Nock & Nielsen, 2009) (or for brevity composite) if its minimising scores can be interpreted as probabilities. “Composite” here refers to such losses comprising a base loss ϕ composed with an invertible link function F : R→ [0, 1]. While φ accepts as input real-valued scores (e.g., the final layer logits of a neural network), these are internally converted to probabilities via F . A canonical example is the logistic loss φ(z) = − logF (z) with F : z 7→ σ(z) for sigmoid σ(z) .= (1+e−z)−1. The multiclass analogue is the softmax cross-entropy loss, wherein the sigmoid becomes a softmax. See Appendix B for a more technical discussion.
  Learning under label noise. In classification under label noise, one has samples from distribution D̄ where PD̄(y | x) is a noisy version of PD(y | x), e.g., all labels are corrupted with a fixed constant probability. The goal remains to ensure low risk with respect to the clean D. This problem has a long history in statistics (Ekholm & Palmgren, 1982; Copas, 1988), and has emerged as a topic of recent interest in machine learning. There has been particular interest in the problem of learning under symmetric label noise, wherein all instances have a constant probability of their labels being flipped uniformly to any of the other classes. Scott et al. (2013); Katz-Samuels et al. (2019) proposed a framework for analysing the more general setting of class-conditional label noise. Takenouchi & Eguchi (2004); Natarajan et al. (2013); Cid-Sueiro et al. (2014); Patrini et al. (2017); Natarajan et al. (2018); van Rooyen & Williamson (2018) studied loss-correction for obtaining unbiased risk estimators. Recent works have explored ideas ranging from to model (dis)agreement (Malach & Shalev-Shwartz, 2017; Han et al., 2018; Song et al., 2019) to abstention (Thulasidasan et al., 2019).
sections.heading: 3 GRADIENT CLIPPING AND HUBERISED LOSSES
sections.text: We first show that gradient clipping in general does not endow robustness to label noise, even in simple settings. Specifically, we establish that stochastic gradient clipping with linear models is equivalent to modifying the underlying loss (Lemma 1). This modified loss is closely related to a Huberised loss (Lemma 2), which is equivalent to loss-based gradient clipping (L-gradient clipping). Unfortunately, Huberised losses, and thus L-gradient clipping, are not robust to label noise (Proposition 4).
sections.heading: 3.1 FROM GRADIENT TO L-GRADIENT CLIPPING
sections.text: Consider a binary classification problem, with Y = {±1}. Suppose we use a scoring model sθ(x) for θ ∈ Θ with margin mθ(x, y) .= y · sθ(x), and margin loss `θ(x, y) .= φ(mθ(x, y)) for admissible φ : R→ R+. Then,
  ∇θ`θ(x, y) = ∇θmθ(x, y) · φ′(mθ(x, y)). (3)
  Now suppose we perform stochastic gradient descent (i.e., we use N = 1 in (1)) and use a linear scorer sθ(x) = θTx. Here, gradient clipping of (3) is equivalent to modifying the loss as follows. Lemma 1. Pick any admissible margin loss φ, and τ > 0. Then, for loss `θ(x, y) . = φ(mθ(x, y)) with linear scorer, the clipped loss gradient (2) is equivalent to the gradient of a modified loss ¯̀:
  clipτ (∇`θ(x, y)) = ∇¯̀θ(x, y),
  with ¯̀θ(x, y) . =
  { − τ‖∇mθ(x,y)‖2 ·mθ(x, y) if |φ
  ′(mθ(x, y))| ≥ τ‖∇mθ(x,y)‖2 φ(mθ(x, y)) else.
  (4)
  The loss ¯̀ in (4) is intuitive: if the derivative of the original loss φ exceeds a certain effective clipping threshold, we replace φ with a linear loss function. This effective threshold τ · (‖∇mθ(x, y)‖2)−1 takes into account the instance-dependent margin gradient, viz. ‖x‖2 for linear sθ(x). We will comment in §4.4 as to the properties of gradient clipping in more general scenarios. For the moment, we note that Lemma 1 is closely related to the “Huber loss” (Huber, 1964),
  `huber(x, y; θ) = { τ · |sθ(x)− y| if |sθ(x)− y| ≥ τ 1 2 · (sθ(x)− y)2 else.
  (5)
  This replaces the extremes of the square loss with the absolute loss. Both the absolute and Huber losses are widely employed in robust regression (Huber, 1981, Chapter 3), (Hampel et al., 1986, pg. 100). Note that (4) slightly differs from (5) as the effective clipping threshold is instance-dependent. One may nonetheless arrive at Huber-style losses via a variant of gradient clipping; this connection will prove useful for our subsequent analysis. Per (3), gradient clipping involves using
  clipτ (∇`θ(x, y)) = clipτ (∇mθ(x, y) · φ′(mθ(x, y))) , (6) wherein the clipping considers the margin gradient. Consider now the following loss-based gradient clipping (L-gradient clipping), wherein we clip only the contribution arising from the loss:
  l-clipτ (∇`θ(x, y)) . = ∇mθ(x, y) · clipτ (φ′(mθ(x, y))) . (7)
  Compared to (6), we effectively treat the margin gradient norm ‖∇mθ(x, y)‖2 as constant across instances, and focus on bounding the loss derivative. The latter may be a significant component in the gradient norm; e.g., for linear models, ‖∇mθ(x, y)‖2 = ‖x‖2 is often bounded. Observe further that for linear models with ‖x‖2 ≡ R across instances, (7) is a rescaled version of the clipped gradient:
  clipτ (∇`θ(x, y)) = τ · y · x · φ′(mθ(x, y))
  τ ∨ (R · |φ′(mθ(x, y))|) = ∇mθ(x, y) · clipτ/R (φ′(mθ(x, y))) .
  Interestingly, L-gradient clipping equivalently uses the following “Huberised” version of the loss. Lemma 2. Pick any admissible margin loss φ : R → R+ with Fenchel conjugate φ∗, and τ > 0. Then, the clipped gradient in (7) is equivalent to employing a Huberised loss function φ̄τ such that
  clipτ (φ ′(z)) = φ̄′τ (z) with φ̄τ (z) . = {−τ · z − φ∗(−τ) if φ′(z) ≤ −τ φ(z) else.
  (8)
  Evidently, φ̄τ linearises φ once its derivative is sufficiently large, akin to the Huber loss in (5). One may verify that for φ(z) = (1− z)2, one arrives exactly at (5).
  Example 3.1: For the logistic loss φ(z) = log(1 + e−z), the Huberised loss for τ ∈ (0, 1) is
  φ̄τ (z) = {−τ · z − log(1− τ)− τ · σ−1 (τ) if z ≤ −σ−1 (τ) log(1 + e−z) else.
  Per Figure 1a, this linearises φ beyond a fixed threshold. See Appendix C for further illustrations.
  The use of Huberised losses in classification is not new (Zhang et al., 2002; Zhang & Johnson, 2003; Rosset & Zhu, 2007). However, we now provide a novel study of their label noise robustness.
sections.heading: 3.2 CONSISTENCY AND LABEL-NOISE ROBUSTNESS OF HUBERISED LOSSES
sections.text: Before studying the effect of label noise on Huberised losses, it is apposite to consider whether they are suitable for use even in the absence of noise. One way to formalise this is to ask whether the losses maintain classification calibration, in the sense of §2. This is a minimal requirement on a loss to be useful for classification (Zhang, 2004; Bartlett et al., 2006). One may further ask whether the losses preserve class-probabilities, i.e., are proper composite in the sense of §2. It is desirable to preserve this key trait of losses such as the logistic loss. The following clarifies both points. Lemma 3. Pick any admissible margin loss φ and τ > 0. Then, the Huberised loss φ̄τ in (8) is classification calibrated. If φ is proper composite and τ ≥ −φ′(0), then φ̄τ is also proper composite.
  L-gradient clipping is thus benign for classification, generalising Rosset & Zhu (2007, Section 3.4), which was for the square-hinge loss. Interestingly, for composite φ and small τ , the proof reveals that φ̄τ has a non-invertible link function. Intuitively, such φ̄τ are effectively linear, and linear losses are unsuited for estimating probabilities (van Rooyen et al., 2015; Charoenphakdee et al., 2019).
  We now turn to our central object of inquiry: does gradient clipping endow robustness to label noise? To study this, we consider L-gradient clipping, which as noted above is a special case of gradient clipping under linear models with constant ‖∇mθ(x, y)‖2. Since L-gradient clipping is in turn equivalent to using a Huberised loss, we may study the robustness properties of this loss.
  Surprisingly, when our loss is convex (e.g., softmax cross-entropy), Huberised losses are not robust to even very simple forms of label noise. Essentially, since these losses are still convex, they can still be affected by errant outlier observations. Formally, using a result of Long & Servedio (2010) (see Appendix E.1), we arrive at the following. Proposition 4. Pick any admissible margin loss φ and τ > 0. Then, ∃ a separable distribution for which the optimal linear classifier under φ̄τ is equivalent to random guessing under symmetric noise.
  To situate Proposition 4 in a broader context, we note that for regression problems, it is well known that the Huber loss is susceptible to “high leverage” outliers (Hampel et al., 1986, pg. 313), (Rousseeuw & Leroy, 1987, pg. 13), (Maronna et al., 2019, pg. 104), i.e., extremal instances which dominate the optimal solution. Proposition 4 complements these for the case of label noise in classification.
  Given that gradient clipping does not endow label noise robustness, how else might we proceed? In a regression context, the outlier vulnerability of the Huber loss can be addressed by using a trimmed average of the loss (Rousseeuw & Leroy, 1987; Bhatia et al., 2015; Yang et al., 2018). Such ideas have been successfully explored for label noise problems (Shen & Sanghavi, 2019). We will however demonstrate that a simple variant of clipping yields a loss that does possess label noise robustness.
sections.heading: 4 COMPOSITE LOSS-BASED GRADIENT CLIPPING
sections.text: We now show that noise robustness can be achieved with CL-gradient clipping, a variant wherein for composite losses (e.g., softmax cross-entropy), we perform partial Huberisation of the base loss only.
sections.heading: 4.1 FROM HUBERISATION TO PARTIAL HUBERISATION
sections.text: Consider a composite margin loss `θ(x, y) . = φ(mθ(x, y)), where φ = ϕ ◦ F for some base loss ϕ and invertible link F : R̄→ [0, 1]; e.g., the logistic loss has ϕ(u) = − log u and F (z) = σ(z). We can interpret pθ(x, y) . = F (mθ(x, y)) as a probability estimate; e.g., pθ(x, 1) = σ(mθ(x, 1)) is the probability of x being positive. Now, rewriting `θ(x, y) = ϕ(pθ(x, y)), we may express (3) as: ∇`θ(x, y) = ∇pθ(x, y) · ϕ′(pθ(x, y)). L-gradient clipping in (7) was defined as only clipping φ′ = (ϕ ◦ F )′ above, which ensures that the resulting Huberised loss is Lipschitz. Typically, however, F is already Lipschitz; e.g., this is the case for the commonly used sigmoid or softmax link. This suggests the following composite loss-based gradient clipping (CL-gradient clipping), wherein we only clip the derivative for the base loss ϕ:
  cl-clipτ (∇`θ(x, y)) . = ∇pθ(x, y) · clipτ (ϕ′(pθ(x, y))) . (9)
  As before, CL-gradient clipping corresponds to optimising a new, “partially Huberised” loss. Lemma 5. Pick any admissible, composite margin loss φ = ϕ ◦ F , and τ > 0. Then, the clipped gradient in (9) is equivalent to employing a partially Huberised loss φ̃τ = ϕ̃τ ◦ F , where
  ϕ̃τ (u) . = {−τ · u− ϕ∗(−τ) if ϕ′(u) ≤ −τ ϕ(u) else.
  (10)
  Compared to the Huberised loss (7), the partially Huberised loss only linearises the base loss ϕ, while retaining the link F . Consequently, the composite loss φ̃τ behaves like the link beyond a certain threshold, and will thus be bounded: indeed, φ̃τ (z) = −τ · F (z)− ϕ∗(−τ) if ϕ′(F (z)) ≤ −τ .
  Example 4.1: For the logistic loss, φ(z) = ϕ(F (z)) with ϕ(u) = − log u and F (z) = σ(z),
  φ̃τ (z) = {−τ · σ(z) + log τ + 1 if z ≤ σ−1 ( 1τ ) log(1 + e−z) else.
  (11)
  Note that partial Huberisation readily generalises to a multi-class setting. Indeed, suppose we have softmax probability estimates pθ(x, y) ∝ exp(mθ(x, y)). Then, whereas the softmax cross-entropy employs `θ(x, y) = − log pθ(x, y), our partially Huberised softmax cross-entropy for τ > 1 is
  ˜̀ θ(x, y) = {−τ · pθ(x, y) + log τ + 1 if pθ(x, y) ≤ 1τ − log pθ(x, y) else.
  (12)
sections.heading: 4.2 CONSISTENCY AND LABEL NOISE ROBUSTNESS OF PARTIALLY HUBERISED LOSSES
sections.text: Following §3.2, we establish that CL-gradient clipping is always benign from a classification perspective, and provided τ is sufficiently large, from a probability estimation perspective as well. As before, we do this by exploiting the equivalence of CL-gradient clipping to a partially Huberised loss. Lemma 6. Pick any admissible composite margin loss φ = ϕ ◦ F and τ > 0. Then, the loss φ̃τ in (10) is classification calibrated. If further τ ≥ −ϕ′(1/2), then ϕ̃τ is also proper composite. We now show that partially Huberised losses have an important advantage over Huberised losses: under symmetric label noise, the optimal solution on the clean distribution cannot be too far away from the optimal solution on the noisy distribution. This implies that label noise (such as that considered in Proposition 4) cannot have an excessively deleterious influence on the loss. Proposition 7. Pick any proper loss ϕ and τ > 0. Let f∗ be the risk minimiser of ϕ̃τ on the clean distribution. For any non-trivial level of symmetric label noise, let regτ (f
  ∗) denote the excess risk of f∗ with respect to ϕ̃τ on the noisy distribution. Then, there exists C > 0 such that regτ (f
  ∗) ≤ C. Note that by van Rooyen et al. (2015, Proposition 4), it is impossible for the above bound to hold with C = 0 without using a linear loss. Nonetheless, by virtue of partially Huberised losses being partially linear, we are able to bound the degradation under label corruption. The saturating behaviour of the partially Huberised loss also implies robustness to outliers in feature space; see Appendix D.
sections.heading: 4.3 RELATION TO EXISTING WORK
sections.text: The partially Huberised log loss in (10), (11) can be related to a family of losses studied in several works (Ding & Vishwanathan, 2010; Hung et al., 2018; Zhang & Sabuncu, 2018; Sypherd et al., 2019; Amid et al., 2019b;a): for α ∈ (0, 1], define the generalised cross-entropy ϕα : [0, 1] → R̄+ by ϕα(u) . = (1− uα)/α. See Appendix C.3 for an illustration of ϕα. There are two similarities between (11) and ϕα. First, both proposals interpolate between the log and linear losses: when α → 0+, ϕα approaches the log loss, and when α = 1, ϕα equals the linear loss. Second, both proposals modify the base loss, allowing the link F to be chosen independently. In particular, one may use the heavy-tailed F of Ding & Vishwanathan (2010); Amid et al. (2019b) in conjunction with our partially Huberised loss.
  One difference between (11) and ϕα is that the partially Huberised loss is exactly linear for a suitable region; consequently, it is guaranteed to be Lipschitz, unlike ϕα. This can be understood in terms of the loss gradients: for a class-probability estimate pθ(x, y), let `θ(x, y) . = ϕ(pθ(x, y)). For the generalised cross-entropy, ∇`θ(x, y) = −pθ(x, y)α−1 · ∇pθ(x, y), while for the partially Huberised loss,∇`θ(x, y) = −(pθ(x, y) ∨ τ)−1 · ∇pθ(x, y). Both gradients thus take into account whether a sample is “informative”, in the sense of being poorly-predicted (pθ(x, y) ∼ 0). Further, to guard against such samples being the result of label noise, both ensure this influence is not overwhelming, but in different ways: the generalised cross-entropy softens the influence, while still allowing it to be unbounded as pθ(x, y)→ 0. On the other hand, the partially Huberised loss enforces a hard cap of τ−1 on the influence. This is to be contrast with a truncated loss also considered in Zhang & Sabuncu (2018), which enforces a hard cap on the loss, thus completely discarding poorly-predicted instances.
  As shown in Figure 1a, the partially Huberised loss in (10) exhibits saturating behaviour at the extremes. This by itself is hardly new in the context of robust statistics. For example, Tukey’s “biweight” loss replaces the Huber loss’ linear behaviour with hard saturation (Gross & Tukey, 1973), and is a member of the broader family of redescending M-estimators (Andrews et al., 1972; Shevlyakov et al., 2008). In a similar spirit, Masnadi-Shirazi & Vasconcelos (2009) proposed the bounded Savage loss ϕ(v) = (σ(2v)− 1)2, while Yang et al. (2010); Menon & Williamson (2018) theoretically studied loss clipping. Robust versions of logistic regression derived by variants of the Huber loss have been explored, e.g., Pregibon (1982, Section 4.1), Copas (1988, Section 3.1), (Feng et al., 2014).
  The distinction of the above proposals to our work is two-fold. First, we explicitly consider the classification setting, wherein we show consistency and robustness to label noise for the partially Huberised loss. Second, our proposal explicitly highlights the connection to gradient clipping.
  Finally, while our focus has been on label noise, there are other notions of “robustness”. Indeed, several works have proposed means of making gradient descent robust to heavy-tailed distributions
  Clipping type Clipped gradient form Equivalent loss Reference Label noise robust?
  y · sθ(x), and differentiable composite margin loss φ(z). This loss internally converts scores to probabilities p(θ) .= F (m(θ)) for link function F (·), which is evaluated with some base loss ϕ; i.e., φ = ϕ ◦ F . Gradient clipping applies to the full loss, i.e., φ(m(θ)). L-gradient clipping applies only to the composite loss, leaving the score untouched; this is equivalent to using a Huberised loss. CL-gradient clipping applies only to the base loss, leaving the link untouched; this is equivalent to using a partially Huberised loss. Only the latter has robustness guarantee under symmetric label noise.
  or outliers (Brownlees et al., 2015; Hsu & Sabato, 2016; Lugosi & Mendelson, 2016; Lecué et al., 2018; Prasad et al., 2018; Holland & Ikeda, 2019), typically by passing the gradient through a robust operator (Tukey, 1960; Hampel et al., 1986; Rousseeuw & Leroy, 1987; Lerasle & Oliveira, 2011; Catoni, 2012; Minsker, 2015). By contrast, we analyse the (simpler) gradient clipping approach, showing that while it is inadequate to cope with label noise, a simple modification rectifies this. Since our proposal only modifies the underlying loss, it may be combined with any of these methods.
sections.heading: 4.4 DISCUSSION AND IMPLICATIONS
sections.text: Table 1 summarises our results, highlighting the perspective of gradient clipping as equivalently modifying the loss. Before proceeding, we make some qualifying comments. First, our analysis has assumed symmetric label noise. Often, one encounters asymmetric or instance-dependent noise (Menon et al., 2018). While corresponding guarantees for the linear loss may be ported over to the partially Huberised loss, they require stronger distributional assumptions (Ghosh et al., 2015).
  Second, Proposition 4 exhibits a specific distribution which defeats the Huberised loss under linear models. In practice, distributions may be more benign (Patrini et al., 2016), and models are often nonlinear, meaning that Huberised losses (and thus gradient clipping) are thus unlikely to succumb as extremely to label noise as Proposition 4 suggests. The aim of §4 is however to establish that a simple modification of clipping avoids worst-case degradation, without adding significant complexity.
  Third, for minibatch size N > 1, the effect of clipping is not a simple loss modification, since the loss gradients for each sample will be modified by the entire minibatch loss gradient norm ‖g(θ)‖2. Since this minibatch is randomly drawn, one cannot mimic gradient clipping by a simple modification of the loss function. However, the results for N = 1 suffice to establish that gradient clipping cannot in general endow robustness. One may use our partially Huberised loss in conjunction with minibatch gradient clipping, to potentially obtain both robustness and optimisation benefits.
  Finally, partially Huberised losses such as (12) require setting a hyperparameter τ (e.g., by crossvalidation), similar to α in the generalised cross-entropy per §4.3. Intuitively, the optimal τ trades off the noise-robustness of the linear loss, and the gradient informativeness of the base loss (per the discussion in §4.3). Setting τ to be large tacitly assumes that one’s samples are largely noise-free.
sections.heading: 5 EXPERIMENTAL ILLUSTRATION
sections.text: We now present experiments illustrating that: (a) we may exhibit label noise scenarios that defeat a Huberised but not partially Huberised loss, confirming Propositions 4, 7, and (b) partially Huberised versions of existing losses perform well on real-world datasets subject to label noise.
  Synthetic datasets. Our first experiments involve two synthetic datasets, which control for confounding factors. We begin with a setting from Long & Servedio (2010), comprising a 2D linearly separable distribution. (See Appendix E.1 for an illustration.) We draw N = 1, 000 random samples from this distribution, and flip each label with ρ = 45% probability. We train a linear classifier to minimise one of several losses, and evaluate the classifier’s accuracy on 500 clean test samples.
  We compare the logistic loss with its Huberised and partially Huberised versions, using τ = 1 and τ = 2 respectively. Figure 2a presents the results over 500 independent trials. The logistic loss and its Huberised counterpart suffer significantly under noise, while the partially Huberised loss often achieves perfect near-discrimination. This confirms that in the worst case, L-gradient clipping may succumb to noise, while CL-gradient clipping performs well in the same scenario.
  We next consider a 1D setting based on Ding (2013, Section 3.2.3), comprising 10, 000 linearly separable “inliers” and 50 “outliers”. Assuming the use of a linear model parameterised by scalar θ ∈ R, we plot the empirical risk of the samples with and without the outlier observations as θ is varied. Figure 2b shows that the logistic loss and its Huberised variant are strongly affected by the outliers: their optimal solution goes from θ∗ = +∞ to θ∗ = 0. However, the partially Huberised loss is largely immune to the outliers. Appendix E contains additional details on this experiment.
  Real-world datasets. We now demonstrate that partially Huberised losses perform well with deep neural networks trained on MNIST, CIFAR-10 and CIFAR-100 (Krizhevsky & Hinton, 2009). For MNIST, we train a LeNet (Lecun et al., 1998) using Adam with batch size N = 32, and weight decay
  of 10−3. For CIFAR-10 and CIFAR-100, we train a ResNet-50 (He et al., 2016) using SGD with momentum 0.1, weight decay of 5× 10−3, batch normalisation, and N = 64, 128 respectively. For each dataset, we corrupt the training labels with symmetric noise at flip probability ρ ∈ {0.0, 0.2, 0.4, 0.6}. We compare the test set accuracy of various losses combined with a softmax link. Our baseline is the cross-entropy loss (CE). As representative noise-robust losses, we consider the linear or unhinged loss (van Rooyen et al., 2015; Ghosh et al., 2017), and the generalised cross-entropy (GCE) with α = 0.7, following Zhang & Sabuncu (2018). We additionally assess global gradient clipping (with τ = 0.1) of the CE, which per §3 is akin to a Huberised loss.
  We apply our partial Huberisation of (10) to the CE (12) (“PHuber-CE”), and the GCE (“PHuberGCE”). The latter highlights that partial Huberisation is not tied to the cross-entropy, and is applicable even on top of existing noise-robust losses. Recall that partial Huberisation offers a choice of tuning parameter τ , similar to the α parameter in GCE, and noise-rate estimates in loss-correction techniques more generally. For each dataset, we pick τ ∈ {2, 10} (equivalently corresponding to probability thresholds 0.5 and 0.1 respectively) so as to maximise accuracy on a validation set of noisy samples with the maximal noise rate ρ = 0.6; the chosen value of τ was then used for each noise level. Tuning τ separately for each setting of the noise rate ρ can be expected to help performance, at the expense of increased computational cost. Recall also that as τ → 1, partial Huberisation mimics using the base loss, while as τ → +∞, partial Huberisation mimics using the linear loss; our hypothesis is that an intermediate τ can attain a suitable balance between noise robustness, and gradient informativeness.
  Table 2 shows that in the noise-free case (ρ = 0.0), all methods perform comparably. However, when injecting noise, accuracy for the CE degrades dramatically. Further, gradient clipping sometimes offers improvements under high noise; however, the performance is far inferior to other losses, which is in keeping with their robustness guarantees. Indeed, the linear loss, which is provably robust to symmetric noise, generally performs well even when ρ = 0.6. However, optimisation under this loss is more challenging, since the gradient does not account for instances’ importance (per §4.3). This is particularly reflected on the CIFAR-100 dataset, where this loss suffers to learn even under no noise. The GCE and partially Huberised losses do not suffer from this issue, even at high noise levels.
  Generally, the partially Huberised losses are competitive with or improve upon the counterpart losses they build upon. In particular, the partially Huberised CE performs much better than the CE under high noise, while the partially Huberised GCE slightly bumps up the GCE numbers on CIFAR-100. This indicates that partially Huberised may be useful in combining with generic base losses to cope with noise. We reiterate here that our partially Huberised loss may be used in conjunction with other ideas, e.g., pruning (Zhang & Sabuncu, 2018), consensus (Malach & Shalev-Shwartz, 2017; Han et al., 2018), or abstention (Thulasidasan et al., 2019). We leave such exploration for future work.
sections.heading: 6 CONCLUSION AND FUTURE WORK
sections.text: We established that gradient clipping by itself does not suffice to endow even simple models with label noise robustness; however, a simple variant resolves this issue. Experiments confirm that our composite loss-based gradient clipping performs well on datasets corrupted with label noise. One interesting direction for future work is to analyse the behaviour of gradient-clipping inspired losses for the more general problem of distributionally robust learning (Shafieezadeh-Abadeh et al., 2015; Namkoong & Duchi, 2016; 2017; Hu et al., 2018; Sinha et al., 2018; Duchi & Namkoong, 2019).
sections.heading: A PROOFS OF RESULTS
sections.text: Proof of Lemma 1. Following Equation 3, ∇`θ(x, y) = ∇mθ(x, y) · φ′(mθ(x, y)). Similarly, for the linear loss function `lin(x, y; θ) . = −mθ(x, y), we have ∇`lin(x, y; θ) = −∇mθ(x, y). To compute the normalised gradient, we need ‖∇`θ(x, y)‖2 = ‖∇mθ(x, y)‖2 · |φ′(mθ(x, y))|. Thus,
  ∇`θ(x, y) ‖∇`θ(x, y)‖2 = 1 ‖∇mθ(x, y)‖2 · ∇mθ(x, y) · φ′(mθ(x, y)) |φ′(mθ(x, y))|
  = 1 ‖∇mθ(x, y)‖2 · ∇mθ(x, y) · sign(φ′(mθ(x, y)))
  = 1
  ‖∇mθ(x, y)‖2 · ∇`lin(x, y; θ),
  since φ′(z) < 0 by assumption that φ is admissible, and thus decreasing. Consequently, if N = 1, ḡ(θ) = clipτ (∇`θ(x, y)) = { τ ‖∇mθ(x,y)‖2 · ∇`lin(x, y; θ) if |φ
  ′(mθ(x, y))| ≥ τ‖∇mθ(x,y)‖2 ∇`θ(x, y) else.
  Assuming a linear scorer s(x; θ) = θTx, the score gradient ∇s(x; θ) = x, which is independent of θ. The clipped gradient thus corresponds to the gradient under a “Huberised” loss function
  ¯̀ θ(x, y) =
  { τ
  ‖∇mθ(x,y)‖2 · `lin(x, y; θ) if |φ ′(mθ(x, y))| ≥ τ‖∇mθ(x,y)‖2 `θ(x, y) else.
  Proof of Lemma 2. Since φ is strictly convex and decreasing, it must be strictly decreasing. We have
  clipτ (φ ′(z)) =
  { τ · φ
  ′(z) |φ′(z)| if |φ′(z)| ≥ τ
  φ′(z) else
  = { τ · sign(φ′(z)) if |φ′(z)| ≥ τ φ′(z) else
  = {−τ if φ′(z) ≤ −τ φ′(z) else since φ′ is strictly decreasing
  = {−τ if z ≤ (φ′)−1(−τ) φ′(z) else,
  where (φ′)−1 exists since φ′ is strictly inceasing by definition of strict convexity.
  Now, by definition, the Huberised loss is
  φ̄τ (z) = {−τ · z − φ∗(−τ) if φ′(z) ≤ −τ φ(z) else,
  and so
  φ̄′τ (z) = {−τ if φ′(z) ≤ −τ φ′(z) else,
  which exactly equals clipτ (φ′(z)). We remark here that φ̄τ is continuous, since for any convex conjugate, φ∗(−u) = −u · (φ′)−1(−u)− φ((φ′)−1(−u)). Plugging in u = τ , at the intersection point z0 . = (φ)′−1(−τ) of the two pieces of the function,
  φ̄τ (z0) = −τ · (φ′)−1(−τ)− φ∗(−τ) = φ((φ′)−1(−τ)) = φ(z0).
  Proof of Lemma 3. For admissible φ, the Huberised loss φ̄τ of (8) is trivially convex, differentiable everywhere, and decreasing. In particular, we must have φ̄′τ (0) < 0, and so φ̄τ must be classification calibrated by Bartlett et al. (2006, Theorem 2). As an illustration, Figure 3 shows the minimiser of the conditional risk,
  z∗(η) . = argmin
  z∈R
  [ η · φ̃τ (z) + (1− η) · φ̃τ (−z) ] .
  Note that this quantity must be non-negative if and only if η > 1/2 for a loss to be classification calibrated. This is easily verified to be true for the Huberised logistic loss, regardless of τ .
  Now suppose that φ is a proper composite loss. To show that φ̄τ is proper composite, it suffices by Williamson et al. (2016, Corollary 12) to show that φ̄ ′ τ (z)
  φ̄′τ (−z) is strictly monotone and continuous.
  Continuity is immediate; for monotonicity, observe that by definition,
  φ̄′τ (z) = {−τ if z ≤ (φ′)−1(−τ) φ′(z) else.
  For brevity, let z0 . = (φ′)−1(−τ), where we take z0 = −∞ if −τ /∈ ran(φ′). Then,
  φ̄′τ (z) = { φ′(z0) if z ≤ z0 φ′(z) else.
  φ̄′τ (−z) = { φ′(z0) if z ≥ −z0 φ′(−z) else.
  Thus, the quantity of interest is
  φ̄′τ (z)
  φ̄′τ (−z) =  φ′(z0) φ′(−z) if z ≤ z0 φ′(z) φ′(−z) if z0 ≤ z ≤ −z0 1 if − z0 ≤ z ≤ z0 φ′(z) φ′(z0) if z ≥ −z0.
  Since φ is strictly convex, φ′ is strictly decreasing and thus invertible. Thus, the ratio φ̄ ′ τ (z) φ̄′τ (−z) is invertible, provided z0 ≤ 0, i.e., τ ≥ −φ′(0). Consequently, φ̄τ is proper composite when τ ≥ −φ′(0). To intuit the need for the restriction on τ , observe that by (Reid & Williamson, 2010, Corollary 12) the tentative link function for the loss is
  F̄ (z) . =
  1
  1− φ̄′(z) φ̄′(−z)
  =  φ′(−z) φ′(z0)+φ′(−z) if z ≤ z0 F (z) if z0 ≤ z ≤ −z0 1 2 if − z0 ≤ z ≤ z0
  φ′(z0) φ′(z0)+φ′(z)
  if z ≥ −z0.
  When τ < −φ′(0), the above is seen to be non-invertible. See also Appendix C for an illustration of this link function for the logistic loss.
  Proof of Proposition 4. In order to apply Long & Servedio (2010, Theorem 2), we simply need to check that the loss φ̄τ is a convex potential in the sense of Long & Servedio (2010, Definition 1). This requires that φ̄τ is convex, non-increasing, continuously differentiable, and asymptotes to zero (or equally, is bounded from below). Each of these is satisfied by assumption of φ being admissible.
  Proof of Lemma 5. By Lemma 2, we may write clipτ (ϕ′(u)) as the derivative of a partially Huberised base loss ϕ̃τ given by
  ϕ̃τ (u) . = {−τ · u− ϕ∗(−τ) if ϕ′(u) ≤ −τ ϕ(u) else
  This induces a composite margin loss φ̃τ . = ϕ̃τ ◦ F . Now let pθ(x, y) = F (mθ(x, y)), and define ˜̀ τ (x, y; θ) . = φ̃τ (mθ(x, y)). The gradient under this loss is
  ∇θ ˜̀τ (x, y; θ) = ∇θφ̃τ (mθ(x, y)) = ∇θϕ̃τ (pθ(x, y)) = ∇θpθ(x, y) · ϕ̃′τ (pθ(x, y)) = ∇θpθ(x, y) · clipτ (ϕ′(pθ(x, y))) = cl− clipτ (∇`θ(x, y)).
  Thus, CL-gradient clipping is equivalent to using the loss ˜̀τ .
  Proof of Lemma 6. We proceed in a similar manner to Lemma 3: to show that the loss is proper, we must establish that φ̃ ′ τ (z)
  φ̃′τ (−z) is invertible. By Reid & Williamson (2010, Corollary 14), for the margin
  loss φ to be proper composite with link F , it must be true that F satisfies the symmetry condition F (−z) = 1− F (z). We thus have
  φ̃′τ (z) = F ′(z) · ϕ̃′τ (F (z))
  φ̃′τ (−z) = F ′(−z) · ϕ̃′τ (F (−z)) = −F ′(z) · ϕ′(1− F (z)).
  Consequently,
  φ̃′τ (z)
  φ̃′τ (−z) = − ϕ̃
  ′ τ (F (z))
  ϕ̃′τ (1− F (z)) .
  Since F is invertible by assumption, the above is invertible if and only if ϕ̃ ′ τ (u)
  ϕ̃′τ (1−u) is invertible. Observe that
  ϕ̃′τ (u) = {−τ if u ≤ (ϕ′)−1(−τ) ϕ′(u) else.
  Let u0 . = (ϕ′)−1(−τ) for brevity. Then,
  ϕ̃′τ (u) ϕ̃′τ (1− u) =  − τϕ′(1−u) if u ≤ u0 ∧ (1− u0) ϕ′(u) ϕ′(1−u) if u0 ≤ u ≤ 1− u0 1 if 1− u0 ≤ u ≤ u0 −ϕ
  ′(u) τ if u ≥ u0 ∨ (1− u0)
  This quantity is invertible provided u0 ≤ 12 , i.e., τ ≥ −ϕ′(1/2). A subtlety, however, is that the above does not necessarily span the entire range of [0,+∞]; consequently, ϕ̃τ itself is proper composite, with a link function of its own.
  Even when τ is small, one may verify that the loss φ̃τ is nonetheless classification calibrated: this is because for any η ∈ [0, 1], the minimiser z∗(η) of the conditional risk
  must satisfy the stationarity condition
  − φ̃ ′ τ (z ∗)
  φ̃′τ (−z∗) =
  η
  1− η .
  We thus need to find a suitable z∗ such that the left hand side equates to a given constant. Now, for any C 6= 1 there is a unique u such that ϕ̃ ′ τ (u)
  ϕ̃′τ (1−u) = C. Thus, provided η 6= 1 2 , there is a unique
  z∗ = F−1(u∗) such that φ̃ ′ τ (F (z ∗))
  φ̃′τ (1−F (z∗)) = C. One may verify that this z∗ > 0 ⇐⇒ η > 12 ; for
  example, see Figure 4, which visualises the risk minimiser for various values of τ . Thus, the sign of the minimising score conveys whether or not the positive class-probability is dominant; thus, the loss is classification calibrated.
  Proof of Proposition 7. Let Rτ (f) denote the risk on the clean distribution of a predictor f with respect to the partially Huberised loss ϕ̃τ with parameter τ . Similarly, let R̄τ (f) denote the risk on the noisy distribution. Following Ghosh et al. (2015); van Rooyen et al. (2015), we have
  R̄τ (f) = (1− 2 · ρ) ·Rτ (f) + α · E x [ϕ̃τ (f(x)) + ϕ̃τ (1− f(x))] .
  That is, the risk on the noisy distribution equals a scaled version of the risk on the clean distribution, plus an additional term. This term is a constant independent of f if and only if ϕ̃τ satisfies the symmetry condition of Ghosh et al. (2015) , namely, ϕ̃τ (u) + ϕ̃τ (1− u) = C for some constant C. Even when the symmetry condition does not hold, one may nonetheless aim to bound this additional term as follows. For simplicity, we restrict attention here to ϕ being the log or cross-entropy loss ϕ(u) = − log u. By definition, for any f ∈ (0, 1),
  ϕ̃τ (f) + ϕ̃τ (1− f) =  −τ · f + log τ + 1− log(1− f) if p ≤ 1τ ∧ ( 1− 1τ ) −τ · f − τ · (1− f) + 2 · log τ + 2 if 1− 1τ ≤ p ≤ 1τ − log f − log(1− f) if 1τ ≤ p ≤ ( 1− 1τ
  ) − log f − τ · (1− f) + log τ + 1 if p ≥ 1τ ∨ ( 1− 1τ
  ) =
   −τ · f + log τ + 1− log(1− f) if p ≤ 1τ ∧ ( 1− 1τ ) −τ + 2 · log τ + 2 if 1− 1τ ≤ p ≤ 1τ − log f − log(1− f) if 1τ ≤ p ≤ ( 1− 1τ
  ) − log f − τ · (1− f) + log τ + 1 if p ≥ 1τ ∨ ( 1− 1τ ) .
  Evidently, all piecewise functions involved are bounded on the respective intervals. For example,
  ϕ̃τ (f) + ϕ̃τ (1− f) ≤  log τ + 1− log [ 1 τ ∨ ( 1− 1τ )] if p ≤ 1τ ∧ ( 1− 1τ ) −τ + 2 · log τ + 2 if 1− 1τ ≤ p ≤ 1τ −2 · log 1τ if 1τ ≤ p ≤ ( 1− 1τ ) − log [ 1 τ ∨ ( 1− 1τ )] + log τ + 1 if p ≥ 1τ ∨ ( 1− 1τ ) .
  By taking the maximum of each of the quantities on the right hand side – which are constants depending on τ – we may thus find constants C1, C2 such that
  R̄τ (f) ≤ (1− 2 · ρ) ·Rτ (f) + C1 R̄τ (f) ≥ (1− 2 · ρ) ·Rτ (f) + C2.
  Now let f∗ denote the minimiser of the clean risk Rτ (f), and f̄∗ the minimiser of the noisy risk R̄τ (f). Then, using each of the above inequalities,
  R̄τ (f ∗)− R̄τ (f̄∗) ≤ (1− 2 · ρ) · (Rτ (f∗)−Rτ (f̄∗)) + C1 − C2 ≤ (C1 − C2),
  where the last inequality is because Rτ (f∗) ≤ Rτ (f̄∗) by definition of f∗. The claim follows.
sections.heading: B PROPER AND PROPER COMPOSITE LOSSES
sections.text: Beyond requiring classification-calibration, it is often desirable to use classifier outputs as valid probabilities. Proper losses (Savage, 1971; Schervish, 1989; Buja et al., 2005) ϕ : {±1}×[0, 1]→ R̄+ are the core losses of such class-probability estimation tasks, for which
  (∀p ∈ [0, 1]) argmin u∈[0,1] E y∼Bern(p) [ϕ(y, u)] = p. (13)
  Equation 13 stipulates that when using ϕ to distinguish positive and negative labels, it is optimal to predict the positive class-probability.
  Typically, it is more useful to work with losses that accept real-valued scores, e.g. as output by the pre-activation of the final layer of a neural network. To this end, proper composite losses (Reid & Williamson, 2010; Nock & Nielsen, 2009) are those ` : {±1}×R→ R+ are such that `◦F−1 is proper, for invertible link function F : R̄ → [0, 1]. Proper composite losses are inherently classificationcalibrated (Reid & Williamson, 2010, Theorem 16). Canonical examples are the logistic loss `(y, v) = log(1 + e−yv) with F : v 7→ σ(v), and exponential loss `(y, v) = e−yv with F : v 7→ σ(2 · v). When ` is differentiable, we have (Reid & Williamson, 2010, Corollary 12)
  (∀v ∈ R)F (v) = (
  1− ` ′(+1, v) `′(−1, v)
  )−1 . (14)
  Given a proper loss ϕ and “symmetric” link F with F (−v) = 1−F (v), the loss `(y, v) = ϕ(y, F (v)) defines a margin loss (Reid & Williamson, 2010, Corollary 14).
  Proper composite losses may also be extended to multiclass settings in the natural way (Gneiting & Raftery, 2007; Williamson et al., 2016): one now defines a proper loss ϕ : [K]×∆K → R+, where K is the number of classes and ∆K denotes the K-simplex. A proper composite loss may be defined using a link F : RK → ∆K , such as the softmax operator Fk(v) = exp(vk)∑
  k′ exp(vk′ ) . Combined with
  the log-loss ϕ(y, p) = − log py , this yields the standard softmax cross-entropy loss.
  C ILLUSTRATION OF LOSSES
  We illustrate the Huberised, partially Huberised, and generalised cross-entropy losses as their underlying tuning parameters are varied. Additionally, we illustrate the link functions that are implicit in each of the losses, which illustrates that they may be non-invertible if τ is too large.
  C.1 HUBERISED LOSS
  Figure 5 illustrates the Huberised version of the logistic loss, and its derivative. Following the proof of Lemma 3, for τ ∈ (0, 1) and z0 = −σ−1(τ), the Huberised loss φ̄τ has an implicit link function (see Figure 6)
  (∀z ∈ R) F̄τ (z) =  σ(z) σ(z0)+σ(z) if z ≤ z0 σ(z) if z0 ≤ z ≤ −z0 1 2 if − z0 ≤ z ≤ z0
  σ(z0) σ(z0)+σ(z) if z ≥ −z0. Compared to the standard sigmoid, the Huberised link saturates more slowly as τ is decreased. Note that when τ ≤ 12 , the link function is not invertible everywhere: this results in the loss not being proper composite per our definition.
  C.2 PARTIALLY HUBERISED LOSS
  Figure 7 illustrates the partially Huberised version of the logistic loss, as well as the base log-loss. Following the proof of Lemma 6, the partially Huberised loss φ̃τ has implicit link function
  F̃τ (v) =  1 1+τ ·σ(−v) if σ(v) ≤ 1τ ∧ ( 1− 1τ ) σ(v) if 1τ ≤ σ(v) ≤ ( 1− 1τ ) 1 2 if ( 1− 1τ ) ≤ σ(v) ≤ 1τ
  τ ·σ(v) 1+τ ·σ(v) if σ(v) ≥ ( 1− 1τ ) ∨ 1τ .
  Figure 9 illustrates the link function. The logistic loss has ϕ(u) = − log u, and so ϕ′(1/2) = −2. For τ = 1, the link function will be non-invertible everywhere, which is expected since the loss here is the linear loss, which is not suitable for class-probability estimation. For τ ∈ (1, 2), the link function will be invertible for p /∈ [( 1− 1τ ) , 1τ ] . Intuitively, the case τ ∈ (1, 2) corresponds to the linear regions of the losses on positive and negative instances crossing over. For τ ≥ 2, the link function will always be invertible.
  It may be observed that partial Huberisation causes the link function to saturate at values [1/(1 + τ), τ/(1+τ)]: this does not affect classification calibration, but does imply that rescaling is necessary in order to intepret the output probabilities.
  C.3 ILLUSTRATION OF GENERALISED CROSS-ENTROPY
  Figure 8 illustrates the base ϕα loss, and its composition with a sigmoid link function.
sections.heading: D ROBUSTNESS TO INSTANCE OUTLIERS
sections.text: Following Ding (2013, Section 3.2.2), we consider robustness to an arbitrary corruption under a linear scoring model. For margin loss `(x, y; θ) .= φ(y · θTx) with empirical risk minimiser θ̂N on a sample {(xn, yn)}Nn=1, suppose that the sample is corrupted with an outlier (x′, y′). One would like to ensure that θ̂N is not swayed by making ‖x′‖2 arbitrarily large: that is,
  lim ‖x′‖2→+∞
  1
  N + 1 N∑ n=1 ∇`(xn, yn; θ̂N ) +∇`(x′, y′; θ̂N ) = 0,
  or equivalently, lim‖x′‖2→+∞∇`(x′, y′; θ̂N ) = 0. Fortunately, the saturating behaviour of the partially Huberised loss affords this, as we now show. Proposition 8. Pick any convex, differentiable, proper composite margin loss φ, whose link F satisfies limz→−∞ z · F ′(z) = 0. For any τ > 0, let ˜̀τ (x, y; θ) .= φ̃τ (y · θTx) be the τ -partially Huberised loss under a linear model. Then, for any (x, y) and θ such that ‖θ‖2 < +∞ and θTx 6= 0,
  lim ‖x‖2→+∞
  ‖∇˜̀τ (x, y; θ)‖2 = 0.
  Proof of Proposition 8. By definition,
  ∇˜̀τ (x, y; θ) = y · x · φ′(y · θTx). Thus,
  ‖∇˜̀τ (x, y; θ)‖2 = ‖x‖2 · |φ′(y · θTx)|
  = (y · θTx) · |φ′(y · θTx)| · 1 y · ‖θ‖2 · cosψx,θ ,
  where ψx,θ denotes the angle between x and θ. If θTx 6= 0, then cosψx,θ 6= 0, and so the third term is finite. Thus, ‖∇˜̀τ (x, y; θ)‖2 → limz→±∞ |z| · φ̃′τ (z), depending on the sign of y ·θTx. By definition of φ̃τ , the derivative of the loss asymptotes to either F ′(v), or φ′(v). Now, limz→−∞ z · F ′(v) = 0 by assumption, and limz→+∞ z · φ′(v) = 0 since φ is convex, the claim is shown.
sections.heading: E ADDITIONAL SYNTHETIC EXPERIMENTS
sections.text: We provide some more details regarding the synthetic data used in the body.
  E.1 DETAILS OF LONG & SERVEDIO (2010) DATASET
  The problem considered in Long & Servedio (2010) (see Figure 10) comprises a distribution concentrated on six atoms {±(1, 0),±(γ, 5γ),±(γ,−γ)} ⊂ R2 for some γ > 0; we chose γ = 124 . An instance (x1, x2) is labelled as y = Jx1 ≥ 0K. The instances are weighted so that the first four atoms have probability mass 18 , and the last two atoms mass 1 4 . We modify this distribution slightly by treating the atoms as means of isotropic Gaussians, and treating the marginal distribution over instances to be a mixture of these Gaussians with mixing weights given by the corresponding probability masses of the atoms.
  E.2 DETAILS OF OUTLIER DATASET
  For the experiment involving outliers in feature space, the data comprises points on the line. Positively labelled samples are drawn from a unit variance Gaussian centered at (1, 1), with positively labeled outliers drawn from (−200, 1). Negatively labelled samples comprise the negation of all points. We learn an unregularised linear classifier from this data, which corresponds to a single scalar θ.