Vi etablerar nya generalisering gränser för lärande algoritmer som konvergerar till globala minima. Vi gör det genom att härleda Black-box stabilitetsresultat som endast beror på konvergensen av en lärande algoritm och geometrin runt minimerarna av förlustfunktionen. Resultaten visas för icke konvexa förlustfunktioner som uppfyller villkoren för polyak-șojasiewicz (PL) och quadratic growth (QG). Vi visar vidare att dessa villkor uppstår för vissa neurala nätverk med linjär aktivering. Vi använder våra Black-box resultat för att etablera stabiliteten i optimering algoritmer såsom stokastisk lutning nedstigning (SGD), lutning nedstigning (GD), randomiserad koordinat nedstigning (RCD) och stokastisk varians reducerad lutning metod (SVRG), i både PL och starkt konvex inställning. Våra resultat matchar eller förbättrar toppmoderna generaliseringsgränser och kan enkelt utökas till liknande optimeringsalgoritmer. Slutligen visar vi att även om våra resultat innebär jämförbar stabilitet för SGD och GD i PL-miljö, det finns enkla neurala nätverk med flera lokala minima där SGD är stabil men GD är inte.
I REF studerade författarna generaliseringsfelet för flera första ordningens algoritmer för förlustfunktioner som uppfyller gradientdominansen och de kvadratiska tillväxtförhållandena.
Stability and Generalization of Learning Algorithms that Converge to Global Optima
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}