$\delta$-PAC T2 has the following upper bound:

$\displaystyle\mathbb{E}[\tau_{\delta}]\leq
O\left(\dfrac{\eta\log(C(\eta_{0},\eta))\log
J}{D_{1}^{\prime}}+\dfrac{\log(J/\delta)}{D_{0}^{\prime}}+JC(\eta_{0},\eta)^{1/\eta}\delta^{D_{0}^{\prime}/\eta^{2}}\right).$

###### Proof.

Step 1 (Definitions): Let the action
$i_{\bm{\theta}\bm{\theta}^{\prime}}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\mathop{\rm
arg\,max}\limits_{i\in[n]}(\mu_{i}(\bm{\theta})-\mu_{i}(\bm{\theta}^{\prime}))^{2}$.
Let $\widehat{\bm{\theta}}(t)$ denote the most likely hypothesis at round $s$
and $\tilde{\bm{\theta}}(t)$ be the second most likely hypothesis at round
$s$. Note that T2 only samples the action
$i_{\bm{\theta}\bm{\theta}^{\prime}}$ at round $s$ when
$\widehat{\bm{\theta}}(s)=\bm{\theta}$ and
$\tilde{\bm{\theta}}(s)=\bm{\theta}^{\prime}$. Again, let
$L_{Y^{t}}(\bm{\theta})$ denote the total sum of squared errors of hypothesis
$\bm{\theta}$ till round $t$. We further define the set
$\mathcal{I}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\\{i\in[n]:i=\mathop{\rm
arg\,max}_{i^{\prime}\in[n]}(\mu_{i^{\prime}}(\bm{\theta})-\mu_{i^{\prime}}(\bm{\theta}^{\prime}))^{2}\text{
for some }\bm{\theta},\bm{\theta}^{\prime}\in\mathbf{\Theta}\\}$.

Step 2 (Define stopping time): We define the stopping time $\tau_{\delta}$ for
the policy T2 as follows:

$\displaystyle\tau_{\delta}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min\\{t:\exists\bm{\theta}\in\mathbf{\Theta},L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\bm{\theta})>\beta(J,\delta),\forall\bm{\theta}^{\prime}\neq\bm{\theta}\\}$
(35)

where, $\beta(J,\delta)$ is the threshold function defined in (22).

Step 3 (Define bad event): We define the bad event $\xi^{\delta}(\bm{\theta})$
for the sub-optimal hypothesis $\bm{\theta}$ as follows:

$\displaystyle\xi^{\delta}(\bm{\theta})\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\\{L_{Y^{\tau_{\delta}}}(\bm{\theta}^{\prime})-L_{Y^{\tau_{\delta}}}(\bm{\theta})>\beta(J,\delta),\forall\bm{\theta}^{\prime}\neq\bm{\theta}\\}.$
(36)

The event $\xi^{\delta}(\bm{\theta})$ denotes that a sub-optimal hypothesis
$\bm{\theta}$ has been declared optimal at stopping time $\bm{\theta}$ and its
sum of squared error is smaller than any other hypothesis
$\bm{\theta}^{\prime}\neq\bm{\theta}$ at $\tau_{\delta}$.

Step 4 (Decomposition of bad event): Decomposing the bad event follows the
same approach in Theorem 2. A crucial thing to note is that the stopping time
only depends on the threshold function $\beta(J,\delta)$ and not on the
sampling rule. Again we can decompose the bad event to show that only
comparing $\bm{\theta}$ against $\bm{\theta}^{*}$ is enough to guarantee a
$\delta$-PAC policy. Finally following (28) we can decompose the bad event
$\xi^{\delta}(\bm{\theta})$ as follows:

$\displaystyle\xi^{\delta}(\bm{\theta})\subseteq$
$\displaystyle\\{\widehat{\bm{\theta}}(\tau_{\delta})=\bm{\theta},L_{Y^{\tau_{\delta}}}(\bm{\theta}^{*})-L_{Y^{\tau_{\delta}}}(\bm{\theta})>\beta(J,\delta)\\}$
(37)

such that we compare the sub-optimal hypothesis $\bm{\theta}$ only with
optimal hypothesis $\bm{\theta}^{*}$.

Step 5 (Control bad event): The control of the bad event follows the same
approach in Theorem 2. We want to show that based on the stopping time
definition and the bad event $\xi^{\delta}(\bm{\theta})$ the T2 stops and
outputs the correct hypothesis $\bm{\theta}^{*}$ with $1-\delta$ probability.
As shown in Step $4$, we can define the error event
$\xi^{\delta}(\bm{\theta})$ as follows:

$\displaystyle\xi^{\delta}(\bm{\theta})\subseteq$
$\displaystyle\\{\widehat{\bm{\theta}}(\tau_{\delta})=\bm{\theta},L_{Y^{\tau_{\delta}}}(\bm{\theta}^{*})-L_{Y^{\tau_{\delta}}}(\bm{\theta})>\beta(J,\delta)\\}$

Again define
$\tau_{\bm{\theta}^{*}\bm{\theta}}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min\\{t:T_{Y^{t}}(\bm{\theta}^{*},\bm{\theta})>\beta(J,\delta)\\}$.
Then following the same steps as in Step 5 of Theorem 2 we can show that

$\displaystyle\mathbb{P}\left(\tau_{\delta}<\infty,\widehat{\bm{\theta}}(\tau_{\delta})\neq\bm{\theta}^{*}\right)$
$\displaystyle\leq\mathbb{P}\left(\exists\bm{\theta}\in\mathbf{\Theta}\setminus\\{\bm{\theta}^{*}\\},\exists
t\in\mathbb{N}:T_{Y^{t}}(\bm{\theta}^{*},\bm{\theta})>\beta(J,\delta)\right)$
$\displaystyle\leq\sum_{\bm{\theta}\neq\bm{\theta}^{*}}\mathbb{P}\left(L_{Y^{\tau_{\bm{\theta}^{*}\bm{\theta}}}}(\bm{\theta}^{*})-L_{Y^{\tau_{\bm{\theta}^{*}\bm{\theta}}}}(\bm{\theta})>\beta(J,\delta),\tau_{\bm{\theta}^{*}\bm{\theta}}<\infty\right)\overset{(a)}{\leq}\sum_{\bm{\theta}\neq\bm{\theta}^{*}}\dfrac{\delta}{J}\leq\delta$

where $(a)$ follows follows from Lemma 10 and the definition of
$\beta(J,\delta)$.

Step 6 (Sample complexity analysis): In this step we bound the total sample
complexity of T2 satisfying the $\delta$-PAC criteria. Recall that the set
$\mathcal{I}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\\{i\in[n]:i=\mathop{\rm
arg\,max}_{i^{\prime}\in[n]}(\mu_{i^{\prime}}(\bm{\theta})-\mu_{i^{\prime}}(\bm{\theta}^{\prime}))^{2}\text{
for some }\bm{\theta},\bm{\theta}^{\prime}\in\mathbf{\Theta}\\}$. Note that T2
does not sample by the Chernoff p.m.f. $\mathbf{p}_{\bm{\theta}}$. Rather it
samples by the p.m.f.

$\displaystyle
u_{\bm{\theta}\bm{\theta}^{\prime}}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\dfrac{1}{|\mathcal{I}(\bm{\theta}\bm{\theta}^{\prime})|}$
(38)

where,
$\mathcal{I}(\bm{\theta}\bm{\theta}^{\prime})\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\\{i\in\mathcal{I}:i=\mathop{\rm
arg\,max}_{i^{\prime}\in[n]}(\mu_{i^{\prime}}(\bm{\theta})-\mu_{i^{\prime}}(\bm{\theta}^{\prime}))^{2}\text{
for }\bm{\theta},\bm{\theta}^{\prime}\in\mathbf{\Theta}\\}$. Hence
$u_{\bm{\theta}\bm{\theta}^{\prime}}$ is a uniform random p.m.f between all
the maximum mean squared difference actions between hypotheses $\bm{\theta}$
and $\bm{\theta}^{\prime}$ which are $\widehat{\bm{\theta}}(t)$ and
$\tilde{\bm{\theta}}(t)$ respectively for some rounds $s\in[\tau_{\delta}]$.
The rest of the analysis follows the same steps as in Step 6 of Theorem 2 as
the proof does not rely on any specific type of sampling proportion. We define
the stopping time $\tau_{\delta}$ as follows:

$\displaystyle\tau_{\delta}=\min\left\\{t:L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\widehat{\bm{\theta}}(t))\geq\beta(J,\delta),\forall\bm{\theta}^{\prime}\neq\widehat{\bm{\theta}}(t)\right\\}.$

We further define the stopping time $\tau_{\bm{\theta}^{*}}$ for the
hypothesis $\bm{\theta}^{*}$ as follows:

$\displaystyle\tau_{\bm{\theta}^{*}}:=\min\left\\{t:L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\bm{\theta}^{*})\geq\beta,\forall\bm{\theta}^{\prime}\neq\bm{\theta}^{*}\right\\}$
(39)

We also define the critical number of samples as $(1+c)M$ where $M$ is defined
as follows:

$\displaystyle
M\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left(\dfrac{\alpha(J)}{D^{\prime}_{1}}+\dfrac{C^{\prime}(\eta_{0},\eta)+\log(J/\delta)}{D^{\prime}_{0}}\right)$
(40)

where,
$C^{\prime}(\eta_{0},\eta)=\log(1+\nicefrac{{\eta^{2}}}{{\eta_{0}^{2}}})$,
$c>0$ is a constant, and we define the term $D_{1}^{\prime}$ as follows:

$\displaystyle D_{1}^{\prime}$
$\displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min_{\bm{\theta}\neq\bm{\theta}^{\prime},\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\sum_{i=1}^{n}u_{\bm{\theta}\bm{\theta}^{\prime}}(i)(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{*}))^{2}$

and the term $D_{0}^{\prime}$ as follows:

$\displaystyle
D_{0}^{\prime}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min\limits_{\bm{\theta},\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\sum_{i=1}^{n}u_{\bm{\theta}^{*}\bm{\theta}}(i)(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{*}))^{2}.$

It then follows that

$\displaystyle\mathbb{E}[\tau_{\delta}]$
$\displaystyle\leq\mathbb{E}[\tau_{\bm{\theta}^{*}}]=\sum_{t=0}^{\infty}\mathbb{P}(\tau_{\bm{\theta}^{*}}>t)\overset{(a)}{\leq}1+(1+c)M+\sum_{t:t>(1+c)M}\mathbb{P}(\tau_{\bm{\theta}^{*}}>t)$
$\displaystyle\overset{(b)}{\leq}1+(1+c)\left(\dfrac{\ell\log
J}{D_{1}^{\prime}}+\dfrac{C^{\prime}(\eta_{0},\eta)+\log(J/\delta)}{D_{0}^{\prime}}\right)+\sum_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\sum_{t:t>\left(\dfrac{\alpha(J)}{D_{1}^{\prime}}+\dfrac{4\log(J/\delta)}{D_{0}^{\prime}}\right)(1+c)}C_{1}\exp(-C_{2}t)$
$\displaystyle\leq 1+(1+c)\left(\dfrac{\ell\log
J}{D_{1}^{\prime}}+\dfrac{C^{\prime}(\eta_{0},\eta)+\log(J/\delta)}{D_{0}^{\prime}}\right)+\sum_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}C_{1}\dfrac{\exp\left(-C_{2}\left(\dfrac{\alpha(J)}{D_{1}^{\prime}}+\dfrac{4\log(J/\delta)}{D_{0}^{\prime}}\right)\right)}{1-\exp\left(-C_{2}\right)}$
$\displaystyle\overset{(c)}{\leq}1+\underbrace{2\left(\dfrac{\ell\log
J}{D^{\prime}_{1}}+\dfrac{C^{\prime}(\eta_{0},\eta)+\log(J/\delta)}{D^{\prime}_{0}}\right)}_{\textbf{Term
A}}+\underbrace{\left(44+\dfrac{2\eta^{2}}{\eta_{0}^{2}}\right)^{2}J^{1-\dfrac{\eta_{0}^{2}(\ell+4)}{2\eta^{3}}}}_{\textbf{Term
B}}\underbrace{\delta^{\dfrac{D^{\prime}_{0}}{\eta^{2}}}}_{\textbf{Term C}}$
(41)

where, $(a)$ follows from definition of $M$ in (40), $(b)$ follows from Lemma
11 where
$C_{1}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}23+11\max\left\\{1,\dfrac{\eta^{2}}{2D_{1}^{2}}\right\\}$,
$C_{2}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\dfrac{2D_{1}^{2}\min\\{(\frac{c}{2}-1)^{2},c\\}}{\eta^{2}}$,
and $(c)$ follows the same steps in Theorem 2 by setting $c=\frac{1}{2}$ in
$C_{1}$ and $C_{2}$.

Again, note that in (41) the term C $\leq 1$ as $\delta\in(0,1)$. So for a
constant $\ell>1$ such that if $\ell$ satisfies the following condition

$\displaystyle\ell=\eta\log\left(44+\dfrac{\eta^{2}}{\eta_{0}^{2}}\right)>\log\left(1+\dfrac{\eta^{2}}{\eta_{0}^{2}}\right)$
(42)

we have that Term B $\leq
J^{1-\dfrac{\eta_{0}^{2}(\ell+4)}{2\eta^{3}}+\dfrac{\ell}{\eta\log J}}$.
Hence, Plugging this in (41) we get that the expected sample complexity is of
the order of

$\displaystyle\mathbb{E}[\tau_{\delta}]\leq
O\left(\dfrac{\eta\log(C(\eta_{0},\eta))\log
J}{D_{1}^{\prime}}+\dfrac{\log(J/\delta)}{D_{0}^{\prime}}+JC(\eta_{0},\eta)^{1/\eta}\delta^{D_{0}^{\prime}/\eta^{2}}\right).$

where, $C(\eta_{0},\eta)=44+\dfrac{\eta^{2}}{\eta_{0}^{2}}$. The claim of the
theorem follows. ∎

###  A.5 Proof of Proposition 1 (Batched Setting)

######  Proposition 2.

(Restatement) Let $\tau_{\delta}$, $D_{0}$, and $D_{1}$ be defined as in 2.
Then the sample complexity bound of $\delta$-PAC Batch GC is given by

$\displaystyle\mathbb{E}[\tau_{\delta}]\leq O\left(B+\dfrac{\eta\log(C)\log
J}{D_{1}}+\dfrac{\log(J/\delta)}{D_{0}}+BJC^{\frac{1}{\eta}}\delta^{\frac{D_{0}}{\eta^{2}}}\right).$

###### Proof.

We follow the same proof technique as in Theorem 2. We define the last phase
after which the algorithm stops as $m_{\delta}$ defined as follows:

$\displaystyle
m_{\delta}=\min\\{m:L_{Y^{mB}}(\bm{\theta}^{\prime})-L_{Y^{mB}}(\widehat{\bm{\theta}}(t))>\beta(J,\delta),\forall\bm{\theta}^{\prime}\neq\widehat{\bm{\theta}}(t)\\}.$

We further define the phase $m_{\bm{\theta}^{*}}$ as follows:

$\displaystyle
m_{\bm{\theta}^{*}}=\min\\{m:L_{Y^{mB}}(\bm{\theta}^{\prime})-L_{Y^{mB}}(\widehat{\bm{\theta}}(t))>\beta(J,\delta),\forall\bm{\theta}^{\prime}\neq\bm{\theta}^{*}\\}.$

Then we can show that the expected stopping phase $m_{\delta}$ is bounded as
follows:

$\displaystyle\mathbb{E}[m_{\delta}]\leq\mathbb{E}[m_{\bm{\theta}^{*}}]=\sum_{m=1}^{\infty}\mathbb{P}(m_{\bm{\theta}^{*}}>m)\leq
1+\underbrace{(1+c)M_{1}}_{\textbf{Part
A}}+\sum_{m^{\prime}:m^{\prime}>(1+c)M_{1}}\underbrace{\mathbb{P}(m_{\bm{\theta}^{*}}>m^{\prime})}_{\textbf{Part
B}}$ (43)

where, in Part A we define the critical number of phases

$\displaystyle
M_{1}=\dfrac{\alpha(J)}{BD_{1}}+\dfrac{\beta(J,\delta)}{BD_{0}}.$

