Optimizing Top-$k$Multiclass SVM via Semismooth Newton Algorithm.

Top- $k$ performance has recently received increasing attention in large data categories. Advances, like a top- $k$ multiclass support vector machine (SVM), have consistently improved the top- $k$ accuracy. However, the key ingredient in the state-of-the-art optimization scheme based upon stochastic dual coordinate ascent relies on the sorting method, which yields $O(d\log d)$ complexity. In this paper, we leverage the semismoothness of the problem and propose an optimized top- $k$ multiclass SVM algorithm, which employs semismooth Newton algorithm for the key building block to improve the training speed. Our method enjoys a local superlinear convergence rate in theory. In practice, experimental results confirm the validity. Our algorithm is four times faster than the existing method in large synthetic problems; Moreover, on real-world data sets it also shows significant improvement in training time. [ABSTRACT FROM AUTHOR]