\section{Introduction}
\paragraph{}
Hyperparameter tuning is a common technique for improving the accuracy of neural networks \cite{bischl2021hyperparameter}. 
There are various methods for performing this tuning 
\cite{yu2020hyper, yang2020hyperparameter, luo2016review}, 
in this work we focus on methods which iteratively sample hyperparameter configurations from a stable distribution 
\cite{huang2021novel, roman2021machine, callaghan2021machine}. 
These methods usually involve training the model on multiple sampled hyperparameters, 
in an attempt to find a hyperparameter configuration which improves the model's accuracy. 
This process is complex for a number of reasons:
\begin{itemize}
    \item Each hyperparameter sampling iteration, requires additional training and thus the number of iterations is limited by the researcher's computational budget.
    \item Throughout the tuning each iteration has a diminishing probability of improving accuracy.
    \item Rare rewards make the computational-budget/accuracy trade off hard to handle since it is unclear how to design an effective stopping rule. 
\end{itemize}

\paragraph{}
With no gold-standard for stopping rule different researchers evaluate their methods with different computational budgets, making it hard to compare their results. This has led to the creation of statistical estimators for the EVP - Expected Validation Performance \cite{dodge-etal-2019-show, tang-etal-2020-showing, dodge2021expected}, a tool used for reporting performance (e.g., accuracy) as a function of computational budget. EVP allows for comparison between researchers using different computational budgets by estimating the results of the researcher who had a higher computational budget if he had used a lower computational budget.

\paragraph{}
In this work we examine the opposite problem. We empirically estimate the expected gain in accuracy obtained by sampling one more hyperparameter configuration given the accuracies obtained from the models trained in the first $k$ iterations. To ensure the tightness of our estimation we show that the error is diminishing with $k$ with high probability. Additionally, we show that the estimation error cannot be better than $\frac{1}{k}$.


\subsection{Proof overview}
\paragraph{}
Let $X$ be a r.v. denoting the model accuracy for randomly sampled hyperparameters $h \sim \mathcal{H}$. Let $k$ be the number of hyperparameter search iterations preformed to date. Accurately estimating the accuracy gain from sampling the $k+1$ configuration of hyperparameters, and training the corresponding models, naively would require us to estimate the density function of $X$. However, empirical estimation of the density function $f_X$, is a hard problem and is currently not solvable without additional assumptions. In our case there is no prior knowledge about $f_X$ and we can make no assumptions regarding it.

\paragraph{}
We overcome this hurdle by estimating the empirical accumulated function $F_X$ instead. The estimation is obtained using the Dvoretzky–Kiefer–Wolfowitz Massart inequality (DKW) 
\cite{massart1990tight, naaman2021tight, bitouze1999dvoretzky}
from statistics that allows us to accurately estimate the empirical accumulated function $\widehat{F}_X$ in the $l_\infty$ norm. Using this estimation enables us to use the cumulative function $\widehat{F}_X$ for estimating the expected accuracy gain from the $k+1$ sample.  

Finally, we show that for normally distributed   
$X \sim \mathcal{N}\left( \mu, \sigma\right)$ the best estimator 
behaves like $I\left( \widehat{\mu},\, \widehat{\sigma}\right)$ 
for $\widehat{\mu},\, \widehat{\sigma}$ 
the empirical values of $\mu, \sigma$ and $I$ a convex function. 
We then bound the error of the 
best estimator from below by both 
\begin{align*}
    & 
    \left( 1\right)
    \quad
        \frac{\partial}{\partial \mu} I\left( \mu,\, \sigma\right) 
        \cdot \abs{\mu - \widehat{\mu}}\,
\end{align*}
and
\begin{align*}
    &
    \left( 2\right)
    \quad
        \frac{\partial}{\partial \sigma} I\left( \mu,\, \sigma\right) 
        \cdot \abs{\sigma - \widehat{\sigma}} 
\end{align*}
Taking the expectation of both expressions 
results in $\frac{1}{k}$ lower bound on the 
mean absolute error.  



\section{Related work}

\paragraph{}
Hyperparameter tuning methods can be split into 4 major types: Grid search, Random search, Bayesian Optimisation, Meta Heuristic algorithms. We will discuss each one briefly.

\paragraph{}

Grid Search is a simple exhaustive method, its major limitation being that it is time-consuming and impacted by the curse of dimensionality \cite{claesen2014easy}. Thus, it is unsuitable for a large number of hyperparameters and is often imprecise for continuous parameters. It is also computationally expensive as it is an exhaustive search. Therefore Grid Search is only efficient for a small number of categorical hyper-parameters \cite{yang2020hyperparameter}.

\paragraph{}
Random Search is more efficient than Grid Search and supports all types of hyperparameters. In practical applications, using Random Search to evaluate
the randomly selected hyperparameter values helps explore a large search space \cite{yang2020hyperparameter}.

\paragraph{}
Bayesian optimization models include: BO-GP, SMAC, and BO-TPE - based on their surrogate models. To reduce unnecessary evaluations and improve efficiency theses models determine the next hyper-parameter value to be tested based on the previously evaluated results. They can be used for categorical, discre, continuous and conditional parameters \cite{yang2020hyperparameter}.

\paragraph{}
Metaheuristic algorithms, (such as GA and PSO), are more complicated tuning algorithms, yet they often perform well for complex optimization problems. They support all types of hyper-parameters and are particularly efficient for large configuration spaces, since they can obtain near-optimal solutions within very few iterations. These algorithms have their own disadvantages though as an appropriate initialization is crucial for the success of PSO and GA introduces its own hyperparameters, such as crossover and mutation rates~\cite{yang2020hyperparameter}.

A comprehensive comparison between the algorithms can be found in~\cite{yang2020hyperparameter}. Our work only pertains to algorithms based on Random Search, which despite having some disadvantages is still commonly used in many modern works \cite{huang2021novel, roman2021machine, callaghan2021machine}.


\section{Preliminaries}
\subsection{Dvoretzky–Kiefer–Wolfowitz inequality} 
\paragraph{}
For a fixed random variable $X$ the DKW inequality aims to bound the discrepancy between the empirical $X$ and the ground truth of the distribution. 
We will start by defining the empirical cumulative function. 

\begin{definition}
    Given a natural number $n$ let $X_1, X_2, \hdots, X_n$
    be real-valued independent and identically distributed
    random variables with cumulative distribution function 
    $F_X$. Let $F_n$ denote the associated empirical distribution function defined by
    \begin{equation*}
        F_n\left( x\right) 
        \,=\, 
        \frac{1}{n} \overset{n}{\underset{i=1}{\Sigma}}\, 
        \mathbf{1}_{X_i \leq x}, \quad\; x \in \mathbb{R}
    \end{equation*}
\end{definition}
In words $F_n(x)$ is the fraction of random variables that are smaller than $x$.
The Dvoretzky–Kiefer–Wolfowitz inequality \cite{massart1990tight, bitouze1999dvoretzky} bounds the probability that the random function $F_n$ differs from $F_X$ by more than a given constant $\epsilon > 0$  anywhere on the real line. Formally: 

\begin{theorem}\label{dkw_thm}
    Let $X_1, \hdots, X_n \sim \mathcal{D}$ be identically distributed random variables 
    and let $F_n$ denote the empirical cumulative distribution. 
    Then for every $0 < \alpha < 1$ the following inequlity bound holds 
    \begin{equation*}
        \norm{F_n\left( w\right) - F_X\left( w\right)}_{\infty} \leq \epsilon        
    \end{equation*}
    with probability $1 - \alpha\,\,$ for  
    \begin{equation*}
        \epsilon = \sqrt{\frac{\log \frac{2}{\alpha}}{2n}}        
    \end{equation*} 
