Our paper [1] on understanding the role of local and strong convexity on the convergence and robustness of saddle-point dynamics has been accepted to the Allerton Conference on Communication, Control and Computing!
[Bibtex] [Abstract] [Download PDF]
This paper studies the projected saddle-point dynamics for a twice differentiable convex-concave function, which we term saddle function. The dynamics consists of gradient descent of the saddle function in variables corresponding to convexity and (projected) gradient ascent in variables corresponding to concavity. We provide a novel characterization of the omega-limit set of the trajectories of these dynamics in terms of the diagonal Hessian blocks of the saddle function. Using this characterization, we establish global asymptotic convergence of the dynamics under local strong convexityconcavity of the saddle function. If this property is global, and for the case when the saddle function takes the form of the Lagrangian of an equality constrained optimization problem, we establish the input-to-state stability of the saddlepoint dynamics by providing an ISS Lyapunov function. Various examples illustrate our results.
@inproceedings{cmlc2016allerton,
abstract = {This paper studies the projected saddle-point dynamics for a twice differentiable convex-concave function, which we term saddle function. The dynamics consists of gradient
descent of the saddle function in variables corresponding to convexity and (projected) gradient ascent in variables corresponding to concavity. We provide a novel characterization of the omega-limit set of the trajectories of these dynamics in terms of the diagonal Hessian blocks of the saddle function. Using this characterization, we establish global asymptotic convergence of the dynamics under local strong convexityconcavity of the saddle function. If this property is global, and for the case when the saddle function takes the form of the Lagrangian of an equality constrained optimization problem, we establish the input-to-state stability of the saddlepoint dynamics by providing an ISS Lyapunov function. Various examples illustrate our results.},
author = {Ashish Cherukuri and Mallada, Enrique and Steven H. Low and Jorge Cortes},
booktitle = {54th Allerton Conference on Communication, Control, and Computing},
doi = {10.1109/ALLERTON.2016.7852273},
grants = {1544771},
keywords = {Saddle-Point Dynamics; Caratheodory solutions},
month = {09},
pages = {504-510},
title = {The role of strong convexity-concavity in the convergence and robustness of the saddle-point dynamics},
url = {https://mallada.ece.jhu.edu/pubs/2016-Allerton-CMLC.pdf},
year = {2016}
}