More Like this

1. Weston-Watkins Hinge Loss and Ordered Partitions

   Wang, Yutong ; Scott, Clayton ( January 2020 , Advances in neural information processing systems)

   null (Ed.)

   Multiclass extensions of the support vector machine (SVM) have been formulated in a variety of ways.A recent empirical comparison of nine such formulations [1]recommends the variant proposed by Westonand Watkins (WW), despite the fact that the WW-hinge loss is not calibrated with respect to the 0-1 loss.In this work we introduce a novel discrete loss function for multiclass classification, theordered partitionloss, and prove that the WW-hinge lossiscalibrated with respect to this loss. We also argue that theordered partition loss is maximally informative among discrete losses satisfying this property. Finally,we apply our theory to justify the empirical observation made by Doˇgan et al. [1] that the WW-SVMcan work well even under massive label noise, a challenging setting for multiclass SVMs. 

   more » « less
2. An Exact Solver for the Weston-Watkins SVM Subproblem

   Wang, Yutong ; Scott, Clayton ( January 2021 , International Conference on Machine Learning, PMLR)

   null (Ed.)

   Recent empirical evidence suggests that the Weston-Watkins support vector machine is among the best performing multiclass extensions of the binary SVM. Current state-of-the-art solvers repeatedly solve a particular subproblem approximately using an iterative strategy. In this work, we propose an algorithm that solves the subproblem exactly using a novel reparametrization of the Weston-Watkins dual problem. For linear WW-SVMs, our solver shows significant speed-up over the state-of-the-art solver when the number of classes is large. Our exact subproblem solver also allows us to prove linear convergence of the overall solver. 

   more » « less
3. An Exact Solver for the Weston-Watkins SVM Subproblem

   Wang, Yutong ; Scott, Clayton ( January 2021 , Proceedings of the 38th International Conference on Machine Learning)

   Recent empirical evidence suggests that the Weston-Watkins support vector machine is among the best performing multiclass extensions of the binary SVM. Current state-of-the-art solvers repeatedly solve a particular subproblem approximately using an iterative strategy. In this work, we propose an algorithm that solves the subproblem exactly using a novel reparametrization of the Weston-Watkins dual problem. For linear WW-SVMs, our solver shows significant speed-up over the state-of-the-art solver when the number of classes is large. Our exact subproblem solver also allows us to prove linear convergence of the overall solver. 

   more » « less
4. Calibrated Surrogate Losses for Adversarially Robust Classification

   Bao, Han ; Scott, Clayton ; Sugiyama, Masashi ( January 2020 , Conference on Learning Theory, 2020)

   null (Ed.)

   Adversarially robust classification seeks a classifier that is insensitive to adversarial perturbations of test patterns. This problem is often formulated via a minimax objective, where the target loss is the worst-case value of the 0-1 loss subject to a bound on the size of perturbation. Recent work has proposed convex surrogates for the adversarial 0-1 loss, in an effort to make optimization more tractable. In this work, we consider the question of which surrogate losses are calibrated with respect to the adversarial 0-1 loss, meaning that minimization of the former implies minimization of the latter. We show that no convex surrogate loss is calibrated with respect to the adversarial 0-1 loss when restricted to the class of linear models. We further introduce a class of nonconvex losses and offer necessary and sufficient conditions for losses in this class to be calibrated. Keywords: surrogate loss, classification calibration, adversarial robustness 

   more » « less
5. Top-label calibration and multiclass-to-binary reductions

   Gupta, Chirag ; Ramdas, Aaditya ( April 2022 , International Conference on Learning Representations)

   A multiclass classifier is said to be top-label calibrated if the reported probability for the predicted class -- the top-label -- is calibrated, conditioned on the top-label. This conditioning on the top-label is absent in the closely related and popular notion of confidence calibration, which we argue makes confidence calibration difficult to interpret for decision-making. We propose top-label calibration as a rectification of confidence calibration. Further, we outline a multiclass-to-binary (M2B) reduction framework that unifies confidence, top-label, and class-wise calibration, among others. As its name suggests, M2B works by reducing multiclass calibration to numerous binary calibration problems, each of which can be solved using simple binary calibration routines. We instantiate the M2B framework with the well-studied histogram binning (HB) binary calibrator, and prove that the overall procedure is multiclass calibrated without making any assumptions on the underlying data distribution. In an empirical evaluation with four deep net architectures on CIFAR-10 and CIFAR-100, we find that the M2B + HB procedure achieves lower top-label and class-wise calibration error than other approaches such as temperature scaling. 

   more » « less