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

arXiv: https://arxiv.org/abs/1902.03755 · HTML: https://mlsanity.com/paper/1902.03755/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2019.

## Built on by (most cited first, 3 of 3)

- [Active Labeling: Streaming Stochastic Gradients](https://mlsanity.com/paper/2205.13255/) (2022)
- [An Exact Solver for the Weston-Watkins SVM Subproblem](https://mlsanity.com/paper/2102.05640/) (2021)
- [From Weakly Supervised Learning to Active Learning](https://mlsanity.com/paper/2209.11629/) (2022)

## Abstract (arXiv)

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