Robust Kernelized Method

It is natural to assume that uncertainty in the dataset will lead to uncertainty in the kernel matrices. We study the problem of designing robust classifiers when there is uncertainty in kernel matrix K. The methods discussed in ( Bhattacharyya et al., 2004 ; Shivaswamy et al., 2006) do not readily apply to the case of arbitrary kernel functions and merits further study. The problem studied here is motivated from the problem of classifying protein structures where kernel methods have been highly successful.

In (Bhadra et al., 2010) we studied problem of robust kernelized classification where the uncertainty is characterized by independent additive noise in each of the entries of the kernel matrix. A novel distribution free large deviation inequality has been proposed which handles uncertainty in kernels through co-positive programming in a chance constraint setting. Although such formulations are NP hard, under several cases of interest the problem reduces to a convex program.

However, the independence assumption mentioned above, is restrictive and may not always define a valid uncertain kernel. To alleviate this problem, in (Ben-Tal et al, 2012) the uncertainty in the kernel matrix is modelled by a convex and bounded uncertain set which encompasses possible realizations of K. The realizations are modelled by an affine combination of a finite set of fixed kernels. This new approach leads to an optimization problem which could be cast as a saddle point(minimax) problem. Due to favourable conditions satisfied by the problem, we are able to use a novel algorithm which uses only first order information, yet proved to decrease the initial error by a factor of O(1/T2), after T iterations. For more details please see Bhadra's Thesis and referecnes there in.