Vi studerar det detaljerade patologiska beteendet hos den diskreta Langevin algoritmen för icke-konvex Empirisk riskminimering (ERM) genom linsen av metastaserbarhet, genom att anta vissa tekniker från Berglund och Gentz (2003). För en särskild lokal optimal av den empiriska risken, med en godtycklig initiering, visar vi att med hög sannolikhet, minst en av följande två händelser kommer att inträffa: (1) Langevin bana hamnar någonstans utanför ε-grannskap av denna speciella optimal inom en kort upprepningstid; (2) det går in i denna ε-grannskap av upprepningstiden och stannar där tills en potentiellt exponentiellt lång flykttid. Vi kallar detta fenomen empirisk metastaserbarhet. Denna tvåtidskarakterisering stämmer fint överens med den befintliga litteraturen i de följande två sinnena. För det första är den effektiva upprepningstiden (dvs. antalet iterationer multiplicerade med stegize) dimensionsoberoende och liknar konvergenstiden för kontinuerlig tidsdeterministisk gradientdecent (GD). Men till skillnad från GD, Langevin algoritm inte kräver starka villkor på lokal initiering, och har möjlighet att så småningom besöka alla optima. För det andra är flykttidens omfattning förenlig med Eyring-Kramers-lagen, där det anges att Langevin-systemet så småningom kommer att besöka alla lokala minima, men det kommer att ta exponentiellt lång tid att passera mellan dem. Vi tillämpar denna vägvisa koncentration i samband med statistisk inlärning för att undersöka lokala föreställningar om generalisering och optimalitet.
REF gav en finare analys av recidivtiden och flykttiden för SGLD genom empirisk metastaserbarhet.
Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
{'venue': 'Proceedings of COLT 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}