📊 statistics

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

AdaPrivate-TS ist ein differenziell privater kontextueller Bandit-Algorithmus, der die Interpretation von Privatsheitsrauschen als erhöhte Unsicherheit innerhalb des Thompson-Sampling nutzt und durch gebatchte zCDP-Komposition sowie Privacy Amplification eine nahezu optimale Performance mit logarithmischen Privatsheitskosten erreicht.

Ursprüngliche Autoren: Mohammadreza Riyazat, Eranga Ukwatta

Veröffentlicht 2026-06-23

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mohammadreza Riyazat, Eranga Ukwatta

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Koch, der versucht, das perfekte Rezept für ein neues Gericht zu kreieren. Sie haben eine Liste von Zutaten (den „Kontext“) und müssen entscheiden, welche Kombination Sie kochen (die „Aktion“), um den besten Geschmack (die „Belohnung“) zu erzielen. Das Problem ist, dass Sie das exakte Rezept noch nicht kennen, also müssen Sie experimentieren. Das ist die Welt der Contextual Bandits, ein schicker Begriff für Online-Empfehlungssysteme (wie Netflix, das Filme vorschlägt, oder Spotify, das Songs empfiehlt).

Es gibt jedoch einen Haken: Um zu lernen, was Menschen mögen, müssen sie deren private Daten sehen (was sie angeklickt, bewertet oder gekauft haben). Nutzer möchten jedoch nicht, dass ihre Geheimnisse verraten werden. Hier kommt Differential Privacy (DP) ins Spiel – es ist wie das Hinzuffügen einer Schicht aus „Nebel“ oder „Rauschen“ zu den Daten, sodass niemand genau sagen kann, was eine einzelne Person getan hat, während der Koch dennoch die allgemeinen Trends lernen kann.

Das Problem mit den meisten bestehenden Methoden ist, dass dieser „Nebel“ normalerweise den Lernprozess ruiniert. Es ist, als würde man versuchen, eine Suppe zu schmecken, während man dicke Handschuhe trägt; man kann die Aromen nicht gut spüren, also macht man schlechte Vermutungen.

Die große Idee: Den Nebel in ein Merkmal verwandeln

Die Autoren dieser Arbeit, Mohammadreza Riyazat und Eranga Ukwatta, haben einen cleveren neuen Algorithmus namens AdaPrivate-TS entwickelt. Ihr Geheimrezept ist ein Perspektivwechsel.

Die meisten Algorithmen behandeln den Privatsphäre-„Nebel“ als Korruption – einen Fehler, der ihre Daten ruiniert. Sie versuchen, dagegen anzukämpfen oder ihn zu ignorieren, was zu einer schlechten Leistung führt.

Die Autoren erkannten, dass ihre spezifische Methode, genannt Thompson Sampling, den Nebel nicht als Fehler sieht. Stattdessen sieht sie den Nebel als Unsicherheit.

Die Analogie:
Stellen Sie sich vor, Sie sind ein Detektiv, der ein Rätsel löst.

Der alte Weg (UCB): Sie haben eine Liste von Verdächtigen. Wenn die Beweise verschwommen sind (Privatsphäre-Rauschen), werden Sie verwirrt und machen eine starre, vorsichtige Vermutung. Sie könnten den wahren Täter verpassen, weil Sie zu viel Angst haben, eine falsche Vermutung anzustellen.
Der neue Weg (AdaPrivate-TS): Sie sind ein Detektiv, der gerne rät. Wenn die Beweise verschwommen sind, denken Sie: „Ah, das ist ein kniffliger Fall! Ich bin mir nicht sicher, wer es war, also sollte ich mehr Möglichkeiten erforschen.“ Der „Nebel“ macht Sie tatsächlich neugieriger und bereit, mehr Möglichkeiten auszuprobieren.

In technischen Begriffen erhöht das Privatsphäre-Rauschen die „Unsicherheit“ des Algorithmus. Anstatt das System zu brechen, sagt dieser zusätzliche Nebel dem Algorithmus: „Hey, sei abenteuerlustiger!“ Dies verwandelt eine Schwäche (Privatsphäre-Rauschen) in eine Stärke (bessere Exploration).

Wie sie es geschafft haben: Der „Batch“-Trick

Um dies effizient umzusetzen, verwendeten sie eine Technik namens Batching.
Anstatt nach jeder einzelnen Benutzerinteraktion Privatsphäre-Rauschen hinzuzufügen (was sehr teuer und langsam wäre), warteten sie, bis sie eine kleine Gruppe von Interaktionen (einen „Batch“) gesammelt hatten, und fügten das Rauschen dann nur einmal für die gesamte Gruppe hinzu.

