and note that $(1,\tilde{\nu})\in E_{H}(W)$. In turn, we have

$\displaystyle{\delta^{\pi}_{t}}^{\prime}c$ $\displaystyle=$
$\displaystyle\tilde{c}_{[1]}\left(\tilde{\delta}^{\pi}_{t,[1]}+(\tilde{\delta}^{\pi}_{t,[2:d]})^{\prime}\tilde{\nu}\right)$
$\displaystyle\leq$
$\displaystyle\tilde{c}_{[1]}\left(\tilde{\delta}^{\pi}_{t,[1]}+\sup_{(1,\nu)\in
E_{H}(W)}(\tilde{\delta}^{\pi}_{[2:d]})^{\prime}\nu\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\tilde{c}_{[1]}\left(\tilde{\delta}^{\pi}_{t,[1]}+\sqrt{(\tilde{\delta}^{\pi}_{t,[2:d]})^{\prime}W_{t}\tilde{\delta}^{\pi}_{t,[2:d]}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\tilde{c}_{[1]}\left(\sqrt{(\tilde{\delta}^{\pi}_{t,[2:d]})^{\prime}W_{t}\tilde{\delta}^{\pi}_{t,[2:d]}}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$ $\displaystyle\epsilon,$

where $(a)$ follows from the fact that $E_{H}(W)$ is an ellipsoid and the
optimization of a linear function over an ellipsoid has an analytical solution
as given above (see, for instance, Boyd and Vandenberghe (2004)), $(b)$ holds
due to the fact that
${\tilde{\delta}}^{\pi}_{t,[1]}=(\tilde{\delta}^{\pi})^{\prime}e_{1}={\delta_{t}^{\pi}}^{\prime}U_{t}e_{1}={\delta_{t}^{\pi}}^{\prime}c_{t}^{\pi}\leq
0$ (see Eq. (11)), and $(c)$ follows from $c_{[1]}^{\star}\leq 1$ and the
assumption of the lemma. This completes the proof.

∎

###### Proof of Lemma 5.

Suppose first that
$\lambda_{1}(W_{1})>\left(\frac{\epsilon}{10(d-1)}\right)^{2}$. By Lemma 3, we
have that that for every update period $t$,

$\displaystyle\prod_{i=1}^{d-1}\lambda_{i}(W_{t+1})$ $\displaystyle\leq$
$\displaystyle e^{-1/(d-1)}\prod_{i=1}^{d-1}\lambda_{i}(W_{t}).$

For any time $t$ after exactly $I_{T}^{\pi}$ updates took place, we can apply
the latter recursively to obtain

$\displaystyle\prod_{i=1}^{d-1}\lambda_{i}(W_{t})$ $\displaystyle\leq$
$\displaystyle
e^{-I_{T}^{\pi}/(d-1)}\prod_{i=1}^{d-1}\lambda_{i}(W_{1})\>\leq\>e^{-I_{T}^{\pi}/(d-1)}(\lambda_{max}(W_{1}))^{d-1}.$
(B-5)

Next we lower bound, for any $t$, the eigenvalues $\lambda_{i}(W_{t})$. We
will establish that
$\lambda_{1}(W_{t})\geq\left(\frac{\epsilon}{10d}\right)^{2}$ for all $t\geq
1$.

If $I_{T}^{\pi}=0$, then we have that
$\lambda_{1}(W_{t})=\lambda_{1}(W_{1})>\left(\frac{\epsilon}{10(d-1)}\right)^{2}>\left(\frac{\epsilon}{10d}\right)^{2}$.

Suppose now that $I_{T}^{\pi}>0$. We will show by induction that
$\lambda_{1}(W_{t})\geq\left(\frac{\epsilon}{10d}\right)^{2}$ for all $t\geq
1$.

This clearly true for $t=1$. Suppose that it is true at time $s$. If there is
no update, then this is trivially true for $s+1$. If there is an update $s$,
two cases can happen.

Case 1: $\lambda_{1}(W_{s})>\left(\frac{\epsilon}{10(d-1)}\right)^{2}$. Note
that the largest decrease possible in any eigenvalue after applying the
ellipsoid method in $\mathbb{R}^{d-1}$ is $(d-1)^{2}/d^{2}$ (this is the
decrease that happens when the cut is along that particular eigenvector). As a
result, we must have
$\lambda_{1}(W_{s+1})\geq((d-1)^{2}/d^{2})\left(\frac{\epsilon}{10(d-1)}\right)^{2}=\left(\frac{\epsilon}{10d}\right)^{2}$.

Case 2: $\lambda_{1}(W_{s})\leq\left(\frac{\epsilon}{10(d-1)}\right)^{2}$. In
this case, given that updates are only performed when
$\delta_{s,[2:d]}^{\prime}W_{s}\delta_{s,[2:d]}>\epsilon^{2}$, we can use
(Cohen et al., 2020, Lemma 4). Indeed, in an update period, the second to the
fourth update equations in algorithm ConeUpdate are precisely the update
equations for the ellipsoid method for an ellipsoid in $\mathbb{R}^{d-1}$.
Cohen et al. (2020) introduce a version of the ellipsoid method where updates
are not performed if the length of the ellipsoid along the direction to be cut
is smaller than a certain threshold $\epsilon$. The condition in Eq. (12) for
an update in our paper is essentially the same (our condition is on the
distance from the center to the edge of the ellipsoid, but this is simply half
the length).

Recall the notation used in algorithm ConeUpdate and note that every time that
we update the matrix $W_{t}$ with the ellipsoid method, we get a matrix $N$.
Let $\lambda_{1}(N)$ denote the smallest eigenvalue of the matrix $N$. By
construction, if $t$ is an update period, we have that
$\lambda_{1}(W_{t+1})=\lambda_{1}(N)$. Lemma 4 from Cohen et al. (2020) says
that if we update our ellipsoidal cone according to algorithm ConeUpdate, if
$\lambda_{1}(W_{s})\leq\left(\frac{\epsilon}{10(d-1)}\right)^{2}$ and
$\delta_{s,[2:d]}^{\prime}W_{s}\delta_{s,[2:d]}>\epsilon^{2}$, then
$\lambda_{1}(W_{s+1})\geq\lambda_{1}(W_{s})$, i.e., the smallest eigenvalue
does not decrease after the update.

In this case, we deduce that
$\lambda_{1}(W_{s+1})\geq\lambda_{1}(W_{s})\geq\left(\frac{\epsilon}{10d}\right)^{2}$,
where the last inequality follows from the induction hypothesis. This
concludes the induction.

Combining this result with (B-5), we obtain

$\lambda_{max}(W_{t})\leq\left(\frac{10d}{\epsilon}\right)^{2(d-2)}\left(\lambda_{max}(W_{1})\right)^{(d-1)}e^{-I_{T}^{\pi}/(d-1)}.$

Suppose now that
$\lambda_{1}(W_{1})\leq\left(\frac{\epsilon}{10(d-1)}\right)^{2}$. By
construction, $W_{1}$ is a revolution cone and
$\lambda_{i}(W_{1})=\lambda_{1}(W_{1})$ for $i=1,...,d-1$. For any vector
$\delta\in\mathbb{R}^{d-1}$ with $\|\delta\|\leq 1$, we have
$\delta^{\prime}W_{1}\delta\leq\|\delta\|^{2}\lambda_{max}(W_{1})\leq\left(\frac{\epsilon}{10(d-1)}\right)^{2}\leq\epsilon^{2}$.
Hence, in this case, no update takes place, $I_{T}^{\pi}=0$, $W_{t}=W_{1}$ for
all $t$, and by Lemma 4, the per period regret is bounded above by $\epsilon$.
This concludes the proof. ∎

###### Proof of Theorem 3.

We prove Theorem 3 in four steps. In the first step, we prove that
$C_{0}\subseteq E(W_{1},U_{1})$ and, that for every $t\geq 1$,
$C(\mathcal{I}_{t})\subseteq E(W_{t+1},U_{t+1})$. In the second step, we
decompose the cumulative regret based on periods in which the condition in Eq.
(12) is satisfied or violated. In the third step, we upper bound the number of
times that Eq. (12) can be violated, to obtain a bound on the cumulative
regret. In the fourth step, we prove the running time claim.

Step 1. Note that $E(W_{1},U_{1})$, by construction, is precisely the
revolution cone with aperture angle $\alpha(C_{0})$ that contains $C_{0}$. The
inclusions $C(\mathcal{I}_{t})\subseteq E(W_{t+1},U_{t+1})$, $1\leq t\leq T$
follows from our construction and Lemma 3.

Step 2. Recall that
$I^{\pi}_{T}=\sum_{t=1}^{T}\mathbf{1}\\{{\delta}^{\prime}_{t,[2:d]}W_{t}\delta_{t,[2:d]}>\epsilon^{2}\\}$
is the number of cone-update periods. We have the following regret bound.

$\displaystyle{\cal R}^{\pi}_{T}\left(c^{\star},\vec{\cal
X}_{T},\vec{f}_{T}\right)$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\left(f_{t}(x_{t}^{\pi})-f_{t}(x^{\star}_{t})\right)^{\prime}c^{\star}$
(B-6) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}{\|f_{t}(x^{\pi}_{t})-f_{t}(x^{\star}_{t})\|}{\delta_{t}^{\pi}}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\sum_{t=1}^{T}\left(\mathbf{1}\\{{\delta}^{\prime}_{t,[2:d]}W_{t}\delta_{t,[2:d]}>\epsilon^{2}\\}+\mathbf{1}\\{{\delta}^{\prime}_{t,[2:d]}W_{t}\delta_{t,[2:d]}\leq\epsilon^{2}\\}\right){\delta_{t}^{\pi}}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\sum_{t=1}^{T}\mathbf{1}\\{{\delta}^{\prime}_{t,[2:d]}W_{t}\delta_{t,[2:d]}>\epsilon^{2}\\}{\delta_{t}^{\pi}}^{\prime}c^{\star}+\sum_{t=1}^{T}\mathbf{1}\\{{\delta}^{\prime}_{t,[2:d]}W_{t}\delta_{t,[2:d]}\leq\epsilon^{2}\\}\epsilon$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$
$\displaystyle\sum_{t=1}^{T}\mathbf{1}\\{{\delta}^{\prime}_{t,[2:d]}W_{t}\delta_{t,[2:d]}>\epsilon^{2}\\}+\sum_{t=1}^{T}\mathbf{1}\\{{\delta}^{\prime}_{t,[2:d]}W_{t}\delta_{t,[2:d]}\leq\epsilon^{2}\\}\epsilon$
$\displaystyle=$ $\displaystyle
I^{\pi}_{T}+\left(T-I^{\pi}_{T}\right)\epsilon$ $\displaystyle\leq$
$\displaystyle I^{\pi}_{T}+T\epsilon,$

where $(a)$ follows from the fact that
$\|f_{t}(x^{\pi}_{t})-f_{t}(x^{\star}_{t})\|\leq 1$ since
$f_{t}\in\mathcal{F}$, ${\cal X}_{t}\in\mathcal{B}$, for all $t\leq T$, $(b)$
follows from Lemma 4, and $(c)$ follows from Cauchy-Schwarz inequality:
${\delta_{t}^{\pi}}^{\prime}c^{\star}\leq\|\delta_{t}^{\pi}\|\|c^{\star}\|=1$.

Step 3. We now provide an upper bound for $I^{\pi}_{T}$. We need to consider
two separate cases as a function of $\alpha(C_{0})$.

If $\alpha(C_{0})\leq\arctan\epsilon$, an application of Theorem 1 shows that
the regret of every period is less than
$\sin\arctan\epsilon=\epsilon/(1+\epsilon)$ which is enough to ensure a
performance of at least $\epsilon$ when using the circumcenter as the proxy
cost vector. Moreover, Proposition 1 and our choice of $E(W_{1},U_{1})$ in
Algorithm EllipsoidalCones implies that
$\lambda_{max}(W_{1})\leq\epsilon^{2}$, and hence, for every possible vector
$\delta$, $\delta_{[2:d]}^{\prime}W_{1}\delta_{[2:d]}\leq\epsilon^{2}$. In
this case, the algorithm never has a cone-update period and $I_{T}^{\pi}=0$.
Therefore, Eq. (B-6) implies that the regret is bounded by $T\epsilon$, which
is equal to $d$ by our choice of $\epsilon$.

When $\alpha(C_{0})>\arctan\epsilon$, we may have cone-update periods. We show
that after an $\mathcal{O}(\log 1/\epsilon)$ amount of update steps, it must
be the case that $\alpha(E(W_{t},U_{t}))<\arctan\epsilon$. Then, from this
time onward, it must be the case that the algorithm never updates again and
Lemma 4 implies that the regret is upper bounded by $\epsilon$ for every
period from this time onward.

Suppose that we updated the ellipsoidal cone $\tau$ times. Lemma 5 and the
revolution cone initialization,
$\lambda_{1}(W_{1})=\cdots=\lambda_{d-1}(W_{1})=\tan^{2}\alpha(C_{0})$ gives
us that

$\displaystyle\lambda_{max}(W_{t})$
$\displaystyle\leq\left(\frac{10d}{\epsilon}\right)^{2(d-2)}\left(\lambda_{max}(W_{1})\right)^{d-1}e^{-\frac{\tau}{(d-1)}}=\left(\frac{10d}{\epsilon}\right)^{2(d-2)}(\tan\alpha(C_{0}))^{2(d-1)}e^{-\frac{\tau}{(d-1)}},$

for every $t$ after $\tau$ updates. Note that if we have
$\tau=2(d-1)^{2}\ln\left(\frac{10d\tan\alpha(C_{0})}{\epsilon}\right)$, then

$\displaystyle\lambda_{max}(W_{t})$
$\displaystyle\leq\left(\frac{10d}{\epsilon}\right)^{2(d-2)}(\tan\alpha(C_{0}))^{2(d-1)}e^{-\frac{2(d-1)^{2}\ln\left(\frac{10d\tan\alpha(C_{0})}{\epsilon}\right)}{(d-1)}}$
$\displaystyle\leq\left(\frac{10d}{\epsilon}\right)^{2(d-1)-2}\left(\tan\alpha(C_{0})\right)^{2(d-1)}\left(\frac{10d\tan\alpha(C_{0})}{\epsilon}\right)^{-2(d-1)}$
$\displaystyle\leq\left(\frac{10d}{\epsilon}\right)^{-2}\leq\epsilon^{2}.$

In this case, starting after $\tau$ updates, we are as in case $i.)$ of Lemma
5; there will be no cone-update periods onward, and the per period regret will
bounded by $\epsilon$ in future periods. In turn,

$I_{T}^{\pi}\leq
2(d-1)^{2}\ln\left(\frac{10d\tan\alpha(C_{0})}{\epsilon}\right).$ (B-7)

Combining Eqs. (B-6) and (B-7), and selecting $\epsilon=d/T$ leads to:

$\displaystyle{\cal R}^{\pi}_{T}\left(c^{\star},\vec{\cal
X}_{T},\vec{f}_{T}\right)\leq
2(d-1)^{2}\ln\left(\frac{10d\tan\alpha(C_{0})}{\epsilon}\right)+T\epsilon\leq
2(d-1)^{2}\ln\left(10T\tan\alpha(C_{0})\right)+d.$

Step 4. This algorithm runs in polynomial time in $d$ and $T$ since every
period’s computation is a function only of $d$. Low-regret periods are
computationally very cheap, while each cone-update period requires a spectral
decomposition, which has a running time upper bound of $\mathcal{O}(d^{3})$.

The proof is complete. ∎

###### Proof of Lemma 6.

The subspace $\Delta_{t_{0}+1}$ is a one-dimensional object and, by the
definition of $\Delta_{t_{0}+1}$, we have that for every element
$c\in\Pi_{\Delta_{t_{0}+1}}\left(C(\mathcal{I}_{t_{0}+1})\right)$,
$c=\gamma\delta^{\pi}_{t_{0}}$ for some $\gamma\in\mathbb{R}$. Moreover, for
every $t\geq{t_{0}}$, Eq. (10) implies that we must have for every $c\in
C(\mathcal{I}_{t})$ that ${\delta_{t_{0}}^{\pi}}^{\prime}c\geq 0$. Since
$\delta^{\pi}_{t_{0}}\in\Delta_{t_{0}+1}$, we have that
${\delta_{t_{0}}^{\pi}}^{\prime}c\geq
0\iff{\delta_{t_{0}}^{\pi}}^{\prime}\Pi_{\Delta_{t_{0}+1}}(c)\geq 0$. Hence,

$\Pi_{\Delta_{t_{0}+1}}\left(C(\mathcal{I}_{t_{0}+1})\right)\subseteq\\{c\in\mathbb{R}^{d}:\;c=\gamma\delta_{t_{0}}^{\pi},\;\gamma\geq
0\\}\implies\alpha(\Pi_{\Delta_{t_{0}+1}}\left(C(\mathcal{I}_{t_{0}+1})\right))=0,$

and $\Pi_{\Delta_{t_{0}+1}}\left(C(\mathcal{I}_{t_{0}+1})\right)$ lives in a
pointed cone.

The second affirmative follows directly from the fact that whenever
$f_{t}(x_{t}^{\pi})=f_{t}(x_{t}^{\star})$, there is no suboptimality gap and
the regret is zero. ∎

###### Proof of Lemma 7.

For every time $t$, we have that

$\displaystyle\sup_{x^{\star}_{t}\in\psi(c^{\star},{\cal
X}_{t},f_{t})}\left(f_{t}(x_{t}^{\pi})-f_{t}(x^{\star}_{t})\right)^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\;{\delta_{t}^{\pi}}^{\prime}c^{\star}={r_{t}^{\pi}}^{\prime}c^{\star}+{\Pi_{\Delta_{t}}(\delta_{t}^{\pi})}^{\prime}c^{\star}\stackrel{{\scriptstyle(b)}}{{\leq}}\eta+{\Pi_{\Delta_{t}}(\delta_{t}^{\pi})}^{\prime}\Pi_{\Delta_{t}}(c^{\star}),$

where $(a)$ follows from the fact that $f_{t}\in\mathcal{F}$, ${\cal
X}_{t}\in\mathcal{B}$ and $(b)$ follows from bounding
${r_{t}^{\pi}}^{\prime}{c^{\star}}$ with $\eta$ since we assumed
$\|r_{t}^{\pi}\|\leq\eta$, and replacing $c^{\star}$ with its projection onto
$\Delta_{t}$.

Next, we show that
${\Pi_{\Delta_{t}}(\delta_{t}^{\pi})}^{\prime}\Pi_{\Delta_{t}}(c^{\star})\leq\epsilon$
when the assumptions of the lemma are satisfied. For that, note that
$\Pi_{\Delta_{t}}(\delta_{t}^{\pi})\in\Delta_{t}$ and
$E(W_{t},U_{t})\subset\Delta_{t}$. Moreover, we have by assumption that
$\Pi_{\Delta_{t}}(c^{\star})\in\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))\subseteq
E(W_{t},U_{t})$. Hence, an application of Lemma 4 in the subspace $\Delta_{t}$
completes the proof.

