Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper concerns an important and broad issue in machine learning regarding hyperparameter optimisation (HPO) and that it might lead to inconsistent outcomes and conclusions about approaches and their performance, in particular the performance that is relative to other approaches. The authors argue that the analysis of an HPO should be an object of study by itself. The paper takes into account some existing related work in regard to HPO. It provides definitions for an (HPO) log, an HPO procedure, an epistemic HPO procedure, to formalise the reasoning process regarding HPOs, among other definitions. It provides an illustration (an example) of how HPOs can be deceptive (that example is also referenced in further sections to help the narrative). As a possible solution, the authors suggest a process (they call it “epistemic hyperparameter optimization” or “EHPO”) and a logical framework (with syntax and semantics provided). That provides a way to analyse uncertainty in EHPO and reason about inconsistent HPO conclusions, to which such uncertainty might lead. The authors define a t-non-deceptive EHPO via a definition that depends on some time (i.e. “t-”) notion (relevant to execution time of experiments). They also show how, theoretically, a defended reasoner can be made, the use of which could result in a guaranteed t-non-deceptive EHPO. Then, they present a defended version of a random search for HPO and present a theorem statement regarding such a search’s t-non-deceptiveness under certain assumptions. Then, the authors explain and show results for an experiment using a modified version of the random search on the illustrative example, and finally they conclude the paper and provide a summary of some practical takeaways.
main_review: This is a very important submission. Its significance is huge. Thanks extremely much to the authors for their work.

The paper is written generally well.

The prior work is described and scoped well. Based on that, the idea and approach seem to be novel.

Note that one, potentially relevant, point does not seem to be covered in the related work review: the hyperparameter optimisation belongs to a general class of optimisation problems, and it probably would be relevant to cover any relevant literature regarding optimisation in general (or mention that there is none relevant).

Clarity:

A. In the Definition 2, it is not exactly clear whether a PRNG (Pseudo-random number generator) G is used only for running A_lambda-s or also for picking lambda-s (e.g. as part of a random search), or for both? The educated guess from the Definition 2 is that it is used only for the former (i.e. for running A_lambda-s) but that is not fully clear. (If that is the case, is it that the randomness of H* itself (e.g. for choosing different lambda-s) left “ambiguous”?) It would be helpful to have it all clarified. (A clarification for this would be also important to help interpret lines 242-244, where it is discussed what a demon could or could not control regarding a PRNG, and line 262 (to understand and verify whether all randomness is covered there or not)).

B. The line 166 talks about “We want to be sure that we will not be deceived by any logs the demon *could* produce” - is it generally realistic in practice?

C1. (A discussion point and a minor clarity point.) It is explained in lines 180-189 that statistics is not the choice for this work. It is appreciated that applications of statistics are generally made under certain assumptions and its use might give false confidence. However, it is not clear what other tool, rather than statistics, can be used to analyse situations with uncertainty (to quantify it), even though it is not easy to quantify that uncertainty, as the authors highlight. Moreover, the authors do seem to use probability theory/statistics themselves in the paper (e.g. in the definition 5, which is one of the key definitions in the submission, and in theorem 1), _in conjunction_ with modal logic (and that is appreciated).

C2. It is not clear what is meant by “out-of-band” in that context in line 187. (As in, e.g. if a normal distribution is used, can it be “out-of-band”?)

C3. (More a discussion point) Regarding that “Hyper-HP selection is not a random process; [...]” (lines 183-185): it could be argued that it is, from some point of view, if we consider that a choice of hyper-HPs by humans or machines follows some distribution, although it is appreciated that it is hard, if possible at all, to practically define such a distribution.

D. Clarification on the meaning of the definition 5 would help: partially because of another clarity point A described above, it is not fully clear what exactly should be guaranteed (e.g., should a whole deception process (from the moment when a demon does not know anything about the problem) be guaranteed; should a “replication” of that process be guaranteed only up to the extent of sampling from omega(L) and randomly selecting G (if any)?; or something else).

E. It would help to clarify what does “defends with a log size K R” mean in line 362.

F. For the empirical validation at the end of section 5, a modified version of an HPO was used. It is not clear why it was necessary to modify it. (Was it e.g. because of computational limitations?)

G. The word “guarantee” is used on line 393: that might feel too strong given assumptions and limitations.

Correctness:

A. I am not sure about lines 257-258 and lines 295-296: if they are read formally, given the definition 5, to the best of my understanding (and there are have been some things that are not fully clear e.g. see clarity points A and D above) and assuming that is the definition that should be applied to interpret them, it is presumably not proven that e.g. “Wilson’s results show [it is possible p in time t]”: I assume it was not checked in a strict way according to the full definition 5 (and I am not sure if it could be proofed formally for this example).

