Year: 2021

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 (a.k.a., optimizer) itself? To close such a gap, the prerequisite is to consider the optimizers as sampled from a distribution, rather than a few prefabricated and fixed update rules. We first take the novel angle to consider the algorithmic space of optimizers, and provide definitions for the optimizer prior and likelihood, that intrinsically determine the posterior and therefore uncertainty. We then leverage the recent advance of learning to optimize (L2O) for the space parameterization, with the end-toend training pipeline built via variational inference, referred as uncertainty-aware L2O (UA-L2O). Our study represents the first effort to recognize and quantify the uncertainty of the optimization algorithm. The extensive numerical results show that, UA-L2O achieves superior uncertainty calibration with accurate confidence estimation and tight confidence intervals, suggesting the improved posterior estimation thanks to considering optimizer uncertainty. Intriguingly, UA-L2O even improves optimization performances for two out of three test functions, the loss function in data privacy attack, and four of five cases of the energy function in protein docking. All our codes will be publicly released upon acceptance.

heading: 1 INTRODUCTION
text: 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 optimizer) could guarantee the global optima in general. Instead their solutions’ usefulness (sometimes based on their proximity to optima), when the optima are unknown, can be very uncertain. Being able to quantify solution uncertainty directly provides calibration with ensured awareness of the solution quality and usefulness (and another potential benefit is in optimization performance by enhancing the search efficiency). For instance, reliable and trustworthy machine learning models demand uncertainty awareness and quantification (UQ) during training (optimizing) such models, whereas in reality deep neural networks without proper modelling of uncertainty suffer from overconfidence and miscalibration (Guo et al., 2017). In another example of 3D prediction of proteinprotein interactions, even though there exists the model uncertainty of the objective function and the data uncertainty of the protein structure data (Cao & Shen, 2020), state-of-the-art methods only predict several ranked solutions (Porter et al., 2019) without any associated uncertainty, which is hard for biologists to interpret.
Despite progress in optimization with uncertainty-awareness, fundamental open questions remain: existing methods consider uncertainty either within the data or the model (including objective functions) (Kendall & Gal, 2017; Ortega et al., 2012; Cao & Shen, 2020), whereas inconspicuous attention was paid to the uncertainty arising from the optimizer that is directly responsible for deriving the end solutions. The optimizer is usually prefabricated and fixed. For instance, there are several popular update rules in Bayesian optimization, such as expected improvement (Vazquez & Bect, 2010) or upper confidence bound (Srinivas et al., 2009), that are chosen and unaltered for the entire process. For Bayesian neural networks training, the update rule of the iterative optimizer is usu-
ally chosen off-the-shelf like Adam, SGD, or RMSDrop. In principle, it is important to recognize the existence of an optimization algorithm space where the specific optimizer lies as well as the importance of the optimizer uncertainty, intrinsically defined in the space to the optimization and UQ solutions. In practice, such uncertainty is unwittingly omitted in the current context where an optimizer is treated as a de facto specified sample in the space.
A naı̈ve characterization for a hand-built optimizer is to rely on a few of its hyper-parameters (Wenzel et al., 2020; Lorraine & Duvenaud, 2018), whereas such a parameterization space could be too biased and restricted to span a broader and more complicated optimizer manifold, potentially resulting in inaccurate UQ results (see Section 4, confidence estimation for test functions). Fortunately, the recent surge of learning to optimize (L2O) (Andrychowicz et al., 2016a; Li & Malik, 2016; Chen et al., 2021) which is another prominent optimization paradigm, parameterized by a neural network using high-dimensional weights and following the data-driven ethos to learn the update rule adaptively, therefore introducing the less inductive bias and accompanied with the universal approximation ability, indicates a plausible solution to depict the sophisticated and more complete optimizer space.
Contributions. The aforementioned introduction reveals and discusses the fundamental question of why modelling the optimizer uncertainty, and our contingent questions would be, what defines the optimizer uncertainty and how to enable UQ during optimization. We give the following answers. (i) We define the prior and likelihood of the optimizer (Neal, 2012), which routinely determine the optimizer posterior with the general product rule and Bayes’ theorem. The optimizer uncertainty is therefore well-defined. (ii) To unseal UQ within optimization, we treat an optimizer as a random sample from an algorithmic space of iterative optimizers. We leverage the surging L2O technique (Andrychowicz et al., 2016a; Li & Malik, 2016) with high-dimensional weights for the optimizer space parameterization. (iii) We further construct the end-to-end training pipeline via variational inference (Kingma & Welling, 2013; Higgins et al., 2016) to avoid the expensive computational cost of Markov chain Monte Carlo (MCMC) and degenerated posterior. The newly trained L2O is referred as uncertainty-aware L2O (UA-L2O). In summary, the core intellectual value of this work is for the first time, we recognize and quantify a novel form of uncertainty that lies in the optimization algorithm space parameterized by L2O, apart from the classical data- or model-based uncertainties (also known as epistemic and aleatoric uncertainties (Fox & Ülkümen, 2011)).
Extensive experiments show that UA-L2O had superior capability in uncertainty calibration thanks to the accurate estimation of solution posteriors. It confidence levels well match the chance for the global optimum falling in the corresponding intervals. Intriguingly, although not directly targeted, UA-L2O also outperformed competing methods in optimization performance, as seen in optimizing two out of three test functions in high dimensions, the loss function in data privacy attack, energy functions in four out of five protein-docking cases.

