Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Updated review
----
----

# Summary

This work proposes an approach for model-based optimization based on learning a density function through an approximation of the normalized maximum likelihood (NML). This is done by discretizing the space and fitting distinct model parameters for each value. To lower the computational cost, the authors propose optimizing the candidates concurrently with the model parameters. Each model's distribution is encoded as a neural net outputting a scalar which is then encoded using a thermometer approach using a series of shifted sigmoid. Candidates are optimized based on the average value of the scalar of each model evaluated using parameters obtained from an exponentially weighted average of its most recent parameters.

# Reason for score

This work proposes a reasonable approximation to an interesting estimator and demonstrate it is capable of achieving good consistent performance. This is likely to be of interest to the community and, as far as I'm aware, is sufficiently novel. Given that I see no noteworthy issues and all of my major concerns have been addressed, I don't see any reason for rejection. I strongly support acceptance.

# Pros

* Using estimates of the NML for model-based optimization is an interesting idea.
* This work shows that the NML can be successfully approximated with a relatively coarse discretization and that both the optimization of the candidate and the various model parameters can be optimized in tandem. This suggests that this type of approach is viable and possibly warrants further investigation.


Initial review
----
----

# Summary

This work proposes an approach for model-based optimization based on learning a density function through an approximation of the normalized maximum likelihood (NML). This is done by discretizing the space and fitting distinct model parameters for each value. To lower the computational cost, the authors propose optimizing the candidates concurrently with the model parameters. Each model's distribution is encoded as a neural net outputting a scalar which is then encoded using a thermometer approach using a series of shifted sigmoid. Candidates are optimized based on the average value of the scalar of each model evaluated using parameters obtained from an exponentially weighted average of its most recent parameters.

# Reason for score

There are a lot of typos and issues with the notation which make this paper unfit for publication in its current state. Otherwise, the work seems interesting but I find the experiments don't provide much insight. Though the comparison with the selected method is favorable, it's hard to consider them significant when there is a notable difference in only one of the three datasets of an unpublished benchmark. Additionally, the fact that the reported results only cover half the datasets from this benchmark raises some questions. Despite the negative tone of this paragraph, I want to note that the severity of some of these issues is subjective while others can be easily fixed. My mind isn't made up and I hope the authors can clarify anything I might have missed.

# Pros

* Using estimates of the NML for model-based optimization is an interesting idea.
* This work shows that the NML can be successfully approximated with a relatively coarse discretization and that both the optimization of the candidate and the various model parameters can be optimized in tandem. This suggests that this type of approach is viable and possibly warrants further investigation.

# Cons

* The current notation is often confusing and even ambiguous at times. This will probably transpire in some of my other comments, but I do consider these issues to be superficial and easily fixed. I've provided some suggestions below for how to improve the notation. I understand that notation preference is a very subjective thing so the authors should feel free to opt for something different, but I do think the notation needs to be improved.
* The "thermometer encoding" of the output seems like an odd choice, especially given how it is done here. If I understood the approach correctly, this seems to be a hacky way of using the output of the NN, $o_{int}$, as parameters to a logistic distributions. Why not treat it this way directly? My interpretation of this approach is that the $o^k_{int}$s are parameters for logistic distributions and the mean is optimized through the unnormalized probs by optimizing each $o^k_{int}$ directly. Would this be a fair description of the approach? I was expecting the discretization to be used directly to approximate the integral in eq. (2). 
* The experimental results aren't very conclusive, only showing a clear benefit in a single case. Without additional results, it is difficult to say much about the behavior and properties of this method. A visualization of the distribution of the value of the candidates might help convey some additional information in favor of this method. It's possible that I am missing some context to appreciate these results. If that is the case, it would help if the authors could provide the context I need to appreciate these results.

# Questions

* I don't think I understand what makes the appendix results an ablation study. From what I understand, these results only compare with the case where there is no learning of the model parameters. What are the models initialized to? Where does the data come into play?
* Have the authors considered using points selected from some fixed quadrature method instead of a uniform grid?
* A common theme for the comparison methods is the idea of not diverging too much from the data. Was the validity of the outputs of this method evaluated in any way? How can I know that the method isn't just exploiting some quirk in the learned models used to evaluate it while some of the other methods avoid doing this?
* Were comparisons with a simple approaches Bayesian optimization tried, e.g., Gaussian process?
* What happens when doing more iterations on the log likelihood before updating $x$? How much do we lose when only doing a single update? Does using a more accurate approximation of the NLM improve/worsen performance? (I was hoping this would be part of the ablation study)
* How do the run times compare?
* Were the other datasets from the Design-bench benchmark tried?

