📊 statistics

AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification

AdaPrivate-TS is een differentieel privaat contextual bandit-algoritme dat gebruikmaakt van de interpretatie van privacyruis als verhoogde onzekerheid binnen Thompson Sampling, waarbij het bijna optimale prestaties bereikt met logaritmische privacykosten door middel van gebatchte zCDP-compositie en privacy-amplificatie.

Oorspronkelijke auteurs: Mohammadreza Riyazat, Eranga Ukwatta

Gepubliceerd 2026-06-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mohammadreza Riyazat, Eranga Ukwatta

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een chef bent die probeert het perfecte recept te creëren voor een nieuw gerecht. Je hebt een lijst met ingrediënten (de "context"), en je moet beslissen welke combinatie je gaat koken (de "actie") om de beste smaak te krijgen (de "beloning"). Het probleem is dat je het exacte recept nog niet kent, dus moet je experimenteren. Dit is de wereld van Contextual Bandits, een chique term voor online aanbevelingssystemen (zoals Netflix die films suggereert of Spotify die nummers suggereert).

Maar er is een addertje onder het gras: om te leren waar mensen van houden, moet je hun privédata zien (wat ze hebben aangeklikt, beoordeeld of gekocht). Gebruikers willen niet dat hun geheimen worden verklapt. Dit is waar Differential Privacy (DP) om de hoek komt kijken—het is als het toevoegen van een laag "mist" of "ruis" aan de data, zodat niemand precies kan zien wat één specifiek persoon heeft gedaan, terwijl de chef nog steeds de algemene trends kan leren begrijpen.

Het probleem met de meeste bestaande methoden is dat deze "mist" meestal het leerproces verpest. Het is alsof je probeert een soep te proeven terwijl je dikke handschoenen draagt; je kunt de smaken niet goed voelen, waardoor je slechte gissingen doet.

Het Grote Idee: Mist Veranderen in een Kenmerk

De auteurs van dit artikel, Mohammadreza Riyazat en Eranga Ukwatta, hebben een slim nieuw algoritme bedacht genaamd AdaPrivate-TS. Hun geheime ingrediënt is een verschuiving in perspectief.

De meeste algoritmen behandelen de privacy "mist" als corruptie—een fout die hun data verpest. Ze proberen ertegen te vechten of het te negeren, wat leidt tot slechte prestaties.

De auteurs realiseerden zich dat hun specifieke methode, genaamd Thompson Sampling, de mist niet ziet als een fout. In plaats daarvan ziet het de mist als onzekerheid.

De Analogie:
Stel je voor dat je een detective bent die een mysterie oplost.

De Oude Manier (UCB): Je hebt een lijst met verdachten. Als het bewijsmateriaal wazig is (privacy-ruis), raak je in de war en doe je een rigide, voorzichtige gok. Je zou de echte dader kunnen missen omdat je te bang bent om een foute gok te wagen.
De Nieuwe Manier (AdaPrivate-TS): Je bent een detective die van gokken houdt. Wanneer het bewijsmateriaal wazig is, denk je: "Ah, dit is een lastige zaak! Ik weet niet wie het gedaan heeft, dus ik moet meer mogelijkheden verkennen." De "mist" maakt je juist nieuwsgieriger en bereid om meer verschillende verdachten te proberen.

In technische termen vergroot de privacy-ruis de "onzekerheid" van het algoritme. In plaats van het systeem te breken, vertelt deze extra onzekerheid het algoritme: "Hé, wees avontuurlijker!" Dit verandert een zwakte (privacy-ruis) in een kracht (betere exploratie).

Hoe Ze Het Deden: De "Batch"-Truc

Om dit efficiënt te laten werken, gebruikten ze een techniek genaamd Batching.
In plaats van na elke interactie van een gebruiker privacy-ruis toe te voegen (wat erg duur en traag zou zijn), wachtten ze tot ze een kleine groep interacties hadden (een "batch") en voegden ze de ruis slechts één keer toe voor de hele groep.