∎

###### Proof of Lemma 8.

First we show that we do not exclude any feasible vector when we update the
ellipsoidal cone using the projected effective difference. By the definition
of the residual, we have that, for any $c\in C(\mathcal{I}_{t+1})$, that
${\delta^{\pi}_{t}}^{\prime}c={\Pi_{\Delta_{t+1}}(\delta^{\pi}_{t})}^{\prime}c+{r^{\pi}_{t}}^{\prime}c\geq
0,$ where the inequality follows from Eq. (10). Therefore,

$\displaystyle\Pi_{\Delta_{t+1}}\left(C(\mathcal{I}_{t+1})\right)$
$\displaystyle\subseteq$
$\displaystyle\Pi_{\Delta_{t+1}}\left(C(\mathcal{I}_{t})\cap\\{c\in\mathbb{R}^{d}:\;{\delta^{\pi}_{t}}^{\prime}c\geq
0\\}\right)$ $\displaystyle\subseteq$
$\displaystyle\Pi_{\Delta_{t+1}}\left(C(\mathcal{I}_{t})\cap\\{c\in\mathbb{R}^{d}:\;{\Pi_{\Delta_{t}}(\delta^{\pi}_{t})}^{\prime}c\geq-\eta\\}\right)$
$\displaystyle=$
$\displaystyle\Pi_{\Delta_{t}}\left(C(\mathcal{I}_{t})\cap\\{c\in\mathbb{R}^{d}:\;{\Pi_{\Delta_{t}}(\delta^{\pi}_{t})}^{\prime}\Pi_{\Delta_{t}}(c)\geq-\eta\\}\right)$
$\displaystyle\subseteq$
$\displaystyle\Pi_{\Delta_{t}}\left(C(\mathcal{I}_{t})\right)\cap\\{c\in\Delta_{t}:\;{\Pi_{\Delta_{t}}(\delta^{\pi}_{t})}^{\prime}c\geq-\eta\\}$
$\displaystyle\subseteq$ $\displaystyle
E(W_{t},U_{t})\cap\\{c\in\Delta_{t}:\;{\Pi_{\Delta_{t}}(\delta^{\pi}_{t})}^{\prime}c\geq-\eta\\},$

