Multi-Class Learning: From Theory to Algorithm
In this paper, we study the generalization performance of multi-class classification and obtain a shaper data-dependent generalization error bound with fast convergence rate, substantially improving the state-of-art bounds in the existing data-dependent generalization analysis. The theoretical analysis motivates us to devise two effective multi-class kernel learning algorithms with statistical guarantees. Experimental results show that our proposed methods can significantly outperform the existing multi-class classification methods.
After author response: thank you for your detailed comparison.  ======  Proving generalization bounds is one of the most important tasks in theoretical machine learning. The current paper is focusing on multi-class classification where the output cardinality K is larger than 2. The investigation of multi-class classification has a long history (e.g., [1, 7, 12, 14]).  The paper claims to highly improve the generalization bound using the known technique of "local rademacher complexity" ([3]). This technique focuses on a smaller class that contains only hypotheses with small variance. The paper claims to improve the generalization bound from K/sqrt{n} to logK^(O(1))/n (where n is the sample size), which seems like an impressive improvement. Of course, this is under the assumption that the "true" hypothesis is with low variance.  It is unclear to me why the authors have decided not to reference and compare to the paper "Xu, Chang, et al. "Local rademacher complexity for multi-label learning." IEEE Transactions on Image Processing 25.3 (2016): 1495-1507" which has a similar goal: "We analyze the local Rademacher complexity of empirical risk minimization (ERM)-based multi-label learning algorithms, and in doing so propose a new algorithm for multi-label learning."