Instanz-optimale private Dichteschätzung in der Wasserstein-Distanz

Die Schätzung der Dichte einer Verteilung aus Stichproben ist ein fundamentales Problem in der Statistik. In vielen praktischen Anwendungen ist die Wasserstein-Distanz ein geeignetes Fehlermaß für die Dichteschätzung. Wenn beispielsweise die Bevölkerungsdichten in einer geografischen Region geschätzt werden, bedeutet eine kleine Wasserstein-Distanz, dass die Schätzung in der Lage ist, grob zu erfassen, wo sich die Bevölkerungsmasse befindet. In dieser Arbeit untersuchen wir differentially private Dichteschätzung in der Wasserstein-Distanz. Wir entwerfen und analysieren instanz-optimal Algorithmen für dieses Problem, die sich an einfache Instanzen anpassen können. Für Verteilungen P über R betrachten wir eine starke Auffassung von Instanz-Optimalität: ein Algorithmus, der uniform die instanz-optimale Schätzrate erzielt, ist wettbewerbsfähig mit einem Algorithmus, der gesagt bekommt, dass die Verteilung entweder P oder QP ist für eine bestimmte Verteilung QP, deren Wahrscheinlichkeitsdichtefunktion (pdf) innerhalb eines Faktors von 2 der pdf von P liegt. Für Verteilungen über R² verwenden wir eine andere Auffassung von Instanz-Optimalität. Wir sagen, dass ein Algorithmus instanz-optimal ist, wenn er wettbewerbsfähig ist mit einem Algorithmus, der eine konstant-faktor-multiplikative Annäherung der Dichte der Verteilung erhält. Wir charakterisieren die instanz-optimalen Schätzraten in beiden diesen Einstellungen und zeigen, dass sie gleichmäßig erreichbar sind (bis zu polylogarithmischen Faktoren). Unser Ansatz für R² erstreckt sich auf beliebige metrische Räume, da er über hierarchisch getrennte Bäume erfolgt. Als Spezialfall führen unsere Ergebnisse zu instanz-optimalem privatem Lernen in der TV-Distanz für diskrete Verteilungen.