\section{Introduction}\label{Introduction}

 Halo nuclei are among the most peculiar nuclear structures~\cite{T96,HJ87}. Indeed, they exhibit a unusually large size compared to stable nuclei. This  size is due to the low binding of one or two nucleons, which tunnel far from the rest of the nucleons and form a diffuse halo around them. Accordingly, one can model these nuclei as few-body objects: a compact core with one or two neutrons in the halo.
 An archetypical halo nucleus is $^{11}\rm Be$, seen as a $^{10}\rm Be$ core with one loosely-bound neutron  in its halo.

 Due to their  short lifetime, halo nuclei cannot be studied through usual spectroscopic techniques, i.e., where they are fixed targets, but are probed through indirect techniques, such as reactions. Breakup reactions describe the dissociation of the halo from the core. Because the core-halo binding is  fragile, breakup observables can have  high   statistics and are often used in the  low-intensity exotic beam facilities~\cite{P03,Fetal04}. These reactions reveal the cluster structure inside the nucleus and, when dominated by Coulomb, can be used to extract cross sections of astrophysical interest~\cite{BBR86}. To infer reliable information about the nuclear structure, one needs  an accurate reaction model coupled to a realistic description of the projectile.

Very precise models have been developed to this aim (see a recent review in Ref.~\cite{BC12}): the continuum-discretized coupled-channels method (CDCC)~\cite{Kam86,YOMM12}, time-dependent models~\cite{BW81,AW75} and the  dynamical eikonal approximation (DEA)~\cite{BCG05}. These models are  time consuming and are thus often restricted to a simple description of the projectile, i.e., usually a two-body description of the projectile. Extensions to three-body projectiles have been developed, but they are often restricted to elastic scattering observables~\cite{RGetal09,FG15}. Simpler methods, such as the usual eikonal model~\cite{G59}, are cheaper from a computational viewpoint and provide a simple interpretation of the collision. The  eikonal model relies on an adiabatic approximation and  is thus valid at energies above 60$A$~MeV, where breakup reactions are usually measured. However, its adiabatic treatment of the collision has three main drawbacks:  (i) its wave functions do not have the right asymptotic behavior, (ii) it  exhibits an additional symmetry that more elaborate methods do not have, and (iii) it is incompatible with the Coulomb interaction, causing a divergence in the breakup observables.

 Since the eikonal model provides precise results for nuclear-dominated reactions, a correction to its inefficient treatment of the Coulomb interaction -- called the Coulomb-corrected eikonal model (CCE)~\cite{MBB03,CBS08} -- has been developed. This correction replaces the diverging term of the eikonal phase by  the first-order approximation of the perturbation theory~\cite{AW75}.    In Ref.~\cite{CBS08}, the authors show that the CCE provides accurate energy and parallel-momentum distributions for the Coulomb-dominated breakup of one-neutron halo nucleus. Its extension to  two-neutrons halo nuclei  also leads to precise Coulomb breakup cross section~\cite{BCDS09,PDB12}. Nonetheless, this correction mixes two reaction models and   treats the nuclear and the Coulomb interactions on different footings.

 In this work, we develop a simplification to the DEA (S-DEA) which naturally removes the Coulomb divergence and {partly }corrects the asymptotic behavior, i.e.\ it tends to the first-order of  the perturbation theory.  This model is derived from an approximate solution of the DEA equation and has the advantage of having a numerical cost similar to the usual eikonal model. In the present article, we study the efficiency of this model  in the case of the nuclear- and Coulomb-dominated breakups of a one-neutron halo nucleus; we consider $^{11}\rm Be$ impinging on  $^{12}\rm C$ and $^{208}\rm Pb$ targets at 67$A$~MeV and 69$A$~MeV, respectively. These reactions were measured at RIKEN~\cite{Fetal04} and are precisely reproduced by the full DEA calculations~\cite{GBC06}. We thus compare our S-DEA  results to the DEA and to the CCE.

 Sec.~\ref{Sec2} describes the reaction model and provides the main ideas of the DEA, the CCE and the S-DEA. In Sec.~\ref{Sec3}, we evaluate the accuracy of the S-DEA for the breakup distribution of $^{11}\rm Be$ as a function of the $^{10}\rm Be$-$n$ relative energy and parallel momentum. This analysis is made for both  nuclear- and Coulomb-dominated breakups. Sec.~\ref{Conclusions} summarizes the main conclusions of this work.

\section{Theoretical framework}\label{Sec2}
	\subsection{Reaction model}\label{Sec2A}
 We study the  breakup of a one-neutron halo-nucleus projectile $P$ of charge $Z_P e$ with a structureless target $T$ of mass $m_T$ and charge $Z_T e$. Since halo nuclei exhibit a  clusterized structure, we model $P$ as a two-body object, composed of a core $c$ of mass $m_c$ and charge $Z_Pe$, and a neutron $n$ of mass $m_n$. We assume all three particles structureless and only the spin of the neutron is considered. The structure of the projectile is described through an effective internal Hamiltonian~\cite{BC12}
	\begin{equation}
h_{cn} = \frac{p^2 }{2 \mu_{cn}}  + V_{cn}(r),\label{eq1}
\end{equation}
where $\ve{p}$ and $\ve{r}=(\ve{s},z)$ are respectively the $c$-$n$ relative momentum and coordinate, $\mu_{cn}$ is the $c$-$n$ reduced mass and $V_{cn}$ is an effective $c$-$n$ potential, that we assume local. Here, this real potential is taken as the sum of a Woods-Saxon and a spin-orbit terms (see Sec.~\ref{Sec3}).

 The interactions of both fragments $c$ and $n$   with the target $T$ are simulated through central local optical potentials   $V_{cT}$ {(including Coulomb)} and $V_{nT}$, respectively. The collision is thus described by the three-body \Sch equation~\cite{BC12}
	\begin{eqnarray}
	\lefteqn{\left[\frac{P^2}{2\mu}+h_{cn}+V_{cT}(R_{cT})+V_{nT}(R_{nT})\right]\Psi(\ve{R},\ve{r})=}\nonumber\\
	&\hspace{5cm}&E_{\rm tot}\ \Psi(\ve{R},\ve{r}), \label{eq2}
	\end{eqnarray}
	where $\ve{P}$ and $\ve{R}=(\ve{b},Z)$ are respectively the $P$-$T$ relative momentum and coordinate, $\mu$ is the $P$-$T$ reduced mass, $E_{\rm tot}$ is the total energy of the system and $\ve{R_{(c,n)T}}=(\ve{b_{(c,n)T}},Z_{(c,n)T})$ are respectively the $c$-$T$ and $n$-$T$ relative coordinates.
This \Sch equation is solved with the initial condition that the projectile is in its ground state $\phi_0$ with energy $E_0$, and is impinging on the target with a velocity $\ve{v}=\ve{P}/\mu=\hbar \ve{K}/\mu$. The wave function verifies
		\begin{equation}
	\Psi(\ve{R},\ve{r})\flim{Z}{- \infty}e^{iKZ+\cdots}\ \phi_{0} (\ve{r}),\label{eq3}
	\end{equation}
	where we choose the $Z$-axis to be the beam axis.	The ``$\cdots$" in Eq.~\eqref{eq3} reflects the fact that the long-range Coulomb interaction distorts the incoming plane wave, even at large distances.

	\subsection{Dynamical eikonal approximation}\label{Sec2B}

	 At high enough energy, the beam is only slightly deflected and the three-body wave function $\Psi$ does not differ much from a plane wave. The eikonal model~\cite{G59} factorizes this plane wave out of the wave function
		\begin{equation}
	\Psi(\ve{R},\ve{r}) =e^{iKZ}\ \widehat{\Psi}(\ve{R},\ve{r})\label{eq4}
	\end{equation}
	and assumes that the second derivatives of the new wave function $\widehat{\Psi}$  can be neglected. The three-body \Sch equation~\eqref{eq2} simplifies into the DEA equation~\cite{BCG05}
			\begin{eqnarray}
	\lefteqn{	i\hbar v \pderiv{}{Z} \widehat{\Psi}^{\rm DEA}(\ve{R},\ve{r})=}\nonumber\\
		&\hspace{0cm}&[h_{cn}-E_0+V_{cT}(R_{cT})+V_{nT}(R_{nT})]\widehat{\Psi}^{\rm DEA}(\ve{R},\ve{r}).\label{eq5}
	\end{eqnarray}
 This partial-derivative equation is solved through a numerical evolution calculation as a function of the transverse coordinate \ve{b} \cite{BCG05}. Its solutions {at large $b$s} tend  asymptotically to the {ones obtained at the perturbation theory}  and are  accurate at energies above 40$A$~MeV~\cite{GBC06,GCB07}.

		\subsection{Eikonal approximation}\label{Sec2C}

 The usual eikonal model~\cite{G59} relies on the adiabatic approximation, which sees the coordinate of the projectile as frozen during the collision. Consequently, the internal Hamiltonian {is approximated} by the energy of the ground state  in Eq.~\eqref{eq5}, i.e. $h_{cn}\approx E_0$. The solutions satisfying \Eq{eq4} can be derived analytically and have the simple asymptotic form~\cite{BC12}
	\begin{eqnarray}
\widehat{\Psi}^{\rm eik}(\ve{R},\ve{r})&\flim{Z}{+\infty}&e^{i \chi_{cT}(\ve{b},\ve{s})+ i\chi_{nT}(\ve{b},\ve{s})} \phi_{0}(\ve{r})\nonumber\\
&=& e^{i\chi^C_{PT}(b)+i\chi^C(\ve{b},\ve{s}) +i \chi^N(\ve{b},\ve{s})}\phi_{0}(\ve{r}),\label{eq6}
\end{eqnarray}
with the eikonal phases  defined as
\begin{equation}
\chi_{(c,n)T}(\ve{b},\ve{s})=-\frac{1}{\hbar v} \int^{+\infty}_{-\infty} V_{(c,n)T} (\ve{b_{(c,n)T}},Z)\ \mathrm{d}Z.\label{eq7}
\end{equation}
The phases $\chi^N$ corresponds to the nuclear  potential and the Coulomb phases  $\chi^C$ and $\chi^C_{PT}=2\eta \ln (Kb)$ to the Coulomb tidal force and the $P$-$T$ Coulomb scattering, respectively.
 The eikonal solutions~\eqref{eq6} can be interpreted semiclassically as $P$ following a straight-line trajectory and accumulating a phase through its interaction with $T$ during the collision. The main advantage of this model is that  the whole information about the collision is contained within the eikonal phases.
 This model is restricted to high energies, i.e.\ above 60$A$~MeV, where straight-line trajectories make sense.

  Compared to more elaborate models, e.g.\ CDCC and the DEA, the eikonal model exhibits an additional symmetry across the plane of the projectile's internal transverse  coordinate~$\ve{s}$~\cite{BCDS09}. Consequently, the breakup distributions as a function of the relative $c$-$n$ parallel-momentum    are symmetric. One can also note that the eikonal solutions~\eqref{eq6} {at large $b$s} do not tend asymptotically to the {ones obtained with the perturbation theory}. Moreover,  the adiabatic approach is incompatible with the infinite range of the Coulomb interaction. The eikonal phases are therefore not well defined for this interaction and the eikonal breakup matrix elements diverge~\cite{CBS08}.

		\subsection{Coulomb-corrected eikonal approximation}\label{Sec2D}

   The CCE~\cite{MBB03} was developed to remove the divergence from the breakup matrix element. The idea is to replace within the matrix element the diverging  Coulomb first-order term $\chi^C$ by the Coulomb first-order-perturbation approximation $\chi^C_{{\rm FO}}$~[see Eq.~{~\eqref{eq13}} below]~\cite{MBB03,CBS08}
 \begin{eqnarray}
e^{i\chi^C_{PT}} e^{i\chi^C}  e^{i\chi^N} \to e^{i\chi^C_{PT}}\left(e^{i\chi^C}-i\chi^C +i\chi^C_{{\rm FO}}\right) e^{i\chi^N}.	\label{eq8}
 \end{eqnarray}
 In the CCE~\cite{MBB03,CBS08}, $\chi_C^{{\rm FO}}$ is approximated by its dipole contribution, which is dominant for $^{11}\rm Be$~\cite{CB05}.
Beside removing the divergence, this model  {partly} corrects the asymptotic  behavior {at large $b$s} and does not exhibit the additional symmetry of the eikonal model. Nevertheless,  the nuclear and Coulomb interactions are not treated on the same footing.

	\subsection{Simplified dynamical eikonal approximation}\label{Sec2E}