Die Analogie:
Stellen Sie sich vor, Sie schreiben Briefe an einen Freund.

Der alte Weg: Sie schreiben einen Brief, legen ihn in einen speziellen Privatsphäre-Umschlag und schicken ihn sofort ab. Dann schreiben Sie den nächsten, verpacken ihn in einen Umschlag und schicken ihn ab. Das ist langsam und verbraucht viele Umschläge.
Der neue Weg: Sie schreiben 30 Briefe, legen sie alle in einen großen Karton und bringen einen Privatsphäre-Siegel für den gesamten Karton an. Sie verschicken den Karton einmal.
Dieses „Batching“ ermöglicht es ihnen, die Kosten der Privatsphäre über viele Interaktionen zu verteilen, was das System viel schneller und genauer macht.

Der „Subsampling“-Boost

Sie fanden auch einen Weg, die Privatsphäre noch stärker zu machen, ohne an Genauigkeit zu verlieren, genannt Privacy Amplification.
Die Analogie: Stellen Sie sich vor, Sie führen eine Umfrage durch. Anstatt jeden in einer Menge zu fragen, fragen Sie zufällig ein paar Leute (sagen wir 30 % der Menge). Da Sie nur einen zufälligen Ausschnitt betrachten, ist es tatsächlich schwieriger für jemanden, herauszufinden, was eine spezifische Einzelperson gesagt hat. Dies ermöglicht es ihnen, weniger „Nebel“ (Rauschen) zu verwenden, während sie das gleiche Niveau an Privatsphärenschutz beibehalten.

Was sie herausfanden

Sie testeten ihren neuen Chef (AdaPrivate-TS) gegen die alten Köche (andere Algorithmen) auf zwei Arten:

Fiktive Daten (Synthetisch): Sie erstellten eine Computersimulation von 10.000 Interaktionen.
Reale Daten: Sie verwendeten reale Datensätze wie MovieLens (Filmbewertungen) und Jester (Witz-Bewertungen).

Die Ergebnisse:

Bessere Leistung: Selbst unter strengen Privatsphäre-Regeln erreichte ihr Algorithmus 93 % bis 99 % der Leistung eines Systems ohne jegliche Privatsphäre.
Die Konkurrenz schlagen: Er übertraf konsequent die bisherigen besten Methoden (wie UCB) um einen kleinen, aber signifikanten Abstand von 0,5 % bis 3,7 % und manchmal sogar um eine enorme Spanne (bis zu 18 %), wenn die Privatsphäre-Regeln sehr streng waren.
Stabilität: Wenn das Privatsphäre-Rauschen das System traf, gerieten die alten Algorithmen ins Straucheln und brachen in der Leistung ein. Der neue Algorithmus stieg einfach stetig weiter an, was beweist, dass die Behandlung von Rauschen als „Unsicherheit“ das System stabiler macht.
Private Merkmale: Selbst als auch die Merkmale (wie die Beschreibung eines Films) privatsphäregeschützt waren, gewann ihr Algorithmus immer noch, was zeigt, dass diese „Rauschen-als-Unsicherheit“-Idee in vielen verschiedenen Szenarien funktioniert.

Das Fazbeispiel

Das Paper behauptet, dass wir durch die Änderung der Art und Weise, wie wir Privatsphäre-Rauschen betrachten – nämlich nicht als Bug, sondern als Feature, das die Exploration fördert – Empfehlungssysteme bauen können, die die Privatsphäre der Nutzer respektieren, ohne die Qualität der Empfehlungen zu opfern. Es ist, als würde man lernen, im Regen zu tanzen, anstatt zu versuchen, den Regen zu stoppen.

Technisches Resümee: AdaPrivate-TS

Problemstellung

Online-Empfehlungssysteme stehen vor einem grundlegenden Spannungsfeld zwischen dem Lernen von Nutzerpräferenzen aus privaten Verhaltensdaten und der Bereitstellung strenger Privatsheitsgarantien. Während Differential Privacy (DP) einen starken Schutz bietet, führt sie typischerweise Rauschen ein, das die Lernleistung verschlechtert. Bestehende Algorithmen für private kontextuelle Banditen behandeln DP-Rauschen oft als reine Korruption, was zu signifikantem Regret (Reue) führt. Darüber hinaus verlassen sich viele Ansätze auf Joint DP (Schutz der gesamten Aktionssequenz) oder sequentielle Komposition, was zu hohen Privatsheitskosten (z. B. $O(T^{3/4})$ Regret) führt oder einen vertrauenswürdigen zentralen Kurator erfordert.

