Analyse de convergence de l'algorithme de descente de miroir stochastique à points selles -- Un point de vue dynamique projeté

Les problèmes de points selles, omniprésents dans l'optimisation, s'étendent au-delà de la théorie des jeux pour inclure des domaines divers tels que les réseaux électriques et l'apprentissage par renforcement. Cet article présente des approches novatrices pour aborder les problèmes de points selles, en se concentrant sur des contextes en temps continu. Dans cet article, nous proposons une dynamique en temps continu pour traiter le problème de points selles en utilisant un système dynamique projeté dans un domaine non euclidien. Cela implique de calculer le (sous/super) gradient de la fonction min-max dans une métrique riemannienne. De plus, nous établissons des solutions viables de Carathéodory et prouvons également la stabilité de Lyapunov et la stabilité asymptotique de l'ensemble du système dynamique en temps continu proposé. Ensuite, nous présentons l'algorithme de descente de miroir à points selles stochastiques (SSPMD) et établissons son équivalence avec la dynamique en temps continu proposée. En tirant parti de l'analyse de stabilité de la dynamique en temps continu, nous démontrons la convergence presque sûre des itérations de l'algorithme. En outre, nous introduisons l'algorithme de descente de miroir à points selles d'ordre zéro (SZSPMD), qui approxime les gradients en utilisant l'approximation gaussienne de Nesterov, montrant une convergence vers un voisinage des points selles. L'analyse de cet article fournit des perspectives géométriques sur l'algorithme de descente de miroir et illustre comment ces perspectives offrent des bases théoriques pour diverses applications pratiques de l'algorithme de descente de miroir dans des scénarios variés.