Given the clarity points, the correctness point and the limitations described in another section of the review, although I think this work is very important, sadly I don’t feel comfortable at this point to recommend its acceptance, my apologies. There is a chance though that: (a) I did misunderstand some points (in particular, I have had some questions described in this review regarding the definition 5 and related aspects, and that might be due to my misunderstanding); (b) some points are obvious and they just were not mentioned in the submission; (c) or/and some points are valid and they can be addressed by the camera-ready version submission if the paper is accepted. Given the authors’ rebuttal, to which I am looking forward, there is a chance that the score might be adjusted.

All parts of the review are provided to the best of my understanding and knowledge. Mistakes/misunderstandings in the review are possible. I kindly ask to point me to them, if any, if possible, please.

*

**For the update, please, see my message dated the 2nd of September 2021 (GMT).**
limitations_and_societal_impact: The paper focuses on the execution time in regard to resource budget. The authors highlight that alternatives (such as energy) might be considered. The issue with the time (including e.g. in relation to the theorem 1), and probably up to some extent with some other resource types, is that e.g. parallel computations or more efficient computational techniques might significantly affect the definitions/considerations covered in the paper.

Some other limitations:

A. The paper talks about “a worst-case setting” (line 156) in regard to “a demon”; that means, if I understand correctly, that a demon, in the worst case, can be capable of the worst possible strategy (that also relates to the definition 5). And, we are still interested whether the demon can reliably execute it under time t. It is also mentioned that there is “the easier case of well-intentioned ML researchers” (line 235).

This could be potentially followed-up on in two related ways (I follow the paper here and use here the metaphorical “demon” narrative that is introduced in the paper, but I think it can be also formulated in a more formal way, and the argument would still stand):

A1. A demon might be fine that it does not always succeed. For example, it might try to deceive us in a limited time t, and it is fine that sometimes it won’t deceive us (or someone else). But sometimes, depending e.g. on particular random samples (across a whole HPO process, not just A_lambda runs), it still can sometimes generate deceptive results. If it succeeds though, we are then deceived, even if that deception was not _guaranteed_. That is, a deception attempt might be opportunistic (or at least with probability less than 1), and it still might be very harmful for science. (It also could be argued that a lot of bad actors in the world are probably opportunistic: they are fine to just try to trick, and they are okay if not everyone is tricked, but they might gain a lot when some victims are tricked.)

A2. That argument can be continued further for “well-intentioned ML researchers”. They might accidentally deceive us (and themselves), even though the chance of that is less than 1.

(A continued.) Because of that, it could be argued that:
i. The definition 5 is too strong because we still could be deceived sometimes even if not always (and that could be generally considered as bad). (There might be even cases when a demon might “almost” always deceive us and/or it might do so “almost” always in a reasonable time _t_, but that is already out of the scope of the definition 5.)
ii. There is probably no general way to reliably check that those conditions (i.e. with the probability and the expectation) from the definition 5 are satisfied, in particular for complex models that are optimised as part of HPOs.

B. The paper mentions “is always possible” on line 335 (and also on line 397 without a reference to “t”) and it also mentions “if we cannot easily evaluate whether [...]” in line 337. While it is appreciated that theoretically a t-defended reasoner has been constructed in the section 5, it might be the case that it is just practically (almost) impossible for quite a few scenarios (and potentially theoretically for some tasks, although not clear) to “evaluate whether [...]” (as in line 337).

C. Lines 363-365 talk about what a “good-faith actor can” do, and how that defends us “against adversaries”. However, it is not clear how hard it is to a good-faith actor to produce a log that would satisfy the requirements of the definition 7.

D. (It is probably obvious from the submission:) The theorem 1 depends on “random-search distributions” under considerations to be in a particular relationship. Because of that, somebody else (an “adversary” including a demon) might always argue that their choice of a distribution is as reasonable as (or even better than) than “our” choice.

E. The choice of delta (see e.g. line 380) is another parameter, and it is not exactly clear what delta to use.

F. It is unclear how far generally (in terms of its eventual reliability and strength) the algorithm 1 is from the defended random search EHPO described on page 8.

*

Societal impact: generally this work is expected to bring (huge) positive social impact. The authors have a broader impact section in the appendix. That is all really appreciated.

