Schnelle John-Ellipsoid-Berechnung mit Differential Privacy-Optimierung

Die Bestimmung des John-Ellipsoids – des größten Volumenellipsoids, das sich innerhalb eines konvexen Polytope befindet – ist ein fundamentales Problem mit Anwendungen in maschinellem Lernen, Optimierung und Datenanalytik. Jüngste Arbeiten haben schnelle Algorithmen zur Annäherung an das John-Ellipsoid unter Verwendung von Skizzierungs- und Hebewert-Probenahmetechniken entwickelt. Diese Algorithmen bieten jedoch keine Datenschutzgarantien für sensible Eingabedaten. In diesem Papier präsentieren wir den ersten differenziell privaten Algorithmus zur schnellen Berechnung des John-Ellipsoids. Unsere Methode integriert Rauschstörungen mit Skizzierung und Hebewert-Probenahme, um sowohl Effizienz als auch Datenschutz zu erreichen. Wir beweisen, dass (1) unser Algorithmus (, ) -differenzielle Privatsphäre bietet und die Datenschutzgarantie für benachbarte Datensätze gilt, die ₀-nah sind, was Flexibilität in der Datenschutzdefinition ermöglicht; (2) unser Algorithmus dennoch zu einer (1+) -Annäherung des optimalen John-Ellipsoids in O (^-2 ( (n/₀) + (L₀) ^-2) ) Iterationen konvergiert, wobei n die Anzahl der Datenpunkte ist, L die Lipschitz-Konstante ist, ₀ die Fehlerrate ist und ₀ die Nähe benachbarter Eingabedatensätze ist. Unsere theoretische Analyse demonstriert die Konvergenz- und Datenschutzmerkmale des Algorithmus und bietet einen robusten Ansatz zur Balance zwischen Nutzen und Datenschutz in der Berechnung des John-Ellipsoids. Dies ist der erste differenziell private Algorithmus zur schnellen Berechnung des John-Ellipsoids, der Wege für zukünftige Forschungen in datenschutzbewahrenden Optimierungstechniken eröffnet.