stat.ML

(what is this?)

# Title:Efficient Primal-Dual Algorithms for Large-Scale Multiclass Classification

Authors:Dmitry Babichev (SIERRA, Inria, PSL), Dmitrii Ostrovskii (SIERRA, Inria, PSL), Francis Bach (SIERRA, Inria, PSL)
Abstract: 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.
 Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC) Cite as: arXiv:1902.03755 [stat.ML] (or arXiv:1902.03755v1 [stat.ML] for this version)

## Submission history

From: Dmitrii Ostrovskii [view email]
[v1] Mon, 11 Feb 2019 07:39:24 UTC (131 KB)