and $D_{0}$, $D_{1}$ as defined in Theorem 2. Note that this definition of
$M_{1}$ is different that the critical number of samples defined in Theorem 2.
Now we control the Part B. As like Lemma 5 we define the following bad events

$\displaystyle\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(m)$
$\displaystyle=\\{L_{Y^{mB}}(\bm{\theta}^{\prime})-L_{Y^{mB}}(\bm{\theta}^{*})<\beta(J,\delta)\\}$
$\displaystyle\tilde{\xi}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(m)$
$\displaystyle=\\{L_{Y^{mB}}(\bm{\theta}^{\prime})-L_{Y^{mB}}(\bm{\theta}^{*})<\alpha(J)\\}$

We further define the good stopping phase
$\tilde{m}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}$ as follows:

$\displaystyle\tilde{m}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}$
$\displaystyle=\min\\{m:L_{Y^{m^{\prime}B}}(\bm{\theta}^{\prime})-L_{Y^{m^{\prime}B}}(\bm{\theta}^{*})>\alpha(J),\forall
m^{\prime}>m\\}$ $\displaystyle\text{and }\tilde{m}_{\bm{\theta}^{*}}$
$\displaystyle=\max_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\\{\tilde{m}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}\\}$

denote the last phase after which in all subsequent phases we have
$\bm{\theta}^{*}$ is $\widehat{\bm{\theta}}(t)$. We further define
$\tilde{m}_{\bm{\theta}^{*}}$ as

$\displaystyle\tilde{m}_{\bm{\theta}^{*}}=\dfrac{\alpha(J)}{BD_{1}}+\dfrac{mc}{2}.$

Note that this definition of $\tilde{m}_{\bm{\theta}^{*}}$ is different that
$\tilde{\tau}_{\bm{\theta}^{*}}$ in Lemma 5. Using Lemma 6 we can further show
the event $\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}$ is bounded as follows:

$\displaystyle\mathbb{P}(\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(m))$
$\displaystyle=\mathbb{P}\left(\underbrace{L_{Y^{mB}}(\bm{\theta}^{\prime})-L_{Y^{mB}}(\bm{\theta}^{*})}_{\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}T_{Y^{mB}}(\bm{\theta}^{\prime},\bm{\theta}^{*})}<\beta(J,\delta)\right)$
$\displaystyle\leq\mathbb{P}\left(T_{Y^{mB}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-\mathbb{E}[T_{Y^{mB}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]<D_{0}\left(\dfrac{\beta(J,\delta)}{D_{0}}-B(m-\tilde{m}_{\bm{\theta}^{*}})\right)\right)$
$\displaystyle\overset{(a)}{\leq}\exp\left(4B\right)\sum_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\exp\left(-\dfrac{2D_{1}^{2}Bm\left(\frac{c}{2}-1\right)^{2}}{\eta^{2}}\right)$
(44)

where, $(a)$ follows usinf the same steps as in Lemma 6. Similarly we can show
that,

$\displaystyle\mathbb{P}\left(\tilde{\xi}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(m)\right)=\sum_{\bm{\theta}\neq\bm{\theta}^{\prime}}\sum_{m^{\prime}:m^{\prime}>\dfrac{\alpha(J)}{BD_{1}}+\dfrac{mc}{2}}\mathbb{P}\left(T_{Y^{m^{\prime}B}}-\mathbb{E}[T_{Y^{m^{\prime}B}}]<\alpha(J)-\mathbb{E}[T_{Y^{m^{\prime}B}}]\right)$
$\displaystyle\overset{(a)}{\leq}\sum_{\bm{\theta}\neq\bm{\theta}^{\prime}}\sum_{m^{\prime}:m^{\prime}>\dfrac{\alpha(J)}{BD_{1}}+\dfrac{mc}{2}}\mathbb{P}\left(T_{Y^{m^{\prime}B}}-\mathbb{E}[T_{Y^{m^{\prime}B}}]<\alpha(J)-m^{\prime}BD_{1}\right)\overset{(b)}{\leq}\exp\left(4\right)\sum_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\dfrac{\exp\left(-\dfrac{2D_{1}^{2}mcB}{2}\right)}{1-\exp\left(-\dfrac{2D_{1}^{2}cB}{2}\right)}$
(45)

where, $(a)$ follows as $\mathbb{E}[T_{Y^{m^{\prime}B}}]\geq m^{\prime}BD_{1}$
for all $m^{\prime}>\frac{\alpha(J)}{BD_{1}}+\frac{mc}{2}$, and $(b)$ follows
using the same steps as in Lemma 7.

Finally using eq. 44 and eq. 45 we can show that the Part B is bounded as
follows:

$\displaystyle\mathbb{P}(m_{\bm{\theta}^{*}}>m)$
$\displaystyle\leq\mathbb{P}\left(\left\\{\bigcup_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(m)\right\\}\bigcap\left\\{\tilde{m}_{\bm{\theta}^{*}}<\dfrac{\alpha}{BD_{1}}+\dfrac{mc}{2}\right\\}\right)+\sum_{\bm{\theta}\neq\bm{\theta}^{\prime}}\sum_{m^{\prime}:m^{\prime}>\dfrac{\alpha(J)}{BD_{1}}+\dfrac{mc}{2}}\mathbb{P}\left(\tilde{\xi}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(m^{\prime})\right)$
$\displaystyle\overset{(a)}{\leq}\sum_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\underbrace{\left[23+11\max\\{1,\frac{\eta^{2}}{2D_{1}^{2}B}\\}\right]}_{\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}C_{1}}\exp\left(-\underbrace{\dfrac{2D_{1}^{2}B\min\\{(\nicefrac{{c}}{{2}}-1)^{2},c\\}}{\eta^{2}}}_{\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}C_{2}}m\right)\leq
JC_{1}\exp\left(-C_{2}m\right)$

where, $(a)$ follows from the same steps as in Lemma 5, and using eq. 44 and
eq. 45. Plugging this back in eq. 43 we get that

$\displaystyle\mathbb{E}[m_{\delta}]$ $\displaystyle\leq
1+(1+c)\left(\dfrac{\alpha(J)}{BD_{1}}+\dfrac{\beta(J,\delta)}{BD_{0}}\right)+J\sum_{m:m>\dfrac{\alpha(J)}{BD_{1}}+\dfrac{\beta(J,\delta)}{BD_{0}}}C_{1}\exp\left(-C_{2}m\right)$
$\displaystyle\overset{(b)}{\leq}1+2\left(\dfrac{\eta\log\left(44+\nicefrac{{\eta^{2}}}{{B\eta_{0}^{2}}}\right)\log
J}{BD_{1}}+\dfrac{\log\left(1+\nicefrac{{\eta^{2}}}{{\eta_{0}^{2}B}}\right)+\log\left(\dfrac{J}{\delta}\right)}{BD_{0}}\right)+J^{1+\dfrac{\log\left(44+\nicefrac{{\eta^{2}}}{{B\eta_{0}^{2}}}\right)}{\log
J}}\delta^{D_{0}/\eta^{2}}$
$\displaystyle\overset{(b)}{=}O\left(1+\dfrac{\eta\log C\log
J}{BD_{1}}+\dfrac{\log(J/\delta)}{BD_{0}}+JC^{1/\delta}\delta^{D_{0}/\eta^{2}}\right)$

where, $(a)$ follows using the same steps as in Step 6 of 2, and in $(b)$ we
substitute
$C\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\log\left(44+\nicefrac{{\eta^{2}}}{{B\eta_{0}^{2}}}\right)$.
Finally, the expected total number of samples is given by

$\displaystyle\mathbb{E}[\tau_{\delta}]\leq
B\mathbb{E}[m_{\delta}]=O\left(B+\dfrac{\eta\log C\log
J}{D_{1}}+\dfrac{\log(J/\delta)}{D_{0}}+BJC^{1/\delta}\delta^{D_{0}/\eta^{2}}\right).$

The claim of the proposition follows. ∎

###  A.6 Minimax Optimality Proof (Theorem 4)

######  Example 2.

We define a bandit model $B_{j}$ consisting of $N$ actions and $J$ hypotheses
with true hypothesis $\bm{\theta}^{*}=\bm{\theta}_{j}$ ($j$-th column) as
follows:

$\displaystyle\begin{matrix}\bm{\theta}&=&\bm{\theta}_{1}&\bm{\theta}_{2}&\bm{\theta}_{3}&\ldots&\bm{\theta}_{J}\\\
\hline\cr\mu_{1}(\bm{\theta})&=&\Gamma&\Gamma\\!-\\!\frac{\Gamma}{J}&\Gamma\\!-\\!\frac{2\Gamma}{J}&\ldots&\Gamma\\!-\\!\frac{(J-1)\Gamma}{J}\\\
\mu_{2}(\bm{\theta})&=&\epsilon_{21}&\epsilon_{22}&\epsilon_{23}&\ldots&\epsilon_{2J}\\\
&\vdots&&&\vdots\\\
\mu_{n}(\bm{\theta})&=&\epsilon_{n1}&\epsilon_{n2}&\epsilon_{n3}&\ldots&\epsilon_{nJ}\end{matrix}$

where, each $\epsilon_{ij}$ is distinct and satisfies
$\epsilon_{ij}<\Gamma/4J$. Note that we introduce such $\epsilon_{ij}$ for
different hypotheses so as not to violate Assumption 2. $\bm{\theta}_{1}$ is
the optimal hypothesis in $B_{1}$, $\bm{\theta}_{2}$ is the optimal hypothesis
in $B_{2}$ and so on such that for each $B_{j}$ and $j\in[J]$ we have column
$j$ as the optimal hypothesis.

######  Theorem 4.

(Restatement) In the environment in (6), any $\delta$-PAC policy $\pi$ that
identifies $\bm{\theta}^{\ast}$ satisfies
$\mathbb{E}[\tau_{\delta}]\geq\Omega\left({J^{2}\Gamma^{-2}}\log({1}/{\delta})\right)$.
Applying Theorem 2 to the same environment, the sample complexity of GC is
$O\left(J^{2}\Gamma^{-2}\log(J/\delta)\right)$.

###### Proof.

The proof follows the standard change of measure argument. We follow the proof
technique in Theorem 1 of huang2017structured. We first state a problem setup
in Example 2.

Let, $\Lambda_{1}$ be the set of alternate bandit models having a different
optimal hypothesis than $\bm{\theta}^{*}=\bm{\theta}_{1}$ such that all bandit
models having different optimal hypothesis than $\bm{\theta}_{1}$ such as
$B_{2},B_{3},\ldots B_{J}$ are in $\Lambda_{1}$. Let $\tau_{\delta}$ be a
stopping time for any $\delta$-PAC policy $\pi$. Let $Z_{i}(t)$ denote the
number of times the action $i$ has been sampled till round $t$. Let
$\widehat{\bm{\theta}}(t)$ be the predicted optimal hypothesis at round
$\tau_{\delta}$. We first consider the bandit model $B_{1}$. Define the event
$\xi=\\{\widehat{\bm{\theta}}(t)\neq\bm{\theta}^{*}\\}$ as the error event in
bandit model $B_{1}$. Let the event
$\xi^{\prime}=\\{\widehat{\bm{\theta}}(t)\neq\bm{\theta}^{{}^{\prime}*}\\}$ be
the corresponding error event in bandit model $B_{2}$. Note that
$\xi^{C}\subset\xi^{\prime}$. Now since $\pi$ is $\delta$-PAC policy we have
$\mathbb{P}_{B_{1},\pi}(\xi)\leq\delta$ and
$\mathbb{P}_{B_{2},\pi}(\xi^{C})\leq\delta$. Hence we can show that,

$\displaystyle
2\delta\geq\mathbb{P}_{B_{1},\pi}(\xi)+\mathbb{P}_{B_{2},\pi}(\xi^{c})$
$\displaystyle\overset{(a)}{\geq}\frac{1}{2}\exp\left(-\mathrm{KL}\left(P_{B_{1},\pi}||P_{B_{2},\pi}\right)\right)$
$\displaystyle\mathrm{KL}\left(P_{B_{1},\pi}||P_{B_{2},\pi}\right)$
$\displaystyle\geq\log\left(\dfrac{1}{4\delta}\right)$
$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{B_{1},\pi}[Z_{i}(\tau_{\delta})]\cdot\left(\mu_{i}(\bm{\theta}^{*})-\mu_{i}(\bm{\theta}^{{}^{\prime}*})\right)^{2}$
$\displaystyle\overset{(b)}{\geq}\log\left(\dfrac{1}{4\delta}\right)$
$\displaystyle\left(\Gamma-\Gamma+\frac{\Gamma}{J}\right)^{2}\mathbb{E}_{B_{1},\pi}[Z_{1}(\tau_{\delta})]+\sum_{i=2}^{n}(\epsilon_{i1}-\epsilon_{i2})^{2}\mathbb{E}_{B_{1},\pi}[Z_{i}(\tau_{\delta})]$
$\displaystyle\overset{(c)}{\geq}\log\left(\dfrac{1}{4\delta}\right)$
$\displaystyle\left(\dfrac{1}{J}\right)^{2}\Gamma^{2}\mathbb{E}_{B_{1},\pi}[Z_{1}(\tau_{\delta})]+\sum_{i=2}^{n}(\epsilon_{i1}-\epsilon_{i2})^{2}\mathbb{E}_{B_{1},\pi}[Z_{i}(\tau_{\delta})]$
$\displaystyle\overset{}{\geq}\log\left(\dfrac{1}{4\delta}\right)$
$\displaystyle\left(\dfrac{1}{J}\right)^{2}\Gamma^{2}\mathbb{E}_{B_{1},\pi}[Z_{1}(\tau_{\delta})]+\sum_{i=2}^{n}\frac{\Gamma^{2}}{4J^{2}}\mathbb{E}_{B_{1},\pi}[Z_{i}(\tau_{\delta})]$
$\displaystyle\overset{(d)}{\geq}\log\left(\dfrac{1}{4\delta}\right)$ (46)

where, $(a)$ follows from Lemma 2, $(b)$ follows from Lemma 1, $(c)$ follows
from the construction of the bandit environments, and $(d)$ follows as
$(\epsilon_{ij}-\epsilon_{ij^{\prime}})^{2}\leq\frac{\Gamma^{2}}{4J^{2}}$ for
any $i$-th action and $j$-th hypothesis pair.

Now, we consider the alternate bandit model $B_{3}$. Again define the event
$\xi=\\{\widehat{\bm{\theta}}(t)\neq\bm{\theta}^{*}\\}$ as the error event in
bandit model $B_{1}$ and the event
$\xi^{\prime}=\\{\widehat{\bm{\theta}}(t)\neq\bm{\theta}^{{}^{\prime\prime}*}\\}$
be the corresponding error event in bandit model $B_{3}$. Note that
$\xi^{C}\subset\xi^{\prime}$. Now since $\pi$ is $\delta$-PAC policy we have
$\mathbb{P}_{B_{1},\pi}(\xi)\leq\delta$ and
$\mathbb{P}_{B_{3},\pi}(\xi^{C})\leq\delta$. Following the same way as before
we can show that,

$\displaystyle\left(\dfrac{2}{J}\right)^{2}\Gamma^{2}\mathbb{E}_{B_{1},\pi}[Z_{1}(\tau_{\delta})]+\sum_{i=2}^{n}\frac{\Gamma^{2}}{4J^{2}}\mathbb{E}_{B_{1},\pi}[Z_{i}(\tau_{\delta})]$
$\displaystyle\overset{(d)}{\geq}\log\left(\dfrac{1}{4\delta}\right).$ (47)

Similarly we get the equations for all the other $(J-2)$ alternate models in
$\Lambda_{1}$. Now consider an optimization problem

$\displaystyle\min_{x_{i}:i\in[n]}\sum x_{i}\quad
s.t.\quad\left(\frac{1}{J}\right)^{2}\Gamma^{2}x_{1}+\frac{\Gamma^{2}}{4J^{2}}\sum_{i=2}^{n}x_{i}\geq\log(1/4\delta)$
$\displaystyle\left(\frac{2}{J}\right)^{2}\Gamma^{2}x_{1}+\frac{\Gamma^{2}}{4J^{2}}\sum_{i=2}^{n}x_{i}\geq\log(1/4\delta)$
$\displaystyle\vdots$
$\displaystyle\left(\frac{J-1}{J}\right)^{2}\Gamma^{2}x_{1}+\frac{\Gamma^{2}}{4J^{2}}\sum_{i=2}^{n}x_{i}\geq\log(1/4\delta)$
$\displaystyle x_{i}\geq 0,\forall i\in[n]$