\end{theorem}

\section{Estimator theorem}
\paragraph{}
In this section we will estimate the expected improvement by 
the $k+1$ iteration of hyperparameter sampling and will bound the error with high probability. 
Theorem~\ref{thm_11} presents a formal description of our main result 
and proceeds with the corresponding proof 

\begin{theorem}\label{thm_11}
    Let $h_1, \hdots, h_k \sim H$ be i.i.d sampled hyperparameters, 
    and let $X_1, \hdots, X_k$ be the model accuracies when 
    trained with hyperparameters $h_1, \hdots, h_k$ correspondingly. 
    Let $\widehat{F}_k$ be the empirical cumulative function
    induced by $X_1, \hdots, X_k$ 
    and let $\Delta_{k+1}$ be the random variable denoting 
    the expected accuracy gain from sampling the $k+1$ hyperparameter. 
    The expected accuracy gain can be estimated by 
    \equ{
        \underset{h_{k+1}\sim \mathcal{D}_\mathcal{H}}{\mathbb{E}}\left[ \,\Delta_{k+1}\,\right] 
        = \int_0^1\, \left( \widehat{F}_k \right)^{\,k}\,\cdot\,\left( 1-\widehat{F}_k\right) \, d t \,+\, \epsilon_\textit{error} 
    } 
    with probability of at least $1-\frac{1}{\sqrt{k}}\,$ for 
    \equ{
        \epsilon_\textit{error} \leq 
        6\sqrt{\frac{\log k}{k}} 
    }   
\end{theorem}



\section{Theorem development}
\paragraph{}
Let $\left\{ h_k\right\}_{k \in \mathbb{N}} \subset H$ be i.i.d randomly sampled 
hyperparameters and let $\left\{ X_k\right\}_{k \in \mathbb{N}}$ 
be the random variable representing the model accuracy 
at time $k$ when trained with $h_k$. 
Denoting by $Y_k$ the best model accuracy up to time $k$,  
then 
\begin{align*}
        &
        Y_k = \underset{i \leq k}{\max}\left( \left\{ X_i\right\}_{i \leq k}\right) 
\end{align*}
and 
\begin{align*}
        &
        \Delta_k 
        \,=\,
        Y_{k} - Y_{k-1} 
\end{align*}

We will start by estimating
$\;Y_{k},\; Y_{k} - Y_{k-1}\;$ 
as functions of 
$\;X_1,...,X_k,\; Y_1,...,Y_{k-1}\;$ 
then observe that
\begin{equation*}
        F_{Y_k}\left( w\right)
        = P \left( Y_k \leq w\right)
        = P \left( X_1,...,X_k \leq w\right)
\end{equation*}
\begin{equation*}
        = \underset{i \leq k}{\prod} P \left( X_i \leq w\right)
        = \underset{i \leq k}{\prod} F_{X_i}\left( w\right)
        = F_{X}\left( w\right)^{k}
\end{equation*}
Thus
\begin{equation*}
    F_{Y_k}\left( w\right) = F_{X}\left( w\right)^{k}     
\end{equation*}
hence 
\begin{equation*}
    \mathbf{E} \left[Y_k\right] = \int_{0}^1 1-F_{Y_k}\left( w\right)\; dw = 1 - \int_{0}^1 F_{X}\left( w\right)^k\; dw