# Misc and typos

* page 2, "in that it has shown to be", missing word?
* page 2, "to discuss how approximate this intractable", missing word?
* page 3, when $p_{NML}$ is formally written, the meaning of $y$ is ambiguous since it is on the LHS and also being redefined by $\max_y$ in the RHS.
* page 3, "The notation $D \cup (x, y)$ refers to an augmented dataset $D \cup (x_{N+1}, y_{N+1})$", this wasn't very informative and felt a bit tautological. I would recommend sticking with one of the two notations.
* page 3, "where $D$ is fixed to the given offline dataset, and $\theta_{D \cup (x,y)}$ [...]", this sentence is a bit confusing as a whole. The start of the sentence talks only about $D$ so the $\theta$ mention is unexpected when reading.
* page 3, right after eq. (2), $(x, y)$ is on the LHS but then also part of the expectation on the RHS. What is the expectation being taken over? Are $x$ and $y$ being redefined?
* page 4, "for y in 1 ... K do", is $y$ I don't believe that $y$ is assumed to be an integer. 
* page 4, algorithm 4?
* page 4,  "this would produce a distribution over output values $p(y|x)$", this doesn't "type check" for me. If I understood correctly, $p$ or $p(\bullet | x)$ represent distributions and $y$ are output values. Also, it might be good to reuse the "$\hat p_{NML}$" notation to get the following sentence: "this would produce a conditional distribution, $\hat p_{NML}(\bullet | x_t)$,  over output values.
* page 4, "we can optimize $x_t$ with respect to some evaluation function $g(y)$ of this distribution, such as the
mean", this is confusing since algorithm 1 has $\mathbb{E}[ g(y)]$. What does it mean for the evaluation function $g$ to be the mean in this context? How should I interpret the expectation of mean(y)? Also, I assumed that what was meant is that $g$ is the evaluation function, not $g(y)$, or is $g$ meant to return a function given a $y$?
* page 6, "a straightforward choice for the evaluation function g is the identity function $g(x) = x$", it might be best to stick to a consistent variable name, e.g., $g(y) = y$, to avoid confusion about what the domain of $g$ is.
* Proof of thm 4.1, equation under "using these two facts, we can show:", $q$ should be replaced with $p_{NML}$ in the RHS.
* Proof of thm 4.1, going from TV to KL, looking up the bound returns a $1/2$ factor inside the root rather than a $2$. I could have missed a detail but thought worth mentioning in case I haven't.
* Proof of thm 4.1, missing a "]" when bounding the KL divergence.
* Algorithm 2, there is some undefined superscript $k$ and $y$ in the loop over $x^m_t$.

# Notation suggestions

* When writing expectations, I would strongly recommend making it explicit over which variables they are, e.g., $\mathbb{E}\_{y \sim p(\bullet | x, \theta)}$. Introducing some shorthand notation might help make this more concise, e.g., $p_{x, \theta}(y) := p(y | x, \theta)$.
* When referring to a function, only mention its name/symbol and reserve the form that includes inputs to refer to the output of the function given those inputs, e.g., a function $g$, an evaluation score $g(y)$.
* Avoid relying on the readers pattern matching abilities for assigning meaning to variables and make sure variables, e.g., $\mathbf{x}$ and $y$, are always explicitly defined. By explicitly defined, I include defining $y$ compactly with something like $\max_{y \in \mathcal{Y}} g(y)$, for example. There is not need to be overly verbose but it should never leave room for interpretation. This is related to the point about expectation notation.
* I usually prefer explicit domains, e.g., $\sum_{y \in \mathcal{Y}}$ instead of $\sum_y$, but I consider it fine to omit it if variables names are always reserved to the same domain when reused. This was not the case for $x$ in this paper.
* When writing pseudocode, either loop over integer indices or over elements of a set, it is confusing to use "for y in 1 ... K" when $y$ isn't an integer. Additionally, using both makes it difficult to tell that $k$ is associated with $y$ inside a loop.
review_title: Reviewer 2

final_score: rating: 6: Marginally above acceptance threshold
review_content: # summary

This paper proposed a method based on NML and provided a principled approach
to estimate the uncertainty for OOD data.


# pros

1.  The method proposed in this work is a principled way to handle uncertainty
    for novel points out of the original dataset compared with, for example,
    deep ensemble.
