<p><em>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.</em></p>
<p>As <a href="https://cstheory.stackexchange.com/a/42015/2022">Aryeh observes</a>, it suffices to bound <span class="math-container">$\mathbb{E}[\|\overline X - \mu\|_\infty]$</span>.</p>
<p>First, use the duality between the <span class="math-container">$\infty$</span>-norm and the <span class="math-container">$1$</span>-norm: Let <span class="math-container">$$Y = \underset{\|y\|_1 \le 1}{\mathsf{argmax}} ~~ \langle y, \overline X - \mu \rangle$$</span> so that <span class="math-container">$\langle Y, \overline X - \mu \rangle = \|\overline X - \mu \|_\infty$</span>. Note that we may assume <span class="math-container">$Y$</span> is a deterministic function of <span class="math-container">$\overline X$</span> and that it is supported on the standard basis vectors and their negations.</p>
<p>Next, we use a <a href="https://ee.stanford.edu/%7Egray/it.pdf#page=112" rel="nofollow noreferrer">simple (yet magical) inequality</a>: For all random variables <span class="math-container">$U,V$</span> on <span class="math-container">$\Omega$</span> and all <span class="math-container">$f : \Omega \to \mathbb{R}$</span> (such that everything is well-defined), <span class="math-container">$$\mathbb{E}[f(U)] \le \mathsf{D}(U\|V) + \log \mathbb{E}[e^{f(V)}].$$</span>
For simplicity, I'm using natural logs (rather than binary logs) even for information theoretic quantities like the KL divergence.</p>
<p>I'm going to apply this with <span class="math-container">$U = (\overline X, Y)$</span> and <span class="math-container">$V = \overline X \times Y$</span> (i.e., <span class="math-container">$V$</span> is a product distribution whose marginals match those of <span class="math-container">$U$</span>) and <span class="math-container">$f(x,y) = \lambda \cdot \langle y, x - \mu \rangle$</span> for some <span class="math-container">$\lambda &gt; 0$</span>. Thus the divergence is the mutual information: <span class="math-container">$\mathsf{D}(U\|V) = \mathsf{I}(\overline X; Y)$</span>. Then we have
<span class="math-container">$$\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}),$$</span> where the final inequality uses <a href="https://en.wikipedia.org/wiki/Hoeffding%27s_lemma" rel="nofollow noreferrer">Hoeffding's lemma</a>. Rearranging yields <span class="math-container">$$\mathbb{E}[\|\overline X - \mu\|_\infty] \le \inf_{\lambda &gt; 0} \frac{1}{\lambda}\left(\mathsf{I}(\overline X; Y) + \frac{\lambda^2}{8n}\right) = \sqrt{\frac{\mathsf{I}(\overline X;Y)}{2n}}.$$</span></p>
<p>Now it only remains to bound <span class="math-container">$\mathsf{I}(\overline X;Y)$</span>.</p>
<p>Note that, since <span class="math-container">$Y$</span> is assumed to be supported on a set of size <span class="math-container">$2d$</span>, we have <span class="math-container">$\mathsf{I}(\overline X;Y) \le \mathsf{H}(Y) \le \log(2d)$</span>, which gives <span class="math-container">$\mathbb{E}[\|\overline X - \mu \|_\infty] \le \sqrt{\log(2d)/2n}$</span>. This corresponds to the worst-case union bound.</p>
<p>We also have <span class="math-container">$$\mathsf{I}(\overline X;Y) \le \mathsf{H}(\overline X) \le \mathsf{H}(X_1, \cdots, X_n) = n \cdot \mathsf{H}(\mathcal D).$$</span> This yields the bound</p>
<blockquote>
<p><span class="math-container">$$\mathbb{E}[\|\overline X - \mu\|_\infty] \le \sqrt{\frac12 \mathsf{H}(\mathcal D)}.$$</span></p>
</blockquote>
<p>This bound is non-trivial when <span class="math-container">$\mathsf{H}(\mathcal D) &lt; 2$</span><a href="https://en.wikipedia.org/wiki/Nat_(unit)" rel="nofollow noreferrer">nats</a><span class="math-container">$=2.88$</span>bits and it is an improvement over the worst-case bound when the entropy is very low, namely <span class="math-container">$\mathsf{H}(\mathcal D) &lt; \frac{\log(2d)}{n}$</span>.</p>
<p>The obvious deficiency of this bound is that it doesn't improve as <span class="math-container">$n$</span> grows. So there is definitely some slack in the proof, but I'm not sure how to exploit it.</p>
<p>One might hope that <span class="math-container">$\mathsf{I}(\overline X; Y) \le n \cdot \mathsf{H}(\mathcal D)$</span> can be improved to, say, <span class="math-container">$\mathsf{I}(\overline X; Y) \le \mathsf{H}(\mathcal D)$</span>. Unfortunately, this is not true -- e.g., let <span class="math-container">$\mathcal D$</span> be all zeros with probability <span class="math-container">$1-1/n$</span> and, with probability <span class="math-container">$1/n$</span>, uniform over the <span class="math-container">$d$</span> standard basis vectors. This example has <span class="math-container">$\mathsf{H}(\mathcal D) = O(\log(nd)/n)$</span> and <span class="math-container">$\mathsf{I}(\overline X; Y) = \Omega(\log(d))$</span>, 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 <span class="math-container">$\mathsf{I}(\overline X; Y) \le \mathsf{H}(\mathcal D)$</span> held.</p>
<p><strong>Conjecture.</strong> <span class="math-container">$\mathbb{E}[\|\overline X - \mu\|_\infty] \le O\left(\sqrt{\mathsf{H}(\mathcal D)/n}\right)$</span>.</p>
<p><em>Here is an idea for improving this bound and maybe proving the conjecture:</em></p>
<p>Let's replace the argmax <span class="math-container">$Y$</span> with a randomized <em>approximate</em> argmax <span class="math-container">$\tilde Y$</span>. The hope is the randomization reduces the mutual information but the approximation is good enough for the rest of the proof to carry over.</p>
<p>Specifically, <span class="math-container">$\tilde Y$</span> will be supported on the standard basis vectors and their negations with probabilities given by <span class="math-container">$$\mathbb{P}[\tilde Y = y] \propto e^{ \eta \cdot \langle y, \overline X - \mu \rangle}$$</span> for some <span class="math-container">$\eta &gt; 0$</span>. It is straightforward to show that <span class="math-container">$$\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).$$</span>
The next step is to pick <span class="math-container">$\eta$</span> and show that <span class="math-container">$\mathsf{I}(\overline X; \tilde Y)$</span> and <span class="math-container">$\mathsf{H}(\tilde Y | \overline{X})$</span> are both sufficiently small. I have no idea if this will work out, but the intution is that changing one <span class="math-container">$X_i$</span> will only change the distribution of <span class="math-container">$\tilde Y$</span> by a <span class="math-container">$e^\eta$</span> multiplicative factor, yielding low mutual information. In particular, as <span class="math-container">$\eta \to 0$</span>, we have <span class="math-container">$I(\overline X; \tilde Y) \to 0$</span>. Conversely, as <span class="math-container">$\eta \to \infty$</span> we have <span class="math-container">$\tilde Y \to Y$</span> and we get back to the proof above.</p>
<hr />
<p>Thanks to <a href="https://cstheory.stackexchange.com/questions/42009/is-uniform-convergence-faster-for-low-entropy-distributions?noredirect=1#comment112813_42009">Aryeh's comment</a> 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 <span class="math-container">$\mathcal{D}$</span> 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.</p>

