Nesterov Acceleration for the SMO Algorithm

摘要

We revise Nesterov's Accelerated Gradient (NAG) procedure for the SVM dual problem and propose a strictly monotone version of NAG that is capable of accelerating the second order version of the SMO algorithm. The higher computational cost of the resulting Nesterov Accelerated SMO (NA-SMO) is twice as high as that of SMO so the reduction in the number of iterations is not likely to translate in time savings for most problems. However, understanding NAG is presently an area of strong research and some of the resulting ideas may offer venues for even faster versions of NA-SMO.