Hyperparameter Optimization Is Deceiving Us, and How to Stop It
Authors: A. Feder Cooper
Yucheng Lu
Jessica Zosa Forde
Christopher De Sa
Venue: NeurIPS 2021 Poster (2021)
Keywords: hyperparameter optimization
science of machine learning
reproducibility
logic

Abstract: Recent empirical work shows that inconsistent results based on choice of hyperparameter optimization (HPO) configuration are a widespread problem in ML research. When comparing two algorithms J and K searching one subspace can yield the conclusion that J outperforms K, whereas searching another can entail the opposite. In short, the way we choose hyperparameters can deceive us. We provide a theoretical complement to this prior work, arguing that, to avoid such deception, the process of drawing conclusions from HPO should be made more rigorous. We call this process epistemic hyperparameter optimization (EHPO), and put forth a logical framework to capture its semantics and how it can lead to inconsistent conclusions about performance. Our framework enables us to prove EHPO methods that are guaranteed to be defended against deception, given bounded compute time budget t. We demonstrate our framework's utility by proving and empirically validating a defended variant of random search. 

Hyperparameter Optimization Is Deceiving Us, and How to Stop It
A. Feder Cooper" Cornell University af afc78@cornell.ed
Yucheng Lu Corelll University y119677ccoreel1. edu
Jessica Zosa Forde Brown University jforde20cs. brown.
Christopher De Sa Comelll University cdesašcs cornell edu
Abstract
Recent empirical work shows that inconsistent results based on choice of hyper- parameter optimization (HPO) configuration research. When comparing two algorithms J and K,, searching one subspace can yield the conclusion that J outperforms K,, whereas searching another can entail the opposite. In short, the way we choose hyperparameters can deceive us. We provide theoretical complement this prior work, arguing that, avoid such deception, the process drawing conclusions from HPO should be made more rigorous. We call this process epistemic hyperparameter optimization (EHPO), and put forth logical framework to capture its semantics and how it can lead to incon- sistent conclusions about performance. Our framework enables methods that are guaranteed to be defended against deception, given bounded compute time budget We demonstrate our framework's utility by proving and empirically validating a defended variant of random search.
widespread problem in ML
prove EHPO
Introduction
Machine learning can be informally thought of as a double-loop optimization problem. The inner loop is what is typically called training: It learns the parameters some model by running a training algorithm on training set. This is usually done to minimize some training loss function via an algorithm such as stochastic gradient descent (SGD). Both the inner-loop training algorithm and the model are parameterized by a vector of hyperparameters (HPs). Unlike the learned output parameters of MI. model, HPs are inputs provided the learning algorithm that guide the learning process, such as learning rate and network size. The outer-loop optimization problem is to find HPs (from set of allowable HPs) that result a trained model that performs the best in expectation on "fresh" examples drawn from the same source the training set, measured by some loss loss approximation. An algorithm that attempts this task called a hyperparameter optimization (HPO) procedure [12, 20).
From this setup comes the natural question: How do we pick the subspace for the HPO procedure to search over? The HPO search space enormous, suffering from the curse of dimensionality; training. which is also expensive, has to be run for each HP configuration tested. Thus, we have to make hard choices. With limited compute resources, we typically pick a small subspace of possible HPs and perform grid search or random search over that subspace. This involves comparing the empirical performance of the resulting trained models, and then reporting on the model that performs best in
"Corresponding author: https://cacioope..
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

