Our papers on Dissipative Gradient Descent-Ascent algorithms for min-max problems [1], Accelerated saddle flow dynamics [2], and invertibility of sparse linear dynamical systems [3] have been accepted to the 63rd IEEE Conference on Decision and Control. Congrats to the leading students Tianqi, Yingzhu, Kyle, and to all the rest of the team!
[Bibtex] [Abstract] [Download PDF]
Gradient Descent Ascent (GDA) methods for min-max optimization problems typically produce oscillatory behavior that can lead to instability, e.g., in bilinear settings. To address this problem, we introduce a dissipation term into the GDA updates to dampen these oscillations. The proposed Dissipative GDA (DGDA) method can be seen as performing standard GDA on a state-augmented and regularized saddle function that does not strictly introduce additional convexity/concavity. We theoretically show the linear convergence of DGDA in the bilinear and strongly convex-strongly concave settings and assess its performance by comparing DGDA with other methods such as GDA, Extra-Gradient (EG), and Optimistic GDA. Our findings demonstrate that DGDA surpasses these methods, achieving superior convergence rates. We support our claims with two numerical examples that showcase DGDA’s effectiveness in solving saddle point problems.
@inproceedings{zlym2024cdc,
abstract = {Gradient Descent Ascent (GDA) methods for min-max optimization problems typically produce oscillatory behavior that can lead to instability, e.g., in bilinear settings.
To address this problem, we introduce a dissipation term into the GDA updates to dampen these oscillations. The proposed Dissipative GDA (DGDA) method can be seen as performing standard GDA on a state-augmented and regularized saddle function that does not strictly introduce additional convexity/concavity. We theoretically show the linear convergence of DGDA in the bilinear and strongly convex-strongly concave settings and assess its performance by comparing DGDA with other methods such as GDA, Extra-Gradient (EG), and Optimistic GDA.
Our findings demonstrate that DGDA surpasses these methods, achieving superior convergence rates. We support our claims with two numerical examples that showcase DGDA's effectiveness in solving saddle point problems.},
author = {Zheng, Tianqi and Loizou, Nicolas and You, Pengcheng and Mallada, Enrique},
booktitle = {63rd IEEE Conference on Decision and Control (CDC)},
grants = {CPS-2136324, Global-Centers-2330450},
month = {07},
note = {also in L-CSS},
pubstate = {accepted, submitted Mar 2024},
title = {Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization},
url = {https://mallada.ece.jhu.edu/pubs/2024-LCSS-ZLYM.pdf},
year = {2024}
}[Bibtex] [Abstract] [Download PDF]
Minimax problems have attracted much attention due to various applications in constrained optimization problems and zero-sum games. Identifying saddle points within these problems is crucial, and saddle flow dynamics offer a straightforward yet useful approach. This study focuses on a class of bilinearly coupled minimax problems and designs an accelerated algorithm based on saddle flow dynamics that achieves a convergence rate beyond stereotype limits. The algorithm is derived based on a sequential two-step transformation of the objective function. First, a change of variable is aimed at a better-conditioned saddle function. Second, a proximal regularization, when staggered with the first step, guarantees strong convexity-strong concavity of the objective function that can be tuned for accelerated exponential convergence. Besides, such an approach can be extended to a class of weakly convex-weakly concave functions and still achieve exponential convergence to one stationary point. The theory is verified by a numerical test on an affine equality-constrained convex optimization problem.
@inproceedings{lmly2024cdc,
abstract = {Minimax problems have attracted much attention due to various applications in constrained optimization problems and zero-sum games. Identifying saddle points within these problems is crucial, and saddle flow dynamics offer a straightforward yet useful approach. This study focuses on a class of bilinearly coupled minimax problems and designs an accelerated algorithm based on saddle flow dynamics that achieves a convergence rate beyond stereotype limits. The algorithm is derived based on a sequential two-step transformation of the objective function. First, a change of variable is aimed at a better-conditioned saddle function. Second, a proximal regularization, when staggered with the first step, guarantees strong convexity-strong concavity of the objective function that can be tuned for accelerated exponential convergence.
Besides, such an approach can be extended to a class of weakly convex-weakly concave functions and still achieve exponential convergence to one stationary point. The theory is verified by a numerical test on an affine equality-constrained convex optimization problem.},
author = {Liu, Yingzhu and Mallada, Enrique and Li, Zhongkui and You, Pengcheng},
booktitle = {63rd IEEE Conference on Decision and Control (CDC)},
grants = {CPS-2136324, Global-Centers-2330450},
month = {07},
pubstate = {accepted, submitted Mar 2024},
title = {Accelerated Saddle Flow Dynamics for Bilinearly Coupled Minimax Problems},
url = {https://mallada.ece.jhu.edu/pubs/2024-Preprint-LMLY.pdf},
year = {2024}
}[Bibtex] [Abstract] [Download PDF]
One of the fundamental problems of interest for discrete-time linear systems is whether its input sequence may be recovered given its output sequence, a.k.a. the left inversion problem. Many conditions on the state space geometry, dynamics, and spectral structure of a system have been used to characterize the well-posedness of this problem, without assumptions on the inputs. However, certain structural assumptions, such as input sparsity, have been shown to translate to practical gains in the performance of inversion algorithms, surpassing classical guarantees. Establishing necessary and sufficient conditions for left invertibility of systems with sparse inputs is therefore a crucial step toward understanding the performance limits of system inversion under structured input assumptions. In this work, we provide the first necessary and sufficient characterizations of left invertibility for linear systems with sparse inputs, echoing classic characterizations for standard linear systems. The key insight in deriving these results is in establishing the existence of two novel geometric invariants unique to the sparse-input setting, the weakly unobservable and strongly reachable subspace arrangements. By means of a concrete example, we demonstrate the utility of these characterizations. We conclude by discussing extensions and applications of this framework to several related problems in sparse control.
@inproceedings{pmv2024cdc,
abstract = {One of the fundamental problems of interest for discrete-time linear systems is whether its input sequence may be recovered given its output sequence, a.k.a. the left inversion problem. Many conditions on the state space geometry, dynamics, and spectral structure of a system have been used to characterize the well-posedness of this problem, without assumptions on the inputs. However, certain structural assumptions, such as input sparsity, have been shown to translate to practical gains in the performance of inversion algorithms, surpassing classical guarantees. Establishing necessary and sufficient conditions for left invertibility of systems with sparse inputs is therefore a crucial step toward understanding the performance limits of system inversion under structured input assumptions. In this work, we provide the first necessary and sufficient characterizations of left invertibility for linear systems with sparse inputs, echoing classic characterizations for standard linear systems. The key insight in deriving these results is in establishing the existence of two novel geometric invariants unique to the sparse-input setting, the weakly unobservable and strongly reachable subspace arrangements. By means of a concrete example, we demonstrate the utility of these characterizations. We conclude by discussing extensions and applications of this framework to several related problems in sparse control.},
author = {Poe, Kyle and Mallada, Enrique and Vidal, Rene},
booktitle = {63rd IEEE Conference on Decision and Control (CDC)},
grants = {CPS-2136324, Global-Centers-2330450},
month = {07},
pubstate = {accepted, submitted Mar 2024},
title = {Invertibility of Discrete-Time Linear Systems with Sparse Inputs},
url = {https://mallada.ece.jhu.edu/pubs/2024-Preprint-PMV.pdf},
year = {2024}
}