Is uniform convergence faster for low-entropy distributions?

Question

Let $\mathcal D$ be a probability distribution on $\{0,1\}^d$. Let $X_1, \cdots, X_n \in \{0,1\}^d$ be i.i.d. samples from $\mathcal D$. Let $\mu \in [0,1]^d$ be the mean of $\mathcal D$ and let $\overline X = \frac{1}{n} \sum_{i=1}^n X_i \in [0,1]^d$ be the mean of the samples.

By Hoeffding's inequality and a union bound, $$\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le 2d \cdot e^{-2n\varepsilon^2}$$ for all $\varepsilon \ge 0$. Equivalently, for $\varepsilon,\delta>0$, if $n \ge \frac{\log(2d/\delta)}{2\varepsilon^2}$, then $\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le \delta$.

This bound is tight (up to constants) in the worst case. In particular, the uniform distribution achieves this bound.

My question is whether better bounds are known if we know that $\mathcal D$ has low entropy.

Obviously, if $\mathcal D$ has no entropy (i.e., $\mathcal D$ is a point mass) then one sample is enough for perfect convergence. If the entropy is maximal, then $\mathcal D$ is the uniform distribution and the above bound is tight. What if the entropy is intermediate, e.g., $\mathsf H(\mathcal D) = \Theta(\log d)$? Could we replace $d$ with, say, $\mathsf H(\mathcal D)$ in the above bounds?

---

Some remarks about how I came to this question:

Let's imagine you are running the Multiplicative Weights algorithm for online learning or solving a repeated zero-sum game. Typically we assume that it outputs a full probability distribution at each step and the loss/gain is exactly the expectation over this distribution. What happens if we cannot output the whole distribution?

If you only output one sample from the MW distribution, then the environment/adversary/other player can best-respond to that move and force the MW algorithm to suffer large loss/small gain. So one sample is insufficient to retain the no-regret guarantee.

What if instead you have $n$ samples from the MW distribution? If $n$ is large enough, uniform convergence kicks in and the empirical distribution of the sample is close to the desired MW distribution and you get the no regret guarantee with high probability.

So the question is how many samples $n$ do you need from the multiplicative weights distribution to get the desired uniform convergence? One thing to note is that the entropy of the MW distribution decreases with each step. (Entropy is one way to analyze the MW algorithm.) So I was hoping that one could show that, as the MW algorithm proceeds, fewer and fewer samples are needed. That led to this question, which I think is interesting in its own right.

My question about MW arose from reading this paper. Here there is a specific cost to each sample from the MW distribution and that cost grows linearly with the number of time steps. Thus, if we could show that, in the final steps where the entropy is low (since MW has converged) and the cost is high, fewer samples are needed, then this might improve the algorithm.

Answer 1

This is very much a partial answer to my question. I'm hoping for a much better bound (or a counterexample). I managed to show a very weak bound. It is not very useful, but it does at least show that uniform convergence can be bounded using entropy.

As Aryeh observes, it suffices to bound $\mathbb{E}[\|\overline X - \mu\|_\infty]$.

First, use the duality between the $\infty$-norm and the $1$-norm: Let $$Y = \underset{\|y\|_1 \le 1}{\mathsf{argmax}} ~~ \langle y, \overline X - \mu \rangle$$ so that $\langle Y, \overline X - \mu \rangle = \|\overline X - \mu \|_\infty$. Note that we may assume $Y$ is a deterministic function of $\overline X$ and that it is supported on the standard basis vectors and their negations.

Next, we use a simple (yet magical) inequality: For all random variables $U,V$ on $\Omega$ and all $f : \Omega \to \mathbb{R}$ (such that everything is well-defined), $$\mathbb{E}[f(U)] \le \mathsf{D}(U\|V) + \log \mathbb{E}[e^{f(V)}].$$ For simplicity, I'm using natural logs (rather than binary logs) even for information theoretic quantities like the KL divergence.

