Abstract
In traditional online learning, an algorithm updates its strategy based on immediate feedback from the ground truth. However, in many real-world scenarios—such as long-term forecasting or crowdsourcing—the ground truth is delayed, expensive, or entirely unavailable. This paper investigates the "blind" learning scenario where an algorithm must identify the best experts using only the predictions of their peers. We present a framework based on peer prediction that utilizes a calibrated peer-score function to treat the consensus of experts as a proxy for the truth. We demonstrate that under specific compatibility conditions, an algorithm can achieve sub-linear regret relative to the best expert, even without ever observing the true outcomes.
1. Introduction
The "expert advice" problem is a cornerstone of online learning. In the standard model, a learner receives predictions from a set of experts, makes its own prediction, and then observes the actual outcome (the ground truth). The learner then updates the weights assigned to each expert based on their accuracy.
However, this model fails when the ground truth is missing. Consider a hiring committee evaluating candidates; the true "success" of a hire might not be known for a decade. In crowdsourcing, a platform may receive thousands of labels for images without knowing the correct classification for any of them. This paper, "Online Learning Using Only Peer Assessment" by Yang Liu and David P. Helmbold, addresses this gap by proposing a method to reward "good" experts and penalize "bad" ones using peer-to-peer consistency rather than external validation.
2. The Peer Prediction Framework
The fundamental challenge in learning without ground truth is that the majority opinion is not necessarily the correct one. A simple majority-vote approach can be lead astray if the group is consistently biased. To overcome this, the authors propose a framework centered on Peer Prediction.
Instead of comparing an expert’s prediction to the true outcome $y_t$, the algorithm compares it to a "peer reference answer" $\hat{y}_t$ derived from the other experts in the pool. The core of this approach is the Peer-Score Function ($s$). This function is designed to estimate an expert's loss by using the peer consensus as a noisy proxy.
2.1 Peer Calibration and $\psi$-Compatibility
The authors introduce the concept of Peer Calibration to ensure that the proxy loss leads to the same conclusions as the true loss. This is formalized through $\psi$-Compatibility, a mathematical relationship between the proxy loss (calculated via peer scores) and the hidden true loss. If the scoring function is $\psi$-compatible, an algorithm that minimizes the proxy loss is guaranteed to also minimize the true loss over time.
3. Managing Noisy Consensus
Because the peer consensus is itself a product of fallible experts, it is inherently noisy. The algorithm must account for the error rate ($\eta$) of this consensus.
3.1 Noise Estimation without Labels
One of the paper's most significant contributions is a method for estimating noise without any ground-truth labels. The authors demonstrate that by partitioning experts into subgroups and analyzing their patterns of disagreement, the overall accuracy of the group can be calculated. This "self-supervised" approach allows the algorithm to adjust its scoring function dynamically.
3.2 Homogenization
To handle non-stationary environments where the group's accuracy might fluctuate, the authors introduce a "homogenization" or "flipping" mechanism. By randomly perturbing the reference labels, the algorithm makes the noise more consistent, which allows for more stable regret bounds.
4. Theoretical Results
The paper provides a rigorous theoretical foundation for this approach, focusing on regret analysis and competitive ratios.
- Regret Bounds: In Theorem 3, the authors prove that the "True Regret"—the difference between the algorithm's performance and the best expert's performance on the hidden labels—is bounded. As the number of trials $T$ increases, the average regret approaches zero, indicating that the algorithm eventually performs as well as the best expert.
- Squared Loss Construction: The authors derive a concrete peer-score function for settings involving squared loss. This construction is shown to be robust against label noise, providing a practical template for implementation.
- Competitive Ratio: Theorem 9 addresses scenarios where expert error rates vary over time. The authors show that their algorithm maintains a competitive ratio relative to the optimal loss, plus a sub-linear term, ensuring efficiency even in shifting environments.
5. Discussion and Limitations
While the paper establishes a powerful framework for blind online learning, it notes several areas for further development. The current proofs rely on a "gap" assumption—a minimum difference in performance between the best and second-best experts—to guarantee convergence. Additionally, while the framework is general, much of the specific derivation focuses on binary outcomes.
As a purely theoretical work, the paper lacks empirical validation on real-world datasets. Future research is expected to apply these peer-prediction methods to practical domains such as committee decision-making and large-scale crowdsourcing platforms to test the robustness of the $\psi$-compatibility framework in practice.
6. Conclusion
Liu and Helmbold provide a compelling solution to the problem of online learning without ground truth. By leveraging the internal consistency of expert groups and carefully calibrating peer scores, they demonstrate that it is possible to identify and follow the best experts in a "blind" environment. This work opens new avenues for self-supervised learning in high-stakes domains where feedback is delayed or unavailable.
Summary updated