Discretization of Optimization Flows through State-Triggered Control

Abstract

L'interès recent en algorismes d'optimització de primer ordre ha derivat en la formulació de les conegudes com a equacions diferencials d'alta resolució, substituts en el domini continu dels algorismes d'optimització clàssic en temps discret amb acceleració. El domini continu permet l'ús d'eines ben establertes en l'àmbit de les equacions diferencials ordinàries, com les funcions de Lyapunov. Aquest marc pot ser utilitzat per guanyar una certa intuïció sobre l'encara misteriós fenomen de l'acceleració dels algoritmes d'optimització. En aquest treball analitzem aquestes equacions diferencials d'alta resolució i el problema crític de rediscretitzar-les tot mantenint la seva velocitat de convergència. També revisem un treball recent que proposa una tècnica de discretització utilitzant idees prestades de la teoria de control oportunístic i suggerim algunes millores sobre els algorismes aquí presentats en termes de la seva velocitat de convergència.

El interés reciente en algoritmos de optimización de primer orden ha derivado en la formulación de las conocidas como equacions diferenciales de alta resolución, sustitutos en el dominio continuo de los algoritmos de optimización clásicos en tiempo discreto con aceleración. El dominio continuo permite el uso de herramientas bien establecidas en el ámbito de las equacions diferenciales ordinarias, como las funciones de Lyapunov. Este marco puede ser utilizado para ganar una cierta intuición sobre el aún misterioso fenómeno de la aceleración de los algoritmos de optimización. En este trabajo analizamos estas equaciones diferenciales de alta resolución y el problema crítico de rediscretitzarlas manteniendo su velocidad de convergencia. Tambien revisamos un trabajo reciente que propone una técnica de discretitzación utilizando ideas prestadas de la teoria de control oportunístico y sugerimos algunas mejoras sobre los algoritmos aquí presentados en términos de su velocidad de convergencia.

Recent interest in first-order optimization algorithms has lead to the formulation of so-called high-resolution differential equations, continuous surrogates for some of the classical discrete-time optimization algorithms exhibiting acceleration. The continuous setting allows the use of some powerful and well-established tools, like Lyapunov functions. This framework can be used to gain some intuition into the still somewhat mysterious phenomenon of acceleration. In this work we study these high-resolution differential equations and the crucial problem of re-discretizing them while maintaining their rate of convergence. We also review a recent paper that proposes a discretization technique by using ideas borrowed from event-triggered control and suggest some improvements on those algorithms in terms of their rate of convergence.

Outgoing