Learning the Truth From Only One Side of the Story

Heinrich Jiang, Qijia Jiang, Aldo Pacchiano

Abstract

Learning under one-sided feedback (i.e., where we only observe the labels for examples we predicted positively on) is a fundamental problem in machine learning—applications include lending and recommendation systems. Despite this, there has been surprisingly little progress made in ways to mitigate the effects of the sampling bias that arises. We focus on generalized linear models and show that without adjusting for this sampling bias, the model may converge suboptimally or even fail to converge to the optimal solution. We propose an adaptive approach that comes with theoretical guarantees and show that it outperforms several existing methods empirically. Our method leverages variance estimation techniques to efficiently learn under uncertainty, offering a more principled alternative compared to existing approaches.

Introduction

In many real-world decision-making scenarios, feedback is inherently asymmetric. In bank lending, criminal justice, and medical screening, we typically only observe the outcome of our decisions when we act affirmatively (e.g., granting a loan or performing a biopsy). If a bank denies a loan, it never learns whether that applicant would have repaid it. This "one-sided feedback" creates a dangerous sampling bias: the model only learns from the sub-population it already deems favorable. If the model is initially incorrect about a specific demographic, it may never collect the data necessary to correct that mistake, leading to a permanent feedback loop of suboptimal decisions and systemic unfairness.

Methodology

This research focuses on Generalized Linear Models (GLMs) and addresses the inherent "myopia" of standard learning algorithms in one-sided feedback settings.

The Failure of Greedy Learning

The authors demonstrate theoretically that a "greedy" learner—one that simply updates its model based on the positive outcomes it observes—can fail to converge to the optimal solution. Because it stops exploring regions of the feature space it has prematurely labeled as negative, it can become "stuck" in a suboptimal state.

Adaptive One-Sided Batch Algorithm

To overcome this, the paper introduces an adaptive strategy that incorporates uncertainty quantification. Instead of relying solely on the model's point estimate, the algorithm calculates an uncertainty bonus, similar to Upper Confidence Bound (UCB) strategies used in multi-armed bandit problems. By examining the covariance matrix of observed data, the algorithm identifies "regions of uncertainty." If a new data point falls into such a region, the algorithm is more likely to predict a positive outcome to gain information, even if the current model's prediction is slightly below the decision threshold.

Empirical Evaluation

Datasets

The proposed method was evaluated on 10 diverse benchmark datasets simulating one-sided feedback scenarios, including:

  • Finance/Credit: Adult (income prediction), Bank Marketing, German Credit, Australian Credit.
  • Social/Justice: ProPublica’s COMPAS (recidivism), Communities and Crime.
  • Medical/Health: Blood Transfusion, Diabetes.

Key Results

The adaptive algorithm consistently outperformed baselines such as standard Greedy, $\epsilon$-Greedy (random exploration), and "Margin" sampling.

Average loss over rounds for COMPAS and Crime datasets.

As shown in the figures, the adaptive method (labeled "Adaptive (ours)") achieves a lower average loss over time compared to other strategies. While greedy learners often see their error rates plateau, the adaptive method's loss continues to drop as it systematically resolves uncertainty in the feature space.

Average loss over rounds for Adult and Bank datasets.

Quantitatively, on the Bank dataset at a 50% cutoff, the adaptive method achieved a cumulative loss of 74.64, significantly lower than the 164.23 recorded for the greedy approach. The method also proved robust across various selection thresholds (from 50% to 95% percentiles).

Discussion and Future Work

Structural Bias and Fairness

A key insight of this work is that one-sided feedback is not merely a "label imbalance" problem but a structural one. The issue lies in the location of missing data within the feature space. By forcing the model to resolve uncertainty rather than relying on biased point estimates, the adaptive approach naturally promotes individual fairness, reducing the likelihood that qualified individuals from under-sampled groups are systematically excluded.

Limitations

The current theoretical guarantees are specific to GLMs. While GLMs are standard in regulated industries like finance, they do not capture the complexity of deep learning architectures. Additionally, the paper assumes a fixed cutoff threshold, whereas real-world scenarios may involve dynamic budgets.

Future Directions

Future research will focus on extending these uncertainty-quantification principles to more complex model classes, such as neural networks, where estimating reliable "error bars" for predictions remains a significant challenge.

Summary updated

Abstract

Learning under one-sided feedback (i.e., where we only observe the labels for examples we predicted positively on) is a fundamental problem in machine learning -- applications include lending and recommendation systems. Despite this, there has been surprisingly little progress made in ways to mitigate the effects of the sampling bias that arises. We focus on generalized linear models and show that without adjusting for this sampling bias, the model may converge suboptimally or even fail to converge to the optimal solution. We propose an adaptive approach that comes with theoretical guarantees and show that it outperforms several existing methods empirically. Our method leverages variance estimation techniques to efficiently learn under uncertainty, offering a more principled alternative compared to existing approaches.
BibTeX
@inproceedings{jiang2021learning,
  author = {Heinrich Jiang and Qijia Jiang and Aldo Pacchiano},
  title = {{Learning the Truth From Only One Side of the Story}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=r8EgnvF-SH},
}
Figure