heading: 2 PRELIMINARIES

heading: 2.1 LEARNING TO OPTIMIZE
text: Let us consider an optimization problem: minx f(x) where x ∈ Rd. A classic optimizer often iteratively updates x based on a handcrafted rule. For example, the first-order gradient descent algorithm takes an update at iteration t based on the local gradient at the instantaneous point xt: xt+1 = xt − α∇f(xt), where α is the step size. Learning to Optimize (L2O) has lots of freedom to use the available information. We define zt as optimization trajectories’ historical information up to time t, e.g., the existing iterates x0, . . . ,xt, and/or their gradients ∇f(x0), . . . ,∇f(xt). L2O models an update rule by a predictor function g of zt: xt+1 = xt − g(zt;φ), where the mapping of g is parameterized by φ. Finding an optimal update rule can be formulated mathematically as searching for a good φ over the parameter space of g. Practically, g is often a neural network. Since neural networks are universal approximators, L2O has the potential to discover completely new update rules without relying on existing rules. In order to find a desired φ associated with a fast optimizer, (Andrychowicz et al., 2016b) proposed to
minimize the weighted sum of the objective function f(xt) over a time span T :
min φ T∑ t=1 wtf(xt), with xt+1 = xt − g(zt;φ), t = 0, . . . , T − 1, (1)
where w1, . . . , wT are the weights whose choices vary from case to case and depend on empirical settings. Note that φ determines the objective value through determining the iterates xt. L2O solves the problem (1) for a desirable φ and correspondingly the update rule g(zt;φ).
A typical L2O workflow is divided into two stages (Chen et al., 2021): a meta-training stage that learns the optimizer with a set of similar optimizees from the task distribution; and a meta-testing stage that applies the learned optimizer to training new unseen optimizees. The meta-training process often occurs offline and is time consuming. However, the online application of the method is (aimed to be) time saving.

heading: 2.2 THE UNCERTAINTY OF OPTIMIZATION
text: The choice of optimizers is recognized to remarkably impact the solution quality, especially for non-convex and rugged objectives such as various loss functions for training deep networks. While non-convex optimization is NP-hard and the global optimum is never guaranteed, domain users usually can only blindly take the solutions given by a particular optimizer, or choose from several well-known algorithms based on human experiences or on an ad hoc basis. Such trial-and-error selections are biased and restricted to span a more complete optimizer manifold, and computationally expensive, even intractable when new algorithms are to be discovered by L2O, whose “fitness” or confidence on certain problem instances (especially instances with shifts from the target task distributions) is never known. Given a specific problem instance, if we can provide a confidence score or quantify the uncertainty of each candidate optimizer, it will certainly improve the selection and calibration of optimization algorithms, in particular the learned optimizers since they are essentially all “new”, and hence enhancing the reliability of L2O.
As for non-convex objectives, different choices of optimizers, even each algorithm’s hyperparameter or initialization variations, can lead to vastly different solutions, implying a new type of uncertainty arising from choosing optimizers. Stochastic optimization methods like random search (Zhigljavsky, 2012), simulated annealing (Kirkpatrick et al., 1983) and genetic algorithms (Goldenberg, 1989) inject the randomness into algorithms to reduce solution uncertainty. However, they cannot reliably quantify its effect on the final solutions. Several works explored uncertainty quantification during optimization, by Bayesian optimization (Hennig & Schuler, 2012; Wang & Jegelka, 2017) or Monte Carlo sampling (Ortega et al., 2012). However, those methods are often computationally too expensive, not to mention applied within the already costly L2O process. More importantly, they neither explicitly consider the uncertainty within the optimizer itself, nor concern the automatic learning and discovery of the most suitable optimizer.

