Optimizing Large-Scale Hyperparameters via Automated Learning Algorithm
Authors: Bin Gu
Guodong Liu
Yanfu Zhang
Xiang Geng
Heng Huang
Venue:  (2021)

Abstract: Modern machine learning algorithms usually involve tuning multiple (from one to  thousands) hyperparameters which play a pivotal role  in terms of model  generalizability. Globally choosing appropriate values of hyperparameters is extremely  computationally challenging. Black-box optimization and gradient-based algorithms are  two dominant approaches to hyperparameter optimization while  they have totally  distinct advantages. How to design a new hyperparameter optimization technique inheriting all benefits  from both approaches is still an open problem. To address this challenging problem, in this paper, we  propose a new  hyperparameter optimization  method with zeroth-order hyper-gradients (HOZOG). Specifically, we first exactly formulate  hyperparameter optimization  as  an $\mathcal{A}$-based constrained optimization problem, where $\mathcal{A}$ is  a black-box optimization algorithm (such as deep neural network). Then, we use the average zeroth-order hyper-gradients  to update  hyperparameters. We provide the feasibility analysis of using  HOZOG to achieve hyperparameter optimization.  The experimental  results on three representative  hyperparameter (the size is from 1 to 1250) optimization tasks  demonstrate the benefits of HOZOG  in terms of  \textit{simplicity, scalability, flexibility, effectiveness and efficiency} compared with the  state-of-the-art hyperparameter optimization methods.

Under review as a conference paper at ICLR 2021
OPTIMIZING LARGE-SCALE HYPERPARAMETERS VIA AUTOMATED LEARNING ALGORITHM
Anonymous authors Paper under double-blind review
ABSTRACT
Modern machine learning algorithms usually involve tuning multiple (from one to thousands) hyperparameters which play pivotal role in terms of model generaliz- ability. Black-box optimization and gradient- based algorithms are two dominant approaches hyperparameter optimization while they have totally distinct advan- tages. How to design a new hyperparameter optimization technique inheriting all benefits from both approaches is still an open problem. To address this challenging problem, in this paper, we propose new hyperparameter optimization method with zeroth-order typer-gradients (HOZOG), Specifically, we first exactly formulate hyperparameter optimization an A-based constrained optimization problem, where A is a black-box box optimization algorithm (such as deep neural network). Then, we use the average zeroth-order hyper-gradient to update hyperparameters. We provide the feasibility analysis using HOZOG to achieve hyperparameter op- timization. Finally, the experimental results three representative hyperparameter (the size is from I to 1250) optimization tasks demonstrate the benefits of HOZOG in terms of simplicity, scalability, flexibility, effectiveness and efficiency compared with the state-of-the- hyperparameter optimization methods.
INTRODUCTION
Modern machine learning algorithms usually involve tuning multiple hyperparameters whose size could be from thousands. For example, support vector machines (Vapnik, 2013) have the regu- larization parameter and kernel hyperparameter, deep neural networks (Krizhevsky et al., 2012) have the optimization hyperparameters (e.g., learning rate schedules and momentum) and regularization hyperparameters (e.g.. weight decay and dropout rates). The performance of the most prominent algorithms strongly depends on the appropriate setting of these hyperparameters.
Traditional hyperparameter tuning is treated as a bi-level optimization problem as follows. min f() (ww(A), A), s.t. (x)) arg XERP
A)
(1)
where E IRd are the model parameters, X E Eº are the hyperparameters, the outer objective E represents proxy the generalization error w.r.t. the hyperparameters, the inner objective represents traditional learning problems (such as regularized empirical risk minimization problems), and wA) are the optimal model parameters of the inner objective L for the fixed hyperparameters Note that the size of hyperparameters is normally much smaller than the one of model parameters (i.e., p < d). Choosing appropriate values of hyperparameters is extremely computationally challenging due to the nested structure involved in the optimization problem. However, at the same time both researchers and practitioners desire the hyperparameter optimization methods as effective, efficient, scalable, simple and flexible" as possible.
Classic techniques such as grid search (Gu & Ling, 2015) and random search (Bergstra & Bengio, 2012) have very restricted application in modern hyperparameter optimization tasks, because they only can manage a very small number of hyperparameters and cannot guarantee to converge to
'The choice of objective function E depends on the specified tasks. For example, accuracy, AUC or Fl can be used for binary classification problem. Square error loss absolute error loss be used as the objective of E. for regression problems on validation samples.
""effective": good generalization performance. "efficient": running fast. "scalable": scalable in terms of the sizes of hyperparameters and model parameters. "simple": easy to be implemented. "flexible": flexible to various learning algorithms.

---

