Generalization bound for kernel similarity learning
This work addresses generalization guarantees for similarity learning, which is important for scientific and industrial applications, but it appears incremental as it extends existing complexity analysis to this specific framework.
The paper tackles the problem of generalization in kernel similarity learning by formulating it as a regression task and providing Rademacher complexity bounds on the generalization error, showing that the complexity is bounded by the maximum radius of the feature and output spaces with high probability.
Similarity learning has received a large amount of interest and is an important tool for many scientific and industrial applications. In this framework, we wish to infer the distance (similarity) between points with respect to an arbitrary distance function $d$. Here, we formulate the problem as a regression from a feature space $\mathcal{X}$ to an arbitrary vector space $\mathcal{Y}$, where the Euclidean distance is proportional to $d$. We then give Rademacher complexity bounds on the generalization error. We find that with high probability, the complexity is bounded by the maximum of the radius of $\mathcal{X}$ and the radius of $\mathcal{Y}$.