CC BY-SA 4.0
2018-12-10T17:27:13.167Z
If you're using display (5.16) in Gray's book, I don't see how you get $E[f]$ being *upper*-bounded rather than *lower*-bounded.
Aryeh
CC BY-SA 4.0
2018-12-10T17:31:03.757Z
@Aryeh For a particular f, $\mathsf{D}(U\|V) = \sup_\Phi (\mathbb{E}_U[\Phi] - \log \mathbb{E}_V[e^\Phi]) \ge \mathbb{E}_U[f] - \log \mathbb{E}_V[e^f]$, which rearranges to $\mathbb{E}_U[f] \le \mathsf{D}(U,V) +  \log \mathbb{E}_V[e^f]$, no?
Thomas Steinke
CC BY-SA 4.0
2018-12-10T17:39:03.893Z
ah, yes -- I had it backwards! Nice
Aryeh
CC BY-SA 4.0
2018-12-12T00:27:18.933Z
I think your argument is the same as the Russo and Zou argument here https://blogs.princeton.edu/imabandit/2018/09/18/how-to-generalize-algorithmically/.
Sasho Nikolov
CC BY-SA 4.0
2018-12-10T17:16:02.480Z
2022-01-20T17:42:54.257Z
2022-01-20T17:42:54.257Z
Thomas Steinke
<p>First, let's use McDiarmid's inequality to conclude that
<span class="math-container">$$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge 
\mathbb{E}|| \bar X - \mu ||_\infty
+
\varepsilon \right] \le  e^{-2n\varepsilon^2},$$</span>
so it remains to bound <span class="math-container">$\mathbb{E}|| \bar X - \mu ||_\infty$</span>.
Using Jensen's inequality,
<span class="math-container">$$ (\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)],
$$</span>
whence
<span class="math-container">$$ \mathbb{E}|| \bar X - \mu ||_\infty\le
\sqrt{\frac1{n}\sum_{j=1}^d\mathrm{Var}[X(j)]}.
$$</span>
For sufficiently small variances, this is an improvement over your bound.</p>
<p>Update. A different approach would be to introduce the Rademacher random variables <span class="math-container">$\sigma_i$</span> and to use the standard symmetrization argument to obtain
<span class="math-container">$$ \mathbb{E}|| \bar X - \mu ||_\infty
\le2\mathbb{E}\max_{j\in[d]}\frac1n\sum_{i=1}^n\sigma_i X_i(j), 
$$</span>
where <span class="math-container">$X_i(j)$</span> indicates the <span class="math-container">$j$</span>th bit of <span class="math-container">$X_i$</span>. Now there must be a way to bound the latter Rademacher complexity using the entropy of <span class="math-container">$\mathcal{D}$</span>, 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 <span class="math-container">$O(\sqrt{\log(d)/n})$</span>.</p>