where the optimization variables are $x_{i}$. It can be seen that the optimum
objective value is $J^{2}\Gamma^{-2}\log(1/4\delta)$. Interpreting
$x_{i}=\mathbb{E}_{B_{1},\pi}[Z_{i}(\tau_{\delta})]$ for all $i$, we get that
$\mathbb{E}_{B_{1},\pi}[\tau_{\delta}]=\sum_{i}x_{i}$ which gives us the
required lower bound. Let $\mathbf{p}_{\bm{\theta}^{*}}$ be the sampling p.m.f
for the environment $B_{1}$ for verifying $\bm{\theta}^{*}$. We also know that
the Chernoff verification in (3) has a nice linear programming formulation as
stated in (4). Using that for $B_{1}$ we can show that,

$\displaystyle\max\ell\quad
s.t.\quad\mathbf{p}_{\bm{\theta}^{*}}(1)\Gamma^{2}\left(\frac{1}{J}\right)^{2}+\sum_{i=2}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)(\epsilon_{i\bm{\theta}^{*}}-\epsilon_{i\bm{\theta}^{\prime}})^{2}\geq\ell$
$\displaystyle\mathbf{p}_{\bm{\theta}^{*}}(1)\Gamma^{2}\left(\frac{2}{J}\right)^{2}+\sum_{i=2}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)(\epsilon_{i\bm{\theta}^{*}}-\epsilon_{i\bm{\theta}^{\prime\prime}})^{2}\geq\ell$
$\displaystyle\vdots$
$\displaystyle\mathbf{p}_{\bm{\theta}^{*}}(1)\Gamma^{2}\left(\frac{J-1}{J}\right)^{2}+\sum_{i=2}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)(\epsilon_{i\bm{\theta}^{*}}-\epsilon_{i\bm{\theta}^{\prime\prime\prime}})^{2}\geq\ell$
$\displaystyle\sum_{i=1}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)=1.$

We can relax this further by noting that
$(\epsilon_{i\bm{\theta}^{*}}-\epsilon_{i\bm{\theta}^{\prime}})^{2}\leq\frac{\Gamma^{2}}{4J^{2}}$
for all $i\in[n]$ and
$\bm{\theta}^{*},\bm{\theta}^{\prime}\in\mathbf{\Theta}$. Hence,

$\displaystyle\max\ell\quad
s.t.\quad\mathbf{p}_{\bm{\theta}^{*}}(1)\Gamma^{2}\left(\frac{1}{J}\right)^{2}+\sum_{i=2}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)\frac{\Gamma^{2}}{4J^{2}}\geq\ell$
$\displaystyle\mathbf{p}_{\bm{\theta}^{*}}(1)\Gamma^{2}\left(\frac{2}{J}\right)^{2}+\sum_{i=2}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)\frac{\Gamma^{2}}{4J^{2}}\geq\ell$
$\displaystyle\vdots$
$\displaystyle\mathbf{p}_{\bm{\theta}^{*}}(1)\Gamma^{2}\left(\frac{J-1}{J}\right)^{2}+\sum_{i=2}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)\frac{\Gamma^{2}}{4J^{2}}\geq\ell$
$\displaystyle\sum_{i=1}^{n}\mathbf{p}_{\bm{\theta}^{*}}(i)=1.$

Solving this above optimization gives that
$\mathbf{p}_{\bm{\theta}^{*}}(1)=1$, and
$\mathbf{p}_{\bm{\theta}^{*}}(2)=\mathbf{p}_{\bm{\theta}^{*}}(3)=\ldots=\mathbf{p}_{\bm{\theta}^{*}}(n)=0$.
Similarly, for verifying any hypothesis $\bm{\theta}\in\mathbf{\Theta}$ we can
show that the verification proportion is given by
$\mathbf{p}_{\bm{\theta}}=(1,\underbrace{0,0,\ldots,0}_{\text{(J-1) zeros}})$.
This also shows that for Example 2,

$\displaystyle D_{0}$
$\displaystyle=\min_{\bm{\theta}^{\prime}\neq\bm{\theta}^{\ast}}\sum_{i=1}^{n}p_{\bm{\theta}^{*}}(i)(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{\ast}))^{2}=p_{\bm{\theta}^{*}}(1)\Gamma^{2}\left(\frac{1}{J}\right)^{2}+\sum_{i=2}^{n}p_{\bm{\theta}^{*}}(i)(\epsilon_{i\bm{\theta}^{*}}-\epsilon_{i\bm{\theta}^{\prime}})^{2}=\dfrac{\Gamma^{2}}{J^{2}}$
$\displaystyle D_{1}$
$\displaystyle=\min_{\\{\mathbf{p}_{\bm{\theta}}:\bm{\theta}\in\mathbf{\Theta}\\}}\min_{\bm{\theta}^{\prime}\neq\bm{\theta}^{\ast}}\sum_{i=1}^{n}p_{\bm{\theta}}(i)(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{*}))^{2}\overset{(a)}{\geq}p_{\bm{\theta}}(1)\Gamma^{2}\left(\frac{1}{J}\right)^{2}+\sum_{i=2}^{n}p_{\bm{\theta}}(i)(\epsilon_{i\bm{\theta}}-\epsilon_{i\bm{\theta}^{\prime}})^{2}=\dfrac{\Gamma^{2}}{J^{2}}$

where, $(a)$ follows as the verification of any hypothesis $\bm{\theta}$ is a
one hot vector $p_{\bm{\theta}}=(1,\underbrace{0,0,\ldots,0}_{\text{(J-1)
zeros}})$. Note that $\eta/4=\Gamma^{2}$. Plugging this in Theorem 2 gives us
that the upper bound of GC as

$\displaystyle\mathbb{E}[\tau_{\delta}]$ $\displaystyle\leq
O\left(\dfrac{J^{2}\Gamma^{2}\log(\Gamma^{4}/\eta_{0}^{4})\Gamma\log
J}{\Gamma^{2}}+\dfrac{J^{2}\log(J/\delta)}{\Gamma^{2}}+J\log(\Gamma^{4}/\eta_{0}^{4})^{1/\Gamma^{2}}\delta^{\Gamma^{2}/(J^{2}\Gamma^{4})}\right)$
$\displaystyle\leq O\left(J^{2}\log(\Gamma^{4}/\eta_{0}^{4})\Gamma\log
J+\dfrac{J^{2}\log(J/\delta)}{\Gamma^{2}}\right)\leq
O\left(\dfrac{J^{2}\log(J/\delta)}{\Gamma^{2}}\right).$

The claim of the theorem follows. ∎

###  A.7 Proof of Theorem 5 (Continuous hypotheses)

######  Theorem 5.

(Restatement) Assume that $\mu_{i}(\bm{\theta})$ for all $i\in[n]$ is a
differentiable function, and the set
$\\{\nabla\mu_{i}(\widehat{\bm{\theta}}(t)):i\in[n]\\}$ of gradients evaluated
at $\widehat{\bm{\theta}}(t)$ span $\mathbb{R}^{d}$. Consider the p.m.f.
$\mathbf{p}_{\widehat{\bm{\theta}}(t)}$ from (7) for verifying
$\widehat{\bm{\theta}}(t)$ among all alternatives in
$\mathbf{\Theta}_{2}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\mathbf{\Theta}\setminus\\{\widehat{\bm{\theta}}(t)\\}$.
The desired p.m.f. is the solution to the following optimization:

$\displaystyle\mathbf{p}_{\widehat{\bm{\theta}}(t)}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\mathop{\rm
arg\,max}_{\text{ }\mathbf{p}}\text{min
eigenvalue}\left(\sum_{i=1}^{n}p_{i}\nabla\mu_{i}(\widehat{\bm{\theta}}(t))\nabla\mu_{i}(\widehat{\bm{\theta}}(t))^{T}\right).$

###### Proof.

Consider the $\max\min$ optimization in (7) for verifying
$\widehat{\bm{\theta}}(t)$ against all alternatives in
$\mathbf{\Theta}\setminus\\{\widehat{\bm{\theta}}(t)\\}$. Denoting
$f_{i}(\bm{\theta})\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}(\mu_{i}(\bm{\theta})-\mu_{i}(\widehat{\bm{\theta}}(t)))^{2}$
for any generic $\bm{\theta}$, we can rewrite the optimization using a
probability density function (p.d.f.) $\mathbf{q}$ over parameters in
$\mathbf{\Theta}$, as explained subsequently.

$\displaystyle\mathbf{p}_{\widehat{\bm{\theta}}(t)}$
$\displaystyle=\mathop{\rm arg\,max}_{\text{
}\mathbf{p}}\inf_{\bm{\theta}\neq\widehat{\bm{\theta}}(t)}\sum_{i=1}^{n}p(i)f_{i}(\bm{\theta})$
$\displaystyle=\mathop{\rm arg\,max}_{\text{
}\mathbf{p}}\inf_{\mathbf{q}:q(\widehat{\bm{\theta}}(t))=0}\int_{\mathbf{\Theta}}q(\bm{\theta})\sum_{i=1}^{n}p(i)f_{i}(\bm{\theta})d\bm{\theta}.$
(48)

The above equality is true because if in the LHS, the inner infimum was
attained at a $\bm{\theta}\in\mathbf{\Theta}$, then the same value can be
attained in the RHS by a degenerate p.m.f. $\mathbf{q}$ that puts all its mass
on that $\bm{\theta}$. Conversely, suppose the inner infimum in the RHS was
attained at a p.m.f. $\mathbf{q}^{\ast}$. Since the objective function is a
linear in $\mathbf{q}$, the objective value is the same for a degenerate pmf
that puts all its mass on one of the support points of $\mathbf{q}^{\ast}$,
and this value can also be attained by the LHS infimum.

For any given $\eta>0$ and all $i\in[n]$, define

$\displaystyle\epsilon_{\eta}(i)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\max\\{\epsilon>0:|f_{i}(\bm{\theta})|\leq\eta\text{
if }||\bm{\theta}-\widehat{\bm{\theta}}(t)||\leq\epsilon\\},\text{ and }$
$\displaystyle\epsilon_{\eta}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min_{i}\epsilon_{\eta}(i).$
(49)

Existence of $\epsilon_{\eta}(i)$ is ensured by the continuity of
$f_{i}(\bm{\theta})$ in $\bm{\theta}$ and the fact that
$f_{i}(\widehat{\bm{\theta}}(t))=0$, and thus $\epsilon_{\eta}>0$. Consider a
family $\mathcal{Q}_{\eta}$ of pdfs supported on the boundary of an
$\epsilon_{\eta}$-ball around $\widehat{\bm{\theta}}(t)$, i.e.,

$\displaystyle\mathcal{Q}_{\eta}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left\\{\mathbf{q}:\int_{\mathbf{\Theta}}q(\bm{\theta})d\bm{\theta}=1,q(\bm{\theta}^{\prime})=0\text{
if
}||\bm{\theta}^{\prime}-\widehat{\bm{\theta}}(t)||\neq\epsilon_{\eta}\right\\}.$

For any pmf $\mathbf{p}$, if the infimum in (48) is attained at
$\mathbf{q}^{\ast}_{\mathbf{p}}$, then the suboptimality gap by restricting
the infimum to be over the set $\mathcal{Q}_{\eta}$ is non-negative, and is
upper bounded by

$\displaystyle\inf_{\mathbf{q}\in\mathcal{Q}_{\eta}}\sum_{i=1}^{n}p_{i}\int_{\mathbf{\Theta}}q(\bm{\theta})f_{i}(\bm{\theta})d\bm{\theta}$
$\displaystyle\leq\sum_{i=1}^{n}p_{i}\int_{\bm{\theta}:||\bm{\theta}-\widehat{\bm{\theta}}(t)||=\epsilon_{\eta}}q(\bm{\theta})\eta
d\bm{\theta}\leq\eta.$

As $\eta\rightarrow 0$, the suboptimality gap also tends to zero. Hence for
any pmf $\mathbf{p}$,

$\displaystyle\lim_{\eta\rightarrow
0}\inf_{\mathbf{q}\in\mathcal{Q}_{\eta}}\int_{\mathbf{\Theta}}q(\bm{\theta})\sum_{i=1}^{n}p_{i}f_{i}(\bm{\theta})d\bm{\theta}=\inf_{\mathbf{q}:q(\widehat{\bm{\theta}}(t))=0}\int_{\mathbf{\Theta}}q(\bm{\theta})\sum_{i=1}^{n}p_{i}f_{i}(\bm{\theta})d\bm{\theta}.$

The objective function in (48) is linear in both $\mathbf{p}$ and
$\mathbf{q}$, so using Sion’s minimax theorem we can interchange the order of
$\inf$ and $\max$ to get the same value, i.e., the optimum value is equal to

$\displaystyle\inf_{\mathbf{q}:q(\widehat{\bm{\theta}}(t))=0}\max_{\mathbf{p}}\sum_{i=1}^{n}p(i)\int_{\mathbf{\Theta}}q(\bm{\theta})f_{i}(\bm{\theta})d\bm{\theta}$
$\displaystyle=\lim_{\eta\rightarrow
0}\inf_{\mathbf{q}\in\mathcal{Q}_{\eta}}\max_{\mathbf{p}}\sum_{i=1}^{n}p_{i}\int_{\mathbf{\Theta}}q(\bm{\theta})f_{i}(\bm{\theta})d\bm{\theta}$
$\displaystyle=\lim_{\eta\rightarrow
0}\max_{\mathbf{p}}\inf_{\mathbf{q}\in\mathcal{Q}_{\eta}}\int_{\mathbf{\Theta}}q(\bm{\theta})\sum_{i=1}^{n}p_{i}f_{i}(\bm{\theta})d\bm{\theta}.$

For any choice of $\eta>0$ in the convergent series to $0$, define
$\mathbf{p}_{\eta}^{\ast}$ to be the maximizer in the above display. Consider
the multivariable Taylor series of $f_{i}$ around $\widehat{\bm{\theta}}(t)$,
for $\bm{\theta}$ that satisfies
$||\bm{\theta}-\widehat{\bm{\theta}}(t)||<\epsilon_{\eta}$.

$\displaystyle f_{i}(\bm{\theta})$
$\displaystyle=f_{i}(\widehat{\bm{\theta}}(t))+(\bm{\theta}-\widehat{\bm{\theta}}(t))^{T}\nabla
f_{i}(\widehat{\bm{\theta}}(t))$
$\displaystyle\mspace{18.0mu}+0.5(\bm{\theta}-\widehat{\bm{\theta}}(t))^{T}\nabla^{2}f_{i}(\widehat{\bm{\theta}}(t))(\bm{\theta}-\widehat{\bm{\theta}}(t))+o(||\bm{\theta}-\widehat{\bm{\theta}}(t)||^{3}).$

For indices $j,k\in[d]$ we can evaluate

$\displaystyle\nabla f_{i}(\bm{\theta})$
$\displaystyle=\begin{bmatrix}\frac{\partial
f_{i}}{\partial\bm{\theta}_{j}}(\bm{\theta})\end{bmatrix}_{j}=\begin{bmatrix}2(\mu_{i}(\bm{\theta})-\mu_{i}(\widehat{\bm{\theta}}(t)))\frac{\partial\mu_{i}}{\partial\bm{\theta}_{j}}(\bm{\theta})\end{bmatrix}_{j},\text{
and}$ $\displaystyle\nabla^{2}f_{i}(\bm{\theta})$
$\displaystyle=\begin{bmatrix}\frac{\partial^{2}f_{i}}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}(\bm{\theta})\end{bmatrix}_{j,k}$
$\displaystyle=\begin{bmatrix}2(\mu_{i}(\bm{\theta})-\mu_{i}(\widehat{\bm{\theta}}(t)))\frac{\partial^{2}\mu_{i}}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}(\bm{\theta})+2\frac{\partial\mu_{i}}{\partial\bm{\theta}_{j}}(\bm{\theta})\frac{\partial\mu_{i}}{\partial\bm{\theta}_{k}}(\bm{\theta})\end{bmatrix}_{j,k}$

