Distributionally Robust Data Join

Pranjal Awasthi, Christopher Jung, Jamie Morgenstern

Here is a concise, blog-style technical summary of the paper.

TL;DR

This paper introduces Distributionally Robust Data Join, a framework for training machine learning models across two fragmented data sources: a labeled dataset missing auxiliary features, and an unlabeled dataset containing those auxiliary features under a potentially different distribution. By formulating this as a two-anchor Wasserstein Distributionally Robust Optimization (DRO) problem, the authors derive a tractable convex approximation with provable approximation guarantees, outperforming standard baselines under distribution shifts.

What Problem Does This Paper Address?

In real-world settings (such as cross-hospital medical research), data is often fragmented across multiple sources. For instance:

  • Dataset 1 ($S_P$): Contains shared features $x$ and task labels $y$, but lacks auxiliary features.
  • Dataset 2 ($S_A$): Contains shared features $x$ alongside useful auxiliary features $a$, but lacks labels $y$.

Standard semi-supervised learning or data imputation methods typically assume that data is missing at random or that both sets originate from identical distributions without distribution shift. In practice, both datasets often follow distinct distributions ($D_1 \neq D_2$), yet an ideal target distribution might be close to both. The fundamental question is: How do we reliably join and learn from both datasets while hedging against worst-case distribution shift across features and labels?

Methods

The authors formulate the problem as a minimax optimization over an ambiguity set of joint distributions $Q(x, a, y)$ bounded by two Wasserstein metric balls: $$Q \in \mathcal{W}(S_A, S_P, r_A, r_P) \implies D_{d_A}(Q_{X,A}, \hat{P}_{S_A}) \le r_A \quad \text{and} \quad D_{d_P}(Q_{X,Y}, \hat{P}_{S_P}) \le r_P$$

Because directly optimizing over 3-way couplings is computationally challenging and leads to an intractable semi-infinite program, the authors develop:

  1. Strong Duality Formulation: By leveraging Kantorovich duality, they convert the saddle-point problem into a minimization dual program.
  2. Convex Conjugacy & Infimal Convolution Approximation: The dual program contains a non-convex supremum constraint over $(x, a)$. The authors bound this supremum term using infimal convolution of norm-constrained linear functions, then approximate it using an explicit point-evaluation trick at $\hat{x}_{i,j} = \arg\min (x_i^A, x_j^P)$ combined with properties of the logistic loss.
  3. Tractable Decomposition: The final approximation decomposes into two convex optimization problems solvable via standard convex solvers or projected gradient descent, with an explicit approximation error bound proportional to $2\hat{\alpha} \max_{i,j} \|x_i^A - x_j^P\|$.

Datasets

  • Synthetic Dataset: A synthetic binary classification benchmark generated via a mixture of multivariate Gaussians across two demographic groups, engineered explicitly to exhibit covariate shift between the labeled set ($S_P$, mostly group 1) and unlabeled/test sets ($S_A$ and $S_{\text{test}}$, mostly group 2).
  • UCI Benchmarks: Four standard real-world datasets adapted to simulate fragmented data join tasks:
  • Breast Cancer (BC)
  • Ionosphere (IO)
  • Heart Disease (HD)
  • Handwritten Digits (1 vs. 8)

Key Insights and Ideas

  • Beyond Standard 1-Anchor DRO: Standard Wasserstein DRO anchors uncertainty around a single empirical distribution. Here, the ambiguity set is an intersection of two Wasserstein balls ("two anchors"). This naturally restricts the set of adversarial distributions by forcing them to stay consistent with both the labeled training set and the unlabeled auxiliary feature set.
  • Indirect Relation Learning via Overlapping Features: Shared features $x$ act as a bridge. The quality of matching between feature representations in $S_A$ and $S_P$ determines how effectively the model links the auxiliary features $a$ to the target label $y$.
  • Fairness Applications without Protected Labels: When auxiliary features represent protected demographic attributes that cannot legally or ethically be paired with labels in the primary task, this framework allows enforcement of fairness constraints across demographic groups without explicit imputation.

Key Results

  • Synthetic Shift Experiment: On the synthetic shift task, the Data Join (DJ) approach substantially outperformed single-dataset baselines by leveraging the unlabeled auxiliary features closer to the test distribution:
  • Logistic Regression (LR): $41.26\% \pm 10.49\%$
  • Regularized Logistic Regression (RLR): $57.86\% \pm 39.92\%$
  • Distributionally Robust LR (DRLR): $90.68\% \pm 0.76\%$
  • Robust Data Join (DJ): $99.23\% \pm 0.57\%$
  • UCI Real-World Datasets: Even without explicit distribution shift (i.i.d. splits), DJ outperformed or matched baselines on limited labeled training data:
  • Breast Cancer ($m_1=5$): DJ reached $91.40\%$ vs. LR's $90.12\%$ and RLR's $90.53\%$.
  • Ionosphere ($m_1=4$): DJ reached $82.08\%$ vs. LR's $77.64\%$ and RLR's $79.15\%$.
  • Digits (1vs8): DJ reached $90.84\%$ vs. LR's $87.29\%$ and RLR's $89.53\%$.

Limitations and Future Work

  • Hyperparameter Sensitivity: The practitioner must specify the Wasserstein radii $r_A$ and $r_P$, which requires prior intuition or validation data regarding the distance between the training and target distributions.
  • Worst-Case Pairwise Dependency: The theoretical approximation error scale depends on the maximum pairwise feature distance $\max_{i,j} \|x_i^A - x_j^P\|$. While the authors propose restricting this to $k$-nearest neighbors, doing so relies on transport heuristics.
  • Trade-off Between Robustness and Clean Accuracy: As with most DRO approaches, hedging against worst-case distributions can lead to conservative models that sacrifice marginal accuracy in strictly non-shifted environments.

Summary updated

Abstract

Suppose we are given two datasets: a labeled dataset and unlabeled dataset which also has additional auxiliary features not present in the first dataset. What is the most principled way to use these datasets together to construct a predictor? The answer should depend upon whether these datasets are generated by the same or different distributions over their mutual feature sets, and how similar the test distribution will be to either of those distributions. In many applications, the two datasets will likely follow different distributions, but both may be close to the test distribution. We introduce the problem of building a predictor which minimizes the maximum loss over all probability distributions over the original features, auxiliary features, and binary labels, whose Wasserstein distance is r₁ away from the empirical distribution over the labeled dataset and r₂ away from that of the unlabeled dataset. This can be thought of as a generalization of distributionally robust optimization (DRO), which allows for two data sources, one of which is unlabeled and may contain auxiliary features.
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},
}

Loading related content...

Figure