Making SVMs Robust to Uncertainty in Kernel Matrices

Опубликовано 12 августа 2016, 2:11

Motivated from several real world problems we consider the problem of designing SVM classifiers which are robust to uncertainty in the Kernel matrices. In general the problem is NP hard for arbitrary uncertainty. However we show that in certain cases one can derive tractable formulations which yield robust classifiers. Following robust optimization based methodology we model the uncertainty as an affine set. Though this leads to a SOCP formulation, we demonstrate that the optimization problem can be reformulated as a saddle point problem which can be solved by an algorithm which has $O(1/T^2)$ convergence. Here $T$ is the number of iterations and the complexity of each iteration is same as solving an SVM. Experimental results on real world protein structure datasets demonstrate the utility of the proposed formulation.