giving that $\nabla f_{i}(\widehat{\bm{\theta}}(t))=0$ and
$\nabla^{2}f_{i}(\widehat{\bm{\theta}}(t))=2\nabla\mu_{i}(\widehat{\bm{\theta}}(t))\nabla\mu_{i}(\widehat{\bm{\theta}}(t))^{T}$.
Thus for small $\epsilon_{\eta}$ we have the approximation that
$f_{i}(\bm{\theta})\approx((\bm{\theta}-\widehat{\bm{\theta}}(t))^{T}\nabla\mu_{i}(\widehat{\bm{\theta}}(t)))^{2}$.
By the assumption that the set of gradients at $\widehat{\bm{\theta}}(t)$ span
$\mathbb{R}^{d}$, choosing a small $\eta$ implies that $\epsilon_{\eta}$
defined in (A.7) is also small. When $\mathbf{q}\in\mathcal{Q}_{\eta}$ for
small $\eta$, the optimization of (48) becomes the following.

$\displaystyle\max_{\mathbf{p}}\inf_{\mathbf{q}\in\mathcal{Q}_{\eta}}\int_{\mathbf{\Theta}}q(\bm{\theta})\sum_{i=1}^{n}p_{i}f_{i}(\bm{\theta})d\bm{\theta}$
$\displaystyle=\max_{\mathbf{p}}\inf_{\mathbf{q}\in\mathcal{Q}_{\eta}}\int_{\bm{\theta}:||\bm{\theta}-\widehat{\bm{\theta}}(t)||=\epsilon_{\eta}}q(\bm{\theta})\sum_{i=1}^{n}p_{i}(\bm{\theta}-\widehat{\bm{\theta}}(t))^{T}\nabla\mu_{i}(\widehat{\bm{\theta}}(t))\nabla\mu_{i}(\widehat{\bm{\theta}}(t))^{T}(\bm{\theta}-\widehat{\bm{\theta}}(t))d\bm{\theta}$
$\displaystyle=\max_{\mathbf{p}}\inf_{\mathbf{q}\in\mathcal{Q}_{\eta}}\int_{\bm{\theta}:||\bm{\theta}-\widehat{\bm{\theta}}(t)||=\epsilon_{\eta}}\frac{(\bm{\theta}-\widehat{\bm{\theta}}(t))^{T}\sum_{i=1}^{n}p_{i}\nabla\mu_{i}(\widehat{\bm{\theta}}(t))\nabla\mu_{i}(\widehat{\bm{\theta}}(t))^{T}(\bm{\theta}-\widehat{\bm{\theta}}(t))}{(\bm{\theta}-\widehat{\bm{\theta}}(t))^{T}(\bm{\theta}-\widehat{\bm{\theta}}(t))}q(\bm{\theta})||\bm{\theta}-\widehat{\bm{\theta}}(t)||^{2}d\bm{\theta}$
$\displaystyle=\max_{\mathbf{p}}\text{min
eigenvalue}\left(\sum_{i=1}^{n}p_{i}\nabla\mu_{i}(\widehat{\bm{\theta}}(t))\nabla\mu_{i}(\widehat{\bm{\theta}}(t))^{T}\right)\epsilon_{\eta}^{2}.$

Since the above is true for all values of $\eta$, as $\eta\rightarrow 0$ the
maximizer $\mathbf{p}_{\eta}^{\ast}$ for the above optimization converges to
the desired p.m.f. $\mathbf{p}_{\widehat{\bm{\theta}}(t)}$, having the
definition as claimed. ∎

####  A.7.1 How to solve the optimization

The optimization in Theorem 5 can be solved using convex optimization
software. This is because the objective function, i.e., the minimum eigenvalue
function is a concave function of the matrix argument, and the domain of the
optimization $\\{\mathbf{p}:\sum_{i=1}^{n}p(i)=1,p(i)\geq 0\forall i\in[n]\\}$
is a convex set. Hence we can maximize the objective over the domain. Since
the set of gradients $\\{\nabla\mu_{i}(\widehat{\bm{\theta}}(t)):i\in[n]\\}$
span $\mathbb{R}^{d}$, the optimal objective value is positive. Since, the
verification proportions are the solution to a convex optimization problem, so
we can terminate it early to get an approximate solution. Computing to
specified accuracy takes $O(n^{3}+nd^{2}+d^{3})$ operations
[fan1995minimizing].

###  A.8 Sample Complexity Proof of GCE

######  Proposition 2.

(Restatement) Let $\tau_{\delta}$, $D_{0}$, and $De$ be defined as in (cite).
Then the sample complexity bound of $\delta$-PAC GCE is given by

$\displaystyle\mathbb{E}[\tau_{\delta}]\\!\leq\\!O\left(\dfrac{\eta\log(C(\eta_{0},\eta))\log
J}{D_{e}}+\dfrac{\log(J/\delta)}{D_{0}}+J(C(\eta_{0},\eta))^{1/\eta}\delta^{D_{0}/\eta^{2}}\right).$

where, $C(\eta_{0},\eta)=\log(44+\eta^{2}/\eta_{0}^{2})$ is a constant.

###### Proof.

Recall that

$D_{1}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min_{\\{\mathbf{p}_{\bm{\theta}}:\bm{\theta}\in\mathbf{\Theta}\\}}\min_{\bm{\theta}^{\prime}\neq\bm{\theta}^{\ast}}\sum_{i=1}^{n}p_{\bm{\theta}}(i)(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{*}))^{2}.$

Define
$D_{e}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min_{\bm{\theta}^{\prime}\neq\bm{\theta}^{\ast}}\sum_{i=1}^{n}\frac{1}{n}(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{*}))^{2}$
as the objective value of uniform sampling optimization. Finally define the
quantity at round $s$ as

$\displaystyle
D^{\epsilon_{s}}_{1}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}(1-\epsilon_{s})D_{1}+\epsilon_{s}D_{e}$
(50)

Let
$T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\bm{\theta}^{*})$.
Note that following Assumption 1 we can show that

$\displaystyle
T_{Y_{s}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-D_{1}^{\epsilon_{s}}\overset{(a)}{\leq}4\eta,\quad
T_{Y_{s}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-D_{0}\leq 4\eta$

where, $(a)$ follows as $D_{1}\leq\eta$ and $D_{e}\leq\eta$ which implies
$(1-\epsilon)D_{1}+\epsilon D_{e}\leq\eta$ as $\epsilon\in(0,1)$. Now define
the quantity

$\displaystyle\alpha(J)$
$\displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\dfrac{C(\eta_{0},\eta)\log
J}{D_{e}},$ $\displaystyle\beta(J,\delta)$
$\displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\dfrac{C(\eta_{0},\eta)\log(J/\delta)}{D_{0}}$

where, the constant
$C(\eta_{0},\eta)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\log\left(44+\nicefrac{{\eta^{2}}}{{\eta_{0}^{2}}}\right)$.
Now define the failure events

$\displaystyle\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t)$
$\displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\\{L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\bm{\theta}^{*})<\beta(J,\delta)\\},$
$\displaystyle\tilde{\xi}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t)$
$\displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\\{L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\bm{\theta}^{*})<2\alpha(J)\\}$

where, for a constant
$C(\eta_{0},\eta)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\log\left(44+\nicefrac{{\eta^{2}}}{{\eta_{0}^{2}}}\right)$
we define
$\alpha(J)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\dfrac{C(\eta_{0},\eta)\log
J}{D^{e}_{1}}$, and
$\beta(J,\delta)=\dfrac{C(\eta_{0},\eta)\log(J/\delta)}{D_{0}}$. Then we
define the stopping times as follows:

$\displaystyle\tau_{\bm{\theta}^{*}}$
$\displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min\\{t:L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\bm{\theta}^{*})>\beta(J,\delta),\forall\bm{\theta}^{\prime}\neq\bm{\theta}^{*}\\}$
$\displaystyle\tilde{\tau}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}$
$\displaystyle\overset{}{\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}}\min\\{t:L_{Y^{t^{\prime}}}(\bm{\theta}^{\prime})-L_{Y^{t^{\prime}}}(\bm{\theta}^{*})>2\alpha(J),\forall
t^{\prime}>t\\}$ $\displaystyle\tilde{\tau}_{\bm{\theta}^{*}}$
$\displaystyle\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\max_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\\{\tilde{\tau}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}\\}.$

Then we have that Assumption 2 is no longer required which can be shown as
follows

$\displaystyle\mathbb{E}_{I^{t},Y^{t}}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]=\mathbb{E}_{I^{t},Y^{t}}[L_{Y^{t}}(\bm{\theta}^{\prime})-L_{Y^{t}}(\bm{\theta}^{*})]$
$\displaystyle=\mathbb{E}_{I^{t},Y^{t}}\left[\sum_{s=1}^{t}(Y_{s}-\mu_{I_{s}}(\bm{\theta}^{*}))^{2}-\sum_{s=1}^{t}(Y_{s}-\mu_{I_{s}}(\bm{\theta}))^{2}\right]$
$\displaystyle=\sum_{s=1}^{t}\mathbb{E}_{I_{s}}\mathbb{E}_{Y_{s}|I_{s}}\left[\left(\mu_{I_{s}}(\bm{\theta}^{*})-\mu_{I_{s}}(\bm{\theta})\right)^{2}|I_{s}\right]$
$\displaystyle=\sum_{s=1}^{t}\sum_{i=1}^{n}\mathbb{P}(I_{s}=i)\left(\mu_{i}(\bm{\theta}^{*})-\mu_{i}(\bm{\theta})\right)^{2}$

In the case when $D_{1}\geq 0$, we can show that

$\displaystyle\mathbb{E}_{I^{t},Y^{t}}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]$
$\displaystyle\overset{(a)}{\geq}\sum_{s=1}^{t}\left((1-\epsilon_{s})D_{1}+\epsilon_{s}D_{e}\right)$
$\displaystyle=\sum_{s=1}^{\tilde{\tau}_{\bm{\theta}^{*}}}(1-\epsilon_{s})D_{1}+\sum_{s=1}^{\tilde{\tau}_{\bm{\theta}^{*}}}\epsilon_{s}D_{e}+\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}+1}^{t}(1-\epsilon_{s})D_{0}+\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}+1}^{t}\epsilon_{s}D_{e}$
$\displaystyle\overset{(b)}{\geq}\sum_{s=1}^{\tilde{\tau}_{\bm{\theta}^{*}}}\epsilon_{s}D_{e}+\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}+1}^{t}D_{e}-\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}+1}^{t}\epsilon_{s}D_{0}+\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}+1}^{t}\epsilon_{s}D_{e}$
$\displaystyle\overset{(c)}{\geq}2\sqrt{\tilde{\tau}_{\bm{\theta}^{*}}}D_{e}-2D_{e}+(t-\tilde{\tau}_{\bm{\theta}^{*}}-1)D_{e}-kD_{0}$
$\displaystyle\overset{}{=}(t-1)D_{e}+2\sqrt{\tilde{\tau}_{\bm{\theta}^{*}}}D_{e}-\tilde{\tau}_{\bm{\theta}^{*}}D_{e}-(kD_{0}+2D_{e})$
$\displaystyle\overset{(d)}{\geq}(t-1)D_{e}-\left(\dfrac{\alpha(J)}{D_{e}}+\dfrac{tc}{2}\right)D_{e}$
$\displaystyle=(t-1)D_{e}-\alpha(J)-\frac{tc}{2}D_{e}$
$\displaystyle=\left(t-1-\frac{tc}{2}\right)D_{e}-\alpha(J)=tD_{e}\left(1-\frac{1}{t}-\frac{c}{2}\right)-\alpha(J)$
$\displaystyle\overset{(e)}{\geq}tD_{e}\underbrace{\left(\frac{1}{2}-\frac{c}{2}\right)}_{c_{1}}-\alpha(J)$
$\displaystyle=c_{1}tD_{e}-\alpha(J)$

where, $(a)$ follows due to the forced exploration definition, $(b)$ follows
by dropping $D_{1}$, $(c)$ follows $\epsilon_{s}>\frac{1}{\sqrt{s}}$ and
$\int_{1}^{t}\frac{1}{\sqrt{s}}ds=2\sqrt{s}-2$ and $D_{0}\geq D_{e}$, and
$(d)$ follows by definition of
$\tilde{\tau}_{\bm{\theta}^{*}}=\frac{\alpha(J)}{D_{e}}+\frac{tc}{2}$ and
trivially assuming that
$2\sqrt{\tilde{\tau}_{\bm{\theta}^{*}}}D_{e}-(kD_{0}+2D_{e})>0$ for large
enough $\tilde{\tau}_{\bm{\theta}^{*}}$, and $(e)$ follows as $t\geq 2$. Next
we can show that for $t\geq\tilde{\tau}_{\bm{\theta}^{*}}$

$\displaystyle\mathbb{E}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]\overset{(a)}{=}\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}}^{t}(1-\epsilon_{s})D_{0}+\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}}^{t}\epsilon_{s}D_{e}$
$\displaystyle\overset{(b)}{\geq}\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}}^{t}(1-\epsilon_{s})D_{0}+\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}}^{t}\epsilon_{s}\frac{D_{0}}{n}$
$\displaystyle=(t-\tilde{\tau}_{\bm{\theta}^{*}})D_{0}-\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}}^{t}\epsilon_{s}D_{0}+\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}}^{t}\epsilon_{s}\frac{D_{0}}{n}$
$\displaystyle=(t-\tilde{\tau}_{\bm{\theta}^{*}})D_{0}-D_{0}\frac{n-1}{n}\sum_{s=\tilde{\tau}_{\bm{\theta}^{*}}}^{t}\epsilon_{s}$
$\displaystyle\geq(t-\tilde{\tau}_{\bm{\theta}^{*}})D_{0}-kD_{0}$
$\displaystyle=(t-\tilde{\tau}_{\bm{\theta}^{*}}-k)D_{0}$

where, $(a)$ follows from the definition of exploration, and $(b)$ follows
from as $D_{0}\leq nD_{e}$, It follows that

$\displaystyle\mathbb{P}({\xi}_{\bm{\theta}^{\prime},\bm{\theta}^{*}}(t))$
$\displaystyle=\mathbb{P}(T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})<\beta(J,\delta))$
$\displaystyle\overset{}{=}\mathbb{P}(T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-\mathbb{E}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]<\beta(J,\delta)-\mathbb{E}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})])$
$\displaystyle\overset{(a)}{\leq}\mathbb{P}\left(T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-\mathbb{E}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]<\beta(J,\delta)-(t-\tilde{\tau}_{\bm{\theta}^{*}}-k)D_{0}\right)$
$\displaystyle\overset{(b)}{=}\mathbb{P}\left(T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-\mathbb{E}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]<D_{0}\left(\dfrac{\beta(J,\delta)}{D_{0}}-t+\tilde{\tau}_{\bm{\theta}^{*}}+k)\right)\right)$

Once we define the failure events and stopping times we can follow the same
proof technique as Theorem 2 and show that

$\displaystyle\mathbb{P}(\tilde{\xi}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t))$
$\displaystyle\overset{(a)}{\leq}\mathbb{P}(T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-\mathbb{E}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]<2\alpha(J)-c_{1}tD_{e})$

where, in $(a)$ the choice of $c_{1}tD_{1}$ follows as
$\mathbb{E}[T_{Y^{t}}(\bm{\theta}^{\prime},\bm{\theta}^{*})]\geq c_{1}tD_{e}$
as $D_{e}>0$ and noting that
$|T_{Y_{s}}(\bm{\theta}^{\prime},\bm{\theta}^{*})-D_{e}|\leq 4\eta$ by (19)
for any round $s\in[t]$. It follows from Lemma 5 since $D_{0}\geq D_{e}$ and
$D_{e}>0$ that the probability of the failure event is bounded as follows:

