Motiverade av det senaste arbetet med Renegar [21] presenterar vi nya beräkningsmetoder och tillhörande beräkningsgarantier för att lösa problem med konvex optimering med hjälp av första ordningens metoder. Vårt problem av intresse är den allmänna konvex optimering problem f * = min x.Q f (x), där vi antar kunskap om en strikt nedre gräns f slb < f *. [Indeed, f slb är naturligt känt när optimera många förlustfunktioner i statistik och maskininlärning (minst-kvartor, logistisk förlust, exponentiell förlust, total variationsförlust, etc.) liksom i Renegars transformerade version av standardkonikoptimeringsproblemet [21], i alla dessa fall har man f slb = 0 < f *.] Vi inför en ny funktionell åtgärd som kallas tillväxtkonstanten G för f (·), som mäter hur snabbt nivåerna av f (·) växer i förhållande till funktionsvärdet, och som spelar en grundläggande roll i komplexitetsanalysen. När f (·) är icke-smooth, presenterar vi nya beräkningsgarantier för Subgradient Descent Method och för utjämningsmetoder, som kan förbättra befintliga beräkningsgarantier på flera sätt, särskilt när den initiala iterat x 0 är långt ifrån den optimala lösningen uppsättning. När f (·) är smidig, presenterar vi ett system för periodisk omstart av Accelerated Gradient Method som också kan förbättra befintliga beräkningsgarantier när x 0 är långt ifrån den optimala lösningen uppsättning, och i närvaro av ytterligare struktur presenterar vi ett system med parametriskt ökad utjämning som ytterligare förbättrar tillhörande beräkningsgarantier. 1 Problemförklaring och översikt över resultat Motiverad av det senaste arbetet med Renegar [21] presenterar vi nya beräkningsmetoder och tillhörande beräkningsgarantier för att lösa konvexa optimeringsproblem med hjälp av första ordningens metoder. Vårt problem av intresse är följande optimeringsproblem:
I REF införde författarna en ny smidig approximationsalgoritm genom att utnyttja den strikta nedre gränsen för den objektiva funktionen och ett funktionstillväxttillstånd.
New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics', 'Computer Science']}