DS-MLR: Exploiting Double Separability for Scaling up Distributed Multinomial Logistic Regression

Scaling multinomial logistic regression to datasets with very large number of\ndata points and classes is challenging. This is primarily because one needs to\ncompute the log-partition function on every data point. This makes distributing\nthe computation hard. In this paper, we present a distributed stochastic\ngradient descent based optimization method (DS-MLR) for scaling up multinomial\nlogistic regression problems to massive scale datasets without hitting any\nstorage constraints on the data and model parameters. Our algorithm exploits\ndouble-separability, an attractive property that allows us to achieve both data\nas well as model parallelism simultaneously. In addition, we introduce a\nnon-blocking and asynchronous variant of our algorithm that avoids\nbulk-synchronization. We demonstrate the versatility of DS-MLR to various\nscenarios in data and model parallelism, through an extensive empirical study\nusing several real-world datasets. In particular, we demonstrate the\nscalability of DS-MLR by solving an extreme multi-class classification problem\non the Reddit dataset (159 GB data, 358 GB parameters) where, to the best of\nour knowledge, no other existing methods apply.\n