SDM SVM L1 and SDM SVM L2
S. S. Keerthi and O. Chapelle
Yahoo! Research

SDM stands for Sequential Dual Method, which is a dual method for solving SVMs whose basic
iteration is to select a subset of examples, order them randomly and update the dual variable
of one example at a time. There are two types of iterations: full and shrunk. In a full iteration
all examples are chosen for update. In a shrunk iteration only examples whose dual variable is
away from boundary (0 and C in L1 and only 0 in L2) are chosen for update. The method is essentially
the same as what is in [1] (as well the liblinear code in [2]), but the shrunk iterations are
slightly different from those.

The method is stopped when one of the following occurs: (1) dual optimality violation is within 0.1;
(2) the total number of individual example updates is more than 20 times the number of training
examples.

When training with different data set sizes, C is taken to be a function of n, the number of training 
examples as follows: C = C_const * sqrt(N/n), where N is the size of the full training set.

For each dataset the value of C_const is tuned using 100,000 training examples and optimizing PRC on the
remaining labeled examples.

[1] C.-J. Hsieh, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundararajan. A dual coordinate descent 
method for large-scale linear SVM. ICML 2008. 

[2] LIBLINEAR code with "-s 3" option. http://www.csie.ntu.edu.tw/~cjlin/liblinear/