<p>For each <span class="math-container">$b \in \mathfrak{B}$</span>, define <span class="math-container">$\Delta(b):=  \mathrm{Upper}(b)-\mathrm{Lower}(b)$</span>.</p>
<p>The key estimate in Algorithm 2 is that:
<span class="math-container">\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*}</span></p>
<p>It follows that, for each <span class="math-container">$t \in \mathbb{N}$</span>, we have:</p>
<p><span class="math-container">\begin{align*}
   \sum_{b \in B_{2t+1}} \Delta(b)
&amp;\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)
\\
&amp;\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*}</span>
In particular, if <span class="math-container">$t =2^n-1$</span> we get:
<span class="math-container">\begin{align*}
   \sum_{b \in B_{t}} \Delta(b) &amp;= \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)
\\
&amp;\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*}</span>
Up to worsening the leading constant, the same relation holds for every <span class="math-container">$t \in \mathbb{N}$</span>.</p>

CC BY-SA 4.0
2022-07-04T20:49:33.593Z
2022-07-04T21:20:03.610Z
2022-07-04T21:20:03.610Z
Bob
<p>Let <span class="math-container">$\mathfrak{B}$</span> be a set, which will be called the set of bins. Suppose we have five maps
<span class="math-container">\begin{align*}
   \mathrm{Value} &amp;: \mathfrak{B} \to \mathbb{R}
\\
   \mathrm{Upper} &amp;: \mathfrak{B} \to \mathbb{R}
\\
   \mathrm{Lower} &amp;: \mathfrak{B} \to \mathbb{R}
\\
   \mathrm{Size} &amp;: \mathfrak{B} \to (0,1]
\\
   \mathrm{Split} &amp;: \mathfrak{B} \times\{0,1\} \to \mathfrak{B}
\end{align*}</span>
such that
<span class="math-container">\begin{align*}
\forall b\in\mathfrak{B}, &amp;\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}, &amp;\qquad  \mathrm{Lower}(b) \le \mathrm{Value}(b) \le \mathrm{Upper}(b)
\\   
\forall b\in\mathfrak{B}, &amp;\qquad  \mathrm{Upper}(b) - \mathrm{Lower}(b) \le \big(\mathrm{Size}(b)\big)^2
\\
   \forall s\in\{0,1\}, \forall b \in \mathfrak{B}, &amp;\qquad \mathrm{Size}\big( \mathrm{Split}(b,s) \big)= \frac{1}{2} \cdot \mathrm{Size}(b)
\\
   \forall b \in \mathfrak{B}, &amp;\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*}</span></p>
