Många nya applikationer inom maskininlärning och datamontering kallar för algoritmisk lösning av strukturerade smidiga konvexa optimeringsproblem. Även om lutning nedstigningsmetoden är ett naturligt val för denna uppgift, kräver det exakta lutningsberäkningar och kan därför vara ineffektiv när problemstorleken är stor eller lutningen är svår att utvärdera. Därför har det funnits stort intresse för inexakt gradient metoder (IGMs), där en effektivt beräknande ungefärlig gradient används för att utföra uppdateringen i varje iteration. För närvarande är icke-asymptotiska linjära konvergensresultat för IGM vanligtvis fastställda under antagandet att den objektiva funktionen är starkt konvex, som inte är tillfredsställd i många tillämpningar av intresse; medan linjära konvergensresultat som inte kräver den starka konvexitet antagande är oftast asymptotic i naturen. I detta papper kombinerar vi det bästa av dessa två typer av resultat och etablerar-enligt standard antagandet att gradient approximationsfelen minskar linjärt till noll-det icke-asymptotiska linjära konvergensen av IGMs när den tillämpas på en klass av strukturerade konvexa optimeringsproblem. En sådan klass omfattar inställningar där den objektiva funktionen inte nödvändigtvis är starkt konvex och innehåller minst kvadrater och logistiska regressionsproblem. Vi tror att våra tekniker kommer att hitta ytterligare tillämpningar i den icke-asymptotiska konvergensanalysen av andra första ordningens metoder.
Ett sådant antagande är ganska starkt och är inte tillfredsställt av flera problem, såsom minst kvadrater och logistisk regression REF.
Non-Asymptotic Convergence Analysis of Inexact Gradient Methods for Machine Learning Without Strong Convexity
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}