\[\begin{equation}\lambda^{(*)} = \underset{\lambda \in \Sigma}{argmin}{\mathbb{E}_{x \sim \mathcal{G}_{x}}\left[\mathcal{L}\left(x ; \mathcal{A}_{\lambda}\left(\mathcal{X}^{(train)}\right)\right)\right]}\label{eq:hyper-optimization}\end{equation}\]

• learning algorithm \(\mathcal{A}\): find function \(f\) minimizes loss \(\mathcal{L}(x;f)\) over i.i.d. samples \(x\) from grand truth distribution \(\mathcal{G}_x\).
  • \(\mathcal{A} : \mathcal{X}^{(train)} \rightarrow f\)
• Given hyper parameter \(\lambda \in \Sigma\), \(f = \mathcal{A}_\lambda\left(\mathcal{X}^{(train)}\right)\)
• The formula is to find \(\lambda\) which optimizes the expected loss

• \(\eqref{eq:hyper-optimization}\) does not have efficient algorithm
• \(\mathcal{G}_x\) is approximated by \(\mathcal{X}^{(valid)}\)
• Search the trial points \(\{\lambda^{(1)}, \lambda^{(2)}, ..., \lambda^{(S)}\}\) for optimal parameter

\[\begin{eqnarray} \lambda^{(*)} &\approx& \underset{\lambda \in \Sigma}{argmin} \underset{x \in \mathcal{X}^{(valid)}}{mean} \mathcal{L}\left( x ; \mathcal{A}_\lambda \left(X^{(train)}\right) \right) \\ &=& \underset{\lambda \in \Sigma}{argmin} \Psi(\lambda) \\ &\approx& \underset{\lambda \in \{\lambda^{(1)}, \lambda^{(2)}, ..., \lambda^{(S)}\}}{argmin} \Psi(\lambda) = \hat{\lambda} \end{eqnarray}\]

• Grid Search
  • Combination of all possible values
• Manual Search
  • Domain Knowledge
  • Intuition

• \(\lambda = (C, \sigma)\)
  • \(C\): regularization penalty
  • \(\sigma\): Gaussian kernel
• \(C = (0.01, 0.1, 1, 10)\)
• \(\sigma = (0.001, 0.01, 0.1)\)
• Trial Set: \(\{(0.01, 0.001), (0.01, 0.01), (0.01, 0.1), (0.1, 0.001), ..., (10, 0.1)\}\)

• Manual optimization gives researchers some degree of insight into \(\Psi\)
• There is no technical overhead or barrier to manual optimization
• Grid search is simple to implement and parallelization is trivial
• Grid search typically find a better \(\hat{\lambda}\) than purely manual sequential optimization(in the same amount of time)
• Grid search is reliable in low dimensional spaces

• Grid Search: curse of dimensionality
• Manual Search: reproducing results

• Independently and uniformly draw from \(\Sigma\) to produce trial set

• Roughly equivalent to manual search + grid search
• Implementation simplicity
• Reproducibility of pure grid search
• Adding new trials to the set or ignoring are both feasible

• \(\Psi\) are more sensitive to changes in some dimensions than others.
• For example, if \(f(x1, x2) \approx g(x1)\), then \(f\) has low effective dimension.

• \(\Psi^{(valid)}(\lambda) = \underset{x \in \mathcal{X}^{(valid)}}{mean} \mathcal{L}\left(x ; \mathcal{A}_\lambda \left( \mathcal{X}^{(train)} \right)\right)\)
• \(\Psi^{(test)}(\lambda) = \underset{x \in \mathcal{X}^{(test)}}{mean} \mathcal{L}\left(x ; \mathcal{A}_\lambda \left( \mathcal{X}^{(train)} \right)\right)\)

• Pick \(\hat{\lambda}\) that optimizes \(\Psi^{(valid)}(\lambda^{(s)})\)
• Compare \(\Psi^{(test)}(\hat{\lambda})\)

• Model both \(\Psi(\lambda)\) as a random variable
  • The uncertainty comes from the approximation between \(\mathbb{G}_x\) and \(\mathcal{X}\)

• It depends on the loss. For example, the variance of 0-1 loss is:
  • \(\mathbb{V}^{(valid)}(\lambda) = \frac{\Psi^{(valid)}(\lambda)\left(1 - \Psi^{(valid)}(\lambda)\right)}{\left|\mathcal{X}^{(valid)}\right| - 1}\)
  • \(\mathbb{V}^{(test)}(\lambda) = \frac{\Psi^{(test)}(\lambda)\left(1 - \Psi^{(test)}(\lambda)\right)}{\left|\mathcal{X}^{(test)}\right| - 1}\)

• Let \(Z^{(i)} \sim \mathcal(N)\left( \Psi^{(valid)}(\lambda^{(i)}), \mathbb{V}^{(valid)}(\lambda^{(i)}) \right)\)
• The probability of pick \(s\) as \(\hat{\lambda}\) is \(P\left(Z^{(s)} < Z^{(s')}, \forall s' \neq s\right)\)
  • Let \(w_s = P\left(Z^{(s)} < Z^{(s')}, \forall s' \neq s\right)\)
• The mean of \(\Psi^{(test)}(\hat{\lambda})\): \[\mu_Z = \sum_{s=1}^{S}{w_s \Psi^{(test)}(\lambda^{(s)})}\]
• The variance of \(\Psi^{(test)}(\hat{\lambda})\): \[\sigma_Z^2 = - \mu_Z^2 + \sum_{s=1}^{S} w_s\left(\Psi^{(test)}(\lambda^{(s)})^2 + \mathbb{V}^{(test)}(\lambda^{(s)})\right)\]

• 28x28 pixel grey scale of digits
• 10 classes
• https://www.iro.umontreal.ca/%20%cc%83lisa/twiki/bin/view.cgi/Public/DeepVsShallowComparisonICML2007 (404?)

• mnist basic: 10000 training, 2000 validation, 50000 testing
• mnist background: 10000 training, 2000 validation, 50000 testing
• mnist rotated: 10000 training, 2000 validation, 50000 testing
• mnist rotated background: 10000 training, 2000 validation, 50000 testing
• rectangles: 1000 training, 200 validation, 50000 testing
• rectangles images: 10000 training, 2000 validation, 50000 testing

• Similar to Larochelle et al. (2007)
• The type of data preprocessing: none, normalize, PCA(with different detailed settings)
• Pretraining:
  • Distributions: uniform on (-1, 1), unit normal
  • Scaling heuristics: between 0.1 and 10.0 divided by the square root of the number of inputs, the square root of 6 divided by the square rott of the number of inputs plus hidden units
• Number of hidden units is drawn geometrically from 18 to 1024
• Activity function: sigmoidal or tanh nonlinearity
• Minibatch: 20 or 100

• Learning rate \(\varepsilon_0\) is drawn geometrically from 0.001 to 10
• annealed learning rate \(t_0\) is drawn geometrically from 300 to 30000. The final learning rate is \(\varepsilon_t = \frac{t_0\varepsilon_0}{max(t, t_0)}\)
• \(L_2\) regularization is drawn exponentially from \(3.1 \times 10^{-7}\) to \(3.1 \times 10^{-5}\).