Refereed Learning

Each language version is independently generated for its own context, not a direct translation.

Stel je voor dat je een zeer dure en complexe wetenschappelijke experiment moet uitvoeren, bijvoorbeeld het testen van hoe goed een nieuwe medicijn werkt. Dit experiment kost duizenden euro's en neemt dagen in beslag.

Nu heb je twee farmaceutische bedrijven die beiden zeggen: "Ons medicijn werkt perfect!" Maar je kunt hun beweringen niet zomaar geloven. Je wilt het beste medicijn kiezen, maar je hebt niet genoeg geld om het experiment duizenden keren te herhalen om de waarheid te achterhalen.

Dit is precies het probleem dat dit paper, getiteld "Refereed Learning" (Gereferdeerd Leren), oplost.

Hier is een uitleg in gewone taal, met behulp van een paar creatieve vergelijkingen:

1. Het Probleem: De "Black Box" en de Dure Waarheid

In de moderne wereld maken computers (AI-modellen) voorspellingen. Soms zijn deze modellen als een zwarte doos: je ziet wat erin gaat en wat eruit komt, maar je weet niet hoe ze precies werken.
Om te weten of een model goed is, moet je het vergelijken met de "waarheid" (de grondwaarheid). Maar die waarheid achterhalen is vaak extreem duur of moeilijk (zoals het uitvoeren van een fysiek experiment).

De oude manier: Om te weten welk van de twee modellen beter is, zou je duizenden experimenten moeten doen. Dat is te duur.
De nieuwe manier (Refereed Learning): Je hebt twee concurrerende bewijzers (de twee bedrijven). Ze willen je overtuigen dat hun model het beste is. Maar hier is de truc: ze zitten tegenover elkaar. Als één liegt, kan de ander dat onthullen.

2. De Oplossing: Het Systeem van de "Rechter"

Stel je een rechtszaak voor. Je bent de rechter (de leerder/verifier). Je hebt twee advocaten (de bewijzers/provers).

Advocaat A zegt: "Mijn cliënt (model A) is perfect!"
Advocaat B zegt: "Nee, mijn cliënt (model B) is perfect!"

In een normaal proces zou je alle bewijzen zelf moeten controleren (duizenden experimenten). Maar in dit nieuwe systeem gebruiken jullie een slimme truc: de weddenschap.

De twee advocaten moeten elkaar uitdagen. Als ze het oneens zijn over een detail, zegt de rechter: "Oké, ik ga dit één keer zelf controleren."

Als advocaat A liegt, zal hij de fout opmerken bij de controle en wordt hij betrapt.
Omdat ze tegen elkaar spelen, heeft de eerlijke advocaat een enorme prikkel om de leugenaar te ontmaskeren.

3. De Magische Truc: "Certifiable Sampling" (Geverifieerd Steekproeven)

Het grootste probleem was: hoe vind je de zeldzame gevallen waarin de modellen het niet met elkaar eens zijn? Stel, model A en B zijn bijna altijd hetzelfde, maar op 1 op de 1.000.000 gevallen maken ze een andere keuze. Als je willekeurig zoekt, duurt het eeuwen voordat je dat ene verschil vindt.

De auteurs hebben een slimme methode bedacht, noem het "De Slimme Zoektocht":

De rechter vraagt de advocaten om een lijst te maken van alle gevallen waarin hun cliënten het niet eens zijn.
De advocaten zeggen: "Hier is de lijst!"
De rechter zegt: "Ik geloof jullie niet zomaar. Bewijs dat jullie de lijst goed hebben gemaakt."
De advocaten moeten dan stap voor stap aantonen dat hun lijst klopt, zonder dat de rechter de hele lijst hoeft te lezen. Ze gebruiken een soort "digitale ladder": ze bewijzen eerst dat de helft van de lijst klopt, dan een kwart, dan een achtste, tot ze bij één specifiek geval zijn.
Als één advocaat liegt op een van die trappen, valt de hele constructie in elkaar en wordt hij betrapt.

Dit stelt de rechter in staat om snel en goedkoop precies die zeldzame gevallen te vinden waar het verschil zit, zonder duizenden experimenten te hoeven doen.

4. Het Resultaat: Meer met Minder

Het paper laat zien dat met deze methode:

De rechter (jij) maar één keer hoeft te experimenteren (één query naar de waarheid).
Je kunt toch met enorme zekerheid zeggen welk model beter is, zelfs als het verschil heel klein is.
Zonder deze truc zou je duizenden experimenten nodig hebben.

5. Waarom is dit belangrijk?

Stel je voor dat je een AI gebruikt voor medische diagnoses of financiële beleggingen. Een klein foutje kan levens kosten of miljoenen kosten.

Vroeger: Je kon het beste model niet kiezen zonder onbetaalbare tests.
Nu: Met "Refereed Learning" kun je twee AI-modellen laten vechten om de eerlijkheid, en jij hoeft maar één keer te kijken om de winnaar te kiezen. Het is alsof je twee detectives laat ruziën over een zaak, en jij hoeft maar één bewijsstuk te controleren om te weten wie de waarheid spreekt.