\end{equation*}
and 
\begin{align*}
    & 
       \Delta_{k+1} \equiv \mathbf{E} \left[Y_{k+1} - Y_k\right]
    \\ & 
        = \left( 1 - \int_{0}^1 F_{X}\left( w\right)^{k+1}\; dw \right) - \left( 1 - \int_{0}^1 F_X\left( w\right)^k\; dw \right)         
    \\ & 
        = \int_{0}^1 F_X\left( w\right)^k - F_X\left( w\right)^{k+1}\; dw
    \\ & 
        = \int_{0}^1 F_X\left( w\right)^k \left( 1 - F_X\left( w\right)\rb\; dw
\end{align*}
and by the DKW theorem (\ref{dkw_thm}) we have  
\begin{equation*}
    \norm{\widehat{F}_k  \left( w\right) - F_{X}\left( w\right)}_{\infty} \leq \epsilon        
\end{equation*}
with probability $1 - \alpha\,$ 
for 
\begin{equation}\label{eq_eps_choice}
    \epsilon = \sqrt{\frac{\log \frac{2}{\alpha}}{2k}}   
\end{equation}
Thus denoting by $G\,$ the event that the DKW approximation holds then 
\begin{align*}
    & 
    \Delta_{k+1} 
    \equiv \mathbf{E} \left[Y_{k+1} - Y_k\right]
    = \mathbf{E} \left[\left( Y_{k+1} - Y_k\right) \left( \mathbf{1}_{G} + \mathbf{1}_{G^c}\right)\right]             
    \\ & 
    \leq \alpha + \left( 1-\alpha\right) \mathbf{E}\left[Y_{k+1} - Y_k| G\right]
    \leq
    \alpha + \mathbf{E}\left[Y_{k+1} - Y_k| G\right]            
\end{align*}
similarly 
\begin{align*}
    & 
        \Delta_{k+1} 
        \,\geq\, \left( 1-\alpha\right) \cdot \mathbf{E}\left[Y_{k+1} - Y_k| G\right]
\end{align*}


Given $G$ we may estimate $\mathbf{E}\left[Y_{k+1} - Y_k| G\right]$ 
by using the DKW theorem. for replacing
$F_X$ and  $\widehat{F}_k$
\begin{align*}
    & 
        \mathbf{E}\left[Y_{k+1} - Y_k| G\right] 
    \geq
        \int_0^1 \left( \widehat{F}_k - \epsilon\right)^k
        \left( 1 - \epsilon - \widehat{F}_k\right)\, dw
    \equiv 
        LB_{k+1} 
\end{align*}
similarly 
\begin{align*}
    & 
            \mathbf{E}\left[Y_{k+1} - Y_k| G\right] 
        \leq
            \int_0^1 \left( \widehat{F}_k +\epsilon\right)^k
            \left( 1 + \epsilon - \widehat{F}_k\right)\, dw
        \equiv 
            UB_{k+1}        
\end{align*}
combining the last three equations 
\begin{align*}
    \Delta_{k+1} 
    \,=\,
    \int_0^1 
    \left( \widehat{F}_k\right)^k
    \left( 1 - \widehat{F}_k\right)
    \,dw \,+\, \epsilon_{err}    
\end{align*}
when $\epsilon_{err}\,$ is bounded by  
\begin{align*}
    & 
    \epsilon_{err} 
    \,\leq\, 
    UB_{k+1} \,-\, LB_{k+1}   
     \,+\, 
    2 \alpha
\end{align*}
choosing $\alpha=\frac{1}{\sqrt{2 k}}\,$ 
and using the lemma (\ref{lem_764}) 
to bound $UB_{k+1} \,-\, LB_{k+1}$
we have 
\begin{align*}
    & 
        \epsilon_{err} 
        \,\leq\, 
        UB_{k+1} \,-\, LB_{k+1}   
         \,+\, 
        2 \alpha
    \\ & 
        \,\leq\, 
            2\, \alpha + \left( 2+\frac{2}{e}\right)\, \epsilon 
        \,\leq\, 
            3\left( \alpha + \epsilon \right)  
    \\ & 
        \underbrace{\,=\,}_{\left( 3\right)} 
            3\left( \alpha + \sqrt{\frac{\log \frac{2}{\alpha}}{2k}} \right)  
        \underbrace{\,=\,}_{\alpha = \frac{1}{\sqrt{2 k}}} 
           3\left( \frac{1}{\sqrt{2 k}} + \sqrt{\frac{\log\, \sqrt{2 k}}{2k}} \right)
    \\ & 
        \,=\, 
            3\left( \frac{1}{\sqrt{2 k}} + \sqrt{\frac{\log\, 2 k}{k}} \right)
        \,\leq\, 
            6 \, \sqrt{\frac{\log\, k}{k}} 
\end{align*}
when transition $\left( 3\right)$ is from $\epsilon$ choice (\ref{eq_eps_choice})
$\hfill\square$

Thus it is left to prove the following lemma for us to end the theorem 
development (\ref{thm_11})
 
 \begin{lemma}\label{lem_764}
     Let $k \in \mathbb{N}$ be an integer and let $\epsilon > 0$ 
     denote by 
     \begin{align*}
         &
        LB_{k+1}
        \,=\,
        \int_0^1 \left( \widehat{F}_k - \epsilon\right)^k
        \left( 1 - \epsilon - \widehat{F}_k\right)\, dw
        \\ & 
         UB_{k+1}
         \,=\,
        \int_0^1 \left( \widehat{F}_k +\epsilon\right)^k
        \left( 1 + \epsilon - \widehat{F}_k\right)\, dw
     \end{align*}
    then 
    \begin{align*}
        UB_{k+1} - LB_{k+1} 
        \,\leq\,  
        \left( 2+\frac{2}{e}\right) \epsilon
    \end{align*}
 \end{lemma}
 \begin{proof}
    And indeed using the $UB_{k+1}$, $LB_{k+1}$ definitions 
    \begin{align*}
        &
            UB_{k+1}-LB_{k+1}
        \\ & 
            \quad\quad\quad\quad
            = \int_0^1 \left( 1-\widehat{F}_k\right) \left[ \left( \widehat{F}_k+\epsilon\right)^k
            - \left( \widehat{F}_k-\epsilon\right)^k \right]\; dw
        \\ & 
            \quad\quad\quad\quad\quad\quad\quad
            \,+\, 
            \epsilon \int_0^1 \left[ \left( \widehat{F}_k+\epsilon\right)^k + \left( \widehat{F}_k - \epsilon\right)^k \right]\; dw
        \\ & 
        \leq \int_0^1 \left( 1-\widehat{F}_k\right) \left[ \left( \widehat{F}_k + \epsilon\right)^k - \left( \widehat{F}_k - \epsilon\right)^k \right]\; dw
        + 2\epsilon    
    \end{align*}
    denote by 
    \begin{align*}
        I \,=\, \int_0^1 \left( 1-\widehat{F}_k\right) \left[ \left( \widehat{F}_k + \epsilon\right)^k - \left( \widehat{F}_k - \epsilon\right)^k \right]\; dw
    \end{align*}
    and observe that 
    \begin{align*}
        & 
            \left( \widehat{F_D}+\epsilon\right)^k - \left( \widehat{F_D}-\epsilon\right)^k 
        \\ & \quad\quad\quad\;\;
        \,=\, 
            2\epsilon\left[
            \frac{\left( \widehat{F_D}+\epsilon\right)^k - \left( \widehat{F_D}-\epsilon\right)^k}{2\epsilon} 
            \right]
        \,\approx\, 2\epsilon\,k\,\widehat{F_D}^{k-1}    
    \end{align*} 
    thus 
    \begin{align*}
        &
        I 
        \,=\, 
        \int_0^1 \left( 1-F_k\right) \left[ \left( \widehat{F}_k \,+\, \epsilon\right)^k - \left( \widehat{F}_k \,-\, \epsilon\right)^k \right]\; dw
        \\ &
        \,\approx\, 
        2\,\epsilon\,k\,\int_0^1 \left( 1-\widehat{F}_k\right)\cdot\left( \widehat{F}_k\right)^{k-1}\; dw
        \\ &
        \,=\, 
        2\epsilon\,k \left[\underset{\widehat{F}_k \leq 1-\delta}{\int}+\underset{1-\delta\leq \widehat{F}_k}{\int}\right] 
        \left( 1-\widehat{F}_k\right)\cdot\left( \widehat{F}_k\right)^{k-1}\; dw
        \\&
        \,\leq\, 
        2\epsilon\,k 
        \norm{\left( 1-\widehat{F}_k\right)\cdot\left( \widehat{F}_k\right)^{k-1}\;}_\infty
        \\ & 
        \,=\,
        2\,\epsilon\,k \underset{x \in \left[ 0, 1\right]}{\max}\, \left( 1-x\right)\, x^{k-1}    
        \\ & 
        \underbrace{\,=\,}_{\left( 6\right)} 
        2\epsilon\,k \left( \frac{\frac{1}{k}}{\frac{k-1}{k}}\right) \left( 1-\frac{1}{k}\right)^{k}
        \\ & 
        \,\approx\, 
        2\epsilon\,k \left( \frac{1}{k-1}\right) e^{-1}
        \,\approx\,
        \frac{2}{e} \epsilon
    \end{align*}
    when transition $\left( 6\right)$ is because the function 
    \begin{equation*}
        f\left( x\right) = x^{k-1} - x^k
    \end{equation*}
    gets its maximum at 
    \begin{equation}\label{23}
        f^{'}\left( x\right)
        = \left( k-1\right) x^{k-2} - k x^{k-1} 
        \implies x = 1 - \frac{1}{k}
    \end{equation}
    combining 
    \begin{align*}
        &
            UB_{k+1}-LB_{k+1}
        \\ & 
        \,\leq\,
        \int_0^1 \left( 1-\widehat{F}_k\right) \left[ \left( \widehat{F}_k + \epsilon\right)^k - \left( \widehat{F}_k - \epsilon\right)^k \right]\; dw
        + 2\epsilon    
        \\ & \quad\quad\quad\quad
        \,=\, I + 2\epsilon 
        \,\leq\ \frac{2}{e} \epsilon + 2 \epsilon 
        \,=\, \left( \frac{2}{e} + 2\right) \epsilon
    \end{align*}
    as needed $\hfill\square$
 \end{proof}
 

  


To conclude we showed an empirical estimator for the 
expected gain from the $k+1$ hyperparameter sample 
and bound the error with $O\left( \sqrt{\frac{\log k}{k}}\right)$.  

 







\subsection{Estimator development}
The next theorem presents a closed and more explicit 
formula for the empirical estimator defined thus far (\ref{thm_11}) 
\begin{theorem}
    Let $X_1, \hdots, X_n \sim \mathcal{D}$ be $n$ i.i.d random variables 
    we will denote the estimate gain from the $n+1$ sample 
    as defined in theorem (\ref{thm_11}) by 
    \begin{equation}\label{eq_int}
        S_n = \int_0^1\, F_n^n\cdot \left( 1 - F_n\right) \, d t 
    \end{equation}
    Assuming that $X_1, \hdots, X_n$ are given in their order 
    $X_1 \leq \hdots \leq X_n$ 
    and taking $X_{n+1}=1$. 
    Then a closed form representation for $S_n$ can be 
     \begin{equation}
            S_n 
        \,=\, 
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot \left( X_{k+1} - X_k \right) 
     \end{equation}
\end{theorem}
\begin{proof}
    Assuming $X_1 \leq \hdots \leq X_n$ 
    and denoting $I_k = \left[ X_k,\, X_{k+1}\right)$ 
    we have 
    \begin{equation*}
            F_n\left( x\right) 
        \,=\,
            \frac{1}{n}\,\overset{n}{\underset{k=1}{\Sigma}}\, 
            \mathbf{1}_{X_k \leq x} 
        \,=\,
            \frac{1}{n}\,\overset{n}{\underset{k=1}{\Sigma}}\, 
              k \cdot \mathbf{1}_{x \in I_k} 
    \end{equation*}
    and since all the $\left\{ I_k\right\}_{k=1}^n$ are mutually disjoint we have 
    \begin{equation*}
            F_n\left( x\right)^n 
        \,=\,
            \left( \frac{1}{n}\,\overset{n}{\underset{k=1}{\Sigma}}\, 
              k \cdot \mathbf{1}_{x \in I_k} \right)^n 
        \,=\,
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left[ \frac{k}{n}\right]^n \cdot \mathbf{1}_{x \in I_k}
    \end{equation*}
    thus denoting by $I$ the integrand of equation (\ref{eq_int}) 
    i.e. 
    \begin{align*}
        & 
            I 
            \,=\, F_n^n\cdot \left( 1 - F_n\right) 
        \\ & 
            \,=\, 
            \left( \overset{n}{\underset{k=1}{\Sigma}}\, 
              \left[ \frac{k}{n}\right]^n \cdot \mathbf{1}_{x \in I_k}\right) 
            \cdot 
            \left( 1 - \overset{n}{\underset{k=1}{\Sigma}}\, 
              \left[ \frac{k}{n}\right] \cdot \mathbf{1}_{x \in I_k}\right) 
        \\ & 
            \,=\, 
                \left( \overset{n}{\underset{k=1}{\Sigma}}\, 
                \left[ \frac{k}{n}\right]^n \cdot \mathbf{1}_{x \in I_k}\right) 
        \\ & 
            - 
            \left( \overset{n}{\underset{k=1}{\Sigma}}\, 
              \left[ \frac{k}{n}\right]^n \cdot \mathbf{1}_{x \in I_k}\right)
              \cdot 
            \left( \overset{n}{\underset{k=1}{\Sigma}}\, 
              \left[ \frac{k}{n}\right] \cdot \mathbf{1}_{x \in I_k}\right) 
        \\ & 
            \underbrace{\,=\,}_\textit{mutually disjoint} 
            \left( \overset{n}{\underset{k=1}{\Sigma}}\, 
              \left[ \frac{k}{n}\right]^n \cdot \mathbf{1}_{x \in I_k}\right) 
             - 
            \left( \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left[ \frac{k}{n}\right]^{n+1} \cdot \mathbf{1}_{x \in I_k}\right)
        \\ & 
            \underbrace{\,=\,}_\textit{mutually disjoint} 
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot \mathbf{1}_{x \in I_k}
    \end{align*}
    overall we get  
    \begin{align*}
        & 
            I 
            \,=\, 
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot \mathbf{1}_{x \in I_k}
    \end{align*}
    Taking the integral we end with 
    \begin{align*}
        & 
        S_n 
        \,=\, \int_0^1 F_n^n\cdot \left( 1 - F_n\right) \, d x  
        \\ & 
        \,=\, 
            \int_0^1 \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot \mathbf{1}_{t \in I_k} \; d x
        \\ & 
        \,=\, 
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot
            \int_0^1  \mathbf{1}_{x \in I_k} \; d x
        \\ & 
        \,=\, 
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot \abs{I_k}
        \\ & 
        \,=\, 
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot \left( X_{k+1} - X_k \right) 
    \end{align*}
    To sum up we ended with 
    \begin{align*}
        & 
            S_n 
        \,=\, 
            \overset{n}{\underset{k=1}{\Sigma}}\, 
            \left( \left[ \frac{k}{n}\right]^n - \left[ \frac{k}{n}\right]^{n+1} \right) 
            \cdot \left( X_{k+1} - X_k \right) 
    \end{align*}
    as needed $\hfill\square$
\end{proof}


\section{Lower bound}
\paragraph{}
In the previous section we established an estimator with bounded error on the expected gain from the $k+1$ hyperparameter tuning step. 
In this section we will bound from below the best error possible for such estimators. 
We will do so by bounding from below the error for
$X_1, \hdots,X_k \sim \mathcal{N}\left( \mu,\, \sigma\right)$ 
and thus derive a lower bound on the best possible error for 
$X_1, \hdots, X_k$ taken from a general distribution 

\paragraph{}
Let $X$ be normally distributed r.v. $ X \sim \mathcal{N}\left( \mu,\, \sigma\right)$ 
and let $\alpha$ be our highest achieved accuracy 
then the expected improvement from additional sample  
 is $\mathbb{E}\left[ X \,|\, X > \alpha\,\right]\,$ 
the next lemma provides estimate for this quantity 

\begin{lemma}\label{lem_3}
    For $X \sim \mathcal{N}\left( \mu, \sigma\right)$ 
    and $f_X,\, F_X$ the density and accumulative distribution 
    functions for $X$ the following equality holds 
    \begin{equation*}
        \mathbb{E}\left[ X \,|\, X > \alpha\,\right] 
        \,=\, 
        \mu + 
        \sigma^2 
        \frac{f_X\left( \alpha\right)}{1-F_X\left( \alpha\right)}
    \end{equation*}
\end{lemma}
\begin{proof}
    Well known as the inverse Mills ratio 
    \cite{greene2003econometric} 
    $\hfill\square$
\end{proof}


\begin{lemma}\label{lem_03}
    For $X\sim \mathcal{N}\left( \mu, \sigma\right)$ 
    a gaussian distribution and $\alpha \in \mathbb{R}$ 
    the current accuracy. 
    The expected improvement from 
    sampling one more point 
    is 
    $\mathbb{E}\left[\, 
    \left( X-\alpha\right) \cdot \mathbf{1}_{X \geq \alpha}
    \,\right]$
    and the following equality holds 
    \begin{equation}\label{eq_33}
            \mathbb{E}\left[\, 
                \left( X-\alpha\right) \cdot \mathbf{1}_{X \geq \alpha}
            \,\right] 
        \,=\, 
        \left( \mu - \alpha\right)
        \cdot
        \left( 1- F_X\left( \alpha \right) \right)
        \,+\,
        \sigma^2 \cdot 
        f_X\left( \alpha\right) 
    \end{equation}
\end{lemma}

\begin{proof}
    Developing the right hand side of (\ref{eq_33}) we have
    \begin{equation*}
            \mathbb{E}\left[\, 
                \left( X-\alpha\right) \cdot \mathbf{1}_{X \geq \alpha}
            \,\right] 
        \,=\, 
            \mathbb{E}\left[\, 
                \left( X-\alpha\right) \,|\,X \geq \alpha 
            \,\right] \cdot P\left( X \geq \alpha \right) 
    \end{equation*}
    \begin{equation*}
        \,=\,
            \left( \mathbb{E}\left[\, X \,|\,X 
            \geq \alpha\,\right] - \alpha\right)
            \cdot
            \left( 1- F_X\left( \alpha \right) \right)  
    \end{equation*}
    \begin{equation*}
        \underbrace{\,=\,}_\textit{Lemma (\ref{lem_3})}
            \left( 
                \mu - \alpha +
                \sigma^2 
                \frac{f_X\left( \alpha\right)}{1-F_X\left( \alpha\right)}  
            \right)
            \cdot
            \left( 1- F_X\left( \alpha \right) \right)  
    \end{equation*}
    \begin{equation*}
        \,=\,
            \left( \mu - \alpha\right)
            \cdot
            \left( 1- F_X\left( \alpha \right) \right)
            +
            \sigma^2 \cdot 
            f_X\left( \alpha\right) 
    \end{equation*}
    as needed $\hfill\hfill\square$
\end{proof}

\paragraph{}
Denoting by $\Hat{\mu},\,\Hat{\sigma}$ the empirical 
values for the gaussian $\mathcal{N}\left( \mu,\, \sigma\right)$ 
and noting that $\Hat{\mu},\,\Hat{\sigma}$ are sufficient 
statistics for the gaussian distribution the best 
estimator for the expected improvement 
from additional sampler is 
\begin{equation*}
        err = I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)
\end{equation*}
when 
\begin{equation*}
        I\left( \mu, \sigma, \alpha\right) 
    = 
        \left( \mu - \alpha\right)
        \cdot
        \left( 1- F_X\left( \alpha \right) \right)
        +
        \sigma^2 \cdot 
        f_X\left( \alpha\right) 
\end{equation*}
and $\alpha = \max\left( X_1, \hdots, X_n\right)\,$.  
Thus the discrepancy is lower bounded by 
\begin{align*}
    & 
            err
        \,=\,
            I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)
