Abstract
We propose a novel method for semi-supervised learning based on data-driven distributionally robust optimization (DRO) using optimal transport metrics. Our proposed method enhances generalization error by using the non-labeled data to restrict the support of the worst case distribution in our DRO formulation. We enable the implementation of the DRO formulation by proposing a stochastic gradient descent algorithm which allows to easily implement the training procedure. We demonstrate the improvement in generalization error in semi-supervised extensions of regularized logistic regression and square-root LASSO. Finally, we include a discussion on the large sample behavior of the optimal uncertainty region in the DRO formulation. Our discussion exposes important aspects such as the role of dimension reduction in semi-supervised learning.
Introduction
Supervised learning models often struggle to generalize when labeled data is scarce. Semi-supervised learning (SSL) addresses this by incorporating large volumes of unlabeled data to better understand the underlying structure of the input space. While traditional SSL methods often rely on explicit manifold reconstruction or graph-based techniques—which can be computationally intensive—this paper introduces a framework based on Distributionally Robust Optimization (DRO).
By leveraging the Wasserstein distance to define distributional uncertainty, the proposed SSL-DRO method uses unlabeled data to "map out" the data manifold. This restricts adversarial distribution shifts to realistic variations, significantly improving generalization performance over standard supervised and existing SSL methods.
The SSL-DRO Framework
The core of the SSL-DRO approach is an adversarial game. The model seeks to minimize loss while an "adversary" (nature) attempts to maximize it by perturbing data points within a defined budget ($\delta^*$).
Restricting the Support
The primary innovation lies in how the adversary's power is constrained. In standard DRO, the adversary can move points anywhere in the feature space ($\mathbb{R}^d$). In SSL-DRO, the adversary is restricted to the support defined by the unlabeled data. As shown in the figure above, the unlabeled data acts as a "sketch" of the low-dimensional manifold. By restricting the adversary to this sketch, the model learns to generalize specifically along the directions where data is likely to exist.
Optimization via SGD
To overcome the computational challenges of solving DRO problems, the authors developed a specialized Stochastic Gradient Descent (SGD) algorithm. This algorithm utilizes a smoothing technique and an unbiased gradient estimator based on Multilevel Monte Carlo methods to efficiently handle the complex expectations inherent in the gradient calculations.
Theoretical Insights
The paper establishes a theoretical link between DRO and standard regularization. Standard DRO is mathematically equivalent to certain $L_p$ norm regularizations; SSL-DRO serves as the natural semi-supervised extension of this relationship. Furthermore, the authors demonstrate that the optimal uncertainty region size ($\delta^*$) is intrinsically linked to the data's dimensionality, explaining why SSL is most effective when high-dimensional data sits on a low-dimensional manifold.
Experimental Evaluation
The method was evaluated on six binary classification datasets from the UCI Machine Learning Repository, including Breast Cancer, qsar, Magic, Minibone, and Spambase. DROSSL was compared against standard $L_1$-regularized Logistic Regression (LRL1), Entropy Regularized Logistic Regression (ERLRL1), and Self-training (STLRL1).
Key results include:
- Breast Cancer: DROSSL achieved a test accuracy of 0.956, compared to 0.929 for LRL1.
- Spambase: DROSSL significantly reduced test error to 0.333, whereas LRL1 and STLRL1 yielded errors of 0.588 and 1.47, respectively.
- Stability: DROSSL consistently showed lower standard deviations, indicating higher robustness to different data splits.
Conclusion and Future Work
SSL-DRO provides a robust, principled way to integrate unlabeled data into predictive modeling. While highly effective, the method's performance is sensitive to the density of unlabeled points; if the number of unlabeled points is too small, the restricted support might be too sparse. Future research may explore a broader range of cost functions beyond the $L_2$ transport metric and further optimize the computational efficiency of the unbiased gradient estimator.
Summary updated