$\displaystyle\mathbb{P}(\tau_{\bm{\theta}^{*}}>t)\leq\mathbb{P}(\bigcup_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t))$
$\displaystyle=\mathbb{P}\left(\left\\{\bigcup_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t)\right\\}\bigcap\\{\tilde{\tau}_{\bm{\theta}^{*}}<\dfrac{\alpha(J)}{D_{e}}+\frac{tc}{2}\\}\right)+\mathbb{P}\left(\bigcup_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\left\\{\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t)\right\\}\bigcap\\{\tilde{\tau}_{\bm{\theta}^{*}}\geq\dfrac{\alpha(J)}{D_{e}}+\frac{tc}{2}\\}\right)$
$\displaystyle\leq\sum_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\mathbb{P}\left(\left\\{\xi_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t)\right\\}\bigcap\\{\tilde{\tau}_{\bm{\theta}^{*}}<\dfrac{\alpha(J)}{D_{e}}+\frac{tc}{2}\\}\right)+\sum_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\sum_{t^{\prime}:t^{\prime}\geq\frac{\alpha(J)}{D_{e}}+\frac{tc}{2}}\mathbb{P}\left(\tilde{\xi}_{\bm{\theta}^{\prime}\bm{\theta}^{*}}(t^{\prime})\right)\overset{(a)}{\leq}JC_{1}\exp\left(-C_{2}t\right)$

where, in $(a)$ we substitute
$C_{1}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}23+11\max\left\\{1,\dfrac{\eta^{2}}{2(D_{e})^{2}}\right\\}$,
$C_{2}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\dfrac{2(D_{e})^{2}\min\\{(\nicefrac{{c}}{{2}}-1)^{2},c\\}}{\eta^{2}}$,
$c>0$ is a constant, and
$J\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}|\mathbf{\Theta}|$.
Now we define the critical number of samples as follows:

$\displaystyle
M\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left(\dfrac{C(\eta_{0},\eta)\log
J}{D_{e}}+\dfrac{C(\eta_{0},\eta)+\log(J/\delta)}{D_{0}}\right)$

where,
$C(\eta_{0},\eta)=\log\left(44+\nicefrac{{\eta^{2}}}{{\eta_{0}^{2}}}\right)$.
Then we can bound the sample complexity for some constant $c>0$ as follows:

$\displaystyle\mathbb{E}[\tau_{\delta}]$
$\displaystyle\leq\mathbb{E}[\tau_{\bm{\theta}^{*}}]=\sum_{t=0}^{\infty}\mathbb{P}(\tau_{\bm{\theta}^{*}}>t)\overset{(a)}{\leq}1+(1+c)M+\sum_{t:t>(1+c)M}\mathbb{P}(\tau_{\bm{\theta}^{*}}>t)$
$\displaystyle\overset{(a)}{\leq}O\left(\dfrac{\eta\log(C(\eta_{0},\eta))\log
J}{D_{e}}+\dfrac{\log(J/\delta)}{D_{0}}+J(C(\eta_{0},\eta))^{1/\eta}\delta^{D_{0}/\eta^{2}}\right)$

where, $(a)$ follows as $C(\eta_{0},\eta)/D_{0}<C(\eta_{0},\eta)/D_{e}$. ∎

###  A.9 GC Convergence Proof for Smooth Hypotheses Space

####  A.9.1 Theoretical Comparisons for Active Regression

From the result of chaudhuri2015convergence we can show that the ActiveS
algorithm enjoys a convergence guarantee as follows:

$\displaystyle\mathbb{E}\left[L_{U}\left(\widehat{\bm{\theta}}(t)\right)-L_{U}\left(\theta^{*}\right)\right]\leq
O\left(\frac{\sigma^{2}_{U}\sqrt{\log(dt)}}{t}+\frac{R}{t^{2}}\right)$ (51)

where, $L_{U}$ is the loss under uniform measure, $R$ is the maximum loss
under any measure for any $\bm{\theta}\in\mathbf{\Theta}$, and
$\sigma^{2}_{U}$ is defined as

$\displaystyle\sigma^{2}_{U}$
$\displaystyle\overset{(a)}{=}\frac{1}{t^{2}}\operatorname{Trace}\left[\left(\sum_{s=1}^{t}\sum_{s^{\prime}=1}^{t}\mathbb{E}_{L_{Y_{s}}\sim
D}\left[\nabla
L_{Y_{s}}\left(\bm{\theta}^{*}\right)\right]\mathbb{E}_{L_{Y_{s^{\prime}}}\sim
D}\left[\nabla
L_{Y_{s^{\prime}}}\left(\bm{\theta}^{*}\right)^{\top}\right]\right)\
I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}\
I_{U}\left(\bm{\theta}^{*}\right)\
I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}\right]$
$\displaystyle=\frac{1}{t^{2}}\operatorname{Trace}\left[\left(\sum_{s=1}^{t}\sum_{s^{\prime}=1}^{t}\mathbb{E}_{L_{Y_{s}}\sim
D}\left[\nabla
L_{Y_{s}}\left(\bm{\theta}^{*}\right)\right]\mathbb{E}_{L_{Y_{s^{\prime}}}\sim
D}\left[\nabla
L_{Y_{s^{\prime}}}\left(\bm{\theta}^{*}\right)^{\top}\right]\right)\
I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}I_{U}\left(\bm{\theta}^{*}\right)\
I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}\right]$
$\displaystyle\overset{(b)}{=}\frac{1}{t^{2}}\operatorname{Trace}\left[\left(\sum_{s=1}^{t}\sum_{s^{\prime}=1}^{t}I_{\Gamma}\left(\bm{\theta}^{*}\right)\right)I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}I_{U}\left(\bm{\theta}^{*}\right)I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}\right]$
$\displaystyle=\operatorname{Trace}\left[I_{U}\left(\bm{\theta}^{*}\right)I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}\right]$
(52)

where, in $(a)$ the loss $L_{Y_{s}}$ and $L_{Y_{s^{\prime}}}$ are i.i.d drawn
from the same distribution $D$, and $I_{\Gamma}$, $I_{U}$ are the Fisher
information matrix under the sampling distribution $\Gamma$ and $U$, and $(b)$
follows from Lemma 5 of chaudhuri2015convergence. Note that ActiveS is a two-
stage process that samples according to the uniform distribution $U$ to build
an estimate of $\bm{\theta}^{*}$ and then solves an SDP to build the sampling
proportion $\Gamma$ that minimizes the quantity $\sigma_{U}^{2}$ and follows
that sampling proportion $\Gamma$ for the second stage. It follows that

$\displaystyle\sigma^{2}_{U}$
$\displaystyle=\operatorname{Trace}\left[I_{U}\left(\bm{\theta}^{*}\right)I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}\right]$
$\displaystyle\overset{(a)}{\leq}\operatorname{Trace}\left[I_{U}\left(\bm{\theta}^{*}\right)\right]\operatorname{Trace}\left[I_{\Gamma}\left(\bm{\theta}^{*}\right)^{-1}\right]$
$\displaystyle\leq\lambda_{1}dC_{4}\eta$

where, $(a)$ follows as for any positive semi-definite matrices
$\operatorname{Trace}[AB]\leq\operatorname{Trace}[A]\operatorname{Trace}[B]$,
and for $(b)$ we can show that

$\displaystyle I_{U}(\bm{\theta}^{*})$ $\displaystyle=\mathbb{E}_{I_{s}\sim
U}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}L_{Y_{s}}(\bm{\theta})=\mathbb{E}_{I_{s}\sim
U}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}(Y_{s}-\mu_{I_{s}}(\bm{\theta}))^{2}$
$\displaystyle=\mathbb{E}_{I_{s}\sim
U}2\left(Y_{s}-\mu_{i}(\bm{\theta}^{*})\right)\nabla^{2}\mu_{I_{s}}(\bm{\theta}^{*})-2\nabla\mu_{I_{s}}(\bm{\theta}^{*})\nabla\mu_{I_{s}}(\bm{\theta}^{*})^{T}$
$\displaystyle=2\sum_{i=1}^{n}p_{U}(i)\left[\left(Y_{s}-\mu_{i}(\bm{\theta}^{*})\right)\nabla^{2}\mu_{I_{s}}(\bm{\theta}^{*})-\nabla\mu_{I_{s}}(\bm{\theta}^{*})\nabla\mu_{I_{s}}(\bm{\theta}^{*})^{T}\right]$

This leads to the following bound on the trace of the matrix
$I_{U}(\bm{\theta}^{*})$

$\displaystyle\operatorname{Trace}[I_{U}(\bm{\theta}^{*})]\leq\operatorname{Trace}[\sum_{i=1}^{n}p_{U}(i)\left(Y_{s}-\mu_{i}(\bm{\theta}^{*})\right)\nabla^{2}\mu_{I_{s}}(\bm{\theta}^{*})]$
$\displaystyle\leq\lambda_{1}dC_{4}\sqrt{\eta}$

where
$\left(Y_{s}-\mu_{i}(\bm{\theta}^{*})\right)\nabla^{2}\mu_{I_{s}}(\bm{\theta}^{*})\leq\lambda_{1}dC_{4}\sqrt{\eta}$
and similarly,

$I_{\Gamma}(\bm{\theta}^{*})=\mathbb{E}_{I_{s}\sim\Gamma}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}L_{Y_{s}}(\bm{\theta})=\mathbb{E}_{I_{s}\sim\Gamma}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}(Y_{s}-\mu_{I_{s}}(\bm{\theta}))^{2}.$

which leads to an upper bound for
$\operatorname{Trace}[I_{\Gamma}(\bm{\theta}^{*})^{-1}]\leq\lambda_{1}dC_{4}\sqrt{\eta}$.
Plugging this in the statement of the result in eq. 51 we get that

$\displaystyle\mathbb{E}\left[L_{U}\left(\widehat{\bm{\theta}}(t)\right)-L_{U}\left(\theta^{*}\right)\right]\leq
O\left(\frac{d\sqrt{\log(dt)}}{t}+\frac{R}{t^{2}}\right).$

Comparing this to our result in 6 we have the following convergence rate

$\displaystyle\mathbb{E}\left[P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right]\leq\left(1+\epsilon_{t}\right)\frac{\sigma^{2}}{t}+\frac{R}{t^{2}}$
(53)

where $P_{t}$ is a worst case measure over the data points. Next, we can show
that,

$\displaystyle\sigma^{2}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}$
$\displaystyle=\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)^{T}\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)^{-1}\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)$
$\displaystyle\overset{(a)}{\leq}\lambda_{\max}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)^{-1}\right)\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\|^{2}$
$\displaystyle\overset{(b)}{\leq}\lambda_{\max}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)^{-1}\right)dC_{4}\eta$
$\displaystyle=\lambda_{\min}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)dC_{4}\eta$
$\displaystyle=\lambda_{\min}\left(\frac{2}{t}\sum_{s=1}^{t}\sum_{i=1}^{n}p_{\widehat{\bm{\theta}}_{s}}(i)\nabla\mu_{I_{s}}(\bm{\theta}^{*})\nabla\mu_{I_{s}}(\bm{\theta}^{*})^{T}\right)dC_{4}\eta$
$\displaystyle\overset{(c)}{\leq}\left(\frac{2}{t}\sum_{s=1}^{t}\lambda_{\min}\left(\sum_{i=1}^{n}p_{\widehat{\bm{\theta}}_{s}}(i)\nabla\mu_{I_{s}}(\bm{\theta}^{*})\nabla\mu_{I_{s}}(\bm{\theta}^{*})^{T}\right)\right)dC_{4}\eta$
$\displaystyle\leq 2\lambda_{1}dC_{4}\eta$

where, $(a)$ follows from the min-max theorem (variational characterization of
the maximum eigenvalue), in $(b)$ the quantity
$\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\|^{2}\leq d^{2}C_{4}\eta$
by assumption and $C_{4}$ is a constant, and $(c)$ follows from triangle
inequality. Plugging this in our result in eq. 53 we get

$\displaystyle\mathbb{E}\left[P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right]\leq
O\left(\frac{d\sqrt{\log(dt)}}{t}+\frac{R}{t^{2}}\right).$

The updated convergence result is summarized below in this table:

Sample Complexity Bound |  Comments
---|---
$\mathbb{E}\left[L_{U}\left(\widehat{\bm{\theta}}(t)\right)-L_{U}\left(\theta^{*}\right)\right]\leq O\left(d\frac{\sqrt{\log(dt)}}{t}+\frac{R}{t^{2}}\right)$ |  [chaudhuri2015convergence] $L_{U}$ is loss under uniform measure over data points in pool.
$\mathbb{E}\left[P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right]\leq O\left(d\frac{\sqrt{\log(dt)}}{t}+\frac{R}{t^{2}}\right)$ |  GC (Ours) $P_{t}$ is loss under a worst-case measure over data points.
Table 3: Active Regression comparison.

The two upper bounds have the same scaling, even though $P_{t}$ is a different
loss measure than $L_{U}$. The proof has steps similar to that of
[chaudhuri2015convergence], with some additional arguments to handle the fact
that our loss measure varies with time.

####  A.9.2 Discussion on Definitions and Assumptions

######  Definition 2.

We define the following star-norm quantity at round $t$ as

$\displaystyle\|A\|_{*}=\left\|\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1/2}\cdot
A\cdot\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1/2}\right\|.$

Now we state the two following assumptions required by the 6. Also note that
we define the squared loss function
$L_{Y_{s}}(\bm{\theta})=(\mu_{I_{s}}(\bm{\theta})-Y_{s})^{2}$, the cumulative
loss function
$L_{Y^{s}}(\bm{\theta})=\sum_{s^{\prime}=1}^{s}L_{Y_{s^{\prime}}}(\bm{\theta}^{*})=\sum_{s^{\prime}=1}^{s}(\mu_{I_{s^{\prime}}}(\bm{\theta})-Y_{s^{\prime}})^{2}$,
and
$L_{Y^{1}}(\bm{\theta}),L_{Y^{2}}(\bm{\theta}),\ldots,L_{Y^{t}}(\bm{\theta})$
for any $\bm{\theta}\in\mathbf{\Theta}$ are not independent. In contrast
[chaudhuri2015convergence] assumes that the loss functions are independent for
any time $s\in[t]$. Next we state the assumptions used for the proof of 6.

######  Assumption 3.

We assume that
$\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}\left(\bm{\theta}\right)$
is bounded such that
$\lambda_{\max}\left(\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}\left(\bm{\theta}\right)\right)\leq\lambda_{1}$
for each $s\in[1,t]$ and for all $\bm{\theta}^{\prime}\in\mathbf{\Theta}$.

The 3 is a mild assumption on the bounded nature of the eigenvalues of the
Hessian matrix
$\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}\left(\bm{\theta}\right)$
for any $\theta\in\mathbf{\Theta}$ evaluated at $\bm{\theta}^{\prime}$. Then
following assumption states a few regularity assumptions required for 6. A
similar assumption has also been used by chaudhuri2015convergence,
bu2019active.

######  Assumption 4.

(Assumptions for 6): We assume the following assumptions hold with probability
$1$:

  1. 1.

(Convexity of $L_{Y_{s}}$): The loss function $L_{Y_{s}}$ is convex for all
time $s\in[t]$.

  2. 2.

(Smoothness of $L_{Y_{s}}$): The $L_{Y_{s}}$ is smooth such that the first,
second, and third derivatives exist at all interior points in
$\mathbf{\Theta}$.

  3. 3.

(Regularity Conditions):

    1. (a)

$\mathbf{\Theta}$ is compact and $L_{Y_{s}}(\bm{\theta})$ is bounded for all
$\bm{\theta}\in\mathbf{\Theta}$ and for all $s\in[t]$.

    2. (b)

$\bm{\theta}^{*}$ is an interior point in $\mathbf{\Theta}$.

    3. (c)

$\nabla^{2}L_{Y_{s}}(\bm{\theta}^{*})$ is positive definite, for all $s\in[t]$
.

    4. (d)

There exists a neighborhood $B$ of $\bm{\theta}^{*}$ and a constant $C_{3}$,
such that $\nabla^{2}L_{Y_{s}}(\bm{\theta})$ is $C_{3}$ -Lipschitz. Hence, we
have that
$\left\|\nabla^{2}L_{Y_{s}}(\bm{\theta})-\nabla^{2}L_{Y_{s}}\left(\bm{\theta}^{\prime}\right)\right\|_{*}\leq
C_{3}\left\|\bm{\theta}-\bm{\theta}^{\prime}\right\|_{\nabla^{2}P_{s}\left(\bm{\theta}^{*}\right)}$,
for $\bm{\theta},\bm{\theta}^{\prime}$ in this neighborhood.

  4. 4.