\end{align*}
and the total discrepancy in terms of the mean absolute error is  
\begin{align*}
    & 
            err_{ma} 
        \,=\, 
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\, 
                \abs{err}
            \,\right] 
        \,=\,
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,
                    I\left( \mu, \sigma, \alpha\right) - 
                    I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)
                \,}
            \,\right]
\end{align*}

Next we will lower bound the mean absolute error 
$err_{ma}\,$ and for that we will start 
with the following lemma 

\begin{lemma}\label{lem_lb_1} 
    $I$ is monotonic increasing in both 
    $\mu,\, \sigma$, more formally 
    \begin{align*}
        & 
        \frac{\partial}{\partial \mu}\, 
        I\left( \mu, \sigma, \alpha\right) \,\geq\, 0 
        \quad\textit{and}\quad 
        \frac{\partial}{\partial \sigma}\, 
        I\left( \mu, \sigma, \alpha\right) \,\geq\, 0 
    \end{align*}
\end{lemma}
\begin{proof}
    Deferred to appendix A  $\hfill\square$
\end{proof}




\begin{proposition}\label{prop_1}
    In particular we have
    \begin{align*}
    & \quad\quad
        \frac{\partial}{\partial \mu}\, 
        I\left( \mu, \sigma, \alpha\right) 
        \,=\, 1- F_{Z}\left( \frac{\alpha -\mu}{\sigma}\right) 
    \\ & 
        \textit{and}
    \\ & \quad\quad
        \frac{\partial}{\partial \sigma}\, 
        I\left( \mu, \sigma, \alpha\right) 
       \,=\, 
       \left[\, 2 \cdot \left( \frac{\alpha -\mu}{\sigma}\right)^2 + 1 \,\right] \cdot f_{Z}\left( \frac{\alpha -\mu}{\sigma}\right) 
    \end{align*}