Under review as a conference paper at ICLR 2021
Table 1: Representative black-box optimization and gradient-based hyperparameter optimization algorithms. ("BB" and "G" are the abbreviations of black-box and gradient respectively, and " denotes that the property holds for small number of hyperparmaters or medium-size training set. "Scalable-H"" and "Scalable-P" denotes scalability terms of hyperparameters and model parameters respectively.)
Properties
Algorithm
Type Effective Efficient
Scalable-H H Simple Flexible Scalable-P
GPBO (Snock et al., 2012)
BOHB (Falkner ct al., 2018)
BB
X
HOAG (Pedregosa, 2016)
G
X
X
X
RMD
(Maclaurin et al., 2015)
G
V
V
X
X
RFHO (Franceschi et 2017; 2018)
/
V
X
HOZOG
BB+G
local/global minima. For modern hyperparameter tuning tasks, black-box optimization (Snoek et al., 2012; Falkner al., 2018) and gradient-bar based algorithms (Maclaurin et al., 2015; Franceschi et al., 2018; 2017) are currently the dominant approaches due to the advantages in terms of effectiveness, efficiency, scalability, simplicity and flexibility which are abbreviated provide a brief review of representative black-box optimization and gradient-basee hyperparameter optimization algorithms 12.1, 1 and detailed comparison of them in terms of the above properties in Table 1.
E2S2F in this paper. We
Table clearly shows that black-box optimization and gradient- gradient-based approaches have totally distinct advantages, ie., black-box optimization approach is simple, flexible and salable in term of model pa- rameters, while gradient-based approach effective, efficient and scalable term hyperparmeters. Each property of E2S2F is an important criterion to successful hyperparameter optimization method. To the best of our knowledge, there is still no algorithm satisfying the five properties simultane- ously. Designing hyperparameter optimization method having the benefits of both approaches is still an open problem.
To address this challenging problem, in this paper, propose new hyperparameter optimization method with ceroth-order parameter optimization an A-based constrained optimization problem, where A is black-box optimization algorithm (such as the deep neural network). Then, we use the average zeroth-order hyper-gradients update hyperparameters. We provide the feasibility analysis of using HOZOG to achieve hyperparameter optimization. Finally, the experimental results of various hyperparameter (the size is from I to 1250) optimization problems demonstrate the benefits of HOZOG terms of E2S2F compared with the state-of the--rr hyperparameter optimization methods.
(HOZOG). Specifically, we first exactly formulate hyper-
2 HYPERPARAMETER OPTIMIZATION BASED ON ZEROTH-ORDER EYPER-GRADIEN
In this section, we first give a brief review black- box optimization and gradient-based algorithms, and then provide our HOZOG algorithm. Finally, provide the feasibility analysis of HOZOG.
2.1 BRIEF REVIEW OF BLACK- -Bo OPTIMIZATION AND SEADIENT-BASED ALGORITHMS
Black-box optimization algorithms: Black-box optimization algorithms view the bilevel optimiza- tion problem a black-box function. Existing black-box optimization methods (Snoek al., 2012; Falkner et al., 2018) mainly employ Bayesian optimization (Brochu et al., 2010) to solve (1). Black-box optimization approach has good simplicity and flexibility. However, lot of references have pointed out that it can only handle hyperparmeters from few to several dozens (Falkner et al., 2018) while the number of hyperparmeters real hyperparameter optimization problems would range from hundreds to thousands. Thus, black-box optimization approach has weak scalability in term the size of hyperparmeters.
Gradient- based algorithms: The existing gradient-based algorithms can be divided into two parts (i.e., inexact gradients and exact gradients). The approach inexact gradients first solves the inner problem approximately, and then estimates the gradient of (1) based on the approximate solution by the approach of implicit differentiation (Pedregosa, 2016). Because the implicit differentiation involves Hessian matrices of sizes of d x d and d x p where p & d, they have poor scalability. The
2

---