I'm going to apply this with $U = (\overline X, Y)$ and $V = \overline X \times Y$ (i.e., $V$ is a product distribution whose marginals match those of $U$) and $f(x,y) = \lambda \cdot \langle y, x - \mu \rangle$ for some $\lambda > 0$. Thus the divergence is the mutual information: $\mathsf{D}(U\|V) = \mathsf{I}(\overline X; Y)$. Then we have $$\lambda \cdot \mathbb{E}[\|\overline X - \mu\|_\infty] = \mathbb{E}[f(\overline X, Y)] \le \mathsf{I}(\overline X; Y) + \max_y\log\mathbb{E}[e^{\lambda \cdot \langle y, \overline X-\mu\rangle}] \le \mathsf{I}(\overline X; Y) + \log(e^{\lambda^2/8n}),$$ where the final inequality uses Hoeffding's lemma. Rearranging yields $$\mathbb{E}[\|\overline X - \mu\|_\infty] \le \inf_{\lambda > 0} \frac{1}{\lambda}\left(\mathsf{I}(\overline X; Y) + \frac{\lambda^2}{8n}\right) = \sqrt{\frac{\mathsf{I}(\overline X;Y)}{2n}}.$$

Now it only remains to bound $\mathsf{I}(\overline X;Y)$.

Note that, since $Y$ is assumed to be supported on a set of size $2d$, we have $\mathsf{I}(\overline X;Y) \le \mathsf{H}(Y) \le \log(2d)$, which gives $\mathbb{E}[\|\overline X - \mu \|_\infty] \le \sqrt{\log(2d)/2n}$. This corresponds to the worst-case union bound.

We also have $$\mathsf{I}(\overline X;Y) \le \mathsf{H}(\overline X) \le \mathsf{H}(X_1, \cdots, X_n) = n \cdot \mathsf{H}(\mathcal D).$$ This yields the bound

$$\mathbb{E}[\|\overline X - \mu\|_\infty] \le \sqrt{\frac12 \mathsf{H}(\mathcal D)}.$$

This bound is non-trivial when $\mathsf{H}(\mathcal D) < 2$nats$=2.88$bits and it is an improvement over the worst-case bound when the entropy is very low, namely $\mathsf{H}(\mathcal D) < \frac{\log(2d)}{n}$.

The obvious deficiency of this bound is that it doesn't improve as $n$ grows. So there is definitely some slack in the proof, but I'm not sure how to exploit it.

One might hope that $\mathsf{I}(\overline X; Y) \le n \cdot \mathsf{H}(\mathcal D)$ can be improved to, say, $\mathsf{I}(\overline X; Y) \le \mathsf{H}(\mathcal D)$. Unfortunately, this is not true -- e.g., let $\mathcal D$ be all zeros with probability $1-1/n$ and, with probability $1/n$, uniform over the $d$ standard basis vectors. This example has $\mathsf{H}(\mathcal D) = O(\log(nd)/n)$ and $\mathsf{I}(\overline X; Y) = \Omega(\log(d))$, but it still has good uniform convergence properties. However, it feels like a morally equivalent statement should be true, which leads me to the following conjecture, which would be true if $\mathsf{I}(\overline X; Y) \le \mathsf{H}(\mathcal D)$ held.

Conjecture. $\mathbb{E}[\|\overline X - \mu\|_\infty] \le O\left(\sqrt{\mathsf{H}(\mathcal D)/n}\right)$.

Here is an idea for improving this bound and maybe proving the conjecture:

Let's replace the argmax $Y$ with a randomized approximate argmax $\tilde Y$. The hope is the randomization reduces the mutual information but the approximation is good enough for the rest of the proof to carry over.

