Saddle Flow Dynamics: Observable Certificates and Separable Regularization

2020/09/30 by Pengcheng You, Enrique Mallada, You, Pengcheng +1 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2009.14714

openalex publication_date 2020/09/30 · openalex created_date 2020/10/08 · openalex updated_date 2026/07/28

Abstract

This paper proposes a certificate, rooted in observability, for asymptotic convergence of saddle flow dynamics of convex-concave functions to a saddle point. This observable certificate directly bridges the gap between the invariant set and the equilibrium set in a LaSalle argument, and generalizes conventional conditions such as strict convexity-concavity and proximal regularization. We further build upon this certificate to propose a separable regularization method for saddle flow dynamics that makes minimal requirements on convexity-concavity and yet still guarantees asymptotic convergence to a saddle point. Our results generalize to saddle flow dynamics with projections on the vector field and have an immediate application as a distributed solution to linear programs.

Cited by

• On gradient descent-ascent flows in metric spaces

Related

• A Unified Analysis of Saddle Flow Dynamics: Stability and Algorithm Design
• The role of convexity on saddle-point dynamics: Lyapunov function and\n robustness
• Limit Behavior and the Role of Augmentation in Projected Saddle Flows\n for Convex Optimization
• Stability and instability in saddle point dynamics -- Part I
• Saddle-point dynamics: conditions for asymptotic stability of saddle\n points