(Concentration at $\bm{\theta}^{*}$): We further assume that $\left\|\nabla
L_{Y_{s}}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{s}\left(\bm{\theta}^{*}\right)\right)^{-1}}\leq
C_{1}$ and
$\left\|\nabla^{2}L_{Y_{s}}\left(\bm{\theta}^{*}\right)\right\|_{*}\leq C_{2}$
hold with probability one.

4 (c) is different from that of [chaudhuri2015convergence], where they assumed
that $\nabla^{2}\mathbb{E}[\psi_{s}](\bm{\theta}^{*})$ is positive definite,
where $\psi_{s}$ are i.i.d. loss functions from some distribution. In our case
the loss functions are not i.i.d., which is why we make the assumption on the
loss at every time $s$.

####  A.9.3 Concentration Lemmas

######  Lemma 12.

Define $u_{t}\coloneqq\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)$. Then
the probabiliity that
$\|u_{t}\|_{\left(\nabla^{2}P\left(\bm{\theta}^{*}\right)\right)^{-1}}$
crosses the threshold $\sqrt{\dfrac{cp\log(dt)}{t}}>0$ is bounded by

$\displaystyle\mathbb{P}\left(\|u_{t}\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}\geq
C_{1}\sqrt{\dfrac{cp\log(dt)}{t}}\right)\leq\frac{1}{t^{cp}}.$

###### Proof.

Define $u_{s}\coloneqq\nabla\widehat{P}_{s}\left(\bm{\theta}^{*}\right)$. Then
we have $u_{1},u_{2},\ldots,u_{t}$ as random vectors such that

$\displaystyle\mathbb{E}\left[\left\|\sum_{s=1}^{t}u_{s}\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}\bigg{|}u_{1},\ldots,u_{s-1}\right]=\mathbb{E}\left[\sum_{s=1}^{t}u_{s}^{\top}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}u_{s}\mid
u_{1},\ldots,u_{s-1}\right]\leq tC^{2}_{1}$

Also we have that $\|u_{s}\|\leq C_{1}$. Then following Lemma 4 and by setting
$\epsilon=cp\log(dt)$ we can show that

$\displaystyle\mathbb{P}$
$\displaystyle\left(\|\frac{1}{t}\sum_{s=1}^{t}u_{s}\|^{2}_{{}_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}}-\mathbb{E}\left[\|\frac{1}{t}\sum_{s=1}^{t}u_{s}\|^{2}_{{}_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}}\right]>\frac{1}{t}\sqrt{8tC_{1}^{2}\epsilon}+\dfrac{4C_{1}}{3\epsilon}\right)$
$\displaystyle=\mathbb{P}\left(\|\frac{1}{t}\sum_{s=1}^{t}u_{s}\|^{2}_{{}_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}}>C_{1}^{2}+C_{1}\sqrt{\frac{8\epsilon}{t}}+\dfrac{4C_{1}}{3\epsilon}\right)$
$\displaystyle\leq\mathbb{P}\left(\|\sum_{s=1}^{t}u_{s}\|^{2}_{{}_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}}>C_{1}\sqrt{\frac{8\epsilon}{t}}\right)=\mathbb{P}\left(\|\sum_{s=1}^{t}u_{s}\|^{2}_{{}_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}}>4C_{1}\sqrt{\dfrac{cp\log(dt)}{t}}\right)$
$\displaystyle\leq\exp(-cp\log(dt))=\left(\frac{1}{dt}\right)^{cp}\leq\frac{1}{t^{cp}}$

The claim of the lemma follows. ∎

######  Lemma 13.

Under 3 for any $x>0$ we can show that the conditional probability

$\displaystyle\mathbb{P}\left(\sum_{s=1}^{t}-2\left(Y_{s}-\mu_{I_{s}}\left(\bm{\theta}^{*}\right)\right)\lambda_{\max}\left(\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}\left(\bm{\theta}\right)\right)\geq
x\mid I^{t-1}\right)\leq
2\exp\left(-\dfrac{x^{2}}{2t\eta^{2}\lambda^{2}_{1}}\right).$

###### Proof.

Recall that the 3 states that
$\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}\left(\bm{\theta}\right)$
is bounded such that
$\lambda_{\max}\left(\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}\left(\bm{\theta}\right)\right)\leq\lambda_{1}$
for each $s\in[1,t]$ and for all $\bm{\theta}\in\mathbf{\Theta}$. Following
the 3 we have that

$-2\left(Y_{s}-\mu_{I_{s}}\left(\bm{\theta}^{*}\right)\right)\lambda_{\max}\left(\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}(\bm{\theta})\right)\in\left[-2\eta\lambda_{1},2\eta\lambda_{1}\right],$

for all $s\in[t]$ with

$\mathbb{E}\left[-2\left(Y_{s}-\mu_{I_{s}}\left(\bm{\theta}^{*}\right)\right)\lambda_{\max}\left(\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}(\bm{\theta})\right)\mid
I^{s-1}\right]=0$

and conditioned on
$\left(\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{t}\right)$, the
random variables
$-2\left(Y_{s}-\mu_{I_{s}}\left(\bm{\theta}^{*}\right)\right)$ are
independent. Hence, we can use Hoeffding’s inequality to get

$\displaystyle\mathbb{P}\left(\sum_{s=1}^{t}-2\left(Y_{s}-\mu_{I_{s}}\left(\bm{\theta}^{*}\right)\right)\lambda_{\max}\left(\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}\mu_{I_{s}}\left(\bm{\theta}\right)\right)\geq
x\mid I_{1},\ldots,I_{t-1}\right)$ $\displaystyle\leq
2\exp\left(-\dfrac{2x^{2}}{t4\eta^{2}\lambda_{1}^{2}}\right)$
$\displaystyle=2\exp\left(-\dfrac{x^{2}}{2t\eta^{2}\lambda_{1}^{2}}\right).$

The claim of the lemma follows. ∎

######  Lemma 14.

Let
$\widehat{P}_{t}(\bm{\theta}^{*})=\frac{1}{t}\sum_{s=1}^{t}L_{Y_{s}}(\bm{\theta}^{*})$
and
$\nabla^{2}P_{t}(\bm{\theta}^{*})=\frac{1}{t}\sum_{s=1}^{t}\nabla^{2}\mathbb{E}[L_{Y_{s}}(\bm{\theta}^{*})|\mathcal{F}^{s-1}]$.
Then we can bound the

$\displaystyle\mathbb{P}$
$\displaystyle\left(\lambda_{\max}(\nabla^{2}\widehat{P}_{t}(\bm{\theta}^{*})-\nabla^{2}P_{t}(\theta^{*}))>\sqrt{\dfrac{2\eta^{2}\lambda^{2}_{1}cp\log(dt)}{t}}|I^{t-1}\right)\leq\dfrac{2}{(dt)^{cp}}.$

###### Proof.

Recall that
$\widehat{P}_{t}(\bm{\theta}^{*})=\frac{1}{t}\sum_{s=1}^{t}L_{Y_{s}}(\bm{\theta}^{*})$
and
$\nabla^{2}P_{s}(\theta^{*})=\nabla^{2}\mathbb{E}[L_{Y_{s}}(\bm{\theta}^{*})|\mathcal{F}^{s-1}]$.
We define
$\nabla^{2}P_{t}(\bm{\theta}^{*})=\frac{1}{t}\sum_{s=1}^{t}\nabla^{2}\mathbb{E}[L_{Y_{s}}(\bm{\theta}^{*})|\mathcal{F}^{s-1}]$.
Then we can show that,

$\displaystyle\mathbb{P}$
$\displaystyle\left(\lambda_{\max}(\nabla^{2}\widehat{P}_{t}(\bm{\theta}^{*})-\nabla^{2}P_{t}(\theta^{*}))>\sqrt{\dfrac{2\eta^{2}\lambda^{2}_{1}cp\log(dt)}{t}}|I^{t-1}\right)$
$\displaystyle=\mathbb{P}\left(\lambda_{\max}\left(\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}\frac{1}{t}\sum_{s=1}^{t}L_{Y_{s}}(\bm{\theta})-\frac{1}{t}\sum_{s=1}^{t}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}]\right)>\sqrt{\dfrac{2\eta^{2}\lambda^{2}_{1}cp\log(dt)}{t}}|I^{t-1}\right)$
$\displaystyle=\mathbb{P}\left(\lambda_{\max}\left(\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}\frac{1}{t}\sum_{s=1}^{t}\left(L_{Y_{s}}(\bm{\theta})-\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}]\right)\right)>\sqrt{\dfrac{2\eta^{2}\lambda^{2}_{1}cp\log(dt)}{t}}|I^{t-1}\right)$
$\displaystyle\overset{(a)}{\leq}\mathbb{P}\left(\frac{1}{t}\sum_{s=1}^{t}\lambda_{\max}\left(\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}L_{Y_{s}}(\bm{\theta})-\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}]\right)>\sqrt{\dfrac{2\eta^{2}\lambda_{1}^{2}cp\log(dt)}{t}}|I^{t-1}\right)$
$\displaystyle\overset{(b)}{=}\mathbb{P}\left(\sum_{s=1}^{t}-2\left(Y_{s}-\mu_{I_{s}}\left(\bm{\theta}^{*}\right)\right)\lambda_{\max}\left(\nabla_{\bm{\theta}=\bm{\theta}^{*}}^{2}\mu_{I_{s}}\left(\bm{\theta}^{\prime}\right)\right)>t\sqrt{\dfrac{2\eta^{2}\lambda_{1}^{2}cp\log(dt)}{t}}|I^{t-1}\right)$
$\displaystyle\overset{(c)}{\leq}2\exp\left(-\dfrac{t^{2}2\eta^{2}\lambda_{1}^{2}cp\log(dt)}{t}\cdot\dfrac{1}{2t\eta^{2}\lambda_{1}^{2}}\right)\leq
2\left(\dfrac{1}{dt}\right)^{cp}.$

where, $(a)$ follows by triangle inequality, $(b)$ follows by substituting the
value of
$\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}L_{Y_{s}}(\bm{\theta})-\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}]$
from Lemma 17, and $(c)$ follows from Lemma 13. ∎

####  A.9.4 Support Lemma

######  Lemma 15.

Let the $j$-th row and $k$-th column entry in the Hessian matrix
$\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(L_{Y_{s}}(\bm{\theta}))$ be
denoted as
$[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(L_{Y_{s}}(\bm{\theta}))]_{jk}$.
Then we have that

$\displaystyle[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(L_{Y_{s}}(\bm{\theta}))]_{jk}=2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\left(\mu_{I_{s}}(\bm{\theta})-Y_{s}\right)\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}.$

###### Proof.

We want to evaluate the Hessian
$\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(L_{Y_{s}}(\bm{\theta}))$ at any
$\bm{\theta}^{\prime}\in\mathbf{\Theta}$. We denote the $j$-th row and $k$-th
column entry in the Hessian matrix as
$[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(L_{Y_{s}}(\bm{\theta}))]_{jk}$.
Then we can show that

$\displaystyle[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(L_{Y_{s}}(\bm{\theta}))]_{jk}$
$\displaystyle\coloneqq\frac{\partial}{\partial\bm{\theta}_{j}}\left[\frac{\partial(\mu_{I_{s}}(\bm{\theta})-Y_{s})^{2}}{\partial\bm{\theta}_{k}}\right]=\frac{\partial}{\partial\bm{\theta}_{j}}\left[2(\mu_{I_{s}}(\bm{\theta})-Y_{s})\frac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}\right]$
$\displaystyle=\frac{\partial}{\partial\bm{\theta}_{j}}\left[2\mu_{I_{s}}(\bm{\theta})\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}-2Y_{s}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}\right]$
$\displaystyle=2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\mu_{I_{s}}(\bm{\theta})\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}-2Y_{s}\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}-2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial
Y_{s}}{\partial\bm{\theta}_{k}}$
$\displaystyle=2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\left(\mu_{I_{s}}(\bm{\theta})-Y_{s}\right)\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}$

The claim of the lemma follows. ∎

######  Lemma 16.

AT: why is there no sum over s in the RHS? also why is $I_{s}$ still present
after the expectation Let the $j$-th row and $k$-th column entry in the
Hessian matrix
$\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}])$
be denoted as
$[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}])]_{jk}$.
Then we have that

$\displaystyle\left[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}\sum_{s=1}^{t}\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}]\right]_{jk}=2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\left(\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*})\right)\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}.$

###### Proof.

Now we want to evaluate the Hessian
$\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}])$
at any $\bm{\theta}^{\prime}\in\mathbf{\Theta}$. We denote the $j$-th row and
$k$-th column entry in the Hessian matrix as
$[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}(\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}])]_{jk}$.
Then we can show that

$\displaystyle\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}\sum_{s=1}^{t}\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}]$
$\displaystyle=\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}\sum_{s=1}^{t}\left(\mu^{2}_{I_{s}}(\bm{\theta})+\mathbb{E}[Y^{2}_{s}|\mathcal{F}^{s-1}]-2\mathbb{E}[Y_{s}|\mathcal{F}^{s-1}]\mu_{I_{s}}(\bm{\theta})\right)$
$\displaystyle=\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}\sum_{s=1}^{t}\left(\mu^{2}_{I_{s}}(\bm{\theta})+\mu^{2}_{I_{s}}(\bm{\theta}^{\prime})+\frac{1}{2}-2\mu_{I_{s}}(\bm{\theta}^{*})\mu_{I_{s}}(\bm{\theta})\right)$
$\displaystyle=\sum_{s=1}^{t}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}\left(\left(\mu_{I_{s}}(\bm{\theta}^{*})-\mu_{I_{s}}(\bm{\theta})\right)^{2}+\frac{1}{2}\right)$
$\displaystyle=\sum_{s=1}^{t}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}\left(\left(\mu_{I_{s}}(\bm{\theta}^{*})-\mu_{I_{s}}(\bm{\theta})\right)^{2}\right)$
(54)

We now denote the $j$-th row and $k$-th column entry of the Hessian Matrix
$\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}((\mu_{I_{s}}(\bm{\theta})-\mu_{i}(\bm{\theta}^{*}))^{2})$
as
$\big{[}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}((\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*}))^{2})\big{]}_{jk}$.
Then we can show that

$\displaystyle\big{[}\nabla^{2}_{\bm{\theta}=\bm{\theta}^{*}}((\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*}))^{2})\big{]}_{jk}$
$\displaystyle\coloneqq\frac{\partial}{\partial\bm{\theta}_{j}}\left[\frac{\partial(\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*}))^{2}}{\partial\bm{\theta}_{k}}\right]=\frac{\partial}{\partial\bm{\theta}_{j}}\left[2(\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*}))\frac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}\right]$
$\displaystyle=\frac{\partial}{\partial\bm{\theta}_{j}}\left[2\mu_{I_{s}}(\bm{\theta})\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}-2\mu_{i}(\bm{\theta}^{*})\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}\right]$
$\displaystyle=2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\mu_{I_{s}}(\bm{\theta})\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\bm{\theta}_{k}}$
$\displaystyle-2\mu_{I_{s}}(\bm{\theta}^{*})\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\bm{\theta}_{k}}-2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta}^{*})}{\partial\bm{\theta}_{k}}$
$\displaystyle=2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\left(\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*})\right)\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}$

Plugging this back in eq. 54 we get that

$\displaystyle\left[\nabla^{2}_{\bm{\theta}=\bm{\theta}^{\prime}}\sum_{s=1}^{t}\mathbb{E}[L_{Y_{s}}(\bm{\theta})|\mathcal{F}^{s-1}]\right]_{jk}=2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\left(\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*})\right)\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}.$

∎

######  Lemma 17.

The sum of the difference of the Hessians
$\sum_{s=1}^{t}\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)-\mathbb{E}\left[\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)\mid\mathcal{F}^{s-1}\right]$
is given by

$\displaystyle\sum_{s=1}^{t}$
$\displaystyle\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)-\mathbb{E}\left[\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)\mid\mathcal{F}^{s-1}\right]=\sum_{s=1}^{t}-2(Y_{s}-\mu_{I_{s}}(\bm{\theta}))\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}$

###### Proof.

First note that the difference
$\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)-\mathbb{E}\left[\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)\mid\mathcal{F}^{s-1}\right]$
is given by