De Analogie:
Stel je voor dat je brieven naar een vriend stuurt.

De Oude Manier: Je schrijft een brief, doet hem in een speciale privacy-envelop, en verstuurt hem onmiddellijk. Daarna schrijf je een andere, doet hem in een envelop, en verstuurt hem. Dit is traag en verbruikt veel enveloppen.
De Nieuwe Manier: Je schrijft 30 brieven, doet ze allemaal in één grote doos, en voegt één privacy-zegel toe aan de hele doos. Je verstuurt de doos één keer.
Dit "batching"-proces stelt hen in staat om de kosten van privacy over veel interacties te spreiden, waardoor het systeem veel sneller en nauwkeuriger wordt.

De "Subsampling" Boost

Ze ontdekten ook een manier om de privacy nog sterker te maken zonder aan nauwkeurigheid in te boeten, genaamd Privacy Amplification.
De Analogie: Stel je voor dat je een peiling doet. In plaats van iedereen in een menigte te vragen, vraag je willekeurig een paar mensen (bijvoorbeeld 30% van de menigte). Omdat je alleen naar een willekeurige doorsnede kijkt, is het eigenlijk moeilijker voor iemand om te achterhalen wat elk specifiek individu heeft gezegd. Dit stelt hen in staat om minder "mist" (ruis) te gebruiken terwijl ze hetzelfde niveau van privacybescherming behouden.

Wat Ze Vonden

Ze hebben hun nieuwe chef (AdaPrivate-TS) getest tegen de oude chefs (andere algoritmen) op twee manieren:

Nepdata (Synthetisch): Ze creëerden een computersimulatie van 10.000 interacties.
Echte Data: Ze gebruikten echte datasets zoals MovieLens (filmbeoordelingen) en Jester (grapbeoordelingen).

De Resultaten:

Betere Prestaties: Zelfs met strikte privacyregels bereikte hun algoritme 93% tot 99% van de prestaties van een systeem zonder enige privacy.
De Concurrentie Verslaan: Het presteerde consequent beter dan de vorige beste methoden (zoals UCB) met een kleine maar significante marge van 0,5% tot 3,7%, en soms met een enorme marge (tot 18%) wanneer de privacyregels zeer strikt waren.
Stabiliteit: Wanneer de privacy-ruis het systeem raakte, struikelden de oude algoritmen en daalde hun prestaties. Het nieuwe algoritme bleef echter gestaag klimmen, wat bewees dat het behandelen van ruis als "onzekerheid" het systeem stabieler maakt.
Private Kenmerken: Zelfs toen de kenmerken (zoals de beschrijving van een film) ook privacy-beschermd waren, won hun algoritme nog steeds, wat aantoont dat dit "ruis-als-onzekerheid"-idee werkt in veel verschillende scenario's.

De Kern van het Verhaal

Het artikel stelt dat door de manier waarop we over privacy-ruis denken te veranderen—het niet langer als een bug te zien, maar als een kenmerk dat exploratie stimuleert—we aanbevelingssystemen kunnen bouwen die de privacy van de gebruiker respecteren zonder in te leveren op de kwaliteit van de aanbevelingen. Het is als leren dansen in de regen in plaats van proberen de regen te stoppen.

Technische Samenvatting: AdaPrivate-TS

Probleemstelling

Online aanbevelingssystemen staan voor een fundamentele spanning tussen het leren van gebruikersvoorkeuren uit private gedragsgegevens en het bieden van strikte privacygaranties. Hoewel Differential Privacy (DP) sterke bescherming biedt, introduceert het doorgaans ruis die de leerprestaties verslechtert. Bestaande private contextual bandit-algoritmen behandelen DP-ruis vaak als pure corruptie, wat leidt tot aanzienlijke regret (spijt). Bovsamen zijn veel benaderingen afhankelijk van joint DP (het beschermen van de volledige actiesequentie) of sequentiële compositie, wat resulteert in hoge privacykosten (bijv. $O(T^{3/4})$ regret) of een vertrouwde centrale curator vereist.