Under review as a conference paper at ICLR 2021
approach of exact gradients' treats the inner level problem as a dynamic system, and use chain rule (Rudin et al., 1964) to compute the gradient. Because the chain rule highly depends on specific learning algorithms, this approach has poor flexibility and simplicity. Computing the gradients involves Hessian matrices of sizes of p x and d x p. Thus, the approach of exact gradients has better scalability than the approach of inexact gradients because normally we have p d.
t Enlightenment: As introduced in (Nesterov & Spokoiny, 2017; Gu et al., 2018). zeroth-ordes gradient (also known as finite difference approximation (Cui et al., 2017)) technique is a black-box optimization method which estimates the gradient only by two function evaluations. Thus, zeroth- order gradient technique belongs both to black-box optimization and gradient-basel optimization. We hope that the hyperparameter optimization method bases on zeroth-order hyper-gree gradients* can inherit all benefits as described in Table 1.
2.2 HOZOG ALGORITIM
Principle: Instead of directly computing the hyper-gradient as in (Pedregosa, 2016; Maclaurin et al., 2015; Franceschi et al., 2017; 2018), we use two function evaluations (i.e., the zeroth- hyper-gradient technique (Nesterov & Spokoiny, 2017; Gu et al., 2018)) to estimate the and update hyperparameters with hyper-gradien which derives our HOZOG algorithm.
Before presenting HOZOG algorithm in detail, we first clarify what problem we are solving exactly.
What problem we are solving exactly? As mentioned in (1), the inner level problem in the traditional hyperparameter tuning is finding the model parameters that minimize the inner objective L. (t.e., wxA) E arg min LL (w,)), A)). However, in the real-world hyperparameter tuning problems, we are usually trying to find an approximate minimum solution of T. by an optimization algorithm usually try to find an approximate local solution or a stationary point. Thus, we replace the inner level problem by (AA) A(A) where A is an optimization algorithm which approximately solves the inner objective L. Further, we replace the bi-level optimization problem (1) by the following A-based constrained optimization problem (2).
the inner level problem L in convex. If the inner level problem I. in non-convex,
min ((A) = (Aw()), 8.l. w(A) = A(A)
XeRr
where (A) are the values returned by the optimization algorithm AA.
Hyperparameters:
Hyperparameters can be divided into two types, i.e., problem-based hyperparam-
eters and algorithm-based hyperparameters.
1. Problem- based hyperparameters: The problem- based hyperparameters are the hyperparame- ters involved in learning problems such as the regularization parameter and the architectural hyperparameters deep neural networks.
2. seporithm-based hyperparameters: These are the hyperparameters involved in optimization algorithms such as the learning rate, momentum and dropout rates.
The traditional bi-level optimization problem (1) can only formulate the problem-based hyperpa- rameters. However, our A-based constrained optimization problem (2) can formulate both types of hyperparameters.
To solve the A-bbaed constrained optimization problem (2), we propose HOZOG algorithm in Algorithm 1, where the "for" loop is referred as "meta-iteration". We describe the two key operations of Algorithm (i.e., estimating the function value and average zeroth-order hyper-gradient) in detail as follows.
Algorithm:
Estimating the function value: We treat the optimization algorithm A as a black-box oracle. Given hyperparameters X, the black-box oracle A returns model parameters u<()). Based on the pair of and w()), the function value can be estimated as (A)()),).
Computing the average zeroth-order hyper-gradiens Zeroth-order hyper- graddentt can be computed as v((a) E. (J(A + pw) f())) based on the two function evaluations ʃ(^ + pu) and s(A),
Ithough the inner-problem is usually solved approximately e.g. by taking finite number of steps of gradient descent, we still call this kind methods as exact gradients throughout this paper to avoid using too complex terminology.
We call the gradient w.r.t hyperparameter as hyper- in this paper.
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Hyperparameter optimization method with zeroth-order hyper-gradients (HOZOG)
Input: Learning rate 7, approximate parameter ju, size of directions y and black-hox inner solver A.
Initialize Ag Rp.
2: for = 0, 1, ., T do
3: Generate u = [u],... Uo where u, ~ N (0; 1p).
4: Compute
the average zeroth-order png Ei= (J(A, + pm4) - f()e)) us, where f()e)
hyper-gradient
f(())
P.
is estimated based on the solution
returned by the black-box inner solver
5: Update det1 t d -VVf(A)..
6: end for Output: 'y-
where u ~ (0, I,) a random direction drawn from uniform distribution over unit sphere, and j is an approximate parameter. (A) has large variance due single direction To reduce the variance, we use the average zeroth-orde hyper- hyper-gradient (3) by sampling a set of directions (u; )
f(A)
P Σ (f(A+ pu)) - f()) u,
(3)
Based on the average zeroth-order hyper-gradient (A), we update the hyperparameters as follows.
+ x (A)
(4)
Note that (A) is a biased approximation to the true gradient V (A() Its bias can be reduced by decreasing the value of However, in a practical system, μ could not be too small, because in that case the function difference could be dominated by the system noise (or error) and fails to represent the function differential (Lian et al., 2016).
Parallel acceleration. Because the average seroth-ordes apper-gradient involves q + 1 function evaluations shown in (3), evaluations in parallel to accelerate the computation average zeroth-order hyper-gradients.
GPU multiple cores to compute the function
2.3 FEASIBILITY ANALYSIS
Challenge: In treating the optimization algorithm A(A) black-box oracle that maps w, the most important problem is whether the mapping function A(A) is continuous which is the basis of using the zeroth-order hyper-gradient technique optimize (2).
Continuity: Before discussing the continuity of the A-based constrained optimization problem f (A). we first give the definitions of iterative algorithm and continuous function Definitions and
2 respectively.
Definition (Iterative algorithm). Assume the optimization algorithm A(A) can be formulated as nested function as A(A) = wT and w, [,,(w,1,>) for 1,..., T, where T the number of iterations, wo is an initial solution, and, for every TI,...,T), 4, (R4 x RP) + Rd is mapping function that represents the operation performed by the 1-th step of the optimization algorithm. We call the optimization algorithum A(X) an iterative algorithm.
Definition (Continuous function). For all X E IR, if the limit of f(A + 8) as 8 E R approaches 0 exists and is equal to fA)) we call the function f()) continuous everywhere.
Based Definitions 1 and 2, give Theorem to show that the A-based constrained optimization problem f()) is continuous under mild assumptions. The proof is provided Appendix.
Theorem 1. If the hyperparameters are continuous and the mapping functions (e(w,-1, A) (for every & E {1,...,Th ,TT) are continuous, the mapping function A()) is continuous, and the outer objective E is continuous, we have that the A-based constrained optimization problem f(A) is continuous w.r.t. X.
We provide several popular types of optimization algorithms to show that almost existing iterative algorithms are continuous mapping functions which would make ((A) continious.
1. Gradient descent algorithms: is a gradient descent algorithm (such as SGD (Ghadimi & Lan, 2013), SVRG (Reddi et al., 2016; Allen-Zhu & Hazan, 2016), SAGA (Defazio et al., 2014),
4

---

Under review as a conference paper at ICLR 2021
SPIDER (Fang et al., 2018)), the updating rules can be formulated as f- w 22,, where is a stochastic or deterministic gradient estimated by the current w, and 7 is the learning rate. To accelerate the training of deep neural networks, multiple adaptive variants of SGD (e.g.. Adagrad, RMSProp and Adam (Goodfellow et al., 2016)) have emerged.
2. Proximal gradient descent algorithms: A is a proximal gradient descent algorithm (Zhao et al., 2014; Xiao & Zhang, 2014; Gu & Huo, 2018), the updating rules should be the form of w <- Prox(w 7/w), where Prox is a proximal operator (such as the soft-thresholding operator for Lasso (Tibshirani, 1996)) which is normally continuous (Bredies & Lorenz, 2007; Zou, 2006).
It is easy to verify that the mapping functions A()) corresponding to these iterative algorithms are continuous according to Theorem 1.
For continuous function f()), there exists a Lipschitz constant L (see Definition 3) which upper bounds [f(As)=f(Aa) Vλ1, X2 E RP. Unfortunately, exactly calculating the Lipschitz constant of f() NP-hard problem (Virmaux & Scaman, 2018). We provide an upper bound the Lipschitz constant of (A) in Theorem 2.
Definition (Lipschitz continuous constant). For a continuous function f()), there exists a constant L such that, VA1, X2 E RR, we have - I L| - >21l- The smallest L for which the inequality is true is called the Lipsehitz constant of f()).
Theorem 2. Given the continuous mapping functions De(wi-1. where t E (1.....,T] TH,, A =
(0,(w)-1:)) B, (01(10111)), Given the continuous objective function E(WT, A), AT+1
O
DA
(44+11 l12. LB, = supxeR" wEER" || aE(wT.A) and BT+1 aE(wr.)) Let LA, = supXeR", ||A
Out
DA
Let I..f) denote the Lipschitz constant of the continuous function f()), we can upper bound L(f) by ET LR, LB41. L..
Because the A-based constrained optimization problem f() is continuous, we can use the zeroth-order hyper-gradient technique to optimize f()) (Nesterov & Spokoiny, 2017). Nesterov Spokoiny (2017) provided the convergence guarantee of zeroth-order hyper-gradient method when fA) is Lipschitz continuous as defined in Definition 3.
Conclusion:
3 EXPERIMENTS
We conduct the hyperparameter optimization experiments on three representative learning problems (i.e., lg-regularized logistic regression, deep neural networks (DNN) and data hyper-cleaning), whose sizes of hyperparameters are from 1 to 1250. We also test the parameter sensitivity analysis of HOZOG under different settings of parameters 4: l and 7, which are included in Appendix due to the page limit. All the experiments are conducted on Linux system equipped with four NVIDIA Tesla P40 graphic cards.
Compared algorithms: We compare our HOZOG with the representative hyperparameter optimization approaches such as random search (RS) (Bergstra Bengio, 2012), RFHO with forward (FOR) or reverse (REV) gradients (Franceschi et al., 2017) HOAG (Pedregosa, 2016)', GPBO Snock et al. (2012)& 8 and BOHB (Falkner al., 2018) 9. Most of them are the representative black-box optimization and gradient- based hyperparameter optimization algorithms as presented in Table 1. We implement our HOZOG in Python
Evaluation criteria: We compare different algorithms with three criteria, i.e., || f sub- optimality and test error, where "suboptimality" denotes f()) - f(X9) and f(X²) is the minimum
$ "Alhhough the upper bound is related T, our simulation results show that it does not grow exponentially with T because LA, or LB, not larger than one at most times.
"The code of RFHO is is available at ht /ggthtb.b..../.gg/ wwm coom/Iucfra/REHO.
7 "The code HOAG is available at httpt::
com/ wwt.faaaiaaaaaaaa
"The code of GPBO is available http: / //gi com
haem//ffn///e Bayes anopt miziioio/
'The code of BOHB is available at https: //pp::////// //gi wtw..ccc.//cocc..tccco wwt.cccmm/aa/aaeceeeeeeocoe/ aut.mm hasicommmHHpaaa /HphandSter. Note that BOHB is an improved version of Hyperband (Li ct al., 2017). Thus, we do not compare HOZOG with Hyperhand.
We will release the code of HOZOG and the experiments after the paper is accepted.
5

