Technische Zusammenfassung: Moduliertes Lernen für private und verteilte Regression mit einem Sample pro Client

Problemstellung

Diese Arbeit adressiert eine kritische Einschränkung in den Standard-Paradigmen des Federated Learning (FL) und des Differenziell Privaten (DP) Lernens: die Annahme, dass Client-Geräte über lokale Datensätze verfügen, die groß genug sind, um aussagekräftige Gradienten-Updates zu berechnen. In vielen realen Szenarien – wie Fitness-Trackern, am Körper getragenen Sensoren und täglichen Ereignismonitoren – verfügen Clients möglicherweise nur über ein einziges Datensample (oder sehr wenige).

In diesem Regime „ein Sample pro Client" scheitert das standardmäßige DP-SGD-basierte FL, weil:

1. Unzuverlässige lokale Updates: Ein auf einem einzelnen Punkt berechneter lokaler Gradient ist stark verrauscht und unzuverlässig für die Schätzung von Modellkoeffizienten, insbesondere in frühen Trainingsrunden.
2. Verstärkung des Privatsphären-Rauschens: Das zur Einhaltung der Differenziellen Privatsphäre eingebrachte Rauschen verschlechtert die Nutzbarkeit dieser ohnehin schwachen lokalen Updates weiter und macht die Konvergenz des globalen Modells unwirksam.

Die Arbeit fragt: Können wir nützliches, differenziell privates verteiltes Lernen ermöglichen, wenn jeder Client nur einen einzigen Datenpunkt beiträgt?

Methodik

Die Autoren schlagen ein Framework für Moduliertes Lernen vor. Anstatt dass Clients Modellkoeffizienten (wie im Standard-FL) oder Rohgradienten senden, übertragen Clients eine privat transformierte Repräsentation ihres einzelnen Datensamples. Der Server aggregiert diese Repräsentationen, um eine unverzerrte Schätzung des zentralisierten Gradienten zu erhalten.

Kernmechanismus: Kosinus-modulierte Transformation

Das Protokoll arbeitet in Runden. In jeder Runde $t$ hält der Server ein globales Modell $\beta_t$ vor und wählt eine Modulationsrichtung $v_t$ (orthogonal zu $\beta_t$).

1. Client-seitige Verarbeitung:
Gegeben ein privates Sample $(x_i, y_i)$ führt der Client folgende Schritte aus:

• Modulation: Der Client sampelt eine zufällige Phase $\phi_i \sim \text{Unif}[0, 2\pi]$ und berechnet einen modulierten Merkmalsvektor:
  $$g_i = (1 - \alpha)x_i + \lambda \cos(\omega \langle x_i, v_t \rangle + \phi_i) v_t$$
  Hier sind $\alpha, \lambda, \omega$ Hyperparameter. Der Term $(1-\alpha)x_i$ bewahrt das Signal, während der Kosinus-Term eine kontraktive, privatsphäreschützende Perturbation einführt.
• Rauscheinbringung: Um $(\epsilon, \delta)$-lokale Differenzielle Privatsphäre (LDP) zu gewährleisten, fügt der Client Gaußsches Rauschen $\xi_i \sim \mathcal{N}(0, \sigma_{DP}^2 I)$ hinzu:
  $$\tilde{g}_i = g_i + \xi_i$$
• Übertragung: Der Client sendet das Paar $(\tilde{g}_i, y_i)$ an den Server. Beachten Sie, dass $y_i$ in diesem spezifischen Setup als öffentlich/nicht-sensibel behandelt wird, während $x_i$ der private Input ist.

2. Server-seitige Aggregation und Entzerrung:
Der Server empfängt $\{(\tilde{g}_i, y_i)\}_{i=1}^K$ und führt algebraische Korrekturen durch, um die durch Modulation und Rauschen eingeführte Verzerrung zu entfernen:

• Kovarianzschätzung: Der Server berechnet die empirische Kovarianz der empfangenen Merkmale und subtrahiert die bekannten Verzerrungsterme (die Modulationsvarianz und die Rauschvarianz):
  $$\hat{\Sigma}_x = \frac{1}{(1-\alpha)^2} \left( \frac{1}{K}\sum \tilde{g}_i \tilde{g}_i^\top - \frac{\lambda^2}{2} v_t v_t^\top - \sigma_{DP}^2 I \right)$$
  Satz 3.1 und Korollar 3.2 beweisen, dass $\hat{\Sigma}_x$ ein unverzerrter Schätzer für die wahre Datenkovarianz $\Sigma_x = \frac{1}{K}\sum x_i x_i^\top$ ist.
• Gradientenwiederherstellung: Der Server konstruiert einen unverzerrten Gradientenschätzer $G$:
  $$G = \hat{\Sigma}_x \beta_t - \frac{1}{1-\alpha} \frac{1}{K} \sum y_i \tilde{g}_i$$
  Dieser $G$ erfüllt $\mathbb{E}[G] = \nabla L(\beta_t)$ und entspricht im Erwartungswert dem nicht-privaten zentralisierten Gradienten.

Varianten

• Multi-Vektor-Modulation: Um die Lipschitz-Konstante (und damit das erforderliche Rauschen $\sigma_{DP}$) zu reduzieren, verallgemeinern die Autoren die Methode auf die Verwendung von $m$ orthonormalen Vektoren. Dies reduziert die Sensitivitätsschranke von $|1-\alpha| + \lambda\omega$ auf $|1-\alpha| + \frac{\lambda\omega}{\sqrt{m}}$.
• Nicht-iterativer (One-Shot) Schätzer: Die Arbeit leitet zudem einen geschlossenen Momentenschätzer ab, der $\beta$ in einem einzigen Schritt löst und die Kosten der Privatsphären-Komposition iterativer Methoden vermeidet.

