Konvex empirisk riskminimering är ett grundläggande verktyg inom maskininlärning och statistik. Vi tillhandahåller nya algoritmer och matchar lägre gränser för differentialt privat konvex empirisk riskminimering förutsatt att endast varje datapunkts bidrag till förlustfunktionen är Lipschitz och att optimeringsdomänen begränsas. Vi tillhandahåller en separat uppsättning algoritmer och matchar lägre gränser för den inställning där förlustfunktionerna är kända för att också vara starkt konvexa. Våra algoritmer körs i polynom tid, och i vissa fall även matcha den optimala icke-privata körtid (mätt som orakel komplexitet). Vi ger separata algoritmer (och lägre gränser) för (, 0) och (, δ)-differentiell integritet; kanske överraskande, de tekniker som används för att utforma optimala algoritmer i de två fallen är helt olika. Våra nedre gränser gäller även för mycket enkla, smidiga funktionsfamiljer, såsom linjära och kvadratiska funktioner. Detta innebär att algoritmer från tidigare arbete kan användas för att erhålla optimala felfrekvenser, under det ytterligare antagandet att bidragen från varje datapunkt till förlustfunktionen är smidig. Vi visar att enkla metoder för att utjämna godtyckliga förlustfunktioner (för att tillämpa tidigare tekniker) inte ger optimala felfrekvenser. I synnerhet var optimala algoritmer inte tidigare kända för problem som t.ex. träningsstöd vektor maskiner och den högdimensionella medianen.
Bassily och al. REF föreslog nya algoritmer för det privata konvexa ERM-problemet när förlustfunktionen bara är Lipschitz och domänen för optimeringen begränsas.
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
{'venue': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'journal': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}