heading: 3 TECHNICAL APPROACH
text: To quantify and address such “fitness” especially for the L2O parameterization in a principled way, we will introduce this new optimizer uncertainty arising from the choice of optimization algorithms, which is different from the classical data- or model-based uncertainties (also known as epistemic and aleatoric uncertainties (Fox & Ülkümen, 2011)). We will explore: how to quantify optimizer uncertainty? how to design a learned optimizer so that its uncertainty can be more accurately quantified? what is the best calibrated optimizer we can choose or learn for a given problem?
The core innovation is to treat an optimizer as a random sample from a continuous algorithmic space, rather than one of a few hand-crafted update rules, so as to model the intrinsic uncertainty within the optimizer. This novel view of algorithmic space is particularly enabled by L2O. Note an L2O update rule is typically parameterized by a neural network g, with its inputs zt and learnable parameters φ. Its learning capacity allows us to “sample” optimizers by taking g(· ;φ) with different weights φ. That is sufficiently versatile and flexible in practice.

heading: 3.1 CONCEPTS FOR OPTIMIZER UNCERTAINTY
text: Without loss of generality, we define am iterative algorithmic space G, where each point g ∈ G produces an update g(zt) dependent on the current/past zero-th order and/or first-order information zt. We treat g as a random vector from G, that leads to defining the optimizer uncertainty as follows:
Definition 1 (Optimizer Uncertainty) Let G be the algorithmic space, where each point g ∈ G is an optimizer (omitting φ parameterization). We assume that
1. g has a prior distribution p(g); 2. Its likelihood can be interpreted as p(zt|zt0 , g) = ∏t i=t0+1 p(xi|zi−1, g), ∀t0 < t.
The likelihood factorization is based on causality of first-order optimizers, i.e., (xi, zi) depends solely on {(xi0 , zi0)}i0<i given g. Thereby, we define the optimizer uncertainty at step t as the posterior of g, that is a conditional distribution on the t steps of the trajectory, using Bayes’ theorem:
p(g|zt) ∝ p(g) t∏ i=1 p(xi|zi−1, g). (2)
Intuitively, the prior p(g) represents the belief about well-performing optimizers, the likelihood p(zt|zt0 , g) represents the probability of observing an optimization trajectory (data) under a given optimizer g, and the posterior p(g|zt) represents the probability for g being the optimizer generating the observed data.
Prior work on hyper-parameter optimization (HPO) for classical algorithms (Feurer & Hutter, 2019) could be viewed as a special case of L2O (e.g., only a few hyper-parameters are “learnable”, which resulting in a much biased and restricted prior p(g)). The seminal work Bergstra et al. (2011) optimized hyper-parameters using posterior-based fitness modeling. Recently, Wenzel et al. (2020) proposed a non-Bayesian approach of hyper-parameter ensembling that can estimate the predictive uncertainty of an optimization algorithm by varying hyper-parameters. Our work generalizes from tuning a few hyper-parameters to learning the entire optimizer space, and extends a Bayesian treatment. Since L2O involves much higher-dimensional parameters compared to HPO, its uncertainty quantification calls for computationally tractable and scalable approaches, which is detailed next.

