A hybrid optimization method for acceleration of building linear classification models

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.