Dit artikel adresseert de uitdaging van het ontwerpen van een differentieel privaat contextual bandit-algoritme dat opereert onder event-level DP (het beschermen van individuele gebruiker-beloningsparen) met stochastische contexten, met als doel de regret te minimaliseren terwijl een strikte privacy wordt gehandhaafd zonder een vertrouwde centrale entiteit.

Methodologie: AdaPrivate-TS

De auteurs stellen AdaPrivate-TS voor, een nieuw algoritme dat Thompson Sampling (TS) integreert met gebatchte zero-concentrated Differential Privacy (zCDP).

Kerninzicht: Ruis als Onzekerheid

De centrale theoretische bijdrage is de observatie dat DP-ruis, wanneer toegevoegd aan de voldoende statistieken van een lineaire bandit, de schatting niet alleen corrumpeert, maar de posterior covariantie structureel opblaast.

In standaard Thompson Sampling is de posterior distributie $\theta | H_t \sim \mathcal{N}(\hat{\theta}_t, v^2 A_t^{-1})$ .
Wanneer Gaussische ruis $\eta \sim \mathcal{N}(0, \sigma^2 I)$ wordt toegevoegd aan de voldoende statistiek $b_t$ voor privacy, wordt de resulterende sampling-distributie:
$\tilde{\theta}_t \sim \mathcal{N}\left(\hat{\theta}_t, v^2 A_t^{-1} + \sigma^2 A_t^{-2}\right)$
In tegen tegenstelling tot Upper Confidence Bound (UCB) methoden, die deze ruis als fout behandelen, interpreteert Thompson Sampling deze opgeblazen covariantie ( $v^2 A_t^{-1} + \sigma^2 A_t^{-2}$ ) op natuurlijke wijze als toegenomen onzekerheid. Dit stimuleert het algoritme om meer te exploreren in richtingen waar de privacyruis dominant is, waardoor de "corruptie" effectief wordt omgezet in een gunstig exploratiesignaal.

Algoritmische Componenten

Gebatchte zCDP Compositie: Het algoritme verwerkt interacties in batches. Het geeft ruizige voldoende statistieken (specifiek de vector $b$ ) vrij aan het einde van elke batch. Door parallelle compositie te gebruiken, wordt de totale privacykost bepaald door de maximale kost van een enkele batch ( $\max_k \rho_k = \rho$ ) in plaats van de som van de kosten, waardoor de privacykost logaritmisch in $T$ kan blijven.
Privacy Amplificatie: Om de ruis verder te verminderen bij strikte privacybudgetten ( $\epsilon \leq 1$ ), gebruiken de auteurs Poisson-subsampling. Door elke beloning met een waarschijnlijkheid $q$ in de batchsom op te nemen, wordt de effectieve privacykost met een factor ongeveer $2q^2$ verminderd zonder de sensitiviteit te herschalen, waarbij gebruik wordt gemaakt van Rényi Differential Privacy (RDP) analyse.
Adaptieve Exploratie: Het algoritme laat de exploratieparameter $v_k$ over de tijd afnemen ( $v_k = v_0 \cdot \gamma^{k-1}$ ) om agressieve vroege exploratie te balanceren met verfijnde exploitatie naarmate het model convergeert.

Privacy Model

Het algoritme voldoet aan event-level DP, waarbij aangrenzende datasets verschillen in exact één gebruiker-beloningspaar $(u_t, r_t)$ . Acties worden behandeld als algoritme-outputs, niet als private inputs. Het mechanisme gebruikt zCDP voor nauwere compositiebounds, wat wordt omgezet naar $(\epsilon, \delta)$ -DP via standaard conversieformules.

Belangrijkste Bijdragen

