Refereed Learning

This paper introduces the framework of "refereed learning," where a learner leverages two competing provers (one honest) to efficiently select the superior black-box model with high precision using only a single query to the ground truth, achieving accuracy levels that are provably unattainable by learners with access to just a single prover or no provers at comparable cost.

The Gist

Imagine you are a hiring manager trying to choose the best candidate for a job. You have two applicants, Alice and Bob, who both claim to be experts at predicting the weather. However, you don't have a weather station of your own, and checking the actual weather forecast is incredibly expensive and time-consuming (maybe you have to send a drone into a storm to verify the data).

You can't just trust their word. You need a way to figure out who is actually better without spending a fortune on verification.

This is the problem the paper "Refereed Learning" solves.

The Setup: The Two-Headed Debate

In this scenario, you (the Learner/Verifier) are weak and resource-poor. You have two Provers (Alice and Bob's representatives).

• One Prover is Honest and wants to prove their candidate is the best.
• The other Prover is Dishonest (or "strategic") and wants to win the argument, even if they have to lie.

The magic trick of this paper is that you don't need to know who is lying. You just need to know that at least one of them is telling the truth. By forcing them to compete against each other, you can extract the truth with very little effort.

The Old Way: The "Brute Force" Approach

Before this paper, if you wanted to check who was better, you might try to ask them to predict the weather for 10,000 different days.

• The Problem: To verify their answers, you'd have to check the actual weather for all 10,000 days. That's too expensive!
• The "Single Prover" Fix: Some previous methods let you ask one powerful AI to do the checking for you. But if that AI lies, you have no way to catch it unless you check a huge number of answers yourself.

The New Way: The "Refereed" Approach

This paper introduces a system where you act like a referee in a debate. Here is how it works, using a few analogies:

1. The "Spot the Difference" Game (Zero-One Loss)

Imagine Alice and Bob are trying to predict a simple "Yes/No" outcome (like "Will it rain?").

• The Trick: Instead of checking every single day, you ask the Provers to find the specific days where Alice and Bob disagree.
• The Competition: Alice says, "On Day 5, it will rain." Bob says, "On Day 5, it will be sunny."
• The Referee Move: You pick one of those "disagreement days" at random. You ask the Provers what the answer is.
  • If they agree, you trust them.
  • If they disagree, you ask one of them to prove it. You check the weather for that single day.
  • If the Prover lied, they get caught immediately. If they are honest, they win the round.
• The Result: By repeating this a few times, you can statistically prove who is better, even if you only check the weather once in the entire process.

2. The "Weighted Lottery" (Metric Loss)

Sometimes the answer isn't just "Yes/No." Maybe Alice predicts "Light Rain" and Bob predicts "Hurricane," while the truth is "Tornado." The difference matters more.

• The Trick: The paper invents a special "Weighted Lottery." The Provers have to generate a list of days where the predictions are most different from each other.
• The Competition: The dishonest Prover can't fake the lottery results because the other Prover is watching. If the dishonest one tries to cheat the lottery to hide a bad prediction, the honest one will expose the lie.
• The Result: You end up checking the weather only on the days that matter most, giving you a highly accurate verdict with minimal cost.

Why is this a Big Deal?

The paper proves that with this "two-prover" setup, you can achieve near-perfect accuracy while only asking for one single verification from the ground truth.

• Without Provers: You might need to check 1,000,000 data points to be sure.
• With One Prover: You might need to check 10,000 points to catch a liar.
• With Two Competing Provers: You only need to check 1 point.

The "Catch" (Lower Bounds)

The paper also explains the limits of this magic:

1. The Provers must be smart: To pull off this trick, the Provers (the AI agents) might need to do a lot of heavy lifting (computational work) to find the "disagreement days" or generate the "weighted lottery." If the models are too complex, the Provers might need super-computers to do their job.
2. You still need a little access: You can't do this if you have zero access to the truth. You need at least one way to check a single data point to break the tie.

Real-World Analogy: AlphaFold

The paper mentions AlphaFold (a system that predicts how proteins fold).

• The Problem: To verify if a new AI model predicts protein folding correctly, scientists have to synthesize the protein and run expensive lab experiments. Doing this for millions of predictions is impossible.
• The Solution: Two competing AI labs (Provers) argue about which model is better. They debate specific protein structures. You, the scientist, only need to run one or two expensive lab experiments to see who is lying. You save millions of dollars and years of time.

Summary

Refereed Learning is a method where a weak verifier uses two competing, powerful agents to find the truth. By pitting them against each other, the verifier can detect lies and identify the best model with almost zero cost, provided the agents are willing to do the heavy computational lifting. It turns a "trust me" situation into a "prove it" game where the truth always wins.

Technical Summary

Technical Summary: Refereed Learning

1. Problem Statement

The paper addresses the challenge of verifying the performance of black-box machine learning models when the ground truth is expensive to compute (e.g., requiring physical experiments like cryo-EM) and the models themselves are opaque.

In standard settings, a learner (verifier) must estimate the loss of a model $h$ with respect to a ground truth function $f$ over a distribution $D$. This typically requires:

1. High Sample Complexity: Drawing a large number of labeled samples $(x, f(x))$ to estimate empirical loss.
2. High Query Complexity: Querying the expensive ground truth $f$ many times.
3. Trust Issues: Relying on a single powerful but untrusted prover to report loss values, which is prone to deception.

The authors propose a new setting called Refereed Learning, where the learner interacts with two competing provers ($P_0, P_1$), only one of whom is honest (or they are strategic agents in a zero-sum game). The goal is to select the model with the lower loss relative to the ground truth with high accuracy, while minimizing the learner's access to the ground truth and the distribution.

2. Methodology and Core Techniques

The paper introduces a framework where the learner-verifier ($V$) interacts with two provers to verify properties of models $h_0, h_1$ against a ground truth $f$ and distribution $D$. The core methodology relies on three novel cryptographic/algorithmic tools:

A. Certifiable Sum Protocol

This allows the verifier to compute the sum of a function $t(x)$ over a domain $\{0,1\}^d$ (e.g., $\sum t(x)$) with query access only to $t$, assisted by two provers.

• Mechanism: The provers claim the total sum and the sums of two disjoint halves of the domain. The verifier recursively challenges the provers to identify which half contains the lie. After $d$ rounds, the verifier is left with a single point and checks it with one query.
• Guarantee: If one prover is honest, the verifier obtains the correct sum with high probability, even if the other prover is malicious.

B. Certifiable Sample Protocol

This enables the verifier to efficiently sample from an arbitrary distribution $D$ (even if the support is exponentially large or sparse) without knowing the Probability Mass Function (PMF) explicitly, provided they have query access to the PMF.

• Mechanism: Uses Inverse CDF Sampling. The verifier picks a random value $p \in [0,1]$ and asks provers to return the element $x$ such that the cumulative probability up to $x$ contains $p$. The Certifiable Sum protocol is used to verify that the provers' claimed cumulative sums are consistent with the PMF.
• Significance: Allows sampling from complex distributions (like the "disagreement set" of two models) without enumerating the domain.

C. Refereed Query Delegation

A technique to offload the burden of querying the ground truth $f$ to the provers.

• Mechanism: The verifier sends a query to both provers. If they agree, the verifier accepts. If they disagree, the verifier makes a single query to $f$ to determine the truth, identifies the liar, and uses the honest prover's answers for all subsequent queries.
• Result: The verifier's query complexity to $f$ is reduced to at most 1, regardless of the number of samples needed for statistical accuracy.

3. Key Contributions and Results

The paper presents protocols for different error regimes (multiplicative, additive, and mixed) and establishes lower bounds proving their optimality.

A. Multiplicative Error Protocols (High Precision)

The primary contribution is a protocol that achieves a multiplicative approximation of the best model's loss (i.e., output loss $\le (1+\epsilon) \times \text{best loss}$) with extremely low cost.

• Zero-One Loss: For the zero-one metric, the protocol selects a model with loss within a factor of $(1+\epsilon)$ of the optimal.
  • Learner Cost: 1 query to the ground truth $f$. Communication complexity is $\tilde{O}((1 + 1/\epsilon^2) \cdot \text{poly}(d))$.
  • Prover Cost: In the general case, provers may require exponential time (inherent lower bound). However, for Juntas (functions depending on few variables), provers can be efficient ($\text{poly}(d)$).
• General Metric Loss: For arbitrary metrics, the protocol achieves a $(3+\epsilon)$-approximation with similar query and communication costs.
  • Technique: Uses a loss-rescaled distribution $D_{h_0, h_1}^\ell$ that places higher probability mass on points where the models disagree significantly, ensuring that high-loss points are sampled efficiently.

B. Additive and Mixed Error Protocols

The authors show how to achieve additive error $\eta$ (or mixed $\alpha, \eta$) with improved efficiency over prior single-prover work (e.g., [GRSY21]).

• Additive Error: The verifier makes 1 query to $f$ and draws $O(1/\eta^2)$ samples. Provers handle the labeling.
• Mixed Error: Achieves $(1+\epsilon, \eta)$ error. The verifier makes 1 query to $f$, draws $O((1+1/\epsilon^2)/\eta)$ samples, and provers make significantly fewer queries to $f$ compared to single-prover settings.

C. Lower Bounds (Optimality)

The paper proves that their protocols are optimal in several respects:

1. Query Access to Ground Truth: Without query access to $f$ (relying only on labeled samples), the learner requires $\Omega(1/\eta)$ samples, making high-precision ($\eta \to 0$) impossible without direct queries.
2. Query Access to PMF: Without query access to the distribution's PMF $Q_D$, the learner requires $\Omega(1/\eta)$ samples.
3. Prover Complexity: For general black-box models, achieving purely multiplicative error requires provers to run in exponential time (specifically, solving 3-SAT). This is proven via a reduction, showing that a polynomial-time prover would imply $P=NP$ (or similar hardness assumptions).

4. Significance and Applications

• Efficiency in Verification: The work demonstrates that with two competing provers, a resource-constrained verifier can assess model accuracy with constant (or single) queries to expensive ground truth data. This is a massive improvement over standard empirical risk minimization which scales with $1/\eta^2$.
• Real-World Applicability: The framework is ideal for domains like AlphaFold (protein folding), where validating a prediction requires expensive physical experiments. A researcher can use this protocol to verify which of two AI models is better by performing only a handful of physical experiments, while the "heavy lifting" of checking thousands of predictions is delegated to competing AI agents.
• Theoretical Foundation: It extends the theory of Refereed Delegation of Computation (FST88, CRR11) into the realm of Machine Learning and Property Testing, providing the first rigorous framework for learning with competing provers.
• Strategic Incentives: The model aligns with economic incentives (e.g., prediction markets or AI debate systems) where agents are rewarded for truthfulness and penalized for inconsistency, allowing the system to function even if neither prover is strictly "honest" but both are rational.

In summary, Refereed Learning provides a theoretically sound and practically efficient method for verifying black-box models against expensive ground truths, leveraging competition between provers to achieve high precision with minimal resource expenditure from the verifier.