Real-time Sampling and Estimation

Shirin Saeedi Bidokhti, Assistant Professor, University of Pennsylvania

The Internet of Things (IoT) and social networks have provided unprecedented information platforms. The information is often governed by processes that evolve over time and/or space (e.g., on an underlying graph) and they may not be stationary or stable. We seek to devise efficient strategies to collect real-time information for timely estimation and inference. This is critical for learning and control. In the first part of the talk, we focus on the problem of real-time sampling and estimation of autoregressive Markov processes over random access channels. For the class of policies in which decision making has to be independent of the source realizations, we make a bridge with the recent notion of Age of Information (AoI) to devise novel distributed policies that utilize local AoI for decision making. We also provide strong guarantees for the performance of the proposed policies. More generally, allowing decision making to be dependent on the source realizations, we propose distributed policies that improve upon the state of the art by a factor of approximately six. Furthermore, we numerically show the surprising result that despite being decentralized, our proposed policy has a performance very close to that of centralized scheduling.

In the second part of the talk, we go beyond time-evolving processes by looking at spread processes that are defined over time as well as an underlying network. We consider the spread of an infectious disease such as COVID-19 in a network of people and design sequential testing (and isolation) strategies to contain the spread. To this end, we develop a probabilistic framework to sequentially learn nodes’ probabilities of infection (using test observations) by an efficient backward-forward update algorithm that first infers about the state of the relevant nodes in the past before propagating that forward into future. We further argue that if nodes’ probabilities of infection were accurately known at each time, exploitation-based policies that test the most likely nodes are myopically optimal in a relevant class of policies. However, when our belief about the probabilities is wrong, exploitation can be arbitrarily bad, as we provably show, while a policy that combines exploitation with random testing can contain the spread faster. Accordingly, we propose exploration policies in which nodes are tested probabilistically based on our estimated probabilities of infection Using simulations, we show in several interesting settings how exploration helps contain the spread by detecting more infected nodes, in a timely manner, and by providing a more accurate estimate of the nodes’ probabilities of infection.


Shirin Saeedi Bidokhti is an assistant professor in the Department of Electrical and Systems Engineering at the University of Pennsylvania (UPenn). She received her M.Sc. and Ph.D. degrees in Computer and Communication Sciences from the Swiss Federal Institute of Technology (EPFL). Prior to joining UPenn, she was a postdoctoral scholar at Stanford University and the Technical University of Munich. She has also held short-term visiting positions at ETH Zurich, University of California at Los Angeles, and the Pennsylvania State University. Her research interests broadly include the design and analysis of network strategies that are scalable, practical, and efficient for use in Internet of Things (IoT) applications, information transfer on networks, as well as data compression techniques for big data. She is a recipient of the 2022 IT society Goldsmith lecturer award, 2021 NSF-CAREER award, 2019 NSF-CRII Research Initiative award and the prospective researcher and advanced postdoctoral fellowships from the Swiss National Science Foundation.


You may also like

Page 1 of 3