\section{Theoretical results}

As mentioned above, there are three theoretical contributions in this work: 1. We provide simple regret upper bound of BLiE algorithm; 2. We show that BLiE requires very few rounds of data communications; 3. We also develop simple regret lower bounds for uniform search and random-search-based algorithms, which demonstrate that BLiE has better performance.

\subsection{Simple regret upper bound of BLiE}\label{sec:log}
The following Theorem gives the simple regret upper bound of BLiE algorithm with Doubling Edge-length Sequence $r_m=2^{-m}$. Doubling Sequence is also the edge-length sequence used in our experiments.

\begin{theorem}\label{thm:blin-upper}
If Assumption \ref{ass:hoeffding} and \ref{ass:lip} are satisfied, then output arm $\widetilde{x}^*$ of BLiE algorithm with total budget $T$, edge-length sequence $r_m=2^{-m}$, $\alpha=2L+2$ and $\beta$ satisfies
\begin{equation}\label{upp-simple}
    \Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}},
\end{equation}
where $d_z$ is the zooming dimension and $c$ is a constant. In addition, BLiE needs no more than $\frac{1}{d_z+\beta}\log T$ batches to achieve this simple regret.
\end{theorem}

Our analysis needs the following lemma, which shows that BLiE can gradually identify areas with small simple regret. The proofs of Theorem \ref{thm:blin-upper} and Lemma \ref{lem:eli} are in Appendix.

\begin{lemma}\label{lem:eli}
    For any $1\leq m\leq B$, any $C\in\mathcal{A}_m$ and any $x\in C$, simple regret of arm $x$ satisfies $\Delta_x\leq(4L+4)r_{m-1}$.
\end{lemma}

\subsection{Achiving better communication bound}\label{sec:loglog}

The communication bound can be improved without causing worse simple regret. To achieve this, we use the following edge length sequence.

\begin{definition}
    \label{def:ace}
    For a problem with ambient dimension $d$, zooming dimension $d_z$ and time horizon $T$, we denote $c_1=\frac{d_z+\beta-1}{(d_z+\beta)(d+\beta)}\log T$ and $c_{i+1} = {\eta c_i }$ for any $i\ge 1$, where $\eta=\frac{d+1-d_z}{d+\beta}$. Then we let $\alpha_n=\lfloor\sum_{i=1}^nc_i\rfloor$, $\beta_n=\lceil\sum_{i=1}^nc_i\rceil$, and define\footnote{To simplify the notation, in this subsection we assume $\{r_m\}$ is strictly decreasing. See Appendix \ref{app:race} for the version without this assumption.} Appropriate Combined Edge-length Sequence (ACE Sequence) $\{r_m\}_{m\in\mathbb{N}}$ as $r_m=2^{-\alpha_k}$ for $m=2k-1$ and $r_m=2^{-\beta_k}$ for $m=2k$.
\end{definition}
Then we show that BLiE with ACE Sequence can achieve the same simple regret using only $\mathcal{O}(\log\log T)$ batches.

\begin{theorem}\label{thm:ace}

If Assumption \ref{ass:hoeffding} and \ref{ass:lip} are satisfied, then output arm $\widetilde{x}^*$ of BLiE algorithm with total budget $T$, ACE Sequence $\{r_m\}$, $\alpha=2L+2$ and $\beta$ satisfies $$\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}},$$
where $d_z$ is the zooming dimension and $c$ is a constant. In addition, BLiE needs $\mathcal{O}(\log\log T)$ batches to achieve this simple regret.
\end{theorem}
\begin{proof}
We let $B$ be the total number of batches of the BLiE run ($B-1$ batches in the for-loop and $1$ clean-up batch), and $N_m$ be the total budget of batch $m$. In the following analysis, we bound $N_m$ for $m=2k-1$ and $m=2k$ separately, and then obtain the simple regret upper bound.

Firstly, we consider the case $m=2k-1$. For convenience, we let $\widetilde{r}_k=2^{-\sum_{i=1}^kc_i}$, and thus we have $\widetilde{r}_{k-1}\geq r_{m-1}\geq r_m\geq \widetilde{r}_{k}$. Recall that $\mathcal{A}_{m-1}^+$ is set of cubes not eliminated in batch $m-1$, and $\cup_{C\in\mathcal{A}_{m-1}^+}C=\cup_{C^\prime\in\mathcal{A}_m}C^\prime$. Lemma \ref{lem:eli} implies that each cube in $\mathcal{A}_{m-1}^+$ is a subset of $S((4L+4)r_{m-1})$, and thus $\left|\mathcal{A}_{m-1}^+\right|\leq N_{r_{m-1}}\leq C_z\cdot r_{m-1}^{-d_z}$. The total budget of batch $m$ is
\begin{align*}
    N_m= \; |\mathcal{A}_m|\cdot n_m = \left(\frac{r_{m-1}}{r_m}\right)^d\left|\mathcal{A}_{m-1}^+\right|\cdot n_m
    \leq \; C_z\cdot\frac{r_{m-1}^{d+1-d_z}\cdot r_m^{-d-\beta}}{r_{m-1}}
    \leq C_z\cdot\frac{\widetilde{r}_{k-1}^{d+1-d_z}\cdot\widetilde{r}_k^{-d-\beta}}{r_{m-1}}.
\end{align*}
For the numerator, we have
\begin{align*}
    \widetilde{r}_{k-1}^{d+1-d_z}\cdot\widetilde{r}_k^{-d-\beta}
    = \; 2^{-\left(\sum_{i=1}^{k-1}c_i\right)(d+1-d_z)+\left(\sum_{i=1}^{k}c_i\right)(d+\beta)}
    = \; 2^{\left(\sum_{i=1}^{k-1}c_i\right)(d_z+\beta-1)+c_m(d+\beta)}.
\end{align*}
Define $C_m=\left(\sum_{i=1}^{k-1}c_i\right)(d_z+\beta-1)+c_m(d+\beta)$. Since $c_m=c_{m-1}\cdot\frac{d+1-d_z}{d+\beta}$, calculation shows that $C_m = (\sum_{i=1}^{m-2} c_i) (d_z+\beta-1)  + c_{m-1}(d+\beta)+ c_{m-1}(d_z+\beta-1-d-\beta)+c_m(d+\beta)=C_{m-1}$. Thus for any $m$, we have $C_M=C_1=\frac{d_z+\beta-1}{d_z+\beta}\log T$. Hence,
\begin{equation*}
    N_m\leq C_z\cdot2^{\frac{d_z+\beta-1}{d_z+\beta}\log T}/r_{m-1}=C_z\cdot T^{\frac{d_z+\beta-1}{d_z+\beta}}/r_{m-1}.
\end{equation*}

Secondly, we consider the case $m=2k$. Lemma \ref{lem:eli} implies that each cube in $\mathcal{A}_m$ is a subset of $S(8L+8)r_m$. Similar argument to the first case shows that $\left|\mathcal{A}_m\right|\leq C_z\cdot r_m^{-d_z}$ and $N_m\leq C_z\cdot r_m^{-(d_z+\beta)}$.

Line 7 of Algorithm \ref{BLiN} ensures that the sum of budgets of full $B$ batches is greater than $T$. Therefore, combining the above two cases, we have
\begin{align}\label{upp-budget-ace}
    T\leq&\sum_{\substack{m=2k-1, \\ m\leq B }}C_z \cdot\frac{T^{\frac{d_z+\beta-1}{d_z+\beta}}}{r_{m-1}}+\sum_{\substack{m=2k,\\mathrm{m}\leq B}}C_z\cdot \frac{1}{r_m^{d_z+\beta}}.
\end{align}

The rounding step in Definition \ref{def:ace} yields that $r_m\leq\frac{r_{m-1}}{2}$ for any $m$. If $B$ is odd, from (\ref{upp-budget-ace}) we have $T\leq2C_z\cdot T^{\frac{d_z+\beta-1}{d_z+\beta}}\cdot\frac{1}{r_{B-1}}+2C_z\cdot\frac{1}{r_{B-1}^{d_z+\beta}}$.  We set $c_r=\max\{(4C_z)^\frac{1}{d_z+\beta}, 4C_z\}$, then $\frac{1}{c_r^{d_z+\beta}}+\frac{1}{c_r}\leq\frac{1}{2C_z}$ and the above inequality implies that $r_{B-1}\leq c_r\cdot T^{-\frac{1}{d_z+\beta}}$. Lemma \ref{lem:eli} shows that $\Delta_x\leq(4L+4)r_{B-1}$ for any $x\in\cup_{C\in\mathcal{A}_B}C$, so we have $\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}}$, where $c=(8L+8)\cdot\max\{c_r, 1\}$. If $B$ is even, similar arguments also yleid that $\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}}$. See Appendix \ref{app:race} for details.

Finally, we consider the communication bound. For any $B^*$, $\widetilde{r}_{B^*}=2^{-\sum_{i=1}^{B^*}c_i}=2^{-c_1\cdot\frac{1-\eta^{B^*}}{1-\eta}}=T^{-\frac{1}{d_z+\beta}}\cdot T^{\frac{\eta^{B^*}}{d_z+\beta}}$. Then by choosing $B^*\geq\frac{\log\log T-\log(d_z+\beta)}{\log\frac{d+\beta}{d+1-d_z}}$, we have $\frac{\eta^{B^*}}{d_z+\beta}\leq\log T$ and $\widetilde{r}_{B^*}\leq T^{-\frac{1}{d_z+\beta}}$. Definition \ref{def:ace} shows that $r_m<\widetilde{r}_{B^*}$ for any $m\geq2B^*$. As a consequence, no more than $\hat{B}=\frac{2\log\log T}{\log\frac{d+\beta}{d+1-d_z}} + 1$ batches are needed to achieve $r_{\hat{B}-1}\leq T^{-\frac{1}{d_z+\beta}}$ and $\Delta_{\widetilde{x}^*}\leq (4L+4)T^{-\frac{1}{d_z+\beta}}\leq c\cdot T^{-\frac{1}{d_z+\beta}}$.
\end{proof}

\subsection{Lower bound for uniform search}
Now we derive the theoretical performance of uniform search strategy for pure-exploration Lipschitz bandits. The following theorem provides lower bound of the resulting optimal gap for uniform search. Recall that simple regret upper bound of BLiE is $\mathcal{O}\left(T^{-\frac{1}{d_z+\beta}}\right)$, this result yields that theoretical performance of uniform search is worse than BLiE. Pseudocode of uniform search strategy and proof of Theorem \ref{thm:lower-us} are presented in Appendix \ref{app:us}.

\begin{theorem}\label{thm:lower-us}
For any total budget $T$, dimension $d$ and grid length $r$, there exists an instance with zooming dimension $d_z=0$ such that the uniform exploration strategy returns an arm $\widetilde{x}^*$ with optimal gap $\mathbb{E}\Delta_{\widetilde{x}^*}\geq \frac{1}{2}T^{-\frac{1}{d+\beta}}$.
\end{theorem}

\subsection{Lower bound for random-search-based algorithms}
The following theorem provides lower bound of resulting optimal gap for random search strategy (Algorithm \ref{random-search}).
\begin{algorithm}[htt]
	\caption{Random-Search-Based Algorithm for Lipschitz Bandits}
	\label{random-search}
	\begin{algorithmic}[1]
		\STATE \textbf{Input.} Arm set $\mathcal{X}=[0,1]^d$; total budget $T$; Number of selected arms $N\leq T$.
		\STATE Uniformly select $N$ arms $\mathcal{X}_s=\{x_i\}_{i=1}^N\subseteq\mathcal{X}$.
		\STATE Choose an arm $\widetilde{x}^*\in\mathcal{X}_s$ according to some policy.
		\STATE \textbf{Output} $\widetilde{x}^*$.
	\end{algorithmic}
\end{algorithm}

\begin{theorem}\label{thm:lower-hb}
For any total budget $T$, dimension $d$, zooming dimension $d_z$ and number of selected arms $N$, there exists an instance such that any random-search-based algorithm returns an arm $\widetilde{x}^*$ with optimal gap $\mathbb{E}\Delta_{\widetilde{x}^*}\geq c\cdot T^{-\frac{1}{d-d_z}}$, where $c$ is a constant.
\end{theorem}

Proof of Theorem \ref{thm:lower-hb} is deferred to Appendix \ref{app:lower-hb}. In Section \ref{sec:log} and \ref{sec:loglog}, we show that the simple regret upper bound of BLiE is of order $\mathcal{O}\left(T^{-\frac{1}{d_z+\beta}}\right)$. Therefore, when $d_z$ is sufficiently small such that $d_z\leq\frac{d-\beta}{2}$, BLiE outperforms random-search-based algorithms. Recall the definitions of zooming dimension. Smaller $d_z$ means that the near-optimal region is smaller, and thus the task of finding a sufficient good arm is harder. Consequently, based on concepts from Lipschitz bandits, we show that BLiE outperforms random search when the problem is hard. Note that the above bound is valid for any random-search-based algorithm, thus including Hyperband. In the next subsection,
we further make a comparison of the two algorithms and partially explain the reasons for the superiority of BLiE.

\subsection{Comparison with Hyperband under Lipschitz bandits setting}