It might be important to note that (obviously) generally, most likely, any defended and/or guaranteed approach can be subject to some limitations (especially if approximations are used), and that means that results could not, most likely, be fully guaranteed*. (In particular, that might be the case if an adversary is fine to be opportunistic and they are fine to fail many times before they (e.g. accidentally) succeed.) (* - unless e.g. the full hyper-parameter space is enumerated.)
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: Motivated by recent work that empirically show how different conclusions can be made depending on the hyperparameter optimization (HPO) protocol, this paper aims to study the act of drawing conclusions from HPO in a rigorous manner. The authors use modal logic to formalize the idea of deception (where a wrong conclusion is made, or a conclusion is made when there is none to make), while taking uncertainty into account. The idea is that deception happens when two contradicting conclusions can be made given a realistic resource budget (time, compute, etc), so a HPO protocol that is safe to deception should be such that this can never happen. Using this idea, the authors propose an example HPO protocol for random search that is safe against deception.
main_review: Studying the act of making conclusions based on HPO is important because, as the authors mention, it is possible, in the worst case, to game the system and produce results that are more favorable to a particular algorithm (by setting a specific hyperparameter search space or a specific seed), or to draw conclusions from noise. Studying this topic in a practically useful manner is very tricky though, because the selections of hyperparemeters to tune over, the search spaces for the hyperparemters, and also the computational budget to use for tuning, are all arbitrarily chosen.

I think this paper’s approach is interesting and novel, but I’m not sure it adds much to help practically prevent hyperparameter deception, at its current state. The paper provides a good foundation for analysis, and the main result, which is the t-non-deceptiveness axiom, makes intuitive sense. However, the paper provides no guidelines as to how to deal with the more practical issues like setting the search space, and the computational budget. In fact, in the experiments, a specific HPO protocol (two-phsed search) was used leading to some choice of hyperparameter ranges. This choice makes sense, but it still leaves room for deception (for example, if the hyperparameter to test performance mapping has several local optima, and one chooses a suboptimal range that includes the performance degradation point as the authors mentioned, but is still worse than what it could be. This might lead to misleading conclusions). Based on all of this, the paper seems more anecdotal than formal. 

Other comments:
- Sections 3 and 4 seem overly long with too much detail and text. Maybe I’m missing something, but in my understanding, the main result of the paper is section 4.4, but this section doesn’t appear until much later in the paper, which makes the paper a bit hard to read.
- Definition 7 and therefore Algorithm 1 resembles bootstrapping. It’s interesting because Choi et al. uses the exact two-phase tuning protocol and reports results using bootstrapping. 