\end{proposition}   
\begin{proof}
    Follows immediately from the proof of the last lemma (\ref{lem_lb_1}) 
    $\hfill\square$
\end{proof}

\begin{lemma}\label{lem_conv_1}
    $I$ is always convex in $\alpha$ 
    it is also convex in $\sigma$ whenever 
    \begin{align*}
         \alpha   
        \;\leq\; \mu - \sqrt{\frac{3}{2}}\sigma 
        \;\;\;\textit{or}\;\;\; 
        \alpha   
        \;\geq\; \mu + \sqrt{\frac{3}{2}}\sigma\,   
    \end{align*}
    more formally 
    \begin{align*}
        & 
        \frac{\partial^2}{\partial^2 \mu}\, 
        I\left( \mu, \sigma, \alpha\right) \,\geq\, 0 
        \quad\textit{and}\quad
        \frac{\partial^2}{\partial^2 \sigma}\, 
        I\left( \mu, \sigma, \alpha\right) \,\geq\, 0 
    \end{align*}
    when the second inequality holds in the specified range. 
\end{lemma}
\begin{proof}
    Deferred to appendix B $\hfill\square$
\end{proof}



\begin{lemma}\label{lem_4}
    The following equality holds for the discrepancy 
    $\Hat{\mu} - \mu$
    \begin{align*}
        \underset{\Hat{\mu}}{\mathbb{E}}\left[\,
              \Hat{\mu} - \mu  
            \;|\; \Hat{\mu} - \mu > 0 
        \,\right]  
    \,=\, 
        \sqrt{\frac{2}{ \pi}}
        \cdot\frac{\sigma^2}{n}   
    \end{align*}
\end{lemma}
\begin{proof}
    Observe that 
    $
    \Hat{\mu} = \overline{X_n} 
    \,\sim\, 
    \mathcal{N}\left( \mu,\, \frac{\sigma}{\sqrt{n}}\right)
    \,$ 
    and thus 
    $
    \Hat{\mu} - \mu  
    \sim \mathcal{N}\left( 0,\, \frac{\sigma}{\sqrt{n}}\right)
    $ 
    denoting $Y = \Hat{\mu} - \mu$ and 
    using lemma (\ref{lem_3}) we have 
    \begin{align*}
        & 
            \mathbb{E}\left[ Y \,|\, Y > \alpha\,\right] 
            \,=\, 
            \mu_Y + 
            \sigma_Y^2 
            \frac{f_Y\left( \alpha\right)}{1-F_Y\left( \alpha\right)}
    \end{align*}
    taking $Y=\Hat{\mu} - \mu$ and $\alpha = 0$ results in 
    \begin{align*}
        &         
            \underset{\Hat{\mu}}{\mathbb{E}}\left[\,
                \Hat{\mu} - \mu  
                \;|\; \Hat{\mu} - \mu > 0 
            \,\right]  
        \,=\, 
            \mathbb{E}\left[ Y \,|\, Y > \alpha\,\right] 
        \\ & 
        \,=\, 
            \mu_Y + 
            \sigma_Y^2 
            \frac{f_Y\left( \alpha\right)}{1-F_Y\left( \alpha\right)}
        \,=\, 
            0 + 
            \left( \frac{\sigma}{\sqrt{n}}\right)^2 
            \frac{f_Z\left( 0\right)}{1-F_Z\left( 0\right)}
        \\ & 
        \,=\, 
            \frac{\sigma^2}{n} \cdot 
            \frac{\frac{1}{\sqrt{2 \pi}}}{1-\frac{1}{2}}
        \,=\, 
            \frac{\sigma^2}{n} \cdot 
            \frac{2}{\sqrt{2 \pi}}
        \,=\, 
            \sqrt{\frac{2}{ \pi}}
            \cdot\frac{\sigma^2}{n} 
            \quad\quad\quad\;\;\;\square
    \end{align*}
\end{proof}

The next lemma establish lower bound on the mean absolute error
$err_{ma}$ 
of the best estimator for the expected improvement 
by one more hyperparameter tuning step  

\begin{lemma} 
    The following lower bound on $err_{ma}$ holds   
    \begin{align*}
        & 
                err_{ma} 
            \,=\, 
                \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\, 
                    \abs{err}
                \,\right] 
            \,=\,
                \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                    \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,}
                \,\right] 
        \\ & \quad\quad\quad\quad\quad\quad\quad\quad\;
            \,\geq\,
                \frac{\sigma^2}{2 \,\sqrt{2\, \pi}\, n} 
                \cdot 
               \left[\, 1 - F_X\left( \alpha\right) \,\right] 
    \end{align*}
