Timezone: »
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.
Author Information
Abhijin Adiga (University of Virginia)
Chris J Kuhlman (Biocomplexity Institute & Initiative, University of Virginia)
Madhav Marathe (Biocomplexity Institute & Initiative, University of Virginia)
S. S. Ravi (University of Virginia and University at Albany -- SUNY)
Anil Vullikanti (Biocomplexity Institute and Dept of Computer Science, University of Virginia)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: PAC Learnability of Node Functions in Networked Dynamical Systems »
Wed. Jun 12th 01:30 -- 04:00 AM Room Pacific Ballroom
More from the Same Authors
-
2022 Poster: Differentially Private Community Detection for Stochastic Block Models »
Mohamed Mohamed · Dung Nguyen · Anil Vullikanti · Ravi Tandon -
2022 Spotlight: Differentially Private Community Detection for Stochastic Block Models »
Mohamed Mohamed · Dung Nguyen · Anil Vullikanti · Ravi Tandon -
2022 Poster: Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries »
Daniel Rosenkrantz · Abhijin Adiga · Madhav Marathe · Zirou Qiu · S. S. Ravi · Richard Stearns · Anil Vullikanti -
2022 Spotlight: Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries »
Daniel Rosenkrantz · Abhijin Adiga · Madhav Marathe · Zirou Qiu · S. S. Ravi · Richard Stearns · Anil Vullikanti -
2021 Poster: Differentially Private Densest Subgraph Detection »
Dung Nguyen · Anil Vullikanti -
2021 Spotlight: Differentially Private Densest Subgraph Detection »
Dung Nguyen · Anil Vullikanti -
2021 Poster: PAC-Learning for Strategic Classification »
Ravi Sundaram · Anil Vullikanti · Haifeng Xu · Fan Yao -
2021 Oral: PAC-Learning for Strategic Classification »
Ravi Sundaram · Anil Vullikanti · Haifeng Xu · Fan Yao