Agnostic insurance tasks and their relation to compression
Narayana Santhanam, Venkat Anantharam · 2012
We consider the following insurance problem: our task is to predict finite upper bounds on unseen samples of an unknown distribution p over the set of natural numbers, using only observations generated i.i.d. from p. While p is unknown, it belongs to a known collection P of possible models. To emphasize, the support of the unknown distribution p is unbounded, and the game proceeds for an infinitely long time. If the said upper bounds are accurate over the infinite time window with probability arbitrarily close to 1, we say P is insurable. We have previously characterized insurability of P by a condition on the neighborhoods of distributions in P, one that is both necessary and sufficient. We examine connections between the insurance problem on the one hand, and weak and strong universal compression on the other. We show that if P can be strongly compressed, it can be insured as well. However, the connection with weak compression is more subtle. We show by constructing appropriate classes of distributions that neither weak compression nor insurability implies the other.