More Like this

1. Efficient and passive learning of networked dynamical systems driven by non-white exogenous inputs

   Harish Doddi, Deepjyoti Deka (May 2022, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics)

   We consider a networked linear dynamical system with p agents/nodes. We study the problem of learning the underlying graph of interactions/dependencies from observations of the nodal trajectories over a time-interval T. We present a regularized non-casual consistent estimator for this problem and analyze its sample complexity over two regimes: (a) where the interval T consists of n i.i.d. observation windows of length T/n (restart and record), and (b) where T is one continuous observation window (consecutive). Using the theory of M-estimators, we show that the estimator recovers the underlying interactions, in either regime, in a time-interval that is logarithmic in the system size p. To the best of our knowledge, this is the first work to analyze the sample complexity of learning linear dynamical systems driven by unobserved not-white wide-sense stationary (WSS) inputs. 

   more » « less
2. Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs

   Veedu, Mishfad; Deka, Deepjyoti; Salapaka, Murti (May 2024, Proceedings of Machine Learning Research)

   Dasgupta, Sanjoy; Mandt, Stephen; Li, Yingzhen i (Ed.)

   In this article, the optimal sample complexity of learning the underlying interactions or dependencies of a Linear Dynamical System (LDS) over a Directed Acyclic Graph (DAG) is studied. We call such a DAG underlying an LDS as dynamical DAG (DDAG). In particular, we consider a DDAG where the nodal dynamics are driven by unobserved exogenous noise sources that are wide-sense stationary (WSS) in time but are mutually uncorrelated, and have the same power spectral density (PSD). Inspired by the static DAG setting, a metric and an algorithm based on the PSD matrix of the observed time series are proposed to reconstruct the DDAG. It is shown that the optimal sample complexity (or length of state trajectory) needed to learn the DDAG is n = Θ(q log(p/q)), where p is the number of nodes and q is the maximum number of parents per node. To prove the sample complexity upper bound, a concentration bound for the PSD estimation is derived, under two different sampling strategies. A matching min-max lower bound using generalized Fano’s inequality also is provided, thus showing the order optimality of the proposed algorithm. The codes used in the paper are available at https://github.com/Mishfad/Learning-Dynamical-DAGs 

   more » « less
3. Learning the Topology and Behavior of Discrete Dynamical Systems

   https://doi.org/10.1609/aaai.v38i13.29390  

   Qiu, Zirou; Adiga, Abhijin; Marathe, Madhav V; Ravi, S S; Rosenkrantz, Daniel J; Stearns, Richard E; Vullikanti, Anil (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems. 

   more » « less
4. FedSysID: A Federated Approach to Sample-Efficient System Identification

   Wang, H.; Toso, L.F.; Anderson, J. (June 2023, Proceedings of Machine Learning Research)

   Matni, N.; Morari, M; Pappas, G. (Ed.)

   We study the problem of learning a linear system model from the observations of M clients. The catch: Each client is observing data from a different dynamical system. This work addresses the question of how multiple clients collaboratively learn dynamical models in the presence of heterogeneity. We pose this problem as a federated learning problem and characterize the tension between achievable performance and system heterogeneity. Furthermore, our federated sample complexity result provides a constant factor improvement over the single agent setting. Finally, we describe a meta federated learning algorithm, FedSysID, that leverages existing federated algorithms at the client level. 

   more » « less
5. Towards Testing Monotonicity of Distributions Over General Posets

   Alaikbarpour, A.; Gouleakis, T.; Peebles, J.; Rubinfeld, R.; Yodpinyanee, A (January 2019, Proceedings of the Thirty-Second Conference on Learning Theory (COLT 2019))

   In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution p over a poset is monotone if, for any pair of domain elements x and y such that x ⪯ y, p(x) ≤ p(y). To understand the sample complexity of this problem, we introduce a new property called bigness over a finite domain, where the distribution is T-big if the minimum probability for any domain element is at least T. We establish a lower bound of Ω(n/ log n) for testing bigness of distributions on domains of size n. We then build on these lower bounds to give Ω(n/ log n) lower bounds for testing monotonicity over a matching poset of size n and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem. The previous lower bound for testing Monotonicity of 

   more » « less