In this work, we develop a simplification to the DEA, combining the simplicity of the usual eikonal model while removing its divergence and  treating both interactions within a unique framework. This model is based on a unitary transformation of the wave function $\widehat{\Psi}$ of Eq.~\eqref{eq4}
			\begin{eqnarray}
	\widetilde{\Psi}(\ve{R},\ve{r}) &=&e^{\frac{i}{\hbar v}\left[\left(h_{cn}-E_0\right){Z}+\int^Z_{-\infty} V^C_{PT}(R') dZ'\right]} \widehat{\Psi}(\ve{R},\ve{r}),\label{eq9}
	\end{eqnarray}
	where $V^C_{PT}$ is the $P$-$T$ Coulomb interaction.
The three-body \Sch equation~\eqref{eq5} thus becomes
	\begin{eqnarray}
	  \lefteqn{	i\hbar v \pderiv{}{Z} \widetilde{\Psi}(\ve{R},\ve{r})=}\nonumber \\
	&&\hspace{-0.3cm}e^{\frac{i}{\hbar v}h_{cn}Z}[V_{cT}(R_{cT})+V_{nT}(R_{nT})-V^C_{PT}(R)]e^{-\frac{i}{\hbar v}h_{cn}Z}\nonumber \\
	&&\hspace{1cm}\times\widetilde{\Psi}(\ve{R},\ve{r}). \label{eq10}
	\end{eqnarray}
Note that Eq.~\eqref{eq10} is equivalent to the DEA equation~\eqref{eq5} and is at the basis of all perturbation treatments~\cite{Joa75}.

	Here, we adopt another strategy, we  approximate the solution {of Eq.~\eqref{eq10} by only keeping the first term in the exponent of its Magnus expansion or, equivalently, the first factor of its Fer expansion} \cite{M54,F58,W67}
	\begin{eqnarray}
 		\lefteqn{\widetilde{\Psi}(\ve{R},\ve{r})\approx}\nonumber \\
 		&& e^{-\frac{i}{\hbar v}\int_{-\infty}^{Z} e^{\frac{i}{\hbar v}h_{cn}Z'}[V_{cT}(R'_{cT})+V_{nT}(R'_{nT})-V^C_{PT}(R')]e^{-\frac{i}{\hbar v}h_{cn}Z'}dZ'}\nonumber \\
 		&& \hspace{1cm}\times\phi_{0}(\ve{r}),\label{eq11}
\end{eqnarray}
where $R'_{cT}$, $R'_{nT}$ and $R'$ depend on $Z'$. {Asymptotically, this new wave function tends to the ground state of the projectile, i.e., $\widetilde{\Psi}(\ve{R},\ve{r}) \flim{Z}{- \infty} \phi_0(\ve{r})$.} With this approximation, we neglect all the terms containing commutators, appearing in higher-orders terms of both Magnus and Fer expansions.

To compute the breakup matrix element, we make a second approximation; we replace the operators $h_{cn}$ in the exponentials~\eqref{eq11} by the eigenvalues corresponding to the closest wave function, i.e., the final energy $E$ on the left-hand side and the initial energy $E_0$ on the right-hand side. We therefore obtain an eikonal-like model where the exponential of the eikonal phases within the breakup matrix element is replaced according to
\begin{eqnarray}
e^{i\chi^C_{PT}} e^{i\chi^C} e^{i\chi^N} \to e^{i\chi^C_{PT}}e^{i\chi^C_{{\rm FO}}}e^{i\chi^N_{{\rm FO}}}\label{eq12}
\end{eqnarray}
with $\chi^{(C,N)}_{{\rm FO}}$ the first-order-perturbation approximations of respectively the Coulomb and nuclear interactions~\cite{AW75}.

 The Coulomb part is evaluated analytically~\cite{AS64}
 \begin{eqnarray}
\chi^C_{{\rm FO}}(\ve{b},\ve{r})=& -\eta \int_{-\infty}^{+\infty}e^{i\frac{\omega Z}{v}}\left(\frac{1}{R_{cT}}-\frac{1}{R}\right) dZ\label{eq13}\\
=&-2\eta \left[e^{i\frac{\omega}{v}\frac{m_n}{m_P}z}K_0\left(\frac{\omega}{v}b_{cT}\right)-K_0\left(\frac{\omega}{v}b\right)\right]\label{eq14}
\end{eqnarray}
where $\omega=\frac{E-E_0}{\hbar}$, $m_P=m_n+m_c$, and $\eta= Z_TZ_P e^2/(4\pi \epsilon_0 \hbar v)$ is the $P$-$T$ Sommerfeld parameter. Compared to the CCE which only uses the dipole contribution, we consider the whole Coulomb first-order-perturbation  approximation. However, as previously mentioned, for $^{11}\rm Be$, the higher multipoles do not contribute significantly.

{We rewrite the nuclear part of the first-order-perturbation approximation as}
\begin{eqnarray}
\chi^N_{{\rm FO}}(\ve{b}, \ve{r})&=& - \frac{1}{\hbar v}  \int_{-\infty}^{+\infty}e^{ i\frac{\omega Z}{v}}
\Bigg\{
e^{-i \frac{\omega}{ v } \frac{m_c}{m_P} z}  V_{nT}\left(\sqrt{b_{nT}^2+Z^2}\right)\nonumber\\
&&\hspace{-1.6cm}+e^{i \frac{\omega}{ v} \frac{m_n}{m_P}z} \bigg[V_{cT}\left(\sqrt{b_{cT}^2+Z^2}\right)-\frac{\hbar v\eta}{\sqrt{b_{cT}^2+Z^2}}\bigg] \Bigg\}dZ\label{eq15}
\end{eqnarray}
and we compute this integral  numerically.
 Additionally to its simple implementation, the S-DEA wave functions  naturally tend asymptotically to the first-order of the perturbation theory {at large $b$s}. Moreover, this model does not introduce the additional symmetry of the eikonal model across the plane defined by $\ve{s}$.

{Approximation \Eq{eq12} has a serious drawback, caused by the imaginary part of the first-order-perturbation approximations~\eqref{eq14}--\eqref{eq15}. When the imaginary part of the first-order-perturbation approximation is negative, the cross sections may take unrealistic values 	as $\exp[i\chi^C_{\rm FO}+i\chi^N_{\rm FO}]$ then involve increasing real exponentials.
This problem is   enhanced by  the use of optical potentials. 	Such potentials contain an imaginary part simulating the absorption into channels other than the elastic one in the core or neutron interaction with the target.   Consequently, the Hamiltonian is not Hermitian and the $S$-matrix looses its unitarity. Even for purely real potentials, an imaginary part would arise from the imaginary exponential multiplying the potentials. }
{To partly cure   this problem, we treat separately the absorptive part of the potentials with the usual eikonal approximation. This ensures that the imaginary parts of the optical potentials suppress the unphysical contributions.  The S-DEA model is thus defined by }
\begin{eqnarray}
 e^{i\chi^C_{PT}}  e^{i\chi^C} e^{i\chi^N} \to e^{i\chi^C_{PT}}  e^{i\chi^C_{{\rm FO}}}e^{i\chi^N_{{\rm S-DEA}}}\label{eq16}
\end{eqnarray}
{with}
\begin{eqnarray}
\chi^N_{{\rm S-DEA}}(\ve{b}, \ve{r}) = \mathrm{Im}\, \chi^N(\ve{b}, \ve{r}) \nonumber \\
- \frac{1}{\hbar v}  \int_{-\infty}^{+\infty}e^{ i\frac{\omega Z}{v}}
\Bigg\{e^{-i \frac{\omega}{ v } \frac{m_c}{m_P} z}{ \rm Re} \,V_{nT}\left(\sqrt{b_{nT}^2+Z^2}\right) \nonumber \\
+e^{i \frac{\omega}{ v} \frac{m_n}{m_P}z} \bigg[{ \rm Re}\,V_{cT}\left(\sqrt{b_{cT}^2+Z^2}\right)-\frac{\hbar v\eta}{\sqrt{b_{cT}^2+Z^2}}\bigg]
\Bigg\}dZ\label{eq17}
\end{eqnarray}
where $\chi^N$ has been defined in {Sec.}~\ref{Sec2C}.

\section{Results}\label{Sec3}

	 In this article, we study the S-DEA with the breakup of $^{11}\rm Be$ on $^{12}\rm C$  and  $^{208}\rm Pb$ targets. We use the same description of $^{11}\rm Be$ as in Refs.~\cite{CGB04,CBS08}:  it is seen  as  $^{10}\rm Be$ core in its $0^+$ ground state to which a neutron is bound by $0.504$~MeV. The $^{10}\rm Be$-$n$ interaction  is simulated by a Woods-Saxon potential and a spin-orbit term,  adjusted to the three first levels: $1/2^+$, $1/2^-$ and $5/2^+$, modelled respectively as a $1s1/2$ state,  a $0p1/2$ state and  a $d5/2$ resonance. The parameters of this $^{10}\rm Be$-$n$ potential are given in Ref.~\cite{CGB04}. The $^{10}\rm Be$-$T$ and $n$-$T$ interactions are simulated through the same optical potentials as in Ref.~\cite{CBS08}. Our eikonal, CCE and DEA calculations have the same numerical inputs  as in   Ref.~\cite{CBS08}. The numerical computations of the S-DEA  use the same meshes as  the CCE.

	 \begin{figure*}
	 	\center
	 		 	{\includegraphics[width=0.45\linewidth]{Fig11Be12CSdE.eps}}
	 	\hspace{0.5cm}
	 	{\includegraphics[width=0.45\linewidth]{Fig11Be208PbSdE.eps}}
	 	\caption{Diffractive breakup cross sections of $^{11}\rm Be$ with  (a) $^{12}\rm C$ at $67A$~MeV and (b) $^{208}\rm Pb$ at 69$A$~MeV  as a function of the  $^{10}\mathrm{Be}$-$n$ relative energy $E$. In  panel (a), we also plot a zoom of the energy distributions between 3~MeV and 3.5~MeV. } \label{FigSbudE}
	 \end{figure*}
To evaluate the accuracy of the S-DEA, we compute the breakup cross section as a function of the relative $c$-$n$ energy, displayed in Fig.~\ref{FigSbudE}. The panel (a) corresponds to a  nuclear-dominated breakup,  $^{11}\rm Be$ on $^{12}\rm C$ at $67A$~MeV, and the panel (b) to a Coulomb-dominated reaction, $^{11}\rm Be$ on $^{208}\rm Pb$ at $69A$~MeV. For these two reactions, the DEA (solid red lines) reproduces well the RIKEN data~\cite{Fetal04,BCG05,GBC06} and is used as reference. As previously mentioned, the eikonal model (dashed green lines) does not treat properly the Coulomb interaction and therefore requires the use of an upper cutoff $b_{\rm max}$ to provide breakup calculations~\cite{AS00}. With this cutoff, the usual eikonal model leads to results close to the DEA ones for the nuclear-dominated reaction but fails to describe the Coulomb-dominated breakup, due to the incompatibility of this long-range interaction with the adiabatic assumption.

Both panels (a) and (b) of Fig.~\ref{FigSbudE} show that the CCE (dash-dotted blue lines) improves the eikonal treatment of the Coulomb interaction and gives accurate energy distributions for both reactions. Let us first consider the approximation defined by \Eq{eq12}. For the nuclear-dominated breakup distribution (a), it leads to exactly the same results (dotted magenta lines) as the CCE at $E<1.5$~MeV. The Coulomb-dominated cross section (b) shows that it is accurate at $E<2.5$~MeV. Indeed, even if it slightly overestimates the peak of the distribution, it lies close to the DEA and the CCE. For both reactions, the approximation \eqref{eq12} starts to increase at higher energies and completely fails to reproduce the shape and the magnitude of the breakup cross section. These unrealistic values are due to a lack of absorption at small $b$s within the model. {As explained in Sec.~\ref{Sec2E},  the real parts of the potentials contribute to the imaginary parts of the phases~\eqref{eq14}--\eqref{eq15}. These contributions    decrease the absorption and lead to unrealistic values of the cross section.}

{To suppress these unphysical contributions of the real part of the potentials, we treat separately the real and  imaginary  parts of the nuclear potential.}
As shown in \Eq{eq16}, the S-DEA is applied to the Coulomb potential and the real part of the nuclear potentials. The imaginary part of the nuclear interaction is treated with the usual eikonal model. The corresponding distributions are plotted in  dash-dotted-dotted  black lines. For both  collisions with   carbon and lead targets, the S-DEA is accurate over the whole considered  energy range. Note that, the distribution of the  Coulomb-dominated breakup  still exhibits an unphysical increase at $E=12$~MeV, {caused by the imaginary part of the} Coulomb first-order  approximation~\eqref{eq14}. However, at these energies, the breakup cross section is negligible. There is no such increase in the nuclear-dominated collision since the Sommerfeld parameter $\eta$ and thus the Coulomb first-order-perturbation  approximation are smaller.

\begin{figure*}
	\center
	{\includegraphics[width=0.45\linewidth]{Fig11Be12CSdkp.eps}}
	\hspace{0.5cm}
		{\includegraphics[width=0.45\linewidth]{Fig11Be208PbSdkp.eps}}
	\caption{Diffractive breakup distribution of $^{11}\rm Be$ with (a)  $^{12}\rm C$ at $67A$~MeV  and (b) $^{208}\rm Pb$ at 69$A$~MeV as a function of $^{10}\rm Be$-$n$  parallel momentum. } \label{FigSbudkp}
\end{figure*}

We now consider in Fig.~\ref{FigSbudkp}(a) the breakup distribution as a function of the relative $^{10}\rm Be$-$n$ parallel momentum {[see Eq.~\eqref{eq18} below] for} the breakup of $^{11}\rm Be$ on $^{12}\rm C$ at $67A$~MeV\footnote{{We have noted that the magnitudes of the  parallel-momentum distributions in Figs. 4, 5, 8 and 9 of  Ref.~\cite{CBS08} are underestimated by a factor 2. }}. In this case, the eikonal model does not display a divergence since the nuclear interaction dominates. However, it overestimates the magnitude of the cross section and does not reproduce the asymmetry of the distribution. Indeed, the eikonal distribution is perfectly symmetric, due to the additional symmetry of the projectile across the  plane defined by ${\ve{s}}$ (see Sec.~\ref{Sec2C}).  The CCE cross section lies close to eikonal results, because its Coulomb correction~\eqref{eq8} is not significant for such nuclear-dominated reaction. On the contrary, the S-DEA leads to a more accurate distribution, enhancing both shape and magnitude. This result confirms that the asymmetry of the distribution is due to dynamical effects and shows that a first-order simplification of the DEA already improves significantly the distributions. Further analyses have shown that the $d5/2$ resonance does not impact the accuracy of the S-DEA. Similarly to the energy distribution, the S-DEA underestimates the DEA magnitude.

 The parallel-momentum distributions obtained for the collision of $^{11}\rm Be$ on $^{208}\rm Pb$  at 69$A$~MeV are plotted in Fig.~\ref{FigSbudkp}(b). As for the energy distributions, the eikonal model fails to describe the parallel-momentum distribution: the  magnitude and shape of the distribution are different from the DEA predictions.  On the contrary, the CCE lies  close to the DEA results and is  precise for this Coulomb-dominated breakup. The S-DEA  slightly overestimates the peak of the distribution and is too symmetrical compared to the DEA. Since this collision is dominated by the Coulomb interaction, this difference is due to the treatment of electric transitions within the CCE and S-DEA.

To understand the origin of the asymmetry, we consider the expression of the parallel-momentum observable, which reads
 		\beq
 		\lefteqn{\frac{d\sigma_{bu}}{dk_\parallel}=\frac{8\pi}{2j_0+1}
 			\sum_{m_0}\int_0^\infty b db {\int_{|k_\parallel|}^{k_{\rm max}}} \frac{dk}{k}
 			\sum_{\nu m}}\nonumber\\
 		&&\times \left|\sum_{lj}(lI m-\nu \nu|jm)
 		Y_l^{m-\nu}(\theta_k,0)S_{kljm}^{(m_0)}(b)\right|^2,
 		\eeqn{eq18}
 		where $\theta_k=\arccos (k_\parallel/k)$ is the colatitude of the
 		$c$-$n$ relative wave vector $\ve{k}$ after breakup, $l$ is the orbital angular momentum of the $c$-$n$ system, $j$ is the total angular momentum, resulting from
 		the composition of $l$ and the spin of the neutron $I$, $m$ is its projection and $\nu$ is the projection of the spin. The subscript $0$ corresponds to the quantum numbers of the ground state $\phi_0$. The partial breakup amplitude $S_{kljm}^{(m_0)}$ is  the matrix element of the operator~\eqref{eq8} [resp.~\eqref{eq16}] for the CCE (resp. for the S-DEA) between the initial state $\phi_0$ and the final breakup state (see Eq. (25) of Ref.~\cite{CBS08}).
{The integration over $k$ is limited to $k_{\rm max}=0.7$~fm$^{-1}$ for the $\rm Pb$ target and $k_{\rm max}=1.4$~fm$^{-1}$ for the $\rm C$ target, which correspond respectively to $E_{\rm max}=11.26$~MeV and $E_{\rm max}=45$~MeV. These values are large enough to reach convergence.}

{This observable coherently sums the  partial breakup amplitudes and is therefore sensitive to their interferences.
With the property of the spherical harmonics
	\begin{equation}
	Y_{l}^{m-\nu}(\theta_k,0)=(-1)^{l+m-\nu} 	Y_{l}^{m-\nu}(\pi-\theta_k,0),
	\end{equation}
each partial-wave contribution to the parallel-momentum distribution differs by a phase $(-1)^l$ for two opposite $k_\parallel$ values, making opposite interferences between even $l$ and odd $l$ partial waves.}
In both models, the asymmetry of the distribution is caused by  the terms asymmetric in $z$,  contained in   the breakup amplitudes with odd $l+m-\nu$ as the ground state is in the $s$ wave.

	\begin{figure*}
		\center
		{\includegraphics[width=0.45\linewidth]{69AMeV11BePbCCESbudkpla.eps}}
		\hspace{0.5cm}
		{\includegraphics[width=0.45\linewidth]{69AMeV11BePbACESbudkpla.eps}}
		\caption{Coulomb contribution to  breakup  of $^{11}\rm Be$ with  $^{208}\rm Pb$ at 69$A$~MeV obtained with the (a) CCE and (b) S-DEA as a function of $^{10}\rm Be$-$n$  parallel momentum. A cutoff at $b_{\rm min}=10$~fm is used to simulate the nuclear absorption.} \label{FigSbudkpla}
	\end{figure*}
{For a pure Coulomb breakup}, only the imaginary part of $\chi^C_{\rm FO}$ [\Eq{eq14}] is responsible for the asymmetries of the CCE and S-DEA distributions.
In the CCE, this asymmetric term contributes {at only $l=1$ and not to all $l$ as in the S-DEA}, where $\chi^C_{\rm FO}$ appears in the exponential~\eqref{eq16}. To understand how this affects the shape of the parallel-momentum distributions, we plot in Fig.~\ref{FigSbudkpla} its Coulomb contribution for the breakup of $^{11}\rm Be$ with $^{208}\rm Pb$, obtained with (a) the CCE and (b) the S-DEA.  We use a cutoff at $b_{\rm min}=10$~fm from which we compute the cross sections to simulate the nuclear absorption. As expected, the {$l=0$ term} (solid lines) leads to  symmetric distributions for both the CCE and S-DEA. For both models, the asymmetry {first} arises from the interferences of the {$l=0$ and $l=1$} terms (dashed lines). Moreover, the magnitude of the distributions increases drastically when we add the {$l=1$} term, because this  reaction is dominated by E1 transitions.

The main difference between the two models is the influence of the {$l=2$} term: in the CCE, it barely influences the shape of the distribution while in the S-DEA, it makes it more symmetric. {In the CCE, the {$l=2$} term depends on $\chi^C$ [\Eq{eq8}], which is symmetric. Since the collision is dominated by E1 transitions, it does not impact much the distribution.} In the S-DEA, the {$l=2$} term depends on $\chi_{{\rm FO}}^C$, and thus also contains an asymmetric {component. However, it contributes in an opposite way to the {$l=1$} term, i.e., more to positive $k_\parallel$ values. It} tends to diminish the asymmetry of the distribution. Therefore, each  {{partial wave $l$} influences the asymmetry in the S-DEA and the total effect reduces} the asymmetry due to the E1 transition.

{The asymmetry of the breakup distribution of $^{11}\rm Be$ with $^{12}\rm C$ in Fig.~\ref{FigSbudkp} obtained at the S-DEA can  also be analysed. In this case, the nuclear interaction dominates and  therefore the asymmetry is mainly influenced by the imaginary part of  $\chi^N_{\rm S-DEA}$~\eqref{eq17}. Contrary to the Coulomb case, this phase has two  imaginary exponentials, one depending on $-z$, and another one on $+z$. Therefore, ${\rm Im}\,\chi^N_{\rm S-DEA}$  contains two   asymmetric terms which have an opposite sign and their sum  depends on  $z$,  $b_{cT}$ and $b_{nT}$.  This complex dependence implies that  the partial waves with odd and even $l$ do not necessarily have opposite contributions to the asymmetry of the parallel-momentum distribution.  In this case, we have observed that in a pure nuclear calculation, both odd and even partial waves $l$ contribute to the asymmetry, i.e, push the distribution to negative $k_\parallel$.   Contrary to the Coulomb-dominated reaction, the asymmetry of the total distribution (in Fig.~\ref{FigSbudkpla}) is overestimated. This  analysis suggests that the S-DEA improves the descriptions of electric and nuclear transitions but still misses part of the dynamics of the reaction.}

In conclusion, the S-DEA with a separate treatment of the real and imaginary parts of the nuclear potential leads to  accurate energy distributions for both nuclear- and Coulomb-dominated breakups. We have also shown that the S-DEA improves the  parallel-momentum distribution for both reactions compared to the usual eikonal model. Moreover, the S-DEA reproduces better the asymmetry of the distribution of nuclear-dominated breakup compared to the CCE. It misses however part of the asymmetry of the Coulomb-dominated distribution, due to destructive interferences between different partial waves, decreasing the {asymmetry} of the distribution.

\section{Conclusions}\label{Conclusions}
To infer reliable information from breakup observables, one needs an accurate reaction model coupled with a realistic description of the collision. The eikonal model  has the advantage of being  cheap from a computational viewpoint, while keeping the quantal description of the collision. Unfortunately,  it does not treat well the Coulomb interaction, causing a divergence within the breakup matrix element.

We develop in this work a simplification to the DEA, which has a similar numerical cost as the usual eikonal approximation. This model  is based on an approximation of the solutions of the DEA wave functions. We make a second approximation by replacing the internal Hamiltonian by their eigenvalues within the breakup matrix element. This leads to an eikonal-like model, where the eikonal phases are replaced by the first-order-perturbation approximations. Compared to the  eikonal model, this model does not require any cutoff and {its wave functions tend to the first-order-perturbation theory}. These approximations are applied to only the real part of the potentials, leaving the imaginary part to the usual eikonal model. This avoids a lack of absorption and gives precise energy distributions.

The S-DEA also improves  the breakup distribution as a function of the  $^{10}\rm Be$-$n$ parallel momentum. Compared to the usual eikonal model, it lies closer to the DEA results.  For nuclear-dominated breakup, the S-DEA improves both the shape and the magnitude of the distribution, confirming that the asymmetry is due to dynamical effects during the collision. It is therefore an excellent model to describe both energy distribution and parallel-distribution observables of breakup with light targets. The S-DEA does however not reproduce the asymmetry of the parallel-momentum distribution of {this Coulomb-dominated reaction. The  contribution of higher multipoles {of the wave function} weakens the interferences caused by the dominant E1 transition.}

Since the S-DEA  elegantly solves  the Coulomb divergence within the eikonal model and significantly enhances  its accuracy while keeping a small numerical cost, it would be interesting to study its extension  to three-body projectiles, such as two-neutron halo nuclei. As there are still some differences with the DEA, higher-order approximations of the DEA solutions could be studied. A first step could be to improve the crude approximation of the exponential operators of \Eq{eq11} within the breakup matrix elements. This could be done by expanding the wave function onto a basis of eigenstates and pseudostates for the $c$-$n$ continuum of the internal Hamiltonian (as in CDCC~\cite{Kam86,YOMM12}). The  matrix elements could then be obtained  through a diagonalization method~\cite{AW60,AW75,BH73} and an interpolation of the energies.

\begin{acknowledgements}
	We thank P. Capel for interesting discussions on this topic.	C.~Hebborn acknowledges the support of the Fund for Research Training in Industry and Agriculture (FRIA), Belgium.  This project has received funding from the European Union’s Horizon 2020 research	and innovation program under grant agreement 	No 654002. This work was supported by the Fonds de la Recherche Scientifique - FNRS under Grant Number 4.45.10.08.
\end{acknowledgements}

\bibliographystyle{apsrev}


\section{Introduction}
Many high-performance algorithms
for solving computationally hard problems,
ranging from exact methods such as mixed integer
programming solvers to heuristic methods such
as local search,
involve a large number of free parameters that need to be
carefully tuned to achieve their best performance.
In many cases, finding performance-optimizing
parameter settings is performed manually in an ad-hoc way.
However, the manually-tuning approach is often intensive
in terms of human effort \cite{lopez2016irace}
and thus there are a lot of attempts on automating this process
(see \cite{hutter2009paramils} for a comprehensive review),
which is usually referred to as
automatic algorithm configuration (AAC) \cite{Hoos121}.
Many AAC methods such as ParamILS \cite{hutter2009paramils},
GGA/GGA+\cite{ansotegui2009gender,AnsoteguiMSST15},
irace \cite{lopez2016irace} and SMAC \cite{hutter2011sequential}
have been proposed in the last few years.
They have been
used for boosting the algorithm's performance in
a wide range of domains such as
the boolean satisfiability problem (SAT) \cite{hutter2009paramils},
the traveling salesman problem (TSP) \cite{lopez2016irace,LiuT019},
the answer set programming (ASP) \cite{HutterLFLHLS14}
and machine learning \cite{FeurerKESBH15,KotthoffTHHL17}.

Despite the notable success achieved in application,
the theoretical aspects of AAC have been rarely investigated.
To our best knowledge, for AAC the first
theoretical analysis was given by \citet{Birattari2004},
in which the author analyzed expectations and
variances of different performance estimators that estimate the
true performance of a given parameter configuration on the basis
of $N$ runs of the configuration. It
is concluded in \cite{Birattari2004} that
performing one single run on $N$ different problem instances guarantees
that the variance of the estimate is minimized,
which has served as a guidance in the design of the
performance estimation mechanisms in later AAC methods including irace, ParamILS and SMAC.
It is noted that the analysis in \cite{Birattari2004} assumes
that infinite problem instances could be sampled
for configuration evaluation.
However, in practice we are often only given
a set of finite training instances \cite{Hoos121}.

Recently, \citet{KleinbergLL17} introduced
a new algorithm configuration framework named
Structured Procrastination (SP),
which is guaranteed to find an approximately optimal parameter configuration
within a logarithmic factor of the optimal runtime in a worst-case sense.
Furthermore, the authors showed
that the gap between worst-case runtimes of
existing methods (ParamILS, GGA, irace, SMAC) and SP
could be arbitrarily large.
These results were later extended in
\cite{WeiszGS18,WeiszGS19}, in which the authors
proposed new methods, called LEAPSANDBOUNDS (LB) and
CapsAndRuns (CR),
with better runtime guarantees.
However, there is a discrepancy between
the algorithm configuration problem
addressed by these methods (SP, LB and CR)
and the problem that is most
frequently encountered in practice.
More specifically, these methods are designed to
find parameter configurations with approximately optimal
performances on the input (training) instances;
while in practice it is more desirable
to find parameter
configurations that will perform well on
new unseen instances rather than
just the training instances \cite{Hoos121}.
Indeed, one of the most critical issues
that needs to be addressed in AAC is the over-tuning
phenomenon \cite{Birattari2004},
in which the found parameter configuration is with
excellent training performance,
but performs badly on new instances
\footnote{
To appropriately evaluate AAC methods,
in the literature,
including widely used benchmarks (e.g., AClib \cite{HutterLFLHLS14})
and major contests (e.g., the Configurable SAT Solver Challenge (CSSC) \cite{HutterLBBHL17}),
the common scheme is to use an independent test set
that has never been used during the configuration procedures to
test the found configurations.}.

Based on the above observation, this paper extends
the results of \cite{Birattari2004} in several aspects.
First, this paper introduces a new formulation of the algorithm configuration problem
(Definition~\ref{def:AAC_definition}),
which concerns the optimization of the
expected performance of the configured
algorithm on an instance distribution $\mathcal{D}$.
Compared to the one considered by \citet{Birattari2004}
in which $\mathcal{D}$ is directly given
(thus could be sampled infinitely),
in the problem considered here $\mathcal{D}$
is unknown and inaccessible,
and the assumption
is that the input training instances (and the test instances) are
sampled $i.i.d$ from $\mathcal{D}$.
Therefore when solving this configuration problem,
we can only use the given finite training instances.
One key difficulty is that
the true performance of a parameter configuration is unachievable.
Subsequently, we could only run a configuration on
the training instances to obtain an estimate
of its true performance.
Thus a natural and important question is that,
given finite computational budgets,
e.g., $N$ runs of the configuration,
how to allocate them over the training instances
to obtain the most reliable estimate.
Moreover, given that we could obtain an
estimate of the true performance,
is it possible to quantify the difference
between the estimate and the true performance?

The second and the most important contribution of this paper
is that it answers the above questions theoretically.
More specifically,
this paper first introduces a universal best
performance estimator (Theorem~\ref{theorem:best_estimator})
that always distributes
the $N$ runs of a configuration to all training instances
as evenly as possible, such that
the performance estimate is most reliable.
Then this paper investigates the estimation error,
i.e., the difference between the training performance (the estimate)
and the true performance, and establishes
a bound on the estimation error
that holds for all configurations in the
configuration space, considering the cardinality
of the configuration space is finite (Theorem~\ref{theorem:finite}).
It is shown that the bound
deteriorates as the number of the considered configurations increases.
Since in practice the cardinality
of the configuration space
considered could be considerably large or even infinite,
by making two mild assumptions
on the considered configuration scenarios,
we remove the dependence on  the cardinality
of the configuration space
and finally establish a new bound on the estimation error
(Theorem~\ref{theorem:infinite}).

The effectiveness of these results have been
verified in extensive experiments conducted on four configuration
scenarios involving problem domains including SAT, ASP and TSP.
Some potential directions for improving current
AAC methods from these results
have also been identified.

\section{Algorithm Configuration Problem}
\label{sec:2}
In a nutshell, the algorithm configuration problem concerns optimization
of the free parameters of a given parameterized algorithm (called target algorithm)
for which the performance is optimized.

Let $\mathcal{A}$ denote the target algorithm and
let $p_{1},...,p_{h}$ be parameters of $\mathcal{A}$.
Denote the set of possible values for each parameter $p_{i}$
as $\Theta_{i}$.
A parameter configuration $\theta$ (or simply configuration)
of $\mathcal{A}$ refers to a complete setting of $p_{1},...,p_{h}$,
such that the behavior of $\mathcal{A}$
on a given problem instance is completely specified (up to
randomization of $\mathcal{A}$ itself).
The configuration space $\bm{\Theta} = \Theta_{1} \times \Theta_{2}...\times \Theta_{h}$
contains all possible configurations of $\mathcal{A}$.
For brevity, henceforth we will not distinguish
between $\theta$ and the instantiation of $\mathcal{A}$
with $\theta$.
In real application $\mathcal{A}$ is often randomized and its output is determined
by the used configuration $\theta$, the input instance $z$
and the random seed $v$.
Let $\mathcal{D}$ denote a probability distribution over a
space $\mathcal{Z}$ of problem instances from which
$z$ is sampled.
Let $\mathcal{G}$ be
a probability distribution
over a space $\mathcal{V}$ of random seeds from which $v$ is sampled.
In practice $\mathcal{G}$ is often given implicitly through a random
number generator.

Given an instance $z$ and a seed $v$, the quality of $\theta$ at $(z, v)$
is measured by a utility function $f_{\theta}:\mathcal{Z} \times \mathcal{V} \rightarrow [L,U]$,
where $L,U$ are bounded real numbers.
In practice, it means running $\theta$ with $v$ on $z$,
and maps the result of this run to a scalar score.
Note how the mapping is done depends on the considered performance metric.
For examples, if we are interested in optimizing quality of
the solutions found by $\mathcal{A}$,
then we might take the (normalized) cost of the solution
output by $\mathcal{A}$ as the utility;
if we are interested in minimizing computational
resources consumed by $\mathcal{A}$ (such as runtime,
memory or communication bandwidth),
then we might take the quantity of the consumed
resource of the run as the utility.
No matter which performance metric is considered,
in practice the value of $f_{\theta}$ is bounded
for all $\theta \in \bm{\Theta}$,
i.e., for all $\theta \in \bm{\Theta}$ and all
$(z,v) \in \mathcal{Z} \times \mathcal{V}$,
$f_{\theta}(z,v) \in [L, U]$.

To measure the performance of $\theta$,
the expected value of the utility scores of $\theta$ across
different $(z,v)$, which is the most widely adopted criterion
in AAC applications
\cite{Hoos121}, is considered here.
More specifically,
as presented in Definition~\ref{def:AAC_definition},
the performance of $\theta$, denoted as $u(\theta)$, is its expected utility
score over instance distribution $\mathcal{D}$ and
random seed distribution $\mathcal{G}$.
Without loss of generality, we always assume a smaller value is better
for $u(\theta)$.
The goal of the algorithm configuration problem is to find a
configuration from the configuration
space $\bm{\Theta}$ with the best performance.

\begin{definition}[Algorithm Configuration Problem]
\label{def:AAC_definition}
  Given a target algorithm $\mathcal{A}$ with configuration space $\bm{\Theta}$,
  an instance distribution $\mathcal{D}$ defined over space $\mathcal{Z}$,
  a random seed distribution $\mathcal{G}$ defined over space $\mathcal{V}$ and
  a utility function $f_{\theta}:\mathcal{Z} \times \mathcal{V} \rightarrow [L,U]$ that
  measures the quality of $\theta$ at $(z, v)$,
  the algorithm configuration problem is to find a configuration $\theta^{\star}$ from
  $\bm{\Theta}$ with the best performance:
  \[
  \label{eq:denitionofutheta}
    \theta^{\star} \in \argmin_{\theta \in \bm{\Theta}} u(\theta),
  \]
  where  $u(\theta) = \mathbb{E}_{z \sim \mathcal{D}, v \sim \mathcal{G}}[f_{\theta}(z,v)]$.
\end{definition}
In practice, $\mathcal{D}$ is usually unknown
and the analytical
solution of $u(\theta)$ is unachievable.
Instead, usually we have a set of problem instances $\{z_{1},...,z_{K}\}$, called training instances, which are assumed
to be sampled $i.i.d$ from $\mathcal{D}$.
To estimate $u(\theta)$, a series of experiments of $\theta$ on $\{z_1, z_2,...,z_K\}$
could be run.
As presented in Definition~\ref{def:exsetting},
an experimental setting $S_{N}$ to estimate $u(\theta)$
is to run $\theta$ on $\{z_{1},...,z_{K}\}$ for $N$ times,
each time with a random seed sampled $i.i.d$ from $\mathcal{G}$.
\begin{definition}[Experimental Setting $S_{N}$]
\label{def:exsetting}
  Given a configuration $\theta$, a set of $K$ training instances $\{z_{1},...,z_{K}\}$ and
  the total number $N$ of runs of $\theta$,
  an experimental setting $S_{N}$ to estimate $u(\theta)$
  is a list of $N$ tuples, in which each tuple $(z,v)$ consists
  of an instance $z$ and a random seed $v$, meaning a single run
  of $\theta$ with $v$ on $z$. Let $n_{i}$ denote the number of runs
  performed on $z_{i}$ (note $n_{i}$ could be 0, meaning $\theta$
  will not be run on $z_{i}$).
  It holds that $\sum_{i=1}^{K} n_{i}=N$
  and $S_{N}$ could be written as:
  \[
    \begin{aligned}
    S_{N}=[&(z_{1}, v_{1,1}),...,(z_{1},v_{1,n_{1}}),...,(z_{i}, v_{i,1}),...,\\
    &(z_{i},v_{i,n_{i}}),...,(z_{K}, v_{K,1}),...,(z_{K},v_{K,n_{K}})].
    \end{aligned}
  \]
\end{definition}
After performing the $N$ runs of $\theta$ as specified in $S_{N}$,
the utility scores of these runs are aggregated to
estimate $u(\theta)$.
The following estimator $\hat{u}_{S_{N}}(\theta)$, which calculates the
mean utility across all runs and
is widely adopted in AAC methods \cite{hutter2009paramils,lopez2016irace,hutter2011sequential},
is presented in Definition~\ref{def:estimator}.

\begin{definition}[Estimator $\hat{u}_{S_{N}}(\theta)$]
\label{def:estimator}
  Given a configuration $\theta$ and an experimental setting $S_{N}$,
  the training performance of $\theta$, which is
  an estimate of $u(\theta)$, is given by:
  \[
  \label{eq:estimator}
    \hat{u}_{S_{N}}(\theta) = \frac{1}{N}\sum_{i=1}^{K}\sum_{j=1}^{n_{i}}f_{\theta}(z_{i}, v_{i, j}).
  \]
\end{definition}

Since different experimental settings represent different performance estimators,
which have different behaviors.
It is thus necessary to investigate which $S_N$
is the best.

\section{Universal Best Performance Estimator}
\label{section3}
To determine the values of $n_{1},...,n_{K}$ in $S_{N}$,
\citet{Birattari2004} analyzed expectations and variances of
$\hat{u}_{S_{N}}(\theta)$,
and concluded that $\hat{u}_{S^{\circ}_{N}}(\theta)$
with $S^{\circ}_{N}:=[(z_{1}, v_{1,1}),(z_{2},v_{2,1}),...,(z_{N},v_{N,1})]$
has the minimal variance.
It is noted that the analysis in \cite{Birattari2004}
assumes that infinite problem instances could be sampled from $\mathcal{D}$;
thus for performing $N$ runs of $\theta$, as specified in $S^{\circ}_{N}$,
it is always the best to
sample $N$ instances from $\mathcal{D}$ and perform one single run of $\theta$ on each
instance.
In other words, $S^{\circ}_{N}$ is established
on the basis that the number of the training
instances $K$ could always be set equal to $N$.
However, in practice usually we only have a finite number of training instances.
In the case that $K \not= N$, which $S_{N}$ is the
best?
Theorem~\ref{theorem:best_estimator} answers this question for arbitrary relationship
between $K$ and $N$.
Before presenting Theorem~\ref{theorem:best_estimator},
some necessary definitions are introduced.

Given a configuration $\theta$ and an instance $z$,
the expected utility of $\theta$ within $z$,
denoted as $u_{z}(\theta)$, is $\mathbb{E}_{\mathcal{G}}[f_{\theta}(z,v)|z]$.
The variance of the utility of $\theta$ within $z$,
denoted as $\sigma^{2}_{z}(\theta)$,
is $\mathbb{E}_{\mathcal{G}}[(f_{\theta}(z,v)-u_{z}(\theta))^{2}|z]$.
Based on $u_{z}(\theta)$ and $\sigma^{2}_{z}(\theta)$,
the expected within-instance variance $\bar{\sigma}^{2}_{WI}(\theta)$ of $\theta$
and the across-instance variance $\bar{\sigma}^{2}_{AI}(\theta)$ of $\theta$
are defined in Definition~\ref{def:within_instance} and
Definition~\ref{def:across_instance}, respectively.
\begin{definition}[Expected within-instance Variance of $\theta$]
  $\bar{\sigma}^{2}_{WI}(\theta)$
  is the expected value of $\sigma^{2}_{z}(\theta)$ over instance distribution $\mathcal{D}$:
  \small
  \[
    \bar{\sigma}^{2}_{WI}(\theta) = \mathbb{E}_{\mathcal{D}}[\sigma^{2}_{z}(\theta)].
  \]
\label{def:within_instance}
\end{definition}
\begin{definition}[Across-instance Variance of $\theta$]
  $\bar{\sigma}^{2}_{AI}(\theta)$
  is the variance of $u_{z}(\theta)$ over instance distribution $\mathcal{D}$:
  \small
  \[
    \bar{\sigma}^{2}_{AI}(\theta) = \mathbb{E}_{\mathcal{D}}[(u_{z}(\theta) - u(\theta))^{2}].
  \]
\label{def:across_instance}
\end{definition}
The expectation and the variance of an estimator $\hat{u}_{S_{N}}(\theta)$ are presented
in Lemma~\ref{lem:unbiased} and Lemma~\ref{lem:variance}, respectively.
The proofs are omitted here due to space limitations.

\begin{lemma}
\label{lem:unbiased}
 The expectation of $\hat{u}_{S_{N}}(\theta)$ is $u(\theta)$, that is,
 $\hat{u}_{S_{N}}(\theta)$ is an unbiased estimator of $u(\theta)$ no matter
 how $n_{1},...,n_{K}$ in $S_{N}$ are set:
 \small
 \[
 	 \mathbb{E}_{S_{N}}[\hat{u}_{S_{N}}(\theta)] = u(\theta).
 \]
\end{lemma}

\begin{lemma}
\label{lem:variance}
 The variance of $\hat{u}_{S_{N}}(\theta)$ is given by:
 \small
 \begin{equation}
 \label{eq:variance}
  	 \mathbb{E}_{S_{N}}[(\hat{u}_{S_{N}}(\theta)-u(\theta))^{2}] = \frac{1}{N} \bar{\sigma}^{2}_{WI}(\theta) + \frac{\Sigma_{i=1}^{K}n_{i}^{2}}{N^{2}} \bar{\sigma}^{2}_{AI}(\theta).
 \end{equation}
\end{lemma}

\begin{theorem}
\label{theorem:best_estimator}
  Given a configuration $\theta$, a training set of $K$ instances and the total number $N$
  runs of $\theta$, the universal best estimator $\hat{u}_{S^{\ast}_{N}}(\theta)$
  for $u(\theta)$ is obtained by setting
  $S^{\ast}_{N}:= n_{i} \in \{\lfloor{\frac{N}{K}}\rfloor, \lceil{\frac{N}{K}}\rceil \} $
  for all $i \in \{1,2,...,K\}$, s.t. $\sum_{i=1}^{K} n_{i}=N$.
  $\hat{u}_{S^{\ast}_{N}}(\theta)$ is an unbiased estimator of $u(\theta)$ and
  is with the minimal variance among all possible estimators.
\end{theorem}
\begin{proof}

By Lemma~\ref{lem:unbiased}, $\hat{u}_{S^{\ast}_{N}}(\theta)$ is an unbiased estimator of $u(\theta)$.
  We now prove $\hat{u}_{S^{\ast}_{N}}(\theta)$ has the minimal variance. By Lemma~\ref{lem:variance}, the variance of $\hat{u}_{S_{N}}(\theta)$ is $\frac{1}{N} \bar{\sigma}^{2}_{WI}(\theta) + \frac{\Sigma_{i=1}^{K}n_{i}^{2}}{N^{2}} \bar{\sigma}^{2}_{AI}(\theta)$.
  Since $N$ and $K$ are fixed, and $\bar{\sigma}^{2}_{WI}(\theta)$ and $\bar{\sigma}^{2}_{AI}(\theta)$ are constants for a given $\theta$, we need to minimize
  $\sum_{i=1}^{K}n_{i}^{2}$, s.t. $\sum_{i=1}^{K}n_{i}=N$.
  Define $Q_{n}=\sqrt{\sum_{k=1}^{K}n_{i}^{2}}$ and $\bar{n}=\frac{\sum_{i=1}^{K}n_{i}}{K}=\frac{N}{K}$,
  it then follows that
  $Q_{n}^{2}=K\bar{n}^{2}+\sum_{i=1}^{K}(n_{i}-\bar{n}^{2})$.
  Then it suffices to prove that $Q_{n}^{2}$ is minimized on the condition $n_{i} \in \{\lfloor{\frac{N}{K}}\rfloor, \lceil{\frac{N}{K}}\rceil \}$ for all $i \in \{1,2,...,K\}$.
  Assuming $Q_{n}^{2}$ is minimized while the condition not satisfied, then there must exist
  $n_{i}$ and $n_{j}$, such that $n_{i}-n_{j}>1$;
  then we have
  $(n_{i}-\bar{n})^{2}+(n_{j}-\bar{n})^{2} > (n_{i}-\bar{n})^{2}+(n_{j}-\bar{n})^{2}-2(n_{i}-n_{j})+2 = (n_{i}-\bar{n}-1)^{2}+(n_{j}-\bar{n}+1)^{2}$.
  This contradicts the assumption that $Q_{n}^{2}$ is minimized.
The proof is complete.
\end{proof}

Theorem~\ref{theorem:best_estimator} states that it is always the best
to distribute the $N$ runs of $\theta$ to all training instances
as evenly as possible, in which case $\max_{i,j \in \{1,...,K\}} |n_{i}-n_{j}| \leq 1$,
no matter $K \neq N$ or $K=N$.
When $K=N$, $S^{\ast}_{N}(\theta)$ is actually equivalent to  $S^{\circ}_{N}$
that performs one single run of $\theta$ on each instance.
When $K \neq N$, $S^{\ast}_{N}(\theta)$ will
perform $\lceil\frac{N}{K}\rceil$ runs of $\theta$ on each of $(N\ \mathrm{mod}\ K)$ instances
and perform $\lfloor\frac{N}{K}\rfloor$ runs on each of the rest instances.
It is worth mentoring that
practical AAC methods including ParamILS,
SMAC and irace actually
adopt the same or quite similar estimators as
$S^{\ast}_{N}(\theta)$.
Theorem~\ref{theorem:best_estimator} provides a theoretical guarantee
for these estimators, and
$S^{\ast}_{N}(\theta)$ will be further evaluated in the experiments.

\section{Bounds on Estimation Error}
Although Theorem~\ref{theorem:best_estimator} presents the estimator with the
universal minimal variance, it cannot provide any information about
how large the estimation error, i.e., $u(\theta)-\hat{u}_{S_{N}}(\theta)$, could be.
Bounds on estimation error are useful in both theory and practice because
we could use them to establish bounds on the true performance $u(\theta)$,
given that in algorithm configuration process the training performance
$\hat{u}_{S_{N}}(\theta)$ is actually known.
In general,
given a configuration $\theta$,
its training performance $\hat{u}_{S_{N}}(\theta)$
is a random variable
because the training instances and the random seeds specified in $S_{N}$
are drawn from distributions $\mathcal{D}$ and $\mathcal{G}$, respectively.
Thus we focus on establishing probabilistic
inequalities for $u(\theta)-\hat{u}_{S_{N}}(\theta)$,
i.e., for any $0<\delta<1$, with probability at least $1-\delta$,
there holds $u(\theta)-\hat{u}_{S_{N}}(\theta) \leq A(\delta)$.
In particular, probabilistic bounds on uniform estimation error,
i.e., $\sup_{\theta \in \bm{\Theta}}[u(\theta)-\hat{u}_{S_{N}}(\theta)]$,
that hold for all $\theta \in \bm{\Theta}$ are established.
Recalling that Lemma~\ref{lem:unbiased} states
$\mathbb{E}_{S_{N}}[\hat{u}_{S_{N}}(\theta)] = u(\theta)$,
the key technique for deriving bounds on
$u(\theta)-\hat{u}_{S_{N}}(\theta)$ is the concentration
inequality presented in Lemma~\ref{lem:concen} that bounds how $\hat{u}_{S_{N}}(\theta)$
deviates from its expected value $u(\theta)$.

\begin{lemma}[Bernstein's Inequality \cite{bernstein1927theory}]
 Let $X_{1},X_{2},...,X_{n}$ be independent centered bounded random variables, i.e., $\mathrm{Prob}\{|X_{i}| \leq a\}=1$ and $\mathbb{E}[X_{i}]=0$.
 Let $\sigma^{2}=\frac{1}{n}\sum_{i=1}^{n}Var[X_{i}]$ where $Var[X_{i}]$ is the variance of $X_{i}$.
 Then for any $\epsilon>0$ we have
 \[
   \mathrm{Prob}\{\frac{1}{n}\sum_{i=1}^{n}X_{i} \geq \epsilon\} \leq \mathrm{exp}(-\frac{n\epsilon^{2}}{2\sigma^{2}+\frac{2a\epsilon}{3}}).
 \]
\label{lem:berstein}
\end{lemma}

\begin{lemma}
  Given a configuration $\theta$, an experimental setting
  $S_{N}=[(z_{1}, v_{1,1}),...,(z_{K},v_{K,n_{K}})]$
  and a performance estimator $\hat{u}_{S_{N}}(\theta)=\frac{1}{N}\sum_{i=1}^{K}\sum_{j=1}^{n_{i}}f_{\theta}(z_{i}, v_{i, j})$.
  Let $\tau_{\theta}^{2}=\bar{\sigma}^{2}_{WI}(\theta) + \frac{\sum_{i=1}^{K}n_{i}^{2}}{N}\bar{\sigma}^{2}_{AI}(\theta)$.
  Let $C=U-L$, where $L,U$ are the lower bound and the upper
  bound of $f_{\theta}$ respectively (see Definition~\ref{def:AAC_definition}),
  and let $n=\max\{n_{1},n_{2},...,n_{K}\}$.
  Then for any $\epsilon>0$, we have
  \[
    \mathrm{Prob}\{u(\theta) - \hat{u}_{S_{N}}(\theta)
    \geq \epsilon \}
    \leq \mathrm{exp}(-\frac{N\epsilon^{2}}{2\tau_{\theta}^{2}+\frac{2nC\epsilon}{3}}).
  \]
\label{lem:concen}
\end{lemma}
\begin{proof}
 Define random variables $x_{i,j}=u(\theta)-f_{\theta}(z_{i}, v_{i,j})$,
 and define random variables $X_{i}=\sum_{j=1}^{n_{i}}x_{i,j}$.
 First we prove that $X_{1},...,X_{K}$ satisfy the conditions in Lemma~\ref{lem:berstein}.
 $\mathbb{E}[X_{i}]=\sum_{j=1}^{n_{i}}\mathbb{E}[x_{i,j}]=\sum_{j=1}^{n_{i}}[u(\theta)-\mathbb{E}[f_{\theta}(z_{i},v_{i,j})]]=0$.
 By Definition~\ref{def:AAC_definition},
 $\mathrm{Prob}\{L \leq f_{\theta}(z_{i},v_{i,j}) \leq U\}=1$,
 it holds that $L \leq u(\theta) \leq U$ (since $u(\theta) = \mathbb{E}[f_{\theta}(z_{i},v_{i,j})]$).
 Thus we have $\mathrm{Prob}\{|x_{i,j}| \leq U-L\}=1$
 and
 $\mathrm{Prob}\{|X_{i}| \leq n(U-L) \}=1$.
 For any $p \neq q$,
 $X_{p}$ and $X_{q}$ are independent.
 Thus $X_{1},X_{2},...,X_{K}$ are independent random variables.

 Let $\bar{X}=\frac{1}{K}\sum_{i=1}^{K}X_{i}$.
 By Lemma~\ref{lem:berstein}, it holds that, for any $\epsilon>0$,
 $\mathrm{Prob}\{\bar{X} > \epsilon\} \leq \mathrm{exp}(-\frac{K\epsilon^{2}}{2\sigma^{2}+\frac{2C\epsilon}{3}})$,
 where $\sigma^{2}=\frac{1}{K}\sum_{i=1}^{K}Var[X_{i}]$.
 Notice that $\frac{K}{N}\bar{X}=u(\theta) - \hat{u}_{S_{N}}$;
 thus it holds that for any $\epsilon>0$,
 \begin{equation}
 \label{eq:midresult1}
  \mathrm{Prob}\{u(\theta) - \hat{u}_{S_{N}}>\epsilon\} \leq \mathrm{exp}(-\frac{N\epsilon^{2}}{\frac{2K}{N}\sigma^{2}+\frac{2nC\epsilon}{3}}).
 \end{equation}
  The rest of the proof focuses on $\sigma^{2}$.
  Since $E[x_{i}]=0$,
  $Var[X_{i}]=\mathbb{E}[(X_{i}-E[X_{i}])^{2}]=\mathbb{E}[X_{i}^{2}]$.
  Substitute $X_{i}$ with $\sum_{j=1}^{n_{i}}x_{i,j}$ and
  we have
  $Var[X_{i}]=\sum_{j=1}^{n_{i}}\mathbb{E}[x_{i,j}^{2}]
  +\sum_{1 \leq j < l \leq n_{i}}2\mathbb{E}[x_{i,j}x_{i,l}]$.
  We analyze $\mathbb{E}[x_{i,j}^{2}]$ and $\mathbb{E}[x_{i,j}x_{i,l}]$ in turn.
  $\mathbb{E}[x_{i,j}^{2}]=Var[x_{i,j}]+\mathbb{E}[x_{i,j}]^{2}=Var[x_{i,j}]+0=\bar{\sigma}^{2}_{WI}(\theta)+\bar{\sigma}^{2}_{AI}(\theta)$ (by setting $N,K=1$ in Eq.~(\ref{eq:variance})).
  $\mathbb{E}[x_{i,j}x_{i,l}]=\mathbb{E}[(f_{\theta}(z_{i},v_{i,j})-u(\theta))(f_{\theta}(z_{i},v_{i,l})-u(\theta))]=\mathbb{E}[(f_{\theta}(z_{i},v_{i,j})(f_{\theta}(z_{i},v_{i,l})]-u(\theta)^{2}$.
  Given an instance $z_{i}$, $f_{\theta}(z_{i},v_{i,j})$ and $f_{\theta}(z_{i},v_{i,l})$ are independent because $v_{i,j}$ and $v_{i,l}$ are sampled $i.i.d$ from $\mathcal{G}$.
Thus it holds that:
\small
\begin{align}
&\mathbb{E}[(f_{\theta}(z_{i},v_{i,j})(f_{\theta}(z_{i},v_{i,l})]
= \mathbb{E}_{\mathcal{D}}[\mathbb{E}_{\mathcal{G}} [f_{\theta}(z_{i},v_{i,j}) f_{\theta}(z_{i},v_{i,l}) |z_i]] \nonumber \\
&= \mathbb{E}_{\mathcal{D}}[\mathbb{E}_{\mathcal{G}} [f_{\theta}(z_{i},v_{i,j})|z_{i}]
\mathbb{E}_{\mathcal{G}} [f_{\theta}(z_{i},v_{i,l})|z_{i}]]
=\mathbb{E}_{\mathcal{D}}[u_{z_{i}}(\theta)^{2}]. \nonumber
\end{align}
By the fact
$\mathbb{E}_{\mathcal{D}}[u_{z}(\theta)]=u(\theta)$,
$\mathbb{E}_{\mathcal{D}}[u_{z_i}(\theta)^{2}] - u(\theta)^{2}
=\mathbb{E}_{\mathcal{D}}[(u_{z_i}(\theta)-u(\theta))^{2}]=\bar{\sigma}^{2}_{AI}(\theta)$.
The last step is by Definition~\ref{def:across_instance}.

Summing up the above results, we have
  $Var[X_{i}]=n_{i}(\bar{\sigma}^{2}_{WI}(\theta)+\bar{\sigma}^{2}_{AI}(\theta))+n_{i}(n_{i}-1)\bar{\sigma}^{2}_{AI}(\theta)
  =n_{i}\bar{\sigma}^{2}_{WI}(\theta) + n_{i}^{2}\bar{\sigma}^{2}_{AI}(\theta)$.
  Thus $\sigma^{2}=\frac{1}{K}\sum_{i=1}^{K}Var[X_{i}]=\frac{N}{K}\bar{\sigma}^{2}_{WI}(\theta) + \frac{\sum_{i=1}^{K}n_{i}^{2}}{K}\bar{\sigma}^{2}_{AI}(\theta)$.
  Substitute $\sigma^{2}$ in Eq.~(\ref{eq:midresult1}) with this result and the proof is complete.
\end{proof}

\subsection{On Configuration Space with Finite Cardinality}
Theorem~\ref{theorem:finite} presents the
bound for uniform estimation error
when $\bm{\Theta}$ is of finite cardinality.

\begin{theorem}
  \label{theorem:finite}
   Given a performance estimator $\hat{u}_{S_{N}}(\theta)$.
   Let $\theta^{\dagger}=\argmax_{\theta \in \bm{\Theta}}\tau_{\theta}^{2}$,
   where $\tau_{\theta}^{2} = \bar{\sigma}^{2}_{WI}(\theta) + \frac{\sum_{i=1}^{K}n_{i}^{2}}{N}\bar{\sigma}^{2}_{AI}(\theta)$,
   and let
   $\tau^{2}=\tau_{\theta^{\dagger}}^{2}$,
   $\bar{\sigma}^{2}_{WI}=\bar{\sigma}^{2}_{WI}(\theta^{\dagger})$
   and
   $\bar{\sigma}^{2}_{AI}=\bar{\sigma}^{2}_{AI}(\theta^{\dagger})$.
   Let $n=\max\{n_{1},n_{2},...,n_{K}\}$
   and $C=U-L$.
   Given that $\bm{\Theta}$ is of finite cardinality, i.e.,
   $\bm{\Theta}=\{\theta_{1},\theta_{2},...,\theta_{m}\}$,
   then for any $0<\delta<1$, with probability at least $1-\delta$,
   there holds:
   \small
   \begin{align}
   \label{eq:finite}
    \sup_{\theta \in \bm{\Theta}}&[u(\theta)-\hat{u}_{S_{N}}(\theta)] \nonumber \\
    &\leq
    \frac{2nC\ln{\frac{m}{\delta}}}{3N}
    +
    \sqrt{2\ln{\frac{m}{\delta}}(\frac{1}{N}\bar{\sigma}^{2}_{WI} + \frac{\sum_{i=1}^{K}n^{2}_{i}}{N^{2}}\bar{\sigma}^{2}_{AI})}.
   \end{align}
\end{theorem}
\begin{proof}
  By Lemma~\ref{lem:concen}, for a
  given configuration $\theta$,
  for any $\epsilon>0$, it holds that
  $
    \mathrm{Prob}\{u(\theta) - \hat{u}_{S_{N}}(\theta)
    \geq \epsilon \}
    \leq \mathrm{exp}(-\frac{N\epsilon^{2}}{2\tau_{\theta}^{2}+\frac{2nC\epsilon}{3}})
  $.
  By union bound,
  $
  \mathrm{Prob}\{\sup_{\theta \in \bm{\Theta}}[u(\theta) - \hat{u}_{S_{N}}(\theta)]
    \geq \epsilon \}
    \leq \sum_{i=1}^{m}
    \mathrm{Prob}\{u(\theta_{i}) - \hat{u}_{S_{N}}(\theta_{i})
    \geq \epsilon\}
    \leq
    m \mathrm{exp}(-\frac{N\epsilon^{2}}{2\tau^{2}+\frac{2nC\epsilon}{3}}).
  $
  Let $\delta=m \mathrm{exp}(-\frac{N\epsilon^{2}}{2\tau^{2}+\frac{2nC\epsilon}{3}})
  $,
  and $\epsilon$ is solved as:
  $\epsilon=\frac{1}{2N}
  [\frac{2nC}{3}\ln{\frac{m}{\delta}}
  + \sqrt{(\frac{2nC}{3}\ln{\frac{1}{\delta})^{2}
  +8N\tau^{2}\ln{\frac{m}{\delta}}
  }}]
  \leq
  \frac{2nC\ln{\frac{m}{\delta}}}{3N}
	+
	\sqrt{2\ln{\frac{m}{\delta}}(\frac{\tau^{2}}{N})}.
   $
   Substituting $\tau^{2}$ with
   $\bar{\sigma}^{2}_{WI} + \frac{\sum_{i=1}^{K}n_{i}^{2}}{N}\bar{\sigma}^{2}_{AI}$
   proves Theorem~\ref{theorem:finite}.
\end{proof}

Note that for different $S_{N}$,
the bounds on the right side of
Eq.~(\ref{eq:finite}) are different.
The proof of Theorem~\ref{theorem:best_estimator}
shows that $\sum_{i=1}^{K}n_{i}^{2}$, s.t. $\sum_{i=1}^{K}n_{i}=N$,
is minimized on the condition $n_{i} \in \{\lfloor{\frac{N}{K}}\rfloor, \lceil{\frac{N}{K}}\rceil \}$ for all $i \in \{1,2,...,K\}$.
Moreover, it is easy to verify that
$n=\max\{n_{1},n_{2},...,n_{K}\}$
is also minimized on the same condition,
in which case $n=\lceil{\frac{N}{K}\rceil}$.
Thus we can immediately obtain
Corollary~\ref{cor:finite}.

\begin{corollary}
  \label{cor:finite}
   The estimator
  $\hat{u}_{S^{\ast}_{N}}$ established
  in Theorem~\ref{theorem:best_estimator},
  has the best bound for uniform estimation
  error in Theorem~\ref{theorem:finite}.
  Given that $K$ divides $N$,
  for any $0<\delta<1$, with probability at least $1-\delta$, there holds:
  \small
   \begin{equation*}
    \sup_{\theta \in \bm{\Theta}}[u(\theta)-\hat{u}_{S_{N}^{\ast}}(\theta)] \leq
    \frac{2C\ln{\frac{m}{\delta}}}{3K}
    +
    \sqrt{2\ln{\frac{m}{\delta}}(\frac{1}{N}\bar{\sigma}^{2}_{WI} + \frac{1}{K}\bar{\sigma}^{2}_{AI})}.
    \end{equation*}
\end{corollary}

\subsection{On Configuration Space with Infinite Cardinality}
Since in practice the cardinality of $\bm{\Theta}$ could be considerably
large (e.g., $10^{12}$),
in which case the bound provided
by Theorem~\ref{theorem:finite}
could be very loose.
Moreover, when the cardinality of $\bm{\Theta}$
is infinite, Theorem~\ref{theorem:finite}
does not apply anymore.
To address these issues,
we establish
new uniform error bound without dependence
on the cardinality of $\bm{\Theta}$
based on two mild assumptions given below.

\begin{assumption}\label{ass}
  \begin{enumerate}[(a)]
    \item We assume there exists $R>0$ such that $\bm{\Theta}\subseteq B_R$, where $B_{R}=\{\mathbf{w}\in\mathbb{R}^h:\|\mathbf{w}\|_2\leq R\}$ is a ball of radius $R$ and $\|\mathbf{w}\|_2=\sum_{i=1}^{h}w_i^2$ for $\mathbf{w}=(w_1,\ldots,w_h)$.
    \item We assume for any $(z,v) \in \mathcal{Z} \times \mathcal{V}$, the utility function $f$ is L-Lipschitz continuous, i.e., $|f_{\theta}(z,v)-f_{\tilde{\theta}}(z,v)| \leq L||\theta -\tilde\theta||_{2}$ for all $\theta,\tilde{\theta}\in\bm{\Theta}$.
  \end{enumerate}
\end{assumption}

Part (a) of Assumption \ref{ass} means
the ranges of the values of all parameters considered are bounded,
which holds in
nearly all practical algorithm configuration scenarios \cite{HutterLFLHLS14}.
Part (b) of Assumption \ref{ass}
poses limitations on how fast
$f_{\theta}$ can change
across $\bm{\Theta}$.
This assumption is also mild in
the sense that it is expected
that configurations with similar
parameter values would result in
similar behaviors of $\mathcal{A}$,
thus getting similar performances.
The key technique for deriving the new
bound is \textit{covering numbers} as defined in Definition~\ref{def:covering_numers}.

\begin{definition}
\label{def:covering_numers}
Let $\mathcal{F}$ be a set and $d$ be a metric.
For any $\eta>0$,
a set $\mathcal{F}^\triangle \subset \mathcal{F}$
is called an $\eta$-cover of $\mathcal{F}$
if for every $f \in \mathcal{F}$ there
exists an element $g \in \mathcal{F}^\triangle$
satisfying $d(f,g) \leq \eta$.
The covering number $\mathcal{N}(\eta,\mathcal{F}, d)$
is the cardinality of the minimal
$\eta$-cover of $\mathcal{F}$:
\[
    \mathcal{N}(\eta,\mathcal{F},d):=\min\{|\mathcal{F}^\triangle|:\mathcal{F}^\triangle\text{ is an $\epsilon$-cover of }\mathcal{F}\}.
  \]
\end{definition}

Lemma~\ref{lem:bound_on_cover_B} presents a covering number bound on $B_R$.

\begin{lemma}[\cite{pisier1999volume}]
\label{lem:bound_on_cover_B}
  \[\ln\mathcal{N}(\eta,B_R,d_2)\leq h\ln(3R/\eta),\]
  where $d_2(\mathbf{w},\tilde{\mathbf{w}})=\|\mathbf{w}-\tilde{\mathbf{w}}\|_2$.
\end{lemma}
Since $\bm{\Theta} \subset B_{R}$,
it is easy to verify that
$\ln\mathcal{N}(\eta,\bm{\Theta},d_2) \leq \ln\mathcal{N}(\eta,B_R,d_2)$.
Based on the L-Lipschitz continuity assumption,
Lemma~\ref{lem:bound_on_cover_F}
establishes a bound
for $\mathcal{N}(\eta,\mathcal{F},d_\infty)$,
where $\mathcal{F}=\{f_{\theta}:\theta \in \bm{\Theta}\}$.

\begin{lemma}
\label{lem:bound_on_cover_F}
Let $\mathcal{F}=\{f_{\theta}:\theta \in \bm{\Theta}\}$ and $ d_\infty(f_{\theta},f_{\tilde{\theta}})
=\sup_{(z,v) \in \mathcal{Z} \times \mathcal{V}}
|f_{\theta}(z,v)-f_{\tilde{\theta}}(z,v)|$.
If Assumption \ref{ass} holds,
then
$\ln\mathcal{N}(\eta,\mathcal{F},d_\infty) \leq h\ln(3RL/\eta)$.
\end{lemma}
\begin{proof}
  For any $\theta,\tilde{\theta}\in \bm{\Theta}$, by the Lipschitz continuity we know $d_\infty(f_\theta,f_{\tilde{\theta}})\leq L\|\theta-\tilde{\theta}\|_2$. Then, any $(\epsilon/L)$-cover of $B_R$ w.r.t. $d_2$ would imply an $\epsilon$-cover of $\mathcal{F}$ w.r.t. $d_\infty$. This together with Lemma \ref{lem:bound_on_cover_B} implies the stated result. The proof is complete.
\end{proof}

\begin{table*}[tbp]
  \centering
  \caption{Summary of the configuration scenarios and gathered performance matrix in each scenario. h is the \#parameters of the target algorithm. Tmax is the cutoff time. The $portgen$ generator \cite{johnson2007experimental} was used to generate the TSP instances (in which the cities are randomly distributed). For each scenario, $\bm{\Theta}_{M}$ was composed of the default parameter configuration and $M-1$ random configurations.
  }
  \scalebox{0.66}{
  \begin{tabular}{c|c|c|c|c|c|c}
  \hline
  Scenario& Algorithm& \multicolumn{1}{l|}{Domain} &Bechmark & $M$  & $P$ & \multicolumn{1}{l}{Tmax} \\ \hline
  SATenstein-QCP          & SATenstein \cite{DKhudaBukhshXHL16}, h = 54 & SAT& Randomly selected from QCP \cite{aaai/GomesS97}  & 500 & 500 & 5s \\ \hline
  clasp-weighted-sequence & clasp \cite{lpnmr/GebserKNS07a}, h=98      & ASP&  "small" type weighted-sequence \cite{padl/LierlerSTW12}  & 500 & 120 & 25s \\ \hline
  LKH-uniform-400 & LKH \cite{helsgaun2000effective}, h=23       & TSP& Generated by $portgen$ \cite{johnson2007experimental}, \#city=400  & 500 & 250 & 10s          \\ \hline
  LKH-uniform-1000 & LKH \cite{helsgaun2000effective}, h=23        & TSP& Generated by $portgen$ \cite{johnson2007experimental}, \#city=1000  & 500 & 250 & 10s \\ \hline
  \end{tabular}}
  \label{tab:scenarios}
  \end{table*}

  \captionsetup[sub]{font=small}
  \begin{figure*}[tbp]
    \centering
      \begin{subfigure}[b]{0.505\columnwidth}
        \scalebox{1.0}{\includegraphics[width=\linewidth]{SATenstein-QCP_8_com_estimator}}
        \caption{SATenstein-QCP}
      \end{subfigure}
      \hfill
      \begin{subfigure}[b]{0.505\columnwidth}
        \scalebox{1.0}{\includegraphics[width=\linewidth]{clasp-weighted_sequence_8_com_estimator}}
        \caption{clasp-weighted-sequence}
      \end{subfigure}
      \hfill
      \begin{subfigure}[b]{0.505\columnwidth}
        \scalebox{1.0}{\includegraphics[width=\linewidth]{LKH-uniform-400_8_com_estimator}}
        \caption{LKH-uniform-400}
      \end{subfigure}
      \hfill
      \begin{subfigure}[b]{0.505\columnwidth}
        \scalebox{1.0}{\includegraphics[width=\linewidth]{LKH-uniform-1000_8_com_estimator}}
        \caption{LKH-uniform-1000}
      \end{subfigure}
    \caption{Estimation error for different estimators in different scenarios at $r_1=0.5$.}
    \label{fig:com_estimator}
  \end{figure*}

With the bound for $\mathcal{N}(\eta,\mathcal{F},d_\infty)$,
the new bound for $u(\theta)-\hat{u}_{S_{N}}(\theta)$
is established in
Theorem~\ref{theorem:infinite}.

\begin{lemma}\label{lem:inequality-solution}
  For any positive constants $k, l, b, c$, the inequality $\epsilon^k l+b\ln\epsilon\geq c$ has a solution
  \begin{equation*}\label{eq:inequality-solution}
  \epsilon_0=\left(\frac{c+b\max(\ln l-\ln c,0)/k}{l}\right)^{1/k}.
\end{equation*}
\end{lemma}

\begin{theorem}
  \label{theorem:infinite}
  If Assumption \ref{ass} holds and $h\ln(12LR)\geq1$,
then for any $0<\delta<1$, with probability $1-\delta$
   there holds:
   \small
   \begin{align*}
    &\sup_{\theta \in \bm{\Theta}}[u(\theta)-\hat{u}_{S_{N}}(\theta)] \\
    & \leq
    \sqrt{\frac{h\ln(12LR)+\ln(\frac{1}{\delta})+\frac{1}{2}h\ln\frac{N}{8\tau^2+\frac{4nC}{3}}}{N}\Big(8\tau^2+\frac{4nC}{3}\Big)},
   \end{align*}
   where $n, C,\tau^{2}, \bar{\sigma}^{2}_{WI},\bar{\sigma}^{2}_{AI}$ are defined
   the same as in Theorem~\ref{theorem:finite}.
\end{theorem}
\begin{proof}
  Without loss of generality we can assume $\epsilon\leq1$.
  Let $\{f_{\theta_1},...,f_{\theta_m}\}$
  be a $\epsilon/4$-cover of $\mathcal{F}$
  with $m=\mathcal{N}(\epsilon/4,\mathcal{F},d_\infty)$, where
  $\mathcal{F}=\{f_{\theta}:\theta \in \bm{\Theta}\}$.
 By Definition~\ref{def:covering_numers},
 for any $f_{\theta} \in \mathcal{F}$
 there exists $f_{\theta_{j}} \in
 \{f_{\theta_1},...,f_{\theta_m}\}$,
 such that
 $d_\infty(f_{\theta},
f_{\theta_{j}})
=\sup_{(z,v) \in \mathcal{Z} \times \mathcal{V}}
|f_{\theta}(z,v)-f_{\theta_{j}}(z,v)|
\leq \epsilon/4$;
 it follows that
 $|\mathbb{E}[f_{\theta}(z,v)]-\mathbb{E}[f_{\theta_{j}}(z,v)]|
 =|u(\theta)-u(\theta_{j})|
 \leq \epsilon/4
 $
 and
 $
 |\hat{u}_{S_{N}}(\theta)-\hat{u}_{S_{N}}(\theta_{j})|
= \frac{1}{N}\sum_{i=1}^{K}\sum_{j=1}^{n_{i}}|f_{\theta}(z_{i}, v_{i, j})
 -
 f_{\theta_{j}}(z_{i}, v_{i, j})|
 \leq \epsilon/4.
 $
 Then,
 \small
 \begin{align*}
   & \sup_{\theta\in\bm{\Theta}}\big[u(\theta)-\hat{u}_{S_N}(\theta)\big] \leq\\
   & \sup_{\theta\in\bm{\Theta}}\Big[u(\theta)-u(\theta_j)+u(\theta_j)-\hat{u}_{S_N}(\theta_j)+\hat{u}_{S_N}(\theta_j)-\hat{u}_{S_N}(\theta)\Big]\\
   &\leq \frac{\epsilon}{2}+\max_{j\in\{1,..,m\}}[u(\theta_{j})-\hat{u}_{S_{N}}(\theta_{j})].
 \end{align*}
 It then follows that $\mathrm{Prob}\{
\sup_{\theta \in \bm{\Theta}}[u(\theta)-\hat{u}_{S_{N}}(\theta)]
\geq \epsilon
\}
\leq
\mathrm{Prob}\{
\max_{j\in\{1,..,m\}}[u(\theta_{j})-\hat{u}_{S_{N}}(\theta_{j})] \geq \epsilon/2
\}\leq \sum_{j=1}^{m}
\mathrm{Prob}\{
[u(\theta_{j})-\hat{u}_{S_{N}}(\theta_{j})] \geq \epsilon/2
\}\leq m \mathrm{exp}(-\frac{\frac{N}{4}\epsilon^{2}}{2\tau^{2}+\frac{nC\epsilon}{3}})$, where the last inequality is due to Lemma \ref{lem:concen}.
We need to find a $\epsilon$ satisfying $\mathrm{exp}(h\ln(12RL/\epsilon)-\frac{N\epsilon^{2}}{8\tau^{2}+\frac{4nC\epsilon}{3}})\leq \delta$, for which it suffices to find a solution of (by $\epsilon\leq1$)
$\frac{N\epsilon^2}{8\tau^2+\frac{4nC}{3}}+h\ln\epsilon\geq h\ln(12LR)+\ln(1/\delta)$. This inequality takes the form of the inequality in Lemma~\ref{lem:inequality-solution} (the proof of Lemma~\ref{lem:inequality-solution} is omitted here due to space limitations).
We can apply Lemma \ref{lem:inequality-solution} to show that a solution is (note $h\ln(12LR)\geq1$)
\[
\epsilon=\bigg(\frac{h\ln(12LR)+\ln(1/\delta)+2^{-1}h\ln\frac{N}{8\tau^2+\frac{4nC}{3}}}{\frac{N}{8\tau^2+\frac{4nC}{3}}}\bigg)^{\frac{1}{2}}.
\]

\end{proof}

\subsection{Discussion}
There are some important findings from the above results.
First, both
Theorem~\ref{theorem:finite} and Theorem~\ref{theorem:infinite}
relate the bounds on $u(\theta)-\hat{u}_{S_{N}}(\theta)$ with the complexity
of $\bm{\Theta}$,
and the bounds deteriorate as the complexity increases.
This means as the considered configuration space
gets more complex, there is a possibility that the estimation
error could be larger.
Second, as expected, as
$N$ and $K$ get larger,
the estimation error gets smaller,
and $\hat{u}_{S_{N}}(\theta)$
will converge to $u(\theta)$ with
probability 1 with $N \rightarrow \infty$
and $K \rightarrow \infty$.
Third, Corollary~\ref{cor:finite}
shows that, for the estimator
$\hat{u}_{S_{N}}(\theta^{\ast})$
which are widely used in current AAC methods,
the gain on error reduction
decreases rapidly as $N$ and $K$
get larger (which are also shown in Figure~\ref{fig:analysis}
in the experiments),
and the effects of increasing $N$ and $K$
also depend on
$\bar{\sigma}^{2}_{WI}$ and
$\bar{\sigma}^{2}_{AI}$,
two quantities
varying across different
algorithm configuration scenarios.
Thus for enhancing current AAC methods,
instead of fixing $N$ as a large number (e.g., SMAC sets $N$ to 2000 by default)
and using as many training instances as possible,
it is more desirable to use different
$N$ and $K$ according to the
configuration scenario considered,
in which case
$N$ and $K$ may be adjusted dynamically
in the configuration process as more data
are gathered to estimate
$\bar{\sigma}^{2}_{WI}$ and
$\bar{\sigma}^{2}_{AI}$.

\section{Experiments}
\label{section5}

In this section, we present our experimental studies.
First we introduce our experiment setup.
Then, we verify our theoretical results in two facets: 1) comparison of different performance estimators;
2) the effects of different values of $m$ (the number of considered configurations),
$N$ (the number of runs of $\theta$ to estimate $u(\theta)$) and
$K$ (the number of training instances)
on the estimation error.

We conducted experiments based on a re-sampling approach \cite{Birattari2004},
which is often used for time-consuming empirical analysis.
Specifically, we
considered 4 different scenarios.
We selected two scenarios SATenstein-QCP and clasp-weighted-sequence from
the Algorithm Configuration Library (AClib) \cite{HutterLFLHLS14}
and built two new scenarios LKH-uniform-400/1000.
For each scenario, we
gathered a $M \times P \times 5$ matrix containing the performances of
$M$ configurations on $P$ instances,
with each configuration running on each
instance for 5 times.
Let $\bm{\Theta}_{M}$ be the set of the $M$ configurations
and
$\mathcal{Z}_{P}$ be the set of the $P$ instances.
In the experiments,
when acquiring the performance of
a configuration $\theta$ on an instance,
instead of actually running $\theta$,
the value stored in the corresponding
entry of the matrix was used.
The details of the scenarios and the performance matrices are summarized in Table~\ref{tab:scenarios}.
In the experiments the optimization goal considered is
the runtime needed to solve the problem instances
(for SAT and ASP) or to find the optima of the problem instances (for TSP).
In particular, the performance metric was set to Penalized Average Runtime–10 (PAR-10) \cite{hutter2009paramils},
which counts a timeout as 10 times the given cutoff time.

For convenience henceforth
we will use ``$\mathrm{split}_{P_{1}|P_{2}}$''
to denote that we
subsequently randomly select,
without replacement,
$P_{1}$ and $P_{2}$
instances from $\mathcal{Z}_{P}$
as training instances
and test instances respectively.
For a given $\theta$,
we always used
the performance
obtained by an estimator
on the training instances
as its training performance,
and used its performance
on the test instances as its
true performance.
We use
$\mathrm{uniform\_es\_error(\bm{\Theta})}$
to denote the maximal estimation error
across the configurations in $\bm{\Theta}$.

All the experiments were conducted on a Xeon machines with 128 GB RAM and 24 cores each
(2.20 GHz, 30 MB Cache), running CentOS.
The code was implemented based on AClib \cite{HutterLFLHLS14}
\footnote{The code and the complete experiment results are
available at \url{https://github.com/EEAAC/ac_estimation_error}}.

\captionsetup[sub]{font=small}
\begin{figure*}[tbp]
  \centering
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{SATenstein-QCP_DM_m}}
      \caption{SATenstein-QCP}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{clasp-weighted_sequence_DM_m}}
      \caption{clasp-weighted-sequence}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{LKH-uniform-400_DM_N}}
      \caption{LKH-uniform-400}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{LKH-uniform-1000_DM_K}}
      \caption{LKH-uniform-1000}
    \end{subfigure}
  \caption{Uniform estimation error at different $m$, $N$ and $K$ and the fit functions based on the theoretical results.}
  \label{fig:analysis}
\end{figure*}

\captionsetup[sub]{font=small}
\begin{figure*}[tbp]
  \centering
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{clasp-weighted_sequence_DM_m_train}}
      \caption{clasp-weighted-sequence}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{LKH-uniform-1000_DM_m_train}}
      \caption{LKH-uniform-1000}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{LKH-uniform-400_DM_N_train}}
      \caption{LKH-uniform-400}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.505\columnwidth}
      \scalebox{0.9}{\includegraphics[width=\linewidth]{SATenstein-QCP_DM_K_train}}
      \caption{SATenstein-QCP}
    \end{subfigure}
    \caption{Estimation error on
    $\theta^{\ast}$ at different $m$, $N$ and $K$ and the fit functions based on the theoretical results.}
    \label{fig:train_bound}