where the first inclusion follows from the fact that including elements in a
set can only include elements in the projection of that set, the second
inclusion follows from applying Chauchy-Schwarz for ${r^{\pi}_{t}}^{\prime}c$
and using that $\|r_{t}^{\pi}\|\leq\eta$, the equality follows the fact that
$\Pi_{\Delta_{t}}(\delta^{\pi}_{t})\in\Delta_{t}$, which implies that
${\Pi_{\Delta_{t}}(\delta^{\pi}_{t})}^{\prime}c={\Pi_{\Delta_{t}}(\delta^{\pi}_{t})}^{\prime}\Pi_{\Delta_{t}}(c)$
and the fact that $\Delta_{t+1}=\Delta_{t}$, the third inclusion follows from
the fact that the orthogonal projection of the intersection of sets must
belong to the orthogonal projection of each of the sets and, finally, the last
inclusion follows from assumption of the lemma.

The next step is a direct application of Lemma 8. For every cone update period
$t$, we focus on the subspace $\Delta_{t}$ which has dimension $2\leq p\leq
d$. We represent the vectors in $\Delta_{t}$ under its basis representation by
calculating $B_{\Delta_{t}}c\in\mathbb{R}^{p}$ for every
$c\in\Delta_{t}^{\pi}$. Therefore, it suffices to apply Lemma B-1 with $p=p$,
$\delta=B_{\Delta_{t}}\Pi_{\Delta_{t}}(\delta_{t}^{\pi})$, $\eta=\eta$ and
$E(W_{t},U_{t})$, where the matrices $W_{t},U_{t}$ are already written in the
basis representation of $\Delta_{t}$ by construction.

The final step of this proof is to show that our choice of $\eta$ and $\delta$
satisfy the assumptions of the lemma, meaning that the shallow-cut is
sufficiently deep to ensure a volume reduction. Since

$\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}^{\prime}W_{t}\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}>\epsilon^{2}\implies\frac{1}{\sqrt{\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}^{\prime}W_{t}\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}}}<\frac{1}{\epsilon},$

we have that, for $\eta=\epsilon/2d$ and $1<p\leq d$:

$\eta\leq\frac{\sqrt{\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}^{\prime}W_{t}\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}}}{2d}\leq\frac{\sqrt{\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}^{\prime}W_{t}\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}}}{2(p-1)}=\frac{\sqrt{(B_{\Delta_{t}}\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]})^{\prime}W_{t}B_{\Delta_{t}}\Pi_{\Delta_{t}}(\delta_{t})_{[2:p]}}}{2(p-1)}$

The desired inclusion and the reduction in the product of the eigenvalues
follows directly from Lemma B-1. ∎

###### Proof of Lemma 9.

In order to prove the result, we will follow the same strategy as in the proof
of Lemma 5. For the boundary cases where $t=t_{0}^{p}$ for $2\leq p\leq d$,
the ellipsoidal cone $E(W_{t},U_{t})$ is constructed by a dimension update
period, and we must have that
$\lambda_{1}(W_{t_{0}^{p}})=\lambda_{max}(W_{t_{0}^{p}})$.

Suppose $\lambda_{1}(W_{t_{0}^{p}})>\left(\frac{\epsilon}{10p}\right)^{2}$.
The shallow-cut equivalent of Lemma 4 from Cohen et al. (2020) says that if we
update our ellipsoidal cone according to Eq. (13), if
$\lambda_{1}(W_{t})\leq\frac{\epsilon^{2}}{100(p-1)^{2}}$ and
$\delta_{t,[2:p]}^{\prime}W_{t}\delta_{t,[2:p]}>\epsilon^{2}$, then
$\lambda_{1}(W_{t+1})\geq\lambda_{1}(W_{t})$, i.e., the smallest eigenvalue
does not decrease after the update. Since the largest decrease possible in any
eigenvalue after applying the ellipsoid method in $\mathbb{R}^{p-1}$ is
$(p-1)^{2}/p^{2}$ (this is the decrease that happens when the cut is along
that particular eigenvector), we have that for all $t_{0}^{p}<t<t_{0}^{p+1}$
(all time periods where the dimensionality of $\Delta_{t}$ is $p$) that

$\lambda_{1}(W_{t+1})\geq\frac{(p-1)^{2}}{p^{2}}\frac{\epsilon^{2}}{100(p-1)^{2}}=\left(\frac{\epsilon}{10p}\right)^{2}.$

We omit the induction argument here since it mimics the proof of Lemma 5.
Hence,

$\lambda_{p-1}(W_{t})\geq\left(\frac{\epsilon}{10p}\right)^{2}.$

Moreover, the shrinking factor of Lemma 8 gives us that

$\prod_{i=1}^{p-1}\lambda_{i}(W_{t+1})\leq
e^{-1/20(p-1)}\prod_{i=1}^{p-1}\lambda_{i}(W_{t}).$

Using the lower bound for the eigenvalues of $W_{t}$ gives us that

$\lambda_{max}(W_{t})\leq\left(\frac{10p}{\epsilon}\right)^{2(p-2)}\left(\lambda_{max}(W_{1})\right)^{(p-1)}e^{-\frac{I_{T}^{\pi,p}}{20(p-1)}},$

similarly to the proof of step 3 of Theorem 3, we must have that

$I_{T}^{\pi,p}\leq
20(p-1)^{2}\ln\left(\frac{10p\tan\alpha(E(W_{t_{0}^{p}},U_{t_{0}^{p}}))}{\epsilon}\right),$

where $t_{0}^{p}$ is the first time such that the dimension of $\Delta_{t}=p$
and $E(W_{t_{0}},U_{t_{0}})$ the initial ellipsoidal cone.

If $\lambda_{1}(W_{t_{0}^{p}})\leq\left(\frac{\epsilon}{10p}\right)^{2}$, then
noting that $\lambda_{max}(W_{t_{0}^{p}})=\lambda_{1}(W_{t_{0}^{p}})$, the
same argument from Lemma 5 holds and $I_{T}^{\pi,p}=0$, while Lemma 7 ensures
a upper bound of $\epsilon$ for each period regret $t$ such that
$\mbox{dim}(\Delta_{t})=p$. ∎

###### Proof of Lemma 10.

The proof is divided in three parts. First we show the inclusion, then we show
how to compute the circumcenter, and finally we prove the bound for the
uncertainty angle.

Inclusion. The definition of the knowledge set implies that for every $c\in
C(\mathcal{I}_{t})$, ${\delta_{t}^{\pi}}^{\prime}c\geq 0$. In particular, this
holds for all $i\in\tau(t)$. Moreover, by definition,
$\delta_{i}^{\pi}\in\Delta_{t}$ for all $i\in\tau(t)$. Hence, for every $c\in
C(\mathcal{I}_{t})$, we have that
${\delta_{i}^{\pi}}^{\prime}c={\delta_{i}^{\pi}}^{\prime}\Pi_{\Delta_{t}}(c)\geq
0$ for all $i\in\tau(t)$, which implies that
$\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))\subseteq K_{t}$.

