Eine neuartige Interpretation von Nesterovs Beschleunigung mittels variabler Schrittgrößen bei linearen Multistep-Methoden

Nesterovs Beschleunigung in der kontinuierlichen Optimierung kann auf neuartige Weise verstanden werden, wenn die Nesterovs beschleunigte Gradientenmethode (NAG) als lineare Multistep-Methode (LM) für den Gradientenfluss betrachtet wird. Obwohl die NAG-Methode für stark konvexe Funktionen (NAG-sc) umfassend diskutiert wurde, wurde die NAG-Methode für L-glatte konvexe Funktionen (NAG-c) nicht behandelt. Um diese Lücke zu schließen, zeigen wir, dass die bestehende NAG-c-Methode als eine variable Schrittgrößen-LM (VLM) für den Gradientenfluss interpretiert werden kann. Überraschenderweise erlaubt die VLM linear steigende Schrittgrößen, was die Beschleunigung im konvexen Fall erklärt. Hier führen wir eine neuartige Technik zur Analyse der absoluten Stabilität von VLMs ein. Anschließend beweisen wir, dass NAG-c optimal in einer bestimmten natürlichen Klasse von VLMs ist. Schließlich konstruieren wir eine neue, breitere Klasse von VLMs, indem wir die Parameter in der VLM für schlecht gestellte Probleme optimieren. Laut numerischen Experimenten übertrifft die vorgeschlagene Methode die NAG-c-Methode in schlecht gestellten Fällen. Diese Ergebnisse implizieren, dass die Perspektive der numerischen Analyse der NAG ein vielversprechendes Arbeitsumfeld darstellt und die Berücksichtigung einer breiteren Klasse von VLMs weitere neuartige Methoden aufdecken könnte.