Neues Verfahren für Differential Private Optimierung bei Tsybakov-Rauschen

In einer aktuellen Veröffentlichung auf arXiv wird ein neues Verfahren für stochastische konvexe Optimierung im Differential-Privacy-Modell vorgestellt. Das Besondere: Die Autoren berücksichtigen die Tsybakov Noise Condition (TNC) mit einem Parameter θ > 1, wodurch die Lipschitz-Konstante des Verlustes beliebig groß oder sogar unbeschränkt sein kann. Stattdessen wird lediglich das ℓ₂‑Gradienten‑Signal mit einem beschränkten k‑ten Moment (k ≥ 2) vorausgesetzt.

Für den Lipschitz‑Fall mit θ ≥ 2 präsentiert das Paper einen (ε, δ)‑DP‑Algorithmus, dessen Nutzen‑Grenze in hoher Wahrscheinlichkeit etwa Õ( (r̃₂ₖ(1/√n + √d/(nε)))^(k−1)/k )^(θ/(θ−1)) ) beträgt. Bemerkenswert ist, dass diese obere Schranke völlig unabhängig von der Lipschitz‑Konstante ist. Das Ergebnis wird anschließend auf Fälle mit θ ≥ θ̄ > 1 erweitert.

Wenn das Privatsphäre‑Budget ε klein genug ist, liefert die Arbeit sogar für nicht‑Lipschitz‑Verluste eine ähnliche obere Schranke, die nur von dem k‑ten Moment des Gradienten abhängt. Auf der Gegenseite wird gezeigt, dass für jeden θ ≥ 2 die private Minimax‑Rate unter ρ‑Zero‑Concentrated Differential Privacy mindestens Ω( (r̃ₖ(1/√n + √d/(n√ρ)))^(k−1)/k )^(θ/(θ−1)) ) beträgt.

Diese Ergebnisse markieren einen bedeutenden Fortschritt, da sie die Grenzen der privaten Optimierung in Szenarien mit stark variierenden Verlustfunktionen deutlich erweitern und gleichzeitig robuste theoretische Garantien liefern.