Computation of circumcenter. The computation of the circumcenter of $K_{t}$ is
done via algorithm PolyCenter (see Algorithm 3). The subspace updating rule
implies that $\delta_{i}^{\pi}$, $i\in\tau(t)$ are linearly independent.
Hence, the system of equations described has one and only one solution for
each iteration $k$. In addition, we have that $z$ is a vector in the interior
of the cone
$\\{c\in\mathbb{R}^{p}:\;c=\sum\gamma_{i}\bar{\delta}_{i},\;\gamma_{i}\geq
0,\;i\in\tau(t)\\}$, which is the dual cone of $K_{t}$ (Boyd and Vandenberghe,
2004). Hence, $c^{\prime}z>0$, for all $c\in K_{t}$ and
$K_{t}\cap\\{c\in\mathbb{R}^{p}:\;c^{\prime}z\leq 1\\}$ is bounded with
extreme points given by the rays (not normalized) of $K_{t}$ and the origin.
To see why the quadratic program in PolyCenter yields to the solution of the
circumcenter, we refer to Seeger and Vidal-Nuñez (2017). The algorithm runs in
polynomial time in $p$ since it contains $p$ linear systems with $p$ equations
and one quadratic programming formulation.

Upper bound for the uncertainty angle.

For any convex, closed and pointed cone $K\subset\mathbb{R}^{d}$, we define
the circumradius of the cone $\mu(K)$ to be equal to sine of its uncertainty
angle, i.e., $\mu(K)=\sin\alpha(K)$. In this proof, we will show that

$\mu(K_{t+1}){\leq}\sqrt{1-\frac{\eta^{2(p-1)}}{p^{3}}}.$ (B-8)

Once we prove that Eq. (B-8) is true, it follows that

$\cos\alpha(K_{t+1})=\sqrt{1-\mu^{2}(K_{t+1})}\geq\frac{\eta^{(p-1)}}{p^{3/2}}\geq\frac{\eta^{(d-1)}}{d^{3/2}},$

where the second inequality follows from the facts that $0<\eta<1$ and $p\leq
d$, completing the result.

Just as circumradius (and uncertainty angle) are defined by the smallest
revolution cone that contains our cone of interest, we also need to define the
largest revolution cone that fits within a cone of interest. For any convex,
closed and solid cone $K$, we define the inradius of $K$ to be:

$\rho(K)=\max_{x\in S^{d}\cap K}\min_{y\in\partial K}\|x-y\|.$

We denote $x_{\rho}=\operatorname*{arg\,max}_{x\in S^{d}\cap
K}\min_{y\in\partial K}\|x-y\|$ as the incenter of $K$, which is analogous to
the circumcenter, but referring to the axis of the largest revolution cone
inside our cone of interest. The inradius and circumradius of a cone $K$ are
dual quantities in the sense that for every closed convex cone, we have that:

$\mu^{2}(K)+\rho^{2}(K^{\star})=1,$ (B-9)

where $K^{\star}=\\{c\in\mathbb{R}^{d}:\;c^{\prime}x\geq 0,\;\forall x\in
K\\}$ denotes the dual cone of $K$ (Henrion and Seeger, 2010, Theorem 1.4). We
will develop a lower bound on $\rho(K^{\star}_{t+1})$ and then obtain through
Eq. (B-9) our desired upper bound on $\mu(K_{t+1})$.

The lower bound for $\rho(K^{\star}_{t+1})$ is obtained by an application of
three lemmas that are interesting by its own that we prove in the appendix.
The first one, Lemma B-2, shows that the inradius of $K^{\star}_{t+1}$ can be
lower bounded by the ratio of the largest and smallest eigenvalue of the gram-
matrix (the square matrix) constructed with it’s generators. Suppose
$\mbox{dim}(\Delta_{t+1})=p\leq d$. We denote
$g_{i}=B_{\Delta_{t+1}}\delta^{\pi}_{\tau(t+1)}(i)\in\mathbb{R}^{p}$, for
$i=1,...,p$, where we used the notation $\delta^{\pi}_{\tau(t+1)}(i)$ to
denote the $i-th$ effective difference that belongs to $\tau(t+1)$. Let $G$ be
the matrix such that its columns are given by $g_{i}$, $i=1,...,p$. By
construction, the columns of $g_{i}$ are linearly independent and we have $p$
vectors generating $K^{\star}_{t+1}$ that lives in a subspace with dimension
$p$ and the assumptions of Lemma B-2 are satisfied. The lemma gives us that

$\rho(K^{\star}_{t+1})\geq\frac{1}{\sqrt{p}}\sqrt{\frac{\lambda_{max}(G^{\prime}G)}{\lambda_{min}(G^{\prime}G)}}.$

The second lemma, Lemma B-3, allows us to provide an upper-bound for
$\frac{\lambda_{max}(G^{\prime}G)}{\lambda_{min}(G^{\prime}G)}$. Note that $G$
is full column rank with unit norm vectors by construction (the change of
basis through $B_{\Delta_{t+1}}$ do not affect the norm of the effective
differences vectors), and the assumption of the lemma is satisfied. Let
$\Pi_{g_{-i}}(.)$ denote the projection operator on the subspace generated by
$\\{g_{1},\ldots,g_{p}\\}\setminus\\{g_{i}\\}$. Define

$\varphi=\min_{i\leq p}\|g_{i}-\Pi_{g_{-i}}(g_{i})\|,$

and note that $\phi$ is the minimum norm obtained by regressing the column
$g_{i}$ on every other columns. Lemma B-3 implies that

$\frac{\lambda_{max}(G^{\prime}G)}{\lambda_{min}(G^{\prime}G)}\leq\left(\frac{p}{\varphi}\right)^{2}.$

The final step in our proof is to show that $\varphi$ cannot be arbitrarily
small. In Lemma B-4, we show that if the sequence of the $g_{i}$’s satisfy
$\|g_{i}-\Pi_{g_{1},...,g_{i-1}}(g_{i})\|^{2}\geq\eta^{2}$, (which is true due
to the subspace updating rule) then it must be the case that
$\|g_{i}-\Pi_{g_{-i}}(g_{i})\|\geq\eta^{2(p-i)}$ for $i=1$ or greater than
$\eta^{2(p-i)}$ if $i>1$. Taking $i=1$ (or $i=2$) ensures that
$\|g_{i}-\Pi_{g_{-i}}(g_{i})\|\geq\eta^{2(p-1)}$ for every $i$. Then, the
combination of the three lemmas establishes that the inradius of
$K^{\star}_{t+1}$ is lower bounded by
$\frac{\eta^{p-1}}{p^{3/2}}\geq\frac{\eta^{d-1}}{d^{3/2}}$, concluding the
proof of Lemma 10.

∎

###### Proof of Theorem 4.

We prove the result in four steps. First, we establish that
$\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))\subseteq E(W_{t},U_{t})$ for every $t$,
and thus we never lose track of the true cost. In a second step, we decompose
the cumulative regret as a function of the different kinds of periods in
algorithm ProjectedCones and provide an upper bound for the one-period regret
under each case. In the third step, we upper bound the number of periods that
we use cone-updates to obtain our regret bound. In the fourth step, we prove
the polynomial runtime.

Step 1. We show that, for each time $t$, the set $E(W_{t},U_{t})$ contains
$\Pi_{\Delta_{t}}\left(C(\mathcal{I}_{t})\right)$. We establish the result by
induction on $t$. $E(W_{2},U_{2})$ trivially contains
$\Pi_{\Delta_{2}}\left(C(\mathcal{I}_{2})\right)$, so the base case is
satisfied. We next consider $t\geq 2$. Suppose that $E(W_{t},U_{t})$ is such
that $\Pi_{\Delta_{t}}\left(C(\mathcal{I}_{t})\right)\subseteq
E(W_{t},U_{t})$. We then analyze $E(W_{t+1},U_{t+1})$ as a function of the
three situations that can happen at time $t$, no update (low-regret period),
cone update, or subspace update.

No update. This case is trivial since $C(\mathcal{I}_{t+1})\subseteq
C(\mathcal{I}_{t})$, $E(W_{t+1},U_{t+1})=E(W_{t},U_{t})$, and
$\Delta_{t+1}=\Delta_{t}$, thus
$\Pi_{\Delta_{t+1}}\left(C(\mathcal{I}_{t+1})\right)\subseteq
E(W_{t+1},U_{t+1})$.

Cone update. This inclusion follows from Lemma 8.

Subspace update. Lemma 10 shows that
$\Pi_{\Delta_{t+1}}(C(\mathcal{I}_{t+1}))$ is contained in $K_{t+1}$. Our
choices of $W_{t+1}$ and $U_{t+1}$ ensure that $K_{t+1}$ is included in
$E(W_{t+1},U_{t+1})$. The same lemma also shows that the constructed
ellipsoidal cone is large enough to contain $K_{t+1}$.

Step 2. Lemma 7 shows that we incur at most regret $\epsilon+\eta$ in low-
regret periods. Therefore, our total regret from low-regret periods is bounded
by $T(\epsilon+\eta)$. For all other periods, we use the trivial regret upper
bound of 1. There are at most $d$ subspace-update periods, so the total regret
from subspace-update periods is bounded by $d$. Let $I^{\pi,p}_{T}$ be the
number of periods where the subspace has dimension $p$ and we use a cone-
update. Bounding the regret of these cone-update periods by 1 as well, we have
that for any $c^{\star}\in S^{d}$, $f_{t}\in\mathcal{F}$, and ${\cal
X}_{t}\in\mathcal{B}$, the total regret is bounded by:

$\displaystyle{\cal R}^{\pi}_{T}\left(c^{\star},\vec{\cal
X}_{T},\vec{f}_{T}\right)\leq T(\epsilon+\eta)+d+\sum_{p=2}^{d}I^{\pi,p}_{T},$
(B-10)

where the last sum starts from $p=2$ because there are never cone-updates when
$p=1$.

Step 3. Lemma 9 shows that for any $p=2,...,d$, we have

$I_{T}^{\pi,p}\leq
20(p-1)^{2}\ln\left(\frac{10p\tan\alpha(E(W_{t_{0}},U_{t_{0}}))}{\epsilon}\right),$

where $t_{0}$ refers to the period where the subspace was increased to $p$.
For simplicity, we replace $p-1$ and $p$ with the larger value $d$:
$I_{T}^{\pi,p}\leq
20d^{2}\ln\left(\frac{10d\tan\alpha(E(W_{t_{0}},U_{t_{0}}))}{\epsilon}\right)$.
At period $t_{0}$, the subspace update constructs a revolution cone such that
$\alpha(E(W_{t_{0}},U_{t_{0}}))=\arccos\eta^{d-1}/d^{3/2}$ (see Lemma 10).
Since $\tan(x)\leq 1/\cos(x)$, we have that
$\tan\alpha(E(W_{t_{0}},U_{t_{0}}))\leq d^{3/2}/\eta^{d-1}$. Summing over all
$p$:

$\sum_{p=2}^{d}I_{T}^{\pi,p}\leq
20d^{3}\ln\left(\frac{10d^{5/2}}{\epsilon\eta^{d-1}}\right).$

Plugging the bound above into Eq. (B-10) and selecting $\epsilon=d/T$,
$\eta=\epsilon/2d$ leads to:

$\displaystyle{\cal R}^{\pi}_{T}\left(c^{\star},\vec{\cal
X}_{T},\vec{f}_{T}\right)$ $\displaystyle\leq$ $\displaystyle
T(\epsilon+\eta)+d+{20d^{3}}\ln\left(\frac{10d^{5/2}}{\epsilon\eta^{d-1}}\right)$
$\displaystyle=$ $\displaystyle d+2+d+{20d^{3}}\ln(5d^{3/2}T^{d}2^{d})$
$\displaystyle=$ $\displaystyle 2+2d+{20d^{3}}\ln
5+{30d^{3}}\ln(d)+{20d^{4}}\ln(2T)=\mathcal{O}(d^{4}\ln T).$

Step 4. This algorithm runs in polynomial time in $d$ and $T$ because every
period’s computation is a function only of $d$. Low-regret periods are
computationally very cheap. Each cone-update period requires a spectral
decomposition which has a running time upper bound of $\mathcal{O}(p^{3})$.
Each subspace-update period requires the computation of a new circumcenter via
algorithm PolyCenter, which runs in polynomial time in $d$ (cf. Lemma 10).
This completes the proof. ∎

###  B.1 Auxiliary Results

######  Lemma B-1 (Robust ellipsoidal cone updates).

Consider a diagonal and positive-definite matrix $W\in\mathbb{D}_{++}^{p-1}$
and an orthonormal matrix $U\in\mathbb{R}^{p}\times\mathbb{R}^{p}$ and define
the ellipsoidal cone $E(W,U)\subset\mathbb{R}^{p}$. Fix $\eta\geq 0$ and a
vector $\delta\in\mathbb{R}^{p}$ such that
$\eta\leq\sqrt{{\delta}^{\prime}_{[2:p]}W{\delta}_{[2:p]}}(2(p-1))^{-1}$ and
$\delta^{\prime}\hat{c}(W,U)\leq 0$. Define

$\displaystyle\bar{\delta}=U^{-1}\delta,\;\beta=-\frac{\eta}{\sqrt{{\bar{\delta}}^{\prime}_{[2:p]}W{\bar{\delta}}_{[2:p]}}},\;b=\frac{W{\bar{\delta}}_{[2:p]}}{\sqrt{{{\bar{\delta}}}^{\prime}_{[2:p]}W{\delta}_{[2:p]}}},\;a=\frac{1+(p-1)\beta}{p}b,$

and

$\displaystyle
N=\frac{(p-1)^{2}}{(p-1)^{2}-1}(1-\beta^{2})\left(W-\frac{2(1+(p-1)\beta)}{p(1+\beta)}bb^{\prime}\right),\;M=\begin{pmatrix}1&a^{\prime}\\\
a&aa^{\prime}-N\end{pmatrix}.$

Let $V^{\prime}\Lambda V$ denote the spectral decomposition of the matrix $M$.
Then

$E(W,U)\cap\\{c\in\mathbb{R}^{d}\;:\;\delta^{\prime}c\geq-\eta\\}\subseteq
E(\widetilde{W},\widetilde{U})$

for $\widetilde{U}=UV,$ and $\widetilde{W}$ is a diagonal matrix such that
$\;\widetilde{W}_{i,i}=\lambda_{i}(N),\;i=1,\cdots,d-1.$ Moreover, if
$\eta=0$, $\prod_{i=1}^{d-1}\lambda_{i}(\widetilde{W})\leq
e^{-1/2(d-1)}\prod_{i=1}^{d-1}\lambda_{i}(W)$. Otherwise
$\prod_{i=1}^{d-1}\lambda_{i}(\widetilde{W})\leq
e^{-1/20(d-1)}\prod_{i=1}^{d-1}\lambda_{i}(W)$.

###### Proof of Lemma B-1.

We first consider the case where $U$ is the identity matrix, so that
$E(W,U)=E(W)$ and $\bar{\delta}=\delta$. The proof strategy is as follows. In
the first step, we show that
$E(W)\cap\\{c\in\mathbb{R}^{d}:\;\delta^{\prime}c\geq 0\\}$ is contained in a
half-ellipsoidal cone. Second, we show that we can use a variation of the
ellipsoid method to update this half-ellipsoidal cone and construct an
appropriate updated ellipsoidal cone. In a third step, we apply a theorem from
Seeger and Vidal-Nuñez (2017) in order to characterize the obtained
ellipsoidal cone in terms of a standard-position cone and its orthonormal
rotation.

Step 1. Let us consider the intersection of $E(W)$ and a hyperplane
characterized by its circumcenter $\hat{c}(E(W))=e_{1}$. We denote such a
hyperplane as $H=\\{c\in\mathbb{R}^{d}:\;e_{1}^{\prime}c=1\\}$. Since
$c_{[1]}>0$ and $E(W)$ is a cone, we can scale any element $c\in E(W)$ such
that the scaled vector lies in the intersection. Moreover, the intersection
will be an ellipsoid given by

$E_{H}(W)=\\{c\in\mathbb{R}_{+}\times\mathbb{R}^{d-1}:\;c_{[2:d]}^{\prime}W^{-1}c_{[2:d]}\leq
1,\;c_{[1]}=1\\},$

which is precisely the equation of an ellipsoid in $\mathbb{R}^{d-1}$ that
lives in a $(d-1)$\- dimensional subspace of $\mathbb{R}^{d}$. The ellipsoid
$E_{H}(W)$ defined above was obtained by a specific type of projection known
in the literature as the perspective projection of $E(W)$ onto the hyperplane
$H$.

Let us define also
$A=E(W)\cap\\{c\in\mathbb{R}^{d}:\;{{\delta}}^{\prime}c\geq-\eta\\}$. Next,
consider some $c\neq 0\in A$. Since $A\subseteq E(W)$, we must have
$c_{[1]}>0$. Moreover, $A$ is a cone since it is the intersection of two
cones. Then, $c/c_{[1]}\in A$ and $c/c_{[1]}\in H$. Hence,

$\displaystyle c/c_{[1]}$ $\displaystyle\in$ $\displaystyle A\cap H$
$\displaystyle=$ $\displaystyle E(W)\cap
H\cap\\{c\in\mathbb{R}^{p}:\;\delta^{\prime}c\geq-\eta\\}$ $\displaystyle=$
$\displaystyle
E_{H}(W)\cap\\{c\in\mathbb{R}^{d}:\;{\delta}^{\prime}c\geq-\eta\\}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle
E_{H}(W)\cap\\{c\in\mathbb{R}^{d}:\;\delta_{[1]}+{\delta_{[2:d]}}^{\prime}c_{[2:d]}\geq-\eta\\}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\subseteq}}$ $\displaystyle
E_{H}(W)\cap\\{c\in\mathbb{R}^{d}:\;{\delta_{[1]}+\delta_{[2:d]}}^{\prime}c_{[2:d]}\geq-\eta+\delta^{\prime}\hat{c}(E(W))\\}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\subseteq}}$ $\displaystyle
E_{H}(W)\cap\\{c\in\mathbb{R}^{d}:\;{\delta_{[2:d]}}^{\prime}c_{[2:d]}\geq-\eta\\},$

where $(a)$ follows from the fact that $E_{H}(W)\subset H$ so $c_{[1]}$ = 1.
$(b)$ follows from the fact that $\hat{c}(E(W))^{\prime}\delta\leq 0$ by
assumption and $(c)$ follows from the fact that =
$\hat{c}(E(W))^{\prime}\delta=e_{1}^{\prime}\delta=\delta_{[1]}\leq 0$. The
set of the last equation is precisely the ellipsoid $E_{H}(W)$ with a shallow-
cut, and hence is a description of a half-ellipsoid.

Step 2. We now use the ellipsoid method update to replace this half-ellipsoid
with its own Löwner-John ellipsoid. The definitions of $a$, $N$ and $\beta$
are precisely the ones for an ellipsoid update with shallow-cut (See Eq.
(3.1.16) and Eq. (3.1.17) of Grötschel et al. (1993)). Therefore,