\end{figure*}

\textbf{Comparison of Different Estimators.}
We compared $\hat{u}_{S^{\ast}_{N}}(\theta)$ with two
estimators $\hat{u}_{S^{\dagger}_{N}}(\theta)$ and $\hat{u}_{S^{\circ}_{N}}(\theta)$.
For evaluating $\theta$,
$\hat{u}_{S^{\dagger}_{N}}(\theta)$
repeatedly randomly selects an instance
from $\mathcal{Z}_{P}$ without replacement,
and runs $\theta$ for 5 times on the instance as long as the total number
of runs of $\theta$ not exceeding $N$.
$\hat{u}_{S^{\dagger}_{N}}(\theta)$ is greedier
than $\hat{u}_{S^{\ast}_{N}}(\theta)$ in the sense that it ensures the estimated performance of $\theta$ on the used instances is as accurate as possible.
Another estimator $\hat{u}_{S^{\circ}_{N}}(\theta)$
is the one presented in \cite{Birattari2004},
which repeatedly randomly selects an instance from $\mathcal{Z}_{P}$ with replacement,
and runs $\theta$ for a single time on the instance.
$\hat{u}_{S^{\circ}_{N}}(\theta)$ has more
randomness than $\hat{u}_{S^{\ast}_{N}}(\theta)$
since it does not ensure that
$N$ runs of $\theta$ are distributed evenly on all instances.
We set $K=r_{1}P$ and $N=r_{2}K$, and
ranged $r_{1}$ from 0.1 to 0.5 with a step of 0.05,
$r_{2}$ from 0.25 to 4.0 with a
step of 0.25.
To reduce the variations of our experiments,
for each combination of $r_{1}$ and $r_{2}$,
we $\mathrm{split}_{{K}|P/2}$
for 2500 times,
and on each split,
we obtained the estimation error
of an estimator
on each $\theta \in \bm{\Theta}$,
and then calculated
the mean value,
which was further averaged
over all splits.
That is, for each combination
of $r_{1}$ and $r_{2}$,
we obtained a mean estimation
error for each estimator.
Due to space limitations, we only present
the results in terms of error bars (mean $\pm$ std)
at $r_{1}=0.5$ in Figure~\ref{fig:com_estimator}.
The results at other values of $r_{1}$
are similar.
Figure~\ref{fig:com_estimator} is
in line with Theorem~\ref{theorem:best_estimator}.
Overall $\hat{u}_{S^{\ast}_{N}}(\theta)$
is the best estimator among the three,
and its performance advantage is remarkable
when $N$ is small. When $N$ gets larger,
it is expected, and as shown in Figure~\ref{fig:com_estimator},
that the estimation error for
all three estimators will
converge to 0.
The fact that $\hat{u}_{S^{\ast}_{N}}(\theta)$
is better than $\hat{u}_{S^{\circ}_{N}}(\theta)$
indicates that it is necessary to
distribute $N$ runs of $\theta$
as evenly as possible over all instances.

