Efficient Primal-Dual Algorithms for Large-Scale Multiclass Classification
This addresses the computational bottleneck in multiclass classification for applications with high-dimensional data, though it is incremental as it builds on existing optimization techniques.
The paper tackles the problem of training ℓ1-regularized linear classifiers for large-scale multiclass classification by developing efficient primal-dual algorithms, achieving a sublinear algorithm with iterations in O(d+n+k) operations for the multiclass hinge loss.
We develop efficient algorithms to train $\ell_1$-regularized linear classifiers with large dimensionality $d$ of the feature space, number of classes $k$, and sample size $n$. Our focus is on a special class of losses that includes, in particular, the multiclass hinge and logistic losses. Our approach combines several ideas: (i) passing to the equivalent saddle-point problem with a quasi-bilinear objective; (ii) applying stochastic mirror descent with a proper choice of geometry which guarantees a favorable accuracy bound; (iii) devising non-uniform sampling schemes to approximate the matrix products. In particular, for the multiclass hinge loss we propose a \textit{sublinear} algorithm with iterations performed in $O(d+n+k)$ arithmetic operations.