PAC Mode Estimation using PPR Martingale Confidence Sequences
This work addresses mode estimation for discrete distributions, which is incremental as it builds on prior PPR martingale confidence sequences for binary cases.
The paper tackles the problem of identifying the mode of a discrete distribution with high probability using i.i.d. samples, proposing a method called PPR-1v1 that generalizes from binary to multi-class cases. It shows that PPR-1v1 is asymptotically optimal, parameter-free, computationally efficient, and incurs significantly fewer samples than competitors, with demonstrated gains in election forecasting and smart contract verification.
We consider the problem of correctly identifying the \textit{mode} of a discrete distribution $\mathcal{P}$ with sufficiently high probability by observing a sequence of i.i.d. samples drawn from $\mathcal{P}$. This problem reduces to the estimation of a single parameter when $\mathcal{P}$ has a support set of size $K = 2$. After noting that this special case is tackled very well by prior-posterior-ratio (PPR) martingale confidence sequences \citep{waudby-ramdas-ppr}, we propose a generalisation to mode estimation, in which $\mathcal{P}$ may take $K \geq 2$ values. To begin, we show that the "one-versus-one" principle to generalise from $K = 2$ to $K \geq 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.