\citet{li2017hyperband} parameterize the CDF of $\mu(x)$ as $F(\nu)\simeq(\nu-\mu^*)^\gamma$. Now we calculate $\gamma$ under the Lipschitz bandits setting. For any $r>0$, we let $\nu=\mu^*+r$. Then $F(\nu)=\frac{\mathrm{m}(\{x:\;\mu(x)-\mu^*\leq r\})}{\mathrm{m}([0, 1]^d)}=\mathrm{m}(\{x:\Delta_x\leq r\})$, where $\mathrm{m}(A)$ denotes the  measure of set $A$. From the definition of zooming number, we know the set $\{x:\Delta_x\leq r\}$ is covered by $N_{\frac{r}{8L+8}}\leq(8L+8)^{d_z}C_z\cdot r^{-d_z}$ cubes with edge length $\frac{r}{8L+8}$. If this cover is tight, then we have $\mathrm{m}(\{x:\Delta_x\leq r\})\approx N_{\frac{r}{8L+8}}\cdot \left(\frac{r}{8L+8}\right)^d\approx c\cdot r^{d-d_z}$ and $F(\nu)\approx c\cdot r^{d-d_z}=c\cdot(\nu-\mu^*)^{d-d_z}$, where $c$ is a constant. Thus, we obtain an approximate correspondence $\gamma=d-d_z$. Then Theorem 5 in \citet{li2017hyperband} shows that the output arm of Hyperband satisfies $\Delta_{\widetilde{x}^*}\leq T^{\max\left\{-\frac{1}{d-d_z},-\frac{1}{\beta}\right\}}$.

Indeed, theoretical success of Hyperband heavily relies on hitting a good arm in the random sample procedure of a certain SuccessiveHalving subroutine. When the near-optimal region is small, the simple regret bound of Hyperband may get worse or even break.
As a comparison, BLiE only needs to identify and eliminate the sub-optimal region. Thus theoretically, BLiE outperforms Hyperband at least in the following two aspects: 1. As is shown above, when the zooming dimension is small (or equivalently, the near-optimal region is small), the output optimal gap of BLiE is better than Hyperband; 2. BLiE only needs an upper bound of the volume of the near-optimal region. More specifically, upper bound (\ref{upp-simple}) holds when covering number of near-optimal region $N_r$ is upper bounded by $r^{-d_z}$. As a comparison, Hyperband needs an additional assumption that $F(\nu)\gtrsim(\nu-\mu^*)^\gamma$ to ensure the near optimal-region is not too small.
\section{Additional Related Works}
\label{app:related}

\textbf{Lipschitz Bandits:} The Lipschitz bandit problem was introduced as ``continuum-armed bandits'' \cite{agrawal1995continuum}, where the arm space is a compact interval. For this problem, Kleinberg \cite{kleinberg2005nearly} proved an $\Omega (T^{2/3})$ lower bound and introduced an algorithm that matches this lower bound. Under extra conditions on top of Lipschitzness, regret rate of $\widetilde{\mathcal{O}} (T^{1/2})$ was achieved \cite{auer2007improved, cope2009regret}. For compact doubling metric spaces, the Zooming bandit algorithm \cite{kleinberg2008multi}, the Hierarchical Optimistic Optimization (HOO) algorithm \cite{bubeck2011x}, and the BLiN algorithm \citep{fenglipschitz} were developed. Additionally, some attention has been focused on Lipschitz bandit problems where extra conditions are imposed. To name a few, \citet{bubeck2011lipschitz} study Lipschitz bandits for differentiable rewards, which enables algorithms to run without explicitly knowing the Lipschitz constants. \citet{10.1145/3412815.3416885} studied discretization-based Lipschitz bandit algorithms from a Gaussian process perspective. \citet{magureanu2014lipschitz} derive a new concentration inequality and study discrete Lipschitz bandits. The idea of robust mean estimators \cite{bickel1965some, alon1999space, bubeck2013bandits} was applied to the Lipschitz bandit problem to cope with heavy-tail rewards, leading to the development of a near-optimal algorithm for Lipschitz bandit with heavy-tailed rewards \cite{lu2019optimal}. Lipschitz bandits where a clustering is used to infer the underlying metric, has been studied by \cite{christina2019nonparametric}. Contextual Lipschitz bandits have also been studied \cite{slivkins2011contextual,krishnamurthy2019contextual}.

\textbf{Batched Bandits:} Urged by the recent prevalence of distributed computing, online learning problems with batched feedback has captured increasing attention \citep[e.g.,][]{cesa2013online}. In their seminal work, \citet{perchet2016batched} considered batched bandits with two arms, and provided a lower bound for the static grid.
It was then generalized by \citet{gao2019batched} to finite-armed bandit problems. Soon afterwards, \citet{zhang2020inference} studied inference problems for batched bandits; \citet{esfandiari2021regret} studied batched linear bandits and batched adversarial bandits; \citet{han2020sequential} and \citet{ruan2021linear} provided solutions for batched contextual linear bandits; \citet{li2022gaussian} studied batched bandits from a Bayesian perspective. Batched dueling bandits \cite{agarwal2022batched} and batched Lipschitz bandits \citep{fenglipschitz} have also been studied. Parallel to the regret control regime, best arm identification with limited number of batches was also investigated \citep{agarwal2017learning,jun2016top}. Top-$k$ arm identification in the collaborative learning framework is also closely related to the batched setting, where the goal is to minimize the number of iterations (or communication steps) between agents. In this setting, tight bounds have been obtained recently \citep{tao2019collaborative,karpov2020collaborative}.

\section{Proof of Theorem \ref{thm:blin-upper}}\label{app:thm1}

\textbf{Theorem \ref{thm:blin-upper}.} If Assumption \ref{ass:hoeffding} and \ref{ass:lip} are satisfied, then output arm $\widetilde{x}^*$ of BLiE algorithm with total budget $T$, edge-length sequence $r_m=2^{-m}$, $\alpha=2L+2$ and $\beta$ satisfies
\begin{equation*}
    \Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}},
\end{equation*}
where $d_z$ is the zooming dimension and $c$ is a constant. In addition, BLiE needs no more than $\frac{1}{d_z+\beta}\log T$ batches to achieve this simple regret.

\begin{proof}
In the following analysis, we let $B$ be the total number of batches of the BLiE run ($B-1$ batches in the for-loop and $1$ clean-up batch). In each batch $m$, each cube is assigned with budget $n_m=\frac{1}{r_m^\beta}$. Lemma \ref{lem:eli} implies that each cube in $\mathcal{A}_m$ is a subset of $S((8L+8)r_m)$, so from the definition of zooming number and zooming dimension, we have $|\mathcal{A}_m|\leq N_{r_m}\leq C_z\cdot r_m^{-d_z}$. Therefore, the total budget of batch $m$ is upper bounded by $C_z\cdot r_m^{-(d_z+\beta)}$. Line 7 of Algorithm \ref{BLiN} yields that the sum of budgets of full $B$ batches is greater than $T$, so we have
\begin{align*}
    T\leq\sum_{m=1}^BC_z\cdot r_m^{-(d_z+\beta)}&\leq C_z\cdot\sum_{m=1}^B\left(2^{B-m}\cdot r_B\right)^{-(d_z+\beta)}\\
    &\leq\frac{C_z}{1-2^{-(d_z+\beta)}}r_B^{-(d_z+\beta)},
\end{align*}
where the second inequality follows from $r_m=2^{-m}$, and thus $r_B\leq c_0\cdot T^{-\frac{1}{d_z+\beta}}$, where $c_0=\left(\frac{1-2^{-(d_z+\beta)}}{C_z}\right)^{-\frac{1}{d_z+\beta}}$. Lemma \ref{lem:eli} shows that $\Delta_x\leq(8L+8)r_B$ for any $x\in\cup_{C\in\mathcal{A}_B}C$, so we conclude that $\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}}$, where $c=(8L+8)c_0$. Besides, since $r_B=2^{-B}$, no more than $B^*=\frac{1}{d_z+\beta}\log T-\log c_0$ batches are needed to achieve $r_B<c_0\cdot T^{-\frac{1}{d_z+\beta}}$ and $\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}}$.
\end{proof}

\section{Proof of Lemma \ref{lem:eli}}
\label{app:lem1}

\textbf{Lemma \ref{lem:eli}.} For any $1\leq m\leq B$, any $C\in\mathcal{A}_m$ and any $x\in C$, simple regret of arm $x$ satisfies
\begin{align*}
    \Delta_x\leq(4L+4)r_{m-1}.
\end{align*}

The proof of Lemma \ref{lem:eli} is based on the following two results.

\begin{lemma}\label{lem:concen}
    For any cube $C\in\mathcal{A}_m$, selected arm $x_C$ and any arm $x\in C$,
    \begin{equation*}
        |\ell(x_C,n_m)-\mu(x)|\leq L\cdot r_m + n_m^{-\frac{1}{\beta}}.
    \end{equation*}
\end{lemma}
\begin{proof}
    Fix a cube $C\in\mathcal{A}_m$ and the selected arm $x_C$. Assumption \ref{ass:hoeffding} gives that
    \begin{align*}
        |\ell(x_C, n_m)-\mu(x_C)|\leq n_m^{-\frac{1}{\beta}}.
    \end{align*}
    By Lipschitzness of $\mu$, it is obvious that
    \begin{align*}
        \left|\mu(x_C)-\mu(x)\right|\leq L\cdot r_m, \quad \forall x \in C.
    \end{align*}
    Consequently, we have $|\ell(x_C,n_m)-\mu(x)|\leq L\cdot r_m + n_m^{-\frac{1}{\beta}}$.
\end{proof}

\begin{lemma}\label{nel}
    The optimal arm $x^*=\arg\max\mu(x)$ is not eliminated after the first $B-1$ batches of a BLiE run.
\end{lemma}

\begin{proof}
    We use $C^*_m$ to denote the cube containing $x^*$ in $\A_m$. Here we proof that $C^*_m$ is not eliminated in round $m$.

    For any cube $C \in \A_m$ and $x\in C$, we have
    \begin{align*}
    	\ell(x_C,n_m) - \ell(x_{C^*_m}, n_m)\leq\mu(x) + n_m^{-\frac{1}{\beta}} + L\cdot r_m-\mu(x^*) +  n_m^{-\frac{1}{\beta}} + L\cdot r_m\leq(2L+2)r_m .
    \end{align*}
    Then from the elimination rule, $C^*_m$ is not eliminated.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lem:eli}]
    For $m=1$, the conclusion holds directly from the Lipschitzness of $\mu$. For $m>1$, let $C_{m-1}^*$ be the cube in $\A_{m-1}$ such that $x^* \in C_{m-1}^*$. From Lemma \ref{nel}, this cube $C_{m-1}^*$ is well-defined.
    For any cube $C\in\mathcal{A}_m$ and $x\in C$, it is obvious that $x$ is also in the parent of $C$ (the cube in the previous round that contains $C$), which is denoted by $C_{par}$.
    Thus for any $x \in C$, it holds that
    \begin{align*}
    	\Delta_x=\mu(x)-\mu^*\leq\ell(x_{C_{par}}, n_{m-1})+n_{m-1}^{-\frac{1}{\beta}}+L \cdot r_{m-1}-\ell(x_{C^*_{m-1}}, n_{m-1})+n_{m-1}^{-\frac{1}{\beta}}+L \cdot r_{m-1},
    \end{align*}
	where the inequality uses Lemma \ref{lem:concen}.

    Equality $n_{m-1}=\frac{1}{r_{m-1}^\beta}$ gives that
    \begin{align*}
        \Delta_x
        &\le\ell(x_{C_{par}}, n_{m-1})-\ell(x_{C^*_{m-1}}, n_{m-1})+(2L+2)r_{m-1}.
    \end{align*}
    It is obvious that $\ell(x_{C^*_{m-1}}, n_{m-1})\geq\ell_{m-1}^{\min}$. Moreover, since the cube $C_{par}$ is not eliminated, from the elimination rule we have

    \begin{align*}
        \ell(x_{C_{par}}, n_{m-1})-\ell_{m-1}^{\min}\le (2L+2)r_{m-1}.
    \end{align*}
    Hence, we conclude that $\Delta_x\leq(4L+4)r_{m-1}$.
\end{proof}

\section{Definition \ref{def:ace} and Theorem \ref{thm:ace} without decreasing assumption}\label{app:race}

\textbf{Defnintion \ref{def:ace}.} For a problem with ambient dimension $d$, zooming dimension $d_z$ and time horizon $T$, we denote $c_1=\frac{d_z+\beta-1}{(d_z+\beta)(d+\beta)}\log T$ and $c_{i+1} = {\eta c_i }$ for any $i\ge 1$, where $\eta=\frac{d+1-d_z}{d+\beta}$. Then we let $\alpha_n=\lfloor\sum_{i=1}^nc_i\rfloor$, $\beta_n=\lceil\sum_{i=1}^nc_i\rceil$, and inductively define ACE Sequence $\{r_m\}_{m\in\mathbb{N}}$ as $r_m=\min\{r_{m-1}, 2^{-\alpha_k}\}$ for $m=2k-1$ and $r_m=2^{-\beta_k}$ for $m=2k$. Since every $c_i$ is positive, it is easy to see $\{r_m\}$ is a decreasing sequence. If there exists $m$ such that $r_m=r_{m-1}$, then we skip the $m$-th batch when using ACE Sequence in BLiE.

\textbf{Theorem \ref{thm:ace}.} If Assumption \ref{ass:hoeffding} and \ref{ass:lip} are satisfied, then output arm $\widetilde{x}^*$ of BLiE algorithm with total budget $T$, ACE Sequence $\{r_m\}$, $\alpha=2L+2$ and $\beta$ satisfies $$\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}},$$
where $d_z$ is the zooming dimension and $c$ is a constant. In addition, BLiE needs $\mathcal{O}(\log\log T)$ batches to achieve this simple regret.

