Generalization in Supervised Learning Through Riemannian Contraction
This provides a theoretical foundation for generalization in supervised learning, applicable broadly but incremental as it extends known results to more general cases.
The paper proves that Riemannian contraction in supervised learning implies generalization, showing that an optimizer contracting with rate λ yields uniform algorithmic stability with rate O(1/λn), where n is the number of training examples, applicable across various optimization settings.
We prove that Riemannian contraction in a supervised learning setting implies generalization. Specifically, we show that if an optimizer is contracting in some Riemannian metric with rate $λ> 0$, it is uniformly algorithmically stable with rate $\mathcal{O}(1/λn)$, where $n$ is the number of labelled examples in the training set. The results hold for stochastic and deterministic optimization, in both continuous and discrete-time, for convex and non-convex loss surfaces. The associated generalization bounds reduce to well-known results in the particular case of gradient descent over convex or strongly convex loss surfaces. They can be shown to be optimal in certain linear settings, such as kernel ridge regression under gradient flow.