  One of the most efficient methods to solve L2-regularized primal problems,
such as logistic regression and linear support vector machine (SVM)
classification, is the widely used trust region Newton algorithm, TRON. While
TRON has recently been shown to enjoy substantial speedups on shared-memory
multi-core systems, exploiting graphical processing units (GPUs) to speed up
the method is significantly more difficult, owing to the highly complex and
heavily sequential nature of the algorithm. In this work, we show that using
judicious GPU-optimization principles, TRON training time for different losses
and feature representations may be drastically reduced. For sparse feature
sets, we show that using GPUs to train logistic regression classifiers in
LIBLINEAR is up to an order-of-magnitude faster than solely using
multithreading. For dense feature sets--which impose far more stringent memory
constraints--we show that GPUs substantially reduce the lengthy SVM learning
times required for state-of-the-art proteomics analysis, leading to dramatic
improvements over recently proposed speedups. Furthermore, we show how GPU
speedups may be mixed with multithreading to enable such speedups when the
dataset is too large for GPU memory requirements; on a massive dense proteomics
dataset of nearly a quarter-billion data instances, these mixed-architecture
speedups reduce SVM analysis time from over half a week to less than a single
day while using limited GPU memory.
