November 2, 2023
The problem of learning dynamical models from data is of great importance for Cyber-Physical Systems (CPS) since models form the basis for key design and verification tasks. However, models of CPS inherently switch between different dynamical modes. Learning switched models known to be NP-hard even for relatively simple dynamics. Most algorithms based on SAT-modulo theory solvers or mixed-integer linear programming solvers run in time that is exponential in the number of data points, which makes them expensive for all but the smallest of data sets.
We show how reformulating the decision problem as a “promise problem” (a well-known idea in computational complexity theory) surprisingly yields an algorithm that is linear time in the number of data points with an exponential dependence on the dimensionality of the state-space. This is achieved using the idea of separation oracles from convex optimization. The resulting algorithm also turns out to be practical for relatively large datasets in low dimensions. We also look at some of the interesting applications of our work and compare its performance against standard machine learning approaches. The talk will be self-contained, and all relevant concepts will be introduced during the talk.
Joint work, mainly with Monal Narasimhamurthy and Guillaume Berger.
About Sriram Sankaranarayanan
Sriram Sankaranarayanan is a professor of Computer Scienceat the University of Colorado, Boulder. His research interests include automatic techniques for reasoning about the behavior of computer and cyber-physical systems. Sriram obtained a PhD in 2005 from Stanford University where he was advised by Zohar Manna and Henny Sipma. Subsequently he worked as a research staff member at NEC research labs in Princeton, NJ. He has been on the faculty at CU Boulder since 2009. Sriram has been the recipient of awards including the President’s Gold Medal from IIT Kharagpur (2000), Siebel Scholarship (2005), the CAREER award from NSF (2009), Dean’s award for outstanding junior faculty (2012), outstanding teaching (2014), the Provost’s faculty achievement award (2014) and the Coursera outstanding innovation award (2022).