\textbf{Estimation Error at Different $\bm{m}$, $\bm{N}$ and $\bm{K}$.}
We always fixed two values while ranging the other one.
We ranged $m$ from 1 to $M$,
while setting $K=P/2$ and $N=5K$.
We ranged $N$ from 1 to $5K$
while setting $K=P/2$ and $m=M$.
We ranged $K$ from 1 to $P/2$
while setting $N=5K$ and $m=M$.
For a given $m$,
we $\mathrm{split}_{K|P/2}$
for 2500 times,
and on each split,
we started with an empty set
$\bm{\Theta}_{train}$ of configurations and
then repeatedly
expanded $\bm{\Theta}_{train}$
by adding a configuration
randomly selected from
$\bm{\Theta}_{M}\setminus\bm{\Theta}_{train}$.
Each time a new configuration $\theta$
was added to $\bm{\Theta}_{train}$,
$\mathrm{uniform\_es\_error(\bm{\Theta}_{train})}$
was recorded,
which was further averaged
over all 2500 splits.
That is, for each $m$,
we obtained a mean value of
$\mathrm{uniform\_es\_error(\bm{\Theta}_{train})}$,
denoted as $\mathrm{uniform\_es\_error(\bm{\Theta}_{train}, m)}$.
Similarly, for a given $N$
or a given $K$,
we always $\mathrm{split}_{K|P/2}$
for 2500 times,
and on each split,
we obtained
$\mathrm{uniform\_es\_error(\bm{\Theta}_{M})}$,
and then averaged it over all splits.
Thus for each considered
$N$ and $K$,
we obtained
$\mathrm{uniform\_es\_error(\bm{\Theta}_{M}, N)}$
and
$\mathrm{uniform\_es\_error(\bm{\Theta}_{M}, K)}$, respectively.
Due to space limitations,
we only present parts of the results
in Figure~\ref{fig:analysis}
and other results
are very similar.
To verify whether our analysis
(Theorem~\ref{theorem:finite})
correctly captures the dependence of estimation error on
$N$, $M$ and $K$,
we also plot the function
$f(m)=a\ln{m}+b\sqrt{\ln{m}}$
for $m$,
$f(N)=a+b\sqrt{1/N}$ for $N$
and
$f(K)=a/K+b\sqrt{1/K}$
for $K$
in Figure~\ref{fig:analysis},
where the parameters
$a,b$ are computed by
fitting $f$ with
the data collected in the experiments,
i.e.,
$\{m \mapsto \mathrm{uniform\_es\_error(\bm{\Theta}_{train}, m)}:m \in \{1,...,M\}\}$,
$\{N \mapsto \mathrm{uniform\_es\_error(\bm{\Theta}_{M}, N)}:N \in \{1,...,\frac{5}{2}P\}\}$
and
$\{K \mapsto \mathrm{uniform\_es\_error(\bm{\Theta}_{M}, K)}: K \in \{1,...,\frac{1}{2}P\}\}$, respectively.
Overall Figure~\ref{fig:analysis}
demonstrates that our analysis managed to
capture the dependence of uniform estimation error on $m$, $N$ and $K$.
It is worth noting that in the experiments
the effects of increasing $m$, $N$ and $K$
depend on $\bar{\sigma}^{2}_{WI}$ and
$\bar{\sigma}^{2}_{AI}$,
which vary across
configuration scenarios.
Moreover,
the estimation error becomes very low
and quite stable when $N$ approaches $K/2$,
which means running $\theta$ on
half of the training instances
could already obtain a reliable estimate
of $u(\theta)$.

It is also meaningful to investigate whether
our analysis could reflect how
the estimation error
on $\theta^{\ast}$,
i.e., the configuration with
the best training performance in $\bm{\Theta}$,
denoted as $\mathrm{train\_es\_error(\bm{\Theta})}$,
would change.
We conducted the same experiments as described above to gather $\mathrm{train\_es\_error(\bm{\Theta}_{train}, m)}$,
$\mathrm{train\_es\_error(\bm{\Theta}_{M},N)}$
and
$\mathrm{train\_es\_error(\bm{\Theta}_{M},K)}$.
Figure~\ref{fig:train_bound} plots the results and the fit functions.
It could be seen that although
the bounds are not directly established
for $\mathrm{train\_es\_error(\bm{\Theta})}$,
the findings also apply to
it to a considerable extent.

\section{Conclusion}
The main results of this paper include
the universal best performance estimator and
bounds on the uniform estimation error,
which were verified in extensive experiments.
Possible future directions include
data-dependent bounds that are tighter and
computable from realization of training instances
and analysis of the notorious over-tuning phenomenon
based on the results in this paper.

\bibliographystyle{aaai}
\fontsize{9.0pt}{10.3pt} \selectfont