$E_{H}(W)\cap\\{c\in\mathbb{R}^{d}:\;\bar{\delta}_{[2:d]}^{\prime}c_{[2:d]}\geq-\eta\\}\subseteq\\{c\in\mathbb{R}^{d}:\;(c_{[2:d]}-a)^{\prime}N^{-1}(c_{[2:d]}-a)\leq
1,\;c_{[1]}=1\\}.$

Furthermore, since $c_{[1]}>0$, we have that

$c/c_{[1]}\in\\{c\in\mathbb{R}^{d}:\;(c_{[2:d]}-a)^{\prime}N^{-1}(c_{[2:d]}-a)\leq
1\\}$

if and only if

$c\in\\{c\in\mathbb{R}^{d}:\;(c_{[2:d]}-c_{[1]}a)^{\prime}N^{-1}(c_{[2:d]}-c_{[1]}a)\leq
c^{2}_{[1]}\\}.$

Hence, if $c\in A$, then we must have that
$c\in\\{c\in\mathbb{R}^{d}:\;(c_{[2:d]}-c_{[1]}a)^{\prime}N^{-1}(c_{[2:d]}-c_{[1]}a)\leq
c^{2}_{[1]}\\}$.

We finish the second step by showing the contraction in the product of the
eigenvalues of the matrix $N$ (or equivalently, its volume).

Note that if $\eta=0$, the update equations reduces to the standard update
equations of the ellipsoid method, then the standard volume reduction of the
holds and we get
$\prod_{i=1}^{p-1}\lambda_{i}(N)\leq\prod_{i=1}^{p-1}\lambda_{i}(W)e^{1/2(p-1)}$.

If $\eta>0$, we need to argue that the shallow cuts are still sufficiently
deep to induce a reduction in the product of the eigenvalues first need to
ensure that $\beta\geq 1/(p-1)$ in order to have
$\prod_{i=1}^{p-1}\lambda_{i}(N)\leq\prod_{i=1}^{p-1}\lambda_{i}(W)e^{(1+\beta(p-1))/5(p-1)}$
(See Eq. (3.3.21) of Grötschel et al. (1993)). Since in this case

$0<\eta\leq\frac{\sqrt{{\delta}^{\prime}_{[2:p]}W{\delta}_{[2:p]}}}{2(p-1)}$

we have that,

$\beta=-\frac{\eta}{\sqrt{{\delta}^{\prime}_{[2:p]}W{\delta}_{[2:p]}}}\geq-\frac{1}{2(p-1)},$

substituting the lower bound of $\beta$ above leads to
$\prod_{i=1}^{p-1}\lambda_{i}(N)\leq\prod_{i=1}^{p-1}\lambda_{i}(W)e^{1/20(p-1)}$.

Step 3. We have now constructed an ellipsoidal cone
$\\{c\in\mathbb{R}^{d}:\;(c_{[2:d]}-c_{[1]}a)^{\prime}N^{-1}(c_{[2:d]}-c_{[1]}a)\leq
c^{2}_{[1]}\\}$ that contains the half ellipsoidal cone of interest, which is
a cone not in standard position. However, instead of having the set described
by a rotation orthonormal basis, we have it described via a translation of the
center of the ellipsoid at $H$. In the remainder of this proof, we show how to
construct a representation of this ellipsoidal cone that is consistent with
our Definition 4. That is, we need to find a mapping from the parameters $N$
and $a$ to the matrices $W$ and $U$.

To find this mapping, we apply a theorem from (Seeger and Vidal-Nuñez, 2017,
Theorem 4.4 page 296). The theorem states that for

$M=\begin{bmatrix}1&a^{\prime}\\\ a&aa^{\prime}-N\end{bmatrix},$

the matrix $M$ is invertible and the spectral decomposition
$M=V^{\prime}\Lambda V$ allows us to write the ellipsoidal cone
$E(\hat{W},\hat{U})$ that is identical to
$\\{c\in\mathbb{R}^{d}:\;(c_{[2:d]}-c_{[1]}a)^{\prime}N^{-1}(c_{[2:d]}-c_{[1]}a)\leq
c^{2}_{[1]}\\}$, but in standard representation. This ellipsoidal cone is
given by $\hat{U}=V$ and $\hat{W}$ equal to the diagonal matrix with diagonal
entries $\hat{W}_{ii}$ given by $-\lambda_{d-i+1}(M)/\lambda_{1}(M)$, for
$i=1,\cdots,d-1$, where the eigenvalues of $M$ are in nondecreasing order.

For our ellipsoidal update, we will use the same orthonormal rotation as the
one produced by Seeger and Vidal-Nuñez’s theorem: $\widetilde{U}=\hat{U}$. At
this point, we could declare the proof done if we had also defined in the
algorithm $\widetilde{W}$ to be equal to $\hat{W}$. However, in order to
facilitate our analysis, we use a different choice of $\widetilde{W}$ by
setting $\widetilde{W}_{ii}=\lambda_{i}(N)$ for all $i=1,...,d-1$. Hence, in
order to conclude the proof, we still need to show that our choice of
$\widetilde{W}$ has eigenvalues that are at least as large as $\hat{W}$. To be
specific, we need to prove that for all $i=1,...,d-1$,
$\lambda_{i}(\hat{W})=-\lambda_{d-i+1}(M)/\lambda_{1}(M)\leq\lambda_{i}(N)=\lambda_{i}(\widetilde{W})$.
Our definitions of $M$, $N$ and $a$ satisfy:

$M=\begin{bmatrix}0&0\\\ 0&-N\end{bmatrix}+\begin{bmatrix}1\\\
a\end{bmatrix}\begin{bmatrix}1\\\ a\end{bmatrix}^{\prime}.$

Since the matrix $N$ is obtained by one iteration of the ellipsoid method, we
must have that $N$ has strictly positive eigenvalues. Hence, the interlacing
theorem (Hwang, 2004) implies that $M$ has one positive eigenvalue and $d-1$
negative eigenvalues.

Furthermore, we have that $\lambda_{max}(M)=\lambda_{1}(M)=\sup_{c\in
S^{d}}c^{\prime}Mc$. Since $c=e_{1}$ satisfies $c^{\prime}Mc=1$, we must have
that $\lambda_{1}(M)\geq 1$. Finally, another application of the interlacing
theorem for $M$ gives us that for $i=1,\cdots,d-1$, (again in nondecreasing
orther) satisfies $\lambda_{i}(M)\geq\lambda_{i}(-N)$. In turn,

$\lambda_{i+1}(M)\geq\lambda_{i}(-N)=-\lambda_{d-i}(N),$

and we get that

$-\lambda_{d-i+1}(M)/\lambda_{1}(M)\leq-\lambda_{d-i+1}(M)\leq\lambda_{i}(N)=\lambda_{i}(\widetilde{W}),\;i=1,\cdots,d-1.$

Hence, the choice of $\widetilde{W}$ in algorithm ConeUpdate is at least as
large as necessary, which concludes the proof for the case where $U$ is the
identity matrix.

For the general case (when $U$ is not the identity matrix), it suffices to
rotate $\delta$ by $U^{-1}$, which is equivalent to analyze the problem under
the basis representation given by the rows of $U$. After that, we return to
the canonical basis by rotating $V$ by $U$, which leads to $\widetilde{U}=UV$.
∎

######  Lemma B-2 (Inradius of simplicial cones).

Fix $p\geq 2$ and let $K\subset\mathbb{R}^{p}$ denote a simplicial cone, i.e.,
it can be written as
$K=\\{c\in\mathbb{R}^{p}:\;c=\sum_{i=1}^{p}\alpha_{i}g_{i},\;\alpha_{i}\geq
0\\}$, where the $g_{i}$’s are linearly independent unit norm vectors. Define
$G\in\mathbb{R}^{p}\times\mathbb{R}^{p}$ to be the matrix where the columns
are the generators $g_{i}$, $i=1,\cdots,p$. We have that the inradius
$\rho(K):=\max_{x\in S^{d}\cap K}\min_{y\in\partial K}\|x-y\|$ is lower
bounded as follows

$\rho(K)\geq\frac{1}{\sqrt{p}}\sqrt{\frac{\lambda_{min}(G^{\prime}G)}{\lambda_{max}(G^{\prime}G)}}.$

###### Proof of Lemma B-2.

We denote $x_{\rho}=\operatorname*{arg\,max}_{x\in S^{d}\cap
K}\min_{y\in\partial K}\|x-y\|$ as the incenter of $K$, which is analogous to
the circumcenter, but referring to the axis of the largest revolution cone
inside our cone of interest. Let $P$ denote the nonnegative orthant in
$\mathbb{R}^{p}$. One can check that $\rho(P)=\frac{1}{\sqrt{p}}$ and the
incenter of $P$ is given by $x_{\rho}=\mathbf{1}\frac{1}{\sqrt{p}}$ (see, for
instance, Henrion and Seeger (2010)). We have