\begin{proof}
We let $B$ be the total number of batches of the BLiE run ($B-1$ batches in the for-loop and $1$ clean-up batch), and $N_m$ be the total budget of batch $m$. In the following analysis, we bound $N_m$ for $m=2k-1$ and $m=2k$ separately, and then obtain the simple regret upper bound. For $m$ such that $r_m=r_{m-1}$, we skip batch $m$ and define $N_m=0$. Then the following bounds are still hold. Thus, without loss of generality, we assume $r_m<r_{m-1}$.

Firstly, we consider the case $m=2k-1$. Recall that $r_m=\min\{r_{m-1}, 2^{-\alpha_k}\}$, so $r_m<r_{m-1}$ yields that $r_m=2^{-\alpha_k}$. For convenience, we let $\widetilde{r}_k=2^{-\sum_{i=1}^kc_i}$, and thus we have $\widetilde{r}_{k-1}\geq r_{m-1}\geq r_m\geq \widetilde{r}_{k}$. Recall that $\mathcal{A}_{m-1}^+$ is set of cubes not eliminated in batch $m-1$, and $\cup_{C\in\mathcal{A}_{m-1}^+}C=\cup_{C^\prime\in\mathcal{A}_m}C^\prime$. Lemma \ref{lem:eli} implies that each cube in $\mathcal{A}_{m-1}^+$ is a subset of $S((4L+4)r_{m-1})$, and thus $\left|\mathcal{A}_{m-1}^+\right|\leq N_{r_{m-1}}\leq C_z\cdot r_{m-1}^{-d_z}$. The total budget of batch $m$ is
\begin{align*}
    N_m=|\mathcal{A}_m|\cdot n_m = \left(\frac{r_{m-1}}{r_m}\right)^d\left|\mathcal{A}_{m-1}^+\right|\cdot n_m
    \leq C_z\cdot\frac{r_{m-1}^{d+1-d_z}\cdot r_m^{-d-\beta}}{r_{m-1}}
    \leq C_z\cdot\frac{\widetilde{r}_{k-1}^{d+1-d_z}\cdot\widetilde{r}_k^{-d-\beta}}{r_{m-1}}.
\end{align*}
For the numerator, we have
\begin{align*}
    \widetilde{r}_{k-1}^{d+1-d_z}\cdot\widetilde{r}_k^{-d-\beta}=2^{-\left(\sum_{i=1}^{k-1}c_i\right)(d+1-d_z)+\left(\sum_{i=1}^{k}c_i\right)(d+\beta)}=2^{\left(\sum_{i=1}^{k-1}c_i\right)(d_z+\beta-1)+c_m(d+\beta)}.
\end{align*}
Define $C_m=\left(\sum_{i=1}^{k-1}c_i\right)(d_z+\beta-1)+c_m(d+\beta)$. Since $c_m=c_{m-1}\cdot\frac{d+1-d_z}{d+\beta}$, calculation shows that $C_m = (\sum_{i=1}^{m-2} c_i) (d_z+\beta-1)  + c_{m-1}(d+\beta)+ c_{m-1}(d_z+\beta-1-d-\beta)+c_m(d+\beta)=C_{m-1}$. Thus for any $m$, we have $C_M=C_1=\frac{d_z+\beta-1}{d_z+\beta}\log T$. Hence,
\begin{equation*}
    N_m\leq C_z\cdot2^{\frac{d_z+\beta-1}{d_z+\beta}\log T}/r_{m-1}=C_z\cdot T^{\frac{d_z+\beta-1}{d_z+\beta}}/r_{m-1}.
\end{equation*}

Secondly, we consider the case $m=2k$. Recall that $r_{m-1}=\min\{r_{m-2}, 2^{-\alpha_k}\}$. It is easy to verify that $r_{m-2}<2^{-\alpha_k}$ only happens when $r_{m-2}=r_{m}$, so $r_m<r_{m-1}$ yields that $r_{m-1}=2^{-\alpha_k}$. Lemma \ref{lem:eli} implies that each cube in $\mathcal{A}_m$ is a subset of $S(8L+8)r_m$. Similar argument to the first case shows that $\left|\mathcal{A}_m\right|\leq C_z\cdot r_m^{-d_z}$ and $N_m\leq C_z\cdot r_m^{-(d_z+\beta)}$.

Line 7 of Algorithm \ref{BLiN} ensures that the sum of budgets of full $B$ batches is greater than $T$. Therefore, combining the above two cases, we have
\begin{align}\label{app-ace1}
    T\leq&\sum_{\substack{m=2k-1, \\ m\leq B }}C_z \cdot\frac{T^{\frac{d_z+\beta-1}{d_z+\beta}}}{r_{m-1}}+\sum_{\substack{m=2k,\\mathrm{m}\leq B}}C_z\cdot \frac{1}{r_m^{d_z+\beta}}.
\end{align}

The rounding step in Definition \ref{def:ace} yields that $r_m\leq\frac{r_{m-1}}{2}$ for any $m$. If $B$ is odd, from (\ref{app-ace1}) we have
\begin{equation}\label{app-ace2}
    T\leq2C_z\cdot T^{\frac{d_z+\beta-1}{d_z+\beta}}\cdot\frac{1}{r_{B-1}}+2C_z\cdot\frac{1}{r_{B-1}^{d_z+\beta}}.
\end{equation}

We set $c_r=\max\{(4C_z)^\frac{1}{d_z+\beta}, 4C_z\}$, then $\frac{1}{c_r^{d_z+\beta}}+\frac{1}{c_r}\leq\frac{1}{2C_z}$. If $r_{B-1}>c_r\cdot T^{-\frac{1}{d_z+\beta}}$, then calculation shows that
\begin{align*}
    2C_z\cdot T^{\frac{d_z+\beta-1}{d_z+\beta}}\cdot\frac{1}{r_{B-1}}+2C_z\cdot\frac{1}{r_{B-1}^{d_z+\beta}}<T,
\end{align*}
which contradicts (\ref{app-ace2}). Therefore, we have $r_{B-1}\leq c_r\cdot T^{-\frac{1}{d_z+\beta}}$. Lemma \ref{lem:eli} shows that $\Delta_x\leq(4L+4)r_{B-1}$ for any $x\in\cup_{C\in\mathcal{A}_B}C$, so we have $\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}}$, where $c=(8L+8)\cdot\max\{c_r, 1\}$.

If $B$ is even, from (\ref{app-ace1}) we have
\begin{equation*}
    T\leq2C_z\cdot T^{\frac{d_z+\beta-1}{d_z+\beta}}\cdot\frac{1}{r_{B}}+2C_z\cdot\frac{1}{r_{B}^{d_z+\beta}}.
\end{equation*}
Similar arguments yield that $r_B\leq c_r\cdot T^{-\frac{1}{d_z+\beta}}$. Lemma \ref{lem:eli} shows that $\Delta_x\leq(4L+4)r_{B-1}$ for any $x\in\cup_{C\in\mathcal{A}_B}C$. Moreover, since $B$ is even, from definition of ACE Sequence we have $r_{B-1}\leq2r_B$. Consequently, in this case we also have $\Delta_{\widetilde{x}^*}\leq c\cdot T^{-\frac{1}{d_z+\beta}}$.

Finally, we consider the communication bound. For any $B^*$, $\widetilde{r}_{B^*}=2^{-\sum_{i=1}^{B^*}c_i}=2^{-c_1\cdot\frac{1-\eta^{B^*}}{1-\eta}}=T^{-\frac{1}{d_z+\beta}}\cdot T^{\frac{\eta^{B^*}}{d_z+\beta}}$. Then by choosing $B^*\geq\frac{\log\log T-\log(d_z+\beta)}{\log\frac{d+\beta}{d+1-d_z}}$, we have $\frac{\eta^{B^*}}{d_z+\beta}\leq\log T$ and $\widetilde{r}_{B^*}\leq T^{-\frac{1}{d_z+\beta}}$. Definition \ref{def:ace} shows that $r_m<\widetilde{r}_{B^*}$ for any $m\geq2B^*$. As a consequence, no more than $\hat{B}=\frac{2\log\log T}{\log\frac{d+\beta}{d+1-d_z}} + 1$ batches are needed to achieve $r_{\hat{B}-1}\leq T^{-\frac{1}{d_z+\beta}}$
and
\begin{equation*}
    \Delta_{\widetilde{x}^*}\leq(4L+4)r_{\hat{B}-1}\leq(4L+4)T^{-\frac{1}{d_z+\beta}}\leq c\cdot T^{-\frac{1}{d_z+\beta}},
\end{equation*}
where the first inequality follows from Lemma \ref{lem:eli}.
\end{proof}

\section{Proof of Theorem \ref{thm:lower-us}}\label{app:us}
Pseudo code of uniform search is presented below.

\begin{algorithm}[H]
	\caption{Uniform search for Lipschitz bandits}
	\label{uni-exploration}
	\begin{algorithmic}[1]
		\STATE \textbf{Input.} Arm set $\mathcal{X}=[0,1]^d$; total budget $T$; grid length $r$; $n = Tr^d$.
		\STATE Equally partition $\mathcal{X}$ to $N=\frac{1}{r^d}$ subcubes and define $\mathcal{A}$ as the collection of these subcubes.
		\FOR{$C\in\A$}
		    \STATE Uniformly choose an arm $x_C\in C$.
		    \STATE Evaluate arm $x_C$ with budget $n$. Recive the loss $\ell(x_C, n)$.
		\ENDFOR
		\STATE Compute $C^*=\mathop{\arg\min}_{C\in\A}\ell(x_C, n)$.\label{ue:opt-cube}
		\STATE \textbf{Output} $\widetilde{x}^*=x_{C^*}$.
	\end{algorithmic}
\end{algorithm}

\textbf{Theorem \ref{thm:lower-us}.} For any total budget $T$, dimension $d$ and grid length $r$, there exists an instance with zooming dimension $d_z=0$ such that the uniform exploration strategy returns an arm $\widetilde{x}^*$ with optimal gap $\mathbb{E}\Delta_{\widetilde{x}^*}\geq \frac{1}{2}T^{-\frac{1}{d+\beta}}$.

\begin{proof}
We construct a problem instance such that $\mathcal{X}=[0,1]^d$ and $\mu(x)=f(\|x\|_\infty)\triangleq C+\|x\|_\infty$ for some constant $C>0$. For this instance, we have $x^*=0$ and $\Delta_x=\mu(x)-\mu(x^*)=\|x\|_\infty$. This instance satisfies Assumption \ref{ass:lip} with $L=1$. Similar arguments to the example in Section \ref{sec:zooming} yields that the zooming dimension of this instance equals to $0$, with zooming constant $C_z=16^d$.

After given edge length $r$, $\mathcal{X}$ is equally partitioned into $N=\frac{1}{r^d}$ cubes $C_1\cdots C_N$. Additionally, we define the marginal grid point $g_i=\frac{i}{N}$. In the following analysis, we consider the situations where $r\geq T^{-\frac{1}{d+\beta}}$ and $r<T^{-\frac{1}{d+\beta}}$ separately.

If $r\geq T^{-\frac{1}{d+\beta}}$, we define $\ell(x,n)=\mu(x)$ for any $x$ and $n$. For this instance, it is easy to see that the optimal cube $C^*$ in Line \ref{ue:opt-cube} is $C_1=[0,g_1]^d$. Therefore, the output arm is uniformly selected from $C_1$, and
\begin{equation}\label{ue:lower-bound1}
    \mathbb{E} \Delta_{\widetilde{x}^*}=\mathbb{E}_{x\sim \mathrm{Unif}(C_1)}\Delta_x>\frac{r}{2}\geq\frac{1}{2}T^{-\frac{1}{d+\beta}}.
\end{equation}
If $r<T^{-\frac{1}{d+\beta}}$, then each cube is played for $n=Tr^d<T^{\frac{\beta}{d+\beta}}$ times. Since the edge length $g_i-g_{i-1}$ equals to $r$ for each $i$, there exists an integer $0<k_0\leq N$ such that $\frac{1}{2}T^{-\frac{1}{d+\beta}}\leq f(g_{k_0})-\mu(x^*)\leq T^{-\frac{1}{d+\beta}}$. We set $\mathcal{A}_1=\{C_i:\;1\leq i\leq N,\;C_i\subset[0, g_{k_0}]^d\} $ and $\mathcal{A}_2=\{C_i:\;1\leq i\leq N,\;C_i\not\subset[0, g_{k_0}]^d\} $ and then define $\ell(x,n)=\mu(x)+n^{-\frac{1}{\beta}}$ for $x\in\cup_{C\in\mathcal{A}_1}C$, and $\ell(x,n)=\mu(x)-n^{-\frac{1}{\beta}}$ for $x\in\cup_{C\in\mathcal{A}_2}C$.

Since $n<T^{\frac{\beta}{d+\beta}}$, for any $x\in\cup_{C\in\mathcal{A}_1}C$, we have
\begin{equation}\label{error:first-grid}
    \ell(x,n)=\mu(x)+n^{-\frac{1}{\beta}}>\mu(x^*)+\left(T^{\frac{\beta}{d+\beta}}\right)^{-\frac{1}{\beta}}=C+T^{-\frac{1}{d+\beta}}.
