Adversarial Multiclass Classification: A Risk Minimization Perspective
Recently proposed adversarial classification methods have shown promising results for cost sensitive and multivariate losses. In contrast with empirical risk minimization (ERM) methods, which use convex surrogate losses to approximate the desired non-convex target loss function, adversarial methods minimize non-convex losses by treating the properties of the training data as being uncertain and worst case within a minimax game. Despite this difference in formulation, we recast adversarial classification under zero-one loss as an ERM method with a novel prescribed loss function. We demonstrate a number of theoretical and practical advantages over the very closely related hinge loss ERM methods. This establishes adversarial classification under the zero-one loss as a method that fills the long standing gap in multiclass hinge loss classification, simultaneously guaranteeing Fisher consistency and universal consistency, while also providing dual parameter sparsity and high accuracy predictions in practice.
This is a very interesting and well-written paper that closes the gap between theory and practice by providing a Fisher- and universally consistent loss function for multiclass classification that performs empirically well in practice. The authors show how adversarial loss minimization in the multiclass setting can be recast into an empirical risk minimization setup under the adversarial 0-1 loss function. They further prove that the adversarial 0-1 loss is both Fisher and universally consistent (so that it has advantageous theoretical properties) and demonstrate a novel algorithm that for efficient optimization that uses a constraint generation QP method (allowing the method to be computationally efficient).  The experiments are detailed and thorough, testing on 12 UCI datasets and comparing the adversarial 0-1 loss to three other multiclass SVM methods. 
The main theorems of the paper are technically rich, and support the conclusion of the paper. The proofs are extremely well documented in the supplementary material, and easy to follow proof sketches are given in the main body of the work.   The experimental work compares the proposed method to three other competing state of the art multiclass SVM solvers across 12 datasets. The statistical significance of the experimental results are considered; 20 dataset splits are created and a paired t-test is performed. Additionally, the results are convincing in that they agree with previous work, as explained in lines 233-234.  However, I am curious as to why the authors did not compare against OVA multiclass classification since it has been extremely popular for its computational efficiency and shown to perform as well statistically as other methods (see Rifkin “In defense of One vs. All.”)  One main weakness of the experimental results is that they claim that the new algorithm is computationally efficient and provide a proof of convergence, but do not include any performance vs. time results that back up these claims.   Novelty/Originality  The work is highly novel in that it proposes a new loss function and a new, efficient algorithm to solve the associated optimization problem.   Potential impact or usefulness  The impact of the work is high since it combines work done from two somewhat distinct areas (adversarial classification and consistency of empirical risk minimization methods). In addition, the SVM algorithm for multiclass is highly popular, so I expect this result to affect a large number of people.   Clarity and presentation  Overall, the paper is well written. The intro very clearly lays out the gaps in existing approaches, and explains how the AL-01 approach bridges these gaps. The background gives a clear introduction to the main ideas needed to understand the theoretical results of the paper. The explanations in the experimental section make the findings easy to understand.  Some specific comments…  Figure 1 and Figure 2. These are difficult to understand, but I feel could be potentially very elucidating. Spend a little more time in text going over how to interpret these figures?  Table 2 #b - not clear what this means immediately. Should explain in Figure caption.