CC BY-SA 4.0
2018-12-10T05:34:42.720Z
Interesting. One minor correction: $\mathsf{Var}[\overline X(j)] = \frac 1 n \mathsf{Var}[X(j)]$ rather than $\frac 1 {n^2}$.
Thomas Steinke
CC BY-SA 4.0
2018-12-10T08:56:26.680Z
BTW, I might consider spending some more time to try to work out an entropy bound, but I'd need some more background and motivation -- feel free to reach out via email.
Aryeh
CC BY-SA 4.0
2018-12-10T17:21:20.497Z
$\mathsf{Var}[\overline X(j)] = \frac{1}{n^2} \sum_i^n \mathsf{Var}[X_i(j)]$ so one $n$ is cancelled by the sum. I will edit my question to add a little bit of motivation, although at this stage I'm curious even if it doesn't help with what I was trying to do.
Thomas Steinke
CC BY-SA 4.0
2018-12-10T17:22:21.113Z
Note that the sum there is over $d$, not over $n$.
Aryeh
CC BY-SA 4.0
2018-12-13T20:34:47.500Z
The first equality after "Using Jensen's inequality" should be $\leq$ I think.
kodlu
CC BY-SA 4.0
2022-05-10T23:52:39.017Z
@Thomas You're of course right about the factor of $n$, I've hopefully fixed it now.
Aryeh
CC BY-SA 4.0
2018-12-09T22:44:14.207Z
2022-05-10T23:51:50.240Z
2022-05-10T23:51:50.240Z
Aryeh
<p>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,
<a href="https://arxiv.org/abs/2209.04054" rel="nofollow noreferrer">https://arxiv.org/abs/2209.04054</a></p>
<p>I'll be writing <span class="math-container">$\mu$</span> rather than <span class="math-container">$\mathcal{D}$</span> as the distribution on <span class="math-container">$\{0,1\}^d$</span> and <span class="math-container">$p\in[0,1]^d$</span> as its mean (I know, this was denoted <span class="math-container">$p$</span> in the OP -- apologies!).
Finally, the empirical mean will be denoted <span class="math-container">$\hat p_n$</span> (this was <span class="math-container">$\bar X$</span> in the OP).</p>
<p>The result will hold for finite and infinite <span class="math-container">$d$</span>. Assume without loss of generality that <span class="math-container">$p\in[0,1/2]^d]$</span> and <span class="math-container">$p(j)$</span> is decreasing in <span class="math-container">$j$</span>.</p>
<p>Define
<span class="math-container">$$
S := \sup_{j\in[d]}p(j)\log (j+1)
$$</span>
and
<span class="math-container">$$
T := \sup_{j\in[d]}\frac{\log (j+1)}{\log(1/p(j))}.
$$</span></p>
<p>Then:</p>
<ol>
<li><span class="math-container">$\mathbb{E}||\hat p_n-p||_\infty\to0$</span> if and only if <span class="math-container">$T&lt;\infty$</span>.</li>
<li>If <span class="math-container">$T&lt;\infty$</span>, then asymptotically
<span class="math-container">$$
\sqrt n\mathbb{E}||\hat p_n-p||_\infty \asymp \sqrt{S}.
$$</span></li>
<li></li>
</ol>
<p><span class="math-container">$$
\mathbb{E}||\hat p_n-p||_\infty
\lesssim 
\sqrt{\frac{S}{n}}
+\frac{T\log n}{n}
.
$$</span></p>
<ol start="4">
<li>There is also an asymptotic
<span class="math-container">$\mathbb{E}||\hat p_n-p||_\infty
\gtrsim
\frac{T}{n}
$</span>
bound.</li>
</ol>
<p>See the paper for the full details!</p>

