LAWS acquisition lower bound for stationary online caching

Let $P_{\mathcal{M}}$ range over stationary distributions with entropy $H$, and let $N$ be the number of queries. LAWS acquisition lower bound. No online inference caching algorithm can achieve acquisition cost $o(2^{H(P_{\mathcal{M}})}\cdot\log N)$ expert creations in the worst case over these distributions.

The proposed information-theoretic argument uses a distribution with $2^H$ equally probable heavy nodes and the coupon-collector lower bound for discovering them online. A formal treatment must handle adaptive query distributions; the source further claims this establishes acquisition optimality for LAWS.