$\displaystyle\rho(K)$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\max_{\pi\in S^{d}\cap
K}\min_{\delta\in\partial(K)}\|\pi-\delta\|$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$
$\displaystyle\max_{\|Gx\|=1,x\in P}\;\min_{Gy\in\partial(K)}\|Gx-Gy\|$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}$
$\displaystyle\max_{\|Gx\|=1,x\in P}\;\min_{y\in\partial(P)}\|Gx-Gy\|$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}$
$\displaystyle\max_{\|Gx\|=1,x\in P}\;\min_{y\in\partial(P)}\|G(x-y)\|$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}$
$\displaystyle\max_{\|Gx\|=1,x\in
P}\;\min_{y\in\partial(P)}\sqrt{(x-y)^{\prime}G^{\prime}G(x-y)}$
$\displaystyle\stackrel{{\scriptstyle}}{{\geq}}$
$\displaystyle\max_{\|Gx\|=1,x\in
P}\;\min_{y\in\partial(P)}\|x-y\|\sqrt{\lambda_{min}(G^{\prime}G)}$

$(a)$ follows from the definition of inradius, $(b)$ follows from the fact
that $\pi\in K\iff\pi=Gx$ for some $x\in P$ since $K$ is defined by the
nonnegative linear combination of the columns of $G$, and by the fact that $G$
is full rank by assumption, so $y=G^{-1}\delta$ is well defined. $(c)$ holds
since $G$ is linear and establishes a bijection between the generators of $P$
and $K$. The inequality follows from the fact that $G^{\prime}G$ is positive
definite (which follows from $G$ being full column-rank).

Moreover, since $G$ has full column-rank, we have that $Gx=0$ if and only if
$x=0$, implying that $x=\frac{1}{\|G\mathbf{1}\|}\mathbf{1}$ has only positive
components and is well defined since $\|G\mathbf{1}\|\neq 0$. Thus,
$x=\frac{1}{\|G\mathbf{1}\|}\mathbf{1}$ is feasible for the maximization
problem presented above and we have

$\displaystyle\rho(K)$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}$
$\displaystyle\sqrt{\lambda_{min}(G^{\prime}G)}\min_{y\in\partial(P)}\left\|\frac{1}{\|G\mathbf{1}\|}\mathbf{1}-y\right\|$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}$
$\displaystyle\frac{\sqrt{p}}{\|G\mathbf{1}\|}\sqrt{\lambda_{min}(G^{\prime}G)}\min_{y\in\partial(P)}\left\|\frac{1}{\sqrt{p}}\mathbf{1}-y\frac{\|G\mathbf{1}\|}{\sqrt{p}}\right\|$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$
$\displaystyle\frac{\sqrt{p}}{\|G\mathbf{1}\|}\sqrt{\lambda_{min}(G^{\prime}G)}\min_{y\in\partial(P)}\left\|\frac{1}{\sqrt{p}}\mathbf{1}-y\right\|$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}$
$\displaystyle\frac{\sqrt{p}}{\|G\mathbf{1}\|}\sqrt{\lambda_{min}(G^{\prime}G)}\frac{1}{\sqrt{p}}$
$\displaystyle=$
$\displaystyle\frac{1}{\|G\mathbf{1}\|}\sqrt{\lambda_{min}(G^{\prime}G)},$

where $(a)$ follows from the fact that $\frac{1}{\|G\mathbf{1}\|}$ is feasible
for the maximization problem, $(b)$ follows from the fact that we can always
scale by a positive constant our choice for $y$ in the minimization problem,
and $(c)$ follows from the fact that the minimization problem over $y$ is
lower bounded by the definition of the inradius of the nonnegative orthant.

In addition, we have
$\|G\mathbf{1}\|^{2}=\mathbf{1}^{\prime}G^{\prime}G\mathbf{1}\leq\|\mathbf{1}\|^{2}\lambda_{max}(G^{\prime}G)=p\lambda_{max}(G^{\prime}G)$.
In turn, we have

$\displaystyle\rho(K)$ $\displaystyle\stackrel{{\scriptstyle}}{{\geq}}$
$\displaystyle\frac{1}{\sqrt{p}}\sqrt{\frac{\lambda_{min}(G^{\prime}G)}{\lambda_{max}(G^{\prime}G)}}.$

∎

######  Lemma B-3 (Condition number of Gram-Matrices).

Let $p\geq 2$ and let $G$ be a full-column rank matrix with unit norm columns
denoted by $g_{i}$, $i=1,\cdots,p$. Let $\Pi_{g_{-i}}(\cdot)$ denote the
projection operator on the subspace generated by
$\\{g_{1},\ldots,g_{p}\\}\setminus\\{g_{i}\\}$. Let

$\displaystyle\varphi=\min\\{\|g_{i}-\Pi_{g_{-i}}(g_{i})\|:i=2,...,p\\}.$
(B-11)

Then

$\frac{\lambda_{max}(G^{\prime}G)}{\lambda_{min}(G^{\prime}G)}\leq\left(\frac{p}{\varphi}\right)^{2}.$

###### Proof of Lemma B-3.

We start from an upper bound on the ratio of largest to smallest eigenvalues
of $G^{\prime}G$ in terms of its trace and the trace of its inverse. Recall
that $G$ is full column-rank, which implies that $G^{\prime}G$ is positive
definite and we have that

$\displaystyle\frac{\lambda_{max}(G^{\prime}G)}{\lambda_{min}(G^{\prime}G)}=\lambda_{max}(G^{\prime}G)\lambda_{max}((G^{\prime}G)^{-1})\leq\mbox{tr}(G^{\prime}G)\mbox{tr}((G^{\prime}G)^{-1}),$
(B-12)

where the last inequality follows from the fact that $G^{\prime}G$ and
$(G^{\prime}G)^{-1}$ are positive definite and all eigenvalues are
nonnegative.

Since the diagonal elements of $G^{\prime}G$ are equal to one,
$\mbox{tr}(G^{\prime}G)=p$. Next, we establish an upper bound on
$\mbox{tr}((G^{\prime}G)^{-1})$. In order to do that, we use a fact about the
inverse of correlation matrices, commonly denoted as precision matrices. Note
that $G^{\prime}G$ is a correlation matrix because all the columns of $G$ have
norm one and we can consider that each $g_{i}$ is an “observation” of some
data in $\mathbb{R}^{p}$. For the inverse of correlation matrices, we have
that the diagonal elements ($a_{ii}$) of $(G^{\prime}G)^{-1}$ satisfy

$\displaystyle R^{2}_{i}=1-\frac{1}{a_{ii}},$ (B-13)

where $R^{2}_{i}$ is the coefficient of determination of the linear regression
problem of the column $g_{i}$ onto the other columns $g_{j}$, $j\neq i$ (Raveh
(1985)). Note that since the $g_{i}$’s have unit norm,
$R_{i}^{2}=\|\Pi_{g_{-i}}(g_{i})\|^{2}\leq 1$ and it follows from Eq. (B-13)
that

$a_{ii}=\frac{1}{1-\|\Pi_{g_{-i}}(g_{i})\|^{2}}\leq\frac{1}{1-\max_{i=1,...,p}\|\Pi_{g_{-i}}(g_{i})\|^{2}}.$

Note that
$\|g_{i}\|^{2}=\|\Pi_{g_{-i}}(g_{i})\|^{2}+\|g_{i}-\Pi_{g_{-i}}(g_{i})\|^{2}$,
and using the fact that $\|g_{i}\|=1$ and (B-11), we have

$\max_{i=1,...,p}\|\Pi_{g_{-i}}(g_{i})\|^{2}\leq 1-\varphi^{2}.$

In turn, we deduce that for $i=1,...p$

$a_{ii}\leq\frac{1}{\varphi^{2}},$

which implies that $\mbox{tr}((G^{\prime}G)^{-1})=\sum_{i}a_{ii}\leq
p/\varphi^{2}$. Hence, returning to Eq. (B-12), we have

$\frac{\lambda_{max}(G^{\prime}G)}{\lambda_{min}(G^{\prime}G)}\leq\left(\frac{p}{\varphi}\right)^{2},$

which concludes the proof. ∎

######  Lemma B-4 (Residuals).

Let $g_{i}\in\mathbb{R}^{p}$, be a sequence of $p$ unit norm vectors such that

$\displaystyle\|g_{i}-\Pi_{g_{1},\cdots,g_{i-1}}(g_{i})\|^{2}\geq\eta^{2},\quad
i=2,\cdots,p,$ (B-14)

where $\Pi_{g_{1},\cdots,g_{i-1}}(\cdot)$ denote the projection operator on
the subspace generated by $g_{1},\cdots,g_{i-1}$. Then the residuals of the
projection of an arbitrary vector on the subspace generated by all other
vectors can be lower bounded as follows

$\|g_{i}-\Pi_{g_{-i}}(g_{i})\|^{2}\geq\eta^{2(p-i)}(\eta^{2})^{\mathbf{1}\\{i>1\\}},\quad
i=1,...,p,$ (B-15)

where $\Pi_{g_{-i}}(\cdot)$ denotes the projection operator on the subspace
generated by $\\{g_{1},\ldots,g_{p}\\}\setminus\\{g_{i}\\}$.

###### Proof of Lemma B-4.

In order to understand how close $\|g_{i}-\Pi_{g_{-i}}(g_{i})\|^{2}$ can be to
zero, we need to understand how much of the residual
$\|g_{i}-\Pi_{g_{1},...,g_{i-1}}(g_{i})\|^{2}$ can be reduced when adding the
new vectors $g_{j}$’s, for $j=i+1,..,p$. The more the vectors $g_{j}$’s can
explain, the closest $\|g_{i}-\Pi_{g_{-i}}(g_{i})\|^{2}$ gets to zero. We will
leverage that the vectors $g_{j}$’s satisfy Eq. (B-14) to establish that there
is a limit for how small $\|g_{i}-\Pi_{g_{-i}}(g_{i})\|^{2}$ can be.