$\displaystyle\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)-\mathbb{E}\left[\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)\mid\mathcal{F}^{s-1}\right]\overset{(a)}{=}$
$\displaystyle
2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}+2\left(\mu_{I_{s}}(\bm{\theta})-Y_{s}\right)\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}$
$\displaystyle-2\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}}\dfrac{\partial\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{k}}-2\left(\mu_{I_{s}}(\bm{\theta})-\mu_{I_{s}}(\bm{\theta}^{*})\right)\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}$
$\displaystyle=$
$\displaystyle-2(Y_{s}-\mu_{I_{s}}(\bm{\theta}))\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}$
(55)

where, $(a)$ follows from Lemma 15 and Lemma 16. Plugging this equality in
Equation 55 below we get

$\displaystyle\sum_{s=1}^{t}$
$\displaystyle\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)-\mathbb{E}\left[\nabla_{\bm{\theta}=\bm{\theta}^{\prime}}^{2}L_{Y_{s}}\left(\bm{\theta}\right)\mid\mathcal{F}^{s-1}\right]=\sum_{s=1}^{t}-2(Y_{s}-\mu_{I_{s}}(\bm{\theta}))\dfrac{\partial^{2}\mu_{I_{s}}(\bm{\theta})}{\partial\bm{\theta}_{j}\partial\bm{\theta}_{k}}.$

The claim of the lemma follows. ∎

######  Lemma 18.

Let
$\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}=\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\nabla\widehat{P}_{t}(\bm{\theta}^{*})$
where $\widetilde{\bm{\theta}}_{t}$ is between $\widehat{\bm{\theta}}_{t}$ and
$\bm{\theta}^{*}$. Then we can show that

$\displaystyle\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}\leq\left\|\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}\right\|\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}.$

###### Proof.

We begin with the definition of
$\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}$
as follows:

$\displaystyle\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}$
$\displaystyle\overset{(a)}{=}\sqrt{(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*})^{T}\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*})}$
$\displaystyle\overset{(b)}{=}\sqrt{\left(\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right)^{T}\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\left(\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right)}$
$\displaystyle\overset{(c)}{\leq}\left\|\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)^{1/2}\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)^{1/2}\right\|\sqrt{\left(\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)^{T}\left(\nabla^{2}P_{t}(\bm{\theta}^{*})\right)^{-1}\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right)}$
$\displaystyle=\left\|\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}\right\|\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}.$

where, $(a)$ follows as $\|x\|_{M}=\sqrt{x^{T}Mx}$, $(b)$ follows as
$\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\|_{\nabla^{2}P_{t}(\bm{\theta}^{*})}=\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}})\right)^{-1}\nabla\widehat{P}_{t}(\bm{\theta}^{*})$,
and $(c)$ follows from Cauchy Schwarz inequality.

The claim of the lemma follows. ∎

####  A.9.5 Proof of Main 6

######  Theorem 6.

(Restatement) Suppose
$L_{Y^{1}}(\bm{\theta}),L_{Y^{2}}(\bm{\theta}),\cdots,L_{Y^{t}}(\bm{\theta}):\mathbb{R}^{d}\rightarrow\mathbb{R}$
are squared loss functions from a distribution that satisfies 3 and 4. Further
define
$P_{t}(\bm{\theta})=\frac{1}{t}\sum_{s=1}^{t}\mathbb{E}_{I_{s}\sim\mathbf{p}_{\widehat{\bm{\theta}}_{s-1}}\atop
Y_{s}\sim\mathcal{N}(\mu_{I_{s}}(\bm{\theta}^{*}),\frac{1}{2})}[L_{s}(\bm{\theta})|\mathcal{F}^{s-1}]$
where, $\widehat{\bm{\theta}}_{t}=\mathop{\rm
arg\,min}_{\bm{\theta}\in\mathbf{\Theta}}\sum_{s=1}^{t}L_{s}(\bm{\theta})$. If
$t$ is large enough such that
$t\geq\frac{\left(C_{1}C_{3}+2\eta^{2}\lambda_{1}^{2}\right)p\log(dt)}{c^{\prime}}$
then we can show that for a constant $p$

$\displaystyle\left(1-\epsilon_{t}\right)\frac{\sigma^{2}}{t}-\frac{C_{1}^{2}}{t^{p/2}}\leq\mathbb{E}\left[P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right]\leq\left(1+\epsilon_{t}\right)\frac{\sigma^{2}}{t}+\frac{\max_{\bm{\theta}\in\mathbf{\Theta}}\left(P_{t}(\bm{\theta})-P_{t}\left(\bm{\theta}^{*}\right)\right)}{t^{p}}$

where,
$\sigma^{2}\coloneqq\mathbb{E}\left[\frac{1}{2}\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}\right]$,
and
$\epsilon_{t}\coloneqq\left(C_{1}C_{3}+2\eta^{2}\lambda_{1}^{2}\right)\sqrt{\frac{p\log(dt)}{t}}$.

###### Proof.

Step 1: We first bound the
$\left\|\nabla^{2}\widehat{P}_{t}(\bm{\theta})-\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right\|_{*}$
as follows

$\displaystyle\left\|\nabla^{2}\widehat{P}_{t}(\bm{\theta})-\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right\|_{*}$
$\displaystyle\overset{(a)}{\leq}\left\|\nabla^{2}\widehat{P}_{t}(\bm{\theta})-\nabla^{2}\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{*}+\left\|\nabla^{2}\widehat{P}_{t}\left(\bm{\theta}^{*}\right)-\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right\|_{*}$
$\displaystyle\overset{(b)}{\leq}C_{3}\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}+\sqrt{\dfrac{2\eta^{2}\lambda_{1}^{2}cp\log(dt)}{t}}$
(56)

where, $(a)$ follows from triangle inequality, and $(b)$ follows Lemma 14.

Step 2 (Approximation of $\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)$): By
choosing a sufficiently smaller ball $B_{1}$ of radius of
$\min\left\\{1/\left(10C_{3}\right),\right.$ diameter $\left.(B)\right\\}$ ),
the first term in (56) can be made small for $\bm{\theta}\in B_{1}$. Also, for
sufficiently large $t$, the second term in (56) can be made arbitrarily small
(smaller than $1/10$ ), which occurs if
$\sqrt{\frac{p\log(dt)}{t}}\leq\frac{c^{\prime}}{\sqrt{2\eta^{2}\lambda_{1}^{2}}}$.
Hence for large $t$ and $\bm{\theta}\in B_{1}$ we have

$\displaystyle\frac{1}{2}\nabla^{2}\widehat{P}_{t}(\bm{\theta})\preceq\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\preceq
2\nabla^{2}\widehat{P}_{t}(\bm{\theta})$ (57)

Step 3 (Show $\widehat{\bm{\theta}}_{t}$ in $B_{1}$): Fix a
$\widetilde{\bm{\theta}}$ between $\bm{\theta}$ and $\bm{\theta}^{*}$ in
$B_{1}$. Apply Taylor’s series approximation

$\displaystyle\widehat{P}_{t}(\bm{\theta})=\widehat{P}_{t}\left(\bm{\theta}^{*}\right)+\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)^{\top}\left(\bm{\theta}-\bm{\theta}^{*}\right)+\frac{1}{2}\left(\bm{\theta}-\bm{\theta}^{*}\right)^{\top}\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}})\left(\bm{\theta}-\bm{\theta}^{*}\right)$

We can further reduce this as follows:

$\displaystyle\widehat{P}_{t}(\bm{\theta})-\widehat{P}_{t}\left(\bm{\theta}^{*}\right)$
$\displaystyle\overset{(a)}{=}\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)^{\top}\left(\bm{\theta}-\bm{\theta}^{*}\right)+\frac{1}{2}\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}})}^{2}$
$\displaystyle\overset{(b)}{\geq}\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)^{\top}\left(\bm{\theta}-\bm{\theta}^{*}\right)+\frac{1}{4}\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}^{2}$
$\displaystyle\geq-\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}+\frac{1}{4}\left(\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}\right)^{\top}\left(\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}\right)$
$\displaystyle=\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}\left(-\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}+\frac{1}{4}\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}\right)$
(58)

where, $(a)$ follows as
$\left\|\bm{\theta}-\bm{\theta}^{*}\right\|_{\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}})}^{2}\coloneqq\left(\bm{\theta}-\bm{\theta}^{*}\right)^{\top}\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}})\left(\bm{\theta}-\bm{\theta}^{*}\right)$,
and $(b)$ follows as $\widetilde{\bm{\theta}}$ is in between $\bm{\theta}$ and
$\bm{\theta}^{*}$ and then using (57). Note that in (58) if the right hand
side is positive for some $\bm{\theta}\in B_{1}$, then $\bm{\theta}$ is not a
local minimum. Also, since
$\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|\rightarrow
0,$ for a sufficiently small value of
$\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|,$ all points
on the boundary of $B_{1}$ will have values greater than that of
$\bm{\theta}^{*}.$ Hence, we must have a local minimum of
$\widehat{P}_{t}(\bm{\theta})$ that is strictly inside $B_{1}$ (for $t$ large
enough). We can ensure this local minimum condition is achieved by choosing an
$t$ large enough so that $\sqrt{\frac{p\log(dt)}{t}}\leq
c^{\prime}\min\left\\{\frac{1}{L_{1}L_{3}},\frac{\operatorname{diameter}(B)}{L_{1}}\right\\},$
using Lemma 12 (and our bound on the diameter of $B_{1}$ ). By convexity, we
have that this is the global minimum, $\widehat{\bm{\theta}}_{t},$ and so
$\widehat{\bm{\theta}}_{t}\in B_{1}$ for $t$ large enough. We will assume now
that $t$ is this large from here on.

Step 4 (Bound
$\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}$):
For the ERM, $0=\nabla\widehat{P}_{t}(\widehat{\bm{\theta}}_{t})$. Again,
using Taylor’s theorem if $\widehat{\bm{\theta}}_{t}$ is an interior point, we
have:

$\displaystyle
0=\nabla\widehat{P}_{t}(\widehat{\bm{\theta}}_{t})=\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)+\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)$
(59)

for some $\widetilde{\bm{\theta}}_{t}$ between $\bm{\theta}^{*}$ and
$\widehat{\bm{\theta}}_{t}$. Now observe that $\widetilde{\bm{\theta}}_{t}$ is
in $B_{1}$ (since, for $t$ large enough, $\widehat{\bm{\theta}}_{t}\in B_{1}$
). Thus it follows from (59) that,

$\displaystyle\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}=\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)$
(60)

where the invertibility is guaranteed by (57) and the positive definiteness of
$\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)$ (by 4 (3c)). We finally derive
the upper bound to
$\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}$
as follows

$\displaystyle\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}$
$\displaystyle\overset{(a)}{\leq}\left\|\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}\right\|\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}$
$\displaystyle\overset{(b)}{\leq}cL_{1}\sqrt{\frac{p\log(dt)}{t}}$ (61)

where $(a)$ follows from Lemma 18, and $(b)$ from Lemma 12.

Step 5 (Introducing $\widetilde{\mathbf{z}}$): Fix a
$\widetilde{\mathbf{z}}_{t}$ between $\bm{\theta}^{*}$ and
$\widehat{\bm{\theta}}_{t}$. Apply Taylor’s series

$\displaystyle
P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)=\frac{1}{2}\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)^{\top}\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)$
(62)

Now note that both $\widetilde{\bm{\theta}}_{t}$ and
$\widetilde{\mathbf{z}}_{t}$ are between $\widehat{\bm{\theta}}_{t}$ and
$\bm{\theta}^{*},$ which implies
$\widetilde{\bm{\theta}}_{t}\rightarrow\bm{\theta}^{*}$ and
$\widetilde{\mathbf{z}}_{t}\rightarrow\bm{\theta}^{*}$ since
$\widehat{\bm{\theta}}_{t}\rightarrow\bm{\theta}^{*}$. By (56) and (61) and
applying the concentration inequalities give us

$\displaystyle\left\|\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})-\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right\|_{*}\leq\epsilon_{t}$
(63)
$\displaystyle\left\|\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)-\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right\|_{*}\leq
L_{3}\left\|\widetilde{\mathbf{z}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}\leq\epsilon_{t}$
(64)

where
$\epsilon_{t}=c\left(L_{1}L_{3}+2\eta^{2}\lambda_{1}^{2}\right)\sqrt{\frac{p\log(dt)}{t}}$.

Step 6 (Define $\mathbf{M}_{1,t}$ and $\mathbf{M}_{2,t}$): It follows from the
above inequalities (63) and (64) that

$\displaystyle\left(1-\epsilon_{t}\right)\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\preceq\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\preceq\left(1+\epsilon_{t}\right)\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)$
$\displaystyle\left(1-\epsilon_{t}\right)\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\preceq\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)\preceq\left(1+\epsilon_{t}\right)\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)$

Now we define the two quantities $\mathbf{M}_{1,t}$ and $\mathbf{M}_{2,t}$ as
follows:

$\displaystyle\mathbf{M}_{1,t}$
$\displaystyle=\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{1/2}$
$\displaystyle\mathbf{M}_{2,t}$
$\displaystyle=\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1/2}\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1/2}$

Step 7 (Lower bound
$P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)$): Now for
the lower bound it follows from Equation 62 that

$\displaystyle
P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)$
$\displaystyle=\frac{1}{2}\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)^{\top}\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)$
$\displaystyle=\frac{1}{2}\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)^{\top}\nabla^{2}P_{t}(\bm{\theta}^{*})\nabla^{2}P_{t}(\bm{\theta}^{*})^{-1}\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)$
$\displaystyle=\frac{1}{2}\nabla^{2}P_{t}(\bm{\theta}^{*})^{-1}\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)^{\top}\nabla^{2}P_{t}(\bm{\theta}^{*})\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)$
$\displaystyle=\frac{1}{2}\nabla^{2}P_{t}(\bm{\theta}^{*})^{-1/2}\nabla^{2}P_{t}\left(\widetilde{\mathbf{z}}_{t}\right)\nabla^{2}P_{t}(\bm{\theta}^{*})^{-1/2}\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}^{2}$
$\displaystyle\overset{(a)}{=}\frac{1}{2}\mathbf{M}_{2,t}\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}^{2}$

where, $(a)$ follows from definition of $\mathbf{M}_{2,t}$. Then using the
min-max theorem we can show that

$\displaystyle
P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)$
$\displaystyle\geq\frac{1}{2}\lambda_{\min}\left(\mathbf{M}_{2,t}\right)\left\|\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}^{2}$
$\displaystyle\overset{}{=}\frac{1}{2}\lambda_{\min}\left(\mathbf{M}_{2,t}\right)\left\|\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\left(\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\right)^{-1}}^{2}$
$\displaystyle\geq\frac{1}{2}\left(\lambda_{\min}\left(\mathbf{M}_{1,t}\right)\right)^{2}\lambda_{\min}\left(\mathbf{M}_{2,t}\right)\left\|\nabla^{2}\widehat{P}_{t}(\widetilde{\bm{\theta}}_{t})\left(\widehat{\bm{\theta}}_{t}-\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}$
$\displaystyle\overset{(a)}{=}\frac{1}{2}\left(\lambda_{\min}\left(\mathbf{M}_{1,t}\right)\right)^{2}\lambda_{\min}\left(\mathbf{M}_{2,t}\right)\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}$

where, in $(a)$ we use the eq. 60.

Step 8: Define $I(\mathcal{E})$ as the indicator that the desired previous
events hold, which we can ensure with probability greater than
$1-\dfrac{2}{t^{p}}$. Then we can show that:

$\displaystyle\mathbb{E}\left[P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right]\geq$
$\displaystyle\mathbb{E}\left[\left(P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right)I(\mathcal{E})\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\left(\lambda_{\min}\left(\mathbf{M}_{1,t}\right)\right)^{2}\lambda_{\min}\left(\mathbf{M}_{2,t}\right)\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}I(\mathcal{E})\right]$
$\displaystyle\geq$
$\displaystyle\left(1-c^{\prime}\epsilon_{t}\right)\frac{1}{2}\mathbb{E}\left[\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}I(\mathcal{E})\right]$
$\displaystyle=$
$\displaystyle\left(1-c^{\prime}\epsilon_{t}\right)\frac{1}{2}\mathbb{E}\left[\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}(1-I(\operatorname{not}\mathcal{E}))\right]$
$\displaystyle\overset{(a)}{=}$
$\displaystyle\left(1-c^{\prime}\epsilon_{t}\right)\left(\sigma^{2}-\frac{1}{2}\mathbb{E}\left[\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}I(\operatorname{not}\mathcal{E})\right]\right)$
$\displaystyle\geq$
$\displaystyle\left(1-c^{\prime}\epsilon_{t}\right)\sigma^{2}-\mathbb{E}\left[\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}I(\operatorname{not}\mathcal{E})\right]$

