Sammanfattning Vi studerar de värsta fall konvergenshastigheter av proximal gradient metod för att minimera summan av en jämn starkt konvex funktion och en icke-smooth konvex funktion, vars proximal operatör finns tillgänglig. Vi fastställer de exakta värsta fall konvergenshastigheterna för den proximala gradientmetoden i denna inställning för alla stegstorlekar och för olika standardprestandamått: objektiv funktionsnoggrannhet, avstånd till optimalitet och restgradientnorm. Bevismetoden bygger på den senaste utvecklingen när det gäller prestationsuppskattning av första ordningens metoder, baserad på semidefinitprogrammering. När det gäller den proximala gradientmetoden gör denna metod det möjligt att erhålla exakta och icke-asymptotiska värsta-fall-garantier, som är konceptuellt mycket enkla, även om tydligen nya. På vägen diskuterar vi hur stark konvexitet kan ersättas av svagare antaganden, samtidigt som motsvarande konvergensnivåer bibehålls. Vi konstaterar också att samma policy för fast stegstorlek är optimal för alla tre prestationsåtgärderna. Slutligen, vi utökar de senaste resultaten på det värsta-fallet beteendet av lutning nedstigning med exakt linjesökning till det proximala fallet.
En utvidgning av denna ram till den proximala gradientmetoden – för fall av starkt konvexa problem – har nyligen föreslagits i REF.
Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics', 'Computer Science']}