Theoretical analysis of a class of randomized regularization methods

The convergence behavior of traditional learning algorithms can be analyzed in the VC theoretical framework. Recently, many researchers have been interested in a class of randomized learning algorithms including the Gibbs algorithm from statistical mechanics. However, no successful theory concerning the generalization behavior of these randomized learning algorithms have been established previously. In order to fully understand the behavior of these randomized estimators, we shall compare them with regularization schemes for deterministic estimators. Furthermore, we present theoretical analysis for such algorithms which leads to rigorous convergence bounds.