Skip to yearly menu bar Skip to main content


PAC Learnability of Node Functions in Networked Dynamical Systems

Abhijin Adiga · Chris J Kuhlman · Madhav Marathe · S. S. Ravi · Anil Vullikanti

Pacific Ballroom #184

Keywords: [ Supervised Learning ] [ Optimization - Others ] [ Computational Learning Theory ] [ Combinatorial Optimization ]


We consider the PAC learnability of the local functions at the vertices of a discrete networked dynamical system, assuming that the underlying network is known. Our focus is on the learnability of threshold functions. We show that several variants of threshold functions are PAC learnable and provide tight bounds on the sample complexity. In general, when the input consists of positive and negative examples, we show that the concept class of threshold functions is not efficiently PAC learnable, unless NP = RP. Using a dynamic programming approach, we show efficient PAC learnability when the number of negative examples is small. We also present an efficient learner which is consistent with all the positive examples and at least (1-1/e) fraction of the negative examples. This algorithm is based on maximizing a submodular function under matroid constraints. By performing experiments on both synthetic and real-world networks, we study how the network structure and sample complexity influence the quality of the inferred system.

Live content is unavailable. Log in and register to view live content