---

Under review as a conference paper at ICLR 2021
(a) News20
(b) Covtype
(c) Real-sim
(d) News20
(e) Real-sim
(f) Covtype
(g) News20
(h) Real-sim
Covtype
Figure 1: Comparison of different hyperparameter optimization algorithms for /z-regularized logistic
regression sharing the same legend. (a)-(c): Test error. (d)-(f): Suboptimality. (g)-()): [A]]2]
(Larger figures can be found in the supplement material.)
value of f(A) for all À which have been explored, and test error is the average loss the testing set. Note the syyer-gradiend V (A) for all method except for FOR and REV are computed by Eq. (3).
The datasets used in exper- iments are News20, Covtype, Real-sim, CIFAR-10 and Mnist datasets from
Datasets:
Experiment
g 1 Y
News20
0.01
0.05
12-regularized logistic regression
Covtype
0.01
0.03
Real-sim
0.01
0.005
LIBSVM repository, which is available at https://wwwe
2-layer CNN
100
ntu. edu. tw/ oos /dtas/ss////ss/////// Especially, for News20 and Mnist two multi-class datasets, we transform them to binary classification problems by randomly hyperparameters. partitioning the data into two groups.
Deep Neural Networks
VGG-16
20
CIFAR-10
ResNet- 152
10
Data hyper cleaning
500/1250
Mnist
Table 2:
The parameter settings of HOZOG in the ex- periments. (*# HP" is the abbreviation of the number of
The values of parameters 9. I and 7 in HOZOG are given in Table Especially, 9 plays an important role to HOZOG because it determines the accuracy and the running time of estimating the gradients. We empirically observe that S has good balance between two objectives.
Parameters of HOZOG:
3.1 12- 1g-REGULARIZED LOGISTIC REGRESSION
Experimental setup: We consider estimate the regularization parameter in the lz-regularized logistic regression model. We split one data set into three subsets (i.e., the train set Dir. validation Deal and test set D,) with ratio of 2:1:1. We use the logistic loss ((t) log(1 + e e-t) as the loss function. The hyperparameter optimization problem for 12 lz-regularized logistic regression is formulated as follows.
arg min Σ (a,, w())),
s.t. w(A) arg min weRd
Σ (yy w()))) + |w=l| (5)
10[-10,10] iE:Det
The solver used for solving the inner objective is L-BFGS (Liu & Nocedal, 1989) for HOAG and Adam (Kingma Ba, 2014) for the others.
Results and discussions: Figure presents the convergence results of suboptimality, | f(A)ll2 and test error vs. the running time for different methods. Note that we take same initial values of À and for all gradient-based methods, while the black-box methods naturally start from different points. Because HOAG works with tolerances and warm start strategy, HOAG has fast convergence at the early stage but slow convergence the late stage shown in Figures 1g- li. We observe that HOZOG runs faster than other gradient-bart based methods. This is because that FOR and REV need much time to compute hyper-gradients. Figures 1g- provide [ of different methods as functions of running time. We can see that the black-box methods (i.e., BOHB and GPBO) spend much time on exploring because |/ (A)]l2 of these methods didn't strictly go down in the early stage. Overall, all the results show that HOZOG has a faster convergence than other methods.
3.2 DEEP NEURAL NETWORKS
Experimental setup: We validate the advantages of HOZOG optimizing learning rates of DNN which is much more complicated both structure and training compared to ly-regularized logistic regression.
TTeee implementation is available https://gitths.. fabi anp/hoag.

---