Private Thompson Sampling: Het artikel bewijst dat het toevoegen van DP-ruis aan de voldoende statistieken resulteert in een specifieke posterior covariantie-inflatie ( $v^2 A^{-1} + \sigma^2 A^{-2}$ ). Dit stelt TS in staat de ruis te interpreteren als onzekerheid in plaats van corruptie.
Strakke Regret Bound: Onder event-level DP met stochastische contexten bewijzen de auteurs een regret bound waarbij de privacykost $O(\sqrt{d} \cdot \log T / \sqrt{\rho})$ is. Dit is logaritmisch in $T$ , een significante verbetering ten opzichte van de $O(\sqrt{T})$ of $O(T^{3/4})$ kosten die geassocieerd worden met sequentiële compositie of joint DP.
Privacy Amplificatie Analyse: Een rigoureuze RDP-gebaseerde analyse van Poisson-subsampling voor bandits wordt geleverd, die winsten van 2–4% aantoont bij lage $\epsilon$ -waarden.
Uitgebreide Evaluatie: Uitgebreide experimenten op synthetische en real-world datasets (MovieLens-25M, Jester) valideren de theoretische claims.

Experimentele Resultaten

Prestaties vs. Niet-Privaat: AdaPrivate-TS bereikt 93–99% van de prestaties van niet-private Thompson Sampling over privacybudgetten $\epsilon \in [0, 5]$ .
Vergelijking met UCB: Het algoritme presteert gemiddeld 0,5–3,7% beter dan private UCB-baselines. Met getunede adaptieve exploratie groeit het voordeel naar tot 18% bij extreme privacy-instellingen.
Real-World Data: Op de MovieLens en Jester datasets behaalt AdaPrivate-TS de beste algehele prestaties onder de event-level baselines, vooral dominant bij $\epsilon \geq 2$ .
Feature Privacy: Wanneer features geprivatiseerd worden met behulp van DP-SVD, neemt het voordeel van TS ten opzichte van UCB toe tot +11%, wat bevestigt dat het "noise-as-uncertainty" mechanisme zich uitstrekt van reward-privacy naar feature-privacy.
Ablatie: Componentanalyse laat zien dat de combinatie van TS, privacy-amplificatie en adaptieve exploratie een cumulatieve winst oplevert van +6,3% ten opzichte van een baseline private UCB met ruis.

Betekenis en Claims

Het artikel claimt dat Thompson Sampling inherent beter geschikt is dan UCB voor private contextual bandits, omdat het de structurele eigenschappen van DP-ruis kan benutten als een bron van exploratie in plaats van een bron van fouten.

Belangrijke claims met betrekking tot de betekenis zijn:

Efficiëntie: Het gebruik van parallelle compositie met gebatchte verwerking maakt een privacykost mogelijk die logaritmisch is in de tijdhorizon $T$ , waardoor de zware straffen van sequentiële compositie worden vermeden.
Praktische Bruikbaarheid: Het algoritme opereert zonder een vertrouwde centrale curator, en vertrouwt enkel op event-level privacy, wat passend is voor scenario's waarin gebruikers slechts enkele interacties bijdragen.
Robuustheid: De methode blijft stabiel onder private features (DP-SVD) en biedt een principiële manier om privacybudgetten aan te scherpen via Poisson-subsampling zonder de kwaliteit van aanbevelingen op te offeren.
Theoretische Vernieuwing: De identificatie van ruis-geïnduceerde covariantie-inflatie als een mechanisme voor "noise-as-uncertainty" biedt een nieuw perspectief op het ontwerpen van private leeralgoritmen, waarmee men verder gaat dan het paradigma van het behandelen van privacy-ruis louter als corruptie.

De auteurs concluderen dat AdaPrivate-TS een principieel instrument biedt voor praktijkgebruikers die een balans moeten vinden tussen strikte privacyvereisten en hoge kwaliteit van aanbevelingsprestaties, met name in scenario's met stochastische contexten en event-level privacybeperkingen.