\end{lemma}

\begin{proof}
    \begin{align*}
        &
            err_{ma} 
        \,=\,
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,}
            \,\right] 
        \\ & 
        \,\geq\, 
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,} 
                \;|\; \Hat{\mu} > \mu \quad\textit{and}\quad \Hat{\sigma} > \sigma 
            \,\right]  
        \\ & \quad\;\;
            \cdot
            P\left( \Hat{\mu} > \mu \quad\textit{and}\quad \Hat{\sigma} > \sigma\right)
        \\ &  
            \underbrace{\,=\,}_\textit{symmetry}
            \frac{1}{4} \cdot \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,} 
                \;|\; \Hat{\mu} > \mu \,,\; \Hat{\sigma} > \sigma 
            \,\right] 
        \\&  
            \underbrace{\,=\,}_\textit{lemma (\ref{lem_lb_1})}
            \frac{1}{4} \cdot \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \,I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right) - I\left( \mu, \sigma, \alpha\right) \,
                \;|\; \Hat{\mu} > \mu\,,\; \Hat{\sigma} > \sigma 
            \,\right] 
        \\ &  
            \,=\,
            \frac{1}{4} \cdot\left[\, \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \,I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,
                \;|\; \Hat{\mu} > \mu \,,\; \Hat{\sigma} > \sigma 
            \,\right] - I\left( \mu, \sigma, \alpha\right) \,\right]   
        \\ &  
            \underbrace{\,\geq\,}_\textit{lemma (\ref{lem_lb_1})} 
            \frac{1}{4} \cdot\left[\, \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \,I\left( \Hat{\mu}, \sigma, \alpha\right)\,
                \;|\; \Hat{\mu} > \mu \,,\; \Hat{\sigma} > \sigma 
            \,\right] - I\left( \mu, \sigma, \alpha\right) \,\right] 
        \\ &  
            \,=\, 
            \frac{1}{4} \cdot\left[\, \underset{\Hat{\mu}}{\mathbb{E}}\left[\,
                \,I\left( \Hat{\mu}, \sigma, \alpha\right)\,
                \;|\; \Hat{\mu} > \mu 
            \,\right] - I\left( \mu, \sigma, \alpha\right) \,\right] 
        \\ &  
            \,=\, 
            \frac{1}{4} \cdot \underset{\Hat{\mu}}{\mathbb{E}}\left[\,
                I\left( \Hat{\mu}, \sigma, \alpha\right)
                 - I\left( \mu, \sigma, \alpha\right)
                \;|\; \Hat{\mu} > \mu 
            \,\right]  
        \\ &  
            \underbrace{\,\geq\,}_\textit{lemma (\ref{lem_conv_1})} 
            \frac{1}{4} \cdot \underset{\Hat{\mu}}{\mathbb{E}}\left[\,
                 \frac{\partial}{\partial \mu} I\left( \mu, \sigma, \alpha\right) 
                 \cdot \left( \Hat{\mu} - \mu\right) 
                \;|\; \Hat{\mu} > \mu 
            \,\right]  
        \\ &  
            \,=\, 
            \frac{1}{4} \cdot 
            \frac{\partial}{\partial \mu}\, I\left( \mu, \sigma, \alpha\right)
            \cdot 
            \underset{\Hat{\mu}}{\mathbb{E}}\left[\,
                  \Hat{\mu} - \mu  
                \;|\; \Hat{\mu} > \mu 
            \,\right]  
        \\&  
            \,=\, 
            \frac{1}{4} \cdot 
            \frac{\partial}{\partial \mu}\, I\left( \mu, \sigma, \alpha\right)
            \cdot 
            \underset{\Hat{\mu}}{\mathbb{E}}\left[\,
                  \Hat{\mu} - \mu  
                \;|\; \Hat{\mu} - \mu > 0 
            \,\right]  
        \\ & 
            \underbrace{\,=\,}_\textit{lemma (\ref{lem_4})}   
            \frac{1}{4} \cdot 
            \frac{\partial}{\partial \mu}\, I\left( \mu, \sigma, \alpha\right)
            \cdot 
            \sqrt{\frac{2}{\pi}}\cdot\frac{\sigma^2}{n}
        \\ & 
            \underbrace{\,=\,}_\textit{proposition (\ref{prop_1})}   
            \frac{\sigma^2}{2 \,\sqrt{2\, \pi}\, n} 
            \cdot 
            \left[\, 1- F_{Z}\left( \frac{\alpha -\mu}{\sigma}\right) \,\right]
        \\ & 
            \,=\,   
            \frac{\sigma^2}{2 \,\sqrt{2\, \pi}\, n} 
            \cdot 
           \left[\, 1 - F_X\left( \alpha\right) \,\right] 
           \quad\quad\quad\quad\quad\;\;\;
           \quad\quad\quad\quad\quad\;\;\;
           \hfill\square
    \end{align*}
\end{proof}


\begin{lemma} 
    In the region
    $\alpha \;\geq\; \mu + \sqrt{\frac{3}{2}}\cdot\sigma\,$
    the following lower bound holds 
    \begin{align*}
        & 
                err_{ma} 
            \,=\, 
                \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\, 
                    \abs{err}
                \,\right] 
            \,=\,
                \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                    \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,}
                \,\right] 
        \\ & \quad\quad\quad\quad\quad\quad\;
            \,\geq\,
           \frac{\sigma}{2 \cdot e^\frac{3}{2}\cdot n} 
           \cdot \left( \frac{\alpha -\mu}{\sigma}\right)^2 
            \cdot f_{X}\left( \alpha\right) 
    \end{align*}
\end{lemma}

