We consider the problem of correctly identifying the MODE of a discrete distribution 𝒫 with sufficiently high probability by observing a sequence of i.i.d. samples drawn from 𝒫. This problem reduces to the estimation of a single parameter when 𝒫 has a support set of size K equals 2. After noting that this special case is tackled very well by prior-posterior-ratio (PPR) martingale confidence sequences (Waudby-Smith and Ramdas, 2020), we propose a generalization to mode estimation, in which 𝒫 may take K greater than or equal to 2 values. To begin, we show that the "one-versus-one" principle to generalize from K equals 2 to K greater than or equals 2 classes is more efficient than the "one-versus-rest" alternative. We then prove that our resulting stopping rule, denoted PPR-1v1, is asymptotically optimal (as the mistake probability is taken to 0). PPR-1v1 is parameter-free and computationally light, and incurs significantly fewer samples than competitors even in the non-asymptotic regime. We demonstrate its gains in two practical applications of sampling: election forecasting and verification of smart contracts in blockchains.
Prof. Shivaram Kalyanakrishnan, IIT Bombay
Shivaram Kalyanakrishnan is an Associate Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Bombay. His research interests include artificial intelligence and machine learning, spanning topics such as sequential decision making, multi-agent learning, multi-armed bandits, and humanoid robotics. Kalyanakrishnan received a Ph.D. in computer science from the University of Texas at Austin. Subsequently he was a Research Scientist at Yahoo Labs Bangalore and an INSPIRE Faculty Fellow at the Indian Institute of Science,Bangalore. His contributions to robot soccer have received two Best Student Paper awards at the annual RoboCup competitions. Kalyanakrishnan was also a member of the first study panel of the One Hundred Year Study on Artificial Intelligence (AI100), which in 2016 released its report titled "Artificial Intelligence and Life in 2030".