Two key properties that allow us to establish the result can be derived from
the Frisch-Waugh-Lovell Theorem (Lovell, 2008). Intuitively, the theorem
states that when we add a new regressor to a linear regression model, it
suffices to consider only the component of the new regressor that is
orthogonal to the linear subspace of the regressors already present. We will
use the following properties implied by the theorem:

  * •

Projection decomposition: for $i=1,...,p$ and $k=0,...,p-i$,

$\displaystyle\Pi_{g_{1},...,g_{i+k}}(g_{i+k+1})=\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i+k+1})+\Pi_{(g_{i}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i}))}(g_{i+k+1}),$
(B-16)

  * •

$R^{2}$ decomposition: for $i=1,...,p$ and $k=0,...,p-i$,

$\displaystyle\|\Pi_{g_{1},...,g_{i+k}}(g_{i+k+1})\|^{2}=\|\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i+k+1})\|^{2}+\|\Pi_{(g_{i}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i}))}(g_{i+k+1})\|^{2}.$
(B-17)

The first property states that we can decompose the projection of $g_{i+1}$ in
two parts. First, we consider the projection of $g_{i+1}$ onto the subspace
without $g_{i}$. Second, we consider the projection of $g_{i+1}$ on the
component of $g_{i}$ that is orthogonal to the subspace considered in the
previous step, i.e., the projection of $g_{i+1}$ onto the vector
$g_{i}-\Pi_{g_{1},...,g_{i-1}}(g_{i})$. For the second property, since
$g_{i}-\Pi_{g_{1},...,g_{i-1}}(g_{i+1})$ is orthogonal to the vectors
$g_{1},...,g_{i-1}$, we have a situation in which the triangle equality holds
and we can decompose the coefficient of determination $R^{2}$ in the
contribution of each orthogonal set of regressors.

Note that when $i=p$, the result follows from the assumption (cf. Eq.(B-14)).
Next, fix $i$ in $\\{1,...,p-1\\}$ and define the following sequence of
residuals:

$\displaystyle
r^{k}_{i}=g_{i}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i}),\quad
k=0,...,p-i.$ (B-18)

When $i=1$ and $k=0$ we will define by convention $r^{0}_{1}=g_{1}$.

We will show that the sequence of residuals satisfies
$\|r^{k+1}_{i}\|^{2}\geq\|r^{k}_{i}\|^{2}\eta^{2}$. This recursive
relationship allows us to write

$\|r_{i}^{k+1}\|^{2}\geq\|r_{i}^{0}\|^{2}\eta^{2(k+1)},$

Moreover, $\|r_{i}^{0}\|^{2}\geq\eta^{2}$ for $i>1$ (cf. Eq. (B-14)), and
$\|r_{1}^{0}\|^{2}=\|g_{1}\|^{2}=1$, which implies that for $k=0,...,p-i$,

$\|r^{k}_{i}\|\geq\begin{cases}\eta^{2k},&i=1\\\ \eta^{2(k+1)},&2\leq i\leq
p-1,\end{cases}$

Taking $k=p-i$ leads to (B-15). Next, we establish that
$\|r_{i}^{k+1}\|^{2}\geq\|r_{i}^{0}\|^{2}\eta^{2(k+1)}$ holds.

We define the following vectors

$\nu_{i}^{k}=g_{i+k}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k-1}}(g_{i+k}),\quad
k=0,...,p-i.$

Note that Eq. (B-17) implies that $\nu_{i}^{k}$ is the vector that effectively
contributes to reduce the residual $r_{i}^{k-1}$ when $g_{i+k}$ is used to
explain $g_{i}$ and $\\{g_{1},...,g_{i+k-1}\\}\setminus\\{g_{i}\\}$ were
already considered. Eq. (B-17) gives us that

$\|\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k+1}}(g_{i})\|^{2}=\|\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i})\|^{2}+\|\Pi_{\nu_{i}^{k+1}}(g_{i})\|^{2},$

and since $g_{i}$ has unit norm, by construction, we have

$\displaystyle\|\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k+1}}(g_{i})\|^{2}$
$\displaystyle=$ $\displaystyle 1-\|r^{k+1}_{i}\|^{2}$
$\displaystyle\|\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i})\|^{2}$
$\displaystyle=$ $\displaystyle 1-\|r^{k}_{i}\|^{2},$

and hence the following recursive relationship

$\displaystyle\|r^{k+1}_{i}\|^{2}$ $\displaystyle=$
$\displaystyle\|r^{k}_{i}\|^{2}-\|\Pi_{\nu_{i}^{k+1}}(g_{i})\|^{2}.$ (B-19)

Next, we upper bound $\|\Pi_{\nu_{i}^{k+1}}(g_{i})\|^{2}$. We have that

$\displaystyle\|\Pi_{\nu_{i}^{k+1}}(g_{i})\|^{2}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{(g_{i}^{\prime}\nu_{i}^{k+1})^{2}}{\|\nu_{i}^{k+1}\|^{2}}\stackrel{{\scriptstyle(a)}}{{=}}\frac{\Big{(}(\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i})+r^{k}_{i})^{\prime}\nu_{i}^{k+1}\Big{)}^{2}}{\|\nu_{i}^{k+1}\|^{2}}\stackrel{{\scriptstyle(b)}}{{=}}\frac{\Big{(}{r^{k}_{i}}^{\prime}\nu_{i}^{k+1}\Big{)}^{2}}{\|\nu_{i}^{k+1}\|^{2}},$
(B-20)

where $(a)$ follows from the definition of $r_{i}^{k}$ (Eq. (B-18)), and $(b)$
follows from the fact that $\nu_{i}^{k+1}$ and
$\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i})$ are orthogonal since we
removed the projection of $g_{i+1}$ onto the subspace generated by
$\\{g_{1},...,g_{i+k}\\}\setminus\\{g_{i}\\}$ when constructing
$\nu_{i}^{k+1}$. Next we develop an alternative representation for
$\nu_{i}^{k+1}$. We have

$\displaystyle\nu_{i}^{k+1}$ $\displaystyle=$ $\displaystyle
g_{i+k+1}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i+k+1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\Pi_{g_{1},...,g_{i+k}}(g_{i+k+1})+r^{0}_{i+k+1}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i+k+1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$
$\displaystyle\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i+k+1})+\Pi_{\beta_{i}^{k}}(g_{i+k+1})+r^{0}_{i+k+1}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i+k+1})$
$\displaystyle=$ $\displaystyle\Pi_{\beta_{i}^{k}}(g_{i+k+1})+r^{0}_{i+k+1},$

where (a) follows from the definition of $r^{0}_{i+k+1}$ and in (b), we have
used Eq. (B-16) and defined
$\beta_{i}^{k}=g_{i}-\Pi_{g_{1},...,g_{i-1},g_{i+1},...,g_{i+k}}(g_{i})$.
Using this new representation for $\nu_{i}^{k+1}$ in Eq. (B-20) yields

$\displaystyle\Big{(}{r_{i}^{k}}^{\prime}\nu_{i}^{k+1}\Big{)}^{2}$
$\displaystyle=\Big{(}{r_{i}^{k}}^{\prime}(\Pi_{\beta_{i}^{k}}(g_{i+k+1})+r_{i+k+1}^{0})\Big{)}^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\Big{(}{r_{i}^{k}}^{\prime}\Pi_{\beta_{i}^{k}}(g_{i+k+1})\Big{)}^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\|{r_{i}^{k}}\|^{2}\|\Pi_{\beta_{i}^{k}}(g_{i+k+1})\Big{\|}^{2},$
(B-21)

where $(a)$ follows from the fact that $r_{i+k+1}^{0}$ is orthogonal to the
subspace generated by $g_{1},...,g_{i+k}$, to which $r_{i}^{k}$ belongs and
(b) follows from the Cauchy-Schwarz inequality. In addition, we have that
$\Pi_{\nu_{i}^{k}}(g_{i+k+1})$ and $r_{i+k+1}^{0}$ are orthogonal since
$r_{i+k+1}^{0}$ is by definition orthogonal to the subspace generated by
$g_{1},...,g_{i+k}$, which $\Pi_{\beta_{i}^{k}}(g_{i+k+1})$ belongs to.
Therefore, we have that

$\|\nu_{i}^{k+1}\|^{2}=\|\Pi_{\beta_{i}^{k}}(g_{i+k+1})+r_{i+k+1}^{0}\|^{2}=\|\Pi_{\beta_{i}^{k}}(g_{i+k+1})\|^{2}+\|r_{i+k+1}^{0}\|^{2},$

which implies that

$\frac{\|\Pi_{\beta_{i}^{k}}(g_{i+k+1})\|^{2}}{\|\nu_{i}^{k+1}\|^{2}}=1-\frac{\|r_{i+k+1}^{0}\|^{2}}{\|\nu_{i}^{k+1}\|^{2}}\leq
1-\|r_{i+k+1}^{0}\|^{2},$

where the inequality follows from the fact that $\nu_{i}^{k+1}$ is a
projection of a unit vector,so $\|\nu_{i}^{k+1}\|^{2}\leq 1$.

Returning to Eq. (B-19) and Eq. (B-20), we have established that

$\|r^{k+1}_{i}\|^{2}\geq\|r^{k}_{i}\|^{2}-\|{r_{i}^{k}}\|^{2}(1-\|r_{i+k+1}^{0}\|^{2})=\|{r_{i}^{k}}\|^{2}\|r_{i+k+1}^{0}\|^{2}\geq\|{r_{i}^{k}}\|^{2}\eta^{2},$

where the last inequality follows from assumption (cf. Eq. (B-14)). This
completes the proof.

∎