Dieses Paper adressiert die Herausforderung, einen differenziell privaten kontextuellen Bandit-Algorithmus zu entwickeln, der unter Event-Level DP (Schutz einzelner Nutzer-Belohnungs-Paare) mit stochastischen Kontexten operiert, mit dem Ziel, den Regret zu minimieren und gleichzeitig eine rigorose Privatschaft ohne eine zentrale vertrauenswürdige Instanz zu gewährleisten.

Methodik: AdaPrivate-TS

Die Autoren schlagen AdaPrivate-TS vor, einen neuartigen Algorithmus, der Thompson Sampling (TS) mit batched zero-concentrated Differential Privacy (zCDP) integriert.

Kern-Erkenntnis: Rauschen als Unsicherheit

Der zentrale theoretische Beitrag ist die Beobachtung, dass DP-Rauschen, wenn es zu den hinreichenden Statistiken eines linearen Bandits hinzugefügt wird, die Schätzung nicht bloß korrumpiert, sondern die Posterior-Kovarianz strukturell aufbläht.

In Standard-Thompson-Sampling ist die Posterior-Verteilung $\theta | H_t \sim \mathcal{N}(\hat{\theta}_t, v^2 A_t^{-1})$ .
Wenn Gaußsches Rauschen $\eta \sim \mathcal{N}(0, \sigma^2 I)$ zur hinreichenden Statistik $b_t$ für die Privatschaft hinzugefügt wird, wird die resultierende Sampling-Verteilung zu:
$\tilde{\theta}_t \sim \mathcal{N}\left(\hat{\theta}_t, v^2 A_t^{-1} + \sigma^2 A_t^{-2}\right)$
Im Gegensatz zu Upper Confidence Bound (UCB)-Methoden, die dieses Rauschen als Fehler behandeln, interpretiert Thompson Sampling die aufgeblähte Kovarianz ( $v^2 A_t^{-1} + \sigma^2 A_t^{-2}$ ) natürlich als erhöhte Unsicherheit. Dies veranlasst den Algorithmus dazu, verstärkt in Richtungen zu explorieren, in denen das Privatschaftsrauschen dominiert, wodurch die "Korruption" effektiv in ein nützliches Explorationssignal umgewandelt wird.

Algorithmische Komponenten

Batched zCDP Composition: Der Algorithmus verarbeitet Interaktionen in Batches. Er gibt verrauschte hinreichende Statistiken (speziell den Vektor $b$ ) am Ende jedes Batches frei. Durch die Verwendung von paralleler Komposition wird die gesamte Privatschaftskosten durch die maximale Kosten eines einzelnen Batches ( $\max_k \rho_k = \rho$ ) bestimmt, anstatt durch die Summe der Kosten, wodurch die Privatschaftskosten logarithmisch in $T$ bleiben können.
Privatschaftsverstärkung (Privacy Amplification): Um das Rauschen bei strengen Privatschaftsbudgets ( $\epsilon \leq 1$ ) weiter zu reduzieren, verwenden die Autoren Poisson-Subsampling. Indem jede Belohnung mit einer Wahrscheinlichkeit $q$ in die Batch-Summe einbezogen wird, wird die effektive Privatschaftskosten um einen Faktor von etwa $2q^2$ reduziert, ohne die Sensitivität neu zu skalieren, wobei Rényi Differential Privacy (RDP)-Analysen genutzt werden.
Adaptive Exploration: Der Algorithmus lässt den Explorationsparameter $v_k$ über die Zeit abfallen ( $v_k = v_0 \cdot \gamma^{k-1}$ ), um eine aggressive frühe Exploration mit einer verfeinerten Exploitation zu balancieren, während sich das Modell konvergiert.

Privatschaftsmodell

Der Algorithmus erfüllt Event-Level DP, wobei benachbarte Datensätze sich in genau einem Nutzer-Belohnungs-Paar $(u_t, r_t)$ unterscheiden. Aktionen werden als Algorithmus-Outputs behandelt, nicht als private Inputs. Der Mechanismus nutzt zCDP für engere Kompositionsgrenzen und konvertiert dies über Standard-Konvertierungsformeln in $(\epsilon, \delta)$ -DP.

Zentrale Beiträge

