Vi visar att Entropy-SGD (Chaudhari et al., 2017), när den betraktas som en lärande algoritm, optimerar en PAC-Bayes som är bunden av risken för en Gibbs (bakre) klassificerare, d.v.s. en randomiserad klassificering som erhålls genom en riskkänslig perturbation av vikterna hos en lärd klassificerare. Entropy-SGD fungerar genom att optimera gränsens tidigare, bryta hypotesen i PAC-Bayes theorem att föregående väljs oberoende av data. Tillgängliga implementeringar av Entropy-SGD får snabbt noll träningsfel på slumpmässiga etiketter och samma håll i Gibbs bakre. För att få en giltig generalisering bunden, visar vi att en ε-differentiellt privat föregående ger en giltig PAC-Bayes bundna, en enkel konsekvens av resultat som förbinder generalisering med differential integritet. Med hjälp av stokastisk lutning Langevin dynamik (SGLD) för att approximera den välkända exponentiella release mekanism, observerar vi att generalisering fel på MNIST (mätt på hållna data) faller inom (empiriskt nonvakuous) gränser som beräknas under antagandet att SGLD producerar perfekta prover. I synnerhet, Entropy-SGLD kan konfigureras för att ge relativt snäva generalisering gränser och fortfarande passa riktiga etiketter, även om dessa samma inställningar inte får state-of-the-art prestanda. Lokal entropi är bokstavligen en Bayesian log marginell densitet. Sambandet mellan att minimera PAC-Bayes gränser under log förlust och maximera log marginal densiteter är föremål för nyligen arbete av Germain et al. (2016). Liknande förbindelser har gjorts av Zhang (2006a), Zhang (2006b), Grünwald (2012), Grünwald och Mehta (2016). Trots kopplingen till PAC-Bayes, samt teoretiska resultat av Chaudhari et al. tyder på att Entropy-SGD kan vara stabilare än SGD, visar vi att Entropy-SGD (och dess motsvarande Gibbs bakre) snabbt kan överpassa sig, precis som SGD. Vi identifierar två förändringar, motiverade av teoretisk analys, som räcker för att kontrollera generaliseringsfel, och därmed förhindra övermontering. Den första förändringen gäller stabiliteten i att optimera det tidigare medelvärdet. PAC-Bayes theorem kräver att den tidigare vara oberoende av data, och så genom att optimera det föregående medelvärdet, Entropy-SGD ogiltigförklarar den bundna. Gränsen håller faktiskt inte empiriskt. Även om en PAC-Bayes tidigare inte kan väljas baserat på data, kan det bero på datadistributionen. Detta tyder på att om det föregående endast är svagt beroende av uppgifterna, kan det vara möjligt att härleda en giltig gräns. Vi formaliserar denna intuition med hjälp av differential integritet (Dwork, 2006; Dwork et al., 2015b). Genom att ändra korsentropi förlust att begränsas och ersätta SGD med stokastisk lutning Langevin dynamik (SGLD; Welling och Teh, 2011), kan databeroende föregående medelvärde visas vara (ε, δ )-differentiellt privat (Wang, Fienberg, och Smola, 2015; Minami et al., 2016). Vi hänvisar till SGLD varianten som Entropy-SGLD. Använda resultat som förbinder statistisk giltighet och differential integritet (Dwork et al., 2015b, Thm. 11), visar vi att ett ε-differentiellt privat föregående medelvärde ger en giltig, om än lösare, generalisering bunden med PAC-Bayes theorem. (Se Theorem 5.4.) Ett gap kvarstår mellan ren och ungefärlig differentiell integritet. Under vissa tekniska förhållanden, i den utsträckning antalet iterationer skiljer sig åt, är fördelningen av SGLD:s produktion känd för att konvergera svagt till motsvarande stationär distribution, vilket är den välkända exponentiella mekanismen i differentiell integritet (Teh, Thiery och Vollmer, 2016, Thm. 7) och av följande skäl: Svag konvergens är dock inte tillräckligt för att antyda att SGLD uppnår ren ε-differentierad integritet. Vi går vidare under approximationen att SGLD har samma integritet som den exponentiella releasemekanismen, och tillämpa våra ε-differentiellt privata PAC-Bayes bundna. Vi finner att motsvarande 95% konfidensintervall är någorlunda snäva men ändå konservativa i våra experiment. Medan giltigheten av våra gränser är föremål för vår approximation, gränserna ger oss en uppfattning om begränsningarna i att kombinera differential integritet med PAC-Bayes gränser: när integritet Entropy-SGLD är inställd för att bidra med högst 2ε 2 × 100  och 0,2% till generalisering fel, test felet i det lärda nätverket är 3-8%, vilket är cirka 5-10 gånger högre än den senaste tekniken, vilket för MNIST är mellan 0,2-1%, även om samhället har nästan säkert överpassat sina nätverk / lärhastigheter / förlust funktioner / optimerare till MNIST. Vi återkommer till dessa punkter i diskussionen. Den andra ändringen avser stabiliteten i den stokastiska gradientuppskattning som görs på varje iteration av Entropy-SGD. Denna uppskattning görs med hjälp av SGLD. (Hence Entropy-SGD är SGLD inom SGD.) Chaudhari m.fl. göra en subtil men kritisk ändring av bullertermen i SGLD uppdatering: buller är dividerat med en faktor som sträcker sig från 10 3 till 10 4. (Denna faktor har till synes justerats för att ge goda empiriska resultat.) Vår analys visar att Lipschitz-konstanten i den objektiva funktionen är ungefär 10 6 -10 8 gånger större, och slutsatsen att Entropy-SGD-målet är smidigare än den ursprungliga riskytan inte längre står. Denna förändring av bullret inverkar också negativt på det tidigare medelvärdets skiljaktiga privatliv. Vi arbetar bakåt från önskan att få snäva generalisering gränser, vi leds till att dela SGLD buller med en faktor på endast 4 ε m, där m är antalet datapunkter. (För MNIST, 4 och 16.) De resulterande gränserna är icke-vakulösa och stramare än de som nyligen publicerats av Dziugaite och Roy (2017), även om det måste betonas att den gräns som presenteras här är föremål för en tillnärmning av det tidigare medelvärdets privatliv, vilket förvisso kränks men i okänd utsträckning. Vi börjar med en översyn av vissa relaterade arbete, innan vi inför tillräcklig bakgrund så att vi kan göra en formell koppling mellan lokala entropi och PAC-Bayes gränser. Vi introducerar sedan en differentierad privat PAC-Bayes bunden. I Avsnitt 6 presenterar vi experiment på MNIST som ger bevis för vår teoretiska analys. (Emprical validation krävs för att ta itu med ovannämnda gap mellan ren och ungefärlig differentiell integritet.) Vi avslutar med en kort diskussion. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning.
Den PAC-Bayes bundna har också övervägts och beräknas av REF, vilket resulterar i icke-vakulösa gränser för MNIST.
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Data-dependent PAC-Bayes priors via differential privacy
{'venue': 'Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1377-1386, 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}