

\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.