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

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?

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