Hauptbeiträge

1. Unverzerrte Gradientenschätzung aus einzelnen Samples: Die Arbeit zeigt, dass durch Transformation der Daten über eine spezifische kosinus-modulierte Abbildung und Anwendung einer nachgelagerten Entzerrung ein Server eine unverzerrte Gradientenschätzung auch dann wiederherstellen kann, wenn Clients nur jeweils ein Sample besitzen.
2. Optimierung des Trade-offs zwischen Privatsphäre und Nutzen:
   • Die Methode etabliert eine Cramér-Rao-Untergrenze für den Rekonstruktionsfehler und beweist, dass die Modulationsparameter ($\lambda, \omega$) aktiv die Schwierigkeit erhöhen, das private Input $x_i$ über den Schutz hinaus wiederherzustellen, den allein Gaußsches Rauschen bietet.
   • Es wird gezeigt, dass die Multi-Vektor-Variante die erforderliche Rauschvarianz um einen Faktor reduziert, der mit $\sqrt{m}$ zusammenhängt, was den Nutzen bei einem festen Privatsphären-Budget verbessert.
3. Theoretische Garantien:
   • Unverzerrtheit: Strenger Beweis, dass der Schätzer des Servers unverzerrt ist.
   • Konvergenz: Die Arbeit etabliert die asymptotische Normalität des Schätzers und leitet Varianzschranken ab, die Konvergenzraten für projizierten stochastischen Gradientenabstieg zeigen.
   • Privatsphären-Buchhaltung: Die Methode verwendet eine Buchhaltung der Null-konzentrierten Differenziellen Privatsphäre (zCDP), die für sequenzielle Runden engere Kompositionsschranken bietet als das Standard-$(\epsilon, \delta)$-DP.
4. Untergrenzen für Rekonstruktion: Die Autoren leiten eine theoretische Untergrenze für den mittleren quadratischen Fehler eines jeden unverzerrten Angreifers ab, der versucht, $x_i$ aus der übertragenen Nachricht wiederherzustellen, und quantifizieren den Privatsphärenschutz direkt in Bezug auf die Protokollparameter.

Experimentelle Ergebnisse

Die Autoren bewerteten den Ansatz an fünf realen Regressionsdatensätzen (z. B. CO2-Emissionen, Fairness in der Ehedauer, Moduswahl), wobei jedes Trainingssample als separater Client behandelt wurde.

• Vergleich: Die vorgeschlagenen Modulierten Iterativen und Modulierten One-Shot-Schätzer wurden gegen einen abgestimmten DP-SGD FedAvg-Baseline verglichen.
• Ergebnisse:
  • Hohe Privatsphäre (niedriges $\epsilon$): Der Modulierte One-Shot-Schätzer schnitt besser ab als iterative Methoden. Da er sich auf eine einzige private Freigabe stützt, vermeidet er den kumulativen Privatsphärenverlust (Komposition), der in iterativem DP-SGD inhärent ist, und ist somit robuster, wenn das Privatsphären-Budget extrem knapp ist.
  • Moderate/niedrige Privatsphäre (hohes $\epsilon$): Der Modulierte Iterative Schätzer verbesserte sich mit mehr Runden stetig und übertraf schließlich die One-Shot-Methode sowie die DP-SGD-Baseline bei den meisten Aufgaben.
  • Baseline-Leistung: DP-SGD litt in diesem Regime erheblich, da das Rauschen, das zum Schutz eines einzelnen Samples pro Runde erforderlich ist und über mehrere Runden hinweg kumuliert, das Signal überwältigte.

Bedeutung und Behauptungen

Die Arbeit behauptet, ein spezifisches Regime zu lösen, in dem standardmäßiges Federated Learning nicht anwendbar ist: Lernen von Geräten mit extrem begrenzten Daten (ein Sample) unter strengen Privatsphären-Beschränkungen.

• Paradigmenwechsel: Im Gegensatz zum traditionellen privaten FL, bei dem Modell-Updates (Gradienten/Gewichte) geteilt werden, teilt dieser Ansatz privatisierte Datenrepräsentationen. Dieser Wechsel ermöglicht es dem Server, globale statistische Korrekturen vorzunehmen, die unmöglich sind, wenn Clients nur verrauschte lokale Gradienten senden.
• Praktikabilität: Die Methode ermöglicht es Geräten mit minimalen Daten, kollaborativ präzise Regressionsmodelle zu lernen, ohne die Privatsphäre des Einzelnen zu opfern oder große lokale Datensätze zu benötigen.
• Theoretische Strenge: Die Arbeit liefert einen vollständigen theoretischen Rahmen, einschließlich Beweisen für die Unverzerrtheit, Varianzanalysen, Konvergenzgarantien und Untergrenzen für Rekonstruktionen, und stellt fest, dass die Methode nicht nur heuristisch, sondern statistisch fundiert ist.

Die Autoren schließen, dass dieser Ansatz es machbar macht, privatsphäreschützendes maschinelles Lernen in Szenarien einzusetzen, die zuvor aufgrund von Datenknappheit und Privatsphäre-Anforderungen als unmöglich galten.