Near-Orthogonality Regularization in Kernel Methods

Kernel methods perform nonlinear learning in high-dimensional reproducing kernel Hilbert spaces (RKHSs). Even though their large model-capacity leads to high representational power, it also incurs substantial risk of over- fitting. To alleviate this problem, we pro- pose a new regularization approach, near- orthogonality regularization, which encour- ages the RKHS functions to be close to be- ing orthogonal. This effectively imposes a structural constraint over the function space, which reduces model complexity and can im- prove generalization performance. Besides, encouraging orthogonality reduces the redun- dancy among functions, which hence can re- duce model size without compromising mod- eling power and better capture infrequent pat- terns in the data. Here, we define a family of orthogonality-promoting regularizers by en- couraging the Gram matrix of the RKHS func- tions to be close to an identity matrix where the closeness is measured by Bregman ma- trix divergences. We apply these regularizers to two kernel methods, and develop an effi- cient ADMM-based algorithm to solve the reg- ularized optimization problems. We analyze how near-orthogonality affects the generaliza- tion performance of kernel methods. Our re- sults suggest that the closer the functions are to being orthogonal, the smaller the general- ization error is. Experiments demonstrate the efficacy of near-orthogonality regularization in kernel methods.