Is uniform convergence faster for low-entropy distributions? 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&gt;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.
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^2}\sum_{j=1}^d\mathrm{Var}[X(j)],
$$
whence
$$ \mathbb{E}|| \bar X - \mu ||_\infty\le
\frac1{n}\sqrt{\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})$.