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:
På senare tid föreslog REF en ny SG-metod genom att anta att en strikt nedre gräns för f *, betecknad av f slb, är känd och f uppfyller ett tillväxttillstånd, w − w * 2 ≤ G · (f (w) − f slb ), där w * är den optimala lösningen närmast w och G är en tillväxthastighet konstant beroende på f slb.
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']}