Kernelization of matrix updates, when and how?

We define what it means for a learning algorithm to be kernelizable in the case when the instances are vectors, asymmetric matrices and symmetric matrices, respectively. We can characterize kernelizability in terms of an invariance of the algorithm to certain orthogonal transformations. If we assume that the algorithm's action relies on a linear prediction, then we can show that in each case, the linear parameter vector must be a certain linear combination of the instances. We give a number of examples of how to apply our methods. In particular we show how to kernelize multiplicative updates for symmetric instance matrices.

Authors

• Manfred K. Warmuth
• Wojciech Kotłowski
• Shuisheng Zhou

Keywords

• Kernelization
• Multiplicative updates
• Rotational invariance
• Exponentiated Gradient algorithm
• Gradient Descent algorithm