CC BY-SA 4.0
2022-09-07T21:12:58.360Z
2022-09-14T08:58:25.620Z
2022-09-14T08:58:25.620Z
Aryeh
<p>Let <span class="math-container">$\mathcal D$</span> be a probability distribution on <span class="math-container">$\{0,1\}^d$</span>. Let <span class="math-container">$X_1, \cdots, X_n \in \{0,1\}^d$</span> be i.i.d. samples from <span class="math-container">$\mathcal D$</span>.  Let <span class="math-container">$\mu \in [0,1]^d$</span> be the mean of <span class="math-container">$\mathcal D$</span> and let <span class="math-container">$\overline X = \frac{1}{n} \sum_{i=1}^n X_i \in [0,1]^d$</span> be the mean of the samples. </p>

<p>By <a href="https://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_case_of_bounded_random_variables" rel="noreferrer">Hoeffding's inequality</a> and a <a href="https://en.wikipedia.org/wiki/Boole%27s_inequality" rel="noreferrer">union bound</a>, <span class="math-container">$$\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le 2d \cdot e^{-2n\varepsilon^2}$$</span> for all <span class="math-container">$\varepsilon \ge 0$</span>. Equivalently, for <span class="math-container">$\varepsilon,\delta&gt;0$</span>, if <span class="math-container">$n \ge \frac{\log(2d/\delta)}{2\varepsilon^2}$</span>, then <span class="math-container">$\mathbb{P}\left[\left\| \overline X - \mu \right\|_\infty \ge \varepsilon \right] \le \delta$</span>. </p>

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

<p>My question is whether better bounds are known if we know that <span class="math-container">$\mathcal D$</span> has low <a href="https://en.wikipedia.org/wiki/Entropy_(information_theory)#Definition" rel="noreferrer">entropy</a>. </p>

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

<hr>

<p><em>Some remarks about how I came to this question:</em></p>