<blockquote>
<p>Given a bin <span class="math-container">$\bar{b} \in \mathfrak{B}$</span> and we want to calculate <span class="math-container">$\mathrm{Value}(\bar{b})$</span>.</p>
</blockquote>
<p>Unfortunately, we don't have direct access to the function <span class="math-container">$\mathrm{Value}$</span>, but we have black-box access to the functions <span class="math-container">$\mathrm{Upper}, \mathrm{Lower}$</span>, and <span class="math-container">$\mathrm{Size}$</span>.</p>
<p>We start with <span class="math-container">$B_0 :=\{\bar{b}\}$</span> and we proceed according to the following interaction protocol:</p>
<blockquote>
<p>for <span class="math-container">$t=1,2,\dots$</span></p>
<ul>
<li>For each <span class="math-container">$b \in B_{t-1}$</span>, observe <span class="math-container">$\mathrm{Upper}(b)$</span>, <span class="math-container">$\mathrm{Lower}(b)$</span> and <span class="math-container">$\mathrm{Size}(b)$</span>;</li>
<li>Select <span class="math-container">$b_t\in B_{t-1}$</span>;</li>
<li><span class="math-container">$B_t := \big(B_{t-1} \backslash \{b_t\} \big) \cup \{\mathrm{Split}(b_t,0),\mathrm{Split}(b_t,1)\}$</span>;</li>
</ul>
</blockquote>
<p>Our goal is to be as efficient as possible (i.e., with less interactions as possible) to get a sharp estimate of <span class="math-container">$\mathrm{Value}(\bar{b})$</span>.</p>
<p>A possible algorithm to solve this problem can be:</p>
<blockquote>
<p><strong>Algorithm 1</strong></p>
<p>for <span class="math-container">$t=1,2,\dots$</span></p>
<ul>
<li>Select <span class="math-container">$b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Size}(b)\big)$</span>;</li>
</ul>
</blockquote>
<p>Algorithm 1 completely ignores the functions <span class="math-container">$\mathrm{Upper}$</span> and <span class="math-container">$\mathrm{Lower}$</span> in making its choices. Nonetheless, if <span class="math-container">$n \in \mathbb{N}$</span> and <span class="math-container">$t = 2^{n}-1$</span> we have that <span class="math-container">$\forall b \in B_t, \mathrm{Size}(b) \le 2^{-n}$</span>, and the number of elements of <span class="math-container">$B_t$</span> is <span class="math-container">$2^n$</span>, so
<span class="math-container">\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*}</span>
and
<span class="math-container">\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*}</span>
Furthermore, notice that up to worsening the constant, we can make work the previous bound for any <span class="math-container">$t \in \mathbb{N}$</span>.</p>
<p>Since the previous algorithm completely fails to be adaptive to the information provided by <span class="math-container">$\mathrm{Upper}$</span> and <span class="math-container">$\mathrm{Lower}$</span>, I think that a better algorithm should be the following one:</p>
<blockquote>
<p><strong>Algorithm 2</strong></p>
<p>for <span class="math-container">$t=1,2,\dots$</span></p>
<ul>
<li>Select <span class="math-container">$b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Upper}(b) - \mathrm{Lower}(b)\big)$</span>;</li>
</ul>
</blockquote>
<p>The idea is that Algorithm 2 splits the bin where the current available estimate is the sloppiest.</p>
<p>However, the obvious idea to analyze it, namely that at each time <span class="math-container">$t \in \mathbb{N}$</span> we have <span class="math-container">$t$</span> bins in <span class="math-container">$B_{t-1}$</span>, and given that we are selecting <span class="math-container">$b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Upper}(b) - \mathrm{Lower}(b)\big)$</span>, we have that:
<span class="math-container">\begin{align*}
   \sum_{b \in B_{t}}&amp; \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)
\\
 &amp;\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) 
\\
 &amp;\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)
\\
 &amp;\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)
\\
&amp;\quad= \frac{2t-1}{2t} \cdot  \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \;,
\end{align*}</span>
leads by induction to just
<span class="math-container">\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*}</span>
where the last equality follows from <a href="https://math.stackexchange.com/questions/3099976/proving-the-upper-bound-of-the-ratio-of-product-of-odd-n-numbers-to-even-n-numbe">this</a> and <a href="https://math.stackexchange.com/questions/831072/using-sqrt1-t-leq-1-frac-t2-to-show-that-frac1-cdot3-cdot5-cdots2n-1">this</a>.
Now, this proof line leads to a rate of convergence for Algorithm 2 that is just a <span class="math-container">$\Theta(t^{-1/2})$</span>, which is worse than the <span class="math-container">$O(1/t)$</span>-bound we have obtained above for Algorithm 1.</p>
<p>What am I missing? Can it really be the case that Algorithm 2 has a worse rate of convergence than Algorithm 1?</p>

<approximation-algorithms><upper-bounds><analysis-of-algorithms>
Which is the most efficient of the two following approximation algorithms?
Bob
# Which is the most efficient of the two following approximation algorithms?

(Asked by: username_0 on 2022-07-04)

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](https://math.stackexchange.com/questions/3099976/proving-the-upper-bound-of-the-ratio-of-product-of-odd-n-numbers-to-even-n-numbe) and [this](https://math.stackexchange.com/questions/831072/using-sqrt1-t-leq-1-frac-t2-to-show-that-frac1-cdot3-cdot5-cdots2n-1).
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?

**Tags:** approximation-algorithms, upper-bounds, analysis-of-algorithms

---

## 1 answers

### Answer by username_0 on 2022-07-04. Score: 0 | Accepted answer

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


---

