Synapse

 

Monthly Newsletter from CNI

Issue - September 2023

PAC Mode Estimation using PPR Martingale Confidence Sequences    

August 2

Prof. Shivaram Kalyanakrishnan discussed a Probably Approximately Correct (PAC) algorithm for mode estimation in a discrete distribution with K classes, aiming to minimize sample size. They generalize prior work by Waudby-Smith and Ramdas, who solved K=2 using PPR (prior posterior ratio) martingale confidence sequences. This method has practical applications in fields like election forecasting and blockchain contract verification.

 
Almost-Optimal Best Restless Markov Arm Identification with Fixed Confidence 

August 17

In this talk, Dr. P N Karthik discussed recent results on identifying the best arm in a restless multi-armed bandit with fixed confidence. The scenario involves multiple arms modeled as homogenous discrete-time Markov chains with unknown transition probabilities. The goal is to find the best-performing arm while minimizing the expected stopping time given constraints on the error probability. The results include asymptotic lower bounds on expected stopping time and an optimal best arm identification policy whose expected stopping time satisfies an asymptotic growth rate that matches with the lower bound and is hence asymptotically optimal.

Understanding Internet Resilience to Planetary-Scale Risks  

August 22

Prof Sangeetha Abdu Jyothi talked about large-scale threats to our Internet infrastructure such as the cosmic phenomenon of solar superstorms, which can potentially cause large-scale global Internet outages lasting for several months. She talks about the robustness of the current internet infrastructure against this threat as well as the resilience challenges arising from the dependence of internet on the power grid. The talk ended with a roadmap for improving the Internet’s resilience to such risks followed by a discussion of open research challenges in this direction.