\end{equation}
Since $f(g_{k_0})-\mu(x^*)\leq T^{-\frac{1}{d+\beta}}$ and $r<T^{-\frac{1}{d+\beta}}$, we have $f(g_{k_0+1})=f(g_{k_0})+r\leq \mu(x^*)+2T^{-\frac{1}{d+\beta}}$. Therefore, for any $x\in [g_{k_0},g_{k_0+1}]^d$,
\begin{align}\label{err:second-grid}
        \ell(x,n)&=\mu(x)-n^{-\frac{1}{\beta}}<f(g_{k_0+1})-\left(T^{\frac{\beta}{d+\beta}}\right)^{-\frac{1}{\beta}}\leq C+2T^{-\frac{1}{d+\beta}}-T^{-\frac{1}{d+\beta}}=C+T^{-\frac{1}{d+\beta}}.
\end{align}
Combining (\ref{error:first-grid}) and (\ref{err:second-grid}), we show that the loss $\ell(x,n)$ for $x\in\cup_{C\in\mathcal{A}_1}C$ is sub-optimal, and the optimal cube $C^*$ in Line 7 belongs to $\mathcal{A}_2$. From the definition of the instance, for any $x\in\cup_{C\in\mathcal{A}_2}C$, the optimal gap $\Delta_x\geq f(g_{k_0})-\mu(x^*)\geq\frac{1}{2}T^{-\frac{1}{d+\beta}}$. As a consequence, we have
\begin{equation}\label{ue:lower-bound2}
    \mathbb{E}\Delta_{\widetilde{x}^*}\geq\frac{1}{2}T^{-\frac{1}{d+\beta}}.
\end{equation}

Finally, combining (\ref{ue:lower-bound1}) and (\ref{ue:lower-bound2}), we arrive at the conclusion of the theorem.
\end{proof}

\section{Proof of Theorem \ref{thm:lower-hb}}\label{app:lower-hb}

\textbf{Theorem \ref{thm:lower-hb}.} For any time horizon $T$, dimension $d$, zooming dimension $d_z$ and number of selected arms $N$, there exists an instance such that any random-search-based algorithm returns an arm $\widetilde{x}^*$ with optimal gap $\mathbb{E}\Delta_{\widetilde{x}^*}\geq c\cdot T^{-\frac{1}{d-d_z}}$, where $c$ is a constant.

\begin{proof}
We consider an instance with ambient dimension $d$ and zooming dimension $d_z$. Let $x_r$ be a uniformly chosen arm and $\mu_r=\mu(x_r)$. Then we have $\Pr(\mu_r<\mu^*+\varepsilon)=\mathrm{m}(\{x:\mu(x)-\mu^*<\varepsilon\})=\mathrm{m}(S(\varepsilon))$. From the definition of zooming dimension, $S(\varepsilon)$ is covered by $C_z\cdot\left(\frac{\varepsilon}{8L+8}\right)^{-d_z}$ cubes with volume $\left(\frac{\varepsilon}{8L+8}\right)^d$, so the measure is bounded by $\mathrm{m}(S(\varepsilon))\leq C_z\cdot\left(\frac{\varepsilon}{8L+8}\right)^{d-d_z}$. Therefore, we have
\begin{equation}\label{opt-region-bound}
    \Pr(\mu_r<\mu^*-\varepsilon)\leq C_z\cdot\left(\frac{\varepsilon}{8L+8}\right)^{d-d_z}.
\end{equation}
The following analysis is similar to the lower bound proof in \citet{carpentier2015simple}. We set $\varepsilon=c_0\cdot T^{-\frac{1}{d-d_z}}$, where $c_0=\frac{8L+8}{C_z^\frac{1}{d-d_z}}$, and (\ref{opt-region-bound}) gives that $\Pr\left(\mu_r<\mu^*-c_0\cdot T^{-\frac{1}{d-d_z}}\right)\leq\frac{1}{T}$. Then for the $N$ different arms selected in Algorithm \ref{random-search}, we have
\begin{align*}
    \Pr\left(\mu(x_i)\geq\mu^*+c_0\cdot T^{-\frac{1}{d-d_z}},\;\forall\;1\leq i\leq N\right)\geq\left(1-\frac{1}{T}\right)^N\geq\left(1-\frac{1}{T}\right)^T\geq\frac{1}{4}.
\end{align*}
As a consequence, with probability more than $\frac{1}{4}$, all selected arms have optimal gap larger than $c_0\cdot T^{-\frac{1}{d-d_z}}$, and therefore, with probability larger than $\frac{1}{4}$, the output optimal gap of random search is lower bounded by $c_0\cdot T^{-\frac{1}{d-d_z}}$. Consequently, we have $\mathbb{E}\Delta_{\widetilde{x}^*}\geq\frac{1}{4}c_0\cdot T^{-\frac{1}{d-d_z}}$.
\end{proof}

\section{More samples generated using different schedules and diffusion steps}
\begin{figure}[ht]
	\centering
	\subfigure[BLiE Result, $T=100$]{
		\includegraphics[width=6.5cm]{./figures/hp100_full.png}
	}\hspace{+10mm}
	\subfigure[Linear, $T=100$]{
		\includegraphics[width=6.5cm]{./figures/linear100_full.png}
	}\\
	\subfigure[BLiE Result, $T=200$]{
		\includegraphics[width=6.5cm]{./figures/hp200_full.png}
	}\hspace{+10mm}
	\subfigure[Linear, $T=200$]{
		\includegraphics[width=6.5cm]{./figures/linear200_full.png}
	}\\
	\subfigure[BLiE Result, $T=1000$]{
		\includegraphics[width=6.5cm]{./figures/hp1000_full.png}
	}\hspace{+10mm}
	\subfigure[Linear, $T=1000$]{
		\includegraphics[width=6.5cm]{./figures/linear1000_full.png}
	}
    \caption{MNIST samples generated using different noise schedules and diffusion steps.}
\end{figure}
\section{Experiments}

This section provides empirical comparison of BLiE with existing HPO methods including Hyperband (HB), SuccessiveHalving (SH), Random Search (RS) and Tree-structured Parzen Estimator (TPE). The results demonstrate the superior performance of BLiE. Also, we apply BLiE to noise scheduling task of diffusion models. Compared with the standard linear schedule, BLiE schedule only needs very few diffusion steps, and thus greatly improves the sampling speed. Results of toy example are averaged over $256$ runs, and results in Section \ref{sec:exp1} and \ref{sec:exp2} are averaged over $32$ runs.

\subsection{Toy example}

In this experiment, we investigate the performance of BLiE in a high-dimensional toy example. We also run Hyperband (HB) as a comparison. The arm space is $\mathcal{X}=[0, 1]^8$. In order to compare the two algorithms under different $d_z$, we consider two different limit loss functions. Given an arm $x\in\mathcal{X}$, we define $\mu_1(x)=\|x\|_\infty$ ($d_z=0$) and $\mu_2(x)=\|x\|_\infty^{1.5}$ ($d_z=8/3$). For any limit loss $\mu$, assign $1$ budget to arm $x$ corresponds to sample a Gaussian random variable $Y_{x,i}$ with mean equals to $\mu(x)$, and $\ell(x,n)=\frac{\sum_{i=1}^nY_{x, i}}{n}$. Consequently, Assumption \ref{ass:lip} is satisfied with $L=1$, and Assumption \ref{ass:hoeffding} is asymptotically satisfied with $\beta=2$.

We run BLiE and HB with total budget $T=2^{28}$, and report the simple regret $\Delta_{\widetilde{x}^*}=\mu(\widetilde{x}^*)-\mu(x^*)$ in Figure \ref{fig:toy}.
We have two observations from Figure \ref{fig:toy}. Firstly, for both limit losses, the simple regrets of BLiE (red and light blue lines) are smaller than HB (orange and dark blue lines). Secondly, final performance of BLiE on $\mu_1$ (light blue line) is better than $\mu_2$ (red line), while performance of HB on $\mu_2$ (dark blue line) is better than $\mu_1$ (orange line). Recall that Theorem \ref{thm:blin-upper} shows that the simple regret upper bound of BLiE is $\mathcal{O}\left(T^{-\frac{1}{d_z+\beta}}\right)$, and indicates that BLiE performs better for smaller $d_z$. As a comparison, Theorem \ref{thm:lower-hb} shows that the simple regret lower bound of HB is $\mathcal{O}\left(T^{-\frac{1}{d-d_z}}\right)$, and indicates that HB performs worse for smaller $d_z$. In this experiment, $d_z=0$ for $\mu_1$ and $d_z=8/3$ for $\mu_2$. The above observations coincide with theoretical results, and demonstrate that our bounds of simple regrets are tight.

\begin{figure*}[ht]
    \centering
	\subfigure[Toy Example]{
        \includegraphics[width=5cm]{figures/toy_comparison_var.png}
		\label{fig:toy}
	}
	\subfigure[MNIST]{
		\includegraphics[width=5cm]{./figures/MNIST_adam.png}
		\label{fig:mnist}
	}
	\subfigure[CIFAR-10]{
		\includegraphics[width=5cm]{./figures/CIFAR10_adam.png}
		\label{fig:cifar}
	}
    \caption{HPO processes for different tasks. Figure \ref{fig:toy} shows results of toy example with different limit losses. Figure \ref{fig:mnist} and \ref{fig:cifar} show results of tuning optimizer for neural-network classifiers on MNIST and CIFAR-10.}
    \label{fig:adam}
\end{figure*}

\subsection{Tuning optimizer for neural networks}\label{sec:exp1}
In this experiment, we apply BLiE to tune the Adam Optimizer \citep{kingma2014adam} for two classification tasks. The hyperparameter set consists of learning rate $lr$, weights $\beta_1$ and $\beta_2$. We take experiments on two datasets: MNIST and CIFAR-10. For MNIST, one unit of resource corresponds to one mini-batch iteration. For CIFAR-10, one unit of resource corresponds to $60$ mini-batch training. For all experiments in Section \ref{sec:exp1} and Section \ref{sec:exp2}, we set the parameters of BLiE as $\alpha = 0.01$ and $\beta=2.5$.

For the model architecture, we use a two-layer CNN in the MNIST task, and Resnet18 \citep{he2016deep} in the CIFAR-10 task. We choose relatively simple models because our purpose is to compare the performance of HPO algorithms rather than obtain state-of-the-art accuracy, and this can save computational resources. We run BLiE, HB, SH, RS and TPE with total budget $12000$, and report the results in Figure \ref{fig:adam}. The results show that BLiE can not only find good hyperparameters faster, but also output better solutions at the end. We use the found hyperparameters to train both models, and report the final test accuracy in Table \ref{tab:accuracy}. This result shows that the model trained with hyperparameters output by BLiE has the best accuracy.

\begin{table*}[ht]
    \centering
    \caption{Test accuracy of classification tasks. The models are trained with hyperparameters output by the five methods.}
    \begin{tabular}{ccccccc}
         \toprule
         \multicolumn{2}{c}{method} & BLiE & HB & SH & RS & TPE\\
         \midrule
         \multirow{2}*{Accuracy (std)} & MNIST & \textbf{96.27} (0.41) & 95.34 (0.55) & 95.72 (0.68) & 95.22 (0.53) & 94.84 (0.63)\\
         \cmidrule{2-7}
          & CIFAR-10 & \textbf{91.19} (0.11) & 87.65 (2.96) & 88.29 (2.70) & 87.17 (2.56) & 90.40 (0.19)\\
         \bottomrule
    \end{tabular}
    \label{tab:accuracy}
\end{table*}
\section{Introduction}

A Multi-Armed Bandit (MAB) algorithm seeks to balance off the tension between exploring the decision space and exploiting the good options. Roughly speaking, these algorithms try to make few mistakes while searching for the optimal decision. Due to this characteristic, MAB algorithms are often used in environments where trying an action is not cheap \citep[e.g.,][]{}. When exploitation is not as important as exploration, the MAB problem becomes the \emph{pure exploration problem} or the Best Arm Identification (BAI) problem, where the task
is finding the best arm efficiently. MAB and BAI problems have attracted tremendous amount of attention in recent years. Among the uncountably many variations of the classic MAB model \citep{}, bandit learning with \emph{batched feedback} forms an important line of works \citep{}. In bandit problems with batched feedback, the learning agent does not immediately observe reward after pulling arms. Instead, they collect the reward observations every several arm pulls. Effectively, the batched feedback setting allows the learning agent to ``parallelize'' arm pulling: They can pull several arms in parallel, and collect the rewards all together. The authors recommend \citep{} for general exposition on MAB problems.

HyperParameter Optimization (HPO) problems become increasingly important in recent years, urged by increasing size of deep learning models \citep[e.g.,][]{}. HPO problems often carry structures that are not common in bandit problems. For example, in HPO usually a budget is associated to training a hyperparameter configuration. This budget models training resource consumption (e.g., number of training iterations etc). Usually allocating more budget to one hyperparameter means that more accurate learning output are observed \citep{}. Such structures make HPO problems theoretically intriguing and practically important. HPO problems naturally use many bandit learning principles. Since tuning hyperparameters are often not cheap, bandit learning principles can aid HPO tasks by minimizing number of trials. When applying bandit learning principles to HPO, one models the hyperparameter configurations as arms, and the learning output (e.g, testing accuracy/validation accuracy) as rewards. With this correspondence, the HPO task can be modeled as a bandit learning process: One selects some hyperparameter configurations to train models, collect learning output of these hyperparameter configurations, and repeat this procedure until the total training budget runs out.

