Detta dokument visar att felgränser kan användas som effektiva verktyg för att härleda komplexa resultat för första ordningens nedstigningsmetoder i konvex minimering. I ett första skede ledde detta mål oss att se över samspelet mellan felgränserna och ojämlikheten mellan Kurdyka-Lojasiewicz (KL). Man kan visa ekvivalensen mellan de två begreppen för konvexa funktioner med en måttligt plan profil nära uppsättningen av minimatorer (som fungerar med Hölderian tillväxt). Ett motexempel visar att likvärdigheten inte längre gäller för extremt platta funktioner. Detta faktum avslöjar relevansen av en strategi baserad på KL ojämlikhet. I ett andra steg visar vi hur KL ojämlikhet i sin tur kan användas för att beräkna nya komplexitet gränser för en rikedom av nedstigande metoder för konvexa problem. Vårt tillvägagångssätt är helt originellt och använder sig av en endimensionell värsta-fall-proximal sekvens i andan av den berömda majorant metoden av Kantorovich. Vårt resultat gäller en mycket enkel abstrakt plan som täcker en bred klass av nedstigande metoder. Som en biprodukt av vår studie ger vi också nya resultat för globaliseringen av KL ojämlikheter i konvexa ramar. Våra huvudsakliga resultat inviger en enkel metod: härleda ett fel bundet, beräkna desingularizing funktionen när det är möjligt, identifiera väsentliga konstanter i nedstigningsmetoden och slutligen beräkna komplexiteten med hjälp av endimensionella värsta fall proximal sekvens. Vår metod illustreras genom projiceringsmetoder för genomförbarhetsproblem, och genom den berömda iterativa krymptröskelalgoritmen (ISTA), för vilken vi visar att komplexiteten bundet är av formen O(q k ) där komponenterna i den bundna endast beror på fel bundna konstanter som erhållits för en godtycklig minst kvadrater mål med l 1 legalisering.
REF fastställde likvärdigheten för HEB och Kurdyka-Lojasiewicz (KL) ojämlikhet och visade hur man kan härleda lägre beräknings komplexitet genom att använda KL ojämlikhet.
From error bounds to the complexity of first-order descent methods for convex functions
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics', 'Computer Science']}