<p>Let's imagine you are running the <a href="https://theoryofcomputing.org/articles/v008a006/v008a006.pdf" rel="noreferrer">Multiplicative Weights algorithm</a> for online learning or <a href="http://www.cs.cmu.edu/~ninamf/LGO10/wm-minimax.pdf" rel="noreferrer">solving a repeated zero-sum game</a>. 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? </p>

<p>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.</p>

<p>What if instead you have <span class="math-container">$n$</span> samples from the MW distribution? If <span class="math-container">$n$</span> 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.</p>

<p>So the question is how many samples <span class="math-container">$n$</span> 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.</p>

<p>My question about MW arose from reading <a href="https://arxiv.org/pdf/1402.1526.pdf" rel="noreferrer">this paper</a>. 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.</p>

CC BY-SA 4.0
2018-12-09T10:07:48.580Z
I'm trying to mentally compile the problem statement and getting a "type error". $\mathcal{D}$ is a distribution on the cube, so the "type" of $X_i\sim\mathcal{D}$ should be a bit-string of length $d$. Yet you seem to be treating the $X_i$ as scalars?..
Aryeh
CC BY-SA 4.0
2018-12-09T17:14:00.980Z
@Aryeh How so? $\mu,\overline X \in [0,1]^d$ are vectors. I have edited to clarify types
Thomas Steinke
CC BY-SA 4.0
2018-12-09T22:07:53.307Z
ok, I see -- good question!
Aryeh
CC BY-SA 4.0
2018-12-10T07:07:56.170Z
[Sanov's theorem](https://www.timvanerven.nl/blog/2012/08/large-deviations-cramer-vs-sanov/) sounds related, but I'd need to think if it actually says anything about your question. Nice question, btw!
Sasho Nikolov
CC BY-SA 4.0
2018-12-10T16:31:34.487Z
Entropy may not be the right measure of uncertainty for what you're trying to do. I'm thinking of the regime $d \to \infty$ and the distribution that puts $0.99$ probability on $0\cdots 0$ and with $0.01$ probability is uniform on $\{0,1\}^d$. Its entropy is linear in $d$ but I think a constant number of samples (independent of $d$) should suffice for constant accuracy $0.02$ or so (maybe $\log(d)$ samples at most).
usul
CC BY-SA 4.0
2018-12-10T17:28:08.740Z
@usul Yes, one might hope for even better results. :) Shannon entropy feels very natural though.
Thomas Steinke
CC BY-SA 4.0
2018-12-10T17:34:42.750Z
@SashoNikolov Thanks! Sanov's theorem seems very useful I will have to think about how it possibly apply it here.
Thomas Steinke
CC BY-SA 4.0
2022-01-19T12:27:52.223Z
@Thomas have you made any progress? I may have a research interest in this question. Would love to get in touch so I can properly credit you.
Aryeh
CC BY-SA 4.0
2022-01-20T17:35:07.013Z
@Aryeh No progress. It would be great if you figure out the answer, but no need to credit me.
Thomas Steinke
CC BY-SA 4.0
2022-09-07T21:13:57.820Z
@Thomas see new posted answer. This was a really inspiring question!
Aryeh
<pr.probability><vc-dimension><shannon-entropy><sample-complexity>
Is uniform convergence faster for low-entropy distributions?
Thomas Steinke
# Is uniform convergence faster for low-entropy distributions?