Lipschitzness indeed models the behavior of many hyperparameters, of which the learning rate is an important example. Practitioners often find learning rate to be one of the most important hyperparameter to training a good model. Since the learning output does not always increase/decrease with learning rate, parameters like learning rate may not be simply modeled by a linear or polynomial model. For such hyperparameters, Lipschitz bandit models are natural choice. \textcolor{red}{(name a few other examples, e.g., some hyperparameters for Adam, etc. )}

The batched feedback setting also comes in handy for HPO problems. For HPO problems, it is desirable to train several different hyperparameter configurations in parallel. In standard bandit learning settings, the agent usually needs to observe the reward immediately after arm pulling, so that subsequent decisions can be made. In batched feedback setting, one only needs to collect rewards every several arm pulls. Effectively, algorithms for the batched feedback setting allows one to train several hyperparameter configurations in parallel. Compared to the standard sequential decision making setting, this batched feedback setting can significantly improve HPO efficiency.

In this paper, we study pure exploration for Lipschitz bandits with batched feedback, and apply such algorithms to HPO problems. We investigate the \emph{Batched Lipschitz Narrowing} (BLiN) algorithm \citep{} in a setting with training budget constraints, and study its behavior for pure exploration tasks. The BLiN algorithm collects rewards every several arm pulls, and adaptively eliminates regions of low rewards. \textcolor{red}{(describe the algorithm with budget constraints)}.

Performance of the BLiN algorithm for pure exploration tasks is measured by \emph{simple regret}. Simple regret is the gap between the optimal arm and the best arm output by BLiN (within a fixed total budget). The \emph{simple regret} of the BLiN algorithm is controlled by a quantity describing the landscape of the learning output function, called \emph{zooming dimension} \citep{}. Lower zooming dimension means smaller simple regret and thus faster identification of good hyperparameter configurations. For HPO tasks, higher correlation in the hyperparameters implies lower zooming dimension. Usually, the hyperparameters are highly correlated, and thus BLiN naturally efficiently identify good hyperparameter configurations. In fact, we have observed that BLiN can automatically find patterns in hyperparameter configurations. \textcolor{red}{(briefly describe the main theorems, new findings on hyperparameter choice, and summarize the empirical observations)}

The rest of the paper is organized as follows \textcolor{red}{......}

\section{Related Works}

\section{Problem Formulation: Pure Exploration Lipschitz Bandits with Batched Feedback}

For continuous HPO tasks, the candidate hyperparameters are gathered into a compact subset of $\mathbb{R}^d$. When modeling HPO as pure exploration bandit problem, the arm set $\mathcal{X}\in\mathbb{R}^d$ corresponds to the set of hyperparameter configurations, and pulling an arm corresponds to training the model.

Assigning arm $x\in\mathcal{X}$ with budget $n$ means training the model with $n$ units of resources (e.g., iterations), after which we receive a loss $\ell(x,n)$.
Similar to existing bandit-modeling of HPO \citep[e.g.,][]{jamieson2016non, li2017hyperband}, we assume that for any $x$ there exists a \emph{limit loss} $\mu(x)=\lim_{n\to\infty}\ell(x,n)$ and we define the optimal limiting loss as $\mu^*=\min_{x\in\mathcal{X}}\mu(x)$. We also make the following assumption.
\begin{assumption}\label{ass:hoeffding}
For any $x\in\mathcal{X}$ and $n \in \mathbb{N}_+$, the error sequence $\{\ell(x,n)\}_{n=1}^\infty$ is bounded by $|\ell(x,n)-\mu(x)|\leq n^{-\frac{1}{\beta}}$, for some $\beta>0$.
\end{assumption}
Assumption \ref{ass:hoeffding} assumes a power-law decay of the gap between $\ell (x,n)$ and $\mu (x)$. This assumption resonates with the convergence rate of most gradient-based training algorithms. The goal of a pure-exploration bandit algorithm is to output an arm $\widetilde{x}^*$ with as small optimal gap $\Delta_{\widetilde{x}^*}:=\mu(\widetilde{x}^*)-\mu^*$ as possible. A general form of pure exploration bandits is in Algorithm \ref{alg:gen}.

\begin{algorithm}[htb]
	\caption{Pure Exploration Bandits}
	\label{alg:gen}
	\begin{algorithmic}[1]
		\STATE \textbf{Input.} Arm set $\mathcal{X}$; total budget $T$.
		\WHILE{remaining budget $T>0$}
		    \STATE Algorithm chooses arm $x$ and budget $n$.
		    \STATE Assign arm $x$ with budget $n$, and receive $\ell(x, n)$.
		\ENDWHILE
	\STATE Output an arm $\widetilde{x}^*$.
	\end{algorithmic}
\end{algorithm}

\subsection{Lipschitz Bandits Model}
Now we expound our Lipschitz bandits setting. We would like to take advantage of the continuity of the objective function, as shown in Figure \ref{f:visual}. Also, we do not want to introduce parametric models. Therefore, we make the following assumption.

\begin{assumption}\label{ass:lip}
The limiting loss $\mu(x)$ is $L$-Lipschitz with respect to the metric on $\mathcal{X}$, that is, $|\mu(x_1)-\mu(x_2)|\leq L\cdot\|x_1-x_2\|$, for any $x_1,\;x_2\in\mathcal{X}$.
\end{assumption}

As discussed in the introduction and above, this assumption can capture the behavior of many important hyperparameters. Before moving on to the next part, we put forward the following conventions.
\begin{remark}
    \label{rem:doubling}
    As a convention, we focus on the metric space $ ([0,1]^d, \| \cdot \|_\infty) $.
\end{remark}
Note that the restriction in Remark \ref{rem:doubling} does not sacrifice generality. By the Assouad's embedding theorem \citep{assouad1983plongements}, the (compact) doubling metric space $ \mathcal{X} $ can be embedded into a Euclidean space with some distortion of the metric; See \citep{pmlr-v119-wang20q} for more discussions in a machine learning context. Due to existence of such embedding, the metric space $ ([0,1]^d, \| \cdot \|_{\infty})  $, where metric balls are hypercubes, is sufficient for the purpose of our paper. For the rest of the paper, we will use hypercubes in algorithm design for simplicity, while our algorithmic idea generalizes to other doubling metric spaces.

\subsection{Zooming Numbers and Zooming Dimensions}\label{sec:zooming}

An important concept for bandit problems in metric spaces is the zooming number and the  zooming dimension \citep{kleinberg2008multi, bubeck2008tree, slivkins2011contextual}. This concept provides important tools for our theoretical analysis, and we discuss it below.

Define the set of $r$-optimal arms as $ S (r) = \{ x \in \mathcal{X} : \Delta_x \le r \} $. For any $r=2^{-i}$, the decision space $[0,1]^d$ can be equally divided into $2^{di}$ cubes with edge length $r$, which we call \textit{standard cubes} (also referred to as dyadic cubes).
The $r$-zooming number is defined as
\begin{align*}
    N_r := \#\{C: \text{$C$ is a standard cube with edge length $r$} \text{and $C\subset S((8L+8)r)$}\} .
\end{align*}
In words, $N_r$ is the $r$-packing number of the set $S((8L+8)r)$ in terms of standard cubes.
The zooming dimension is then defined as
    $d_z := \min \{  d\geq0: \exists a>0,\;N_r \le ar^{-d},\;
    \forall r=2^{-i} \text{ for $i \in \mathbb{N}$}\}. $

Moreover, we define the zooming constant $C_z$ as the minimal $a$ to make the above inequality true for $d_z$, $C_z=\min\{  a>0:\;N_r \le ar^{-d_z},\;\forall r=2^{-i} \text{ for $i \in \mathbb{N}$} \}$.

It is obvious that $d_z$ is upper bounded by ambient dimension $d$. In fact, zooming dimension $d_z$ can be significantly smaller than $d$ and can be zero. For a simple example, consider a problem with ambient dimension $d=1$ and expected reward function $\mu(x)=x$ for $0\leq x\leq1$, which satisfies Assumption \ref{ass:lip} with $L=1$. Then for any $r=2^{-i}$ with $i\geq4$, we have $S(16r)=[1-16r,1]$ and $N_r=16$. Therefore, for this problem the zooming dimension equals to $0$, with zooming constant $C_z=16$.

\subsection{Bandit Problems with Batched Feedback}

The batched bandit problem is a trending topic in MAB problems (See Appendix \ref{app:related}).
In such problems, the observed losses are communicated to the agent in batches, and the decisions made by the algorithm depend only on information up to the previous batch. Algorithms with good performance for batched bandits also have advantages in HPO problems.
Since the policy  does not depend on observations from the same batch, hyperparameter configurations belonging to the same batch can be trained in parallel.

In the bandit language, this feedback collecting scheme is called bandit with batched feedback. Here we define the batched feedback pattern formally. For a $T$-step game, the player determines a grid $\mathcal{T}=\{t_0,\cdots,t_B\}$ \emph{adaptively}, where $0=t_0<t_1<\cdots<t_B=T$ and $B\ll T$. During the game, loss observations are communicated to the player only at the grid points $t_1, \cdots, t_B$. As a consequence, for any time $t$ in the $j$-th batch, that is, $t_{j-1}<t\leq t_j$, the loss generated at time $t$ cannot be observed until time $t_j$, and the decision made at time $t$ depends only on losses up to time $t_{j-1}$. The determination of the grid $\mathcal{T}$ is adaptive in the sense that the player chooses each grid point $t_j\in\mathcal{T}$ based on the operations and observations up to the previous point $t_{j-1}$.

\section{Related Works}

\textbf{Hyperparameter Optimization:} In recent years, the surging need of hyperparameter optimization algorithms from deep learning has motivated a larger cluster of researches. See \citet{feurer2019hyperparameter} for a recent exposition. To name a few, grid search \citep{wu2011experiments} and random search \citep{bergstra2012random} are now considered two standard benchmark methods. Inspired by biological findings, population-based methods have also been used for HPO tasks \citep{hansen2016cma,jaderberg2017population}.
Another line of research is the model-based methods. In such methods, a model fitted on past observation is built, and subsequent hyperparameter trials are selected based on this model. Examples include Bayesian optimization algorithms with different surrogate \citep[e.g.,][]{10.5555/3104322.3104451,shahriari2015taking}
, and tree-based methods \citep{hutter2011sequential,bergstra2011algorithms,10.1145/3412815.3416885}.

More recently, HPO methods that explicitly model the training nature of neural networks have been invented. In these methods, obtaining a more accurate test/validation error requires higher training expenses. Such methods include multi-fidelity (Bayesian) optimization \citep{forrester2007multi,kandasamy2017multi,song2019general}, where feedback at finer fidelity are more accurate. Other methods that incorporate training budget include Successive Halving \citep{jamieson2016non} and Hyperband \citep{li2017hyperband}, and Beysian versions of Hyperband \citep{falkner2018bohb}. In particular, \citet{huang2022improving} designed a special multi-fidelity algorithm for Bayesian optimization. They proposed a special training data collection strategy for getting better estimation in Bayesian models. A better model can lead to better search area of hyperparameters.

\textbf{Pure Exploration in Multi-Armed Bandits:} Another line of related works is pure exploration bandits, where the goal is to minimize the simple regret, or the gap between the optimal arm and the output one. \citet{bubeck2011pure} gave upper and lower bounds for simple regret under stochastic setting. \citet{jamieson2016non} and \citet{li2017hyperband} extended the problem to non-stochastic setting. \citet{carpentier2015simple} studied pure exploration bandits with infinitly many arms, where the means of arms are drawn from a distribution $F$. \citet{even2006action} and \citet{mannor2004sample} studied a retaled setting, where the aim is to output an $\varepsilon$-optimal arm using as little budget $T$ as possible.

\textbf{Our advantages:} This paper studies HPO from a Lispchitz bandit perspective, and properly incorporate the training budget considerations into the Lipschitz best arm identification framework. Such HPO algorithms, to the best of our knowledge, have not been covered by existing works.
Compared to existing setups, Lipschitzness can better capture the loss landscape of the hyperparameters, as discussed in the introduction. In addition, our algorithm is parallelizable, since the training feedback does not need to be frequently collected. Our method leverages virtues of both Lipschitz bandits and batched bandits. See Appendix \ref{app:related} for more related works.

\section{Algorithms} \label{sec:alg}

In this section, we propose Batched Lipschitz Exploration (BLiE) algorithm to solve pure-exploration Lipschitz bandits with batched feedback. The main policies of BLiE are inspired by \citet{fenglipschitz}. However, the novel analysis in this work shows that BLiE can efficiently identify good arms by using very few data communications, and has better performance than uniform search and random-search-based algorithms.

BLiE works as follows: 1. partition the arm set to a finite number of regions and assign budgets to them; 2. estimate the performance of each region by the observed losses; 3. eliminate regions with high losses; 4. further partition the remaining regions and assign more budget to them. Moreover, in a batched feedback setting, the agent's knowledge does not accumulate within each batch. This characteristic of the problem suggests a `uniform' type algorithm. Following this intuition, in each batch, we partition the remaining arm space into cubes of the same size, and treat them equally in later steps. Next we describe the three main rules in detail.

