Online Learning Using Only Peer Prediction

Yang Liu, David P. Helmbold

Abstract

In the classical online learning setting, a learner makes predictions based on expert advice and subsequently observes the ground-truth outcome to update its strategy. However, many real-world applications—ranging from crowdsourcing to long-term climate forecasting—lack immediate or accessible ground-truth feedback. This paper, presented at AISTATS 2020, introduces a framework for online learning that relies solely on peer prediction. By utilizing a novel "peer calibration" mechanism, the authors demonstrate that it is possible to achieve sub-linear regret against the unobserved truth, effectively learning to identify the best experts by comparing them against the consensus of their peers.

Introduction

The "prediction with expert advice" framework is a cornerstone of machine learning. In this setting, an algorithm aggregates the opinions of $N$ experts to make a decision at each time step $t$. Traditionally, the algorithm then observes the actual outcome $y_t$, calculates the loss for each expert, and adjusts its weights accordingly.

In practice, this feedback loop is often broken. In hiring processes, the true quality of a candidate may not be known for years. In crowdsourcing, the volume of data often precludes the use of a "gold standard" for verification. This paper addresses the fundamental question: How can we identify and follow the best experts when we lack direct feedback on their performance?

The Peer Prediction Framework

The authors propose a self-supervised approach that replaces the missing ground truth $y_t$ with a peer reference answer $\hat{y}_t$. This reference is typically an aggregation, such as a majority vote, of the experts' predictions. To make this work, the framework introduces two core technical components:

  1. Peer-Score Functions: Instead of standard loss functions like squared error, the authors design specific scoring functions $s(\cdot)$ that evaluate an expert's prediction against the peer consensus.
  2. Peer Calibration ($\psi$-compatibility): This is the theoretical bridge of the paper. The authors define a condition called $\psi$-compatibility. If a peer-score function is correctly calibrated, minimizing the peer-score is mathematically guaranteed to minimize the true (but invisible) loss.

Handling Noisy Consensus

Because the peer consensus is itself a noisy approximation of the truth, the authors incorporate methods to estimate the "noise rate" ($\eta$) of the crowd. They introduce a "partitioning" strategy where experts are split into two groups (A and B). One group acts as the reference to evaluate the other, allowing the algorithm to estimate error rates and de-bias the scores without any external gold-standard labels.

Key Theoretical Insights

The paper's most significant contribution is proving that the absence of ground truth does not prevent an algorithm from achieving optimal performance bounds.

  • Sub-linear Regret: The authors prove that their peer-prediction algorithms achieve a regret bound of $R_T \leq O(\sqrt{T \ln N})$. This implies that as time progresses, the algorithm's average error converges to that of the best expert in the pool, even though the algorithm never observes a single correct label.
  • Robustness to Unknown Noise: The framework remains effective even if the crowd's error rate is unknown or non-stationary. By using a converging estimate of the noise, the algorithm maintains its performance guarantees.
  • Beyond Simple Majority: A common pitfall in consensus-based systems is that they tend to favor the most "average" or conformist experts. The calibrated peer-scores developed here are designed to reward experts who are closer to the underlying probability distribution of the truth, even when the aggregate crowd is slightly biased.

Limitations and Future Directions

While the framework provides a robust theoretical foundation for learning without labels, it relies on the "Better than a Coin Flip" assumption. Specifically, the peer consensus must be at least somewhat correlated with the truth (an error rate $\eta < 0.5$). If the majority of the crowd is consistently wrong or worse than random, the peer-score will naturally lead the algorithm astray.

Additionally, the current work focuses primarily on binary outcomes. Future research may extend these $\psi$-compatibility conditions to multi-class or continuous variables. The authors also suggest that "Peer Loss" functions could eventually be simplified to remove the need for explicit noise rate estimation, making the framework more accessible for practical supervised learning with noisy labels.

Conclusion

This research demonstrates that ground truth is not a strictly necessary requirement for effective online learning. By leveraging the collective intelligence of a peer group and applying rigorous calibration, algorithms can navigate uncertain environments and identify high-performing experts with the same theoretical efficiency as if they had access to perfect feedback.

Summary updated

BibTeX
@inproceedings{liu2020online,
  author = {Yang Liu and David P. Helmbold},
  title = {{Online Learning Using Only Peer Prediction}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}
Figure