\begin{proof}
    \begin{align*}
        &
            err_{ma} 
        \,=\,
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,}
            \,\right] 
        \\ & 
        \,\geq\, 
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,} 
                \;|\; \Hat{\mu} > \mu \quad\textit{and}\quad \Hat{\sigma} > \sigma 
            \,\right]  
        \\ & \quad\;\;
            \cdot
            P\left( \Hat{\mu} > \mu \quad\textit{and}\quad \Hat{\sigma} > \sigma\right)
        \\ &  
            \underbrace{\,=\,}_\textit{symmetry}
            \frac{1}{4} \cdot \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,} 
                \;|\; \Hat{\mu} > \mu \,,\; \Hat{\sigma} > \sigma 
            \,\right] 
        \\&  
            \underbrace{\,=\,}_\textit{lemma (\ref{lem_lb_1})}
            \frac{1}{4} \cdot \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \,I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right) - I\left( \mu, \sigma, \alpha\right) \,
                \;|\; \Hat{\mu} > \mu\,,\; \Hat{\sigma} > \sigma 
            \,\right] 
        \\&  
            \,=\,
            \frac{1}{4} \cdot\left[\, \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \,I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,
                \;|\; \Hat{\mu} > \mu \,,\; \Hat{\sigma} > \sigma 
            \,\right] - I\left( \mu, \sigma, \alpha\right) \,\right]   
        \\ &  
            \underbrace{\,\geq\,}_\textit{lemma (\ref{lem_lb_1})} 
            \frac{1}{4} \cdot\left[\, \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \,I\left( \mu, \Hat{\sigma}, \alpha\right)\,
                \;|\; \Hat{\mu} > \mu \,,\; \Hat{\sigma} > \sigma 
            \,\right] - I\left( \mu, \sigma, \alpha\right) \,\right] 
        \\ &  
            \,=\, 
            \frac{1}{4} \cdot\left[\, \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
                \,I\left( \mu, \Hat{\sigma}, \alpha\right)\,
                \;|\; \Hat{\sigma} > \sigma 
            \,\right] - I\left( \mu, \sigma, \alpha\right) \,\right] 
        \\ &  
            \,=\, 
            \frac{1}{4} \cdot \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
                I\left( \mu, \Hat{\sigma}, \alpha\right)
                 - I\left( \mu, \sigma, \alpha\right)
                \;|\; \Hat{\sigma} > \sigma 
            \,\right]  
        \\ &  
            \underbrace{\,\geq\,}_\textit{lemma (\ref{lem_conv_1})} 
            \frac{1}{4} \cdot \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
                 \frac{\partial}{\partial \sigma} 
                 I\left( \mu, \sigma, \alpha\right) 
                 \cdot \left( \Hat{\sigma} - \sigma\right) 
                \;|\; \Hat{\sigma} > \sigma 
            \,\right]  
        \\ &  
            \,=\, 
            \frac{1}{4} \cdot 
            \frac{\partial}{\partial \sigma}\, I\left( \mu, \sigma, \alpha\right)
            \cdot 
            \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
                  \Hat{\sigma} - \sigma  
                \;|\; \Hat{\sigma} > \sigma
            \,\right]  
        \\&  
            \,=\, 
            \frac{1}{4} \cdot 
            \frac{\partial}{\partial \sigma}\, I\left( \mu, \sigma, \alpha\right)
            \cdot 
            \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
                  \Hat{\sigma} - \sigma  
                \;|\; \Hat{\sigma} - \sigma > 0
            \,\right]  
        \\&  
            \underbrace{\,\geq\,}_\textit{lemma (\ref{lem_5})}
            \frac{\sigma}{4 \cdot e^\frac{3}{2}\cdot n} \cdot 
            \frac{\partial}{\partial \sigma}\, I\left( \mu, \sigma, \alpha\right)
        \\ & 
            \underbrace{\,=\,}_\textit{(\ref{prop_1})}
           \frac{\sigma}{4 \cdot e^\frac{3}{2}\cdot n} 
           \cdot
           \left[\, 2 \cdot \left( \frac{\alpha -\mu}{\sigma}\right)^2 + 1 \,\right] 
            \cdot f_{Z}\left( \frac{\alpha -\mu}{\sigma}\right)
        \\ & 
            \,\geq\,
           \frac{\sigma}{2 \cdot e^\frac{3}{2}\cdot n} 
           \cdot \left( \frac{\alpha -\mu}{\sigma}\right)^2 
            \cdot f_{Z}\left( \frac{\alpha -\mu}{\sigma}\right) 
        \\ & 
           \,=\,
           \frac{\sigma}{2 \cdot e^\frac{3}{2}\cdot n} 
           \cdot \left( \frac{\alpha -\mu}{\sigma}\right)^2 
            \cdot f_{X}\left( \alpha\right) 
    \end{align*}
    as needed $\hfill\square$ 
\end{proof}

\begin{lemma}\label{lem_5}
    The following lower bound holds for the discrepancy 
    $\Hat{\sigma} - \sigma$
    \begin{align*}
        \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
              \Hat{\sigma} - \sigma  
            \;|\; \Hat{\sigma} - \sigma > 0 
        \,\right]  
    \,\geq\, 
       \frac{\sigma}{e^{\frac{3}{2}} \cdot n}
    \end{align*}
\end{lemma}
\begin{proof}
    By $\Hat{\sigma}$ definition we have    
    \begin{align*}
        &
        \Hat{\sigma}^2
        = 
        \frac{1}{n-1} 
        \overset{n}{\underset{i=1}{\Sigma}}\, 
        \left( x_i - \overline{x}\right)^2 
        \,\sim\, 
        \frac{\sigma^2}{n-1}\; \chi_{n-1}^2  
    \end{align*}
    when $\chi_{n-1}^2$ is the distribution defined by 
    \begin{align*}
        &
            f_{\chi_{n-1}^2}\left( x\right) 
        \,=\,
            \frac{x^{\frac{k}{2}-1} e^{-\frac{x}{2}}}{\Gamma\left( \frac{k}{2}\right) 2^{\frac{k}{2}}} 
    \end{align*} 
    and thus 
    \begin{align*}
        &
        \Hat{\sigma}
        = 
        \sqrt{\frac{1}{n-1} 
        \overset{n}{\underset{i=1}{\Sigma}}\, 
        \left( x_i - \overline{x}\right)^2}
        \,\sim\, 
        \sigma \cdot \sqrt{\frac{\,\chi_{n-1}^2}{n-1}} 
    \end{align*}
    substituting we have 
    \begin{align*}
    &
        \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
              \Hat{\sigma} - \sigma  
            \;|\; \Hat{\sigma} - \sigma > 0 
        \,\right]  
    \\ & 
    \,=\, 
        \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
            \sigma \cdot \sqrt{\frac{\,\chi_{n-1}^2}{n-1}} \,-\, \sigma  
            \;|\;\, \sqrt{\frac{\chi_{n-1}^2}{n-1}} \,>\, 1 
        \,\right]  
    \\ & 
    \,=\, 
        \sigma \cdot 
        \underset{\chi_{n-1}^2}{\mathbb{E}}\left[\,
            \sqrt{\frac{\chi_{n-1}^2}{n-1}} - 1  
            \;|\;\, \sqrt{\frac{\chi_{n-1}^2}{n-1}} - 1\,>\, 0 
        \,\right]  
    \\ & 
    \,=\, 
        \frac{\sigma}{1-F_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( 1\right)} 
        \cdot 
        \underset{\chi_{n-1}^2}{\mathbb{E}}\left[\,
            \left(\, \sqrt{\frac{\chi_{n-1}^2}{n-1}} - 1 \,\right)^{+} 
        \,\right]  
    \\ & 
    \underbrace{\,\geq\,}_{\left( 4 \right)} 
        \frac{\sigma}{1-F_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( 1\right)} 
        \cdot \gamma \cdot \left[\, 1 - F_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( 1+\gamma\right) \,\right] 
    \\ & 
    \underbrace{\,=\,}_\textit{lemma (\ref{lem_21})}
        \sigma\cdot \gamma \cdot
         \frac{1 - F_{\chi_{n-1}^2}\left( \left(\, n-1 \,\right) \left(\, 1+\gamma \,\right)^2\right) }
        {1-F_{\chi_{n-1}^2}\left(\, n-1 \,\right)}
    \\ & 
    \,=\,
        \sigma\cdot \gamma \cdot
         \frac{1 - \frac{\gamma\left( \frac{n-1}{2}, \frac{\left(\, n-1 \,\right) \left(\, 1+\gamma \,\right)^2}{2}\right)}
         {\Gamma\left( \frac{n-1}{2}\right)}}
        {1 - \frac{\gamma\left( \frac{n-1}{2}, \frac{ n-1 }{2}\right)}
         {\Gamma\left( \frac{n-1}{2}\right)}}
    \\ & 
    \,=\,
        \sigma\cdot \gamma \cdot
         \frac{\Gamma\left( \frac{n-1}{2}\right) - 
         \gamma\left( \frac{n-1}{2}, \frac{\left(\, n-1 \,\right) \left(\, 1+\gamma \,\right)^2}{2}\right)}
        {\Gamma\left( \frac{n-1}{2}\right) - \gamma\left( \frac{n-1}{2}, \frac{ n-1 }{2}\right)}
    \\ & 
    \,=\,
        \sigma\cdot \gamma \cdot
         \frac{\Gamma\left( \frac{n-1}{2}, \frac{\left(\, n-1 \,\right) \cdot \left(\, 1+\gamma \,\right)^2}{2}\right)}
        {\Gamma\left( \frac{n-1}{2}, \frac{ n-1 }{2}\right)}
    \\ & 
    \underbrace{\,\geq\,}_\textit{lemma (\ref{lem_23})} 
        \sigma\cdot \gamma \cdot 
        e^{- \left( \gamma + \frac{\gamma^2}{2}\right) \cdot\left( n-1\right)}
    \end{align*}
    when $\gamma \in \mathbb{R}_{>0}$ is arbitrary constant and 
    transition $\left( 4\right)$ is due to the markov inequality,        
    writing again for clarity  
    \begin{align*}
        \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
              \Hat{\sigma} - \sigma  
            \;|\; \Hat{\sigma} - \sigma > 0 
        \,\right]  
        \,\geq\, 
        \sigma\cdot \gamma \cdot 
        e^{- \left( \gamma + \frac{\gamma^2}{2}\right) \cdot\left( n-1\right)}
    \end{align*}
    choosing $\gamma=\frac{1}{n}$ we end with 
    \begin{align*}
        \underset{\Hat{\sigma}}{\mathbb{E}}\left[\,
              \Hat{\sigma} - \sigma  
            \;|\; \Hat{\sigma} - \sigma > 0 
        \,\right]  
        \,\geq\, 
        \frac{\sigma}{e^{\frac{3}{2}} \cdot n} 
    \end{align*}
    as needed 
    $\hfill\square$