where, in $(a)$ we have
$\sigma^{2}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}$,
and $c^{\prime}$ is an universal constant.

Step 9: Define the random variable
$Z=\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}$.
With a failure event probability of less than $\dfrac{1}{2t^{p}},$ for any
$z_{0},$ we have:

$\displaystyle\mathbb{E}\left[Z^{2}I(\operatorname{not}\mathcal{E})\right]$
$\displaystyle=\mathbb{E}\left[Z^{2}I(\operatorname{not}\mathcal{E})I\left(Z^{2}<z_{0}\right)\right]+\mathbb{E}\left[Z^{2}I(\operatorname{not}\mathcal{E})I\left(Z^{2}\geq
z_{0}\right)\right]$ $\displaystyle\leq
z_{0}\mathbb{E}[I(\operatorname{not}\mathcal{E})]+\mathbb{E}\left[Z^{2}I\left(Z^{2}\geq
z_{0}\right)\right]$
$\displaystyle\leq\frac{z_{0}}{2t^{p}}+\mathbb{E}\left[Z^{2}\frac{Z^{2}}{z_{0}}\right]$
$\displaystyle\leq\frac{z_{0}}{2t^{p}}+\frac{\mathbb{E}\left[Z^{4}\right]}{z_{0}}$
$\displaystyle\leq\frac{\sqrt{\mathbb{E}\left[Z^{4}\right]}}{t^{p/2}}$

where $z_{0}=t^{p/2}\sqrt{\mathbb{E}\left[Z^{4}\right]}$.

Step 10 (Upper Bound):  For an upper bound we have that:

$\displaystyle\mathbb{E}\left[P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right]$
$\displaystyle=\mathbb{E}\left[\left(P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right)I(\mathcal{E})\right]+\mathbb{E}\left[\left(P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right)I(\operatorname{not}\mathcal{E})\right]$
$\displaystyle\leq\mathbb{E}\left[\left(P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right)I(\mathcal{E})\right]+\frac{\max_{\bm{\theta}\in\mathbf{\Theta}}\left(P_{t}(\bm{\theta})-P_{t}\left(\bm{\theta}^{*}\right)\right)}{t^{p}}$

since the probability of not $\mathcal{E}$ is less than $\dfrac{1}{t^{p}}$.
Now for an upper bound of the first term, observe that

$\displaystyle\mathbb{E}\left[\left(P_{t}(\widehat{\bm{\theta}}_{t})-P_{t}\left(\bm{\theta}^{*}\right)\right)I(\mathcal{E})\right]\leq$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\left(\lambda_{\max}\left(\mathbf{M}_{1,t}\right)\right)^{2}\lambda_{\max}\left(\mathbf{M}_{2,t}\right)\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)}^{2}I(\mathcal{E})\right]$
$\displaystyle\leq$
$\displaystyle\left(1+c^{\prime}\epsilon_{t}\right)\frac{1}{2}\mathbb{E}\left[\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}I(\mathcal{E})\right]$
$\displaystyle\leq$
$\displaystyle\left(1+c^{\prime}\epsilon_{t}\right)\frac{1}{2}\mathbb{E}\left[\left\|\nabla\widehat{P}_{t}\left(\bm{\theta}^{*}\right)\right\|_{\left(\nabla^{2}P_{t}\left(\bm{\theta}^{*}\right)\right)^{-1}}^{2}\right]$
$\displaystyle=$
$\displaystyle\left(1+c^{\prime}\epsilon_{t}\right)\frac{\sigma^{2}}{t}$

where, $c^{\prime}$ is another universal constant. ∎

###  A.10 Additional Experiment Details

####  A.10.1 Hypothesis Testing Experiments

In all the active testing experiments we use the threshold function for the
Gaussian distribution as proved in Lemma 10. Hence the threshold function used
is

$\displaystyle\beta=\log(J/\delta).$

Note that this threshold function is smaller than the general sub-Gaussian
threshold function proved in Lemma 9.

Example 1:  Recall that the Example 1 is given by the following table under
the three different hypotheses
$\\{\bm{\theta}^{\ast},\bm{\theta}^{\prime},\bm{\theta}^{\prime\prime}\\}$

$\displaystyle\begin{matrix}\bm{\theta}&=&\bm{\theta}^{*}&\bm{\theta}^{\prime}&\bm{\theta}^{{}^{\prime\prime}}\\\
\hline\cr\mu_{1}(\bm{\theta})&=&1&0.001&0\\\
\mu_{2}(\bm{\theta})&=&1&1.002&0.998\end{matrix}$

We can show that under $p_{\bm{\theta}^{*}}$ we have the following
optimization problem

$\displaystyle\max\ell$ s.t. $\displaystyle
p(1)0.999^{2}+p(2)0.002^{2}\geq\ell$ $\displaystyle
p(1)1^{2}+p(2)0.002^{2}\geq\ell.$

The solution to the above optimization is given by
$p_{\bm{\theta}^{*}}=[p(1),p(2)]=[1,0]$. Similarly we can show that
$p_{\bm{\theta}^{\prime}}$ we have the following optimization problem

$\displaystyle\max\ell$ s.t. $\displaystyle
p(1)0.001^{2}+p(2)0.002^{2}\geq\ell$ $\displaystyle
p(1)0.001^{2}+p(2)0.004^{2}\geq\ell.$

The solution to the above optimization is given by
$p_{\bm{\theta}^{\prime}}=[p(1),p(2)]=[0,1]$. Finally we can show that
$p_{\bm{\theta}^{\prime\prime}}$ we have the following optimization problem

$\displaystyle\max\ell$ s.t. $\displaystyle
p(1)0.001^{2}+p(2)0.004^{2}\geq\ell$ $\displaystyle
p(1)1^{2}+p(2)0.002^{2}\geq\ell.$

The solution to the above optimization is given by
$p_{\bm{\theta}^{\prime\prime}}=[p(1),p(2)]=[0,1]$. Hence,
$D_{1}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\min_{p_{\bm{\theta}}\in\mathbf{\Theta}}\min_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\sum_{i=1}^{n}p_{\bm{\theta}}(i)(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{*}))^{2}=0.002^{2}=4\times
10^{-6}$. Similarly, we can compute that
$D_{0}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\max_{\mathbb{p}}\min_{\bm{\theta}^{\prime}\neq\bm{\theta}^{*}}\sum_{i=1}^{n}(\mu_{i}(\bm{\theta}^{\prime})-\mu_{i}(\bm{\theta}^{*}))^{2}=0.999^{2}$.
Hence the non-asymptotic term $(\log J)/D_{1}=0.3\times 10^{6}$ and the
asymptotic term $\log(J/\delta)/D_{0}=3.4$.

Active Testing environment ($3$ Group setting):  In this setting there are
three groups of actions. In first group there is a single action that
discriminates best between all pair of hypotheses. In second group there are
$5$ actions which can discriminate one hypotheses from others. Finally in the
third group there are $44$ actions which cannot discriminate between any pair
of hypotheses. The following table describes the
$\mu_{1}(\cdot),\mu_{2}(\cdot),\ldots,\mu_{50}(\cdot)$ under different
hypotheses as follows:

$\displaystyle\begin{matrix}\bm{\theta}&=&\bm{\theta}^{*}&\bm{\theta}_{2}&\bm{\theta}_{3}&\bm{\theta}_{4}&\bm{\theta}_{5}&\bm{\theta}_{6}\\\
\hline\cr\mu_{1}(\bm{\theta})&=&{\color[rgb]{1,0,0}3}&0&0&0&0&0\\\
\mu_{2}(\bm{\theta})&=&2&{\color[rgb]{1,0,0}3}&2&2&2&2\\\
\mu_{3}(\bm{\theta})&=&2&2&{\color[rgb]{1,0,0}3}&2&2&2\\\
\mu_{4}(\bm{\theta})&=&2&2&2&{\color[rgb]{1,0,0}3}&2&2\\\
\mu_{5}(\bm{\theta})&=&2&2&2&2&{\color[rgb]{1,0,0}3}&2\\\
\mu_{6}(\bm{\theta})&=&2&2&2&2&2&{\color[rgb]{1,0,0}3}\\\
\mu_{7}(\bm{\theta})&=&1+\epsilon_{7,1}&1+\epsilon_{7,2}&1+\epsilon_{7,3}&1+\epsilon_{7,4}&1+\epsilon_{7,5}&1+\epsilon_{7,6}\\\
\vdots&&&\vdots\\\
\mu_{50}(\bm{\theta})&=&1+\epsilon_{50,1}&1+\epsilon_{50,2}&1+\epsilon_{50,3}&1+\epsilon_{50,4}&1+\epsilon_{50,5}&1+\epsilon_{50,6}\end{matrix}$

In the above setting,we define $\epsilon_{i,j}$ for the $i$-th action and
$j$-th hypothesis as a small value close to $0$ and
$\epsilon_{i,j}\neq\epsilon_{i^{\prime},j^{\prime}}$ for any pair of
hypotheses $j,j^{\prime}\in[J]$ and actions $i,i^{\prime}\in[n]$.

####  A.10.2 Active Regression Experiment for Non-linear Reward Model

Algorithmic Details:  We describe each of the algorithm used in this setting
as follows:

  1. 1.

EMCM : The EMCM algorithm of cai2016batch first quantifies the change as the
difference between the current model parameters and the new model parameters
learned from enlarged training data, and then chooses the data examples that
result in the greatest change.

  2. 2.

$\epsilon$-Ortho-Greedy : The $\epsilon$-Ortho-Greedy algorithm with
$(1-\epsilon)$ probability at each round chooses the most orthogonal action to
its least square estimate $\widehat{\bm{\theta}}(t)$ to maximally reduce the
uncertainty of $\widehat{\bm{\theta}}(t)$. Additionally it explores other
actions with $\epsilon$ probability. We set $\epsilon=0.1$.

  3. 3.

GC : The GC policy used is stated as in Section 3. To calculate the least
square estimate $\widehat{\bm{\theta}}(t)$ we use the python scipy.optimize
least-square function which solves a nonlinear least-squares problem.

  4. 4.

Unif : The Unif policy samples each action uniform randomly at every round.

  5. 5.

ActiveS : The ActiveS policy in chaudhuri2015convergence is a two-stage
algorithm. It first samples all actions uniform randomly to build an initial
estimate of $\bm{\theta}^{*}$. It then solves an Semi-definite Programming
(SDP) to obtain a new sampling distribution that minimizes the quantity
$\sigma^{2}_{U}$ as defined in Equation 52. In the second stage ActiveS
follows this new sampling distribution to sample actions.

Implementation Details:  This setting consist of $50$ measurement actions
divided into three groups. The first group consist of the optimal action
$\mathbf{x}_{i^{*}}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}(1,0)$
in the direction of
$\bm{\theta}^{*}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}(1,0)$.
The second group consist of the informative action
$\mathbf{x}_{2}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}(0,1)$
which is orthogonal to $\mathbf{x}_{i^{*}}$ and selecting it maximally reduces
the uncertainty of $\widehat{\bm{\theta}}(t)$. Finally the third group consist
of $48$ actions such that
$\mathbf{x}_{i}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}(0.71\pm\epsilon_{i},0.71\mp\epsilon_{i})$
for $i\in[3,50]$ where $\epsilon_{i}$ is a small value close to $0$ and
$\epsilon_{i}\neq\epsilon_{i^{\prime}}$. Note that these $48$ actions are less
informative in comparison to action $2$. This is shown in Figure 1c.

####  A.10.3 Active Regression Experiment for Neural Networks From

Implementation Details: At every time step, we use the the least squares
optimizer of scipy to find $\widehat{\bm{\theta}}_{t}$. Since
$c_{1},c_{2}\in\\{-1,1\\}$, we solve four different least squares problems at
each step corresponding to all $(c_{1},c_{2})$ choices, and use the values
returned by the problem having the smallest sum of squares as our current
estimate for $(\mathbf{w}_{1},\mathbf{w}_{2},b_{1},b_{2})$. The derivative
with respect to any parameter is found by the backward pass of automatic
differentiation.

####  A.10.4 Active Regression for the UCI Datasets

Implementation Details: The UCI Red Wine Quality dataset consist of $1600$
samples of red wine with each sample $i$ having feature
$\mathbf{x}_{i}\in\mathbb{R}^{11}$. We first fit a least square estimate to
the original dataset and get an estimate of $\bm{\theta}^{*}$. The reward
model is linear and given by
$\mathbf{x}_{I_{t}}^{T}\bm{\theta}^{*}+\epsilon_{t}$ where $x_{I_{t}}$ is the
observed action at round $t$, and $\epsilon_{t}$ is a zero-mean additive
noise. Note that we consider the $1600$ samples as actions. Then we run each
of our benchmark algorithms on this dataset and reward model and show the
result in Figure 1g. We further show the GC proportion on this dataset in fig.
1i and show that it is indeed sparse with proportion concentrated on few
actions. The Air quality dataset consist of $1500$ samples each of which
consist of $6$ features. We again build an estimate of $\bm{\theta}^{*}$ by
fitting a least square regression on this dataset. We use a similar additive
noise linear reward model as described before and run all the benchmark
algorithms on this dataset.

###  A.11 Table of Notations

Notation | Definition
---|---
$n$ | Total number of actions
$J$ | Total number of hypotheses
$\mathbf{\Theta}$ | Parameter Space
$\mu_{i}(\bm{\theta})$ | Mean of action $i$ under hypothesis $\bm{\theta}$
$\pi$ | Policy
$\delta$ | Probability of error of $\delta$-PAC policy
$\tau_{\delta}$ | Stopping time
$\beta(J,\delta)$ | $\log(J/\delta)$
$\alpha(J)$ | $\ell\log(J),\ell>0$
$Y^{t}$ | Vector of rewards observed till round $t$
$I^{t}$ | Vector of actions sampled till round $t$
$I_{s}$ | action sampled at round $s$
$\tau_{\delta}$ | Stopping time of $\delta$-PAC policy
$Z_{i}(t)$ | Number of time action $i$ is sampled till round $t$
$\mathbf{p}_{\bm{\theta}}$ | p.m.f. to verify hypothesis $\bm{\theta}$ (Solution to Chernoff optimization in (3))
$\mathrm{KL}(.||.)$ | Kullback-Leibler divergence
$\widehat{\bm{\theta}}(s)$ | Most likely hypothesis at round $s$
$\tilde{\bm{\theta}}(s)$ | Second most likely hypothesis at round $s$
$L_{Y^{t}}(\bm{\theta})$ | Sum of squared errors till round $t$ under hypothesis $\bm{\theta}$
$T_{Y^{t}}(\bm{\theta},\bm{\theta}^{*})$ | $L_{Y^{t}}(\bm{\theta})-L_{Y^{t}}(\bm{\theta}^{*})$
$\xi^{\delta}(\bm{\theta},\bm{\theta}^{*})$ | Event that $\\{L_{Y^{\tau_{\delta}}}(\bm{\theta}^{\prime})-L_{Y^{\tau_{\delta}}}(\bm{\theta})>\beta(J,\delta),\forall\bm{\theta}^{\prime}\neq\bm{\theta}\\}$
$(1+c)M$ | Critical number of samples $(1+c)\left(\nicefrac{{\log J}}{{D_{1}}}+\nicefrac{{\log(J/\delta)}}{{D_{0}}}\right),c>0$
$\mathcal{I}$ | $\\{i\in[n]:i=\mathop{\rm arg\,max}_{i^{\prime}\in[n]}(\mu_{i^{\prime}}(\bm{\theta})-\mu_{i^{\prime}}(\bm{\theta}^{\prime}))^{2}\text{ for some }\bm{\theta},\bm{\theta}^{\prime}\in\mathbf{\Theta}\\}$
Table 4: Table of Notations