A hybrid optimization method for acceleration of building linear classification models
Junchao Lv, Qiang Wang, Joshua Zhexue Huang · 2013
Linear classification is an important technique in machine learning and data mining, and development of fast optimization methods for training linear classification models is a hot research topic. Stochastic gradient descent (SGD) can achieve relatively good results quickly, but unstable to converge. Limited-memory BFGS (L-BFGS) method converges, but takes a long time to train the model, as it needs to compute the gradient from the entire data set to make an update. In this paper, we investigate a hybrid method that integrates SGD and L-BFGS into a new optimization process SGD-LBFGS to take advantages of both optimization methods. In SGD-LBFGS, SGD is used to run initial iterations to obtain a suboptimal result, and then L-BFGS takes over to continue the optimization process until the process converges and a better model is built. We present a theoretical result to prove that SGD-LBFGS converges faster than SGD and L-BFGS. Experiment analysis on 6 real world data sets have shown that SGD-LBFGS converged 77% faster than L-BFGS on average and demonstrated more stable results than SGD.