terms of a chosen validation metric [20, 37, 41]. For grid search, the grid points are often manually set to values put forth in now-classic papers as good rules-of-thumb concerning, for example, how to set the learning rate [36, 45, 46, 56]. In other words, how we choose which HPs to test can seem rather ad-hoc. We may have a good rationale in mind, but we often elide the details of that rationale on paper; we choose an HPO configuration without explicitly justifying our choice.
Much recent empirical work has critiqued this practice [7, 11, 16, 48, 50, 53, 62, 65]. The authors examine HPO configuration choices in prior work, and find that those choices can have an outsize impact on convergence, correctness, and generalization. They therefore argue that more attention should be paid to the origins of empirical gains in ML, as it is often difficult to tell whether measured improvements are attributable to training or well-chosen (or lucky) HPs. Yet, this empirical work does not suggest a path forward for formalizing this problem or addressing it theoretically.
To this end, we argue that the process of drawing conclusions using HPO should itself be an object of study. Our contribution is to put forward, to the best of our knowledge, the first theoretically- backed characterization for making trustworthy conclusions about algorithm performance using HPO. problem: When comparing two algorithms,
We model theoretically the following empirically-observe I and K, searching one subspace can pick HPs that yield the conclusion that J outperforms K. whereas searching another can select HPs that entail the opposite result. In short, the way we choose hyperparameters can deceive us us-a a problem that we call hyperparameter deception. We formalize this problem, and prove and empirically validate a defense against it. Importantly, our proven defense does not make any promises about ground boound-truth algorithm performance; rather, it guaranteed to avoid the possibility of drawing inconsistent conclusions about algorithm performance within some bounded HPO time budget f. In summary, we:
Formalize the process of drawing conclusions from HPO (epistemic HPO, Section 3).
Leverage the flexible semantics of modal logic to construct a framework for reasoning rigorously about 1) uncertainty in epistemic HPO, and 2) how this uncertainty can mislead the conclusions drawn by even the most well-intentioned researchers (Section 4).
Exercise our logical framework to demonstrate that naturally suggests defenses with guarantees against being deceived by EHPO, and offer specific, defendeddrandoom-saach EHPO (Section 5).
2 Preliminaries: Problem Intuition and Prevalence in ML Research
Principled HPO methods include grid search [41] and random search [3]. For the former, we perform HPO on a grid of HP-values, constructed by picking set for each HP and taking the Cartesian product. For the latter, the HP-values are randomly sampled from chosen distributions. Both of these HPO algorithms are parameterized themselves: Grid search requires inputting the spacing between different configuration points in the grid, and random search requires distributions from which to sample. We call these HPO-pro Pe0O--oocedur-ingge input values sosperhyperparamette HPO outputs comparable, we also introduce the notion of a log:
(hyper-HPs). To make
Definition 1. A log l records all the choices and measurements made during an HPO run, including the total time T it took to run. It has all necessary information to make the HPO run reproducible.
A log can be thought of as everything needed to produce a table in a research paper: code, random seed, choice of hyper-HPs, information about the learning task, properties of the learning algorithm, all of the observable results. We formalize all of the randomness in HPO in terms of random seed r and a pseudo-rande rreudo-random number generator (PRNG) G. Given a seed, G deterministically produces sequence of pseudo-random numbers: all numbers lie in some set I (typically 64-bit integers), i.c. r E I and PRNG G I - I With this, we can now define HPO formally:
Definition 2. An HPO procedure H is tuple (H,,C.A,A,,,GG, algorithm, C is a set of allowable hyper-HPs (i.e., allowable configurations for H.), A is set of allowable HPs (i.e,, HP sets X), A is a training algorithm (e.g. SGD), M is a model (e.g. VGGI6), G is a PRNG, and X some dataset (usually split into train and validation sets). When run, H. takes as input a hyper-HP configuration e E C and a random seed r E I, then proceeds to run A (on Mx
where H. is a randomized
We provide glossary of all definitions and symbols for reference at the heginning of the Appendix.

---

using G(r) and data' from X) some number of times for different HPs X E A. Finally, H. outputs ruple (X*, .), where X the HP configuration chosen by HPO and E the log documenting the run.
Running H is crucial part of model development. As part of an empirical, scientific procedure, we specify different training algorithms and a learning task, run potentially many HPO passes, and try to make general conclusions about overall algorithm performance. That is, we aim to develop knowledge regarding whether one of the algorithms outperforms the others. However, recent empirical findings indicate that it is actually really challenging pick hyper-HPS that yield reliable knowledge about general algorithm performance. In fact, it is a surprisingly common occurrence to be able to draw inconsistent conclusions based our choice of hyper-HIPs [11, 16, 48, 65].
An example illustrating the possibility of drawing inconsistent conclusions from HPO. As a first step to studying HPO as procedure for developing reliable knowledge, we provide an example of how being inadvertently deceived by HPO is real problem, even excellent research (we give an additional example in the Appendix). We first reproduce Wilson et al. [72], in which the authors trained VGG16 with different optimizers on CIFAR-10 10 (Figure la). This experiment uses grid search, with powers-of-2 grid for the learning rate crossed with the default HPs for Adam. Based on the best-performing HPO per algorithm (a = 1), it reasonable to conclude that non non-adaptive methods (e.g.. SGD) perform better than adaptive ones (e.g., Adam [42]), as the non-adaptive optimizers demonstrate higher test accuracy.
However, this setting of grid search's ' hyper-HPs directly informs this particular conclusion; using different hyper-HPs makes it possible to conclude the opposite. Inspired by Choi et al. [11], we perform grid search over a different subspace, tuning both learning rate and Adam's 's parameter. Our results entail the logically opposite conclusion: Non-adaptive methods do not outperform adaptive ones. Rather, when choosing the HPs that maximize test accuracy, all of the optimizers essentially have equivalent performance (Figure 1b, Appendix). Notably, as we can see from the confidence intervals in Figure 1, satisfying statistical significance is not sufficient to avoid being deceived about comparative algorithm performance [73]. Thus, we will require additional tools aside from statistical tests to reason about this, which we discuss in Sections 4 & 5.
93.0
93.0
92.5
92.5
Accuracy
92.0
Accuracy
92.0
91.5
91.5
91.0
91.0
90.5
90.5
90.0
90.0
SGD
Heavy Ball Adam: (HB) HPO Config.
SCD
Heavy Ball Adam:
(HB) HPO Config. 2
(a)
(b)
Figure 1: Demonstrating the possibility of drawing inconsistent conclusions from HPO (what shorthand hyperparameter deception) when training VGG16 on CIFAR-10. Each box plot represents a log. In (a), we replicate Wilson al. [72] and show the best-performing results: One can reasonably conclude that Adam under-performs non-adaptive methods. In (b), we change the HPO search space for Adam, and similarly show the best-performing results: In contradiction. one can reasonably conclude that Adam performs just as well as non-adaptive methods in terms of test accuracy.
This example not exceptional, or even particularly remarkable, in terms of illustrating the hy- perparameter deception problem. We simply chose it for convenience: The experiment does not require highly-specialized MI. sub-domain expertise to understand it, and it is arguably broadly familiar, as it very well-cited [72]. However, we emphasize that hyperparameter deception is rather common. Additional examples can be found numerous empirical studies across MI. sub- fields [7, 11, 16, 49, 50, 53, 60, 65) (Appendix). This work shows that reported results tend to
3 DDfinition does not preclude cross-valle cross-validation, as can be part of H.. The input dataset X can split various ways, as a function of the random seed r. All code can be found at https: / thub wwt.h.......paaeeeeeeeeeeeeeeeee

---

be impressive for the tested HyP configurations, but that modifying HPO can lead to vastly different performance outcomes that entail contradictory conclusions. More generally, it is possible to develop results that are wrong about performance, or else correct about performance but for the wrong reasons (e.g., by picking "lucky" hyperparameters). Neither of these outcomes constitutes reliable knowledge [27, 47]. As scientists, this is disheartening. We want to have confidence in the conclusions we draw from our experiments. We want to trust that we are deriving reliable knowledge about algorithm performance. In the sections that follow, our aim is to study HPO in this seiialeeknnwwedee sense: We want to develop ways to reason rigorously and confidently about how we derive knowledge from empirical investigations involving HPO.
3 Epistemic Hyperparameter Optimization
Our discussion in Section 2 shows that applying standard HPO methodologies can be deceptive: Our beliefs about algorithm performance can be controlled by happenstance, wishful thinking, or, even worse, potentially by an adversary trying to trick us with a tampered set of HPO logs. This leaves us in position where the "knowledge" we derived may not be knowledge at all-since we could have easily (had circumstancees been different) concluded the opposite. To address this, we propose that the process of drawing conclusions using HPO should itself be an object of study. We formalize this reasoning process, which we call epistemic hyperparameter optimization (EHPO), and we provide an intuition for how EHPO can help us think about the hyperparameter deception problem.
Definition 3. An epistemic hyperparameter optimization procedure (EHPO) is tuple (H, F) where H is set of HPO procedures I1 (Definition 2) and F is a function that maps a set of HPO logs & (Definition 1) to a set of logical formulas P, i.e. F(C) P. An execution of EHPO involves running each H E H some number of times (each run produces log f), and then evaluating F on the logs produced in order to output the conclusions F(C) we draw from all of the HPO runs.
In practice, it is common to run EHPO for two training algorithms, I and K., and to compare their performance to conclude which is better-suited for the task at hand. H contains at least one HPO that runs I and at least one HPO that runs K. The possible conclusions in output P include y "J performs better than 'C", and -p- = "J does not perform better than Λ." Intuitively, EHPO is deceptive whenever it could produce p and also could (if configured differently or due randomness) produce -p. That is, we can be deceived if the EHPO procedure we use to derive knowledge about algorithm performance could entail logically inconsistent results.
Our example in Section 2 is deceptive because using different for H could produce contradictory conclusions. We ran two variants of EHPO (H. The first replicated Wilson et al. [72]'s original H of 3 grid-searches on SGD, HB, and Adam (Figure la), and the second used 3 grid-searches with modified grid search for Adam that also tuned (Figure lb). Each EHPO produced a L with 3 logs. For both, to draw conclusions F picks the best-perfore best-performing HP-config per A and maps them to formulas including "SGD outperforms Adam." From the 3 logs in Figure la, we conclude p: "Non-adaptive optimizers outperform adaptive ones"; from the 3 logs in Figure 1b, we conclude -p: "Non-at Non-addaptvve methods do not outperform adaptive ones." " How can formally reason about EHPO to avoid this possibility of drawing inconsistent conclusions to guard against deceiving ourselves about algorithm performance when running EHPO?
grid searches
Framing an adversary who can deceive us. To begin answering this question, we take inspiration from Descartes' deceptive demon thought experiment (Appendix). We frame the problem in terms of a powerful adversary trying to deceive us-one that can cause us to doubt ourselves and our conclusions. Notably, the demon is not a real adversary: rather, it models worst-case setting of configurations and randomness that are usually set arbitrarily or by happenstance in EHPO.
Imagine an evil demon who is trying to deceive us about the relative performance of different algorithms via running EHPO. At any time, the demon maintains a set L of HPO logs, which it can modify either by running an HPO H E H. with whatever hyper-HP's HPs E C and seed E I it wants (producing new log f, which it adds to L) or by erasing some of the logs in its set. Eventually. it stops and presents us with L. from which we will draw some conclusions using F, i... F(C). The demon's EHPO could deceive us via the conclusions we draw from the set of logs it produces. For example, L may lead us to conclude that one algorithm performs better than another, when in fact picking different set of hyper- HPs could have generated logs that would lead us to conclude differently. We want to be sure that we will not be deceived by any logs the demon could produce. Of

---

course, this intuitive definition is lacking: It is not clear what is meant by could. Our contribution in the sections that follow to pin down a formal, reasonable definition of could in this context, so that we can suggest an EHPO procedure that can defend against such maximally powerful adversary. We intentionally imagine such a powerful adversary because, if we can defend against it, then we will also be defended against weaker or accidental deception.
4 A Logic for Reasoning about EHPO
The informal notion of could established above encompasses numerous sources of uncertainty. There is the time to run EHPO and the choices of random seed, algorithms to compare, HPO procedures, hyper-HPs, and learning task. Then, once we have completed EHPO and have a set of logs, we have to digest those logs into logical formulas from which we base our conclusions. This introduces more uncertainty, as we need to reason about whether we believe those conclusions or not. Our formalization needs to capture all of these sources of uncertainty, and needs to be sufficiently expressive to capture how they could combine to cause us to believe deceptive conclusions. It needs to be expansive enough to handle the common case of well cell-intentioned researcher with limited resources making potentially incorrect conclusions and the rarer, worst case of gaming results.
Why not statistics? As the common toolkit in MI., statistics might seem like the right choice for modeling all this uncertainty. However, statistics is great for reasoning about uncertainty that is quantifiable. For this problem, not all of the sources of uncertainty are easily quantifiable. In particular, it is very difficult to quantify the different hyper-HP possibilities. It is not reasonable to model hyper-HP selection as random process; we do not sample from distribution and, even if we wanted to, is not clear how we would pick the distribution from which to sample. Moreover, saw in our example in Section 2, testing for statistical significance is not sufficient to prevent deception. While the results under consideration may be statistically significant, they can still fail to prevent the possibility of yielding inconsistent conclusions. For this reason, when it comes to deception, statistical significance can even give us false confidence in the conclusions we draw.
Why modal logic? Modal logic is the standard mathematical tool for formalizing reasoning about uncertainty [10, 18] for formalizing the thus far informal notion of what the demon could bring about running EHPO. It is meant precisely for dealing with different types of uncertainty, particularly uncertainty that is difficult to quantify, and has been successfully employed for decades in Al [6, 30, 31J, programming languages [13, 44, 58], and distributed systems [21, 32, 55J. In each of these computer science fields, modal logic's flexible semantics has been indispensable for writing proofs about higher-level specifications with multiple sources of not-precisely quaatiiiiaaiiiibllee lower-level uncertainty. For example, in distributed computing, it lets us write proof' about overall system correctness, abstracting away from the specific den-eeterminism introduced by each lower-level computing process [21]. Analogously, modal logic can capture the uncertainty in EHPO without being prescriptive about particular hyper-HP choices. Our notion of correctness, which we want to reason about and guarantee, is not being deceived. Therefore, while modal logic may be an atypical choice for ML, comes with huge payoff. By constructing the right semanties, we can capture all the sources of uncertainty described above and we can write simple proof's about whether we can be deceived by the EHPO we run. In Section it is this formalization that ultimately enables to naturally suggest a defense against being deceived.
4.1 Introducing our logic: syntax and semantics overview
Modal logic inherits the tools of more-familiar propositional logic and adds two operators: O to represent possibility and D to represent necessity. These operators enable reasoning about possible worlds-a semanties for representing how the world is or could be, making modal logic the natural choice to express the "could" intuition from Section 3. The well-formed formulas & of modal logic are given recursively in Backus- Naur form, where P is any atomic proposition:
P - Φ A OΦ
Op reads, "It is possible that p."; p is true at some possible world, which we could reach (Appendix).
Note that D is syntactic sugar, with Op = -0-p. Similarly, "or" has p V q = -(-p A -9) and "implies" has p g -p q. The axioms of modal logic are as follows:
T Q - QQ
(necessitation).
[Q - R) (DQ - DR)
(distribution).
5

---

where Q and R are any formula, and + Q means Q is theorem of propositional logic. We can now provide the syntax and an intuitive notion of the semantics of our logic for reasoning about deception.
Syntax. Our logic requires an extension of standard modal logic. We need two modal operators to reckon with two overarching modalities: the possible results of the demon running EHPO (0+) and our belief' about conclusions from those results (B), Combining these modalities yields well-formed formulas & where, for any atomic proposition P and any positive real t,
+ = P - db A & Oebb | Bib
Note the EHPO modal operator here is indexed: Or captures "how possible" (0) something is, quantified by the compute capabilities of the demon (1) [6. 18, 33].
Semantics intuition. We suppose that an EHPO user has in mind some atomic propositions (propo- sitions of the background logic unrelated to possibility belief, such "the best-performing log for I has lower loss than the best-performing log for KC") with semantics that are already defined. A and inherit their semantics from ordinary propositional logic, which combine propositions to form formulas. A set of EHPO logs L (Definition 1) can be digested into such logical formulas. That is, we define our semantics using logs L as models over formulas p: C + p. which reads "L models p", means that is true for the set of logs L. We will extend this intuition to give semantics for possibility Or (Section 4.2) and belief B (Section 4.3), culminating in a tool that lets us reason about whether or not EHPO can deceive us by possibly yielding inconsistent conclusions (Section 4.4).
Using our concrete example to ground us. To clarify presentation below, will map semantics to the example from Section 2, providing an informal intuition before formal definitions.
4.2 Expressing the possible outcomes of EHPO using O+
Our formalization for possible EHPO is based on the demon of Section 3. Recall, the demon models a worst-case scenario. In practice, we deal with the easier case of well-intentioned ML researchers. The notion of possibility we define here gives limits on what possible world a demon with bounded EHPO time could reliably bring about. We first define strategy the demon can execute for EHPO:
Definition& 4. A randomized strategy a is function that specifies which action the demon will take, Given L, its current set of logs, (L) gives a distribution over concrete actions, where each action is either 1) running new H with its choice of hyper-HPs and seed r 2) erasing some logs, or 3) returning. We let E denote the set of all such strategies.
The demon we model controls the hyper-HPs and the random seed r, but importantly does not fully control the PRNG G. From the adversary's 's perspective, for a strategy a to be reliable it must succeed regardless of the specific G. Informally, the demon cannot hack the PRNG.
Informally, we now want to execute strategy to bring about a particular outcome p. In Section 2, our good-faith strategy was simple: We ran each H with its own Hyper-HPs and random seed, then returned. The demon is trickier: is adopting a strategy to try to bring about a deceptive outcome. Formally, we model the demon executing strategy a on logs L with PRNG unknown to the demon as follows. Let & denote the distribution over PRNGs G I I in which all number sequence elements are drawn independently and uniformly from I (recall, I is typically the 64-bit integers). First, draw G from G, conditioned on G being consistent with all the runs in L.6 The demon then performs random action drawn from (L), using G as the PRNG when running a new HPO H, and caatuuussupdating the working set of logs as it goes unts the "return" action is chosen.
Using this process, we define what outcomes the demon can reliably bring about (i.c., what is possible, () in the EHPO output logs L by running this random strategy in bounded time t. Informally. Oep means that an adversary could adopt a strategy that is guaranteed to cause the desired outcome p to be the case while taking time at most t expectation. In Section 2, where p is "Non-adaptive methods outperform adaptive ones", Figure la shows Otp. Formally,
Definition 5. Let o [LL] denote the logs output from executing strategy a on logs C. and let To (C) denote the total time spent during execution. (L) is equivalent to the sum of the times T it took
We do not consider adversaries that can directly control how data ordered and submitted to the algorithms under evaluation. This distinction shows that our logical construction non-trivial: We are able to defend against strong adversaries that can game the output EHPO, which is separate from cheating by hacking the PRNG. i.c. All random events recorded in L should agree with the corresponding random numbers produced by G.

---

each HPO procedure H E H executed in strategy to run. Note that both a [[ and To (C) are random variables, as a function of the randomness of selecting G and the actions sampled from (C). For any formula p and any 1 E Ryo, we say L F QtP, i.e. "L models that it is possible p in time 1," if
there exists strategy E, such that [[ F = and B[To st.
We will usually choose to be an upper bound on what is considered reasonable amount of time to run EHPO. It does not make sense for to be unbounded, since this corresponds to the unrealistic setting of having infinite compute time to perform HPO runs. We model our budget in terms of time; however, we could use this setup to reason about other monotonically increasing resource costs, such as energy usage. Our indexed modal logic inherits many axioms of modal logic, with indexes added (Appendix), e.g.:
F (p + a) + (Oep + Qrq)
(necess. + distribution) (transitivity)
- OuP D. Dip
(reflexivity) (symmetry)
Oc0.P OctOP
()(p + (0.p Ozg)
(dist. over A),
To summarize: The demon knows all possible hyper-HPs; it can pick whichever ones it wants to run EHPO within a bounded time budget to realize the outcome p wants. That is, if with some probability the demon can deceive us in some amount of time, then the demon can reliably deceive us with any larger time budget: If the demon fails to produce a deceptive result, can use the strategy of just re- re-running until it yields the result it desires. Since Or models the worst-case all- all-powerful demon, can also model any weaker EHPO user with time budget t.
4.3 Expressing how we draw conclusions using 1
We employ the modal operator B from the logic of belief to model ourselves as an observer who believes in the truth of the conclusions drawn from running EHPO. Bp reads "It is concluded that p." For example, when comparing the performance of two algorithms for a task, p could be "I is better than K"" and thus By would be understood as, "It concluded that J is better than A.."
We model ourselves as a consistent Type reasoner [67]. Informally, this means we believe all propositional tautologies (necessitation), our belief distributes over implication (distribution), and we do not derive contradictions (consistency). We do not require completeness: We allow the possibility of not concluding anything about p (i.c., neither Bp nor B-p). Formally, for any formulas and g,
+ p Bp (necess.); B(p 9) (Bp Bq)
(dist.); -(Bp A B B-p) (consistency).
To understand our belief semantics, recall that EHPO includes function F, which maps set of output logs L to our conclusions (i.e., F(C) = P is our set of conclusions). Informally, when our conclusion set F(C) contains a formula p. we say the set of logs L models our belief 1 in that formula In Section 2, the logs of Figure la model Bp and the logs of Figure 1b model B-p. Formally, Definition 6. For any formula p. we say - Bp. "L models our belief in p" i p E F(C).
Note we constrain what can output. For a reasonable notion of belief, must model the consistent Type reasoner axioms above. Otherwise, deception aside, F is unreasonable way to draw conclusions, since is not even compatible with our belicf logic.
4.4 Expressing hy perraarrrere deception
So far we have defined the semantics of our two separate modal operators, Or and B. We now begin to reveal the benefit of using modal logic for our formalization. These operators can interact formally express what we informally illustrated in Section 2: notion of hyperparameter deception. It is well-known result that we can combine modal logics [61] (Appendix). We so to deñine an axiom that, if satisfied, guarantees EHPO will not be able to deceive us. For any formula
(O.Bp A O,B-p)
(t-non-deceptive).
Informally, running example can be considered a proof by exhibition: It violates this axiom because Figure la's logs model Bp and Figure lb's s logs model O.B-p. That is, G,Bp A 4BB-p using grid search for this task.
B is syntactically analogous to the I modal operator in standard modal logic [35, 63, 69] (Appendix).
7

---

For the warst-case, E-non-deceptiveness expresses the following: If there exists a strategy o by which the demon could get us conclude p in expected time, then there can exist no t-time strategy by which the demon could have gotten us to believe -p. To make this concrete, suppose our t-non-deceptive axiom holds for an EHPO method that results in p. Intuitively, given a maximum reasonable time budget t, if there is no adversary that can consistently control whether we believe p or its negation when running that EHPO, then the EHPO is defended against deception. Conversely, an adversary could consistently control our conclusions, then the EHPO is potentially gameable. That is, if our t-non-deceptive axiom does not hold (i.e., we can be deceived, O,By A O,B pp), then even if we conclude p after running EHPO, cannot claim to know p. Our belief as to the truth-value of p could be under the complete control of an adversary- or just a result of happenstance.
To summarize: An EHPO is t-non- nonn-decepiive if it satisfies all of the axioms above. Our example in Section 2 is 1-deceptive because the axioms do not hold. The semantics of these axioms capture all of the possible uncertainty from the process of drawing conclusions from EHPO-and and how that uncertainty can combine to cause us to believe I-deceptive conclusions.
5 Constructing Defended EHPO
Now that we have formal notion of what it means for EHPO to be (non)-deceptive, we can write proofs about what it means for an EHPO method to be guaranteed to be deception-free. Importantly, these proofs will increase our confidence that our conclusions from EHPO are not due to the happenstance of picking a particular set of hyper-HPs.
To talk about defenses, we need to understand what it means to construct a "defended reasoner." In other words, for an EHPO FF. we need F to yield conclusions that we can defend against deception. Recall from Definition 6 that logs L model our belief in formula p. i.e. C - Bp = p F(C). With this in mind, we begin by supposing we have a naive EHPO (H, Fa)) featuring a naive reasoner B3 with corresponding belief function F,, We want to construct a new "defended reasoner" B. that has a "skeptical" belief function F.. F. should weaken the conclusions of J, (i.e., (.)) F.(C) for any L) and result in an EHPO (H,F.) that is guaranteed to be f-non-deceptive. In other words, defended reasoner B, never concludes more than the naive reasoner B,. Informally, straightforward way to do this is to have B. conclude p only if both the naive B, would have concluded p. and it is impossible for an adversary to get B, to conclude -p in time t. Formally, construct B, such that for any p. B.p = B.P A BB p (1).
Directly from our axioms (Section 4), we can now prove B. defended. We will suppose it is possible for B, to be deceived, demonstrate contradiction, and thereby guarantee that B, is t-non-deceptive. Suppose B, can be deceived in time i.c. O, O.B. p is True. Starting with the left, O,
Rule
O.B.p = 0o. (B.p A -0.B.
Applying O, to the definition of B.p (1)
Oe (-0rBB
Reducing conjunction to either of its terms: (a A b) - b Symmetry; dropping all but the right- most operator: (c(Ora) + Osa
-Q.B.-p
We then pause to apply our axioms to the right side of the conjunction, O.B.-p:
Rule
O.B.-p = 4e -..Bpp)
Applying O. to the definition of B.-p (1)
Q.B. Q.B.p
Distributing O2 over A: 0z(a A b) + (O.a A 0.6)
+ O.B.-P
Reducing a conjunction to either its terms: (a b) + a
We now bring both sides of the conjunction back together: The eight-hand side is of the form -a Aa, which must be False. This contradiets our initial assumption that B, is t-deceptive (i.e., O. A O,B. - is True). Therefore, B, t-non-deceptive.
-O,B, Or
This example illustrates the power of our choice of formalization. In just a few lines of simple logic, we can validate defenses against deception. This analysis shows that a t-defended reasoner B, is always possible, and it does so without needing to refer to the particular underlying semantics of an
8

---

EHPO. However, we intend this example to only be illustrative, as it may not be practical to compute B. as defined (1) if we cannot easily evaluate whether -p. We next suggest a concrete EHPO with defended B., and show how deception can be avoided in our Section 2 example by using this EHPO instead of grid search.
A defended random search EHPO. Random search takes two hyper-HPs, a distribution over the HP space and a number of trials K E N run. HPO consists of K independent trials of training algorithms ANz,... Axx where the HPs A are independently drawn from f4, taking expected time proportional to K. When drawing conclusions, we usually look the "best" run for each algorithm. For simplicity, we suppose there is only one algorithm. A. We bound how much the choice of hyper- can affect the HPs, and define defended EHPO based on variant of random search.
Definition 7. Suppose that we are given naive EHPO procedure Ff)). in which is random search and is the only HPO in our EHPO. and Fn is "naive" function associated with a naive reasoner By. For any K, R E N, we define the "(K, RY-defended" belief function F. for skeptical procedure. First, F. only makes conclusion set
reasoner B, as the following conclusionddravii P. from single log with K R trials; otherwise, it concludes nothing, outputting 0. Second, F. splits the single i into R. logs (2,22..... LR. each containing K independent sesendden--anndom candom-seard trials. Finally, F. outputs the intersection of what the naive reasoner would have output on each log E,,
F.(((T)
Equivalently, (0) F B.p only if (c.) + BaP for all i.
Informally, to draw a conclusion using this EHPO, B. splits a random-search--rial log of size K R into R groups of K-trial logs, passing each K-trial log to one of an ensemble of naive reasoners Bn. B. only concludes p if all R naive reasoners unanimously agree on p. We can guarantee this EHPO to be I-non-deceptive by assuming a bound on how much the hyper-HPs can affect the HPs.
Theorem 1. Suppose that the set of allowable hyper-HIPs C of H is constrained, such that any two allowable random-seurch distributions μ and v have diiverreeeeeeeeeeee at most constant, i.e. D Do (plli) S 7- The (K, R) defended random-search EHPO of Definition 7 is guaranteed to be = -
t-non- -non-deceptive if we set R 2 /tcxp(yK)/K-
We prove Theorem 1 in the Appendix. This result shows that our defense is actually a defense, and moreover it defends with log size K R-and compute requirement for good-faith EHPO-that scales sublinearly in f. A good-faith actor can, in sublinear-in-t time, produce a log (of length K I?) that will allow our t-non- deceppeee reasoner to reach conclusions. This means that defend against adversaries with much larger compute budgets than are expected from good-faith actors.
Validating our defense empirically and selecting hyper-HPs. Any defense ultimately depends on the hyper-HPs it uses. Thus, we should have a reasonable belief that choosing differently would not have led an opposite conclusion. We therefore run a two-phased search [11, 34, 59], repeating our VGG16 1- experiment from Section 2. First, we run a coarse- grained, dynamic protocol to find reasonable hyper-HPs for Adam's E; second, we use those hyper-HPs to run our defended random search. We start with a distribution to search over e, and note that the performance best on the high end. We change the hyper-HPs, shifting the distribution until Adam's 's performance starts to degrade, and use the resulting hyper-HPs (e [1010, 1 to run our defense (Appendix).
We now run a modified version of our defended EHPO in Definition 7, described in Algorithm 1, with K * R 600 (200 logs for each optimizer). Using budget of M 10000 iterations. we subsample = 11 logs and pass them to an ensemble of α naive reasoners B.. We use logs, relaxing the requirement of using all K * R logs in Definition 7, for efficiency. Each iteration m concludes the majority conclusion of the k-sized B, ensemble. This is why we set k to an odd number-te to avoid ties. B, draws conclusions based on the results of the M-majority conclusions. That is, we further relax the requirements of Definition 7: Instead of requiring unanimity, B, only requires agreement on the ruth-value of p for a fractional subset of M. We set this fraction using parameter ó E [0, 1], where 8 controls how skeptical our defended reasoner B, is (lower ó corresponding to more skepticism). B, concludes p when at least (1 - 6) of our M subsampled runs concluded p. When this threshold is not met, B, remains skeptical and concludes nothing. We summarize our final results in Table 1, and
This is not generally allowable. F. can do this because random-search logs contain interchangeable trials.

---

provide complete results in the Appendix. Given how similar the optimizers all perform on this task (similar Figure 1), being more skeptical increases the likelihood that we do not conclude anything.
Algorithm Defense with Random Search
Results from repeating our Sec- tion 2 experiment, using Algorithm in- stead of grid search. p = Wyon-adaptive optimizers (SGD and HB) perform better than the adaptive optimizer Adam".
Table 1:
Require:
Set of K R random-search logs (C defense subsampling budget M,
criterion constant 8, subsample size K.
1: for m = 1,... .M do
2: Subsample x logs: {Li) ~ (R
3: Obtain conclusions {P:} from (Li)
p
p
1 - 8 Conclude
4: Obtain output conclusion for m.
((m) Majority
SGD
0.75
wp Nothing
5: end for
vs.
0.213
0.788
0.8
6: if 3p s.t. 2 (1 - 8)M of (p(m) p conclude
Adam
0.9
Nothing
then
0.75
7: Conclude p.
HB
8: else
vs. Adam
0.168
0.832
0.8
p
9:
Conclude nothing.
0.9
Nothing
10: end if
6 Conclusion and Practical Takeaways
Much recent empirical work illustrates that it is easy to draw inconsistent conclusions from HPO [7, 11, 16, 49, 50, 53, 60, 65]. We call this problem hyperparameter deception and, to derive a defense, argue that the process of drawing conclusions using HPO should itself be an object of study. Taking inspiration from Descartes' demon, we formalize a logic for studying an epistemic HPO procedure. The demon can run any number of reproducible HPO passes try to get to believe particular notion about algorithm performance. Our formalization enables us to not believe deceptive notions: It naturally suggests how to guarantee that EHPO is defended against deception. We offer recommendations to avoid hyperparameter deception in practice (we expand on this in the Appendix):
Researchers should construct their own notion of skepticism B., appropriate to their specific task. There is no one-size-fits fits-all defense solution. Our results are broad insights about defended EHPO: A defended EHPO is always possible, but finding an efficient one will depend the task.
Researchers should make explicit how they choose hyper-HPs. What is reasonable is ultimately function of what the ML community accepts. Being explicit, rather than eliding hyper-HP HP choices, is essential for helping decide what is reasonable. As heuristic, we recommend setting hyper-HP's such that they include HPs for which the optimizers' performance starts to degrade, as we do above.
Avoiding hyperparameter deception is just as important reproducibility. We have shown that reproducibility [7, 29, 34, 57, 64) is only part of the story for ensuring reliability. While necessary for guarding against brittle findings, it is not sufficient. We replicate results- even statistically significant ones that suggest conclusions that are altogether wrong.
More generally, our work is call to researchers to reason more rigorously about their beliefs concerning algorithm performance. In relation EHPO, this akin to challenging researchers to reify their notion of B-to justify their belief in their conclusions from the HPO. Such epistemic rigor concerning drawing conclusions from empirical studies has a long history in more mature branches of science and computing, including evolutionary biology [28]. statistics [25, 26], programming languages [54], and computer systems [23] (Appendix). We believe that applying similar rigor will contribute significantly to the ongoing effort of making ML more robust and reliable.
Acknowledgements
A. Feder Cooper is supported by the Artificial Intelligence Policy and Practice initiative at Cornell University, the Digital Life Initiative at Cornell Tech, and the John D. and Catherine T. MacArthur Foundation. Jessica Zosa Forde is supported by ONR PERISCOPE MURI N00014-17-1- 2699. We would additionally like to thank the following individuals for feedback on earlier ideas, drafts, and
10

---

iterations of this work: Prof. Rediet Abebe, Harry Auster, Prof. Solon Barocas, Jerry Chee, Prof. Jonathan Frankle, Dr. Jack Goetz, Prof. Hoda Heidari, Kweku Kwegyir-Aggrey Prof. Karen Levy. Prof. Helen Nissenbaum, and Prof. Gili Vidan. We also thank Meghan Witherow for her whimsical interpretation of Descartes' evil demon, which we include in the Appendix.
References
[1] Mark Van Atten. On Brouwer. Cengage Learning, 2004.
[2] Alexandru Baltag and Sonja Smets. Probabilistic dynamic belief revision. Synthese, 165(2): 179-202, 2008.
[3] James Bergstra and Yoshua Bengio. Random Search for Mach. Learn. Res., 13:281-300 February 2012. ISSN 1532-4435.
Optimization.
[4] James S. Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for Hyper- Parameter Optimization. In J. Shawe- Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 2546-2554. Curran Associates, Inc., 2011.
[5] Guram Bezhanishvili and Wesley H. Holliday. A semantic hierarchy for intuitionistic logic. Indagationes Mathematicue, 30(3):403- 469, 2019. ISSN 0019-3577.
[6] Patrick Blackburn, Johan A. K. van Benthem, and Frank Wolter. Handbook of Modal Logic, volume 3. Elsevier Science Inc., USA, 2006. ISBN 0444516905.
[7] Xavier Bouthillier, César Laurent, and Pascal Vincent. Unreproducible Research Reproducible. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 725-734. PMLR, 09-15 Jun 2019.
[8] Roberto Calandra, Ignasi Clavera Gilaberte, Frank Hutter, Joaquin Vanschoren, and Jane Wang. Meta-leaming, Meta-Learning Workshop at NeurIPS 2020, 2020.
[9] Jimena Canales. Bedeviled: A Shadow History of Demons in Science. Princeton University Press, Princeton, NJ, USA, 2020.
[10] Brian F. Chellas. Modal Logic An Introduction. Cambridge University Press, 1980.
[11] Dami Choi, Christopher J. Shallue, Zachary Nado, Jaehoon Lee, Chris J. Maddison, and George E. Dahl. On Empirical Comparisons of Optimizers for Deep Learning, 2019.
[12] Mare Claesen and Bart De Moor. Hyperparameter Search in Machine Learning, 2015.
[13] E. M. Clarke, F. A. Emerson, and A. P. Sistla. Automatic Verification of Finite-State Concurmet Systems Using Temporal Logic Specifications. ACM Trans. Program. Lang. Syst., 8(2):244-263 263, April 1986. ISSN 01 0164-09.5
[14] A. Feder Cooper and Ellen Abrams. Emergent Unfairesss in Algorithmic Aacuracy Trade-Off Research. In Artificial Intelligence, Ethics, and Society (AIES), 2021.
[15] René Descartes. Discourse on Method and Meditations on First Philosophy. Hackett Publishing Company, Inc., Translator Donald Cress, 4th edition, 1998. Meditation One: Concerning Those Things That Can Be Called into Doubt.
[16] Jesse Dodge, Suchin Gururangan, Dallas Card, Roy Schwartz, and Noah A. Smith. Show Your Work: Improved Reporting of Experimental Results. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNI.--JCCNIP)) pages 2185-2194, Hong Kong, China, November 2019, Association for Computational Linguistics.
[17] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20:1-21, 2018.

---

[18] E. Allen Emerson. Temporal and Modal Logic, page 995- 1072. MIT Press, Cambridge, MA, USA, 1991. ISBN 0444880747.
[19] Eduardo Fermé and Sven Ove Hansson. AGM 25 Years: Twenty-Five Years of Research in Belief Change. Journal of Philosophical Logic, 40:295-333 April 2011.
[20] Matthias Feurer and Frank Hutter. Hyperparameter Optimization. Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren, editors, Automated Machine Learning: Methods, Systems, Challenges, pages 3-33. Springer International Publishing. 2019.
[21] Michael J. Fischer and Lenore Zuck. Reasoning about uncertainty in fault-tolerant distributed systems. In M. Joseph, editor, Formal Techniques in Real-Time and Fault-Toleran Systems, pages 142-158, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.
[22] Jessica Zosa Forde, A. Feder Cooper, Kweku Kwegyir-Agget Chris De Sa, and Michael Littman. Model Selection's Disparate Impact in Real-World Deep Learning Applications, 2021. ICML 2021 Science of Deep Learning Workshop.
[23] Batya Friedman and Helen Nissenbaum. Bias in Computer Systems. ACM Trans. Inf. Syst., 14 0):330-347, July 1996. ISSN 1046-8188.
[24] James Garson. Modal Logic. In The Stanford Encyclopedia of Philosophy, Fall 2018 Edition, Edward N. Zalta (ed.), 2018
[25] A. Gelman and Eric Loken. The garden of forking paths: Why multiple comparisons can be a problem, even when there is no "fishing expedition" "p-hacking" and the research hypothesis was posited ahead of time, 2019.
[26] Andrew Gelman and Eric Loken. The statistical crisis in science: data-dependent analysis paths"-explaing "garden of forking paths" exxlaans why many statistically significant comparisons don't 't hold up. American Scientist, 102(6))460-466, 2014.
[27] Edmund L. Gettier. Is Justified True Belief Knowledge? Analysis, 23(6):121-123, 06 1963.
[28] Stephen Jay Gould. The Mismeasure of Man. Norton, New York, 1981.
[29] Odd Erik Gundersen and Sigbjørn Kjensmo. State of the Art: Reproducibility in Artificial Intelligence. In AAAI, 2018.
[30] Joseph Halpern. Reasoning about Uncertainty. The MIT Press, 2 edition, 2017.
[31] Joseph Y. Halpern and Y. Shoham. A propositional modal logic of time intervals. In Journal of the ACM, 1991.
[32] Chris Hawblitzel, Jon Howell, Manos Kapritsos, Jacob Lorch, Bryan Parno, Michael L. Roberts, Srinath Setty, and Brian Zill. IronFleet: Proving Practical Distributed Systems Correct. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP '15, page 1-17, New York, USA, 2015. Association for Computing Machinery. ISBN 9781450338349.
[33] Aviad Heifeitz and Philippe Mongin. The Modal Logic of Probability. In Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge, pages 175-185, July 1998.
[34] Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep Reinforcement Learning that Matters. In Thirty-Second AAAI Conference On Artificial Intelligence, 2018
[35] Jaakko Hintikka. Knowledge and Belief. Comell University Press, 1962.
[36] Geoffrey E. Hinton. A Practical Guide to Training Restricted Boltzmann Machines. In Grégoire Montavon, Geneviève B. Orr, and Klaus-Robert Müller, editors, Neural Newworks: Tricks of the Trade: Second Edition, pages 599-619. Springer Berlin Heidelberg, Berlin, Heidelberg. 2012.
[37] Chihwei Hsu, Chihchung Chang, and Chihlen Lin. A Practical Guide Support Vector Classification, November 2003.
12

---

[38] Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren, editors. Automated Machine Learning: Methods, Systems, Challenges. Springer, 2018. In press, available at http://aurr org/ book.
[39] Frank Hutter, Joaquin Vanschoren, Marius Lindauer, Charles Weill, Katharina Eggensperger, and Matthias Feurer. Ieml workshop on automated machine learning. AutoML Workshop at ICML, 2020, 2020.
[40] Charles Isbell. You Can't Escape Hyperparameters and Latent Variables: Machine Learning as Software Engineering Enterprise. NeurlPS Keynote, 2020.
[41] George H. John. cooss-Validated C4.5: Using Error Estimation for Automatic Parameter Selection. Technical report, Stanford University, Stanford, CA, USA, 1994.
[42] Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. International Conference on Learning Representations, 12 2014.
[43] Barteld P. Koou. Probabilistic Dynamic Epistemic Logic. Journal of Logic Language and Information, 12(4):381 148.3888.08... 2003.
[44] Leslie Lamport. "sometime" is Sometimes "Not Never": On the Temporal Logic of Programs. In Proceedings of the 7th ACM SIGPLAN-SIGACE Symposium on Principles of Programming Languages, POPL '80. page 174-185, New York, NY, USA, 1980. Association for Computing Machinery. ISBN 0897910117, 17. doi: 10. 46015644444665566666
[45] Hugo Larochelle, Dumitru Erhan, Aaron Courville, James Bergstra, and Yoshua Bengio. An Empirical Evaluation of Deep Architectures on Problems with Many factors of Variation. In Pro- ceedings of the 24th International Conference on Machine Learning. ICML '07, page 473-484 New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595937933.
[46] Yann LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller. Efficient BackProp. In Neural Networks: Tricks of the Trade, This Book is an Outgrowth of a 1996 NIPS Workshop, page 9-50, Berlin, Heidelberg. 1998. Springer-Verlag. ISBN 3540653112.
[47] Keith Lehrer. The Gettier Problem and the Analysis of Knowledge. In George Sotiros Pappas, editor, Justification and Knowledge: New Studies in Epistemology, pages 65-78. Springer Netherlands, Dordrecht, 1979.
[48] Zachary C. Lipton and Jacob Steinhardt. Troubling Trends in Machine Learning Scholarship. ACM Queue, 2018
[49] Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are GANs Created Equal? Large-Scale Study. In S Bengio, Wallach, Larochelle, K Grauman, N (eea-BBiancii and R Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 700-709. Curran Associates, Inc., 2018
[50] Gábor Melis, Chris Dyer, and Phil Blunsom. On the State of the At of Evaluation in Neural Language models. In International Conference on Learning Representations, 2018.
[51] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv:1609.07888 2016.
[52] Tom M. Mitchell. The Need for Biases in Learning Generalizations. Technical report, Rut- gers University, New Brunswick, NJ, 1980.
cs. cmu, edu/ /
NeedForBBas__190. pdf.
[53] Kevin Musgrave, Serge Belongie, and Ser-Nam Lim. A Metric Learning Reality Check, 2020.
[54]
Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter F. Sweeney. Producing Wrong Data without Doing Anything Obviously Wrong! In Proceedings of the 14th International Conference Architectural Support for Programming Languages and Operating Systems, AS- PLOS XIV, page 265-276, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781 605584065..
13

---

[55] Susan Owicki and Leslie Lamport. Proving Liveness Properties of Concurrent Programs. ACM Trans. Program, Lang. Syst. 4(3): 495, July 1982. ISSN 0164-0925. doi: 10.1145/357172. 357178.
[56] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel. Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, and et al. Scikit-Learn: Machine Learning in Python. J. Mach. Learn. Res., 12:2825-2830, November 2011. ISSN 1532-4435.
[57] Joelle Pineau. The Machine Leamiing Reproducibility Checklist, March 2019. https://wwr ca mogill. ca/" jpppaaa///apppoocccoooyyyyyyeeaa pdf.
[58] Amir Pnueli. The Temporal Logic of Programs. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS '77, page 16-57, USA, 1977. IEEE Computer Society.
[59] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling. In /CLR, February 2018.
[60] Schneider, L. Balles, and P. Hennig. DeepOBS: Deep Learning Optimizer Benchmark Suite. In 7th International Conference on Learning Representations (ICLR). ICLR, May 2019.
[61] Dana Scott. Advice on modal logic. In Karel Lambert, editor, Philosophical Problems in Logic: Some Recent Developments, pages 143-173. Springer Netherlands, Dordrecht, 1970.
[62] D. Sculley, Jasper Snoek, Alex Wiltschko, and Ali Rahimi. Winner's Curse? On Pace, Progress, and Empirical Rigor. In ICLR 2018 Workshop, February 2018.
[63] Krister Segerberg. Two Traditions in the Logic of Belief:
Bringing them Together. In Hans Jür- gen Ohlbach and Uwe Reyle, editors, Logic, Language and Reasoning: Essay Honour of Dov Gabbay, pages 135- 148. Springer Science+Busines, Media, Dordrecht, Netherlands, 1999.
[64] K Sinha, Pineau, J Forde, R N Ke, and H Larochelle. NeurIPS 2019 Reproducibility Challenge. ReScience, 6(2), 2020.
[65] Prabhu Teja Sivaprasad, Florian Mai, Thijs Vogels, Martin Jaggi, and François Fleuret. Op- timizer Benchmarking Needs to Account for Hyperparameter Tuning. Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9036-9045. PMLR, 13-18 Jul 2020.
[66] Brian Cantwell Smith. The Limits of Correctness. SIGCAS Computer and Society, page 18-26, January 1985. ISSN 0095-2737. doi: 10. 10.1145//79488.3795522 URL https://doi. /ttp::///oooooo/.....1 1145/379486. 379512. 375559939883..
[67] Raymond M. Smullyan. Logicians Who Reason about Themselves. In Proceedings of the 1986 Conference on Theoretical Aspects of Reasoning about Knowledge, TARK '86, page 341-352, San Francisco, CA, USA, 1986. Morgan Kaufmann Publishers Inc. ISBN 093461 0944613049,
[68] Richmond H. Thomason. Combinations of tense and modality. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic: Volume II: Extensions of Classical Logic, pages 135-165. Springer Netherlands, Dordrecht, 1984. ISBN 978-94-0009-2559-0
[69] Johan van Benthem. Epistemic Logic and Epistemology: The State of Their Affairs. Philosoph- ical Studies: An International Journal for Philosophy in the Analytic Tradition, 128(1):49-74 2006.
[70] Johan van Benthem. Dynamic logic for belief revision. Journal of Applied Non-Classical Logics, 17(2):129-155, 2007.
[71] Johan van Benthem, Jelle Gerbrandy, and Barteld P. Kooi. Dynamic Update with Probabilities. Stud Logica, 93(1):67-96, 2009.
14

---

[72] Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The Marginal Value of Adaptive Gradient Methods in Machine Learning, I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 4148-4155 Curran Associates, Inc., 2017.
[73] Cristobal Young. Model Uncertainty and the Crisis Science. Socius, 4:2378023117737206
2018. doi: 10.11772578023317777700
[74] Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng-Lin Liu. Practical block-wise neural network architecture generation. CVPR, 2018.
[75] Barret Zoph and Quoe V. Le, Neural architecture search with reinforcement learning. In ICLR, 2017.
15


Reviews:
[{"review_id": "hBuBk9Up8Eq", "reviewer": "Reviewer_6ydM", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a very important submission. Its significance is huge. Thanks extremely much to the authors for their work.\n\nThe paper is written generally well.\n\nThe prior work is described and scoped well. Based on that, the idea and approach seem to be novel.\n\nNote 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).\n\nClarity:\n\nA. 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)).\n\nB. 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?\n\nC1. (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).\n\nC2. 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”?)\n\nC3. (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.\n\nD. 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).\n\nE. It would help to clarify what does “defends with a log size K R” mean in line 362.\n\nF. 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?)\n\nG. The word “guarantee” is used on line 393: that might feel too strong given assumptions and limitations.\n\nCorrectness:\n\nA. 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).\n\nGiven 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.\n\nAll 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.\n\n*\n\n**For the update, please, see my message dated the 2nd of September 2021 (GMT).**", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nSome other limitations:\n\nA. 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).\n\nThis 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):\n\nA1. 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.)\n\nA2. 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.\n\n(A continued.) Because of that, it could be argued that:\ni. 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.)\nii. 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.\n\nB. 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).\n\nC. 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.\n\nD. (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.\n\nE. The choice of delta (see e.g. line 380) is another parameter, and it is not exactly clear what delta to use.\n\nF. 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.\n\n*\n\nSocietal 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.\n\nIt 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.)\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I have not tracked time. I generally conduct a review in a few sub-iterations, to be able to reflect (between them) on a submission/material under review for some time."}, "extra_text": {}}, {"review_id": "aX-X2kUSeZN", "reviewer": "Reviewer_n65K", "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). \n\nTo 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nBy 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.\n\nThe 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.\n\nAs 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.\n\nWhile 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.\n\nOverall, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9vVUdg3pKAa", "reviewer": "Reviewer_31vJ", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nI 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. \n\nOther comments:\n- 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.\n- 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. \n\nUpdate:\nAfter 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "2MmKo5mMW_B", "reviewer": "Reviewer_oWpG", "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\nagainst deception.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality\n\nThe 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.\n\n### Significance\n\nIt 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.\n\nGenerally 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.\n\n### Quality and clarity\n\nThis 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.\n\n### General Remarks\n\n- 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? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

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)