Optimale Raten für reines ε-DP bei konvexer Optimierung mit schweren Tails

In einer neuen Studie auf arXiv wird ein entscheidender Fortschritt in der stochastischen konvexen Optimierung (SCO) erzielt, wenn die Gradienten stark abweichende, unbeschränkte Verteilungen aufweisen. Anstatt die übliche Beschränkung auf den schlimmsten Lipschitz‑Parameter zu nutzen, gehen die Autoren nur von einem beschränkten k‑ten Moment aus. Diese Annahme erlaubt es, mit schweren Tails umzugehen und führt zu präziseren Grenzwerten für den Übermaßrisiko.

Während die minimax‑optimale Rate für die (ε, δ)-Differential Privacy bereits bekannt ist, blieb die reine ε‑DP‑Variante lange Zeit ungeklärt. Die neue Arbeit schließt diese Lücke, indem sie die optimale Übermaßrisiko‑Rate für reine ε‑DP bei schweren Tails bis auf logarithmische Faktoren bestimmt. Das dazugehörige Verfahren erreicht diese Rate in polynomialer Zeit mit hoher Wahrscheinlichkeit und sogar mit 100 % Wahrscheinlichkeit, wenn der Lipschitz‑Parameter polynomial beschränkt ist.

Besonders beeindruckend ist die Anwendung auf strukturierte Problemklassen wie hinge‑/ReLU‑Verluste und absolute‑Wert‑Verluste auf euklidischen Bällen, Ellipsoiden und Polytope. Für diese Fälle liefert das Verfahren dieselbe Übermaßrisiko‑Garantie in polynomialer Zeit, selbst wenn der Lipschitz‑Parameter unendlich groß ist. Der Schlüssel liegt in einem neuartigen Rahmen, der private Optimierung von Lipschitz‑Erweiterungen des empirischen Verlusts ermöglicht.

Zusätzlich zu den oberen Schranken präsentiert die Studie einen neuen, hochwahrscheinlichkeitsbasierten unteren Schranken, der die optimalen Raten bestätigt. Dieser Beitrag liefert damit ein vollständiges Bild der theoretischen Grenzen für reine ε‑DP bei stochastischer konvexer Optimierung mit schweren Tails und eröffnet neue Wege für effiziente, datenschutzfreundliche Algorithmen.