Selective Block Minimization for Faster Convergence of Limited Memory Large-scale Linear Models

Kai-Wei Chang and Dan Roth, in KDD, 2011.

Slides Poster Code

Download the full text

Abstract

As the size of data sets used to build classifiers steadily increases, training a linear model efficiently with limited memory becomes essential. Several techniques deal with this problem by loading blocks of data from disk one at a time, but usually take a considerable number of iterations to converge to a reasonable model. Even the best block minimization techniques [1] require many block loads since they treat all training examples uniformly. As disk I/O is expensive, reducing the amount of disk access can dramatically decrease the training time.

Bib Entry

@inproceedings{ChangRo11,
  author = {Chang, Kai-Wei and Roth, Dan},
  title = {Selective Block Minimization for Faster Convergence of Limited Memory Large-scale Linear Models},
  booktitle = {KDD},
  year = {2011}
}

Related Publications

Large Linear Classification When Data Cannot Fit In Memory, TKDD, 2012
Iterative Scaling and Coordinate Descent Methods for Maximum Entropy Models, JMLR, 2010
A Comparison of Optimization Methods and software for Large-scale L1-regularized Linear Classification, JMLR, 2010
Training and Testing Low-degree Polynomial Data Mappings via Linear SVM, JMLR, 2010
A Sequential Dual Method for Large Scale Multi-Class Linear SVMs, KDD, 2008
A Dual Coordinate Descent Method for Large-Scale Linear SVM, ICML, 2008
Coordinate Descent Method for Large-scale L2-loss Linear SVM, JMLR, 2008
LIBLINEAR: A Library for Large Linear Classification, JMLR, 2008