Which is the most efficient of the two following approximation algorithms?

Question

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?

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