2.  One clear advantage of ths proposed approach is this method can scale to
    large dataset, compared with GP, which scales cubically.


# cons

1.  The authors claim using a supervised approach is brittle and prone to
    failure as the uncertainty of inputs outside of training data is
    uncontroled. However, this is not true and uncertainty can be well
    controlled depending on the model, which can be non-parametric or
    parametric, distribution-free or distribution-dependent. For example, to
    measure uncertainty on novel point, GP could be viewed as the ground truth
    under some conditions. My question is why not directly compare your
    approach with a GP approach, then combine the posterior with an acquisition
    function, such as EI. The offline MBO problem presented in this work is
    similiar to an online MBO, except we have only one online sample, and
    we are tying to optimize this point. Comparing eq(1) of this paper with the
    formula of EI, it is easy to see eq(1) is exactly EI, if we assume there
    exists (x\*,y\*) such that y\* is larger than objective values in the training
    data set. Thus the problem presented in this work can be effectively solved
    through **one step** of conventional BO. Given the datasets used in the
    experiments of this work is are not of large scale, I think comparing with
    a GP-based BO is necessary.
2.  In Figure 3, although not a major concern, I don't think the comparison
    with the ensemble is fair. Although this work uses bootstrap and ensemble,
    MSE cannot capture uncertainty, thus it is not an ideal metric in this
    setting. For example, to obtain a similar uncertainty estimation compared
    with NML (middle column), we can use a deep ensemble, which optimizes NLL
    instead of MSE.
3.  The experimental results, in my opinion, are not sufficient and there is
    only one table presenting empirical results. I don't want to judge
    sufficiency by the quantity of tables or figures, but considering the
    theoretical analysis is not strong enough, I think more empirical study
    should be performed.
4.  The uncertainty estimation seems too conservative, and this could make the
    estimated uncertainty less useful, especially for high-dimensional
    problems.


# questions

The approach proposed in this paper seems very similiar with conformal
prediction. In conformal prediction, the target value y\* for a novel point x\*
(adversarial input) is chosen so that y\* is compatible with the original
dataset. As I am not familiar with the evaluation protocol in Brookles2019 and
Fannjiang2020, the metric used in Table 1 is not clear to me. Can the authors
say more about that?

update:

---
Overall speaking, the added GP-BO results address my  concerns, and I've updated the score from 5->6. A final update will be given later.
review_title: Official Blind Review #1 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: The paper proposes an approximation method, called NEMO (Normalized maximum likelihood Estimation for model-based optimization)  to compute the conditional normalized maximum log-likelihood of a query data point as a way to quantify the uncertainty in a forward prediction model in offline model-based optimization problems. The main idea is to construct a conditional NML (CNML) distribution that maps the high-dimensional inputs to a distribution over output variables. In addition, the paper provides a theoretical motivation that estimating the true function with the CNML is close to the best possible expert even if the test label is chosen adversarially, which is a great challenge for an optimizer to exploit the model. By using this CNML on three offline optimization benchmark datasets (Superconductor, GFP, MoleculeActivity) with gradient ascent-based optimization, the NEMO outputs all the other four baselines on the Superconductor dataset by almost 1.4x to 1.7x, the generate comparable results as the other four baselines method on the GFP and MoleculeActivity datasets.   

Typo: 
In section 4, “We outline the high-level pseudocode in Algorithm 4” -> “…. in Algorithm 1”

Questions: 
1. When sampling a batch of data points at each step of algorithm 1, is the sampling performed with or without replacements?  
2. What’s the variance across the 16 random runs? Is the score of the best algorithm in the average performance across 16 random runs significantly different from the baseline algorithms?
3. When estimating the CNML, what is the number of models in the experiments? Are the number of models differ from dataset to dataset? How to choose the number of models in practice?
4. Since the output y needs to be discretized in the NEMO algorithm, how difficult for the algorithm to scale when y is multivariate?

------------------------------------------------------------------------------------------------------------
Update: 
I think the authors did a great job of addressing my concerns, I'm happy to increase my score to 6

review_title: Utilizing normalized maximum-likelihood for better estimation of model uncertainty for offline data-driven optimization

Meta-review: This work proposes a model-based optimization using an approximated normalized maximum likelihood (NML). It is an interesting idea and has the advantage of scaling to large datasets. The reviewers are generally positive and are satisfied with authors' response.  
Decision: Accept (Poster)