Update:
After reading the other reviews and authors response, I am still unsure of the exact contributions of this paper (reasons are stated in the replies to the authors' response in the thread below), therefore, I am keeping my score.
limitations_and_societal_impact: See main review above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This is a paper in the areas of  *epistemology* and the *philosophy of science*, with strong implications for empiricism in machine learning research, in particular, the way in which we draw conclusions about algorithms that are sensitive to the hyperparameters. The paper advances a formal system, based on modal logic, for reasoning and drawing conclusions about the experimental results of machine learning algorithms, and demonstrate that the framework naturally suggests defenses with guarantees
against deception.
main_review: ### Originality

The contribution of this paper appears to be original, at least in the context of machine learning research. Something to note: the general premise of this work is not unique to hyperparameter selection in machine learning. The observations and motivations also apply to science in general, e.g. experimental physics, chemistry, biology, and the social sciences such as psychology and economics. Here, the motivation, definitions, and examples are just specialized to machine learning algorithms (e.g. in particular, Definition 2). Therefore, it is questionable how novel and original this work is in the wider context of epistemology and scientific empiricism in general [26, 45], or whether this was just a straightforward specialization of the general framework to the context of ML research.

### Significance

It is debatable how well this paper fits the NeurIPS venue (i.e. a machine learning conference with a strong emphasis on methodological contributions). In many ways, it reads more like an essay or manifesto than it does a technical/scientific paper. Regardless, it does have significant implications for the ML research community. The contribution provides valuable insights and has the potential for impact on the current state of empirical validation in machine learning research, particularly towards the direction of making ML methods more reliable and robust.

Generally speaking, ML algorithms are highly sensitive to the choice of hyperparameters and random seeds. Yet the process itself of drawing conclusions about whether one algorithm outperforms another and gaining reliable knowledge in this regard is largely taken for granted. This has led to a proliferation of published methods that produce underwhelming results when considering a different set of hyperparameters than that tested by the original authors. This particular point is illustrated and argued compellingly on Page 3. Here they provide a poignant example of how one can reach both one conclusion and, at the same time, its logical complement by considering different HPs. This point is intuitively obvious but lacks a rigorous logical framework in which to reason about this phenomenon. This paper seeks to fill this gap. Another important point that is emphasized in this paper: "reproducibility is only part of the story for ensuring reliability. While necessary for guarding against brittle ﬁndings, it is not sufﬁcient. We can replicate results---even statistically signiﬁcant ones---that suggest conclusions that are altogether wrong." This is also an important point that is missing from the discourse in the community.

### Quality and clarity

This paper was of a high level of technical quality and clarity. It was well-written and made for an enjoyable read. I checked the details of the logical entailments and derivations in the main text portions of the supplementary material reasonably carefully.

### General Remarks

- On Definition 2 - this abstraction is fairly general and encompasses most of the typical cases. I understand it cannot be expected to capture everything, but there are a few obvious cases that it misses. An immediate example that comes to mind is that the so-called demon can manipulate not only the hyper-HPs $c \in \mathcal{C}$ and seeds $r \in \mathcal{I}$, but also things like the dataset split. Also, does it fully encompass both inductive and transductive learning settings? 
limitations_and_societal_impact: The broader societal impacts are discussed at length in the appendix but perhaps these should be included in the main text.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper argues that hyperparameter optimization can lead researchers to draw opposite conclusions when comparing different algorithms. In particular, the authors show that this happens not only as a result of the choice of hyperparameters, but also as a result of the hyperparameter search procedure (e.g., including the search space choice). 

To alleviate this concern, the authors propose a novel framework based on modal logic to determine whether a hyperparameter search procedure is "defended" against such deceptions. The argument and proposal is demonstrated through a running example based on work from Wilson et al., showing that according to a user-defined skepticism threshold one could either not draw any conclusion or draw the opposite conclusion from what is claimed in the paper.
main_review: The paper is very well written and easy to follow. In particular, I found the work well-organised and articulated, with helpful informal explanations following formal statements and an accessible introduction to the framework of modal logic.

By pointing out how hyperparameter optimization can lead to conflicting conclusions, the work highlights a key issue underlying a large number of current research works in machine learning. This makes it a highly relevant contribution, which I expect will foster better practice in the ML community. I particularly appreciated that the author focus on the hyperparameter search choices, such as the search space, rather than purely on hyperparameter values or statistical significance. This points out how hyperparameter optimization and statistical significance alone are not sufficient to draw meaningful conclusions when comparing competing algorithms. I believe this is a step further compared to prior work that indicated the possible deception arising from statistical testing or lack of proper hyperparameter search altogether.

The paper goes one step further to propose the first formalisation of this recurrent issue through the lens of modal logic, which is used to reason about how robust a conclusion is based on whether opposite conclusions could be drawn by alternative hyperparameter tuning procedures. The chosen framework is elegant, but I am slightly concerned as the core conclusion of the paper is quite intuitive and I am unsure to what extent the proposed formal treatment helps.

As room for improvement, I would have liked the authors to expand on their empirical section beyond the case study of Wilson et al. The reader would be further convinced of the utility of the framework if more practical examples were given in the main text or at least summarized. For instance, have the authors applied their framework to some prior work where the drawn conclusion was actually robust/defendable against deception? It would be interesting to get a sense for how often the proposed approach would refuse conclusions drawn from previous works and how often it would accept them, based on reasonable skepticism thresholds.

While the authors focused on a broad range of hyper-hyperparameters, I would like the authors to also elaborate on the role of the search space itself. If the hyperparameter search space is large enough, and so are the computational resources, one could argue that a close-to-optimal hyperparameter configuration can be found with good approximation. In such case, two algorithms could be compared with that close-to-optimal hyperparameter choice so that the drawn conclusion (e.g., algorithm A performs better than algorithm B) would be meaningful. I'd like the authors to comment on this setting. Would it be fair to reject the drawn conclusion that algorithm A outperforms algorithm B based on the fact that this does not hold for many alternative poorly configured search spaces? Would it not be a reliable conclusion itself that, under a close-to-optimal hyperparameter setting, one algorithms works better? This is also relevant in practice as the winning algorithm is also likely to be deployed with the optimal hyperparameter configuration, which makes the possible lack of robustness to search space definitions of secondary importance.

Overall, I am inclined towards acceptance as the paper points to highly significant problem, and proposes an approach to counteract it. I am only weakly inclined as the authors could have provided more empirical evidence and discussion for the usefulness of their formalism on a variety of empirical problems, including those where previous conclusions are confirmed. I am ready to change my score if the authors address my questions and concerns in the rebuttal.
limitations_and_societal_impact: The authors have discussed the societal impact of their work.
review_title: null

Meta-review: This paper studies an important issue in machine learning research, namely the possibility of drawing wrong conclusions due to specific hyperparameter choices. While it is common practice to optimize hyperparameters, via random search or more advanced global optimization algorithms, a growing body of work suggests that the search space can be the determinant factor. The authors argue for a logical framework to asses whether deception occurs (that is, contradictory conclusions can be drawn). The authors make theoretical contributions acknowledged by all reviewers. They then apply the framework to deception in the context of random search. However, while the topic is important and the approach novel (or unusual for NeurIPS community), it is unclear what its practical implications would be and how researchers could make use of the framework in more complex settings and how it would help them draw more robust conclusions.
Decision: Accept (Poster)