Let $\mathfrak{B}$ be a set, which will be called the set of bins. Suppose we have five maps \begin{align*} \mathrm{Value} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Upper} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Lower} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Size} &: \mathfrak{B} \to (0,1] \\ \mathrm{Split} &: \mathfrak{B} \times\{0,1\} \to \mathfrak{B} \end{align*} such that \begin{align*} \forall b\in\mathfrak{B}, &\qquad \mathrm{Value}(b)= \mathrm{Value}\big(\mathrm{Split}(b,0)\big) + \mathrm{Value}\big(\mathrm{Split}(b,1)\big) \\ \forall b\in\mathfrak{B}, &\qquad \mathrm{Lower}(b) \le \mathrm{Value}(b) \le \mathrm{Upper}(b) \\ \forall b\in\mathfrak{B}, &\qquad \mathrm{Upper}(b) - \mathrm{Lower}(b) \le \big(\mathrm{Size}(b)\big)^2 \\ \forall s\in\{0,1\}, \forall b \in \mathfrak{B}, &\qquad \mathrm{Size}\big( \mathrm{Split}(b,s) \big)= \frac{1}{2} \cdot \mathrm{Size}(b) \\ \forall b \in \mathfrak{B}, &\qquad \sum_{s \in \{0,1\}}\Big(\mathrm{Upper}\big( \mathrm{Split}(b,s) \big) - \mathrm{Lower}\big( \mathrm{Split}(b,s) \big)\Big) \le \frac{1}{2} \cdot \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \end{align*}

Given a bin $\bar{b} \in \mathfrak{B}$ and we want to calculate $\mathrm{Value}(\bar{b})$.

Unfortunately, we don't have direct access to the function $\mathrm{Value}$, but we have black-box access to the functions $\mathrm{Upper}, \mathrm{Lower}$, and $\mathrm{Size}$.

We start with $B_0 :=\{\bar{b}\}$ and we proceed according to the following interaction protocol:

for $t=1,2,\dots$

  • For each $b \in B_{t-1}$, observe $\mathrm{Upper}(b)$, $\mathrm{Lower}(b)$ and $\mathrm{Size}(b)$;
  • Select $b_t\in B_{t-1}$;
  • $B_t := \big(B_{t-1} \backslash \{b_t\} \big) \cup \{\mathrm{Split}(b_t,0),\mathrm{Split}(b_t,1)\}$;

Our goal is to be as efficient as possible (i.e., with less interactions as possible) to get a sharp estimate of $\mathrm{Value}(\bar{b})$.

A possible algorithm to solve this problem can be:

Algorithm 1

for $t=1,2,\dots$

  • Select $b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Size}(b)\big)$;

Algorithm 1 completely ignores the functions $\mathrm{Upper}$ and $\mathrm{Lower}$ in making its choices. Nonetheless, if $n \in \mathbb{N}$ and $t = 2^{n}-1$ we have that $\forall b \in B_t, \mathrm{Size}(b) \le 2^{-n}$, and the number of elements of $B_t$ is $2^n$, so \begin{equation*} \sum_{b \in B_t} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \le \sum_{b \in B_t} (2^{-n})^2 = 2^{-n} = \frac{1}{t+1}\;. \end{equation*} and \begin{equation*} \sum_{b \in B_t} \mathrm{Lower}(b) \le \sum_{b \in B_t} \mathrm{Value}(b) = \mathrm{Value}(\bar{b}) = \sum_{b \in B_t} \mathrm{Value}(b) \le \sum_{b \in B_t} \mathrm{Upper}(b)\;. \end{equation*} Furthermore, notice that up to worsening the constant, we can make work the previous bound for any $t \in \mathbb{N}$.

Since the previous algorithm completely fails to be adaptive to the information provided by $\mathrm{Upper}$ and $\mathrm{Lower}$, I think that a better algorithm should be the following one:

Algorithm 2

for $t=1,2,\dots$

  • Select $b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Upper}(b) - \mathrm{Lower}(b)\big)$;

The idea is that Algorithm 2 splits the bin where the current available estimate is the sloppiest.

However, the obvious idea to analyze it, namely that at each time $t \in \mathbb{N}$ we have $t$ bins in $B_{t-1}$, and given that we are selecting $b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Upper}(b) - \mathrm{Lower}(b)\big)$, we have that: \begin{align*} \sum_{b \in B_{t}}& \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) = \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) - \big(\mathrm{Upper}(b_{t}) - \mathrm{Lower}(b_t)\big) \\ &\qquad+ \sum_{s \in \{0,1\}}\Big(\mathrm{Upper}\big( \mathrm{Split}(b_t,s) \big) - \mathrm{Lower}\big( \mathrm{Split}(b_t,s) \big)\Big) \\ &\quad\le \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big)-\frac{1}{2} \big( \mathrm{Upper}(b_t) - \mathrm{Lower}(b_t)\big) \\ &\quad\le \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big)-\frac{1}{2t} \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \\ &\quad= \frac{2t-1}{2t} \cdot \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \;, \end{align*} leads by induction to just \begin{equation*} \sum_{b \in B_{t}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \le \frac{1\cdot 3 \cdot\ldots \cdot (2t-1)}{2\cdot4\cdot\ldots \cdot 2t} = \Theta(t^{-1/2}), \end{equation*} where the last equality follows from this and this. Now, this proof line leads to a rate of convergence for Algorithm 2 that is just a $\Theta(t^{-1/2})$, which is worse than the $O(1/t)$-bound we have obtained above for Algorithm 1.

What am I missing? Can it really be the case that Algorithm 2 has a worse rate of convergence than Algorithm 1?


1 Answer 1


For each $b \in \mathfrak{B}$, define $\Delta(b):= \mathrm{Upper}(b)-\mathrm{Lower}(b)$.

The key estimate in Algorithm 2 is that: \begin{equation*} \forall t \in \mathbb{N}, \qquad \sum_{k=0}^{t} \max_{b \in B_{t+k}}\Delta(b) \ge \sum_{b \in B_t} \Delta(b) \;. \end{equation*}

It follows that, for each $t \in \mathbb{N}$, we have:

\begin{align*} \sum_{b \in B_{2t+1}} \Delta(b) &\le \sum_{b \in B_{2t}} \Delta(b) -\frac{1}{2} \max_{b \in B_{2t}} \Delta(b) \le \sum_{b \in B_{2t-1}} \Delta(b) -\frac{1}{2} \Big( \max_{b \in B_{2t}} \Delta(b) + \max_{b \in B_{2t-1}} \Delta(b) \Big) \\ &\le \dots \le \sum_{b \in B_{t}} \Delta(b) -\frac{1}{2} \sum_{k=0}^{t} \max_{b \in B_{t+k}}\Delta(b) \le \frac{1}{2}\sum_{b \in B_{t}} \Delta(b)\;. \end{align*} In particular, if $t =2^n-1$ we get: \begin{align*} \sum_{b \in B_{t}} \Delta(b) &= \sum_{b \in B_{2^n-1}} \Delta(b) = \sum_{b \in B_{2(2^{n-1}-1)+1}} \Delta(b) \le \frac{1}{2} \sum_{b \in B_{2^{n-1}-1}} \Delta(b) \\ &\le \dots \le \frac{1}{2^n} \sum_{b\in B_0}\Delta(b) = \frac{1}{2^n} \Delta(\bar{b}) \le \frac{1}{2^n-1+1}=\frac{1}{t+1}. \end{align*} Up to worsening the leading constant, the same relation holds for every $t \in \mathbb{N}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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