heading: 3.2 L2O WITH BAYESIAN UNCERTAINTY QUANTIFICATION
text: Now that we have the optimizer space G parameterized in φ, an optimizer g is modeled as a random vector in the space. That allows for reducing the modeling of optimizer uncertainty p(g|zt) to modeling the posterior p(φ|zt). For simplicity, we use a Gaussian prior of φ: p(φ) ∝ exp(− 12λ‖φ‖ 2 2) where λ is a constant. We also follow the widely-adopted idea in (Gal & Ghahramani, 2016; Bishop & Tipping, 2003; Ortega et al., 2012; Cao & Shen, 2020), to view the loss function value as proportional to the negative logarithmic likelihood, i.e., p(xt|zt−1, g) = p(xt|zt−1,φ) ∝ exp(−f(xφt )). We can then calculate the posterior of the optimizer based upon equation (2):
p(φ|zT ) ∝ exp(− 1
2λ ‖φ‖22) T∏ t=1 exp(−f(xφt )) = exp ( − T∑ t=1 f(xφt )− 1 2λ ‖φ‖22 ) . (3)
Training. Maximum a posteriori (MAP) estimation of the optimizer parameters leads to a degenerate distribution and point estimation without uncertainty. Moreover, directly maximizing the optimizer posterior in Eq. 3 via Markov chain Monte Carlo (MCMC) would encounter computational intractability considering the high-dimensional space of the optimizer space parameterized in L2O by neural network weights. Instead, we introduce a variational distribution q(φ;θ) (Kingma & Welling, 2013) with the variational parameter θ and accordingly we introduce the following objective function whose minimization is equivalent to maximizing the evidence lower bound (ELBO) (see Appendix D for the derivation):
− KL[q(φ;θ)||p(φ|zT )] = −Eφ∼q(φ;θ) T∑ t=1 f(xφt )− KL[q(φ;θ)||p(φ)]. (4)
We refer to the L2O under the new meta-training loss (4) w.r.t θ as uncertainty-aware L2O (UAL2O), which can be trained end-to-end with the Gaussian parametrization and the reparametrization trick (Kingma & Welling, 2013; Higgins et al., 2016). The feed-forward computational chart for training UA-L2O is depicted in Figure 1.
Deployment. With the well-trained UA-L2O and the found θ∗, we ideally assume the function values of the trajectory are submartingales that Eφ∼q(φ;θ∗)f(xφt+1) ≤ f(xt), Eφ∼q(φ;θ∗)|f(x φ t )| < ∞. Then based upon martingale convergence theorem (Doob, 1953) limt→∞ f(xt) = f(x∞) exists almost surely, i.e. it converges with infinite optimization iterations. Within the finite steps, UA-L2O has a well-defined approximated posterior q(φ;θ∗), and hence the baked-in ability to quantify optimizer uncertainty at the solution. Therefore, the posterior of solutions is calculated by the integration with the variational distribution q(φ;θ∗) as:
p(x∗|zT ) = ∫ p(x∗|zT ,φ)q(φ;θ∗)dφ, (5)
which can be estimated by Monte Carlo sampling. Specifically, for estimating the solution posterior, the learned model is run 10,000 times with random initialization and different trajectories zt accordingly. The optimizer parameter θ is sampled from q(θ|φ∗) once per iteration, following variational inference as in Kingma & Welling (2013) and Higgins et al. (2016).

heading: 4 EXPERIMENTS
text: We examine our proposed UA-L2O on optimizing: (i) non-convex test functions, (ii) loss functions in data privacy attack, and (iii) energy functions in predicting 3D protein-protein interactions (protein docking). We compare UA-L2O with three non-Bayesian methods: manually-designed Adam (Kingma & Ba, 2014) and particle swarm optimization (PSO) (Kennedy & Eberhart, 1995) as well as DM LSTM (Andrychowicz et al., 2016a), an L2O method. We also compare to Adam and PSO with hyper-parameter Bayesian optimization (Adam-BO and PSO-BO), Adam with learning rate ensebles (Adam lr Ensemble) and Adam with stochastic gradient MCMC (Adam Noisy Gradient). Lastly we compare to Bayesian active learning (BAL) (Cao & Shen, 2020).
For Adam and PSO, we make their hyper-parameters probabilistic to calculate the posterior as shown in Table 6 in Appendix. All algorithms are running for 10,000 times with random initialization to obtain the empirical posterior distributions p(x∗|zT ), following Eq. 5 for UA-L2O and its counterparts for others. we access the optimization uncertainty with the following expression (Ortega et al.,
2012; Cao & Shen, 2020): P ( lbσ ≤ ‖x∗ − x̂‖2 ≤ ubσ ) = 1− σ, (6)
where lbσ and ubσ are the lower and upper bounds at the confidence level of σ, and we choose the one with the lowest function value (we also study mean value in Appendix E) to be the estimated solution x̂. Ablation on different runs and comparison of wall-clock time with competitors are presented in Appendix E. For the choice of assessing the proximity of solutions rather than function values |f(x∗) − f(x̂)|, the reason is in many optimization applications (e.g. privacy attack and protein docking), the objective function actually plays the role of the “tool” instead of the “goal”, that the function value is not the key metric to assess the quality of solutions in particular when the objective function is non-convex and noisy.
Evaluation metrics. UA-L2O is designed for uncertainty awareness in the optimizer. To assess the calibration of uncertainty quantification (UQ), we use the accuracy of confidence, following (Ortega et al., 2012; Cao & Shen, 2020). In other words, we compare expected confidence levels σ as in Eq. 6 (0.8 and 0.9 in this paper) and the empirical probability εσ of “success” when the corresponding confidence intervals indeed contain the global optima. When there is a tie in the major assessment metric σ− εσ , the tightness of the confidence interval for the solution’s proximity to the global optimum (Eq. 6), rσ = ubσ − lbσ , serves as a tie-breaker. A schematic illustration of the uncertainty assessment is shown in Figure 2.
Although UA-L2O is designed for the uncertainty awareness rather than the quality of optimization solutions, we still assess potential benefit in optimization performance, using the expected distance between the optimized solutions and the global optimum Ex∗∼p(x∗|zT )‖x∗ − xtrue‖2. The lower distances indicate the better solution quality (optimization performance).
Two-stage training. Due to the extremely high-dimensional optimizer space and the rugged posterior landscape, it is over-challenging to directly train the model through the equivalency of ELBO optimization in Equation (4). We therefore perform two-stage training where we first train our model in a non-Bayesian way and then use the resulting θ as the warm start for fine-tuning the mean variational parameters in the second stage. We examine the performance of the warm-start model in Appendix E to show benefit of the second-stage training.
Implementations. The model is implemented in Tensorflow 1.13 (Abadi et al., 2016) and optimized by Adam (Kingma & Ba, 2014). For the L2O architecture, we use the coordinate-wise LSTM from (Andrychowicz et al., 2016a) containing 10,282 free parameters. The meta-training and test data description please refer to Appendix B. For all experiments, the length of LSTM is set to be 20, with 5,000 training epochs for both training stages. We tune the λ values in equations (3) and (4) from {0.1, 1, 10}, validated by validation performance in test functions and the tightness of confidence intervals in privacy attack and protein docking. The ablation study on λ is presented in Appendix C showing that UA-L2O is not sensitive to its values.

