Empirisk riskminimering (ERM) är en standardteknik inom maskininlärning, där en modell väljs genom att minimera en förlustfunktion över begränsningsuppsättning. När träningsdatasetet består av privat information är det naturligt att använda en differentialt privat ERM algoritm, och detta problem har varit föremål för en lång rad arbete [CM08, KST12, JKT12, ST13a, DJW13, JT14, BST14, Ull14]. En privat ERM-algoritm ger en ungefärlig minimering av förlustfunktionen och dess fel kan mätas som skillnaden från det optimala värdet av förlustfunktionen. När begränsningsmängden är godtycklig, krävs felgränser är ganska väl förstådd [BST14]. I detta arbete visar vi att de geometriska egenskaperna hos restriktionssetet kan användas för att få betydligt bättre resultat. Specifikt visar vi att en differentialt privat version av Mirror Descent leder till felgränser av formen Õ(G C /n) för en lipschitz förlust funktion, förbättra på Õ( ε p / n) gränser i [BST14]. Här p är dimensionaliteten av problemet, n är antalet datapunkter i träningssetet, och G C betecknar den Gaussiska bredden av begränsningssetet som vi optimerar över. Vi visar liknande förbättringar för starkt konvexa funktioner och för smidiga funktioner. Dessutom visar vi att när förlustfunktionen är Lipschitz med avseende på 1 norm och C är 1 -bunden, en differentialt privat version av Frank-Wolfe algoritm ger felgränser av formen Õ(n −2/3 ). Detta fångar upp det viktiga och vanliga fallet av gles linjär regression (LASSO), när data x i uppfyller  på x i  och vi optimerar över 1 boll. Vi visar nya nedre gränser för denna inställning, att tillsammans med kända gränser, innebär att alla våra övre gränser är snäva. * 1 I hela papperet, använder vi O,  och för att dölja polynom faktorer i 1/, log( 1/δ), log n, och log p.
Deras nedre gräns beror på den Gaussiska bredden och är oberoende av dimensionaliteten p. Senare, REF anses ett specialfall där förlustfunktionen är Lipschitz under 1 norm och begränsningen uppsättning C är en polytop.
Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}