Specifically, $\tilde Y$ will be supported on the standard basis vectors and their negations with probabilities given by $$\mathbb{P}[\tilde Y = y] \propto e^{ \eta \cdot \langle y, \overline X - \mu \rangle}$$ for some $\eta > 0$. It is straightforward to show that $$\mathbb{E}[\|\overline X - \mu\|_\infty] \le \mathbb{E}[\langle \tilde Y, \overline X - \mu \rangle] + \frac{1}{\eta} \mathsf{H}(\tilde Y|\overline X) \le \sqrt{\frac{\mathsf{I}(\overline X; \tilde Y)}{2n}} + \frac{1}{\eta} \mathsf{H}(\tilde Y|\overline X).$$ The next step is to pick $\eta$ and show that $\mathsf{I}(\overline X; \tilde Y)$ and $\mathsf{H}(\tilde Y | \overline{X})$ are both sufficiently small. I have no idea if this will work out, but the intution is that changing one $X_i$ will only change the distribution of $\tilde Y$ by a $e^\eta$ multiplicative factor, yielding low mutual information. In particular, as $\eta \to 0$, we have $I(\overline X; \tilde Y) \to 0$. Conversely, as $\eta \to \infty$ we have $\tilde Y \to Y$ and we get back to the proof above.

---

Thanks to Aryeh's comment for reminding me about this question three years later. Thinking about it again, I'm starting to think the conjecture above is false. If we let $\mathcal{D}$ be a pseudorandom distribution, we should be able to have both low entropy and the same kind of behaviour as the uniform distribution. I'm not sure exactly what kind of pseudorandom distribution would work, so there is work to be done, but it seems like a promising approach to producing a counterexample.

Answer 2

First, let's use McDiarmid's inequality to conclude that $$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge \mathbb{E}|| \bar X - \mu ||_\infty + \varepsilon \right] \le e^{-2n\varepsilon^2},$$ so it remains to bound $\mathbb{E}|| \bar X - \mu ||_\infty$. Using Jensen's inequality, $$ (\mathbb{E}|| \bar X - \mu ||_\infty)^2\le \mathbb{E}|| \bar X - \mu ||_\infty^2 \le \sum_{j=1}^d\mathbb{E}(\bar X(j)-\mu(j))^2= \sum_{j=1}^d\mathrm{Var}[\bar X(j)]=\frac1{n}\sum_{j=1}^d\mathrm{Var}[X(j)], $$ whence $$ \mathbb{E}|| \bar X - \mu ||_\infty\le \sqrt{\frac1{n}\sum_{j=1}^d\mathrm{Var}[X(j)]}. $$ For sufficiently small variances, this is an improvement over your bound.

Update. A different approach would be to introduce the Rademacher random variables $\sigma_i$ and to use the standard symmetrization argument to obtain $$ \mathbb{E}|| \bar X - \mu ||_\infty \le2\mathbb{E}\max_{j\in[d]}\frac1n\sum_{i=1}^n\sigma_i X_i(j), $$ where $X_i(j)$ indicates the $j$th bit of $X_i$. Now there must be a way to bound the latter Rademacher complexity using the entropy of $\mathcal{D}$, but I don't have anything off the top of my head. Massart's finite class lemma will give you a distribution-free bound of $O(\sqrt{\log(d)/n})$.

Answer 3

We have largely resolved the question for product measures. I'm going to change the notation from the OP to be in line with our paper, https://arxiv.org/abs/2209.04054

I'll be writing $\mu$ rather than $\mathcal{D}$ as the distribution on $\{0,1\}^d$ and $p\in[0,1]^d$ as its mean (I know, this was denoted $p$ in the OP -- apologies!). Finally, the empirical mean will be denoted $\hat p_n$ (this was $\bar X$ in the OP).

The result will hold for finite and infinite $d$. Assume without loss of generality that $p\in[0,1/2]^d]$ and $p(j)$ is decreasing in $j$.

Define $$ S := \sup_{j\in[d]}p(j)\log (j+1) $$ and $$ T := \sup_{j\in[d]}\frac{\log (j+1)}{\log(1/p(j))}. $$

Then:

1. $\mathbb{E}||\hat p_n-p||_\infty\to0$ if and only if $T<\infty$.
2. If $T<\infty$, then asymptotically $$ \sqrt n\mathbb{E}||\hat p_n-p||_\infty \asymp \sqrt{S}. $$

$$ \mathbb{E}||\hat p_n-p||_\infty \lesssim \sqrt{\frac{S}{n}} +\frac{T\log n}{n} . $$

4. There is also an asymptotic $\mathbb{E}||\hat p_n-p||_\infty \gtrsim \frac{T}{n} $ bound.

See the paper for the full details!