\begin{figure}[ht]
	\centering
	\subfigure{
		\includegraphics[width=5cm]{./figures/partition-plot/hpo_partition_step_2.png}
	}\hspace{-5mm}
	\subfigure{
		\includegraphics[width=5cm]{./figures/partition-plot/hpo_partition_step_3.png}
	}\hspace{-5mm}
	\subfigure{
		\includegraphics[width=5cm]{./figures/partition-plot/hpo_partition_step_4.png}
	}
	\caption{Partition and elimination process of a BLiE run. The $i$-th subfigure shows the pattern before the $(i+1)$-th batch. Dark gray cubes are those eliminated in the most recent batch, while the light gray ones are those eliminated in earlier batches.}
	\label{f:visual}
\end{figure}

\textbf{Uniform Play Rule:} At the beginning of each batch $m$, a collection of subsets of the arm space $ \A_m  = \{ C_{m,1}, C_{m,2}, \cdots, C_{m, |\A_m|} \} $ is constructed. This collection of subset $\A_m$ consists of standard cubes, and all cubes in $\A_m$ have the same edge length $r_m$. We refer to cubes in $\mathcal{A}_m$ as active cubes of batch $m$. During batch $m$, one arm $x_C$ from each cube $C \in \A_m$ is sampled\footnote{One can arbitrarily pick $x_C$ from $C$. In practice, we pick $x_C$ uniformly at random.} and assigned with budget $ n_m := \frac{1}{r_m^\beta} $.

\textbf{Arm Elimination Rule:} At the end of batch $ m $, we observe loss $ \ell (x_C, n_m) $ for each $C \in \A_m$. Cubes with high losses are then eliminated, according to the following rule: a cube $C \in \A_m$ is eliminated if $\ell_{m}^{\min} - \ell (x_C, n_m ) \ge \alpha r_m $, where $ \ell_{m}^{\min} := \min_{ C \in \A_m } \ell (x_C, n_m ) $ and $\alpha$ is a parameter to be specified later.

\textbf{Equal Partition Rule:} After necessary removal of ``bad cubes'', each cube in $\A_m$ that survives the elimination is equally partitioned into $\left(\frac{r_m}{r_{m+1}}\right)^d$ subcubes of edge length $ r_{m+1} $, where $\{ r_{m} \}$ is a predetermined edge-length sequence. These cubes (of edge length $ r_{m+1} $) are collected to construct $\A_{m+1}$, and the learning process moves on to the next batch.

\begin{algorithm}[htb]
	\caption{Batched Lipschitz Exploration (BLiE)}
	\label{BLiN}
	\begin{algorithmic}[1]
		\STATE \textbf{Input.} Arm set $\mathcal{X}=[0,1]^d$; total budget $T$; $\alpha$ and $\beta$.
		\STATE \textbf{Initialization} Edge-length sequence $\{r_m\}_{m\in\mathbb{N}^+}$; The first grid point $t_0=0$; Equally partition $\mathcal{X}$ to $r_1^d$ subcubes and define $\mathcal{A}_{1}$ as the collection of these subcubes.

		\FOR{$m=1,2,\cdots$}
			\STATE For each cube $C\in\mathcal{A}_m$, randomly choose an arm $x_C$ and evaluate $x_C$ with budget $n_m=\frac{1}{r_m^\beta}$.
			\STATE Receive the loss $\ell(x_C,n_m)$ for each cube $C\in\mathcal{A}_m$.
			Find  $\ell_m^{\min}=\min_{C\in\mathcal{A}_m}\ell(x_C,n_m)$.
			\STATE For each cube $C\in\mathcal{A}_m$, eliminate $C$ if $\ell(x_C,n_m)-\ell_m^{\min}>\alpha r_m$. Let $\mathcal{A}_m^+$ be set of cubes not eliminated.
			\STATE \label{cond:break}Compute $t_{m+1}=t_m+(r_{m}/r_{m+1})^d\cdot|\mathcal{A}_m^+|\cdot n_{m+1}$. If $t_{m+1}\geq T$ then define $\mathcal{X}_c=\{x_C:\;C\in\mathcal{A}_m^+\}$ and \textbf{break}.
			\STATE Equally partition each cube in $\mathcal{A}_m^+$ into $\left(r_m/r_{m+1}\right)^d$ subcubes and define $\mathcal{A}_{m+1}$ as the collection of these subcubes.
		\ENDFOR
	\STATE Assign budget $n_f$ to each arm $x\in\mathcal{X}_c$ uniformly, so that the total budget is used up.
	\STATE\textbf{Output}  $\widetilde{x}^*=\mathop{\arg\min}_{x\in\mathcal{X}_C}\ell(x, n_m+n_f)$.
	\end{algorithmic}
\end{algorithm}

The learning process is summarized in Algorithm \ref{BLiN}. Moreover, we present a visualization of partition and elimination steps of a real BLiE run in Figure \ref{f:visual}, where the arm space is $[0, 1]^2$.

\section{Introduction}
Success of modern machine learning models heavily relies on the choice of hyperparameters. These hyperparameters are difficult to set, because of high training cost of the complex models.
Therefore, practitioners are in great need of efficient algorithms for finding good hyperparameter configurations.

\begin{figure}[ht]
    \centering
    \includegraphics[width=8cm]{figures/landscape.png}
    \caption{Test error of a CNN-classifier as a function of learning rate.}
    \label{fig:landscape}
\end{figure}

In practice, many hyperparameters need to be chosen from continuous spaces. An important example is the learning rate; See Figure \ref{fig:landscape} for an illustration.
From Figure \ref{fig:landscape} we observe: (1) the choice of hyperparameters has a great impact on model performance; (2) the objective function is continuous, but not well-behaving. Similar hyperparameters include weight parameters, noise schedules in stochastic models, and so on. There have been a lot of methods developed to tackle these problems, model-based \citep{10.5555/3104322.3104451,shahriari2015taking,falkner2018bohb,huang2022improving} or model-free  \citep{wu2011experiments,bergstra2012random,jamieson2016non,li2017hyperband}. However, existing model-based methods lack theoretical guarantees, unless harsh conditions are imposed; model-free methods seldomly search over the hyperparameter space adaptively, which may lead to inefficiency and worse final performance. Therefore, we need a method that (1) takes advantage of the continuity of objective function to guide searching; (2) has better theoretical guarantees than model-based methods.

To this end, we develop a new bandit-based approach for continuous HPO problems. When modeling HPO as a bandit problem, the hyperparameter configuration corresponds to arm, and the learning output corresponds to loss or reward. In this work, we formulate continuous HPO as a pure-exploration Lipschitz bandit problem, where the search space contains infinite arms, and the aim is to find the arm with minimal loss. We assume that the loss function is Lipschitz. This condition captures the fact that closer hyperparameters tend to have similar losses. We take advantage of the Lipschitz property to design efficient HPO algorithms.

We propose Batched Lipschitz Exploration (BLiE) algorithm to solve this pure exploration problem. BLiE adaptively learns the landscape of objective function, and automatically assign more budget to promising hyperparameters. To sum up, BLiE has three advantages:

    $\bullet$ BLiE is model-free and only has one continuity assumption. Thus, our theoretical guarantees work for a wide range of problems. As a comparison, \citet{parker2020provably} assume the objective function is almost surely continuously differentiable and its derivative satisfies Lipschitz assumptions for getting the regret bound. However, these conditions are too complex to meet or verify.

    $\bullet$ BLiE takes advantage of the continuity of objective function to guide sampling, so it is more likely to find best hyperparameter configurations. Theoretically speaking, by simple-regret analysis, we show that performance of our algorithm is better than random-search-based methods \citep[e.g.,][]{bergstra2012random, jamieson2016non, li2017hyperband} when the HPO task is hard.

    $\bullet$ BLiE is suitable for batched feedback setting, and the decision-making process only needs very few data communications. Therefore, BLiE can naturally work in parallel.

Experimental results from different machine learning tasks show the superior performance of BLiE. Furthermore, we apply BLiE to noise scheduling in diffusion models. The BLiE schedule has competitive sample quality by using very few diffusion steps, and thus significantly improves sampling speed without using additional speeding up techniques.
\subsection{Improving noise schedule of diffusion models}\label{sec:exp2}

Diffusion probabilistic models (DPM) \citep{Ho2020DenoisingDP,Song2020ScoreBasedGM,Dhariwal2021DiffusionMB} is a powerful family of generative models. DPMs have achieved state-of-the-art performance on various applications including image generation \citep{Rombach2021HighResolutionIS}, audios or videos generation \citep{Kong2020DiffWaveAV,Ho2022VideoDM}, drug designs \citep{Hoogeboom2022EquivariantDF}, and so on.

Following \citet{Song2020ScoreBasedGM}, a diffusion model uses a forward diffusion SDE to diffuse data distribution and a reverse SDE to generate samples. Moreover, a neural score network is used to approximate marginal score functions of forward diffusion, which is required in the reverse SDE. The Variance Preserving (VP) forward diffusion \citep{Song2020ScoreBasedGM} is favored as an Ornstein--Uhlenbeck-type diffusion SDE across the literature, which takes the form
\begin{align}\label{eqn:vp_forward}
    dX_t = -\frac{1}{2}\beta(t)X_tdt  + \frac{1}{2}\sqrt{\beta(t)}dW_t.
\end{align}
Under certain conditions on $\beta (t)$, such diffusion enables arbitrary initial distribution to converge to multivariate Gaussian with sufficiently large $t$. Here $\beta(t)>0$ is called noise schedule of VP forward diffusion. The noise schedule is an important functional hyperparameter of VP diffusion which can influence both the learning efficiency and generative performance of DPMs. The pioneering work \citep{Ho2020DenoisingDP} proposed a linear learning schedule, for which the noise schedule $\beta(t)$ grows linearly with a start $\beta(0)=10^{-4}$ and an end $\beta(1)=2\times 10^{-2}$ with $t\in [0,1]$.

In spite of impressive generative performance on various forms of data, the major drawback of DPMs is the slow sampling speed compared to other generative models such as GANs, VAEs, or Normalizing Flows. Usually, more than 1k diffusion steps are needed for the best performance of a diffusion model, and thus the same number of neural function evaluations (NFEs) are needed in sampling. Advanced simulation techniques of sampling SDE or ODE in order to reduce the NFEs of DPMs were intensively studied in recent works \citep{Karras2022ElucidatingTD,Bao2022AnalyticDPMAA}. The state-of-the-art sampling technique still requires more than 30+ NFEs to achieve comparable generative performance on image datasets in terms of Fretchet Inception Distance (FID) \citep{Heusel2017GANsTB}.

\begin{figure*}[ht]
	\centering
	\subfigure[T=1000]{
		\includegraphics[width=5cm]{./figures/fid_T_1000.png}
		\label{f:fid-1000}
	}
	\subfigure[T=200]{
		\includegraphics[width=5cm]{./figures/fid_T_200.png}
		\label{f:fid-200}
	}
	\subfigure[T=100]{
		\includegraphics[width=5cm]{./figures/fid_T_100.png}
		\label{f:fid-100}
	}
	\caption{FWD score of DDPM with different diffusion steps $T$.}
	\label{f:fid}
\end{figure*}

In this experiment, we use BLiE to search for noise schedules with fewer diffusion steps $T$. Our result shows that by using only $T=100$ or $200$ diffusion steps, BLiE schedule achieves competitive sample quality with a linear schedule using $T=1000$ diffusion steps. It means that the sampling speed can be greatly improved without using any additional speeding-up technique. Recent works point out that DPMs' forward diffusion can be roughly divided into three stages \citep{deja2022analyzing}.
Based on such results, we consider searching a three-stage piece-wise linear schedule and let the two knots be the hyperparameters. More precisely, we search for four hyperparameters $t_a$, $\beta_a$, $t_b$, $\beta_b$ such that $0<t_a<t_b<1$ and $10^{-4}<\beta_a<\beta_b<2\times10^{-2}$, and the corresponding noise schedule $\beta(t)$ is a piece-wise linear function with start point $\beta(0)=10^{-4}$, end point $\beta(1)=2\times10^{-2}$, and knots $\beta(t_a)=\beta_a$, $\beta(t_b)=\beta_b$.

\begin{figure}[h]
    \centering
    \includegraphics[width=7cm]{figures/mnist_photo.PNG}
    \caption{MNIST samples generated using different noise schedules and diffusion steps.}
    \label{fig:mnist_photo}
\end{figure}

The experiment aims to demonstrate the feasibility of the proposed HPO algorithm for improving diffusion models, so we conduct the diffusion models experiments on the MNIST dataset to save computational costs. Because the MNIST dataset is grayscale, we mimic the calculation of FID on colored images by replacing the pre-trained inception-v3 model with our pre-trained wide-resnet \citep{Zagoruyko2016WideRN} on MNIST, so we named this metric the Frechet Wideresnset Distance (FWD).
Figure \ref{f:fid} presents the FWD curves along training iterations for 1000 (default), 200, and 100 diffusion steps respectively. As shown in the figure, red curves represent BLiE schedule, and blue curves represent the default linear schedule.
The fewer diffusion steps we take, the more advantageous the BLiE schedule is compared to the default schedule. Samples generated using different noise schedules and diffusion steps are shown in Figure \ref{fig:mnist_photo}. This figure also shows that sample quality of BLiE schedule is better when $T$ is small. Besides the above comparison, we also find that the marginal distribution of VP diffusion \eqref{eqn:vp_forward} with BLiE schedule converges to Gaussian distribution more rapidly than that with default schedule. This finding indicates that BLiE potentially finds a more efficient noise schedule with limitations on diffusion steps. Our results may provide helpful insights on the design of forward diffusions to human experts.

