Bayesian Learning to Optimize: Quantifying the Optimizer Uncertainty
Authors: Yue Cao
Tianlong Chen
Zhangyang Wang
Yang Shen
Venue:  (2021)
Keywords: Optimizer Uncertainty
Optimization
Uncertainty Quantification

Abstract: Optimizing an objective function with uncertainty awareness is well-known to improve the accuracy and confidence of optimization solutions. Meanwhile, another relevant but very different question remains yet open: how to model and quantify the uncertainty of an optimization algorithm itself? To close such a gap, the prerequisite is to consider the optimizers as sampled from a distribution, rather than a few pre-defined and fixed update rules.  We first take the novel angle to consider the algorithmic space of optimizers, each being parameterized by a neural network. We then propose a Boltzmann-shaped posterior over this optimizer space, and approximate the posterior locally as Gaussian distributions through variational inference.  Our novel model, Bayesian learning to optimize (BL2O) is the first study to recognize and quantify the uncertainty of the optimization algorithm. Our experiments on optimizing test functions, energy functions in protein-protein interactions and loss functions in image classification and data privacy attack demonstrate that, compared to state-of-the-art methods, BL2O improves optimization and  uncertainty quantification (UQ) in aforementioned problems as well as calibration and out-of-domain detection in image classification.

Under review as a conference paper at ICLR 2021
BAYESIAN LEARNING TO OPTIMIZE:
QUANTIFYING THE OPTIMIZER UNCERTAINTY
Anonymous authors Paper under double-blind review
ABSTRACT
Optimizing an objective function with uncertainty awareness well-known to im- prove the accuracy and confidence of optimization solutions. Mcanwhile, another relevant but very different question remains yet open: how to model and quan- tify the uncertainty of an optimization algorithm itself? To close such gap, the prerequisite is to consider the optimizers as sampled from a distribution, rather than few pre-defined and fixed update rules. We first take the novel angle consider the algorithmic space of optimizers, each being parameterized by neu- ral network. We then propose a Boltzmann-shaped posterior over this optimizer space, and approximate the posterior locally as Gaussian distributions through variational inference. Our novel model, Bayesian learning to optimize (BL20) the first study to recognize and quantify the uncertainty of the optimization algo- rithm. Our experiments on optimizing test functions, energy functions protein- protein interactions and loss functions in image classification and data privacy attack demonstrate that, compared to state-of-the-arr methods, BL20 improves optimization and uncertainty quantification (UQ) in aforementioned problems well as calibration and out- -f--mann detection in image classification.
INTRODUCTION
Computational models of many real-world applications involve optimizing non-convex objective functions. As the non-convex optimization problem is NP-hard, no optimization algorithm (or opti- mizer) could guarantee the global optima in general, and instead, their solutions' usefulness (some- times based on their proximity to the optima), when the optima are unknown, can be very uncertain. Being able to quantify such uncertainty is important to not only assessing the solution uncertainty after optimization but also enhancing the search efficiency during optimization. For instance, re- liable and trustworthy machine learning models demand uncertainty awareness and quantification during training (optimizing) such models, whereas in reality deep neural networks without proper modeling of uncertainty suffer from overconfidence and miscalibration (Guo et al., 2017). In another application example of protein docking, although there exists epistemic uncertainty of the objective function and the alcatoric uncertainty of the protein structure data (Cao Shen 2020). state-of- the-art methods only predict several single solutions (Porter al., 2019) without any associated uncertainty, which makes those predictions hard to be interpreted by the end users.
Various optimization methods have been proposed in response the need of uncertainty aware- ness. Stochastic optimization methods like random search (Zhigljavsky (0022). simulated annealing (Kirkpatrick al. 1983). genetic algorithms (Goldenberg) 1989) and particle swarm optimization Kennedy& & Eberhart 1995) injected the randomness into the algorithms in order to reduce uncer- tainties. However, these methods do not provide the uncertainty quantification (UQ) of solutions. Recently, there have been growing interests in applying inference-based methods to optimization problems (Brochu et al. 2010 Shapiro (2000, [Pelikan et af. 1999p. Generally, they transfer the un- certainties within the data and model into the final solution by modelling the posterior distribution over the global optima. For instance, Bijl et al. (2016) uses sequential Monte Carlo to approximate the distribution over the optima with Thompson sampling the search strategy. Hernández-Lobaan et al. (2014) uses kernel approximation for modelling the posterior over the optimum under Gaus- sian process. Ortega al. (2012); Cao & Shen 2020) directly model the posterior over the optimum as a Boltzmann distribution. They not only surpass the previous methods in accuracy and efficiency, but also provide aasy-to-interpret uncertainty quantification.

---

Under review as a conference paper at ICLR 2021
Despite progress in optimization with uncertainty-awareen Existing methods consider uncertainty either within the data or the model (including objective func- tions) (Kendall & Gal 2017| Ortega et al. 2012, Cao & Shen 2020). However, no attention was ever paid to the uncertainty arising from the optimizer that is directly responsible for deriving the end solutions with given data and models. The optimizer is usually pre-defined and fixed in the optimization algorithm space. For instance, there are several popular update rules in Bayesian opti- mization, such as expected improvement Vazquez & et al. (200)), that are chosen and fixed for the entire process. For Bayesian neural networks training, the update rule is usually chosen off off-the-shelf,, such as Adam, SGD, or RMSDrop. The uncertainty in the optimizer is intrinsically defined over the optimizer space and important to the optimization and UQ solutions. However, such uncertainty is unwittingly ignored when the optimizer is treated as a fixed sample in the space.
significant open questions remain.
or upper confidence bound Srinivas
To fill the aforementioned gap, the core intellectual value of this work is to recognize and quantify new form of uncertainty, that lies in the optimization algorithm (optimizer), besides the classical data- or model- based uncertainties (also known as epistemic and aleatoric uncertainties). The un- derlying innovation is to treat optimizer than one of a few hand-crafted update rules. The key enabling technique is to consider the algorith- mic space being parameterized by neural network. We then leverage Boitzmann-shaped posterior over the optimizers, and approximate the posterior locally as Gaussian distributions through varia- tional inference. Our approach, Bayesian learning to optimize (BL20), for the first time addresses the modeling of the tllmizerr-ased uncertainty. Extensive experiments on optimizing test func- tions, energy functions in bioinformatics application, and loss functions in the image classification and data privacy attack demonstrate that compared to the start-of-art methods, BL20 substantially improves the performance of optimization and uncertainty quantification, as well as calibration and out-of-domain detection in classification.
random sample from the algorithmic space, rather
In the following sections, we first review related methods in details and reveal the remaining gap. We then formally define the problem of optimization with uncertainty quantification and point out the optimizer as a source of uncertainty. After formally defining the optimizer space, the optimal optimizer random vector in the space, and the optimizer uncertainty, propose our novel model, BL20. And lastly, we compare our BL20 with both Bayesian and non- non-Bayesian competing methods on extensive test functions and real-world applications.
RELATED WORK
Many works WWang& & Jegelka 2017: Hennig & Schuler 2012) studied optimization with uncer- tainty quantification under the framework of Bayesian optimization (Shahriari et al.] 2016:] Brochu eet al. 2010). In these studies, multiple objectives are sampled from the posterior over the objec- tives (P), where D is the observed data. Each sampled objective is optimized for obtaining samples of the global optima: w" so that the empirical distribution over "=" can be built. Approx- imation is much needed since those approaches need optimization for every sample. For instance, Henrández-Lobato al. (0014) uses kernel approximation to approximate the posterior distirbution.
Another line of work uses various sampling schemes for estimating the density of posterior distribu- tions. For instance. Bijl et al. (2016) uses sequential Monte Carlo sampling. De Bonet et al. (1977) designs a randomized optimization algorithm that directly samples global optima. These methods are much more efficient, but their performance heavily depends on the objective landscapes. More- over, a few studies (Ahmed et al., 2016 Lizotte, 2008 Osborne et al. 2009 Wu et al., (207)) in Bayesian optimization utilize first-order information to boost the performance of optimization. For instance, OSborne et al. (2009) uses gradient information to improve the covariance matrix in Gaus- sian process. Wu et al, (2017) embeds the derivative knowledge into the acquisition function which is optimized in every iteration.
Finally, there are approaches (Ortega et al. 2012 Cao & Shen 2020) that directly model the shape of posterior as the Boltzmann distributions: p( w DD) & exp( -af( (w")), where is the sched- uled temperature constant. They automatically adjust a during the search in order to balance the
exploration-exploitaioon tradeoff. They beat previous work in terms of both efficiency and accuracy.
However, as revealed earlier in the Introduction, none of the methods above consider the uncertainty within the optimizer.
2

---

Under review as a conference paper at ICLR 2021
3 METHODS
Notation. We use a bold-faced uppercase letter to denote a matrix (e.g. W), bold-faced lowercase letter to denote a vector (e.g. w), and a normal lowercase letter to denote a scalar (e.g. w).
3.1 PROBLEM STATEMENT
The goal of optimization is to find the global optimum for an objective function f(w) w.r.t. w:
w = arg min f(w) 10
(1)
w" is assumed unknown and treated as a random vector in this study. Once a optimizer obtains w. its estimate of w², it important assess the quality and the uncertainty of the solution. Considering that many real-world objective functions are nonconvex and noisy in wù solution quality often measured by ||ıè w"'l. Il. the proximity to the global optimum rather than that the optimal function value. Examples include energy functions as the objective and RMSDs as the proximity measure in protein docking (Lensink al. 2007). Therefore, the goal of uncertainty quantification (UQ) here
is the following:
P( w" < r. D)
where T. is the upper bound of ||0 w0ll at a confidence level, and D denotes samples during optimization. Such UQ results additionally provide confidence the solution and improve model reliability for end users.
To calculate the probability defined in Eq 2 and perform UQ direct albeit challenging way is to model the posterior over w= (p(w"(() (D)) and then sample from the posterior. When the optimizer regarded fixed in existing literature, the posterior actually p(w*|D, g). A central contribution of ours is to further consider the optimizer source of uncertainty, model it as random vector in an optimizer space, and perform posterior estimation of p(w") (w=w(2 (D).
3.2 OPTIMIZER UNCERTAINTY: A FRAMEWORK
An optimizer directly responsible for optimization and thus naturally a source of solution uncer- tainty. To address this often-neglected uncertainty source, first define the space of optimizers and then model an optimizer as a point in this space. Considering that many widely-use optimizers are iterative and using first-order derivatives, we restrict the optimizer space follows:
Definition 3.1 ((First-order Iterative) Optimizer Space) We define first-order. iterative algo- rithmic space G. where each point E G is an iterative optimizer, that has the following mapping: ow where V [(w) and dun' the gradient and the update vector at Tth
g((VS (ww)), and lth tteration, respectively.
Here we use g(.) to denote a pre-defined update rule and the resulting optimizer. For instance, in gradient descent, g( V (ww ))==)) - where is the step size. Now that the optimizer space defined, we next define the (unknown) optimal optimizer and its uncertainty.
Definition 3.2 (Optimal Optimizer) We define the optimal optimizer g" E G as the optimizer that can obtain the lowest function value with a fixed budget T:
T
ga arg min gEG
((wg))
(3)
where w' = -w + g(V f is the parameter value at tth iteration updated through the optimizer g.
In practice the optimal optimizer g" is unknown treat g" random vector and formally define the optimizer uncertainty as follows:
Definition 3.3 (Optimizer Uncertainty) Let G be the algorithmic space, where each point g E g is an optimizer. We assume there is prior distribution over the optimal optimizer g" as p(g"). We also assume likelihood distribution as p(D g+). where D are the observed data (sample trajectory) given g². Then we define the optimizer uncertainty through p(g"(D) o p( ('(g)))))
3

---

Under review as a conference paper at ICLR 2021
To inject the optimizer uncertainty into p(w"|D) it straightforward to have the following integra- tion for posterior estimation:
p(w0 (D) / (D)(()))(("110 ydg
3.3 PARAMETERIZING THE OPTIMIZER SPACE
The optimizer uncertainty p (D) as defined in Def. 3.3 can be intractable when there is no proper parameterization of the optimizer space G. Therefore, we next introduce possible ways of parame- terizing G as defined in Def. 3.1
Parameterization through Hy Hyperparameterss of Specific Optimizers. A simple way to param- eterize the optimizer space for classical optimizers (c.g. Gradient Descent, Adam) is based on their hyperparameters: G = H. where HH is the hyperparameter space. For instance, for gradient descent, we have H = (a)), where a is the learning rate. For Adam, we have H = (a, ,1, B2), where 81 and 32 the coefficients used for computing running averages of gradient and its square.
However, such parameterization has significant drawbacks. The resulting algorithmic space G is very limited and heavily depends the specific optimizer. The & (a 1D space) parameterized by the hyperparameters of gradient descent is different from that (a 3D space) parameterized by the hyperparameters of Adam. In fact, each is rather restricted region flexibility (uncertainty) that lies in an iterative optimizer's ' update rule is not explored at all in this parameterization. These drawbacks are empirically demonstrated in Sec.
the actual G. The intrinsic
Parameterization through Neural Networks. In order to reasonably and accurately model the intrinsic uncertainty within the update rule, we need to find much more flexible way for modelling We thus consider to parameterize the optimizer space as a neural network: G = O, where each are the parameters the neural network. Overcoming drawbacks the optimizer space H by hyperparameters, θ by neural network parameters generalizes update rules through neural networks that can represent a wide variety of functions. We note that this also the space meta-optimizers that learn to optimize (L20) iterative update rules from data on given task (Andrychowicz et al.) 2016 Chen et al.) 2017 Lv et al. 2017; Cao et al.) 2019a). However, there has been no notion of uncertainty let alone the task of UQ for the learned optimizer in these L20 methods, which is to be addressed in our Bayesian L.20 (BI20)).
3.4 MODELING AN OPTIMIZER AS A RANDOM VECTOR
Now that we have the optimizer space & properly defined and parameterized, we proceed to model an optimizer g random vector in the space.
Boltzmann-shapel Posterior. Since we have G = θ, we can rewrite each 9 9 as go with
0 θ and the optimal optimizer g" as ge.. Therefore, p(g" (D) becomes p(0" (D). We consider a Gaussian prior over the parameters of the neural network p(0') x constant controlling the variance. We use the chain rule to decompose the likelihood function p(D(0*) at a fixed budge? T:
[ where
T
T
p(D II I(f(wwb)) w/- 0", 00, (f(w6)))) w6- H-=h) = II p(f((b)), lwg-, 0", (f(ww))) w6- )t=1)
(5)
The second equality is due to that w¹. is fixed given 0" and past data points. For the single sample likelihood, we apply the results from Ortega et al. (2012): Cao & Shen (2020) and obtain
p(f ), w 0" ([(w))) ), w
}==)) x exp(- -f(w)))
(6)
We multiply the likelihood functions of all samples together and obtain the Boltzmann-shapp like- lihood function as p(D)@* 0*) exp(- - f(w)-) )). We finally multiply the conjugate prior the likelihood and obtain the Boltzmann- shaped posterior as:
T
PD) x exp(-
Σ
f(wp-) )) exp(->llo01 = exp(-F(0")
(7)
t=1
4

---

Under review as a conference paper at ICLR 2021
where F(0*) Ei=1 fw/)- 11 which actually contains the objective in Eg plus L2
regularization constant.
Local Approximation and Bayesian Loss. However, the above posterior distribution involves an integral in the normalization constant which is computationally intractable. Moreover, the chitecture of F(O") is so complicated that it is impossible to directly sample from the posterior distribution. In order overcome the aforementioned challenges, would like to learn a distribu- tion function q(0 ( ()) that has the analytic form and is easy to be sampled, where & is the parameter vector in ()) to approximate the real posterior (D)
Furthermore, due to the high dimensions of 0 and the complicated landscape of the posterior, impossible to approximate p(0 (D) at every position the 0* space. We then consider to approximate it locally around 0% an optimum of interest for F(0").
We denote the local region as O", neighborhood around 0% and re-normalization constant fo-ce- p (D)dd"""" Then the local posterior will be conditioned (re-scaled) version of p(0* p' (D) p(0*)D)/C l* 0º. In order to make q00 (Φ) = (D() we calculate the KL-divereence between these two:
/
8(0 Φ) log (0))))
p'O0' d0' / ((0)))) log (0) d0
gec
cr
p(0'ID)/C
q (6)
800 ()) log
d0
+ c
g ()) log dC))
exp(-
g
(8)
where Z = (ep((=((*))dd )do* is the normalization constant. The second term in the above equa- tion equals to log( (C),, a constant w.r.t. Φ, thus could be ignored during optimization.
We then propose our Bayesian loss as:
[ Jo (00)))) (b) log (0))))) + Jer <(0' F(")))
Fb( =
- --((1(0')0) 10
where the first term of FB measures the negative entropy of our approximated posterior, and the second term is the expectation the loss function over posterior.
Gaussian Posterior. For local approximation, we consider & = (HL, Σ) and q(0 (6) N(u, Σ),
where is the mean vector and Σ is the covariance matrix of normal distribution. For simplic- ity, we consider to be a diagonal matrix: Σ = diag(o?, oz. 03. o...... The second term in Eq O involves the integral over F(O"), which is intractable. Therefore, through ((0)))) to replace the integral there. However, the direct sampling of the posterior pa- inaccessible get the gradient w.r.t. μ and
Monte Carlo sampling
rameters makes difficult for the optimization
Σ. Moreover, the standard deviation T1, 02, must be non non-negative, making the optimization constrained.
To overcome those two challenges, we use the trick introduced in (Blundell et al.) 2015) to shift sampling from (0)) to sampling from a standard normal distribution A 7). And we reparam- eterize standard deviation to P: a; = log(1 exp(p::). Then for any sampled from A ((,, T), we could calculate 0* 0 u log + exp(p)) c, where O means element- wise product and (p1, (2..).......
3.5 BAYESIAN AVERAGING
We recall our goal to build the posterior over the global optimum: pDw"(D) through Eq consider using Monte Carlo sampling to approximate the integral as:
We
p(w" (D) = p(a())))p((m> (D,g)d
J (00')))(w" (.) D)d00
Σ p(w" 190; (+), D)
(10)
where 0 is sampled from g0 Φ). Since (0) follows a multivariate Gaussian distribution where individual dimensions are independent of each other, estimate the summation above in
5

---

Under review as a conference paper at ICLR 2021
each dimension using independent MC samplings. In practice, N being 10, 000, 100, 000, and 500, 000 led to negligible differences in the ID estimations, and N was thus fixed at 10, 000.
3.6 META-TRAINING SET
In order boost the robustness and generalizability of our optimizer posterior p(g" (D), we consider using an ensemble of objective functions JF = {fili= Specifically, we replace the objective function in Eq with N Σ> 1==1 Di= fu ,) and rewrite F(0*) as:
N
T Σ
1 F(O*) = N
fa 11
(11)
where w6-,: , is the solution at (th iteration for objective fi optimized by go.. Such replacement can let our posterior generalize to novel objective functions. We regard the functional dataset F as the meta-training set. During the experiments, we create different meta-traine meta-training sets for different problems, which will be described in details in Sec 4. We note that Eq 11 is also the objective or part of the objective in many meta-optimizers (Andrychowicz et al., 2016] Chen et al. 2017 Lv et al.] 2017 Cao et al. 2019a). However, those methods are focusing on training a deterministic optimizer without
3.7 TWO-STAGE TRAINING FOR EMPOWERING THE LOCAL POSTERIOR
As mentioned before, due the extreme large optimizer space, we focus on modelling the posterior locally around 0=, an optimum of interest. If we directly train our model through the Bayesian loss in 9 we simply regard that our posterior is locally around the random initialized point. In order to obtain an real optimum of interest 6% we first train our model in non-Bayesian way through minimizing the loss in Eq [1] We then use f as the warm start for μa, and start the second Bayesian training stage through the loss in Eq 9 posterior. Such statement can be demonstrated through the ablation study in Appendix
Both training stages are critical for empowering our local
3.8
MODEL ARCHITECTURE, IMPLEMENTATION AND COMPUTATIONAL COMPLEXITY
The model is implemented in Tensorflow 1.13 (Abadi et al. 2016 and optimized by Adam (Kingmal & Ba 2014). For the optimizer architecture, we use the coordinate-wise LSTM from Andrychowicz al. 2016). We also validate this design choice in Appendix F. Due the coordinate- wise nature, our B100 model only contains 10,282 free parameters. For all experiments, the length of LSTM is set to be 20. Both training stages include 5,000 training epochs.
The time complexity for BL20 is O(K tories, B is the minibatch size, N₂ is the number of objective parameters, and // is the hidden size of LSTM (H = 20 in the study). As the batch size increases, the computational cost is close to the traditional Bayesian neural networks trained through SGD. Due the coordinate- wise LSTM, the space coomplexity (memory cost) of BL20 is only (HH)), which remains the same the number of objective parameters varies. Both the time and the space complexity of BL.20 are the same as DM_LSTM (Abadi et al. 2016), while those of Adam are (KB) and O(Ne), respectively.
K.KKNN Nt?),, where K is the number of sampling trajec-
4 EXPERIMENTS
We test our BL20 model extensively on optimizing: non-convex test functions, energy functions in protein-protein interactions, loss functions in image classification and loss functions data privacy attack. We compare B1.20 to three non-Bayesian methods: Adam, Particle Swarm Optimization (PSO) (Kennedy Fberhart 1995). DMJLSTM (Andrychowiez et al., 2016) and a recently pub- lished Bayesian method, BAL (Cao & Shen 2020). All algorithms running for 10,000 times with random initializing points to obtain the empirical posterior distributions. During each run, the hy- perparameters in Adam and PSO sampled from Table/iih in Appendix A Out of 10,000 solutions we choose the one with the lowest function value to be the final solution (w)
Generally, for optimization performance,
assess the distance between the final solution and the global optima: || - w| The lower the distance is, the better the solution quality is. For un- certainty quantification, we assess the upper bound re and the real confidence 6, given fixed

---

Under review as a conference paper at ICLR 2021
confidence level The real confidence c, is defined by the fraction of 10,000 solutions that actu- ally fall in the bounded region. The lower the To is, the tighter the confidence interval is. And the closer of e, to is, the more accurate the confidence estimate is.
Comparison in optimizing test functions. We first test the performance on test functions in the global optimization benchmark set (Jamil & Yang 2013). We choose three extremely rugged, non- convex functions: Rastrigin, Ackley and Griewank in 5 dimensions: 6D, I2D, 18D, 24D, 30D. For each function, we create a diverse, broad family of similar functions f as the meta- training set used for training DM LSTM and BL2O. The analytical forms and the meta- training sets of those functions are shown in Table in Appendix B
We compare BL20 with all 4 competing methods. The optimization and UQ performances shown in Fig. [T] In all three cases and 5 dimensions, BL.20 has led to the best solution quality. In terms of UQ BL20 has shown the most accurate confidence estimation (e, x σ) when = 0.9 and a = 0.8, while BAL was the second best. And BL20 has shown much tighter confidence intervals ra against BAL. In some cases, although DM has lower va than BL20, it has much lower confidence level, indicating that this tight upper bound in DM_LSTM is miscalibrated. As a result, BL20 has shown the best performance in both optimization and UQ
Rastrigin
Rastrigin
Rastrigin
and LRLLSTM
14
I|
10-
10-
6
2
2-
24
30
18 Dimension
24
18
30
Dimension
Dimension
Addey
Ackley
Ackley
112
4.
I|W
1.10
12
18
24
30
6
18 Dimension
12
24
30
12
18
24
30
Dimension
Dimension
Griewank
Griewank
Griewank
-10
E0.9
0099
||00
2-
12
18
24
30
12
18
24
30
32
18
24
30
Dimension
Dimension
Dimension
Figure 1: The optimization performance (left) and the UQ performance (r. and ca) of different methods on three test functions.
Comparison in optimizing energy functions for protein docking, We then apply BL20 to a bioinformatics application: predicting the 3D structures of protein-complexes (Smith & Stembberg 2002]. called protein docking. Ab initio protein docking can be recast as optimizing a noisy and expensive energy function in a high-dimensionall conformational space (Cao Shen 2020): x" argmin, ming (a)). While solving such optimization problems still remains difficult, quantifying the uncertainty of resulting optima (docking solutions) even more challenging. In this section, we apply our BL20 to optimization and uncertainty quantification in protein docking and compare with a Mlate-of-the-at method BAL (Cao & Shen (020).
We describe the detailed settings of BL20 on protein docking in Appendix C From BL20, we obtain a posterior distribution p(w") (D) over the native structure w" and the lowest energy structure, w. In protein docking, the quality of predicted structure is based on the distance to the native structure w* f|. For UQ we assess the two-sided confidence interval at a = 0.9 w²|l & ro.9) 0.9.
(the global optimum): |/0 w"
as P(lo.9 & ||
7

---

Under review as a conference paper at ICLR 2021
In Table assess | w' ru.9 lu.9 and whether || || is within the confidence interval. For optimization, BL20 clearly outperforms BAL in two medium cases while performing slightly worse in the other cases. Yet for UQ. BL20 shows clearly superior performance over BAL in all cases, with accurate or/and tight confidence intervals. We also visulize the posterior distributions over | ="I for protein 1JMO_4. As shown in Fig 2
see compared to that of BAL., BL2O's distribution has real / w" within the 90% C.I. and smaller variance. More posterior
distributions are shown in Appendix D
Table Performances in optimization and uncertainty quantification on docking cases.
w
To.9
6.99 (A)
w"ll
E [1o.9, ro.9]
Target (docking diffficulty)
BAL
BL.0
BAL
BL20
BAL
BL200
IAHW .3 (easy)
1.89
2.07
2.20
1.98
No
No
1AK4_7 (easy)
2.45
2.70
1.93
1.66
Yes
Yes
3CPH 7 (medium)
3.89
3.21
1.70
2.20
No
Yes
THES 3 (medium)
3.05
2.32
2.24
1.61
Yes
Yes
1JMO_4 (difficult)
1.45
1.55
2.90
1.26
No
Yes
BAL 1JMO 4
B2LO 1JM0
Roal [iw -]
Deneity
1|W
[| W|l
Figure 2: Visualizations of estimated posterior distributions and confidence intervals.
Comparison in optimizing loss functions in image classification. We then test the performance of optimizing the loss function in image classification on the MNIST dataset. We apply 2- layers MLP network as the classifier. The competing methods include Adam, DM_LSTM and two Bayesian neural network methods: variational inference (VI) (Blundell et al.] 2015) and Learnable Bernoulli Dropout (LBO) (Boluki et al., 2020). Moreover, for DMLLSTM and BL20, we apply trick during the optimizer training called curriculum learning (CL) and introduce it in detail in Ap-
pendix B for training over long-tern iterations. We call DM LSTM with CL DM LSTM C and BL20 with CL. as BI.20 C.
The assessment of the optimization and UQ for this machine learning task is different from that for optimization before. In terms of optimization, we assess the classification accuracy on the test set. In terms of UQ we measure two metries that assess the robustness and trustworthiness of the classifier: the in-domain calibration error and the out-of-domain detection rate.
We first compare the accuracy on the testing set among different methods. As shown in Table 2 Adam, DMLLSTM.C and BL2O-C -_C have almost the same best performance. The significant im- provement from DM.LSTM to DM.LSTM.C and from BL20 to BL20-C shows the big advantage of curriculum learning in learning to optimize. In conclusion, BL20 C had on par accuracy with Adam and DM L.S... on the MNIST dataset.
However, classification models must not only be accurate, but also indicate when they are likely to be incorrect. Confidence calibration, the probability that estimates the true likelihood of each pre- diction is also important for classification models. In the ideal case, the maximum output probability (MaxConfidence) for each test sample should equal to the prediction accuracy for that sample. To assess the calibration of each methods, split the test set into 20 equal-sized bins and assess the calibration error as the average discrepancy between accuracy and MaxConfidence in each bin. As seen in Table 2 among all methods compared, BI20 C and BL20 had the least calibration error. The figure of Acc. vs MaxConf. is also shown in Fig. 4 in Appendix
We also inspect the -ft-oi-domain detection of BL20, BL20-C and competing methods. We train all models on the data belonging to the first 5 classes in the MNIST training dataset (the last layer of the optimizee is modified to have rather than 10 neurons) and test them the remaining
8

---

Under review as a conference paper at ICLR 2021
Table 2: Performance of classification on the MNIST set.
Models
In-Domain Accuracy (%)
In-Domain Calibration Error
Out-of- Detection
(%6
4.5(%)
Adam
93.2
5.0E-4
0.7
2.8
DM_LSTM
81.0
4.2E-3
0.4
2.0
DMLLSTMCC
93.4
9.9E-4
4.6
10.6
VI
87.8
4.4E-3
4.8
10.6
LBO
91.2
9.6E-4
5.2
11.3
BL20
90.1
4.9E-4
29.9
31,8
BL2O_C
93.5
4.3E-4
12.4
20.9
samples from the other 5 classes. An ideal model would predict uniform distribution over the wrong classes. Therefore, we define the out-of-domain detection rate at threshold t, Qt. as the percentage of test samples with max class confidence below t.. The larger the 4. the better out-of- domain detection is. As shown in Table BL20 and BL20.C - shows superior performance with all competing methods. Notably, BL20 without curriculum learning had much better out-of-domain detection rates compared to BL2O with curriculum learning.
Comparison optimizing loss functions for data privacy attack. We finally apply our model an application that critically needs UQ. As many machine learning models are deployed publicly, it is important to avoid leaking private sensitive information, such as financial data, health data and so on. Data privacy attack (Nast al., 2018) studies this problem by playing the role of hackers and attacking the machine-learning models to quantify the risk of privacy leakage. Better attacks would help models to be better prepared for privacy defense.
We use the model and dataset in (Cao et al., 2019b), where each input has 9 features involving patient genetic information and the output p the probability of the clinical significance (having cancer or not) for patient. We study the following model inversion attack (Fredrikson et al. 2015): by giving features w' E [0, 1] out and the label p of each patient, we want to recover the rest 4 features w* E [0, 1 (potentially sensitive patient information). Therefore, for each patient, the objective is wt = arg min |o. (m(w', w) - p)? where w" is the ground-truth m the trained predictive model. The closeness between the predicted and the real input features quantify the risk of information leakage and the quality of the attack. We compare BL20 with Adam, PSO, BAL and DM.LSTM on optimization and UQ on all test cases in (Cao et al. 2019b). The meta-training objectives for BL20 and DM LSTM are the training set in (Cao et al.) 2019b).
w and
As shown in Table BL20 has shown the best performance both optimization and UQ com- pared to all competing methods. It is noteworthy that learned optimizers (DM_LSTM and BL20) had much better optimization performance than pre-defined optimizers. And the Bayesian meth- ods (BAL and BI.20) had significantly better UQ performance than non-Bayesian methods. BI.20 possessed the advantages of both learned and Bayesian optimizers to achieve the hest performance.
Table The optimization and UQ performance of different methods on data privacy attack.
i wn
To.9
<0.9
0.9
To.s
co..8 0.8
Adam
0.45
0.74
0.10
0.63
0.20
PSO
0.32
0.82
0.10
0.72
0.20
BAL
0.34
0.53
0.06
0.41
0.08
LMLM
0.20
0.52
0.10
0.47
0.19
BL20
0.17
0.43
0.05
0.32
0.04
CONCLUSION
Current optimization algorithms, even with uncertainty-awarenee do not address the uncertainty arising within the optimizer itself. To close this gap, we parameterize the update rule as a neural net- work and build a Boltzmann-shane shhaped posterior over the algorithmic space. We apply our Bayesian Learning-to- totttmii (BL20) framework to optimize test functions, energy functions in protein docking, loss functions in image classification and loss functions in data privacy attack. The empiri- cal results demonstrate that BL20 outperforms the state-of-the methods both optimization and uncertainty quantification, well the calibration and out-of-domain detection in classification.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensortlow: system for large- scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Imple- mentation (OSDI 16), pp. 265 283, 2016.
Mohamed Osama Ahmed, Bobak Shahriari, and Mark Schmidt. Do we need "harmless" bayesian optimization and "first-order" bayesian optimization. NIPS BayesOpt, 2016.
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, 2016.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th anmual international conference machine learning, pp. 41-48, 2009.
Hildo Bijl, Thomas B Schön, Jan-Willem van Wingerden, and Michel Verhaegen. A sequen- tial monte carlo approach to thompson sampling for bayesian optimization. arXiv preprint 1004,0060 2016.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. arXiv preprint arXiv:1505.05542, 2015.
Shahin Boluki, Randy Ardywibowo, Siamak Zamani Dadaneh, Mingyuan Zhou, and Xiaoning Qian. Learnable bernoulli dropout bayesian deep learning. arXiv preprint arXiv:2002.05155, 2020.
Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv: arXiv:1012.2599 2010.
Yue Cao and Yang Shen. Bayesian active learning for optimization and uncertainty quantification in protein docking. Journal of chemical theory and computation, 16(8):5334 534437373337 2020.
Yue Cao, Tianlong Chen, Zhangyang Wang, and Yang Shen. Learning to optimize in swarms. In Advances in Neural Information Processing Systems, pp. 15018-15022 15028, 2019a.
Yue Cao, Yuanfei Sun, Mostafa Karimi, Haoran Chen, Oluwaseyi Moronfoye, and Yang Shen. Pre- dicting pathogenicity of missense variants with weakly supervised regression. Human mutation, 40(9):157--1592, 2019b.
Yutian Chen, Matthew Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P Lillicrap, Matt Botvinick. and Nando de Freitas. Learning learn without gradient descent by gradient descent. In Proceedings of the 34th International Conference on Machine Learning-Ven Volume 70, pp. 748-756. JMLR. org. 2017.
Jeremy S De Bonet, Charles Lee Isbell Jr, and Paul A Viola. Mimic: Finding optima by estimating probability densities. In Advances neural information processing systems, pp. 424-430, 1997.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Confer- ence on Computer and Communications Security, pp. 1322-1333, 2015.
David E Goldenberg, Genetic algorithms in search, optimization and machine learning, 1989.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1321-1330. JMLR. org, 2017.
Philipp Hennig and Christian J Schuler. Entropy search for iifformation-ffficiientt global optimiza- tion. The Journal of Machine Learning Research, 13(1):18091137) 2012.
10

---

Under review as a conference paper at ICLR 2021
José Miguel Henrández-Lobato. Matthew W. Hoffman, and Zoubin Ghahramani. Predictive Entropy Search for Efficient Global Optimization Black-box Functions. In Proceedings of the 27th In- ternational Conference Neural Information Processing Systems Volume 1, NIPS 14, pp. 918 926, Cambridge, MA, USA, 2014. MIT Press. URL http:/ /dl 1 acm. org cittiiii.iio...... c cfm?id=2968826. 2 2968929
José Miguel Hleránnde--Lohatt Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. In Advances in neural information processing systems, pp. 918-926- 2014.
Howook Hwang, Thom Vreven, Joël Janin, and Zhiping Weng. Protein-Protein Docking Benchmark Version 4.0. Proteins, 78(15)3111 3114, November 2010. ISSN 0887-3585. doi: 10. p0. 22830. URL htttht:t///wwet
www.iiww............m..........w nih. http://www.....o//////aaaaaaa//a /
Momin Jamil and Xin-She Yang. A literature survey of benchmark functions for global optimisation problems. International Journal of Mathematical Modelling and Numerical Optimisation, 4(2): 150-194, 2013.
Alex Kendall and Yarin Gal. What uncertainties do need in bayesian deep learning for computer vision?, 2017.
J Kennedy and R Eberhart. Particle swarm optimization, proceedings of ieee international confer- ence on neural networks (ienn't 995 in, 1995.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Scott Kirkpatrick, C. Daniel Gelatt, and Mario Vecchi. Optimization by simulated annealing. science, 220(4598)67116680, 1983.
Mare F. Lensink, Raúl Méndez, and Shoshana J. Wodak. Docking and scoring protein complexes: CAPRI 3rd Edition. Proteins: Structure, Function, and Bioinformatics, 69(4))704-718 Decem- ber 2007. ISSN 1097-0134.
doi: 10. 20.1000/prot.21800 URL
wiley. wtw.y//oommoo////acooomo/aa abs/ http://o./aabs11.10022// /tlp:///.c/.///////////////01/00 21804
Daniel James Lizotte. Practical bayesian optimization. University of Alberta, 2008.
Kaifeng Lv, Shunhua Jiang, and Jian Li. Learning gradient descent: Better generalization and longer horizons. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2247-2255. JMLR. org, 2017.
lain H. Moal and Paul A. Bates. SwarmDock and the Use of Normal Modes in Protein-Protenn Dock- ing. International Journal of Molecular Sciences, 11(10):3623 3648, September 2010. ISSN 1422-0067. doi: 10. 10.3390/ijssI 11000//mm1100623...... 103623. URL htw.hhttps:/// httpps://www..o http://www.cbbbbc mlmm n nic.hhhhhh. www.h..vvvvv.....o gtw.goo/rmmmoo gov/pmc/
Stticcea/PMMS PMCaPPPM22000 996808/
Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Stand-alone and federated learning under passive and active white-box inference attacks. arXiv preprint arXiv: /8/1. 28/2.009/ 2018.
Pedro Ortega, Jordi Grau-Moya, Tim Genewein, David Balduzzi, and Daniel Braun. A nonparamet- ric conjugate prior distribution for the maximizing argument of noisy function. In Advances in Neural Information Processing Systems, pp. 3005-3013, 2012.
Michael A Osborne, Roman Garnett, and Stephen J Roberts. Gaussian processes for global opti- mization. In 3rd international conference on learning and intelligent optimization (LION3), pp- 1-15, 2009.
Martin Pelikan, David E Goldberg, Erick Cantú-Paz, et al. Boa: The bayesian optimization al- gorithm. In Proceedings of the genetic and evolutionary computation conference GECCO-99, volume 1, pp. 525-532 Citeseer, 1999.
11

---

Under review as a conference paper at ICLR 2021
Brian G. Pierce, Kevin Wiehe, Howook Hwang, Bong-Hyun Kim, Thom Vreven, and Zhip- ing Weng. ZDOCK server: interactive docking prediction of protein-protein complexes and symmetric multimers. Bioinformaties, 30(12)1171-1173, 02 2014. ISSN 1367-4803. doi:
(0.1093hionffomaatissuu0000 URL btu097
K. A. Porter, Desta, D. Kozakov, and S. Vajda. What method use for protein-protee docking? Curr. Opin. Struct. Biol., 55:1-7, 04 2019.
B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas. Taking the Human Out of the Loop: A Review of Bayesian Optimization. Proceedings of the IEEE, 148417:4 January 2016. ISSN 0018-9219. doi: 10. 100////0C..20155229922 2444444288...
Alexander Shapiro. Probabilistic constrained optimization: Methodology and applications. Statisti- cal inference of stochastic optimization problems, pp. 282-304, 2000.
Graham R Smith and Michael JE Sternberg. Prediction of protein-proten interactions by docking
methods. Current opinion structural biology, 12(1):28 35, 2002.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
Gaussian pro-
Emmanuel Vazquez and Julien Bect. Convergence properties of the expected improvement algo- rithm with fixed mean and covariance functions. Journal of Statistical Planning and inference, 140(1 143811):3888-095 2010.
Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient bayesian optimization. arXiv preprint arXiv: /00.://7030/96 2017.
Jian Wu, Matthias Poloczek, Andrew Wilson, and Peter Frazier. Bayesian optimization with
gradients. In Advances in Neural Information Processing Systems, pp. 5267-5278, 2017.
Anatoly A Zhigljavsky. Theory of global random search, volume 65. Springer Science & Business
Media, 2012.
12

---

Under review as a conference paper at ICLR 2021
A
OPTIMIZER DISTRIBUTION SETTINGS FOR ADAM AND PSO
Methods
Optimizer Distribution Settings 1lg UT-2 -1], 31 00.,, 1.0), 32 0..999 1.0] w~ U|0.5 1.5]. CI ~ U[1.5, 2.5], C2 ~ U[1., 2.5]
Adam
PSO
Table 4: The optimizer distributions over hyperparameters Adam and PSO.
13

---

Under review as a conference paper at ICLR 2021
B ANALYTIC FORMS AND META-TRAINING SETS OF TEST FUNCTIONS
Function Name
Analytic form
Rastrigin
[)(w) = ||
10 coss(2:w; + 10n
Ackley
fy(w) = 20 expp (-0.2 (.xxp--.220... 0.5
(2 + e + 20
Griewank
fs(w) 11 1
1
E u II cos(w;)
4000
Meta- Meta-training set
Rastrigin
fy(w) |1 w byll 10c, cos(2 10z
Ackley
fa(w) - 20 exp 0.2 0.5|
A b - exp(c, cos (2TT)) /n)
Griewank
f+(w) + 2000 Σ
||
byll2 II. (cos(w:) + Cji - 1)
Table The analytic forms of test functions and the meta-training sets used for training DM.LSTM and BL2O, where is the dimension and A, E _=x" bj E _ and сj E gnx1 are parameters whose elements are sampled from i.i.d. normal distributions. is obvious that the test functions are the special cases in the training sets, respectively.
14

---

Under review as a conference paper at ICLR 2021
C SETTINGS FOR PROTEIN DOCKING EXPERIMENTS
We calculate the energy function (objective function fx)) in a CHARMM 19 force field as Moal & Bates 2010). 25 protein-protein complexes are chosen from the protein docking benchmark set 4.0 (Hwang et al. 2010) as the training set, which is shown in Table 6 For each target, we choose starting points (top-5 models from ZDOCK (Pierce et al. 2014)).
total, our training set includes 125 samples. Moreover, we parameterize the search space as R 12 as in BAL (Cao & Shen 2020). The resulting f(z) is fully differentiable in the search space. We only consider 100 interface atoms due to the computational concern. The number of iterations for one training epoch is 600 and in total we have 5000 training epochs. Both BL.20 and BAL have 600 iterations during the testing stage. For fair comparison, after optimization, we rescore the BL20 samples for UQ using the scoring function (random forest) in BAL.
Table 6: 4-letter ID of proteins used the training set.
Difficulty level Rigid
Protein Data Bank (PDB) code
IN80, 7CEI, IDFJ. 1AVX, IBVN IIQD, ICGI, IMAH, IEZU, IJPS, IPPE, IROR, 2125, 2B42, IEAW, 2JEL, IBJ1, IKXQ, IEWY IXQS, 1MT0, 1IJK ,GGNN IIBR, 1ATN
Medium
Flexible
15

---

Under review as a conference paper at ICLR 2021
D POSTERIOR DISTRIBUTIONS IN PROTEIN DOCKING
BAL 1AHW
BL20 1AHW 3
Real I[w
12
5% talls
12
1.0
90% C.I.
10-
Density
Density
2.-
04
24-
62-
3
4
l/ v
l| w|
BAL 1AK4 7
B2LO 1AK4
12-
12-
1.0
10
Density
Density
3.6
0.4
244
02-
02-
3
4
5
2
3
l| vi|l
1| w|
BAL 3CPH 7
BL20 3CPH
Real I[w" WIll
12-
5% tails
12-
1.0
90%
1.-
Density
Density
0.
2.6
0.4
24-
02
12
3
2
3
|| w|
|| W|
BAL 1HEB 3
B2LO
1HES
12-
1.0
1.-
Density
Density
0.
0.4
2.4
02
12-
4
2
Wi
W|
Figure 3: Visualizations of estimated posterior distributions and confidence intervals for more dock-
ing cases.
16

---

Under review as a conference paper at ICLR 2021
E CURRICULUM LEARNING AND CALIBRATION FIGURE IN IMAGE CLASSIFICATION
A common issue in learning optimize for neural network training is that: the optimizer training usually takes hundreds of iterations, while training a neural network usually costs thousands or tens of thousand iterations. For instance, for a MNIST training dataset consisting of 50,000 images, training a neural network for 100 epochs corresponds to almost 20,000 iterations with a batch size of 128.
Hundreds of iterations are good for the first few epochs during optimizer training, since we would like to only focus on decreasing the loss in the first hundreds of iterations. However, training goes we would like to see that the later iterations could also decrease the training loss. During this stage, only hundreds of iterations are clearly not enough.
In order to overcome this issue, we bring the idea from (Bengio et al. 2009). Specifically, We set list for the number of iterations: [100, 200, 500, 1000, 1500, 2000, 2500, 3000] and we gradually increase the number of iterations following the list for every 100 epochs in optimizer training if the optimizee loss is decreasing. Once the number reaches 3000, it will not change any more until the training ends.
Adam
1.0
LSTM
DM_LSTM_C
0.8-
VI
Accuracy
LBO
BL20
0.6-
BL20_C
0.
0.0
0'a
MaxConfidence
Figure 4: The calibration figure image classification.
F ABLATION STUDY.
In order to validate various design choices, we perform the ablation study as follows:
B1: We use the coordinate-wist gated recurrent unit (GRU) network as the optimizer ar-
chitecture. We train our model directly on the Bayesian loss: Eq 9 without non-Bayesia Bayesas training.
B2: We replace the GRU network with the LSTM network.
BL20: We add the non-Bayesian training stage to find local optimum of interest first before training on the Bayesian loss.
17

---

Under review as a conference paper at ICLR 2021
Rastrigin
Rastrigin
Rastrigin
E0.3
12
Ri20
14-
2:10
12
18 Dimension
24
30
12
18
24
30
12
18
30
Dimension
Dimension
Figure 5: Ablation study: the optimization performance (left) and the UQ performance (ra and c,)
of different models on the Rastrigin function.
We test these three models the Rastrigin test function. As shown in Fig 5 B2(LSTM) has slightly better performance in both optimization and UQ compared to GRU. But BL20 has shown superior performance compared to both B1 and B2 in optimization and UQ. These results clearly demonstrate that the two training stages must be coupled together to empower the local posterior.
18


Reviews:
[{"review_id": "xD7mayFdceR", "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": "Summary:\nThis paper proposes to account for an additional source of uncertainty during inference, i.e., the uncertainty introduced by the optimization algorithm. The paper uses a neural network to parameterize the optimization algorithm, and proposes intuitive and heuristic techniques for inferring its posterior distribution.\n\nStrong points:\n- The paper provides a novel perspective by considering the uncertainty introduced by the optimization algorithm, which is novel as far as I know.\n- The experiments cover a diverse set of applications, which indeed showcases the generality of the proposed algorithm.\n\nWeak points:\n- Since the main contribution of the paper is accounting for the uncertainty introduced by the optimization algorithm which is very novel, I think a more rigorous definition of this source of uncertainty is needed. In particular, I think the paper needs a clear definition and illustration of $p(g(\\cdot)|\\mathcal{D})$ which is the ultimate distribution the paper is trying to approximate. Analogously, in standard posterior inference, $p(\\omega|\\mathcal{D})$ is defined through the prior $p(\\omega)$ and likelihood $p(\\mathcal{D}|\\omega)$ which links the observed data $\\mathcal{D}$ and the model parameter $\\omega$ by defining how likely $\\mathcal{D}$ is generated by a given $\\omega$. However, I don't see such a clear link if I replace $\\omega$ by $g(\\cdot)$: how should the likelihood $p(\\mathcal{D}|g(\\cdot))$ be interpreted? Does this mean the choice of the optimization algorithm affect how the observed data is generated?\n- Section 2, first paragraph: it says here that for these Bayesian optimization algorithms, \"significant approximation is needed\". But I wonder whether this can be framed as a disadvantage of these algorithms? I think it should not be a disadvantage as long as these approximations deliver good performances. Also it would be interesting to see the proposed method applied to Bayesian optimization, although this is not an important point.\n- The paper measures the quality of the solution $\\hat{\\omega}$ by $||\\hat{\\omega}-\\omega^*||$ (Equation 3 and in the experimental results). However, I think this may not be very appropriate and $||f(\\hat{\\omega})-f(\\omega^*)||$ would be a better measure, because if $f$ is very non-smooth, even if $||\\hat{\\omega}-\\omega^*||$ is small, $f(\\hat{\\omega})$ may be very large.\n- I think many design choices of the algorithm are too heuristic and lack a rigorous justification. For example, at the bottom of page 3, it is claimed that \"it is important to optimize the following loss\" of Equation 5, but why? Also, defining the different objective functions $f_j(\\cdot)$ by different mini-batches (Equation 6) seems like a convenient and arbitrary choice, and doesn't seem very rigorous. This further calls into question the reliability of the experimental comparisons, since it seems that there isn't a rigorous way to choose these objective functions (I think referred to as \"meta-training set/objectives\" in the Experiments section), and different choices may affect the performance (this should be explored empirically if possible).\n- For experiments, most baselines under comparison are non-Bayesian methods. This doesn't seem very appropriate since the goal of the paper is to learn a better $p(\\omega^*|\\mathcal{D})$ (Equation 4) which is a distribution. I think more Bayesian methods than non-Bayesian methods should have been compared with. For example, for the image classification experiment, the only Bayesian method under comparison is the VI paper from 2015, since then, there have been a number of more recent works on Bayesian neural networks, and it would be better if more comparisons with BNN is performed.\n- In the experimental comparisons, the paper claims that a tighter confidence bound $r_{\\sigma}$ is better. However, I think this may not be the case. For example, if we are training a Bayesian neural network using a very small dataset, then the posterior $p(\\omega^*|\\mathcal{D})$ isn't supposed to be concentrated right?\n- Table 2: It seems without the curriculum learning trick (which is not a main contribution of this paper), BL2O is significantly outperformed by Adam.\n\nMore minor points:\n- Section 2, first paragraph, third line: here \"Bayesian optimization\" should be replaced by some specific instances of Bayesian optimization algorithms such as predictive entropy search, since what's described here isn't how a generic BO algorithm works but only some BO algorithms. It could be misleading to some readers not familiar with BO.\n- Section 2, last paragraph: I think this paragraph (maybe except for the first sentence) should belong to the end of Introduction instead of here.\n- Figure 1: Error bars should be included.\n\n\n----------------------Update After Rebuttal----------------------------------\n\nI appreciate the response from the authors, and the authors' efforts in significantly revising the Method section. The Method section in the current version looks much better and clear. Most points from the authors' response are reasonable, and some of my concerns are indeed cleared, such as my questions regarding the use of $||\\hat{\\omega}-\\omega^*||$ instead of $||f(\\hat{\\omega})-f(\\omega^*)||$. However, in the revised paper, I still find a few places questionable, so I still have a few concerns which are still about the first and fourth points I raised in my original review:\n\n- In Definition 3.2 of the revised paper, I find this definition of optimal optimizer $g^*$ not fully convincing. I understand that this definition of $g^*$ naturally gives rise to the $F(\\theta^*)$ as in the first line of page 5, however, since our problem is an optimization problem (i.e., to minimize $f$), I think the summation in the definition of $g^*$ should be replaced by minimization. The current definition of using a summation over different iterations could lead to problems in some scenarios. For example, imagine we have optimizer B who quickly converges to a local minimum, and optimizer B who explores the entire search space first (encountering many large $f$ values along the way) and finally converges to the global minimum. Then according to this definition, optimizer A is likely to be defined to be better than optimizer B, which is incorrect. Moreover, another problem with the current definition is that the initialization $\\omega^1_g$ is not specified. I feel that for the sake of defining the optimal optimizer, the argmin over all optimizers $g\\in\\mathcal{G}$ should be based on the same initialization for all optimizers, i.e., $\\omega^1_g$ is the same for all $g\\in\\mathcal{G}$. Since I imagine that for different initializations, the optimal optimizer could be different.\n\n- Equation (5) on page 4, I think the distribution of the initial point $p(\\omega^1_{\\theta^*})$ should appear on the Right Hand Side. Because given the optimizer $\\theta^*$, the distribution of the trajectory $\\mathcal{D}$ clearly depends on the initialization. This may not be a serious problem since $p(\\omega^1_{\\theta^*})$ could be factored into the normalization constant of $p(\\theta^*|\\mathcal{D})$.\n\n- Section 3.6, I still find the motivation for using the Meta-Training Set heuristic. It is stated here that the meta-training set is introduced here to improve the robustness and generalizability of solutions, which seems unrelated to the main objective of quantifying optimizer uncertainty. I think (not sure though) a better motivation could be related to uncertainty regarding the function $f$.\n\n- Although the objective of the paper is to \"further\" consider the uncertainty regarding the optimizer, I feel that the introduced method ONLY considers optimizer uncertainty, and hasn't dealt with $p(\\omega^*|\\mathcal{D},g)$ in a rigorous way. If I understand correctly, samples from $p(\\omega^*|\\mathcal{D},g)$ are obtained by running optimizer $g$ for multiple random initialization points (line 5 of Section 4), and I find this kind of heuristic.\n\nOverall I find this paper very interesting mainly due to the novel perspective of considering this additional source of uncertainty, so although I cannot recommend for acceptance this time, I believe it will be a valuable contribution to the community if the problem formulation can be made more rigorous.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "qKTUEZNQAA", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "###########\n Summary:\n\nThe paper considers the question of quantifying the uncertainty that arises from the optimiser used to perform inference in a given model. Taking a Bayesian approach, the aim is to deduce the posterior over the space of optimisers. The form for the posterior is chosen to be a Boltzmann distribution which is then approximated with a multivariate Gaussian using a KL divergence. The parameterisation for the posterior is defined using an LSTM neural network.\n\n\n###########\nReasons for score: \n\nThe high-level idea in the paper is intriguing but I found the logic in the methodology hard to follow and interpret, and it is not clear to me how this work is able to estimate the uncertainty or why it would improve the performance of existing approaches to optimisation. \n\n\n##########\nPros:\n\n- The main high-level idea seems clear.\n- The experiment section is quite extensive and the results provided suggest the approach may have some merit.\n\n\n##########\nCons:\n\n- The presentation is not clear, especially in the method section. It is rather strange that instead of defining the prior over possible optimisers, the paper only talks about the posterior. \n- It seems to me that this work relies heavily on the work of Ortega et al (2012), and if that is the case, a clearer presentation of the main arguments of that work would be very useful. \n- The arguments in the problem statement seem quite scattered. For example, I'm not sure I see the relation of Eq. (3) to the rest of this work. Could you explain this statement from page 3 in some more detail:\n\"It is straightforward to first model the posterior over the global optima (p(w∗|D)) and then sample from the posterior to obtain...\"\n- Some ablation studies may clarify the effect of the various design choices. For example, (1) using an LSTM as a way to parameterise the model, (2) the choice of a local region for the local posterior. \n- One of your criticisms of MC estimates of optimiser uncertainty is that \"it heavily relies on the pre-defined distributions (discrete grids) over the hyperparameters and(or) the start points\". However, in your case, the model seems to be constrained to a local neighbourhood of the input parameters, which seems even more limiting to me. \n- The overall quality of the writing could be improved (for example, Sec. 1 and 2 include a lot of repetition).\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "n3JwBQWHZWO", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "**(Summary)**\nIn order to model the uncertainty of optimizers the authors model the algorithmic space of optimizers by a neural network and use a Boltzmann-shaped posterior posterior over this space.  The use VI to approximate the intractable posterior distribution. Finally, they show that they demonstrate their approach on a diverse set of benchmarks.\n\n**(Strong points)**\n- This is an interesting problem and an interesting approach to understanding the effect of optimizer uncertainty.\n- The experimental section is strong and demonstrates that the proposed method works on a large variety of problems.\n\n**(Weak points)**\n- The paper is quite hard to read due to a rather large number of grammatical errors and typos. The authors need to spend some more time working on the text to make the paper easier to read.\n- I would have appreciated a more thorough discussion on why modeling the space of algorithms by a neural network is a good idea as there are many other possible modeling options that aren’t discussed.\n\n**(Recommendation)**\n- I think this paper may be suitable for publication if the authors improve the quality of the text and address my questions in this rebuttal.\n\n**(Questions for the authors)**\n- Why do you choose to look at $||\\hat{w} - w^*||$ instead of $|f(\\hat{w}) - f(w^*)|$? To what extent does noise in the function observations play into this decision?\n- As theta are the parameters of the neural network, the dimensionality of the integral in 3.5 must be quite large and I can imagine that $N=10,000$ is far from enough to get an accurate estimate.  What motivates this choice and did you explore QMC or other variance reduction techniques?\n- For appendix A, why isn’t the learning rate for Adam log-uniform as it is usually modeled in a log-scale?\n- How well are you able to approximate the intractable posterior?\n\n**(Additional feedback)**\n- The narrative is a bit confusing. In section 2 you describe related work that is mostly zeroth order methods and then in section 3 you start talking about first order methods, which are the focus of the paper.\n- While many methods can be written as the following weight update rule, there are methods that can’t, such as Bayesian optimization with gradients.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers felt that the idea of learning a posterior distribution on optimization algorithms is very novel. However, the negative flip side of this novelty was that it was not clear how the prior and likelihood were defined so that Bayes rule could be approximated. The three reviewers appeared to find the paper somewhat confusing, and while the authors' made significant changes, it would be better to resubmit for a new set of reviews of the revised paper.
Decision: Reject