The Rademacher Complexity of Co-Regularized Kernel Classes

David S. Rosenberg, Peter L. BartlettAISTATS 2007

Abstract

Co-regularization is a prominent technique in semi-supervised multi-view learning that forces models trained on distinct feature sets to agree on unlabeled data. While intuitively appealing, the theoretical impact of this constraint on model complexity has remained largely unquantified. This paper provides a rigorous derivation of the Rademacher complexity for co-regularized kernel classes, specifically focusing on Co-Regularized Least Squares (CoRLS). We prove that the agreement constraint effectively prunes the hypothesis space, and we demonstrate a strong empirical correlation ($r = 0.67$) between this theoretical complexity reduction and actual improvements in predictive performance across 29 benchmark datasets.

Introduction

In many real-world machine learning scenarios, labeled data is expensive to obtain, while unlabeled data is abundant. Multi-view learning exploits this by using multiple independent sets of features (views) for the same data points. Co-regularization is a common strategy in this domain, encouraging predictors from different views to produce similar outputs. However, a precise measure of how much this agreement constraint reduces the "complexity" of the hypothesis space—a key factor in generalization—was previously missing.

Methods

The authors analyze Co-Regularized Least Squares (CoRLS), defining a hypothesis class $\mathcal{J}_\lambda$ that averages predictors from two Reproducing Kernel Hilbert Spaces (RKHS) subject to a disagreement penalty. Using the Representer Theorem and the "Span of the Data," they derive a closed-form expression for the empirical Rademacher complexity (Theorem 3).

Central to their findings is a "reduction term" $\Delta(\lambda)$, which quantifies the shrinkage of the function class due to the co-regularization constraint. This bound depends on the kernel matrices of both labeled and unlabeled data, highlighting how unlabeled data helps restrict the model space even before labels are observed.

Empirical Evaluation

To validate their theoretical findings, the authors tested CoRLS on 29 regression datasets from the UCI repository. Since these were not natively multi-view, views were synthesized by randomly splitting features into two equal sets. They employed a 10-fold "inverse" cross-validation scheme—using one fold as labeled data and nine as unlabeled—to simulate a data-scarce semi-supervised environment.

Key Results

The primary theoretical contribution is the derivation of a tight bound on the Rademacher complexity. The empirical results confirm that this theoretical measure captures the physical reality of the learning process. Specifically, the authors found a significant correlation between the calculated decrease in Rademacher complexity and the observed improvement in Root Mean Square (RMS) error when comparing CoRLS to standard 2-view RLS.

Correlation between the decrease in Rademacher complexity and the percentage improvement in RMS error for CoRLS compared to 2-View RLS.

As shown in the figure above, the reduction in complexity serves as a reliable predictor of performance gains. The correlation coefficient of $r = 0.67$ across diverse datasets suggests that co-regularization's benefit is fundamentally tied to its ability to prune the hypothesis space of functions that lack cross-view agreement.

Discussion and Conclusion

The study demonstrates that co-regularization is more than just a heuristic; it is a mathematically grounded constraint that utilizes unlabeled data to map the input space and restrict the search for optimal predictors. However, the authors caution that complexity reduction does not inherently guarantee accuracy; the views must still contain sufficient information to model the target variable. Future work may leverage these complexity bounds for automated hyperparameter tuning, potentially optimizing the co-regularization parameter $\lambda$ without the need for extensive validation sets.

Summary updated

BibTeX
@article{rosenberg2007rademacher,
  author = {David S. Rosenberg and Peter L. Bartlett},
  title = {{The Rademacher Complexity of Co-Regularized Kernel Classes}},
  journal = {AISTATS},
  year = {2007},
}
Figure