Enrique Mallada

2 papers accpeted to CDC

by

Our paper on non-monotonic Lyapunov functions [1] and our paper on simultaneous state and sparse input recovery [2] have been accepted to the Conference on Decision and Control 2023!

[1] [doi] R. Siegelmann, Y. Shen, F. Paganini, and E. Mallada, “A Recurrence-based Direct Method for Stability Analysis and GPU-based Verification of Non-monotonic Lyapunov Functions,” in 62nd IEEE Conference on Decision and Control (CDC), 2023, pp. 6665-6672.
[Bibtex] [Abstract] [Download PDF]

Lyapunov direct method is a powerful tool that provides a rigorous framework for stability analysis and control design for dynamical systems. A critical step that enables the application of the method is the existence of a Lyapunov function $V$—a function whose value monotonically decreases along the trajectories of the dynamical system. Unfortunately, finding a Lyapunov function is often tricky and requires ingenuity, domain knowledge, or significant computational power. At the core of this challenge is the fact that the method requires every sub-level set of $V$ ($V_łeq c$) to be forward invariant, thus implicitly coupling the geometry of $V_łeq c$ and the trajectories of the system. In this paper, we seek to disentangle this dependence by developing a direct method that substitutes the concept of invariance with a more flexible notion known as recurrence. A set is ($τ$-)recurrent if every trajectory that starts in the set returns to it (within $τ$ seconds) infinitely often. We show that, under mild conditions, the recurrence of level sub-level sets is sufficient to guarantee stability, asymptotic stability, and exponential stability. We further provide a GPU-based algorithm that can to verify whether $V$ satisfies such conditions up to an arbitrarily small subset of the equilibrium.

