7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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?.. $\endgroup$ – Aryeh Dec 9 '18 at 10:07
  • 1
    $\begingroup$ @Aryeh How so? $\mu,\overline X \in [0,1]^d$ are vectors. I have edited to clarify types $\endgroup$ – Thomas Dec 9 '18 at 17:14
  • $\begingroup$ ok, I see -- good question! $\endgroup$ – Aryeh Dec 9 '18 at 22:07
  • 2
    $\begingroup$ Sanov's theorem sounds related, but I'd need to think if it actually says anything about your question. Nice question, btw! $\endgroup$ – Sasho Nikolov Dec 10 '18 at 7:07
  • $\begingroup$ 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). $\endgroup$ – usul Dec 10 '18 at 16:31
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aryeh Dec 10 '18 at 17:27
  • $\begingroup$ @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? $\endgroup$ – Thomas Dec 10 '18 at 17:31
  • $\begingroup$ ah, yes -- I had it backwards! Nice $\endgroup$ – Aryeh Dec 10 '18 at 17:39
  • $\begingroup$ I think your argument is the same as the Russo and Zou argument here blogs.princeton.edu/imabandit/2018/09/18/…. $\endgroup$ – Sasho Nikolov Dec 12 '18 at 0:27
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Interesting. One minor correction: $\mathsf{Var}[\overline X(j)] = \frac 1 n \mathsf{Var}[X(j)]$ rather than $\frac 1 {n^2}$. $\endgroup$ – Thomas Dec 10 '18 at 5:34
  • $\begingroup$ $Var[\alpha X]=\alpha^2 Var[X]$, so I think the $1/n^2$ is correct. $\endgroup$ – Aryeh Dec 10 '18 at 8:02
  • $\begingroup$ 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. $\endgroup$ – Aryeh Dec 10 '18 at 8:56
  • $\begingroup$ $\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. $\endgroup$ – Thomas Dec 10 '18 at 17:21
  • 1
    $\begingroup$ The first equality after "Using Jensen's inequality" should be $\leq$ I think. $\endgroup$ – kodlu Dec 13 '18 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.