Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ###########
 Summary:

The 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.


###########
Reasons for score: 

The 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. 


##########
Pros:

- The main high-level idea seems clear.
- The experiment section is quite extensive and the results provided suggest the approach may have some merit.


##########
Cons:

- 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. 
- 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. 
- 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:
"It is straightforward to first model the posterior over the global optima (p(w∗|D)) and then sample from the posterior to obtain..."
- 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. 
- 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. 
- The overall quality of the writing could be improved (for example, Sec. 1 and 2 include a lot of repetition).


review_title: Confusing paper

final_score: rating: 6: Marginally above acceptance threshold
review_content: **(Summary)**
In 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.

**(Strong points)**
- This is an interesting problem and an interesting approach to understanding the effect of optimizer uncertainty.
- The experimental section is strong and demonstrates that the proposed method works on a large variety of problems.

**(Weak points)**
- 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.
- 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.

**(Recommendation)**
- 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.

**(Questions for the authors)**
- 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?
- 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?
- For appendix A, why isn’t the learning rate for Adam log-uniform as it is usually modeled in a log-scale?
- How well are you able to approximate the intractable posterior?

**(Additional feedback)**
- 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.
- While many methods can be written as the following weight update rule, there are methods that can’t, such as Bayesian optimization with gradients.
review_title: Understanding the effect of optimizer uncertainty

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
This 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.

Strong points:
- The paper provides a novel perspective by considering the uncertainty introduced by the optimization algorithm, which is novel as far as I know.
- The experiments cover a diverse set of applications, which indeed showcases the generality of the proposed algorithm.

Weak points:
- 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?
- 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.
- 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.
- 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).
- 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.
- 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?
- Table 2: It seems without the curriculum learning trick (which is not a main contribution of this paper), BL2O is significantly outperformed by Adam.

More minor points:
- 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.
- Section 2, last paragraph: I think this paragraph (maybe except for the first sentence) should belong to the end of Introduction instead of here.
- Figure 1: Error bars should be included.


----------------------Update After Rebuttal----------------------------------

I 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:

- 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.

- 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})$.

- 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$.

- 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.

Overall 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.

review_title: Novel but Has Important Weaknesses

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