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: The Challenge of One-Sided Feedback

In many real-world AI applications, feedback is fundamentally biased. Consider bank lending: a bank only discovers if a person would have repaid a loan if they actually grant the loan. If the model incorrectly predicts someone will default (a false negative), that person is rejected, and the bank never sees the "label" that would have proven the model wrong.

This creates a dangerous feedback loop where training data is filtered by past decisions, leading to selective sampling bias. While many practitioners assume the main issue is "label imbalance," this research argues the real challenge is myopia. Without a strategy to explore "negative" regions where the model is uncertain, the system may never correct its own mistakes, potentially leading to suboptimal performance and systemic unfairness. Standard "greedy" learning often fails to converge in these scenarios.

Methodology

The authors focus on Generalized Linear Models (GLMs) and introduce several key components to address this bias:

  1. One-Sided Loss: A new objective function that penalizes the model when its decision differs from a "Bayes-optimal" rule, scaled by the distance between the expected outcome and a decision threshold $c$.
  2. Adaptive One-Sided Batch Algorithm: The primary contribution is an algorithm using a "Upper Confidence Bound" (UCB) style approach. Instead of predicting based solely on the mean estimate, it adds an uncertainty bonus: $\mu(x^\top \beta) + \text{uncertainty term} > c$. If the model is uncertain enough about a "negative" sample, it will "query" the label (e.g., grant the loan) to improve future accuracy.
  3. SGD Variant: For large-scale streaming data, a stochastic gradient descent version maintains theoretical guarantees while being computationally efficient.

Experimental Setup and Datasets

The approach was evaluated on 10 diverse real-world datasets covering critical social and business domains, including Finance (Bank Marketing, German Credit), Social Justice (COMPAS, Communities and Crime), and Medical/Health (Diabetes, EEG Eye State). The researchers simulated one-sided feedback by only revealing labels for samples the models "accepted" based on different decision cutoffs (50th and 70th percentiles).

Key Insights

  • Greedy Learning Failure: The authors prove that a greedy learner—one that simply fits the best model to the data it has seen—can fail to converge to the truth even with infinite data. Initial errors can prevent the model from ever seeing the data needed for correction.
  • Efficiency of Adaptive Learning: A "passive" learner (random exploration) requires significantly more data ($O(T^{2/3})$) to reach the same performance that the proposed adaptive learner achieves in $O(\sqrt{T})$.
  • Targeted Uncertainty: Effective exploration shouldn't be random (like $\epsilon$-greedy). Instead, it should target samples where the model's "error bars" cross the decision threshold, allowing for "cautious optimism."

Key Results

Across nearly all 10 datasets, the proposed adaptive algorithm achieved the lowest cumulative one-sided loss compared to common baselines like $\epsilon$-greedy, margin-based exploration, and simple greedy fitting. The method proved robust across both Linear and Logistic Regression frameworks.

Average loss over time across four representative datasets (Adult, COMPAS, Bank, and Crime) comparing the proposed adaptive algorithm against several baselines.

The authors also provided a regret bound of $\tilde{O}(\sqrt{T})$, closing the gap between theory and practice for this class of online learning problems.

Limitations and Future Work

While the results are promising, several areas for future research remain:

  • Model Constraints: Current guarantees are specific to Generalized Linear Models. Extending these to non-linear models like Deep Neural Networks remains a challenge due to the difficulty of quantifying uncertainty in those architectures.
  • Fixed Cutoffs: The paper assumes a fixed decision threshold $c$, whereas real-world business contexts might involve dynamic thresholds based on resource constraints.
  • Computational Overhead: Maintaining and inverting a covariance matrix in the batch algorithm can be expensive in high-dimensional spaces, though the SGD variant offers a mitigation strategy.

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