(Asked by: username_0 on 2018-12-09)

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](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_case_of_bounded_random_variables) and a [union bound](https://en.wikipedia.org/wiki/Boole%27s_inequality), $$\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](https://en.wikipedia.org/wiki/Entropy_(information_theory)#Definition).

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](https://theoryofcomputing.org/articles/v008a006/v008a006.pdf) for online learning or [solving a repeated zero-sum game](http://www.cs.cmu.edu/~ninamf/LGO10/wm-minimax.pdf). 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](https://arxiv.org/pdf/1402.1526.pdf). 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.

**Tags:** pr.probability, vc-dimension, shannon-entropy, sample-complexity
> **Comments:**
> **username_1**: I'm trying to mentally compile the problem statement and getting a "type error". $\mathcal{D}$ is a distribution on the cube, so the "type" of $X_i\sim\mathcal{D}$ should be a bit-string of length $d$. Yet you seem to be treating the $X_i$ as scalars?..  
> **username_0**: @Aryeh How so? $\mu,\overline X \in [0,1]^d$ are vectors. I have edited to clarify types  
> **username_1**: ok, I see -- good question!  
> **username_2**: [Sanov's theorem](https://www.timvanerven.nl/blog/2012/08/large-deviations-cramer-vs-sanov/) sounds related, but I'd need to think if it actually says anything about your question. Nice question, btw!  
> **username_3**: Entropy may not be the right measure of uncertainty for what you're trying to do. I'm thinking of the regime $d \to \infty$ and the distribution that puts $0.99$ probability on $0\cdots 0$ and with $0.01$ probability is uniform on $\{0,1\}^d$. Its entropy is linear in $d$ but I think a constant number of samples (independent of $d$) should suffice for constant accuracy $0.02$ or so (maybe $\log(d)$ samples at most).  
> **username_0**: @usul Yes, one might hope for even better results. :) Shannon entropy feels very natural though.  
> **username_0**: @SashoNikolov Thanks! Sanov's theorem seems very useful I will have to think about how it possibly apply it here.  
> **username_1**: @Thomas have you made any progress? I may have a research interest in this question. Would love to get in touch so I can properly credit you.  
> **username_0**: @Aryeh No progress. It would be great if you figure out the answer, but no need to credit me.  
> **username_1**: @Thomas see new posted answer. This was a really inspiring question!  

---

## 3 answers

### Answer by username_0 on 2018-12-10. Score: 4

*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](https://cstheory.stackexchange.com/a/42015/2022), 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](https://ee.stanford.edu/%7Egray/it.pdf#page=112): 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](https://en.wikipedia.org/wiki/Hoeffding%27s_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](https://en.wikipedia.org/wiki/Nat_(unit))$=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](https://cstheory.stackexchange.com/questions/42009/is-uniform-convergence-faster-for-low-entropy-distributions?noredirect=1#comment112813_42009) 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.

> **Comments:**
> **username_1**: If you're using display (5.16) in Gray's book, I don't see how you get $E[f]$ being *upper*-bounded rather than *lower*-bounded.  
> **username_0**: @Aryeh For a particular f, $\mathsf{D}(U\|V) = \sup_\Phi (\mathbb{E}_U[\Phi] - \log \mathbb{E}_V[e^\Phi]) \ge \mathbb{E}_U[f] - \log \mathbb{E}_V[e^f]$, which rearranges to $\mathbb{E}_U[f] \le \mathsf{D}(U,V) +  \log \mathbb{E}_V[e^f]$, no?  
> **username_1**: ah, yes -- I had it backwards! Nice  
> **username_2**: I think your argument is the same as the Russo and Zou argument here https://blogs.princeton.edu/imabandit/2018/09/18/how-to-generalize-algorithmically/.  

---

### Answer by username_1 on 2018-12-09. Score: 4

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})$.

> **Comments:**
> **username_0**: Interesting. One minor correction: $\mathsf{Var}[\overline X(j)] = \frac 1 n \mathsf{Var}[X(j)]$ rather than $\frac 1 {n^2}$.  
> **username_1**: BTW, I might consider spending some more time to try to work out an entropy bound, but I'd need some more background and motivation -- feel free to reach out via email.  
> **username_0**: $\mathsf{Var}[\overline X(j)] = \frac{1}{n^2} \sum_i^n \mathsf{Var}[X_i(j)]$ so one $n$ is cancelled by the sum. I will edit my question to add a little bit of motivation, although at this stage I'm curious even if it doesn't help with what I was trying to do.  
> **username_1**: Note that the sum there is over $d$, not over $n$.  
> **username_4**: The first equality after "Using Jensen's inequality" should be $\leq$ I think.  
> **username_1**: @Thomas You're of course right about the factor of $n$, I've hopefully fixed it now.  

---

### Answer by username_1 on 2022-09-07. Score: 2

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!


---