Under review as a conference paper at ICLR 2021
EOK3
DOWD
(a) 2-layer CNN
(b) VGG-16
(c) ResNet- 152
(d) 2-layer CNN
(c) VGG-16
Iiee apace
Traete
1000 vile 2310
(f) ResNet- 152
(g) 2-layer CNN
(h) VGG-16
(i ResNet- 152
Figure 2: Comparison of different hyperparameter optimization algorithms for 2-layer CNN, VGG- 16 and ResNet-152 sharing the same legend. (a)-(c): Test error. (d)-(f): Suboptimality. (g)-()): [A)ll2) (Larger figures can be found in the supplement material.)
Specifically, the training of modern DNN is usually an intriguing process, involving multiple heuristic hyperparameter schedules, e.g. learning rate with exponential weight decay. Instead of intuitive settings, we propose to apply epoch-wise learning rates and jointly optimize these hyperparameters. The experiments are conducted on CIFAR-10 10 dataset with 50,000 samples. To demonstrate the scalability of HOZOG, three deep neural networks with various structure are used, including (I) two layers DNN (2-layer CNN) with convolutional, max pooling, and normalizing layers; (2) VGG- 16 (Simonyan & Zisserman, 2014), (3) ResNet- 152 (He et al., 2016). The initialization of inner problem is randomized for different meta-iterations to avoid the potential dependence on the quirks of particular settings. In detail, for all experiments we apply 50 meta-iterations and optimize inner problems using stochastic gradient descent, with batch size 256. On CNN, 100 epochs for inner problem are used, which indicates 100 hyperparameters are involved. On VGG-16. the original model takes 224 224 images as inputs, and we adjust the size of the first fully-connected layer from 7 x convolution to 1 x 1 to fit CIFAR-10 1- inputs. Here 20 epochs for inner used. On ResNet- 152, similar processing is exploited and the inner epoch is 10.
The results are summarized in Figure 2. The experimental results show that the learning rates computed by HOZOG achieve the lowest test error and the fastest descending speed compared to baselines on all tasks. Moreover, the proposed method requires much less time to attain the best hyperparameters, and tends to have smaller variances in gradients. It is noteworthy that, some sfte-off-hh-ar hyperparameter optimization approaches (including HOAG, REV and FOR) are missing in this setting, due to the algorithms of REV and FOR are limited to smooth functions and the implementation of HOAG limited to the hyperparameter optimization problems with small number of hyperparamters. However, these difficulties are avoided by our HOZOG, which also demonstrates the flexibility of HOZOG. Moreover, as a brutal search method, the performance RS is very unstable, which can be identified from the hyper-gradients. For BO and BOHB, the instability also exists, potentially due to the highly complexity of the network structure. Another noteworthy problem with respect BO and BOHB is the computational overhead in sampling, which make the meta-iteration extremely time consuming, compared to other methods.
Results and discussions:
We observe that the difficulty of this problem mainly comes from model complexity, instead of ryper-parameter numbers. For CNN with 100 time and suboptimality. although baselines and ResNet- 152, we notice that though the size of hyperparameters is reduced, it takes baselines longer time to find acceptable results. Instead, HOZOG still shows fast convergence empirically. This observation indicates that HOZOG is potentially more suitable for hyperparameter optimization in large DNN.
HOZOG shows advantages in both also efficiently find reasonable solution. For VGG-16
3.3 DATA HYPER- -EEEECCEANNIG
Experimental setup: We evaluate HOZOG on tuning the hyperparameters data hyper-cleaning task. Compared with the preceding problems, the data cleaning task is more challenging, since has more hyperparameters (hundreds or even thousands).
Assuming that have label noise dataset, with only limited clean data provided. The data hyper- cleaning task is to allocate a hyperparameter weight A; to a certain data point or a group of data points to counteract the influence of noisy samples. We split certain data set into three subsets: D.r
7

---