\section{Conclusion}
In this paper, we focus on continuous HPO problem. We formulate this problem as pure-exploration Lipschitz bandits, and propose BLiE as a solution. BLiE has three advantages: 1. BLiE has theoretical guarantees based only on a continuous assumption; 2. BLiE takes advantage of the continuity of the objective function to guide sampling; 3. BLiE can naturally work in parallel. Our empirical results demonstrate the superior performance of BLiE. We also apply BLiE to search noise schedule for diffusion model. Compared with standard linear schedule, BLiE schedule greatly improves the sampling speed without using additional techniques.


\section{Introduction}
\label{sec:intro}

These guidelines include complete descriptions of the fonts, spacing, and
related information for producing your proceedings manuscripts. Please follow
them and if you have any questions, direct them to Conference Management
Services, Inc.: Phone +1-979-846-6800 or email
to \\\texttt{papers@2021.ieeeicassp.org}.

\section{Formatting your paper}
\label{sec:format}

All printed material, including text, illustrations, and charts, must be kept
within a print area of 7 inches (178 mm) wide by 9 inches (229 mm) high. Do
not write or print anything outside the print area. The top margin must be 1
inch (25 mm), except for the title page, and the left margin must be 0.75 inch
(19 mm).  All {\it text} must be in a two-column format. Columns are to be 3.39
inches (86 mm) wide, with a 0.24 inch (6 mm) space between them. Text must be
fully justified.

\section{PAGE TITLE SECTION}
\label{sec:pagestyle}

The paper title (on the first page) should begin 1.38 inches (35 mm) from the
top edge of the page, centered, completely capitalized, and in Times 14-point,
boldface type.  The authors' name(s) and affiliation(s) appear below the title
in capital and lower case letters.  Papers with multiple authors and
affiliations may require two or more lines for this information. Please note
that papers should not be submitted blind; include the authors' names on the
PDF.

\section{TYPE-STYLE AND FONTS}
\label{sec:typestyle}

To achieve the best rendering both in printed proceedings and electronic proceedings, we
strongly encourage you to use Times-Roman font.  In addition, this will give
the proceedings a more uniform look.  Use a font that is no smaller than nine
point type throughout the paper, including figure captions.

In nine point type font, capital letters are 2 mm high.  {\bf If you use the
smallest point size, there should be no more than 3.2 lines/cm (8 lines/inch)
vertically.}  This is a minimum spacing; 2.75 lines/cm (7 lines/inch) will make
the paper much more readable.  Larger type sizes require correspondingly larger
vertical spacing.  Please do not double-space your paper.  TrueType or
Postscript Type 1 fonts are preferred.

The first paragraph in each section should not be indented, but all the
following paragraphs within the section should be indented as these paragraphs
demonstrate.

\section{MAJOR HEADINGS}
\label{sec:majhead}

Major headings, for example, "1. Introduction", should appear in all capital
letters, bold face if possible, centered in the column, with one blank line
before, and one blank line after. Use a period (".") after the heading number,
not a colon.

\subsection{Subheadings}
\label{ssec:subhead}

Subheadings should appear in lower case (initial word capitalized) in
boldface.  They should start at the left margin on a separate line.

\subsubsection{Sub-subheadings}
\label{sssec:subsubhead}

Sub-subheadings, as in this paragraph, are discouraged. However, if you
must use them, they should appear in lower case (initial word
capitalized) and start at the left margin on a separate line, with paragraph
text beginning on the following line.  They should be in italics.

\section{PRINTING YOUR PAPER}
\label{sec:print}

Print your properly formatted text on high-quality, 8.5 x 11-inch white printer
paper. A4 paper is also acceptable, but please leave the extra 0.5 inch (12 mm)
empty at the BOTTOM of the page and follow the top and left margins as
specified.  If the last page of your paper is only partially filled, arrange
the columns so that they are evenly balanced if possible, rather than having
one long column.

In LaTeX, to start a new column (but not a new page) and help balance the
last-page column lengths, you can use the command ``$\backslash$pagebreak'' as
demonstrated on this page (see the LaTeX source below).

\section{PAGE NUMBERING}
\label{sec:page}

Please do {\bf not} paginate your paper.  Page numbers, session numbers, and
conference identification will be inserted when the paper is included in the
proceedings.

\section{ILLUSTRATIONS, GRAPHS, AND PHOTOGRAPHS}
\label{sec:illust}

Illustrations must appear within the designated margins.  They may span the two
columns.  If possible, position illustrations at the top of columns, rather
than in the middle or at the bottom.  Caption and number every illustration.
All halftone illustrations must be clear black and white prints.  Colors may be
used, but they should be selected so as to be readable when printed on a
black-only printer.

Since there are many ways, often incompatible, of including images (e.g., with
experimental results) in a LaTeX document, below is an example of how to do
this \cite{Lamp86}.

\section{FOOTNOTES}
\label{sec:foot}

Use footnotes sparingly (or not at all!) and place them at the bottom of the
column on the page on which they are referenced. Use Times 9-point type,
single-spaced. To help your readers, avoid using footnotes altogether and
include necessary peripheral observations in the text (within parentheses, if
you prefer, as in this sentence).

\begin{figure}[htb]

\begin{minipage}[b]{1.0\linewidth}
  \centering
  \centerline{\includegraphics[width=8.5cm]{image1}}
  \centerline{(a) Result 1}\medskip
\end{minipage}
\begin{minipage}[b]{.48\linewidth}
  \centering
  \centerline{\includegraphics[width=4.0cm]{image3}}
  \centerline{(b) Results 3}\medskip
\end{minipage}
\hfill
\begin{minipage}[b]{0.48\linewidth}
  \centering
  \centerline{\includegraphics[width=4.0cm]{image4}}
  \centerline{(c) Result 4}\medskip
\end{minipage}
\caption{Example of placing a figure with experimental results.}
\label{fig:res}
\end{figure}

\section{COPYRIGHT FORMS}
\label{sec:copyright}

You must submit your fully completed, signed IEEE electronic copyright release
form when you submit your paper. We {\bf must} have this form before your paper
can be published in the proceedings.

\section{RELATION TO PRIOR WORK}
\label{sec:prior}

The text of the paper should contain discussions on how the paper's
contributions are related to prior work in the field. It is important
to put new work in  context, to give credit to foundational work, and
to provide details associated with the previous work that have appeared
in the literature. This discussion may be a separate, numbered section
or it may appear elsewhere in the body of the manuscript, but it must
be present.

You should differentiate what is new and how your work expands on
or takes a different path from the prior studies. An example might
read something to the effect: "The work presented here has focused
on the formulation of the ABC algorithm, which takes advantage of
non-uniform time-frequency domain analysis of data. The work by
Smith and Cohen \cite{Lamp86} considers only fixed time-domain analysis and
the work by Jones et al \cite{C2} takes a different approach based on
fixed frequency partitioning. While the present study is related
to recent approaches in time-frequency analysis [3-5], it capitalizes
on a new feature space, which was not considered in these earlier
studies."

\vfill\pagebreak

\section{REFERENCES}
\label{sec:refs}

List and number all bibliographical references at the end of the
paper. The references can be numbered in alphabetic order or in
order of appearance in the document. When referring to them in
the text, type the corresponding reference number in square
brackets as shown at the end of this sentence \cite{C2}. An
additional final page (the fifth page, in most cases) is
allowed, but must contain only references to the prior
literature.

\bibliographystyle{IEEEbib}

\section{Introduction}
\label{sec:intro}

Disentanglement of speech into its multiple components is a fundamental problem in signal processing with applications in voice conversion \cite{qian2019autovc, qian2020unsupervised, wang2021adversarially, lian2022robust}, automatic speech recognition \cite{qian2022contentvec, ebbers2021contrastive, hsu2018unsupervised, khurana2019factorial}, speaker recognition \cite{nagrani2020disentangled}, and privacy preservation in speech \cite{aloufi2020privacy}. The goal of disentanglement is to separate different attributes of the speech signal such that the final signal representation will be invariant to attributes not relevant to the downstream task. Previous work has focused on invariance towards acoustic content\footnote{In this paper, “acoustic content", or “acoustics" refers to the information in an audio signal related to the Room Impulse Response (RIR) at a particular location in a room when the source audio is played from a different, fixed location.} so that target attributes like speaker identity or linguistic content will be emphasized. In this paper, we specifically want to preserve acoustic content and extract representations that are invariant to all other attributes in a self-supervised fashion.
These representations are then used for the task of device arbitration \cite{barber2022end}.

The device arbitration task has arisen recently due to the ubiquity of smart voice assistant-enabled devices, which we refer to as “voice assistants" (VA) or “devices" interchangeably. Many households now have multiple VAs in the same room, leading to ambiguity with respect to which device should interact with the user. When the user wishes to begin interaction with a VA, they must first utter a wakeword (“Alexa", “Hey Google", etc.) which is then recorded by all devices in the room. For the most natural user experience, only the intended device from the user should wake up and continue to interact with the user. This leads to the device arbitration problem: \textit{given $N$ recordings of a source audio, where each recording comes from a VA, determine which VA is the intended one}.

Note that device arbitration is closely related to the well-studied source localization problem \cite{chen2002source}.
Time Difference Of Arrival (TDOA) \cite{gustafsson2003positioning} is an effective technique that solves source localization for audio signals but unfortunately requires large arrays of microphones not present on VAs. There are several other constraints imposed by modern VAs that make device arbitration a non-trivial problem: (1) The positions of each VA are unknown and could change over time (moving the device from the living room to the kitchen). (2) The acoustic environment of the VAs is unknown. (3) Clock synchronization between devices is not always available, making TDOA between devices infeasible. Given these constraints, the device arbitration task must be solved by only relying on the room acoustic information present in each audio recording.

Motivated by these constraints, we propose SPADE: Self-supervised Pretraining for Acoustic DisEntanglement. SPADE is a pretraining technique that disentangles acoustic information from speech signals by using multiple views of a source audio without the need for labels. We find that when used in combination with previous work on device arbitration \cite{barber2022end}, SPADE leads to improved performance when less labeled training data is present. Given that labeled data is difficult to collect for this task, SPADE is an invaluable technique for improving performance on device arbitration at zero additional inference
cost.

 The remainder of our paper is organized as follows: In Section 2 we discuss prior work on device arbitration and related tasks. In Section 3, we discuss the data used in our experiments and the simulation process from which it is generated. In Section 4, we detail our proposed pretraining approach. In Section 5, we discuss our experimental setup and in Section 6 we discuss results. The paper ends with conclusions and suggestions for future work in Section 7.

\section{Prior Work}
\label{sec:prior_work}

While device arbitration is a relatively new problem, it is closely related to source localization \cite{chen2002source, gustafsson2003positioning}. The goal of source localization is to determine the position of the object emitting sound, i.e. the source. Current techniques rely on large arrays of microphones which are not available given our problem setup. Previous work \cite{barber2022end} also demonstrated that directly predicting source distances from each device and making arbitration decisions based on those distances resulted in worse performance.

The goal in arbitration is to select an attended device the user is speaking to based on distance and direction. Common techniques compare signal attributes like Signal-to-Noise Ratio (SNR), estimated distance between source and microphone, cross-correlation, etc. \cite{kumatani2011channel}. The goal of device arbitration is different from channel selection \cite{kumatani2011channel, wolf2014channel}  since the optimal device is simply defined as that which is closest to the user or as the attended device (defined as the one in the look direction of the user or any other acoustical or visual relevant cue), and not that which leads to better performance on another downstream task. The differences in problem setup and objective between device arbitration and source localization show that device arbitration should be studied separately and has its own set of unique challenges that make it an interesting problem.

We used as a baseline, the machine learning-based device arbitration proposed by Barber et al. \cite{barber2022end}.
The authors proposed an end-to-end approach to train a neural network to perform device arbitration. Their model consists of a small convolutional feature extractor that runs locally on each device, and a larger arbitration network that runs in the cloud to make the final decision. Results demonstrated significantly improved performance across a variety of room conditions over a simple energy-based approach.

\section{Dataset Simulation}
\label{sec:dataset}

Currently, there is no large-scale dataset for device arbitration with known ground truth labels, so we run our experiments with simulated data following the three main steps described in Barber et al. \cite{barber2022end}:

\begin{itemize}
    \item \textbf{Sample scenario:} Sample a room from a variety of acoustic settings (room length/width, noise sources) as well as device/speaker positions within the room. Given device/speaker positions, generate the arbitration label based on smallest Euclidean distance from device to speaker.
    \item \textbf{Generate RIR:} Given the sampled scenario, generate a Room Impulse Response (RIR) for each device in the scenario using an acoustic simulator.
    \item \textbf{Generate audio:} Convolve speech utterances with generated RIRs and mix with noise for each device. After this step, we have an artificial dataset of device arbitration audio and corresponding ground truth labels.
\end{itemize}
We use the Image Source Method (ISM) \cite{dance1997complete} for data simulation and source audio from \cite{barber2022end}, but have updated the scene sampling hyperparameters to those in Table \ref{tab:hparams_sampling}.

\begin{table}[]
    \centering
    \begin{tabular}{|c|c|} \hline
    Parameter & Distribution \\ \hline
    Room length/width (m) & Uniform(3.0, 10.0) \\ \hline
    Room height (m) & Uniform(2.5, 6.0) \\ \hline
    Reverberation time (s) & Beta(1.1, 3.0) \\ \hline
    Number of devices & ShiftedPoisson(m=3,l=2,h=15) \\ \hline
    Number of noise sources & ShiftedPoisson(m=2,l=1,h=5) \\ \hline
    Speech level (dB SPL) & Uniform(55.0, 70.0) \\ \hline
    Noise level (dB SPL) & Uniform(50.0, 70.0) \\ \hline
    \end{tabular}
    \caption{Hyperparameters for scene sampling. For the ShiftedPoisson distribution we denote mean with “m", low with “l" and high with “h."

    }
    \label{tab:hparams_sampling}