heading: 4.1 NON-CONVEX TEST FUNCTIONS
text: Setup. We first evaluate the performance on the test functions in the global optimization benchmark (Jamil & Yang, 2013). We choose three extremely rugged, non-convex functions, Rastrigin, Ackley and Griewank with analytical forms shown in Appendix B, paired with dimensionalities in {3, 6, ..., 30}. Results. We compare UA-L2O with competitors in optimization and UQ performances shown in Figure 3. In the most relevant assessment metric, the accuracy of confidence levels (middle column), UA-L2O performs the best in all but few cases for all three functions, outperforming hand-engineered optimizers, non-Bayesian or Bayesian, and L2O without uncertainty awareness (DM LSTM). Given that UA-L2O consistently outperforms competitors in confidence accuracy, comparing the tightness of confidence intervals (right column) alone is not meaningful. Note that other methods, when having tighter confidence intervals, were often too overconfident to realize that the true global optima were inside the intervals much less than their confidence levels suggested.
We also examined potential but not intended benefits of UA-L2O in optimization performance (right column of Figure 3). Interestingly, UA-L2O even improved optimization performances for Ackley and Griewank functions when the dimensionality is above 12, while being slightly worse in Rastrigin. These results echo our conjecture that, although our central goal is not for better optimization
solutions but for their better uncertainty awareness, better uncertainty calibration could sometimes improve optimization performances.
We further plot the confidence for solution regions segmented in ‖x∗−x̂‖2 versus the corresponding optimization performance ‖x∗ − xtrue‖2 (see Appendix A for detailed procedure) in Figure 9. We find that when UA-L2O achieves better optimization performance (Ackley and Griewank as opposed to Rastrigin), it generates solutions with higher confidence in the regions closer to the global optima and with narrower distributions (more certain). In contrast the competitors do not show such trends.