Under review as a conference paper at ICLR 2021
(a) 500 HP
(b) 1250 HP
(c) 500 HP
(d) 1250 HP
(c) 500 HP
(f) 1250 HP
Figure 3: Comparison of different hyperparameter optimization algorithms for data hyper-cleaning sharing the same legend, where "HP" is the abbreviation of hyperparameters (a)-(b): Suboptimality. (c)-(d); | f(A)le. (c)-(f): Test error. (Larger figures can be found in the supplement material.)
of Nr training samples, Duat of Neat validation samples and test set Dr containing the Ne samples. We set random labels to |0.5 Nerl training examples, and select random subset D from Der.
Similar to Franceschi et al. (2017), we considered plain softmax regression model with parameters W (weights) and b (bias). The error of model (W, b) on an example (z, y) was evaluated by using the cross coss-entropy I(W, b, (ar, y)) both in the training objective function, L, and in the validation one, E. We added in an hyperparameter vector ing phase through sigmoid function, i.e. T(W, b) Ne.
R.V. that weights each group of examples in the train- 1 Egeg Lieg (Ag) b, (ma, Us)),
where & contain Nr, groups random select from Der- Thus, we have the hyperparameter optimization problem as follows.
arg min E(W (A). s.t. (WAA),(AA) = arg min L(W, b) \
(6)
W/b
We instance two subset dataset for the MNIST dataset, with N.- 5000, Nuat 5000, N, 10000,
NA = 1250 and N2 = 1000, Neat = 1000, N, = 4000, N₁ = 500. We use a standard gradient descent method for the inner problem with fixed learning rate 0.05 and 4000 iteration. RS is used as baseline method, and BOHB and REV are used as comparison.
Results and discussions: Figure 3 presents the results of HOZOG, BOHB, REV and RS for data hyper-cleaning. Note that the methods of GPBO, FOR and HOAG are missing here, because the hyperparameter size is beyond the capability of their implementations. The results show that HOZOG can beat RS and BOHB easily, while not perform completely as good as REV in the long run. This is because REV is an exact gradient method whose convergence rate is faster than the one of zeroth-order gradient method (i.e., HOZOG) by a constant whose value is depending on p (Nesterov & Spokoiny, 2017). However, computing the exact gradients in REV is costly. Specifically, REV takes about 40 seconds to finish the computation of one byper-gradient under the setting of 1250 hyperparameters, which is only about 24 seconds for HOZOG. This is the reason why method converges faster than REV in the early stage of training. Importantly, the application scenarios of REV are limited smooth functions, egg., not suitable for the experimental settings of convolutional neural networks and deeper neural networks. However, our HOZOG can be utilized to broader class of functions (i.e., continuous functions).
3.4 DISCUSSION: IMPORTANCE OF HOZOG
The experimental results show that the black-box optimization methods have a weak performance for the high-dimensional hyperparameter optimization problems which is also verified in large number of existing references (Brochu et al., 2010; Snoek et al., 2012), while they have the advantages of simplicity and flexibility. On the other hand, the existing gradient-based methods (Franceschi et al., 2017; 2018) need experienced researchers to provide a customized program against the optimization algorithm and sometime it would fail, while they have the advantages of scalability and efficiency. HOZOG inherits all the benefits from both approaches in that, the gradients are computed in black- box manner, while the hyperparameter search accomplished via gradient descent. Especially, for high-dimensional hyperparameter optimization problems which have no customized RFHO algorithm, HOZOG currently is the only choice for this kind of problems the best of our knowledge.
4 CONCLUSION
Effeetiienesss efficiency, scalability, simplicity and flexibility (i.e., E2S2F) are important evaluation criteria for hyperparameter optimization methods. In this paper, we proposed a new hyperparameter optimization paradigm with zeroth-order hyper-gradients (HOZOG) which is the first method having all these benefits to the best of our knowledge. We proved the feasibility of using HOZOG to achieve hyperparameter optimization under the condition of Lipschitz continuity. The experimental results on three representative hyperparameter (the size is from 1 to 1250) optimization tasks not only verify the result in the feasibility analysis, but also demonstrate the benefits of HOZOG in terms E2S2F, compared with the sfate-of-the-se hyperparameter optimization methods.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pp. 699-707, 2016.
James Bergstra and Yoshua Bengio. Random search for hyper-pprammee optimization. Journal of Machine Learning Research, 13(Feb):281-305 2012. 1,5
Kristian Bredies and Dirk A Lorenz. Iterative oof-tthresholding converges linearly. arXiv preprint arXiv:0709. 1598, 2007.
Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv: 1012.2990, 2010. 2,
Jianbo Cui, Jialin Hong, and Zhihui Liu. Strong convergence rate of finite difference approxi- mations for stochastic cubic schrödinger equations Journal of Differential Equations, 263:
000220366173025333 2017. 3
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1646-1654, 2014. 4
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti- mization at scale. In International Conference on Machine Learning, pp. 1436-1445, 2018. 2.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- mization via stochastic nath-integrated differential estimator. Advances in Neural Information Processing Systems, pp. 689-699 2018. 5
Herbert Federer. Geometric measure theory. Springer, 2014.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1165-1173. JMLR. org, 2017. 2,
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning In International Conference on Machine Learning, pp. 1563-1572, 2018. 2, 3,
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth- methods for nonconvex stochastic programming. SIAM Journal Optimization, (((4):2341-2366 2013.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016. 5
Bin Gu and Zhouyuan Huo. Asynchronous doubly stochastic group regularized learning. In International Conference on Artificial Intelligence and Statistics (AISTATS 2018), 2018. 5
Bin Gu and Charles Ling. A generalized error path algorithm for model selection. In International Conference on Machine Learning, pp. 2549-2558, 2015.
Bin Gu, Zhouyuan Huo, Cheng Deng, and Heng Huang. Faster derivative-free stochastic algorithm for shared memory machines. In International Conference on Machine Learning, pp. 1807-1816, 2018. 3
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.64/2.680 2014.

---

Under review as a conference paper at ICLR 2021
Alex Krizhevsky, lly Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012. 1
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):6765-688 6816, 2017. 5
Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Liu. comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order. In Advances in Neural Information Processing Systems, pp. 3054-3062, 2016.
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programminng. 45(1-3):503 528, 1989. 6
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference on Machine Learning, pp. 21--222 2015. 2, 3
Yurii Nesterov and Vladimir Spokoiny. Random gradient- minimization of convex functions.
Foundations of Computational Mathematics, 17(2):227-566, 2017. 3, 5,
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pp. 737-746, 2016. 2, 3,5
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp- 314-323, 2016. 4
Walter Rudin. Principles of mathematical analysis. 1976. 12
Walter Rudin al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1964.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409. 1406.1556, 2014. 7
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In Advances in neural information processing systems, pp. 2951-2959, 2012.
2, 5, 8
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267- -288, 1996.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems, pp. 3835-3844, 2018.
Lin Xiao and Tong Zhang. proximal stochastic gradient method with progressive variance reduction.
SIAM Journal on Optimization, 24(4):2057-20755 2014. 5
Tuo Zhao, Mo Yu, Yiming Wang, Raman Arora, and Han Liu. Accelerated mini-batch randomized block coordinate descent method. In Advances in neural information processing systems, pp. 3329-3337, 2014. 5
Hui Zou. The adaptive lasso and its oracle properties. Journal of the American statistical association, 101(476); 1118-149, 2006.
10


Reviews:
[{"review_id": "zalpVd49fBl", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "EDIT: **post rebuttal (could not add a comment readable by authors). Thank you for your rebuttal, I have read it and the other reviews. I agree with the other reviewers that some more baselines for high-dimensional benchmarks are required, and was not convinced by your rebuttal to those requests. I also think the aspect of non-convexity and local optima touched by Reviewer 4 warrants some discussion in the paper. I maintain my score of 4. **\n\nThe paper presents a novel method for hyperparameter optimization based on zeroth order gradient estimation. The zeroth order estimation of the gradient permits the application of the method to complex architectures, provided that the hyperparameters are continuous and the objective function is Lipschitz continuous. The method appears competitive with both gradient-based HPO methods and gradient free methods on a suite of experiments with a number of hyperparameters ranging from 1 to 1250.\n\nStrong points:\n- The method is simple and is competitive with previous gradient-free HPO methods for continuous hyperparameters.\n- The method appears better or competitive with previous gradient-based HPO work.\n- On the technical side the paper appears solid. I see no methodological flaws in the method.\n\nWeak points:\n- There is no comparison with gradient based methods for the deep network experiments (arguably the most important benchmark). The authors state that the methods of Franceschi et al. could not be compared because they require smooth function, but checking their paper, they only mention a smooth optimization operator, and this condition appears to be met by a gradient descent optimization operator. Perhaps I am missing something here, but further justification on this point would be appreciated.\n- The description of the experiments is a bit lacking in certain regards. This diminishes the reproducibility of the work. For instance, the computational budget is not specified for the experiments. How long were benchmarks run for? Was the budget specified in wallclock time? How many function evaluations did each method complete? Did you repeat each experiment and average them? \n- The paper needs a lot of work on a clarity and quality standpoint. I spotted a lot of grammar mistakes and some sentences were hard to interpret.\n\nRecommendation:\n\nGiven the current state of the paper, I would recommend rejection. The paper needs some serious copy-editing before it is up to the standards of a first tier conference such as ICLR. I should say that I like the method proposed in the paper, it would make a nice addition to the literature on HPO -- I just think it needs more polish. \n\nApart from paper quality, more work/details on the following points/questions would help me increase my score for this paper:\n\n- The results are only presented using wallclock time. A general idea of the  \"number of function evaluations\" achieved by each method would also be informative, a graphic comparing the performance with regards to function evaluations could be added in the appendix. This is an important point because some models take a long time to run, and whatever computation is done between function evaluations becomes meaningless in comparison.\n- What is the implication of removing the approximate gradient computation of HOAG with the zeroth order gradient proposed in this paper? Is it still HOAG or does it become a new method?\n- Figure 2. is a bit confusing to me. Why is the x-axis \"Inner epoch\" for the suboptimality figures? Is this presenting the final optimization run with the best hyperparameters found?\n\nExtra comments:\n\nTable 1 feels rather arbitrary, what is the threshold to say that a method is \"effective\" or not? Simple or not? Is BOHB really that simple compared to HOAG? Complexity / optimization guarantees in terms of p and d might provide a clearer picture here (those are generally available for GP-BO and most likely for gradient based methods?) -- just an idea.\n\nSection 2.1: Claim that the number of hyperparameters in real problems would range from hundreds to thousands. It seems to me that problems with thousands of hyperparameters are very academic and never encountered in typical real world problems. Bring forward examples or please reformulate.\n\nSection 2.1: I have mixed feelings about the last paragraph of this section titled Enlightenment with a cross symbol. Is this a religious reference? I would argue this has no place in a scientific paper. \n\nProofreading is required, examples of errors:\n\nPage 2. paragraph 2: salable -> scalable\nPage 3. (such as the deep neural network) -> (such as A deep neural network)\n\nMultiple times in the text: hyperparmeters -> hyperparAmeters", "extra_scores": {}, "extra_text": {}}, {"review_id": "zDInk0BO4zu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes to apply zeroth-order optimization to hyperparameter tuning. Zeroth-order optimization techniques use function evaluation only to approximate the gradients, thus they are applicable to black-box functions for which the gradient is difficult to compute. For hyperparameter tuning this is the case in general. Existing hypergradient-based methods are not applicable to generic tuning tasks, and have scalability issue. Existing generic methods such as Bayesian optimization have weak scalability in number of hyperparameters. I agree with these observations and the goal of having a flexible, efficient, effective, simple and scalable solution.\n\nWhile the idea of using zeroth-order optimization for HPO makes sense, the paper has not reached a sufficient depth in exploring this idea. The paper proposes to use (Nesterov & Spokoiny 2017) without modification. There are several issues: (1) The paper concludes in page 5 that \"Because the A-based constrained optimization problem f($\\lambda$) is continuous, we\ncan use the zeroth-order hyper-gradient technique to optimize f($\\lambda$) (Nesterov & Spokoiny, 2017).\nNesterov & Spokoiny (2017) provided the convergence guarantee of zeroth-order hyper-gradient\nmethod when f($\\lambda$) is Lipschitz continuous as defined in Definition 3.\" With continuity only, the algorithm can converge to local stationary points. Straightforward application of the algorithm could violate the 'effectiveness' and 'efficiency' goal. The situation is worsened in the high-dim case when the variance of the gradient approximation is large. The experiment in Sec 3.3 supports this concern, where HOZOG underperforms REV in the long run. (2) The algorithm still has several hyperparameters to tune, including q, $\\lambda$ and $\\mu$. From the experiments reported in the paper, each task uses different values of q, $\\lambda$ and $\\mu$. That raises the question about the practicability, especially, if one needs to tune these hyperparameters, whether it can still be efficient, scalable and simple. The paper has not discussed how to tune them for a given task. The procedure of tuning is required to be discussed because 'flexibility' is indeed a goal of this paper. (3) The same question can be asked about how the initial point of hyperparameters is chosen, and the paper does not discuss that. \n\nIn addition to these issues, the paper makes a strong claim \"for\nhigh-dimensional hyperparameter optimization problems which have no customized RFHO algorithm,\nHOZOG currently is the only choice for this kind of problems to the best of our knowledge.\" in the end of Sec 3.4. For example, there are other methods designed for high-dimensional problems:\n\nDavid Eriksson et al., Scalable Global Optimization via Local Bayesian Optimization, NeurIPS'19.\n\nN. Hansen. The CMA evolution strategy: A comparing review. In Towards a New Evolutionary Computation, pages 75–102. Springer, 2006.\n\nM. J. Powell. A view of algorithms for optimization without derivatives. Mathematics Today-Bulletin of the Institute of Mathematics and its Applications, 43(5):170–174, 2007.\n\nSince the paper emphasizes the importance of HOZOG in the high-dim scenario, some of these stronger baselines need to used. \n\nA final comment is that the phrase 'automated learning algorithm' in the title is not very informative, especially as the selection of hyperparameters of HOZOG is not automated.", "extra_scores": {}, "extra_text": {}}, {"review_id": "bYB3_ekcUm-", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Paper summary\nThis paper develops a novel approach to hyperparameter optimization that combines the respective advantages of black-box and gradient-based optimization methods.\nThe proposed method (called HOZOG) is based on zeroth-order hyper-gradients, and is empirically demonstrated on several benchmark tasks to compare favourably against state-of-the-art hyperparameter optimisation approaches in terms of simplicity, scalability, flexibility, effectiveness and efficiency.\n\n### Pros\n- overall, the paper is well and clearly written and thus easy to follow\n- the manuscript addresses an important open challenge that is relevant for many practical application domains, namely hyperparameter optimization \n- to tackle this challenge, the paper proposes an approach that is novel by combining previous ideas in a new, interesting and fairly principled way\n- the empirical evaluation is comprehensive and convincingly demonstrates the efficacy of the proposed approach as compared to previous methods for hyperparameter optimization\n\n### Cons\n- the proposed approach seems to be fundamentally based on the assumption that the hyperparameters (and thus the induced function) are continuous; the experiments thus also seem to only involve continuous hyperparameters; this appears rather restrictive, given that many practical hyperparameter optimization problems involve important discrete variables (e.g. architectural parameters of neural networks such as the number of layers/units, or categorical parameters such as the choice of optimiser); it would be interesting to know if it would be feasible to straightforwardly extend the proposed approach to also consider such discrete variables; if not, then this seems to be a severe limitation of the method presented; note that there are several black-box/Bayesian optimization approaches (including BOHB) that can handle discrete variables, e.g. [1,2,3]\n- the paper does not provide any source code, and I am not sure if I would be able to implement the method from scratch and fully reproduce the reported results with the details mentioned in the paper alone; that being said, the authors promise to make the code available upon paper acceptance\n- in the first sentence in the introduction, you claim that \"Modern machine learning algorithms usually involve tuning multiple hyperparameters whose size could be from one to thousands.\"; you proceed to mention two examples, SVMs and DNNs, with only a hand full of hyperparameters; it is thus not clear in which scenario one would have _thousands_ of hyperparameters\n- in Sec. 2.1, you claim that \"a lot of references have pointed out that [black-box optimization] can only handle hyperparameters from a few to several dozens\"; however, you only cite one paper for this claim, and it would be beneficial to cite more of the \"lot of references\"; in Sec. 3.4, you again claim that \"black-box optimization methods have a weak performance for the high-dimensional hyperparameter optimization problems which is also verified in a large number of existing references\", proceeding to cite only two papers (which I wouldn't consider \"a large number of existing references\")\n\n[1] Oh et al., 2019, \"Combinatorial bayesian optimization using graph representations\"\n[2] Baptista et al., 2018, \"Bayesian Optimization of Combinatorial Structures\"\n[3] Daxberger et al., 2019, \"Mixed-Variable Bayesian Optimization\"\n\n### Review summary\nIn summary, I believe this is an interesting, enjoyable-to-read paper that tackles an important problem by proposing a promising and effective new technique. This paper will likely be of great interest to some members of the ICLR community and might become an impactful contribution for machine learning researchers and practitioners alike. That being said, I see some issues with the generality of the method as well as the presentation of the paper. As a result, I overall recommend acceptance of this manuscript, although not too enthusiastically.\n\n### Post-rebuttal\nI thank the authors for their response, addressing some of the issues/questions I had raised.\nAfter carefully reading the other reviews (and corresponding author responses), I agree with the valid criticisms raised (some of which I had overlooked initially), which unfortunately further dampened my enthusiasm for this work.\nAs a result, I am slightly lowering my score.\nHowever, I very much appreciate the author's efforts in this very promising work, and hope that they will revise their manuscript to take into account the feedback raised in the reviews.\n\n### Minor issues\n- Fig. 1: the ordering of the compared methods differs between the reported datasets\n- Experiments: the name of the MNIST dataset is typically capitalised\n- there are minor grammatical errors throughout the paper; I recommend that the author thoroughly proof-read the manuscript (or have it proof-read) for language issues \n- the plots are barely readable without zooming in; I strongly recommend the authors to increase the font sizes to improve their readability and clarity", "extra_scores": {}, "extra_text": {}}, {"review_id": "W31NCGvMldd", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "EDIT: **post rebuttal. I'd like to thank the authors for their response. As scalability to high-dimensional hyperparameter spaces is presented as a key advantage of the method, direct comparisons to high-dimensional BO techniques would be needed. The fact that using trust regions could benefit HOZOG, or that HOZOG is a better strategy compared to TurBO and REMBO, should be demonstrated empirically. I am keeping my score to 4 as the current positioning of the paper would require direct comparisons with these baselines. **\n\n\nThe paper introduces HOZOG, a new HPO method combining the benefits of black-box and gradient-based optimization. This is achieved by means of a finite difference approximation that computes the gradients in a black-box fashion. By doing so, the method achieves both scalability to a large number of model parameters and hyperparameters, the latter being a bottleneck in standard BO methods. A feasibility analysis and experiments against baselines show the benefits of the proposed approach.\n\nPositive\n\n1. **Significance.** This is the first approach trying to take a black-box approach to tackle gradient-based optimization, inheriting the benefits of the two worlds.  I expect this can lead to follow-up work in this direction.\n2. **Clarity.** The paper is generally well articulated and easy to follow. I particularly appreciated the authors clearly comparing black-box and gradient based methods in Table 1 by listing desiderata. \n3. **Feasibility analysis.** The work contributes a rigorous feasibility analysis studying the use of the proposed approach in HPO.\n\nNegative\n\n1. **Missing baselines.** If scalability to high-dimensional hyperparameter spaces is a key selling point of the method, experiments should have focused on comparing against BO methods that are designd to scale to large dimensions. For instance, the authors claim \"a lot of references have pointed out that [BO] can only handle hyperparameters from a few to several dozens\". It would be helpful if the authors elaborated on this point. Is it due to the poor scalability of the Gaussian process model in high dimensions? In that case, non-GP, scalable models have been proposed (e.g., SMAC) or adaptations directly targeting high-dimensional BO problems (e.g., TurBO). Code for these methods is also publicly available but these baselines are missing from the experiments. These are specific references:\n\n(TurBO) Eriksson et al., Scalable Global Optimization via Local Bayesian Optimization. In NeurIPS 2019; \n\n (REMBO) Wang et al., Bayesian Optimization in High Dimensions via Random Embeddings, In IJCAI '13 + follow-ups, including Letham et al. 2020, \"Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization\" ;\n\n(SMAC) Hutter et al., 2011. Sequential Model-Based Optimization for General Algorithm Configuration.  In Proceedings of the conference on Learning and Intelligent Optimization, 2011.\n\n2. **Reproducibility.** No curves in the results include error bars. Are experiments only based on a single run? If not, clearly defined error bars should be reported. If yes, this is not enough to draw meaningful conclusions considering that the BO algortihms are highly stochastic with many sources of variability (e.g., how they are warm-started, often done through a random initial design).\n\n3. **Structure.** The paper is visually rather crammed and the plots are too small to be readable. The authors seem to be aware of this as they provide larger versions of the figures in the appendix. The main paper should be self-contained though and this is not an acceptable way to get around the 8-page limit.\n\nWhile the paper has its merits, I believe the current version falls below the acceptance bar due to the lack of competing high-dimensional BO baselines paired with reproducibility concerns (i.e., experiments have no error bars). I believe this is promising work with valuable theoretical contributions, but the experimental evaluation is currently not sufficient to justify the proposed approach. In particular, relevant baselines for high-dimensional BO should be both discussed and compared against, and all results should be based on multiple repetitions and report confidence intervals.\n\nMinor:\n\n1. Typos at Page 2: \"salable\"  ---> scalable; \"hyperparmaters\" --> hyperparameters\n2. Related to the \"structure\" point above, there is no space between \"results and discussion\" and the rest of the text in page 8. This is also done in several places, including captions. I'd suggest making the content more crisp instead.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has been actively discussed in the light of the authors’ response.
Following a strong consensus across the reviewers, the paper is recommended for rejection.
Even though the paper was, overall, found quite clear, theoretically sound and tackling a relevant problem for the ICLR community, they listed several concerns that remained unclarified after the rebuttal, e.g.,

* Important baselines missing (e.g., high-dimensional BO baselines), a concern unanimously shared across the reviewers. As an example, the fact that using trust regions could benefit HOZOG should be demonstrated empirically. The same goes for the fact that HOZOG is a better strategy compared to TurBO. Such a statement warrants an empirical validation
* Further discussion about the non-convexity and local-optima concerns (raised by reviewer 4)
* Limitation to continuous hyperparameters.

This list, together with the detailed comments of the reviewers, highlight opportunities to improve the manuscript for a future resubmission.
Decision: Reject