\end{proof}

The next lemma present $\sqrt{\frac{\chi_{n-1}^2}{n-1}}$ 
density and cumulative functions in terms of 
the corresponding $\chi_{n-1}^2$-density and cumulative functions  


\begin{lemma}\label{lem_21}
     $\sqrt{\frac{\chi_{n-1}^2}{n-1}}$ cumulative function 
     can be computed by 
    \begin{align*}
        &
        F_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( x\right) 
        \,=\, 
        F_{\chi_{n-1}^2}\left(\, \left[ n-1\right]\cdot x^2 \,\right)
    \end{align*}
    and the density function by 
    \begin{align*}
        &
        f_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( x\right) 
        \,=\, 
        2 \cdot \left( n-1\right)\cdot x \cdot f_{\chi_{n-1}^2}\left(\, \left[ n-1\right]\cdot x^2 \,\right)
    \end{align*}
\end{lemma}
\begin{proof}
    \begin{align*}
        &
        F_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( x\right) 
        \,=\, 
        \mathbb{P}\left[\; \sqrt{\frac{\chi_{n-1}^2}{n-1}} \,\leq\, x \;\right] 
        \,=\, 
        \mathbb{P}\left[\; \frac{\chi_{n-1}^2}{n-1} \,\leq\, x^2 \;\right] 
        \\ & 
        \,=\, 
        \mathbb{P}\left[\; \chi_{n-1}^2 \,\leq\, \left( n-1\right)\cdot x^2 \;\right]  
        \,=\, 
        F_{\chi_{n-1}^2}\left(\, \left[ n-1\right]\cdot x^2 \,\right) 
    \end{align*}
    similarly 
    \begin{align*}
    &
        f_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( x\right) 
        \,=\, 
        \frac{\partial}{\partial x}\, F_{\sqrt{\frac{\chi_{n-1}^2}{n-1}}}\left( x\right)
        \,=\, 
        \frac{\partial}{\partial x}\, F_{\chi_{n-1}^2}\left(\, \left[ n-1\right]\cdot x^2 \,\right)
    \\ & 
        \,=\, 
        2 \left[ n-1\right]\cdot x \cdot f_{\chi_{n-1}^2}\left(\, \left[ n-1\right]\cdot x^2 \,\right) 
        \quad\quad\quad\quad\quad\quad\quad\quad\square
    \end{align*}
\end{proof}

\begin{lemma}\label{lem_23}
    The following inequality holds 
    \begin{align*}
        \forall s,\, x,\, y \in \mathbb{R}_{>0}\quad\quad
        \frac{\Gamma\left( s, x+y\right)}{\Gamma\left( s, x\right)} 
        \,\geq\, e^{-y} 
    \end{align*}
\end{lemma}
\begin{proof}
    Deferred to appendix C. $\hfill\square$
\end{proof}


\begin{conclusion}
    The mean absolute error $err_{ma}$ is bounded from below by 
    \begin{align*}
        & 
            err_{ma} 
        \,=\, 
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\, 
                \abs{err}
            \,\right] 
        \,=\,
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)
            \,\right] 
        \\ & \quad\quad\quad\quad\quad\quad\quad\quad\quad\;\;\;
        \,\geq\,            
            \frac{\sigma^2}{2 \,\sqrt{2\, \pi}\, n} 
            \cdot 
           \left[\, 1 - F_X\left( \alpha\right) \,\right] 
    \end{align*}
    and for $\alpha \,\geq\, \mu + \sqrt{\frac{3}{2}}\cdot \sigma\,$ 
    the bound can be improved to  
    \begin{align*}
        & 
            err_{ma} 
        \,=\, 
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\, 
                \abs{err}
            \,\right] 
        \,=\,
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)
            \,\right] 
        \\ & \quad\quad\quad\quad\quad\quad\quad\;\;
        \,\geq\,            
            \frac{\sigma}{2 \cdot e^\frac{3}{2}\cdot n} 
           \cdot \left( \frac{\alpha -\mu}{\sigma}\right)^2 
            \cdot f_{X}\left( \alpha\right) 
    \end{align*}
    fixing the problem we have the following 
    asymptotic bound in $n,\, \alpha$ 
    \begin{align*}
        & 
            err_{ma} 
        =
            \underset{\Hat{\mu},\, \Hat{\sigma}}{\mathbb{E}}\left[\,
                \abs{\,I\left( \mu, \sigma, \alpha\right) - I\left( \Hat{\mu}, \Hat{\sigma}, \alpha\right)\,}
            \,\right] 
        \,=\,            
           \Omega\left( \frac{\alpha^2 \cdot f_{X}\left( \alpha\right)}{n} \right)  
    \end{align*}
\end{conclusion}

\section{Conclusion}
To conclude, in the paper we provided an estimate for the improvement provided by every additional iteration using the DKW inequality, and bounded our error by: 
\begin{align*}
    O\left( \sqrt{\frac{\log k}{k}}\right)   
\end{align*}

\paragraph{}
Next, we bounded from below the best possible mean absolute error of any estimate by
\begin{align*}
   err_{ma} 
   \,\geq\, 
   \frac{\sigma^2}{2 \,\sqrt{2\, \pi}\, k} 
    \cdot 
    \left[\, 1 - F_X\left( \alpha\right) \,\right] 
\end{align*}
and showed an improved bound 
\begin{align*}
    & 
        err_{ma} 
    \,=\,            
       \Omega\left( \frac{\alpha^2 \cdot f_{X}\left( \alpha\right)}{k} \right)  
\end{align*}
for the case $\alpha \geq \mu + \sqrt{\frac{3}{2}} \sigma$. 
This concludes our proof by showing that the bound on our estimator's error is non-trivial and limits the best possible bound we can hope for.

\paragraph{}
We leave for future research to estimate the expected improvement of different methods of hyperparameter tuning such as grid search \cite{claesen2014easy} or bayesian sampling \cite{eggensperger2013towards}.    





\newpage