@inproceedings{sspm2023cdc,
  abstract = {Lyapunov direct method is a powerful tool that provides a rigorous framework for stability analysis and control design for dynamical systems. A critical step that enables the application of the method is the existence of a Lyapunov function $V$---a function whose value monotonically decreases along the trajectories of the dynamical system. Unfortunately, finding a Lyapunov function is often tricky and requires ingenuity, domain knowledge, or significant computational power. At the core of this challenge is the fact that the method requires every sub-level set of $V$ ($V_łeq c$) to be forward invariant, thus implicitly coupling the geometry of $V_łeq c$ and the trajectories of the system. In this paper, we seek to disentangle this dependence by developing a direct method that substitutes the concept of invariance with a more flexible notion known as recurrence. A set is ($τ$-)recurrent if every trajectory that starts in the set returns to it (within $τ$ seconds) infinitely often. We show that, under mild conditions,  the recurrence of level sub-level sets is sufficient to guarantee stability, asymptotic stability, and exponential stability. We further provide a GPU-based algorithm that can to verify whether $V$ satisfies such conditions up to an arbitrarily small subset of the equilibrium.},
  author = {Siegelmann, Roy and Shen, Yue and Paganini, Fernando and Mallada, Enrique},
  bdsk-url-3 = {https://doi.org/10.1109/CDC49753.2023.10383373},
  booktitle = {62nd IEEE Conference on Decision and Control (CDC)},
  doi = {10.1109/CDC49753.2023.10383373},
  grants = {CPS-2136324, CAREER-1752362, EPICS-2330450},
  month = {12},
  organization = {IEEE},
  pages = {6665--6672},
  record = {presented, accepted Jul 2023, submitted Mar 2023},
  title = {A Recurrence-based Direct Method for Stability Analysis and GPU-based Verification of Non-monotonic Lyapunov Functions},
  url = {https://mallada.ece.jhu.edu/pubs/2023-CDC-SSPM.pdf},
  year = {2023}
}
[2] [doi] K. Poe, E. Mallada, and R. Vidal, “Necessary and Sufficient Conditions for Simultaneous State and Input Recovery of Linear Systems with Sparse Inputs by $\ell_1$-Minimization,” in 62nd IEEE Conference on Decision and Control (CDC), 2023, pp. 6499-6506.
[Bibtex] [Abstract] [Download PDF]

The study of theoretical conditions for recovering sparse signals from compressive measurements has received a lot of attention in the research community. In parallel, there has been a great amount of work characterizing conditions for the recovery both the state and the input to a linear dynamical system (LDS), including a handful of results on recovering sparse inputs. However, existing sufficient conditions for recovering sparse inputs to an LDS are conservative and hard to interpret, while necessary and sufficient conditions have not yet appeared in the literature. In this work, we provide (1) the first characterization of necessary and sufficient conditions for the existence and uniqueness of sparse inputs to an LDS, (2) the first necessary and sufficient conditions for a linear program to recover both an unknown initial state and a sparse input, and (3) simple, interpretable recovery conditions in terms of the LDS parameters. We conclude with a numerical validation of these claims and discuss implications and future directions. 

@inproceedings{pmv2023cdc,
  abstract = {The study of theoretical conditions for recovering sparse signals from compressive measurements has received a lot of attention in the research community. In parallel, there has been a great amount of work characterizing conditions for the recovery both the state and the input to a linear dynamical system (LDS), including a handful of results on recovering sparse inputs. However, existing sufficient conditions for recovering sparse inputs to an LDS are conservative and hard to interpret, while necessary and sufficient conditions have not yet appeared in the literature. In this work, we provide (1) the first characterization of necessary and sufficient conditions for the existence and uniqueness of sparse inputs to an LDS, (2) the first necessary and sufficient conditions for a linear program to recover both an unknown initial state and a sparse input, and (3) simple, interpretable recovery conditions in terms of the LDS parameters. We conclude with a numerical validation of these claims and discuss implications and future directions.
},
  author = {Poe, Kyle and Mallada, Enrique and Vidal, Rene},
  bdsk-url-3 = {https://doi.org/10.1109/CDC49753.2023.10383682},
  booktitle = {62nd IEEE Conference on Decision and Control (CDC)},
  doi = {10.1109/CDC49753.2023.10383682},
  grants = {CPS-2136324,CAREER-1752362},
  month = {12},
  pages = {6499--6506},
  record = {presented, accepted Jul 2023, submitted Mar 2023},
  title = {Necessary and Sufficient Conditions for Simultaneous State and Input Recovery of Linear Systems with Sparse Inputs by $\ell_1$-Minimization},
  url = {https://mallada.ece.jhu.edu/pubs/2023-CDC-PMV.pdf},
  year = {2023}
}

1 paper accepted to ICML

by

Our paper on convergence of gradient flow on multi-layer linear networks [1] has been accepted to International Conference on Machine Learning! Congrats Hancheng!

[1] H. Min, R. Vidal, and E. Mallada, “On the Convergence of Gradient Flow on Multi-layer Linear Models,” in International Conference on Machine Learning (ICML), 2023, pp. 1-8.
[Bibtex] [Abstract] [Download PDF]

In this paper, we analyze the convergence of gra- dient flow on a multi-layer linear model with a loss function of the form f(W1W2···WL). We show that when fsatisfies the gradient dominance property, proper weight initialization leads to ex- ponential convergence of the gradient flow to a global minimum of the loss. Moreover, the con- vergence rate depends on two trajectory-specific quantities that are controlled by the weight initial- ization: the imbalance matrices , which measure the difference between the weights of adjacent layers, and the least singular value of the weight product W=W1W2···WL. Our analysis ex- ploits the fact that the gradient of the overparam- eterized loss can be written as the composition of the non-overparametrized gradient with a time- varying (weight-dependent) linear operator whose smallest eigenvalue controls the convergence rate. The key challenge we address is to derive a uni- form lower bound for this time-varying eigenvalue that lead to improved rates for several multi-layer network models studied in the literature.

@inproceedings{mvm2023icml,
  abstract = {In this paper, we analyze the convergence of gra- dient flow on a multi-layer linear model with a loss function of the form f(W1W2···WL). We show that when fsatisfies the gradient dominance property, proper weight initialization leads to ex- ponential convergence of the gradient flow to a global minimum of the loss. Moreover, the con- vergence rate depends on two trajectory-specific quantities that are controlled by the weight initial- ization: the imbalance matrices , which measure the difference between the weights of adjacent layers, and the least singular value of the weight product W=W1W2···WL. Our analysis ex- ploits the fact that the gradient of the overparam- eterized loss can be written as the composition of the non-overparametrized gradient with a time- varying (weight-dependent) linear operator whose smallest eigenvalue controls the convergence rate. The key challenge we address is to derive a uni- form lower bound for this time-varying eigenvalue that lead to improved rates for several multi-layer network models studied in the literature.},
  author = {Min, Hancheng and Vidal, Rene and Mallada, Enrique},
  bdsk-url-3 = {https://mallada.ece.jhu.edu/pubs/2023-ICML-MVM.pdf},
  booktitle = {International Conference on Machine Learning (ICML)},
  grants = {TRIPODS-1934979, CAREER-1752362},
  month = {4},
  pages = {1-8},
  record = {presented Jul. 2023, accepted Apr. 2023, submitted Jan. 2023},
  title = {On the Convergence of Gradient Flow on Multi-layer Linear Models},
  url = {https://mallada.ece.jhu.edu/pubs/2023-ICML-MVM.pdf},
  year = {2023}
}

1 paper accepted to L4DC

by

Our paper on learning coherent clusters in weakly-connected network systems [1] has been accepted to the 5th Annual Learning for Dynamics and Control Conference. Congrats Hancheng!

[1] H. Min and E. Mallada, “Learning Coherent Clusters in Weakly-Connected Network Systems,” in Proceedings of The 5th Annual Learning for Dynamics and Control Conference, 2023, pp. 1167-1179.
[Bibtex] [Abstract] [Download PDF]

We propose a structure-preserving model-reduction methodology for large-scale dynamic networks with tightly-connected components. First, the coherent groups are identified by a spectral clustering algorithm on the graph Laplacian matrix that models the network feedback. Then, a reduced network is built, where each node represents the aggregate dynamics of each coherent group, and the reduced network captures the dynamic coupling between the groups. We provide an upper bound on the approximation error when the network graph is randomly generated from a weight stochastic block model. Finally, numerical experiments align with and validate our theoretical findings.

@inproceedings{mm2023l4dc,
  abstract = {We propose a structure-preserving model-reduction methodology for large-scale dynamic networks with tightly-connected components. First, the coherent groups are identified by a spectral clustering algorithm on the graph Laplacian matrix that models the network feedback. Then, a reduced network is built, where each node represents the aggregate dynamics of each coherent group, and the reduced network captures the dynamic coupling between the groups. We provide an upper bound on the approximation error when the network graph is randomly generated from a weight stochastic block model. Finally, numerical experiments align with and validate our theoretical findings.},
  author = {Min, Hancheng and Mallada, Enrique},
  booktitle = {Proceedings of The 5th Annual Learning for Dynamics and Control Conference},
  editor = {Matni, Nikolai and Morari, Manfred and Pappas, George J.},
  grants = {CAREER-1752362, TRIPODS-1934979, CPS-2136324},
  month = {6},
  pages = {1167--1179},
  publisher = {PMLR},
  record = {presented, accepted Mar 2022, submitted Nov 2022},
  series = {Proceedings of Machine Learning Research},
  title = {Learning Coherent Clusters in Weakly-Connected Network Systems},
  url = {https://mallada.ece.jhu.edu/pubs/2023-L4DC-MM.pdf},
  volume = {211},
  year = {2023}
}

1 paper published in TAC

by

Our paper on the role of interconnection directionality in the quadratic performance of double-integrator networks [1] has been published in the IEEE Transactions on Automatic Control.

[1] [doi] G. H. Oral, E. Mallada, and D. Gayme, “On the Role of Interconnection Directionality in the Quadratic Performance of Double-Integrator Networks,” IEEE Transactions on Automatic Control, vol. 67, iss. 11, pp. 6211-6218, 2022.
[Bibtex] [Abstract] [Download PDF]

This note provides a quantitative and qualitative eval- uation of the role of interconnection directionality in a general class of quadratic performance metrics for double-integrator net- works. We first develop an analysis framework that can be used to evaluate the quadratic performance metrics of networks defined over a general class of directed graphs. A comparison between systems whose directed graph Laplacians are normal and their undirected counterparts unveils an interplay between the inter- connection directionality and the control strategy that determines network performance. We show that directionality can significantly degrade performance; however well-designed feedback can exploit directionality to mitigate this degradation or even improve perfor- mance.

@article{omg2022tac,
  abstract = {This note provides a quantitative and qualitative eval- uation of the role of interconnection directionality in a general class of quadratic performance metrics for double-integrator net- works. We first develop an analysis framework that can be used to evaluate the quadratic performance metrics of networks defined over a general class of directed graphs. A comparison between systems whose directed graph Laplacians are normal and their undirected counterparts unveils an interplay between the inter- connection directionality and the control strategy that determines network performance. We show that directionality can significantly degrade performance; however well-designed feedback can exploit directionality to mitigate this degradation or even improve perfor- mance.},
  author = {Oral, H. Giray and Mallada, Enrique and Gayme, Dennice},
  bdsk-url-3 = {https://doi.org/10.1109/TAC.2021.3135358},
  doi = {10.1109/TAC.2021.3135358},
  grants = {ENERGISE-DE-EE0008006, EPCN-1711188,AMPS-1736448, CPS-1544771, CAREER-1752362, AMPS-1736448, ARO-W911NF-17-1-0092},
  journal = {IEEE Transactions on Automatic Control},
  month = {11},
  number = {11},
  pages = {6211-6218},
  record = {published, online Dec. 2021, accepted Nov. 2021, conditionally accepted Apr 2021, revised Nov. 2020, submitted Nov. 2019},
  title = {On the Role of Interconnection Directionality in the Quadratic Performance of Double-Integrator Networks},
  url = {https://mallada.ece.jhu.edu/pubs/2022-TAC-OMG.pdf},
  volume = {67},
  year = {2022}
}

Jay defended his dissertation

by

Jay Guthrie, an ECE Ph.D. student in our lab, defended his dissertation entitled “Novel Representations of Semialgebraic Sets Arising in Planning and Control” on Friday, October 21st. Congratulations!

1 paper accepted to Asilomar

by

Our paper on constrained reinforcement learning via dissipative saddle flow dynamics [1] has been accepted to the 56th Asilomar Conference on Signals, Systems, and Computers. Congrats Tianqi!

[1] [doi] T. Zheng, P. You, and E. Mallada, “Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamics,” in 56th Asilomar Conference on Signals, Systems, and Computers, 2022, pp. 1362-1366.
[Bibtex] [Abstract] [Download PDF]

In constrained reinforcement learning (C-RL), an agent seeks to learn from the environment a policy that maximizes the expected cumulative reward while satisfying minimum requirements in secondary cumulative reward con- straints. Several algorithms rooted in sampled-based primal- dual methods have been recently proposed to solve this problem in policy space. However, such methods are based on stochastic gradient descent-ascent algorithms whose trajectories are con- nected to the optimal policy only after a mixing output stage that depends on the algorithm’s history. As a result, there is a mismatch between the behavioral policy and the optimal one. In this work, we propose a novel algorithm for constrained RL that does not suffer from these limitations. Leveraging recent results on regularized saddle-flow dynamics, we develop a novel stochastic gradient descent-ascent algorithm whose trajectories converge to the optimal policy almost surely.

@inproceedings{zym2022asilomar,
  abstract = {In constrained reinforcement learning (C-RL), an agent seeks to learn from the environment a policy that maximizes the expected cumulative reward while satisfying minimum requirements in secondary cumulative reward con- straints. Several algorithms rooted in sampled-based primal- dual methods have been recently proposed to solve this problem in policy space. However, such methods are based on stochastic gradient descent-ascent algorithms whose trajectories are con- nected to the optimal policy only after a mixing output stage that depends on the algorithm's history. As a result, there is a mismatch between the behavioral policy and the optimal one. In this work, we propose a novel algorithm for constrained RL that does not suffer from these limitations. Leveraging recent results on regularized saddle-flow dynamics, we develop a novel stochastic gradient descent-ascent algorithm whose trajectories converge to the optimal policy almost surely.},
  author = {Zheng, Tianqi and You, Pengcheng and Mallada, Enrique},
  bdsk-url-3 = {https://doi.org/10.1109/IEEECONF56349.2022.10052060},
  booktitle = {56th Asilomar Conference on Signals, Systems, and Computers},
  doi = {10.1109/IEEECONF56349.2022.10052060},
  grants = {CAREER-1752362, TRIPODS-1934979, CPS-2136324},
  month = {12},
  pages = {1362-1366},
  record = {presented Dec. 2022, accepted Sep. 2022, submitted Apr. 2022},
  title = {Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamics},
  url = {https://mallada.ece.jhu.edu/pubs/2022-Asilomar-ZYM.pdf},
  year = {2022}
}