Zur nichtasymptotischen Konvergenz von Methoden des zyklischen Koordinatenabstiegs

Zusammenfassung. Der zyklische Koordinatenabstieg ist eine klassische Optimierungsmethode, die eine Wiederbelebung des Interesses in der Signalverarbeitung, Statistik und im maschinellen Lernen erlebt hat. Gründe für dieses erneute Interesse sind die Einfachheit, Schnelligkeit und Stabilität der Methode sowie ihre wettbewerbsfähige Leistung bei 1 regulierten glatten Optimierungsproblemen. Überraschenderweise ist sehr wenig über ihr nichtasymptotisches Konvergenzverhalten bei diesen Problemen bekannt. Die meisten bestehenden Ergebnisse beweisen entweder nur die Konvergenz oder liefern asymptotische Raten. Wir schließen diese Lücke in der Literatur, indem wir O(1/k) Konvergenzraten beweisen (wobei k die Iterationsanzahl ist) für zwei Varianten des zyklischen Koordinatenabstiegs unter der Annahme der Isotonie. Unsere Analyse erfolgt durch den Vergleich der von den beiden Varianten erreichten Zielfunktionswerte miteinander sowie mit dem Gradientenabstieg-Algorithmus. Wir zeigen, dass die durch die Methoden des zyklischen Koordinatenabstiegs generierten Iterationen zeitlich konstant besser sind als die des Gradientenabstiegs.