Bi-level stochastic gradient for large scale support vector machine

We propose a new bi-level stochastic optimization algorithm for training large scale support vector machine (SVM) with automatic selection of the C hyperparameter. We show that in the proposed bi-level formulation, the variation of the inner objective with respect to the outer variable can be nicely expressed. Gradient estimates are computed for both inner and outer objectives in order to perform stochastic moves with low complexity. Extension to nonlinear SVM is also proposed. We further discuss the possibility to integrate the technique within an automatic k-fold cross validation framework. Preliminary results on several datasets show that the method is finding the optimum hyperplane while adjusting the penalty parameter with significant computational time savings when compared to the classic cross validation procedure.