heading: 4.2 DATA PRIVACY ATTACK
text: Setup. We next apply our model to an application that critically needs UQ. As many machine learning models are deployed publicly, it is important to avoid leaking private and sensitive information, such as financial data and health data. Data privacy attack (Nasr et al., 2018) studies this problem by playing the role of hackers and attacking 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 shown in Appendix B, and the output is the probability of the clinical significance (pathogenicity) for genetic variants in patients. We study the following model inversion attack (Fredrikson et al., 2015): given 5 features x′ ∈ [0, 1]5 out of 9 and the label y of each patient, the privacy attack aims to recover the rest 4 features xtrue ∈ [0, 1]4 (potentially sensitive patient information). Therefore, the optimization is minx∈[0,1]4 ∑ (g(x′,x) − y)2 for all patients where g is a trained predictor. The closeness between the optimized and real input features can quantify the risk of information leakage and the quality of the attack. We evaluate our method for all test cases in (Cao et al., 2019b).
Results. We report the UQ and optimization performances of UA-L2O in Table 1. In UQ, UA-L2O’s performance (the accuracy of estimated confidence) stands out against competitors, although not as
dominant as it does to competitors in test functions. Even in optimization, UA-L2O outperforms all competitors, which again demonstrate the potential benefit of uncertainty-awareness to optimization. Note that PSO had slightly more accurate confidence but much looser intervals, suggesting flat posteriors and leading to worse optimization.
We argue that, unlike pure optimization problems in test functions, the optimization for privacy attack involves the generalization issue in the machine learning paradigm: less generalizable samples pose challenges to not only optimization but also UQ. To verify this argument, we plot optimization performance for individual samples versus their estimated posterior precision in Figure 4 showing a positive correlation: samples easier to generalize are closer to the optima (more leftward in the x-axis), and more precise in estimated confidence (more downward in the y-axis). The tightness of confidence intervals is also well correlated with solution quality.
Similar to that in Section 4.1, we also plot confidence versus optimization performance in Figure 10, to further demonstrate the calibration capability of UA-L2O.
4.3 ENERGY FUNCTIONS FOR PROTEIN DOCKING
Setup. We lastly examine UA-L2O using a bioinformatics application: predicting the 3D structures of proteincomplexes (Smith & Sternberg, 2002) or protein docking. Ab initio protein docking can be recast as optimizing a noisy and expensive energy function in a highdimensional conformational space (Cao & Shen, 2020). While solving such optimization problems still remains difficult, quantifying the uncertainty of resulting solutions is even more challenging. The compared state-of-the-art method is BAL (Cao & Shen, 2020).
We calculate the energy function (objective function f(x)) in a CHARMM19 force field as in (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 Appendix C. For
each target, we choose 5 starting points (top-5 models from ZDOCK (Pierce et al., 2014)). In total, our training set includes 125 samples. Moreover, we parameterize the search space as R12 as in BAL. The resulting f(x) is fully differentiable in the search space. We only consider 100 interface atoms due to the computational concern. Results. We compare UA-L2O and BAL in Table 2. For UQ, UA-L2O not only achieves a more accurate confidence as shown in Figure 6 and Appendix C (three of five cases had ground truths located in 90% confidence intervals), but also has a clearer trend that the better solutions correspond
to tighter intervals (more certain) as in Figure 5 (with Pearson correlation coefficient of 0.59 versus -0.8 for BAL). Even for optimization, UA-L2O outperforms other methods in four out of five cases. The results show significant advantages of UA-L2O compared with the state-of-the-art BAL in both UQ and optimization for protein docking.

heading: 4.4 RESULT SUMMARY
text: We briefly summarize the results as follows.
• In general, UA-L2O achieves better optimization performance with a few exceptions. This echos the hypothesis that the assessment of uncertainty is able to enhance the search efficiency and effectiveness during optimization.
• UA-L2O provides the most accurate posterior estimation most of the time. This empirical evidence verifies the effectiveness of our uncertainty-aware L2O inspired from theory.
• Accurate posterior estimation is a key for UA-L2O’s superior calibration capability, such that UA-L2O generates solutions closer to optima with higher confidence and tighter confidence intervals, whereas competitors suffer from overconfidence or miscalibration. Such calibration capability is critical to detect the failure cases in real-world applications.

heading: 5 CONCLUSIONS
text: Current optimization algorithms, even with uncertainty-awareness, do not address the uncertainty arising within the optimizer itself. To close the gap, in this paper we attempt to ask and address three fundamental questions, why modelling the optimizer uncertainty, what defines the optimizer uncertainty, and how to enabling UQ during optimization. We first emphasize the uncertainty arising from the optimizer is a crucial source that directly responses for the end solutions deriving, except for data- and model-uncertainty. Next, we define the prior and likelihood of the optimizer which determines the optimizer posterior and the optimizer uncertainty. We further leverage learning to optimize (L2O) for the optimizer parameterization, treating an optimizer as a random sample from an algorithmic space of iterative optimizers, with the end-to-end training pipeline built via variational inference. Extensive experiments show UA-L2O achieves the optimization performance, superior in two out of three test functions with the high variable dimension, best in the loss function in data privacy attack, and exceeded in the energy function for protein docking in four out of five cases. Besides, it delivers the most accurate posterior estimation and calibration capability, with the solutions closer to the ground truth of a larger population and tighter confidence intervals. Our study represents the first effort to recognize and quantify the uncertainty of the optimization algorithm, with extensive support from numerical results and analysis.
REPRODUCIBILITY STATEMENT
To ensure reproducibility, we use the Machine Learning Reproducibility Checklist v2.0, Apr. 7 2020 (Pineau et al., 2021).
• For all models and algorithms presented,
– A clear description of the mathematical settings, algorithm, and/or model. We clearly describe all of the settings, formulations, and algorithms in Section 3.
– A clear explanation of any assumptions. We state our assumptions clearly in Section 3.
– An analysis of the complexity (time, space, sample size) of any algorithm. We do not make the analysis.
• For any theoretical claim,
– A clear statement of the claim. We provide a clear statement in Section 3. – A complete proof of the claim. We do not make theoretical proofs.
• For all datasets used, check if you include:
– The relevant statistics, such as number of examples. We provide all the related statistics in Section 4 and Appendix B.
– The details of train/validation/test splits. We give this information in our repository. – An explanation of any data that were excluded, and all pre-processing step. We
give this information in our repository. – A link to a downloadable version of the dataset or simulation environment. Our
repository contains all of the instructions to run experiments on the datasets in this work. We put it in supplementary materials.
– For new data collected, a complete description of the data collection process, such as instructions to annotators and methods for quality control. We do not collect or release new datasets.
• For all shared code related to this work, check if you include:
– Specification of dependencies. We give installation instructions in the README of our repository.
– Training code. The training code is available in our repository. – Evaluation code. The evaluation code is available in our repository. – (Pre-)trained model(s). We do not release trained models. – README file includes table of results accompanied by precise command to run
to produce those results. We include a README with detailed instructions to reproduce all of our experimental results.
• For all reported experimental results, check if you include:
– The range of hyper-parameters considered, method to select the best hyperparameter configuration, and specification of all hyper-parameters used to generate results. We provide all details of hyper-parameter tuning in Section 4.
– The exact number of training and evaluation runs. Ten thousand independent repetitions are conducted for each experiments.
– A clear definition of the specific measure or statistics used to report results. We provide all details of evaluation metrics in Section 4.
– A description of results with central tendency (e.g. mean) & variation (e.g. error bars). We report confidence intervals for all experiments in Section 4.
– The average runtime for each result, or estimated energy cost. We do not report the running time or energy cost.
– A description of the computing infrastructure used. A clear description is presented in Section 3.

heading: A CONFIDENCE ESTIMATION PROCEDURES
text: In evaluation, for the confidence versus optimization performance scatter plot, we first perform Monte Carlo sampling on the solution posterior, and then bin the solutions to estimate their fraction and corresponding average distance to the optimum. Detailed procedures can be found in Algorithms 1.
Algorithm 1: Confidence estimation with corresponding optimization performance Input: Sampled solutions x∗ with size N , estimated solution x̂, known optimum xtrue, bin width w. Initialize: S = {}. 1. Calculate ‖x∗ − x̂‖2 for all sampled solutions, and bin them with w. for each bin b do
2. Calculate the population fraction |b|/N . 3. Calculate average distance to xtrue: Mean({‖x∗ − xtrue‖2|x∗ ∈ b}). 4. S ← S ∪ (|b|/N,Mean({‖x∗ − xtrue‖2|x∗ ∈ b})).
end for Return: Scatter point set S.

heading: B DATA DESCRIPTION
text: The analytical forms of three test functions are shown in Table 3. The meta-training data are a broad family of similar functions (Cao et al., 2019a). For Rastrigin, it is fD(x) = ‖Ax − b‖22 − c ∑D i=1 10 cos(2πxi) + 10D where A, b, c are sampled from i.i.d normal distributions; for Ackley,
it is fD(x) = −20 exp(−0.2 √ 0.5‖Ax− b‖22) − c ∑D i=1 exp(cos(2πxi)/D) + exp(1) + 20; for
Griewank, it is fD(x) = 1 + ∑D i=1‖Ax− b‖22/4000− c ∏D i=1 cos(xi).
For privacy attack, we use 9-dimension features of privacy attack data generated from MutPred2 (Pejaver et al., 2017), which captures mutational impacts on protein structure, dynamics, and function, and grouped hierarchically into a custom oncology based on their inherent relationships. The list of features can be found in Table 4. The meta-training is performed on 1,593 patients and we evaluate in 318 patients (Cao et al., 2019b).
For protein docking, the PDB IDs of meta-training samples are shown in Table 5 and we test in proteins with PDB in Table 2.

heading: C MORE EVALUATION RESULTS
text: We provide more evaluation results as follows. (i) The ablation of λ values on three test functions is shown in Figure 7. (ii) The UQ results for test cases 1AHW 3 and 1JMO 4 in protein docking are plotted in Figure 8.

heading: D COMPUTATION OF UA-L2O OBJECTIVE FUNCTION
text: We first rewrite the evidence as: log p(zT |zt0) = ∫ q(φ;θ) log p(zT |zt0)dφ = ∫ q(φ;θ) log
p(zT ,φ|zt0) p(φ|zT ) dφ
= ∫ q(φ;θ) log p(zT ,φ|zt0)dφ− ∫ q(φ;θ) log p(φ|zT )dφ
=− ∫ q(φ;θ) log q(φ;θ)
p(zT ,φ|zt0) dφ+
∫ q(φ;θ) log q(φ;θ)
p(φ|zT ) dφ
=−KL[q(φ;θ)||p(zT ,φ|zt0)] + KL[q(φ;θ)||p(φ|zT )],
where−KL[q(φ;θ)||p(zT ,φ|zt0)] is ELBO and KL[q(φ;θ)||p(φ|zT )] is our objective. Therefore, minimizing KL[q(φ;θ)||p(φ|zT )] is equivalent to maximizing ELBO (Yin & Zhou, 2018). We rewrite our objective as:
KL[q(φ;θ)||p(φ|zT )] = Eφ∼q(φ;θ) { log q(φ;θ)− log p(φ|zT ) } =Eφ∼q(φ;θ) { log q(φ;θ)− log p(φ)p(zT |zt0 ,φ) } + Z
=Eφ∼q(φ;θ) { log q(φ;θ)
p(φ) − log p(zT |zt0 ,φ)
} + Z
=Eφ∼q(φ;θ) T∑
t=t0+1
f(xφt ) + KL[q(φ;θ)||p(φ)] + Z

heading: E ABLATION STUDY
text: We perform ablation studies on sample size in uncertainty quantification of UA-L2O in Table 7, mean versus minimum of x̂ computation and wall-clock time comparison in Table 8, on privacy attack experiment on gene BRCA1/2 in Table 9. Results show UA-L2O is not sensitive to sample size or mean/minimum calculation of x̂, and it is comparably efficient with competitor optimizers.
We further compare with baselines as learning rate ensemble and stochastic gradient MCMC of Adam, shown in Table 10. We also make comparison with warm-start UA-L2O to show the improvement of UA-L2O training.

Review summaries:
This paper proposes a Bayesian Learning to Optimize technique called Uncertainty-Aware Learning to Optimize (UA-L2O). The main contribution of this paper is its introduction of the concept of the space of optimization algorithms and treating an optimizer as a random sample from it, and deriving a proper Bayesian inference algorithm based on that concept. The space of optimization algorithms, to simplify, is expressed as a space of parameters of learned optimizers $\phi$, and a Gaussian prior is placed on those parameters. The posterior inference procedure is approximated with variational inference with reparameterization tricks, and the actual deployment of the learned optimizer is done with Monte-Carlo approximation with learned variational distribution for the optimizer parameters $\phi$. The proposed algorithm is applied to various synthetic and real-world optimization problems and showed some useful calibration behaviors.

This paper considers the problem of quantifying the uncertainty of an optimizer used to do inference on a given model. The authors take a Bayesian approach and treat the optimizer as a random variable in the space of algorithms. They derive an approximate posterior via variational inference. 

The authors looked at uncertainty quantification (UQ) of optimization algorithms. Working under the L2O framework and adopting the Bayesian approach, they used a neural network to model the updating rule, and endowed the network weights with a prior. By treating the solution iterates and their gradients as data, the authors defined a conditional likelihood on them. The resulting posterior on the network weights is then approximated using a variational algorithm. To conduct inference, the authors computed the predictive density of the solution through Monte Carlo sampling. This end-to-end pipeline is called uncertainty aware L2O (UA-L2O) and it is applied to quantify uncertainty in various learning tasks.