Kort samengevat:
Het paper introduceert een manier om de kwaliteit van AI-modellen te testen door twee concurrerende experts tegen elkaar uit te spelen. Door slimme wiskundige spelregels (waarbij liegen onmogelijk wordt zonder betrapt te worden), kan een zwakke "rechter" met heel weinig middelen (slechts één test) bepalen welk model het beste is. Het is een revolutionaire manier om vertrouwen te krijgen in dure, onzichtbare technologie.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het paper "Refereed Learning" van Canetti, Linder en Wagaman, geschreven in het Nederlands.

Titel: Refereed Learning (Gereferdeerd Leren)

Auteurs: Ran Canetti, Ephraim Linder, Connor Wagaman
Datum: 11 maart 2026

1. Probleemstelling

Moderne machine learning-taken vereisen enorme hoeveelheden data en rekenkracht, wat vaak leidt tot het gebruik van externe, krachtige maar onbetrouwbare agents voor modeltraining. Een centrale uitdaging is het verifiëren van de prestaties van deze "black-box" modellen zonder volledig te vertrouwen op de leverancier en zonder zelf de volledige grondwaarheid (ground truth) te hoeven evalueren, wat vaak kostbaar of onmogelijk is (bijvoorbeeld bij fysieke experimenten zoals bij AlphaFold).

Traditionele verificatiemethoden (zoals het berekenen van empirische verliezen op grote steekproeven) zijn vaak te duur in termen van steekproeven en query's naar de grondwaarheid. Bestaande werken over verifieerbaar computationeel (zoals refereed delegation) zijn vaak niet direct toepasbaar op het evalueren van de nauwkeurigheid van een model zonder kennis van het trainingsproces.

Dit paper introduceert een nieuw kader: Refereed Learning. Hierbij heeft de leerder (verifier) toegang tot twee concurrerende bewijzers (provers), waarvan er minstens één eerlijk is. De leerder moet beslissen welk van de twee modellen (hypotheses) de beste prestaties levert ten opzichte van een onbekende grondwaarheid, met minimale kosten en hoge nauwkeurigheid.

2. Methodologie en Kader

Het paper definieert een formeel kader voor refereed learning, gebaseerd op het concept van refereed delegation of computation (FST88, FK97), maar toegepast op het leren en testen van eigenschappen van black-box objecten.

De Set-up: Een leerder-verifier $V$ en twee bewijzers $P_0$ en $P_1$ . De leerder heeft toegang tot twee modellen $h_0, h_1$ en een grondwaarheidsfunctie $f$ (via queries of steekproeven). De bewijzers hebben mogelijk meer rekenkracht of toegang tot $f$ .
Het Doel: De leerder moet een bit $\rho \in \{0, 1\}$ outputen die het beste model selecteert. De prestatie wordt gemeten aan de hand van een verliesfunctie $L_D(f, h)$ .
Foutmarges: Protocollen worden gedefinieerd met multiplicatieve ( $\alpha$ ) en additieve ( $\eta$ ) foutmarges. Het doel is om een model te kiezen waarvan het verlies binnen een factor $\alpha$ en een optelling $\eta$ ligt van het verlies van het beste model.
Strategische Bewijzers: Het model veronderstelt dat minstens één bewijzer eerlijk is. Echter, door de concurrentie (een nul-sum spel) worden beide bewijzers gestimuleerd om eerlijk te zijn, zelfs als beide strategisch zijn, omdat de ene de inconsistenties van de andere kan onthullen.

3. Kerntechnieken

Om deze protocollen te bouwen, ontwikkelen de auteurs twee fundamentele hulpmiddelen:

Certifiable Sum (Gecertificeerde Som):
- Dit protocol stelt de leerder in staat om de som $S = \sum_{x} t(x)$ over een domein van grootte $2^d $te berekenen, gegeven alleen query-toegang tot$ t$.
- Mechanisme: Een bewijzer claimt een totale som en onderverdelingen voor twee helften van het domein. De andere bewijzer moet een helft identificeren waar de claim fout is. Dit proces is recursief (gedurende $d$ ronden) totdat er één punt overblijft. De leerder controleert dit punt met één query. Als een kwaadaardige bewijzer liegt, moet hij op minstens één niveau liegen, wat door de eerlijke bewijzer wordt ontdekt.
- Complexiteit: Polynomiële tijd en communicatie in $d$ .
Certifiable Sample (Gecertificeerde Steekproef):
- Hiermee kan de leerder efficiënt steekproeven trekken uit een willekeurige verdeling $D$ (zelfs als de steun van $D$ exponentieel groot en schaars is), zonder de verdeling volledig te hoeven doorlopen.
- Mechanisme: Gebaseerd op inverse CDF-steekproeven. De leerder kiest een willekeurige waarde $p \in [0, 1]$ . De bewijzers moeten het element $x$ vinden waarbij de cumulatieve kans tot $x$ net onder $p$ ligt. De leerder gebruikt Certifiable Sum om te verifiëren dat de bewijzers de juiste elementen hebben gevonden.
Refereed Query Delegation:
- Een techniek om de leerder in staat te stellen bijna alle queries naar de grondwaarheid $f$ uit te besteden aan de bewijzers. Als de bewijzers het niet eens zijn over een antwoord, doet de leerder zelf één query om de leugenaar te identificeren en gebruikt daarna alleen de antwoorden van de eerlijke bewijzer.

