Distributionally Robust Data Join

Pranjal Awasthi, Christopher Jung, Jamie Morgenstern

In the ideal landscape of machine learning, researchers work with unified, massive, and perfectly labeled datasets containing every relevant feature. In practice, however, data is often messy and fragmented. A common scenario involves having one dataset with labels but missing key features, and another dataset containing those features but lacking labels. Compounding this issue is the fact that these datasets often originate from different sources—such as different hospitals or geographic regions—meaning they follow distinct underlying distributions.

In the paper "Distributionally Robust Data Join," authors Pranjal Awasthi, Christopher Jung, and Jamie Morgenstern introduce a principled framework to "join" these fragmented sources. Their approach ensures the resulting models remain robust to the distribution shifts that inevitably occur when deploying models in the real world.

The Problem: Fragmentation and Distribution Shift

Standard machine learning assumes that training and test data are drawn from the same distribution. Distributionally Robust Optimization (DRO) relaxes this assumption by training a model to perform well across a "ball" of distributions surrounding the training set. However, traditional DRO typically relies on a single "anchor"—the labeled training set.

This paper addresses two specific real-world challenges:

  1. Data Fragmentation: Labels exist in Dataset A ($S_P$), while auxiliary features exist in Dataset B ($S_A$). These datasets do not share the same rows, making a traditional join impossible.
  2. Distribution Shift: Dataset A and Dataset B may follow slightly different distributions, and the eventual test set may differ from both.

The authors propose a method to build a predictor that hedges against any distribution that is reasonably close to both the labeled data and the feature-rich unlabeled data.

Methodology: The Two-Anchor Framework

The core innovation is the Two-Anchor Distributionally Robust Data Join.

The Ambiguity Set

Instead of a single Wasserstein ball, the authors define an "ambiguity set" of distributions $Q$. This set contains all distributions that are within a distance $r_1$ of the labeled set and $r_2$ of the unlabeled auxiliary set. The learner's goal is to find a model $\theta$ that minimizes the maximum loss over this intersection of possible distributions.

Tractable Reformulation

Solving a "min-max" (saddle-point) problem over probability distributions is computationally intensive. The authors utilize Kantorovich duality to transform this into a manageable minimization problem.

A significant technical hurdle involves the infimal convolution. When two anchors are present, the dual problem involves a complex interaction between the datasets. The authors demonstrate that this interaction is convex and provide a method to approximate it using linear interpolation between extreme points. This allows the problem to be solved using standard Projected Gradient Descent (PGD).

Empirical Evaluation

The authors evaluated their approach using both synthetic and real-world data:

  • Synthetic Data: A custom environment was designed with two distinct groups and a forced distribution shift. This highlighted the "data join" advantage, particularly when one group was underrepresented in the labeled set but present in the unlabeled set.
  • UCI Machine Learning Repository: The method was tested on four classic datasets: Breast Cancer (BC), Ionosphere (IO), Heart Disease (HD), and Handwritten Digits (1vs8). Features and labels were artificially split to simulate fragmented data.

Key Results

  • Synthetic Performance: In tests with heavy distribution shifts, the Data Join (DJ) method achieved 99.23% accuracy. In contrast, vanilla logistic regression reached only 41.26%, and standard single-anchor DRO reached 90.68%.
  • Real-World Gains: On the Ionosphere dataset, the DJ method achieved 82.08% accuracy, outperforming the 77.64% achieved by vanilla logistic regression. Even without explicit distribution shifts, the "hedging" behavior of the DJ method allowed it to extract more value from auxiliary features than simple imputation methods.

Insights and Implications

  • Geometry and Robustness: By utilizing the Wasserstein distance (Earth Mover's distance), the model accounts for the underlying geometry of the features. This provides better robustness against "black swan" outliers compared to methods using f-divergences like KL-divergence.
  • Fairness without Demographics: A major potential application is in algorithmic fairness. Often, researchers want to build fair models but lack demographic information (e.g., race or gender) in their labeled data. If a separate, unlabeled dataset exists with those tags, this framework can "join" that information to penalize unfairness during training.

Limitations and Future Work

Despite its strengths, the framework has several limitations:

  • Hyperparameter Sensitivity: Performance is highly dependent on the choice of radii ($r_A, r_P$). Radii that are too small sacrifice robustness, while radii that are too large lead to overly pessimistic models and lower accuracy.
  • Computational Cost: While the reformulation is convex, it remains more computationally demanding than standard empirical risk minimization.
  • Approximation Gap: The tractable algorithm relies on an approximation (Theorem 3.5). While proven to be small, it remains an approximation of the true robust objective.

Future research directions include extending the framework to accommodate more than two anchors and exploring its application with diverse loss functions beyond logistic loss.

Summary updated

BibTeX
@inproceedings{awasthi2023distributionally,
  author = {Pranjal Awasthi and Christopher Jung and Jamie Morgenstern},
  title = {{Distributionally Robust Data Join}},
  booktitle = {FORC},
  year = {2023},
  url = {https://openreview.net/forum?id=9dRGe06Kc7},
}
Figure