Efficient Primal-Dual Algorithms for Large-Scale Multiclass Classification

2019/02/11 by Babichev, Dmitry, Ostrovskii, Dmitrii, Bach, Francis
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1902.03755

Abstract

We develop efficient algorithms to train ℓ₁-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 sublinear algorithm with iterations performed in O(d+n+k) arithmetic operations.

Related

• Multi-class classification: mirror descent approach
• Coresets for Classification -- Simplified and Strengthened
• Robust supervised classification and feature selection using a primal-dual method
• Robust Methods for High-Dimensional Linear Learning
• Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to\n Novel Algorithms