4. Belangrijkste Resultaten

Het paper presenteert protocollen voor verschillende foutscenario's:

A. Pure Multiplicatieve Fout (Hoog-precisie)

Dit is het meest opmerkelijke resultaat. De leerder kan het beste model kiezen met een verlies dat slechts een factor $(1+\epsilon)$ slechter is dan het beste model, zelfs als de verliesverschillen zeer klein zijn.

Resultaat (Theorema 4.2 & 4.4): Voor nul-één verlies (zero-one loss) en uniforme verdeling is er een protocol met een multiplicatieve factor $(1+\epsilon)$ . Voor algemene metrieken is de factor $(3+\epsilon)$ .
Efficiëntie:
- De leerder maakt slechts één query naar de grondwaarheid $f$ .
- Communicatie met de bewijzers is $(1 + 1/\epsilon^2) \cdot \text{poly}(d)$ bits.
- Dit is een enorme verbetering ten opzichte van eerdere methoden die $O(1/\eta^2)$ steekproeven nodig hadden.
Complexiteit Bewijzers: In het algemene geval vereisen de bewijzers exponentiële tijd ( $O(2^d)$ ) om de "disagreement set" (punten waar modellen verschillen) te vinden. Dit is echter noodzakelijk (zie onderstaande ondergrenzen).

B. Additieve en Gemengde Fout

Voor scenario's waar een kleine additieve fout $\eta$ acceptabel is:

Resultaat (Propositie 7.1 & 7.2): De leerder kan het beste model kiezen met additieve fout $\eta$ en multiplicatieve fout $1+\epsilon$.
Efficiëntie: De leerder maakt opnieuw slechts één query naar $f$ . De bewijzers hoeven minder queries te doen dan in eerdere werken (GRSY21), met name in de gemengde fout setting.

C. Specifiek Geval: Juntas

Voor het geval de modellen $k$ -juntas zijn (afhankelijk van slechts $k$ input bits):

Resultaat (Propositie 6.1): Als de actieve indexen bekend zijn, kunnen de bewijzers het protocol uitvoeren in polynoomtijd ( $\text{poly}(d)$ ). Dit toont aan dat refereed learning enorme rekenkracht kan besparen voor de leerder, zelfs als de bewijzers beperkt zijn, zolang het probleem een specifieke structuur heeft.

5. Ondergrenzen (Lower Bounds)

Het paper bewijst dat hun protocollen in meerdere opzichten optimaal zijn:

Noodzaak van Query-toegang: Zonder directe query-toegang tot $f$ (alleen via gelabelde steekproeven) of zonder kennis van de verdeling $D$ (via PMF queries), vereist elk protocol een aantal steekproeven van $\Omega(1/\eta)$ . Dit betekent dat de "één query" prestatie van hun protocollen niet kan worden behaald zonder deze toegang.
Exponentiële Tijd voor Bewijzers: Voor een algemeen protocol met pure multiplicatieve fout is exponentiële tijd voor de bewijzers noodzakelijk. Dit wordt bewezen door een reductie van het 3-SAT probleem. Als er een polynoomtijd refereed learning protocol zou bestaan voor pure multiplicatieve fout, zou dit betekenen dat 3-SAT in polynoomtijd opgelost kan worden (onder standaard complexiteitsaannames).

6. Betekenis en Impact

Doorbraak in Verificatie: Het paper toont aan dat het mogelijk is om de nauwkeurigheid van complexe, black-box modellen te verifiëren met een fractie van de kosten (in termen van grondwaarheid-queries) die normaal nodig zou zijn.
Concurrentie als Mechanisme: Het gebruik van twee concurrerende bewijzers (waarvan er één eerlijk is) blijkt een krachtig mechanisme om hoge nauwkeurigheid te garanderen zonder vertrouwen in de leveranciers.
Praktische Toepassingen: De resultaten zijn relevant voor domeinen waar grondwaarheid-evaluatie duur is (bijv. medische beeldvorming, natuurkunde, protein folding), waarbij het mogelijk wordt om modellen te vergelijken met slechts een handvol experimenten.
Theoretische Fundamenten: Het paper legt een brug tussen complexiteitstheorie (interactieve bewijzen) en machine learning, en definieert een nieuw subveld met strikte optimaliteitsresultaten.

Samenvattend introduceert "Refereed Learning" een krachtig paradigma waarbij een zwakke verifier, geholpen door concurrerende bewijzers, de prestaties van complexe modellen kan verifiëren met een efficiëntie die onmogelijk is in traditionele, single-prover of non-verifier settings.