Privates Thompson Sampling: Das Paper beweist, dass das Hinzufügen von DP-Rauschen zu den hinreichenden Statistiken zu einer spezifischen Inflation der Posterior-Kovarianz ( $v^2 A^{-1} + \sigma^2 A^{-2}$ ) führt. Dies ermöglicht es TS, das Rauschen als Unsicherheit statt als Korruption zu interpretieren.
Enger Regret-Bound: Unter Event-Level DP mit stochastischen Kontexten beweisen die Autoren eine Regret-Schranke, bei der die Privatschaftskosten $O(\sqrt{d} \cdot \log T / \sqrt{\rho})$ betragen. Dies ist logarithmisch in $T$ , was eine signifikante Verbesserung gegenüber den $O(\sqrt{T})$ oder $O(T^{3/4})$ Kosten darstellt, die mit sequentieller Komposition oder Joint DP assoziiert sind.
Analyse der Privatschaftsverstärkung: Eine rigorose RDP-basierte Analyse des Poisson-Subsamplings für Banditen wird bereitgestellt, die Gewinne von 2–4 % bei niedrigen $\epsilon$ -Werten aufzeigt.
Umfassende Evaluierung: Umfangreiche Experimente auf synthetischen und realen Datensätzen (MovieLens-25M, Jester) validieren die theoretischen Ansprüche.

Experimentelle Ergebnisse

Performance vs. Nicht-Privat: AdaPrivate-TS erreicht 93–99 % der Performance von nicht-privatem Thompson Sampling über Privatschaftsbudgets von $\epsilon \in [0.5, 5]$ .
Vergleich mit UCB: Der Algorithmus übertrifft private UCB-Baselines im Durchschnitt um 0,5–3,7 %. Mit adaptiver Exploration steigt der Vorteil bei extremen Privatschaftseinstellungen auf bis zu 18 %.
Reale Daten: Auf den Datensätzen MovieLens und Jester erzielt AdaPrivate-TS die beste Gesamtperformance unter den Event-Level-Baselines, insbesondere bei $\epsilon \geq 2$ .
Feature-Privatschaft: Wenn Features mittels DP-SVD privatisiert werden, steigt der Vorteil von TS gegenüber UCB auf +11 %, was bestätigt, dass der "Rauschen-als-Unsicherheit"-Mechanismus über die Reward-Privatschaft hinaus auch auf die Feature-Privatschaft anwendbar ist.
Ablation: Die Komponentenanalyse zeigt, dass die Kombination aus TS, Privatschaftsverstärkung und adaptiver Exploration einen kumulativen Gewinn von +6,3 % gegenüber einem Baseline-privaten UCB mit Rauschen liefert.

Bedeutung und Behauptungen

Das Paper behauptet, dass Thompson Sampling inhärent besser für private kontextuelle Banditen geeignet ist als UCB, da es die strukturellen Eigenschaften von DP-Rauschen als Quelle der Exploration statt als Quelle des Fehlers nutzen kann.

Zentrale Behauptungen zur Bedeutung sind:

Effizienz: Die Verwendung von paralleler Komposition mit Batch-Verarbeitung ermöglicht eine Privatschaftskosten, die logarithmisch in den Zeithorizont $T$ ist, wodurch die schweren Strafen der sequentiellen Komposition vermieden werden.
Praktikabilität: Der Algorithmus operiert ohne einen vertrauenswürdigen zentralen Kurator und stützt sich lediglich auf Event-Level-Privatschaft, was für Szenarien angemessen ist, in denen Nutzer nur wenige Interaktionen beisteuern.
Robustheit: Die Methode bleibt unter privaten Features (DP-SVD) stabil und bietet einen prinzipiierten Weg, die Privatschaftsbudgets mittels Poisson-Subsampling zu straffen, ohne die Qualität der Empfehlungen zu opfern.
Theoretische Neuheit: Die Identifizierung der durch Rauschen induzierten Kovarianz-Inflation als Mechanismus für "Rauschen-als-Unsicherheit" bietet eine neue Perspektive für das Design privater Lernalgorithmen und bewegt sich über das Paradigma hinaus, DP-Rauschen lediglich als Korruption zu behandeln.

Die Autoren kommen zu dem Schluss, dass AdaPrivate-TS ein fundiertes Werkzeug für Praktiker bietet, die eine Balance zwischen strengen Privatschaftsanforderungen und hoher Qualität der Empfehlungsleistung benötigen, insbesondere in Szenarien mit stochastischen Kontexten und Event-Level-Privatschaftsbeschränkungen.