\end{table}

\section{Method}
\label{sec:method}

Our arbitration model is based on that proposed by Barber et al. \cite{barber2022end} and is composed of two components: the feature encoder and the classifier that makes the arbitration decision. Prior to end-to-end training of the encoder and classifier,
we pretrain the encoder using two schemes: contrastive and reconstructive pretraining. Our preprocessing pipeline and pretraining schemes are discussed in the following subsections.

\subsection{Audio Preprocessing}

Audio is first transformed to log-filterbank energy (LFBE) features, where the spectrogram is computed using a 25ms frame size and a frame skip of 10ms. The Mel transform is applied to the spectrogram with 64 Mel bands, followed by the log transform. LFBE features are
mean and variance normalized before downstream processing by neural models.

\subsection{Encoder Architecture}\label{sec:encoder_arch}

The encoder architecture is a residual convolutional model composed of 18 convolutional layers, with batch normalization and the ReLU activation function applied to each layer.
The encoder model is the same for all approaches discussed in this paper (pretraining, baseline).
This network produces a sequential feature representation of the input with much smaller temporal resolution than the input LFBE features. During pretraining we use a small Transformer \cite{vaswani2017attention} network to map the sequence of vectors output by the encoder to a single vector. This network is discarded after pretraining but is implicit as part of the encoder in the following pretraining discussions and Figs. \ref{fig:contrastive} and \ref{fig:recon}.

\begin{figure}
    \centering
    \includegraphics[width=8.3cm, height=6.6cm]{Figures/contrastive1.pdf}
    \caption{Contrastive pretraining scheme: Acoustic encoder has shared weights.}
    \label{fig:contrastive}
\end{figure}

\subsection{Contrastive Pretraining}

Contrastive loss functions have been shown to create high-quality representations across a variety of domains like speech and natural language processing \cite{baevski2020wav2vec, gao-etal-2021-simcse}. This family of loss functions operates by assuming data are similar or dissimilar with respect to a particular attribute and encouraging embeddings of the data to reflect these relationships via distance in an embedding space. In a device arbitration scene, audio from the same device has the same room acoustic properties, while audio from different devices will have different acoustic properties.\footnote{ This is due to the assumption that the devices are in different locations.} Since we want to encode room acoustic information, we can encourage embeddings of audio from the same device to be similar and simultaneously encourage embeddings of audio from different devices to be orthogonal (see Fig. \ref{fig:contrastive}). Since speech content will be the same across all $N$ recordings from a given room, the embedding should be invariant to speech content and only encode acoustic information.

Let us denote the audio recorded by device $a$ as $x^a$. For this pretraining approach, we create a fixed-length embedding $z^a$ of $x^a$ by passing through the encoder\footnote{The Transformer network discussed in Section \ref{sec:encoder_arch} is implied here to follow the encoder to create the fixed-length representation.}, i.e. $z^a = \text{encoder}(\text{LFBE}(x^a))$. Then $z^a$ is normalized to have magnitude one. We can denote a continuous slice of $x^a$ from time $t_1$ to $t_2$ as $x^a_{t_1:t_2}$ where $t_2 > t_1$ and its corresponding fixed-length embedding as $z^a_{t_1:t_2}$. Given $N$ recordings $x^1,x^2,...,x^N$ that are zero-padded to the same length $T$ and a splitting index $t_{split}$ such that $0<\frac{T}{2}-\epsilon<t_{split}<\frac{T}{2}+\epsilon<T$, where $\epsilon$ is a small random jitter, we arrive at our loss function $\mathcal{L}_{C}$ for one arbitration scenario:

\begin{equation}
    \mathcal{L}_1 = \sum_{i=1}^N \sum_{j=1}^N | \langle z^i_{0:t_{split}} , z^j_{t_{split}:T} \rangle - \delta_{ij}|
\end{equation}

\begin{equation}
    \mathcal{L}_2 = \sum_{i=1}^N \sum_{j\neq i} | \langle z^i_{0:t_{split}} , z^j_{0:t_{split}} \rangle | + | \langle z^i_{t_{split}:T} , z^j_{t_{split}:T} \rangle |
\end{equation}

\begin{equation}
    \mathcal{L}_{C} = \mathcal{L}_1 + \mathcal{L}_2
\end{equation}
where $\delta_{ij}$ is the Kronecker delta function. Note that $\mathcal{L}_1$ encourages the two halves of the same audio recording to map to the same embedding. The $\mathcal{L}_2$ term provides stronger supervision for invariance to speech content by encouraging different recordings of the same respective halves of the audio to be orthogonal.

\subsection{Reconstructive Pretraining}

Disentanglement of different attributes in speech has been accomplished previously using autoencoding with an information bottleneck \cite{qian2019autovc, qian2020unsupervised}. We take a similar approach to disentangle room acoustic information from speech in a self-supervised fashion, making the assumption that the room acoustic properties are constant\footnote{This stationarity assumption may not be true in all cases (people/pets moving around), but it is reasonable given that audio is only recorded over a two-second interval.} for the duration of the wakeword audio ($\sim$2s).

\begin{figure}[t!]
    \centering
    \includegraphics[width=8.3cm, height=10.0cm]{Figures/reconstruction4.png}
    \caption{Reconstruction pretraining scheme: Speech encoder, envelope, and reconstruction network have same time axis dimension as the LFBE time axis. Acoustic encoder creates fixed-length embedding that is copied along time axis of speech encoder and envelope output. Diagonally-shaded units are from non-learnable modules.}
    \label{fig:recon}
\end{figure}

Our model consists of a speech encoder, an acoustic encoder, and a reconstruction decoder. The speech encoder $S(\cdot)$ and reconstruction decoder $R(\cdot)$ are Transformers \cite{vaswani2017attention} and each produce a sequence of vectors. We design the acoustic encoder $A(\cdot)$ to produce a fixed-dimensional embedding due to the stationarity assumption of the acoustics and the need to create an information bottleneck.
Given that $N$ recordings of a source audio all contain identical speech content, the speech representation $s_i=S(x^i)$ should be the same for each recording, i.e. $s^1\approx s^2 \approx...\approx s^N$. To encourage this, we reconstruct one audio recording's LFBE features using its acoustic embedding and the speech embedding from another audio recording in the room. The information bottleneck enforced by creating a small fixed-dimensional embedding encourages the acoustic encoder only to represent information not common to all signals, i.e. room acoustics. Given that the $N$ recordings are not time-aligned, we provide alignment information to the decoder by extracting the envelope $env(x^i)$ of the LFBE features for $x^i$, which is the mean of the feature vector at each timestep:
\begin{equation}
    env(x^i)_k = \frac{1}{N} \sum_{q=1}^{N} \text{LFBE}(x^i)_{kq}
\end{equation}
where $k$ denotes the time axis, $q$ denotes the feature axis of the LFBE feature matrix, and $N=64$. Note that the envelope extractor is not a learnable module but rather a simple mean operation at each timestep to produce a low-dimensional representation of the LFBE features (feature vector $\rightarrow$ scalar). We can formally write our loss function $\mathcal{L}_R$ for one arbitration scenario as:

\begin{equation}
    \mathcal{L}_R = \frac{1}{N}\sum_{i=1}^N ||\text{LFBE}(x^i) - R(S(x^{\neq i}), A(x^i), env(x^i))||_2^2
\end{equation}
where $x^{\neq i}$ denotes a randomly-selected audio recording from $\{x^1, x^2, ..., x^N\}$ other than $x^i$. We form the input to $R(\cdot)$ by copying $A(x^i)$ along the time axis and concatenating it to $S(x^{\neq i})$ and $env(x^i)$. See Fig. \ref{fig:recon} for a diagram detailing this process.

\subsection{Arbitration Classifier Architecture}

The arbitration classifier was implemented previously \cite{barber2022end} as a Multilayer Perceptron (MLP) network, but we found further improvement using a self-attention network like the Transformer \cite{vaswani2017attention}.
For each device $i$, the encoder outputs a sequence of hidden states $h^i_1, h^i_2, ..., h^i_K$. For $N$ devices, the hidden states are concatenated along the time axis to form the sequence:

\begin{equation}
    H = h^1_1, h^1_2,...,h^1_K, h^2_1,h^2_2,...h^2_K,...,h^N_1,h^N_2,...h^N_K
\end{equation}
which is then passed through a network of self-attention layers\footnote{Positional encodings are added to the input.} to produce the sequence:

\begin{equation}
    G = g^1_1, g^1_2,...,g^1_K, g^2_1,g^2_2,...g^2_K,...,g^N_1,g^N_2,...g^N_K
\end{equation}
Each sequence $g^i_1, g^i_2, ..., g^i_K$ is then passed through a second network of self-attention to create a summary $G_i$ over time. Each $G_i$ is then passed through a two-layer feedforward neural network, outputting a scalar logit for device $i$. The logits are then passed through a softmax layer to produce the arbitration probabilities. The entire classification network is optimized using the crossentropy loss between the arbitration probabilities and the ground truth label distribution.

\subsection{Baseline}

The contributions of this paper are the self-supervised pretraining approaches, so as a baseline, we use the encoder and classifier networks discussed previously but do not pretrain the encoder.

\section{Experiments}
\label{sec:experiments}

The training dataset consists of 300k arbitration scenarios. To demonstrate the effectiveness of pretraining for learning representations useful for device arbitration, we create datasets of exponentially decreasing size. For dataset $i$ the training set size $s_i=\lfloor S/4^i \rfloor$, where $S=$300k (full training set size). We choose $i\in\{0, 1, 2, 3\}$ such that the smallest training set consists of $\sim$ 4.7k scenarios.

\subsection{Experimental Procedure}

For each experiment, we choose the final arbitration model based on the checkpoint with the lowest validation loss and evaluate on a held-out test set. We have four experiment setups:

\begin{itemize}
    \item \textbf{Baseline:} Train encoder-classifier model end-to-end on each of the training data subsets of size $s_i$ for $i\in\{0, 1, 2, 3\}$.
    \item \textbf{Contrastive:} Pretrain (acoustic) encoder using contrastive approach on all available training data (300k scenarios, no labels involved). Pick best validation checkpoint as initialization for encoder and then finetune encoder-classifier model end-to-end on each training data subset of size $s_i$ for $i\in\{0, 1, 2, 3\}$.
    \item \textbf{Reconstructive:} Same as contrastive setup except that we use reconstructive pretraining.

    \item \textbf{Combo:} Pretrain using both contrastive and reconstructive pretraining. Loss function becomes $\mathcal{L} = \lambda\mathcal{L}_R + (1-\lambda)\mathcal{L}_C$ where we set $\lambda=0.5$. Finetune encoder-classifier model as in previous setups.

\end{itemize}

\section{Results}
\label{sec:results}

Results are presented here as \textit{relative error rate} with respect to the performance of the 4.7k baseline setting. Denoting the accuracy of the target method $m$ as $\text{acc}_{m}$ and the accuracy of the 4.7k baseline setting as $\text{acc}_{\text{base}}$, we compute relative error rate as:

\begin{equation}
    \text{err}_{\text{rel}} = \frac{1 - \text{acc}_{m}}{1 - \text{acc}_{\text{base}}}
\end{equation}
Our results are presented in Figure \ref{fig:wrt_worst_case}. The most important trend is that the pretraining approaches outperform the baseline by a larger margin when the training dataset is small. This demonstrates that our proposed pretraining schemes
preserve acoustic information, learning features relevant to the device arbitration problem and are most beneficial when labeled training data is scarce. Initialization of the encoder with a pretrained checkpoint helps combat overfitting during the device arbitration training process.
We also find that the combination of contrastive and reconstructive pretraining does not lead to any noticeable improvement over either approach in isolation, indicating that both approaches may encode similar information.

\begin{figure}
    \centering
    \includegraphics[width=7.0cm, height=5.4cm]{Figures/wrt_worst_case.png}
    \caption{Relative Error Rate with respect to worst case.}
    \label{fig:wrt_worst_case}
\end{figure}

\section{Conclusion}
\label{sec:conclusion}

In this paper we propose constrastive and reconstructive pretraining, two forms of self-supervised representation learning, that disentangle acoustic content from speech. Unlike previous work that has aimed to create representations that are invariant to acoustic content, we aim to encode acoustic content only
and demonstrate its usefulness through the device arbitration problem.
We find that both of our proposed pretraining approaches lead to improvement over the baseline, and that improvement is more significant when the labeled training dataset is small. This provides empirical evidence that our pretraining objectives lead to representations of acoustic content that can be useful for the device arbitration task even in the absence of a large training corpus.

Given that self-supervised techniques require no human annotations, it may be possible to apply our proposed approaches to other research problems. For example, our disentangled acoustic representations may be used for other acoustic tasks like room acoustic property estimation or acoustic adaptation for home theater. While not studied in this paper, the speech content representations learned from reconstructive pretraining may be valuable for acoustic-invariant applications like speaker recognition or ASR since they are designed to encode all information except acoustics.

\vfill\pagebreak

\bibliographystyle{IEEEbib}