T H E R I G H T C A L L F O R S O F T WA R E B E N C H M A R K I N G •
Consistent Decisions in Stateful Environments Gábor Melis [email protected]
arXiv:2606.17261v1 [cs.PF] 15 Jun 2026
Google DeepMind
abstract
ging network conditions, co-hosting and the opaqueness of cloud services all conspire against reliable results. Thus, our ability to detect small performance differences is constrained, yet precisely that sensitivity is required for the effective development and tuning of mature compilers, machine learning frameworks and database systems. The present paper studies the challenges inherent to benchmarking programs in stateful environments, assuming the provision of a benchmark suite, whose design, while undeniably important, lies beyond the intended scope. We shall examine the inadequate theoretical underpinnings of prevailing methods when applied in such environments and propose new approaches founded upon more tenable postulates. Our contributions are threefold: 1. Formalize benchmarking as a decision problem concerning the fastest program in a given set under a general, albeit intractable, measurement model (§3); 2. Call for software benchmarking to focus on estimating performance deltas from the same experiment instead of comparing absolute performance numbers across experiments (§4 and §5); 3. Propose experiment designs that guide the selection of programs to call to ensure both asymptotically correct decisions (in the limit of infinitely many measurements) and finite-sample guarantees (§6–7). The goal of this work is to accelerate the development of performance-sensitive software.
In the perpetual pursuit of performance, modern computing systems rely ever more on stateful mechanisms to accommodate the dynamics of workloads and physical environments, bolstering efficiency but confounding benchmarking and thereby the optimization of software. Indeed, by their nature, adaptive mechanisms introduce temporal dependencies between measurements and render naive estimators of individual program performance biased. Observing that rectifying such biases necessitates speculative assumptions about system dynamics, we call for prioritizing performance differentials over absolute measures and formalize software benchmarking as the decision problem of identifying the fastest program, for which relative knowledge suffices. To this end, we propose simple experiment designs admitting consistent estimators of contrasts, whereby program-specific biases cancel under tenable assumptions. These designs asymptotically yield the correct decision and afford a robust methodology for finite-budget benchmarking in stateful environments, bearing broad implications for the development of performance-sensitive software. 1 introduction Software benchmarking [Kuhn, 1997, Tichy, 1998, Sim et al., 2003, Alcocer and Bergel, 2015, Hasselbring, 2021] is at the heart of performance optimization: how could we guide this process if not by measurement? Therein lies the fundamental importance of benchmarking, not unlike the experiments that ground natural sciences in physical reality. Like them, benchmarking must distinguish cause from effect, but on modern computers we face an ever-changing set of strong confounders in the form of stateful processes in hardware controllers, the kernel, the myriad of daemons and other concurrently running programs, defying reliable control. Beyond single computers, this issue is compounded: chan-
2 conventions Standard sets are denoted with blackboard letters (e.g. ℝ), other sets with calligraphic (F, U ), constants with uppercase Roman (M), scalars with lowercase italic ( 𝑓, 𝑠), and vectors with boldface italic (𝒖). Random variables (henceforth rvs, or rv in singular) are denoted with uppercase italic ( 𝐹, 𝑆) if scalar-valued, or in boldface (𝑼 ) if vector-valued. Where realizations of a rv are denoted by a Greek lowercase letter
1
𝐹1 𝑇1 𝑈1
𝐹4
𝐹3
𝐹2
𝑈2
𝑇4
𝑇3
𝑇2 𝑈3
𝑈4
...
𝑈5
Figure 1: The general generative model (Definition 1) of sequential measurements in the presence of uncontrolled state 𝑼 for a given configuration 𝑐 ∈ C , depicted as a Bayesian network with observed nodes shaded and deterministic nodes as diamonds. The program 𝐹𝑖 chosen to run is conditioned directly on all already observed variables (the previously run programs 𝑭<𝑖 and their performance measurements 𝑻<𝑖 , typically run times), which in combination with 𝑼 makes the estimation of the run times hard.
best expected loss 𝑙 ( 𝑓 ) = E𝐶 𝑙 ( 𝑓, 𝑐) .1 This can be viewed as a no-data decision problem in 𝑓, where no-data refers to the absence of prior performance measurements. The expected loss represents the Bayes risk in this context.
(𝜏, 𝜖) whose uppercase is identical to the italic, we use calligraphic uppercase (T , E ) for the rv. We abbreviate the condition or event 𝑋 = 𝑥 to simply 𝑥 provided no ambiguity arises. We employ the phrase under the event 𝑋 = 𝑥 or under 𝑥 to denote operations within a conditional probability space. In this context, E [𝑌 ] is understood as E [𝑌 | 𝑥 ] , Var [ 𝑍 | 𝑦 ] as Var [ 𝑍 | 𝑦, 𝑥 ] , and 𝐴 ⊥ ⊥ 𝐵 as 𝐴 ⊥ ⊥ 𝐵 | 𝑥 , while statements such as 𝑌 = 1 are implicitly conditioned on 𝑋 = 𝑥 . Conversely, we sometimes implicitly extend the probability space to include parameters, writing 𝑃 ( 𝑋 | 𝜃) instead of 𝑃 ( 𝑋 ; 𝜃) . When the domain is clear from context, we write ∀𝑐 rather than ∀𝑐 ∈ C or ∀𝑐 ∈ im ( 𝐶 ) . It is assumed throughout that expectations exist. The standard deviation of a rv 𝑋 is denoted by Std [ 𝑋 ] . We may write E| 𝑋 [𝑌 ] instead of E [𝑌 | 𝑋 ] to improve readability, especially when nesting conditionals and absolute values. Note that this differs from E𝑋 [ 𝑋 + 𝑌 ] , which takes the expected value with respect to 𝑋 only and results in a rv that is a function of 𝑌 . This latter form may be used solely for emphasis. The length of sequence 𝒂 is denoted by | 𝒂 | . We abbreviate confidence interval as CI, data processing inequality as DPI, and mutual information as MI. Our mathematical results are presented as theorems or, where of lesser consequence, propositions. Technical tools used in the proofs are lemmas.
3.1 The Measurement Model To ground the design of experiments and decision rules for identifying the fastest program in data, we posit a generative model of measurements. As per our premise, we must consider stateful environments where the system’s behaviour is influenced by past events or hidden states; together with the specified configuration, this allows our model to account for both the uncontrolled and controlled factors that influence program performance in a sequential setting. The model presented is fully general inasmuch as experiment designs may choose the next program to run based on all previous observables, and the state of the environment may depend on all earlier variables, whether observed or unobserved. We introduce the uncontrolled state 𝑈, a rv over the set U, to represent environmental dynamics without assuming any ability to intervene, observe, or model its underlying distribution and temporal evolution. Factors comprising this state, such as concurrent workloads, OS scheduling, cache and TLB contents, memory controller transitions, and CPU thermal throttling, can vary even within the span of a single program execution. The same variable may be controlled and uncontrolled at different times: by flushing the file system cache before running a program, the initial cache contents are controlled, but their evolution depends on the concurrent workload and the kernel version among many other influencing factors.
3 problem formalization Let F be the set of programs to compare with size 2 ⩽ F < ∞ and 𝐶 a rv over the set of configurations C . The relative importances of configurations in the benchmark are given by the known prior distribution of 𝐶 . Configurations specify the controllable aspects of the benchmarking environment (such as hardware and software settings, input data). In common terminology, a configuration is an individual benchmark, while the set C corresponds to a benchmark suite. The loss function 𝑙 : F × C → ℝ quantifies the cost (e.g. run time) of running a program in a given configuration. Our goal is to find arg min𝑓 ∈ F 𝑙 ( 𝑓 ) , the program with the
1 Due to the symmetry between F and C , this formalization can describe the task of benchmarking hardware on a set of programs, but our proposed solutions require the uncontrolled state to be shared (i.e. affect the performance of all 𝑓 ∈ F similarly, see §6), which is much more reasonable for programs running on the same computer than for different computers running the same program.
2
Definition 1 (Configuration model). Given a configuration 𝑐 ∈ C and an experiment design 𝑑 that prescribes the sequence of programs to run 𝑭 and the stopping time 𝑁 , the model generates a sequence of performance measurements 𝑻 while the uncontrolled state 𝑼 evolves. 1. Initialization a. The initial uncontrolled state 𝑢1 ∈ U is supplied by the execution environment. b. Initialize the index of the next run: 𝑖 = 1. 2. Iteration While the experiment is ongoing (𝑖 ⩽ 𝑛, where 𝑛 ∼ 𝑁 | 𝒕<𝑖 , 𝒇<𝑖 , 𝑐, 𝑑 ): a. Choose a program 𝑓𝑖 ∼ 𝐹𝑖 | 𝒕<𝑖 , 𝒇<𝑖 , 𝑐, 𝑑 , and b. measure its performance: 𝑡𝑖 ∼ 𝑇 | 𝑈 = 𝑢𝑖 , 𝐹 = 𝑓𝑖 , 𝑐. c. Let the uncontrolled state evolve: 𝑢𝑖+1 ∼ 𝑈 next | 𝑇 = 𝑡 𝑖 , 𝑈 = 𝑢𝑖 , 𝐹 = 𝑓𝑖 , 𝑐. d. Set the index of the next run: 𝑖 = 𝑖 + 1.
controlled states {𝑈1𝑐 } 𝑐 ∈ S ′ of configurations in the same part S ′ ∈ S , but requiring that they are otherwise independent. 4 the mirage of absolute performance We allowed the loss 𝑙 ( 𝑓, 𝑐) to be a function of the entire, unknown distribution of the run times, 𝑇 | 𝑓, 𝑐,2 although in the following sections we address only two common, pointwise cases: arithmetic (𝑙 ( 𝑓, 𝑐) = E [𝑇 | 𝑓, 𝑐] ) and geometric averaging (𝑙 ( 𝑓, 𝑐) = E [ ln 𝑇 | 𝑓, 𝑐] ) [Mashey, 2004, SPEC, 2006]. Consider, for example, arithmetic averaging. From the law of total expectation, we have that 𝑙 ( 𝑓, 𝑐) = E [𝑇 | 𝑓, 𝑐] = E𝑈 | 𝑓,𝑐 E [𝑇 | 𝑈, 𝑓, 𝑐] ,
(1)
which suggests estimating 𝑙 ( 𝑓 ) = E𝐶 𝑙 ( 𝑓, 𝑐) by sampling or enumerating 𝑐 ∼ 𝐶 and averaging estimates of E [𝑇 | 𝑈, 𝑓, 𝑐] over 𝑈 | 𝑓, 𝑐. The most straightforward estimator is running 𝑓 repeatedly in configuration 𝑐 and averaging the observed run times.
In the above, 𝑡𝑖 and 𝑢𝑖+1 are drawn from distributions that do not depend on 𝑖 or 𝑑 , modelling the state as Markovian. Typically, these distributions, 𝑇 | 𝑢, 𝑓, 𝑐 and 𝑈 next | 𝑡, 𝑢, 𝑓, 𝑐, are unknown. The rvs 𝐶 , 𝑁 , 𝑭 and 𝑻 (figuratively referred to as the run time) are observed; 𝑼 is unobserved. To tie the measurement model to the problem statement, we assume that the true loss 𝑙 ( 𝑓, 𝑐) is a function of the distribution 𝑇 | 𝑓, 𝑐. This distribution represents the performance of program 𝑓 under configuration 𝑐 marginalized over the possible uncontrolled states:
Definition 3 (Average over runs). Given a sequence of programs 𝒇 and corresponding values 𝒙 , both of length 𝑛, we define the average over runs of a program 𝑓 ∈ F as 𝑥¯𝑓 =
𝑛 1 ∑︁ 𝟙𝑓 = 𝑓 𝑥𝑖 , 𝑛 𝑓 𝑖=1 𝑖
P
where 𝑛 𝑓 = 𝑟𝑖=1 𝟙𝑓𝑖 = 𝑓 is the number of times 𝑓 is run, and 𝟙 is the indicator function.
𝑃 (𝑇 | 𝑓, 𝑐) = E𝑈 [ 𝑃 (𝑇 | 𝑈, 𝑓, 𝑐) 𝑃 (𝑈 | 𝑐)] .
This factorization separates the influence of 𝑇 | 𝑈, 𝑓, 𝑐 (Item 2.b), from the unknown distribution of uncontrolled states, 𝑈 | 𝑐. This latter distribution captures the overall prevalence and importance of uncontrolled states in real workloads, of which any particular execution environment – along with the uncontrolled states 𝑈1 and 𝑈 next it generates – may be unrepresentative. The allusion to the “execution environment” is to mark it as an extension point where additional interactions beyond the scope of the configuration model may arise. We now define the model for benchmark suites that test all configurations. The suite model can be understood as the product extension of the probability spaces of individual, per-configuration measurement models except we allow for additional dependencies between the uncontrolled states within certain groups of configurations, for example, those run on the same computer or in the same data center.
There is a family of benchmarking methods that differ only in experiment design (i.e. in deciding what program to run, when to stop) and otherwise use this averaging estimator 𝑇¯𝑓 of the expected run time. However, regardless of the experiment design, unbiased or consistent estimation of (1) is not possible without further assumptions as it involves the uncontrolled state, which may affect the loss. The inadequacy of the simple average has been noted by various authors [Gil et al., 2011, Chen et al., 2014, Barrett et al., 2017]. Despite its limitations, there are cases where 𝑇¯𝑓 can be unbiased and consistent: • (A.1) If U is a singleton, then this is trivial. • (A.2) If we can sample from 𝑈 | 𝑐 , then we can appeal to the Central Limit Theorem (CLT). • (A.3) If 𝑼 | 𝑐, 𝑑 is Markovian with stationary distribution 𝑈 | 𝑐, then we can use the Markov-chain CLT. • (A.4) If the effect of the previous uncontrolled state on
Definition 2 (Benchmark suite model). Given a partition S of the set C , the benchmark suite model carries out the measurements for each configuration according to Definition 1, allowing for arbitrary dependencies between the initial un-
2
Allowing this dependence on the distribution is still in keeping with von Neumann–Morgenstern rationality [Neumann and Morgenstern, 1944] if we take per-configuration aggregates as outcomes, instead of individual measurements.
3
the run time follows a zero-mean random walk, then we can use the first-difference estimator. • (A.5) If the environmental process mixes strongly enough, 𝑇¯𝑓 can be asymptotically unbiased and consistent. However, all these assumptions are unrealistic, hard to verify or offer only asymptotic guarantees. A.1 states that all features of the environment that can affect performance are known and controlled. With the complexity of current hardware and software, such total control is practically unattainable. Even on uncomplicated embedded systems, this assumption can be hard to verify and is not the focus of this work. Next, A.2 is violated in the presence of stateful processes such as those mentioned earlier. Concerning A.3, these stateful environmental processes are Markovian, but they do not necessarily have a stationary distribution (e.g. due to reducibility or periodicity), so the Markov-chain CLT is not applicable. In practice, we argue that the sequence of states produced by, for example, repeated runs of a program on any given machine may not visit the whole support of 𝑈 | 𝑐, let alone have a matching stationary distribution. A particularly relevant example is that of room temperature, which – if not controlled for – may stay constant, drift slowly or exhibit a strong periodicity (e.g. due to a thermostat), affecting CPU temperature, thermal controller state [Wikipedia, 2024] and ultimately performance. A.4 is easily violated by a single factor, such as the temperature, whose effect does not tend to follow a zeromean random walk. Finally, even if A.5 is known to be true, for it to be useful with a finite number of measurements, we need a non-trivial lower bound on the rate of mixing, which requires some knowledge of the environmental dynamics. In summary, we have argued through examples that consistent estimation of 𝑙 ( 𝑓, 𝑐) , the cost of running a program in a given configuration, needs strong and often unrealistic assumptions about the uncontrolled state. Therefore, relying on absolute performance measurements for benchmarking in stateful environments can be misleading and unreliable. While unexplored possibilities undoubtedly remain, the more general argument is that without detailed knowledge of the environmental dynamics all assumptions are suspect. Can we reverse-engineer the logic of the thermal controller and the kernel? Is that worthwhile? On every hardware and software configuration? Experimental science has long grappled with similar challenges, employing tools like fixedeffect models, randomization and blocking. In the following, we adapt these techniques to benchmarking.
iments is infeasible in the presence of uncontrolled state. However, our formalization of benchmarking as a decision problem in §3 only requires estimating the performance of one program relative to another in the same experiment, which is an easier task. Intuitively, if we have a biased estimator ˆ𝐿 ( 𝑓, 𝑐) of 𝑙 ( 𝑓, 𝑐) , then arg min𝑓 ∈ F 𝑙 ( 𝑓, 𝑐) = arg min𝑓 ∈ F E [ ˆ𝐿 ( 𝑓, 𝑐)] as long as its bias is the same for all 𝑓 ∈ F.3 We expand on this idea in the following. Definition 4 (Deltas). In the context of some 𝑓, 𝑔 ∈ F, we define the true per-configuration and the suitewise average performance deltas as 𝛿𝑐 ( 𝑓, 𝑔 ) = 𝑙 ( 𝑓, 𝑐) − 𝑙 ( 𝑔, 𝑐) , 𝛿 ( 𝑓, 𝑔 ) = 𝑙 ( 𝑓 ) − 𝑙 ( 𝑔 ) .
Assuming that ˆ𝐿 ( 𝑓, 𝑐) is a (potentially biased) estimator of 𝑙 ( 𝑓, 𝑐) , we define its suitewise average as ˆ𝐿 ( 𝑓 ) = P ˆ 𝑐 ∈ C 𝑃 ( 𝑐) 𝐿 ( 𝑓, 𝑐) . With these, the estimated per-configuration delta and the estimated average delta are defined as Δ̂𝑐 ( 𝑓, 𝑔 ) = ˆ𝐿 ( 𝑓, 𝑐) − ˆ𝐿 ( 𝑔, 𝑐) Δ̂ ( 𝑓, 𝑔 ) = ˆ𝐿 ( 𝑓 ) − ˆ𝐿 ( 𝑔 ) . We use the shorthands 𝛿𝑐, 𝛿, Δ̂𝑐, Δ̂ where 𝑓 and 𝑔 are unambiguous in the context. Remark 5. Although for each configuration, ˆ𝐿 ( 𝑓, 𝑐) lives in the probability space of its configuration model, the benchmark suite model ties them together in an extended probability P space, so ˆ𝐿 ( 𝑓 ) = 𝑐 ∈ C 𝑃 ( 𝑐) ˆ𝐿 ( 𝑓, 𝑐) is well-defined given a partition S and the intra-partition dependencies as required by Definition 2. 5.1 Finite-Sample Behaviour In the finite-sample regime, absolute certainty is unattainable. We must therefore quantify the probability of making a correct decision. The timing of this quantification leads to a critical distinction: 1. pre-data: before starting the experiment, ignorant of the realization of the data; 2. post-data: after completing the experiment, conditioning on the observed data and the resulting decision. The pre-data question is: What is the probability that we will make the right decision if we follow the decision-making process given by the experiment design and the decision rule? In contrast, the post-data question is: What is the probability that we made the right decision given the decision-making process that we followed and the observed data?
5 deltas to decision As discussed in the previous section, direct estimation of absolute performance numbers comparable across exper-
3 More generally, utility in decision theory is invariant to positive linear transformations.
4
randomly any 𝑓 ∗ ∈ F such that 𝑃 ( 𝛿ˆ( 𝑓 ∗, 𝑔 ) ⩽ 𝑍 ( 𝑓 ∗, 𝑔 )) ⩾ ′ for all 𝑔 ∈ F \ { 𝑓 ∗ } , 𝛾dec • 0 if there is no such 𝑓 ∗.
The pre-data perspective aligns naturally with frequentist inference, while the post-data perspective is the hallmark of Bayesian inference. However, the dichotomy is not strict: a Bayesian can perform pre-data inference via the prior predictive distribution, and a frequentist can answer post-data questions by constructing confidence intervals conditioned on ancillary statistics [Casella, 1992, Goutis and Casella, 1995]. Thus, the pre- and post-data distinction cuts across the choice of probabilistic paradigm. Beyond their philosophical underpinnings, an operational distinction is that frequentists typically bound the worstcase error (ensuring validity for any true parameter 𝜃), whereas Bayesians optimize the average-case error (integrating over a prior 𝜋 ( 𝜃) ). When the answer to the pre-data question is that the decision-making process gives the correct decision with probability 0.95, the frequentist qualifies that with . . . well, at least 0.95, no matter what the real performance delta is, while the Bayesian goes on to say . . . on average over possible deltas, given our prior beliefs. In this work, we evaluate methods based on their frequentist, pre-data properties, as we view benchmarking as a repeated process in software development. While post-data analysis could theoretically improve efficiency of this process by quantifying the strength of evidence, our inability to model the complex environmental dynamics precludes a full Bayesian treatment.
•
Algebraically, the inequality Δ̂ ( 𝑓, 𝑔 ) ⩽ 𝑍 ( 𝑓, 𝑔 ) expands to Δ̂ ( 𝑓, 𝑔 ) ⩽ Δ̂ ( 𝑓, 𝑔 ) − 𝛿 ( 𝑓, 𝑔 ) , which simplifies to 𝛿 ( 𝑓, 𝑔 ) ⩽ 0. Thus, the decision rule ensures that the data supports the conclusion that 𝑓 ∗ is no slower than any other program with ′ under the noise model 𝑍 . confidence 𝛾dec While the exact noise distribution 𝑍 is typically unknown in practice, we establish the theoretical properties of the decision rule here assuming it is known.In §5.3, we discuss how to safely operationalize this rule using adversarial noise envelopes and finite sample budgets. The rest of this subsection provides an analysis of the probabilistic guarantees of the decision rule. Definition 7 (Noise quantiles). We define the 𝑝-quantile bound of the noise distribution 𝑍 ( 𝑓, 𝑔 ) as 𝑄 𝑝 ( 𝑓, 𝑔 ) = inf { 𝑥 ∈ ℝ | 𝑃 ( 𝑍 ( 𝑓, 𝑔 ) ⩽ 𝑥 ) ⩾ 𝑝} .
Remark 8 (Equivalence to delta thresholding). The antisymmetry of Δ̂ and 𝛿 implies the antisymmetry of 𝑍 . Thus, we can rewrite the probability condition in the decision rule as ′ 𝑃 𝛿ˆ( 𝑓, 𝑔 ) ⩽ 𝑍 ( 𝑓, 𝑔 ) ⩾ 𝛾dec
′ 𝑃 𝛿ˆ( 𝑓, 𝑔 ) ⩽ −𝑍 ( 𝑔, 𝑓 ) ⩾ 𝛾dec
5.1.1 Decisions under Uncertainty
′ 𝑃 𝑍 ( 𝑔, 𝑓 ) ⩽ −𝛿ˆ( 𝑓, 𝑔 ) ⩾ 𝛾dec .
A natural approach to decision making is to construct symmetric CIs for 𝛿 ( 𝑓, 𝑔 ) around Δ̂ ( 𝑓, 𝑔 ) and deem 𝑓 faster than 𝑔 if the entire realized CI is negative. However, as correct decision making requires knowing only the sign of 𝛿 ( 𝑓, 𝑔 ) , one of the two bounds embodied by the CI is unnecessary. Thus, for increased statistical power (that is, reaching the same level of confidence in our decision making process with fewer runs), we require only one-sided bounds. A decision rule maps observations to actions. Here, the desired action is to identify a program from the set of fastest programs in F . However, the finite number of measurements and the resulting uncertainty necessitates an augmented action space, F ∪ {0}, where 0 represents abstaining from a decision, and it is assumed that 0 ∉ F .
′ ( 𝑔, 𝑓 ) , this is the same By the definition of the quantile 𝑄𝛾dec ′ ( 𝑔, 𝑓 ) , which is equivalent to as −𝛿ˆ( 𝑓, 𝑔 ) ⩾ 𝑄𝛾dec ′ ( 𝑔, 𝑓 ) . 𝛿ˆ( 𝑓, 𝑔 ) ⩽ −𝑄𝛾dec
Proposition 9 (Unambiguous region). Let 𝛾 ⩾ 𝛾dec (the “detection confidence”), and let 𝛾 ′ = 1 − ( 1 − 𝛾 )/( F − 1) . We define the separation threshold 𝑆𝛾 ( 𝑓, 𝑔 ) as ′ ( 𝑔, 𝑓 ) . 𝑆𝛾 ( 𝑓, 𝑔 ) = −𝑄𝛾′ ( 𝑓, 𝑔 ) − 𝑄𝛾dec
If the true deltas for some 𝑓 ∈ F are in the corresponding unambiguous region, meaning 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑆𝛾 ( 𝑓, 𝑔 )
Definition 6 (The decision rule). As input, the rule takes the estimates 𝛿ˆ( 𝑓, 𝑔 ) realized from the estimators Δ̂ ( 𝑓, 𝑔 ) in the context of a measurement model with 𝑛 runs. The required decision confidence 𝛾dec ∈ [ 0, 1] is a parameter. Let ′ 𝛾dec = 1 − ( 1 − 𝛾dec )/( F − 1) be its Bonferroni correction. Also, let 𝑍 ( 𝑓, 𝑔 ) = Δ̂ ( 𝑓, 𝑔 ) − 𝛿 ( 𝑓, 𝑔 ) be the rv representing the noise. The decision rule picks
and 𝛿 ( 𝑓, 𝑔 ) < 0
for all 𝑔 ≠ 𝑓 , then this 𝑓 is the unique fastest program, and the decision rule picks 𝑓 with probability at least 𝛾 . For the proofs of propositions in this section, see §B. Table 1 shows the probabilistic confusion matrix of the decision rule by regions defined by the true deltas 𝛿 ( 𝑓 , 𝑔 ) ⩽ 0, where 𝑓 is one of the fastest programs and 𝑔 ≠ 𝑓 .4
5
Tie (∃ 𝑔 : 𝛿 ( 𝑓, 𝑔 ) = 0): For a specific fastest program 𝑓 to be picked, it must statistically “beat” every rival. The bottleneck is the tied rival 𝑔 : since 𝛿 ( 𝑓, 𝑔 ) = 0, 𝑓 can only win if the noise erroneously exceeds the decision threshold. This is a false positive event with probability ′ . Since the decision rule enforces a unique at most 1 − 𝛾dec winner, the events of picking any specific program are disjoint. Thus, the total probability 𝑝0 of picking any of the T fastest programs is at most the sum of these tail ′ ) . Substituting the definition of probabilities: T ( 1 − 𝛾dec ′ 𝛾dec , we verify 𝑝0 = F −T 1 ( 1 − 𝛾dec ) . • Ambiguous region (∀𝑔 : 𝛿 ( 𝑓, 𝑔 ) < 0 and ∃ 𝑔 : 𝛿 ( 𝑓, 𝑔 ) > 𝑆𝛾 ( 𝑓, 𝑔 ) ): The action is Fastest or Abstain with probability 𝛾dec , but we cannot bound their probabilities separately. It may be that the decision rule always abstains. • Unambiguous region (∀𝑔 : 𝛿 ( 𝑓, 𝑔 ) < 0 and 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑆𝛾 ( 𝑓, 𝑔 ) ): The fastest program is picked with confidence 𝛾 . Abstention or picking a slower program have at most probability 1 − 𝛾 together.
Table 1: The probabilistic confusion matrix for the decision rule (Definition 6) with a given decision confidence 𝛾dec . The detection confidence 𝛾 is purely for analysis, where it is assumed that 𝛾dec ⩽ 𝛾 ⩽ 1. The number of programs is F, the number of programs tied for fastest is T. We let 𝑝0 = F −T 1 ( 1 − 𝛾dec ) and 𝑝1 = FF−−T1 ( 1 − 𝛾dec ) . The deltas between the fastest and other programs are denoted by 𝛿 ( 𝑓, 𝑔 ) ⩽ 0 for all 𝑔 ≠ 𝑓 . The region Tie corresponds to the condition ∃ 𝑔 : 𝛿 ( 𝑓, 𝑔 ) = 0; Ambiguous to ∀ 𝑔 : 𝛿 ( 𝑓, 𝑔 ) < 0 ∧ ∃ 𝑔 : 𝛿 ( 𝑓, 𝑔 ) > 𝑆𝛾 ( 𝑓, 𝑔 ) ; and Unambiguous to ∀ 𝑔 : 𝛿 ( 𝑓, 𝑔 ) < 0 ∧ 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑆𝛾 ( 𝑓, 𝑔 ) , where 𝑆𝛾 ( 𝑓, 𝑔 ) denotes the separation bound for the pair 𝑓, 𝑔 defined in Proposition 9. Cells corresponding to Type I, Type II and Type III errors are coloured yellow, orange and red, respectively, while those representing the correct action are white.
•
Region of 𝛿 ( 𝑓, ∗) Action
Tie
Fastest Abstain Slower
⩽ 𝑝0 1 − ( 𝑝0 + 𝑝1 ) ⩽ ⩽ 𝑝1
Ambiguous
Unambig. 𝛾⩽
𝛾dec ⩽
⩽ 1−𝛾
⩽ 1 − 𝛾dec
5.2 Asymptotics
∀𝜔 > 0 : lim 𝑃 ( 𝜃ˆ𝑛 − 𝜃 ⩽ 𝜔) = 1. 𝑛→∞
In this section, we prove that the decision rule makes asymptotically correct decisions if the per-configuration estimators exhibit a certain form of consistency. For sample efficiency in the finite regime, we based the decision rule (Definition 6) on the notion of stochastic upper bounds defined by the noise quantiles (Remark 8). Asymptotically, we expect these noise quantiles to tighten around zero. We formalize this as a one-sided variant of weak consistency.
To tie the discussion to the decision rule, we point out that the upper consistency of Δ̂ ( 𝑓, 𝑔 ) is equivalent to requiring that the noise quantiles (Definition 7) become non-positive in the limit. Specifically, for any fixed confidence 𝑝 < 1, the estimator Δ̂ ( 𝑓, 𝑔 ) is upper consistent if and only if lim sup 𝑄 𝑝 ( 𝑓, 𝑔 ) ⩽ 0. 𝑛→∞
Definition 10 (Upper consistency). We say that a sequence of estimators 𝜃ˆ𝑛 of some 𝜃 ∈ ℝ is upper consistent if the probability that the estimator exceeds the true value by any fixed margin vanishes as 𝑛 → ∞. Formally,
In finite-sample analysis, we must also characterize the rate at which these bounds shrink. Next, we show that if the per-configuration estimators Δ̂𝑐 admit upper bounds that scale as 𝑂 ( 𝑛−1/2 ) , then Δ̂ preserves this rate. Crucially, we construct the suitewise confidence level by combining the per-configuration probabilities according to the dependency structure of the benchmark suite model.
4 Although we emphasize the decision-theoretic point of view throughout, it is worth pointing out that our decision rule corresponds to frequentist multiple hypothesis testing. For a specific candidate 𝑓 ∗, deciding that it is the winner requires rejecting the union of F − 1 pairwise null hypotheses, where each 𝐻0,𝑔 states that 𝑓 ∗ is not faster than 𝑔 . This is an intersection–union test: we declare 𝑓 ∗ the winner only if every pairwise null is rejected. In this framework, we refer to the following global error types. • Type I Error (False Positive): This occurs when the global null hypothesis holds (i.e. there is no unique winner) yet the decision rule rejects it by picking one of the programs. This is a mild error in benchmarking as there is no performance loss. • Type II Error (False Negative): This occurs when the alternative hypothesis holds (i.e. there is a unique winner) but the decision rule fails to reject the null by abstaining. This represents a lack of statistical power: the signal exists, but the test was too conservative or the noise too high to detect it with the required confidence. • Type III Error (Sign Error): Unlike standard binary hypothesis testing, our setup allows for a third outcome: rejecting the null in the wrong direction (declaring a slower program the winner).
Proposition 11 (Suitewise upper consistency and rates). Let 𝑓, 𝑔 ∈ F . Assume that for each configuration 𝑐 ∈ C , the estimator Δ̂𝑐 ( 𝑓, 𝑔 ) of 𝛿𝑐 ( 𝑓, 𝑔 ) admits an upper bound 𝑈𝑛𝑐 such that 𝑃 ( Δ̂𝑐 ( 𝑓, 𝑔 ) − 𝛿𝑐 ( 𝑓, 𝑔 ) ⩽ 𝑈𝑛𝑐 ) ⩾ 1 − 𝛼𝑐 for some failure probability 𝛼𝑐 ∈ ( 0, 1) . Assume further that max ( 0, 𝑈𝑛𝑐 ) = 𝑂 ( 𝜙 ( 𝑛)) uniformly for all 𝑐 ∈ C . Let the suitewise bound be P 𝑈𝑛 = 𝑐 ∈ C 𝑃 ( 𝑐)𝑈𝑛𝑐 . Then, provided the sum and product exist, 𝑈𝑛 is a probabilistic upper bound satisfying 𝑃 ( Δ̂ ( 𝑓, 𝑔 ) − 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑈𝑛 ) ⩾
Y S′ ∈S
and max ( 0, 𝑈𝑛 ) = 𝑂 ( 𝜙 ( 𝑛)) .
6
1 − min 1,
∑︁ 𝑐 ∈S′
𝛼𝑐
,
Corollary 12. If lim𝑛 𝜙 ( 𝑛) = 0, then Δ̂𝑐 is upper consistent for all 𝑐 and so is Δ̂.
um width of these stochastic upper bounds, corresponding to the minimum effect size that the decision rule can detect. Furnished with known, vanishing probabilistic upper bounds, we can readily answer a user’s question: Is this benchmarking method able to identify the fastest program? We might reply thus: Yes, because the underlying estimator of the deltas is upper consistent, but you’ll need to wait forever to be sure. A practical mind would then enquire along these lines: I don’t have the time. How many runs are needed to detect a one percent difference with 0.95 probability? To which, the answer: Let me compute that for you from the bounds on the estimator. We will prove in §6–8 and validate experimentally in ?? that the number of runs required grows at the theoretically optimal rate with our methods.
Finally, we prove that the decision rule is consistent: given a sufficient number of runs, the unambiguous region expands to cover any program with a strictly negative true delta. Proposition 13 (Consistency of the decision rule). Assume there is a unique fastest program 𝑓 ∈ F . If the estimator Δ̂ is upper consistent, then lim 𝑃 ( decision rule picks 𝑓 ) = 1.
𝑛→∞
Remark 14 (Consistency and ties). In the case of tied programs (where 𝛿 ( 𝑓, 𝑔 ) = 0), the probability of correctly abstaining does not converge to 1 as 𝑛 → ∞, but rather remains lower-bounded by 1 − ( 𝑝0 + 𝑝1 ) = 1 − F −F 1 ( 1 − 𝛾dec ) (see Tie / Abstain cell in Table 1). This is a standard feature of fixed-confidence statistical tests: to force the false positive rate to zero asymptotically, one would need to let 𝛾dec → 1.
6 delta experiments To characterize the behaviour of an experiment design, our strategy is to derive stochastic upper bounds for Δ̂𝑐 that vanish with the number of runs 𝑛. In the finite case, this sequence of bounds allows us to find the minimum runs required to meet a given sensitivity and confidence level. For asymptotics, appealing to Propositions 11 and 13 helps derive the consistency of the decision-making process. The experiment designs, presented in later sections, exhibit significant similarities, and to avoid unnecessary repetition, we will discuss their properties in as much generality as possible. To this end, we now describe the class of delta designs, their common substrate, which constrains the configuration model (Definition 1) but leaves the sampling strategy for 𝑭 underspecified. First, we introduce alternative versions of our ceteris paribus (“all things being equal”) assumption positing that environmental noise affects the loss additively and uniformly across all programs.
5.3 Looking Ahead In our setting, the noise distribution 𝑍 is typically unknown. Consequently, we cannot directly evaluate the quantile thresholds 𝑄 𝑝 ( 𝑓, 𝑔 ) in the decision rule. To ensure robustness, we define the noise model used in the decision rule not as a single physical realization but as the adversarial envelope over possible noise models Z . In practice, we want to detect when the actual noise is not in Z . Our proposed methods are based on the simplest such setup: requiring a hard bound on the magnitude of the noise. Definition 15 (Adversarial noise quantiles). We define the adversarial 𝑝-quantile 𝑄 𝑝adv as 𝑄 𝑝adv =
sup
inf { 𝑥 ∈ ℝ | 𝑃 ( 𝑍 ( 𝑓, 𝑔 ) ⩽ 𝑥 ) ⩾ 𝑝} .
Assumption 1 (Additive global effect). Let 𝑙 ( 𝑓, 𝑐) = E [𝑇 | 𝑓, 𝑐] and 𝑇 | 𝑈, 𝑓, 𝑐 of the measurement model (Definition 1) be generated as follows: 1. Draw the true run time 𝜏 | 𝑓, 𝑐. 2. Draw the environmental noise 𝜀 | 𝑢, 𝑐. 3. Let the observed run time 𝑡 = 𝜏 + 𝜀. Here, 𝜏, 𝜀 ∈ ℝ are unobserved, their distributions unknown.
𝑍 ∈ Z , 𝑓,𝑔 ∈ F
Replacing the unknown noise quantiles with their adversarial counterparts makes the decision rule more conservative. Since the adversarial bound is a supremum, satisfying the decision condition 𝛿ˆ( 𝑓, 𝑔 ) ⩽ −𝑄 𝑝adv implies satisfying 𝛿ˆ( 𝑓, 𝑔 ) ⩽ −𝑄 𝑝 ( 𝑔, 𝑓 ) for the true, unknown noise distribution. With the choice of 𝑈𝑛𝑐 = 𝑄 𝑝adv , our results for both the finite and the asymptotic regimes remain valid. In the context of our experimental designs, we will bound 𝑄 𝑝adv to establish the upper consistency of the perconfiguration estimators Δ̂𝑐 ( 𝑓, 𝑔 ) , which guarantees asymptotically correct decisions via Propositions 11 and 13. However, for practical benchmarking, we must satisfy user requirements on the confidence level and the maxim-
Assumption 2 (Multiplicative global effect). Let 𝑙 ( 𝑓, 𝑐) = E [ ln 𝑇 | 𝑓, 𝑐] and 𝑇 | 𝑈, 𝑓, 𝑐 of the measurement model (Definition 1) be generated as follows: 1. Draw the true run time 𝜏 | 𝑓, 𝑐. 2. Draw the environmental noise 𝜀 | 𝑢, 𝑐. 3. Let the observed run time 𝑡 = 𝜏𝜀. Here, 𝜏, 𝜀 ∈ ℝ+ are unobserved, their distributions unknown.
7
𝑵 𝐹1
Λ1
T3
T2
Λ2
𝑇1 E1
𝑈1
𝐹4
𝐹3
𝐹2 T1
Λ3
𝑇2
𝑇3
𝑥
E3
E2
𝑈4
𝑈3
𝑈2
Figure 2: The delta design (Definition 17). This constrains the configuration model (Figure 1) but leaves the sampling strategy for 𝑭 underspecified. Under its ceteris paribus assumption (§6), the observed [log] run time 𝑇𝑖 is a the sum of the unobserved true [log] run time T 𝑖 and the environmental noise E𝑖 . The dependence of E𝑖 on 𝐹𝑖 is mediated solely through 𝑭<𝑖 ; so, by the DPI, we have 𝐼 ( E𝑖 ; 𝐹𝑖 ) ⩽ 𝐼 ( 𝑭<𝑖 ; 𝐹𝑖 ) . Importantly, the mutual information bound 𝐼 ( 𝑭<𝑖 ; 𝐹𝑖 ) is determined by the sampling process independently from the stateful environment, giving us control on the effect of the environmental noise E . The shorthands Λ𝑖 = 𝟙𝐹𝑖 = 𝑓 − 𝟙𝐹𝑖 =𝑔 and P 𝑁 𝑓 = 𝑖𝑅=1 𝟙𝐹𝑖 = 𝑓 (Definition 18) are used in the proofs.
These losses cover the two most common cases [Mashey, 2004]. Choosing between them implies taking a side in the long-running arithmetic vs geometric mean argument [Mashey, 2004]. Crucially, our approach answers this question not by assuming a distribution for the raw run times T or the noise E , but by deriving the estimator directly from the functional form of the noise interaction. Since, in the multiplicative version, the noise is combined with the logarithm of the loss and the distributions of T and E are unknown, we obtain essentially the same model as with the additive assumption. Hence, in the follows, we simply assume the ceteris paribus holds and do not distinguish between the two cases. We write 𝑇, T , and E, even though under Assumption 2 they represent ln 𝑇, ln T , and ln E, respectively, as if we observed ln 𝑇 instead of 𝑇. In practice, we prefer the multiplicative model because it is a good match for common effects that accumulate over the course of a run (e.g. CPU throttling). For some effects and for some sets of programs, the additive model may be more appropriate, but as we argue in §10.3, unbiased estimation with both multiplicative and additive effects is possible only with a single hardware and software configuration. Both assumptions relate the more tractable 𝑇 | 𝑈, 𝑓, 𝑐 to 𝑇 | 𝑓, 𝑐. Playing the role of ceteris paribus, they assert sufficiency of control by requiring the effect of the uncontrolled variables to be the same on all programs. Conversely, all variables whose effects vary by program must be controlled or randomized [Curtsinger and Berger, 2013].
could we determine the better program, as any observed performance difference could be attributed to this state. This is particularly clear when the unobserved uncontrolled state remains constant throughout the benchmarking process. Also note that the global-effect assumption is made for a given set of programs, and the more alike the programs in F, the more similar the impact of uncontrolled states on them. For example, if two programs do proportionally the same amount of CPU and I \O work, then CPU throttling or concurrent I \O may influence their performance similarly. Definition 17 (Delta design, see Figure 2). We say that an experiment design 𝑑 based on the measurement model is a delta design and denote it with 𝑑 ∈ D Δ if under 𝑑 • Assumption 1 or 2 holds, • ∥ 𝑇 ∥∞ < ∞, and, given any 𝑟 ∈ ℕ and for all 𝑖 ∈ [ 1, 𝑛] , • 𝐹𝑖 ⊥ ⊥ (𝑻<𝑖 , 𝐶 ) | 𝐹<𝑖 , 𝑛, • supp ( 𝐹 𝑖 | 𝑛) = F, and • ˆ 𝐿 ( 𝑓, 𝑐) = 𝑇¯𝑓 . The assumption that ˆ𝐿 ( 𝑓, 𝑐) = 𝑇¯𝑓 (see Definition 3) for all 𝑓 ∈ F determines Δ̂𝑐 = Δ̂ ( 𝑓, 𝑔, 𝑐) in Definition 4, so far only partially specified for being dependent on the choice of ˆ𝐿. By this definition, the 𝐹𝑖 depend only on 𝑭<𝑖 and assign non-zero probability to all programs. This constrains but does not fully specify how 𝑭 is sampled. Definition 18 (Δ shorthands). Let 𝑓, 𝑔 ∈ F, 𝑓 ≠ 𝑔 and 𝑐 ∈ C . We introduce the following shorthands: Λ = 𝟙𝑭 = 𝑓 − 𝟙𝑭 =𝑔 ,
Remark 16 (Inevitability of a ceteris paribus). The assumption that uncontrolled noise affects all programs uniformly is a necessary consequence of not modelling state dynamics, a key requirement for our method’s broad applicability. To see why, consider the case where a single uncontrolled state influences programs differently. Not even with infinite data
𝑁𝑓 =
𝑛 ∑︁ 𝑖=1
8
𝟙𝐹𝑖 = 𝑓 ,
𝑁𝑔 =
𝑛 ∑︁ 𝑖=1
𝟙𝐹𝑖 =𝑔 ,
𝐹1
𝐹4
𝐹3
𝐹2 T1
𝑇1 𝑈1
𝑈2
𝑈4
𝑈3
T6
𝑇5
E4
E3
E2
𝐹6 T5
𝑇4
𝑇3
𝑇2
E1
𝐹5 T4
T3
T2
𝑇6
E5
𝑈5
E6
...
𝑈6
𝑈7
Figure 3: The blocked experiment design 𝛽 ( [ 2, 4, . . . ] ) . The individual blocks are delta designs (§6) linked via their last and first uncontrolled states. Run counts of programs within blocks are balanced. The balancing couples 𝐹𝑖 and 𝐹𝑗 in the same block, but those in different blocks are independent.
M𝑐 = max 𝑇 | 𝑐 ∞ , T | 𝑐 ∞ , E | 𝑐 ∞ .
Next, we define blocked experiments, which have blockwise independent 𝑭 and equal run counts within each block for all programs.
Remark 19 (Shift invariance). Note that |𝑇 | is bounded in delta designs, which implies the same for | T | and | E | . This can be easily seen by considering T 1 and E1 , which are independent. Hence, M𝑐 < ∞. Furthermore, 𝑙 ( 𝑓, 𝑐) is unidentifiable under the additive noise assumption since the shifted T + C and E − C lead to the same observable behaviour for any C ∈ ℝ. With this in mind, we could even assume that C is chosen to minimize max{∥ T + C | 𝑐 ∥∞ , ∥ E − C | 𝑐 ∥∞ }, in which case it can be shown that M𝑐 = ∥𝑇 | 𝑐 ∥∞ .
Definition 22 (Block design, see Figure 3). A blocked experiment design for a given blocking 𝒃 is denoted by 𝛽 ( 𝒃) . In the single-block case, 𝒃 = [ 𝑏] and 𝛽 ( [ 𝑏]) (abbreviated as 𝛽 ( 𝑏) ) is a delta design where 𝐹𝑖 are sampled without replacement from a multiset of F𝑏 elements of each 𝑓 ∈ F. In the multi-block case, 𝛽 ( 𝒃) is the “concatenation” of the single-block experiment designs corresponding to the elements of 𝒃, linked via their last and first uncontrolled states.
Remark 20 (Independent vs uncorrelated). If the run times were i.i.d. (see e.g. Georges et al. [2007]), their mean would be approximately normal due to the CLT. Subject to the validity of this approximation, a frequentist CI based on Δ̂𝑐 would then be the same as the Bayesian credible interval for an appropriately chosen prior. However, the Λ̂𝑖𝑇𝑖 terms in Δ̂𝑐 , are at best pairwise uncorrelated, not mutually independent, so the CLT does not apply [Svante, 1988].
In the rest of this section, we establish the upper consistency of blocked experiments by bounding the first two moments of Δ̂𝑐 ( 𝑓, 𝑔 ) and appealing to Cantelli’s inequality (the onesided Chebyshev inequality). This is sufficient to prove that the asymptotic rate is optimal, but the resulting bound is loose. For the finite case, we thus approximate the worstcase behaviour of the noise with dynamic programming, which allows direct comparison with simple randomized experiments, presented later in §8.
With the framework of delta experiments in place, we now present a block-based experiment design that instantiates this model.
7.1 Single-Block Experiments
7 blocked experiments
Here, we state the theorems about the contraction rates of the variance and the bias of the Δ̂ estimator in single-block designs. For the proofs, see §C.1.
A natural approach is to collect an equal number of measurements for all programs. Under independent sampling, this is impractical because the difference in run counts 𝑁𝑓 − 𝑁𝑔 behaves as a simple random walk, for which the expected return time to zero is infinite [Feller 1968]. Instead, the standard solution relies on sampling without replacement.
Theorem 23. For the 𝛽 ( 𝑛) design, Var [ Δ̂𝑐 ] is 𝑂 ( 𝑛−1 ) . Theorem 24. For the 𝛽 ( 𝑛) design, E [ Δ̂𝑐 − 𝛿𝑐 ] = 𝑂 ( 𝑛−1/2 ) . 7.2 Multi-Block Experiments
Definition 21 (Blocking). A blocking 𝒃 is a sequence of natural numbers that are divisible by F such that 1 ⩽ | 𝒃 | < ∞. We indicate block-relative indexing with a superscript. In the context of a blocking 𝒃, we define 𝒙 𝑘 = 𝒙𝑝:𝑞 , where 𝒙 is a P P sequence, 𝑝 = 𝑘𝑖=−11 𝑏𝑖 + 1 and 𝑞 = 𝑘𝑖=1 𝑏𝑖 .
Proposition 25 (Multi-block bounds). Let 𝒃 be a blocking and 𝑐 ∈ C . Assume that the per-block biases and standard deviations are bounded as E [ Δ̂𝑐 | 𝛽 ( 𝑏𝑘 )] − 𝛿𝑐 ⩽ 𝐵𝑘 ,
9
Std [ Δ̂𝑐 | 𝛽 ( 𝑏𝑘 )] ⩽ 𝑆𝑘
Remark 30 (One-sided variance). Although the variance of Δ̂𝑐 vanishes asymptotically, the variance of its constituent ˆ𝐿 ( 𝑓, 𝑐) alone may not. This is evident when the noise E𝑖 are perfectly correlated, preventing it from averaging out. This underlines the necessity of focussing on deltas instead of absolute performance.
for all 𝑘 ∈ [ 1, | 𝒃 |] . Then, these bounds combine linearly as E [ Δ̂𝑐 ] − 𝛿𝑐 ⩽
|𝒃| ∑︁ 𝑘=1
𝑏𝑘 𝐵𝑘 , 𝑖 𝑏𝑖
Std [ Δ̂𝑐 ] ⩽
P
|𝒃| ∑︁ 𝑘=1
𝑏𝑘 𝑆𝑘 . 𝑖 𝑏𝑖
P
See §C.2 for the proof. Remark 26 (Incomplete 𝛽 -experiments). A claim analogous to the above is true when the last block is incomplete. Blocks that are yet to begin or do not have runs for both 𝑓 and 𝑔 are to be ignored.
We have bounded the bias and the standard deviation of a block design for a given blocking, which is sufficient for making decisions under uncertaintly (see §5.1.1 and §5.3) for a given number of runs 𝑛, but to prove consistency and to find the number of runs required for a desired level of sensitivity at a minimum effect size, we need computable bounds for all 𝑛. However, there are many possible blockings for a given 𝑛, so we must first decide how the block sizes shall evolve as the overall size increases. We first study the asymptotics of constant block size designs and the issues inherent therein, then we move on to explore the effect of growing block sizes.
7.3 Combining Per-Configuration Bounds With the bounds on the worst-case bias and variance of the per-configuration estimator Δ̂𝑐 , we construct similar bounds for the suitewise average estimator Δ̂. Then, we derive stochastic upper bounds for Δ̂ − 𝛿. Proposition 27 (Δ̂𝑐 bounds to Δ̂). Assume that | E [ Δ̂𝑐 ] − 𝛿𝑐 | ⩽ 𝑏𝑐 and Std [ Δ̂𝑐 ] ⩽ 𝑠𝑐 for all 𝑐 ∈ C . Then, under the benchmark suite model with partition S of C , E [ Δ̂] − 𝛿 ⩽
∑︁
𝑃 ( 𝑐) 𝑏 ,
𝑐 ∈C
Var [ Δ̂] ⩽
∑︁ ∑︁
7.4 Asymptotics with Constant Block Size
𝑐
𝑃 ( 𝑐) 𝑠
𝑐
In this section, we assume that the sizes of all blocks are 𝑏 ∈ ℕ, and instead of 𝛽 ( [ 𝑏, . . . , 𝑏]) we write 𝛽 ( 𝑛, 𝑏) , where 𝑏 divides 𝑛 to distinguish this from the general case. A quick inspection of the bounds in Proposition 25 reveals that they stay constant as the number of blocks increases. This is because the sums are of constant terms, determined P by the block sizes, and | 𝒃 |/ 𝑖 𝑏𝑖 = 𝑏−1 is constant, too. We now demonstrate that the problem does not lie within the bounds; rather, constant block size designs are biased, even asymptotically.
2 .
S′ ∈S 𝑐 ∈S′
See §C.3 for the proof of this and the following proposition. Proposition 28 ( 𝛽 moment-based noise quantile). Let 𝑏 ( 𝑛) and 𝑠 ( 𝑛) denote the respective suitewise bounds on the absolute bias and standard deviation of Δ̂ for a blocked design 𝛽 ( 𝑛) , where 𝑏 ( 𝑛) = 𝑂 ( 𝑛−1/2 ) and 𝑠 ( 𝑛) = 𝑂 ( 𝑛−1/2 ) . For any confidence level 𝑝 ∈ ( 0, 1) , the adversarial noise quantile 𝑄 𝑝adv is bounded as √︂ 𝑝 adv 𝑄 𝑝 ⩽ 𝑏 ( 𝑛) + 𝑠 ( 𝑛) , 1− 𝑝
Example 31 ( 𝛽 ( 𝑛, 𝑏) bias via 𝐹𝑖 𝑈𝑖+1 ). Let F = { 𝑓, 𝑔 }, 𝑏 = 2. Under 𝛽 ( 𝑛, 𝑏) , in any block 𝑘, the first run 𝐹1𝑘 is equally likely to be preceeded by 𝑓 and 𝑔 . However, if the second run 𝐹2𝑘 = 𝑓 , then 𝐹1𝑘 = 𝑔 , so runs of 𝑓 are more likely overall to be after a run of 𝑔 than after an 𝑓. Thus, with the choices E𝑖 = 𝑈𝑖 , 𝑈𝑖+1 = 𝟙𝐹𝑖 = 𝑓 and 𝑈1 = 0, the bias of 𝑇¯𝑓 varies by program, which renders Δ̂𝑐 biased.
which contracts at a rate of 𝑂 ( 𝑛−1/2 ) . ′ Given the decision rule parameters 𝛾 and 𝛾dec and a desired positive sensitivity 𝜔 , we can determine the smallest number of runs 𝑛 by analytically or numerically solving the separation threshold equation
All blocks have the same bias for all 𝑛, so 𝛽 ( 𝑛, 𝑏) is asymptotically biased. This bias is a potentially blocking issue, and we aim to understand existing practice by reverse engineering the assumptions that may allow blocking to work. We discuss two prominent examples of constant block size designs, paired benchmarking and random interleaving, among related works in §7.4.1 and §7.4.2. The above example relied on propagating information via 𝐹𝑖 𝑈𝑖+1 , but as the next one shows, the bias does not go away if we remove this connection.
−𝑆𝛾 ( 𝑓, 𝑔 ) = 𝑄𝛾adv + 𝑄𝛾adv ⩽ 𝜔. ′ ′ dec Remark 29 (Optimal 𝛽 ( 𝑛) separation rate). Even though the 𝛽 ( 𝑛) bias rate 𝑂 ( 𝑛−1/2 ) proven above is worse than the 𝑂 ( 𝑛−1 ) with i.i.d. noise, the standard deviation rate is 𝑂 ( 𝑛−1/2 ) in both cases. Consequently, the overall rate for the separation threshold, which is a positive linear combination of the standard deviation and the bias, is optimal.
10
Example 32 ( 𝛽 ( 𝑛, 𝑏) bias via 𝐹𝑖 𝑇𝑖 𝑈𝑖+1 ). Consider a set F consisting of three programs with deterministic run times: 𝑓 and 𝑔 with 1s, and ℎ with 2s. Suppose that E𝑖 = 1 if 𝑈𝑖 is even, and 0 otherwise. Let 𝑢1 = 0. Notice that all blocks start with an even 𝑈𝑖 because they take exactly 1s + 1s + 2s = 4s. Enumerating the 6 possible orderings of programs within blocks, simple counting reveals that 𝑓 and 𝑔 are run in an even state with probability 1/2 but ℎ with 2/3. Hence, ℎ experiences higher bias through E𝑖 than the other two.
who propose assigning every pair of consecutive customers to treatment and control in randomized order to reduce variance. In their setting, i.i.d. assumptions guarantee unbiasedness. In contrast, our starting point is that stateful environments rule out independence. 7.4.2 Google Benchmark The Google Benchmark library has the ability to run and measure a number of functions with random interleaving5 , with claims of up to 40% reduction in run-to-run variance but no discussion of bias apart from random interleaving approximating a “real workload”. We may use this library to benchmark alternative implementations of functions against each other, which amounts to a single block experiment 𝛽 ( 𝑛) 6 . Our reservations about the validity of assumptions supporting asymptotic unbiasedness apply. On the other hand, if the functions being benchmarked serve different purposes, we are more likely to be interested in absolute rather than relative performance figures, perhaps to be compared to the previous version of the program that has these functions. Needless to say, comparing results from different experiments reintroduces all the problems that uncontrolled state poses. Still, a large number of unrelated functions may help with dispersion of uncontrolled state, and relative benchmarking of alternative implementations randomly interleaved with many unmeasured, unrelated functions may empirically work better than with a more homogenous approach, such as inserting random waits.
It is also easy to see that the variance may not vanish. In our first example, consider extending the uncontrolled state to a pair, where the new component retains the original 𝑢1 indefinitely, and using this 𝑢1 to modulate the bias. In the second, randomize the parity of 𝑢1 . So, with our current assumptions, constant block size designs can exhibit program bias even asymptotically. Assuming that all programs affect the uncontrolled state the same way would help eliminate the bias, but one only needs to consider how CPU temperature is affected by run time to see that this is hardly a tenable proposition. Alternatively, we could require that the uncontrolled state disperses, and the current state 𝑈𝑖 becomes indistinguishable from the next, 𝑈𝑖+1 | 𝐹𝑖 = 𝑓 , which would prohibit any short-term effect on performance. Similarly, to guarantee that the variance vanishes, the inter-block dependencies must be constrained. But the dependencies can propagate through the uncontrolled state, so we are back to the original problem discussed in §4: lacking detailed knowledge of the dynamics of the environment, all such assumptions are suspect. Therefore, to achieve consistent estimation in stateful environments, alternatives to constant block size designs are necessary.
7.5 Asymptotics with Growing Blocks
7.4.1 Paired Benchmarking
As shown in §7.4, constant block size designs can exhibit non-vanishing bias and variance. In general, in a multi-block setting, the per-block bounds on the bias and the variance combine linearly (Proposition 25), so the block size must grow exponentially in order to have a single block dominate, which guarantees consistency.
Acknowledging the problems posed by stateful environments, Denis Bazhenov [2023] proposes paired benchmarking of programs to reduce variance. Just as paired testing is a kind of blocking in statistics, their proposed method is a special case of 𝛽 -experiments with 𝑏 = F = 2. They demonstrate variance reduction empirically but do not address the bias issue or the question of consistency. In our analysis, we demonstrated the potential for bias and provided sufficient conditions for asymptotic unbiasedness and proved consistency under some conditions. To the extent that these conditions are less realistic than those of 𝛿-experiments, we prefer the latter, although we cannot rule out that better assumptions could change this. In the context of A \B testing, paired benchmarking is similar to the time-grouped randomization of Wu et al. [2022],
Theorem 33 (Growing-blocks rate). Let ( 𝒃𝑛 ) be an infinite sequence of blockings (Definition 21) whose average block size increases without bound, lim 𝒃𝑛 = ∞. Then, for all 𝑐 ∈ C , the bias and the standard deviation vanish: lim E [ Δ̂𝑐 − 𝛿𝑐 | 𝛽 ( 𝒃𝑛 )] = 0,
𝑛→∞
6 Actually, in Google Benchmark, the order is not fully random as a number of runs of the same function are grouped into chunks to avoid measurement problems due to tiny durations, and these chunks are shuffled, but that still fits within 𝛽 -experiments. 6 https://github.com/google/benchmark/issues/1051
11
lim Std [ Δ̂𝑐 | 𝛽 ( 𝒃𝑛 )] = 0.
The value of a state 𝑠 is the success probability 𝑉 ( 𝑠) = 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 | 𝑠) . In terminal states (𝑟 = 𝑛), where 𝜖¯𝑓 − 𝜖¯𝑔 = 𝜎 F/𝑛, the success probabilities are either 0 or 1. For 𝑟 ∈ [ 1, 𝑛) , the value update is
𝑛→∞
Furthermore, the rate for both is 𝑂 ( 𝑛−1/2 ) if the block size grows exponentially, that is, 𝑏𝑛,𝑘 ( 𝑛 ) ∝ 𝑛 for some 𝑘 ( 𝑛) .
𝑉 ( 𝜎, 𝑟, 𝑛 𝑓 , 𝑛𝑔 ) 𝑛/2 − 𝑛 𝑓 = min 𝑉 ( 𝜎 + 𝑞, 𝑟 + 1, 𝑛 𝑓 + 1, 𝑛𝑔 ) 𝑞∈Q 𝑛−𝑟
The theorem is stated in terms of a sequence of blockings, for the following reasons. A blocked design defines behaviour in a single experiment with a finite number of runs, but for the analysis of asymptotics we obviously need infinitely many runs. With a given constant block size, the extension to infinity is uniquely determined, but in the general case it is not. One possibility is to work with a single blocking with infinitely many blocks, corresponding to a single experiment. Here, we instead consider an infinite sequence of finite blockings, which subsumes single experiments as the special case where subsequent blockings can only extend previous ones with new blocks. In addition, this approach is applicable to repeated experiments where, for example, there is a single block of increasing size.
+
Assumption 3. Because the distribution of the programspecific noise T 𝑖 is unknown, it cannot be marginalized out in the value update. Furthermore, it cannot be lumped together with the environmental noise because, unlike E𝑖 , we have T𝑖 ⊥ ⊥ ̸ 𝐹𝑖 | 𝝀<𝑖 , 𝜎𝑖 −1 . Thus, the DP calculation assumes no program-specific noise.
For a 𝛽 -design, we compute the worst-case success probability 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) for given 𝑛 ∈ ℕ and 𝜔 > 0. This cumulative distribution function is the inverse of the quantile function 𝑄 𝑝adv ; thus, we can find, for example by binary search, the minimum number of runs 𝑛 required to meet ′ ( 𝑔, 𝑓 ) at decision conany given decision threshold 𝑄𝛾dec ′ (Remark 8). We can similarly solve numericfidence 𝛾dec ally for 𝑛 to meet a given unambiguous region threshold ′ ( 𝑔, 𝑓 ) (Proposition 9), with decision 𝑆𝛾 = −𝑄𝛾′ ( 𝑓, 𝑔 ) − 𝑄𝛾dec confidence 𝛾dec and detection confidence 𝛾 . In the common case where 𝛾 = 𝛾dec , this simplifies to finding the smallest 𝑛 such that 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ −𝑆𝛾 /2) ⩾ 𝛾 . The calculation is performed with dynamic programming. After 𝑟 runs, the state is the quadruple ( 𝜎, 𝑟, 𝑛 𝑓 , 𝑛𝑔 ) , where 𝑟 ∑︁ 𝑖=1
𝝀𝑖 𝜖𝑖 ,
𝑛𝑓 =
𝑟 ∑︁ 𝑖=1
𝟙 𝑓𝑖 = 𝑓 ,
𝑛𝑔 =
𝑟 ∑︁
𝑉 ( 𝜎 − 𝑞, 𝑟 + 1, 𝑛 𝑓 , 𝑛𝑔 + 1) ,
𝑛−𝑟 where 𝑛 − 𝑟 , 𝑛/2 − 𝑛 𝑓 and 𝑛/2 − 𝑛𝑔 are the number of runs left in total, for 𝑓 and for 𝑔 , respectively. The size of the state space is 𝑂 ( 𝑛3 Q) because the range of 𝜎 grows linearly with 𝑟 , and 𝑛𝑔 = 𝑟 − 𝑛 𝑓 is fully determined. While this means that scalability is a problem, we will only use the DP approximation to compare the blocked design’s efficiency to that of the simple randomized design, which we explore next.
7.6 Dynamic Programming for 𝛽 -Designs
𝜎=
𝑛/2 − 𝑛𝑔
8 simple randomized experiments Our first experiment design chooses a program independently and uniformly at random for each run. In classical experiment design, this is called simple randomized design, where treatment assignments are sampled with replacement from the set of treatments (F, here). Definition 34 (Simple randomized design). A simple randomized experiment design (or 𝛼-design) is a delta design where, for every run 𝑖 ∈ [ 1, 𝑛] , the program 𝐹𝑖 is chosen uniformly and independently from the set of programs F .
𝟙𝑓𝑖 =𝑔.
𝑖=1
To avoid division by zero in ˆ𝐿 ( 𝑓, 𝑐) = 𝑇¯𝑓 , we must also require 𝑁 𝑓 > 0, which introduces slight dependencies in 𝑭.
To keep the action space tractable, the noise is quantized to the set Q = {0, ±1/Q, ±2/Q, . . . , ±1}, where Q ∈ ℕ is the number of quanta. By increasing Q, we can approximate the continuous case, where the noise can take any value in [−1, 1] . In ??, we will demonstrate experimentally that this approximation is very tight even with a moderate number of quanta. Conveniently, due to balancedness and our worst-case focus, runs of programs other than 𝑓 and 𝑔 can be ignored, and we can assume that F = 2 if 𝑛 is scaled by 2/F. Without loss of generality, we can also assume that M𝑐 = 1 as 𝜔 can be scaled by 1/M𝑐 otherwise.
8.1 Asymptotics Definition 35 (Shorthands). Let 𝐿𝑛 = P and Σ𝑛 = 𝑛𝑖=1 Λ𝑖 E𝑖 .
P𝑛
𝑖=1
Λ𝑖 , 𝐸 𝑛 =
P𝑛
𝑖=1
E𝑖
Proposition 36. Under the 𝛼-design with F = 2, we can express the noise difference as 2𝑛Σ𝑛 − 2 𝐿𝑛 𝐸𝑛 Ē 𝑓 − Ē 𝑔 = . 𝑛2 − 𝐿2𝑛
12
= min 0.5 𝑉 ( 𝜎𝑓 + 𝑞, 𝜎𝑔 , 𝑟 + 1, 𝑛𝑓 + 1, 𝑛𝑔 )
For the proof of this and other propositions in this section, see §D.
𝑞∈Q
+ 0.5 𝑉 ( 𝜎𝑓 , 𝜎𝑔 + 𝑞, 𝑟 + 1, 𝑛𝑓 , 𝑛𝑔 + 1) . The size of the state space is 𝑂 ( 𝑛4 Q2 ) because we must track two independent accumulated noise sums (𝜎𝑓 , 𝜎𝑔 ) alongside a 𝑛 𝑓 . Note that 𝑛𝑔 = 𝑟 − 𝑛𝑓 because F = 2. This scales significantly worse than the 𝛽 -design DP. In the following, we propose cheap approximations and verify them against these dynamic programming results in the computationally feasible range.
√
Theorem 37 (𝛼 noise 𝑛-consistency). For any configuration 𝑐 ∈ C and programs 𝑓, 𝑔 ∈ F , with the 𝛼-design, Ē 𝑓 − Ē 𝑔 = 𝑂𝑝 ( 𝑛−1/2 ) given 𝑵 > 0. Note that the theorem’s claim is about the worst-case: no matter how E𝑖 are chosen, the effect of the possibly autocorrelated environmental noise on averages decays at the same asymptotic rate as in the independent case, which implies that this worst-case rate is also the best possible.
8.2.2 Approximations
√
Theorem 38 (𝛼 𝑛-consistency). For any configuration 𝑐 ∈ C and programs 𝑓, 𝑔 ∈ F , with the 𝛼-design, Δ̂𝑐 − 𝛿𝑐 = 𝑂𝑝 ( 𝑛−1/2 ) given 𝑵 > 0.
To motivate the approximations developed later in this section, we first present a theorem characterizing the asymptotic behaviour of the estimator. Given the illustrative purpose of the theorem and the heuristic nature of the approximations it motivates, it adopts Ē ⊥ ⊥ Λ as a simplifying assumption that greatly reduces the complexity of the exposition. While the average noise Ē is clearly not independent from the coin flips Λ under our model, it can be viewed as a weak forgetting assumption.
8.2 Finite-Sample Behaviour Having established the asymptotic rate, we want to know how many runs to perform for a given level of confidence 𝛾 and minimum effect size 𝜔 . We propose three approaches for the F = 2 case, which we finally combine into a bound for the general case.
Proposition 39 (𝛼-approximation). Under an 𝛼-design with ˜ = 2 Σ𝑛 and 𝐶˜ = 2 𝐿𝑛 Ē . Assume F = 2 and 𝑛 runs, let 𝑀 𝑛 𝑛 worst-case noise and that the mean noise is independent of ⊥ Λ. Then, the program choices, Ē ⊥
8.2.1 Dynamic Programming for 𝛼-Designs For an 𝛼-design, we compute the worst-case success probability 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) for given 𝑛 ∈ ℕ and 𝜔 > 0. This parallels the DP approximation for the 𝛽 -design (§7.6), with the following notable differences: • The state space is larger as we need to track partial sums and run counts for 𝑓 and 𝑔 separately. • We cannot ignore programs other than 𝑓 and 𝑔 as their run counts are stochastic; to keep the state space size manageable, we restrict our analysis to F = 2. To handle more programs efficiently, we present a martingale-based approximation to this DP (Approximation 42) in the next section. After 𝑟 runs, the state is the quintuple ( 𝜎 𝑓 , 𝜎𝑔 , 𝑟, 𝑛 𝑓 , 𝑛𝑔 ) , where 𝑟 𝑟 𝜎𝑓 =
∑︁
𝟙𝑓𝑖 = 𝑓 𝜖𝑖 ,
𝜎𝑔 =
𝑖=1
𝑛𝑓 =
𝑟 ∑︁
˜ − 𝐶˜ + 𝑂𝑝 ( 𝑛−3/2 ) , Ē 𝑓 − Ē 𝑔 = 𝑀 ˜ 𝐶˜] = Var [𝐶˜] , Cov [ 𝑀, and consequently for the variance ˜ ] + 𝑂 ( 𝑛−2 ) . Var [ Ē 𝑓 − Ē 𝑔 ] ⩽ Var [ 𝑀 We now present two practical bounds for experimental planning with the 𝛼-design in the two-program case. Approximation 40 (Martingale approximation). Under an 𝛼-design with F = 2, 𝑛 runs, with any 𝜔 > 0,
𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 1 − exp
∑︁ 𝟙𝑓𝑖 =𝑔 𝜖𝑖
−𝑛𝜔2 . 8M2𝑐
𝑖=1
𝟙 𝑓𝑖 = 𝑓 ,
𝑖=1
𝑛𝑔 =
𝑟 ∑︁
See §D for the derivations of this and the following approximations.
𝟙𝑓𝑖 =𝑔 .
𝑖=1
Approximation 41 (Asymmetric approximation). Under an 𝛼-design with F = 2, 𝑛 runs, with any 𝜔 > 0,
In terminal states (𝑟 = 𝑛), if 𝑛 𝑓 > 0 and 𝑛𝑔 > 0, the value is 𝟙𝜎𝑓 /𝑛𝑓 − 𝜎𝑔 /𝑛𝑔 ⩽ 𝜔 ; otherwise, it is 0 (undefined means constitute failure). For 𝑟 ∈ [ 1, 𝑛) , the value update is
√
2
𝑛 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 2Φ 𝜔 −1 . 2M𝑐
𝑉 ( 𝜎 𝑓 , 𝜎𝑔 , 𝑟, 𝑛 𝑓 , 𝑛𝑔 )
13
Comparison with the dynamic programming solution suggests that the asymmetric approximation (Approximation 41) is better, so that is our recommendation for the two-program case. However, the martingale approximation (Approximation 40) admits a convenient closed-form generalization to more programs, as we show next.
1 0.8 0.6 𝛾
0.4
Approximation 42 (Martingale approximation for F > 2). Under an 𝛼-design with 𝑛 runs and any 𝜔 > 0, provided that the martingale approximation (Approximation 40) holds, 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 1 − 𝑝𝑒
−K
𝛼 DP1 𝛼 DP5 𝛼 DP10 𝛽 DP1 𝛽 DP5 𝛽 DP10
0.2 0
50
100
𝑛
+1− 𝑝 ,
150 𝑛
200
250
Figure 4: DP estimates of the worst-case confidence 𝛾 with the detection threshold 𝜔 set to 0.5M𝑐 for the 𝛼 (§8.2.1) and 𝛽 -designs (§7.6) with 1, 5 and 10 quanta. The sequence of quantized DP estimates decreases to the worst case confidence from above. Since the change from 5 to 10 is already quite small, we substitute the DP10 versions for the worst-case confidences.
2
where K = 𝜔 /( 8M2𝑐 ) and 𝑝 = 2/F. This provides a computationally trivial 𝑂 ( 1) approximation. 9 experiments In this section, we empirically evaluate the worst-case confidence 𝛾 of our experimental designs under adversarial noise, assuming F = 2. We utilize the dynamic programming (DP) formulation to compute numerical bounds and validate the analytical approximations derived in §8.2.2.
1 0.8 0.6 𝛾
𝛼 DP1 𝛼 DP5 𝛼 DP10 𝛽 DP1 𝛽 DP5 𝛽 DP10
9.1 Impact of Quantization
0.4
Because the dynamic programming approach relies on discretizing the state space, it inherently provides an upper bound on the true worst-case confidence. In Figures 4 to 6, we verify the effect of the number of quanta on the tightness of this bound. We compute the DP estimates for the 𝛼-design (§8.2.1) and the 𝛽 -design (§7.6) using 1, 5, and 10 quanta. We expect the sequence of quantized DP estimates to decrease towards the true worst-case confidence. However, the marginal improvement diminishes rapidly; the difference between the bounds computed with 5 and 10 quanta is already negligible across all tested sample sizes 𝑛. This justifies the use of the 10-quanta estimate (DP10) as a highly accurate proxy for the true worst-case confidence in the remainder of our experiments. Furthermore, across these three figures, as the detection threshold 𝜔 is progressively halved from 0.5M𝑐 to 0.125M𝑐 , the graphs stretch approximately by a factor of 4 along the horizontal axis, empirically confirming the 𝑂 ( 𝑛−1/2 ) scaling relationship.
0.2 0
50
100
150 𝑛
200
250
Figure 5: Dynamic programming estimates of the worst-case confidence 𝛾 with the detection threshold 𝜔 set to 0.25M𝑐 . As the threshold is halved compared to the previous figure, we see the graph being stretched 4 times along the 𝑛 axis. This stretching is approximate due to the discrete nature of the problem.
0.6
𝛾
0.4
𝛼 DP1 𝛼 DP5 𝛼 DP10 𝛽 DP1 𝛽 DP5 𝛽 DP10
0.2 0
9.2 Validation of Analytical Approximations Next, in Figures 7 to 9, we empirically validate the Asymmetric and the Martingale approximations at various fixed detection thresholds. We benchmark these analytical bounds against the DP10 estimates.
50
100
150 𝑛
200
250
Figure 6: Dynamic programming estimates of the worst-case confidence 𝛾 with the detection threshold 𝜔 set to 0.125M𝑐 . There is similar stretching of the graph as before.
14
We consistently observe that the Asymmetric approximation provides a much tighter bound than the Martingale approximation. At higher sample sizes, where the simplifying assumption Ē ⊥ ⊥ Λ begins to hold sufficiently, the analytical approximations cross over to become true lower bounds. However, as demonstrated in Figure 9, this crossover point occurs at relatively low confidence levels, which are generally irrelevant for rigorous benchmarking decisions. These figures also highlight the finite-sample vulnerabilities of the 𝛽 -design. Particularly at lower detection thresholds (e.g., 𝜔 = 0.25M𝑐 in Figure 8), the 𝛽 -design requires a substantially larger number of samples to achieve strictly positive confidence compared to the 𝛼-design.
1 0.8 𝛾
0.6 0.4
𝛼 DP10 𝛼 Asymmetric 𝛼 Martingale 𝛽 DP10
0.2 0
50
100
150 𝑛
200
250
Figure 7: Estimates of the worst-case confidence 𝛾 with the detection threshold 𝜔 set to 0.5M𝑐 . The dynamic programming approximations, 𝛼 DP10 (§8.2.1) and 𝛽 DP10 (§7.6), are with 10 quanta (Q = 10). The Asymmetric and the Martingale approximations for the 𝛼-design are discussed in §8.2.2.
9.3 Asymptotic Behavior at Constant 𝐾 Finally, to isolate the asymptotic convergence from the absolute threshold scaling, we evaluate the designs while √ holding the scale-invariant parameter 𝐾 = 𝜔 𝑛/M𝑐 constant. In Figures 10 to 15 (see §A), we plot the confidence for 𝐾 ∈ {1, 2, . . . , 6}. By definition, the Asymmetric and Martingale approximations remain perfectly constant for a given 𝐾 . In contrast, the true worst-case confidences (cap√ tured by the DP10 curves) are asymptotically 𝑂𝑝 ( 𝑛) and slowly flatten out towards the analytical limits as 𝑛 → ∞. This constant- 𝐾 perspective clearly illustrates how exploitability depends ont the sample size. For instance, at 𝐾 = 2 (Figure 11) and 𝑛 = 2, the limit can only be exceeded if the adversary successfully guesses the order of the two single runs, capping the confidence at 0.5. As 𝑛 increases while 𝐾 remains constant, the 𝛼-design successfully stabilizes around this level because it leaks minimal useful information to the adversary. Conversely, the 𝛽 -design’s sampling without replacement provides exploitable information, and its confidence decreases. Ultimately, these plots highlight how quickly real performance is dominated by the asymptotic rate. Because the analytical approximations provide reliable lower bounds at all but the smallest sample sizes and lowest confidence levels, relying on the DP approximation is necessary only in its computationally feasible range.
1 0.8 𝛾
0.6 0.4
𝛼 DP10 𝛼 Asymmetric 𝛼 Martingale 𝛽 DP10
0.2 0
50
100
150 𝑛
200
250
Figure 8: With the lower detection threshold of 𝜔 = 0.25M𝑐 , it becomes apparent that the 𝛽 -design needs a significant number of samples to achieve non-zero confidence.
0.6
𝛾
0.4
𝛼 DP10 𝛼 Asymmetric 𝛼 Martingale 𝛽 DP10
0.2 0
50
100
150 𝑛
200
250
9.4 Number of Runs Required
Figure 9: We halve the detection threshold in Figure 8 to 𝜔 = 0.125M𝑐 , roughly stretching the graph four times along the 𝑛 axis. We can see the 𝛼 approximations become lower bounds for large enough 𝑛, where the simplifying assumption Ē ⊥ ⊥ Λ made in §8.2.2 begins to hold to a sufficient degree. This crossover point is at low confidence levels, which are not important for the benchmarking decision problem.
From Figure 7, we can see that the 𝛼-design achieves detection threshold 0.5M𝑐 with confidence 0.9 at 𝑛 = 60, 30 runs for each program. From this point on, we can thus expect the number of runs required to approximately quadruple for each halving the detection threshold. The single-block 𝛽 -design requires significantly more runs to achieve the same confidence.
15
10 further considerations
10.3 The Single-Machine Case
10.1 Meanwhile in Classical Experiment Design
The decision problem arg min𝑓 ∈ F 𝑙 ( 𝑓 ) is invariant to positive affine transformations of the loss (scaling and shifting). Assumption 1 fits this strictly, as the uncontrolled state introduces only an additive bias to the run time. Assumption 2 is analogous, but it biases the logarithm of the run time. Since the total loss is a weighted sum of per-configuration losses, an additive bias on the run times becomes an additive constant in the objective function, leaving the optimal choice of program 𝑓 unchanged. However, simple invariance is lost if the scaling factor varies by configuration. In general, if the multiplicative noise A𝑐 depends on 𝑐, the weighted sum does not reduce to a single global affine transformation. Yet, in the specific case of a single machine (or a homogeneous cluster) – where configurations share identical hardware and system software, differing only in the benchmark task or input – it may be reasonable to assume the multiplicative noise is independent of the configuration. Formally, suppose that in a 𝛿-experiment 𝐿𝑖 = A𝑖 T 𝑖 + E𝑖 , where A𝑖 > 0 and A𝑖 ⊥ ⊥ 𝐶 . Then,
Our approach operates within the framework of randomized controlled experiments, which traditionally rely on the Stable Unit Treatment Value Assumption (SUTVA, Cox [1958], Angrist et al. [1996]) to identify the Average Treatment Effect (ATE). In our context, the ATE corresponds to 𝛿 ( 𝑓, 𝑔, 𝑐) . It is instructive to contrast our assumptions with SUTVA based on the definition of the experimental “unit.” • If we view the individual run as the unit, SUTVA posits non-interference: the outcome of run 𝑖 depends only on its own treatment ( 𝑓𝑖 ) and not on the history ( 𝒇<𝑖 ). In contrast, we explicitly acknowledge interference but impose an additivity assumption, requiring the performance differential between programs to be constant while the bias introduced by the system state varies. • Viewing the configuration as the unit (analogous to a patient), our framework resembles a repeated-measures design. Unlike in clinical trials, our units are infinitely reusable: the same configuration can be run multiple times. Here, our assumption corresponds to the SUTVA consistency requirement: the expected effect is stable across repeated applications of the same treatment. • If we view the uncontrolled state as the unit, our designs share the vulnerabilities of A \B testing in dynamic environments. Because the system state evolves based on previous treatments, the experiment alters the state trajectory, rendering the sample non-representative. In observational study methodology, such covariate shift is typically addressed via re-weighting or post-stratification. However, because the state in modern hardware is largely unobservable, these corrections are impossible. Instead, our designs leverage symmetry to ensure that these statedependent biases cancel out asymptotically, obviating the need to model the underlying distribution of strata.
E [ 𝐿𝑖 | 𝐹𝑖 = 𝑓, 𝑢1 ] = E𝐶𝑖 E [ 𝐿𝑖 | 𝐹𝑖 = 𝑓, 𝑢1 , 𝐶 = 𝐶 𝑖 ]
= E𝐶𝑖 E [ A𝑖 T 𝑖 + E𝑖 | 𝐹𝑖 = 𝑓, 𝑢1 , 𝐶 = 𝐶 𝑖 ] = E𝐶𝑖 E [ A𝑖 | 𝑢1 ] E [ T | 𝑓, 𝑐 = 𝐶 𝑖 ] + E [ E𝑖 | 𝑢1 ] = E [ A 𝑖 | 𝑢1 ] E [ T | 𝑓 ] + E [ E 𝑖 | 𝑢1 ] . It follows that E [𝑇¯𝑓 | 𝑢1 ] is a positive affine transformation of E [ T | 𝑓 ] , where the transformation parameters depend only on the noise 𝑢1 and not on the program 𝑓 . Consequently, the decision problems in the scaled and unscaled domains are equivalent. 10.4 Aggregation Over Configurations The preceding analysis focused on single-configuration estimates, ˆ𝐿 ( 𝑐, 𝑓 ) . We now address the estimation of expected performance over the full configuration space, C . For finite P and tractable C , this expectation is exact: 𝑐 ∈ C 𝑃 ( 𝑐) ˆ𝐿 ( 𝑐, 𝑓 ) . In practice, however, C is often effectively infinite or physically inaccessible. More critically, the set of evaluable configurations is constrained by the manual effort required to construct them (e.g., authoring benchmarks or curating input datasets). Consequently, standard practice restricts evaluation to a fixed subset of configurations. We offer further statistical interpretations of this practice: • Bias–variance tradeoff: We accept a biased estimator (the fixed set) to eliminate the variance inherent in sampling configurations.
10.2 Concurrent Execution In our measurement model, programs run sequentially in a given configuration. We can generalize this concurrent execution on multiple identical machines if we assume that the programs run on one have no effect on the others. In this case, the measurements gathered can be simply averaged as if they came from a single machine. However, if execution units have more tightly coupled states (e.g. a single multi-core machine), the interactions between concurrently running programs can depend on their alignment in time. This can easily violate the crucial assumption that the uncontrolled state affects all programs the same way.
16
Representative performance: We assume that absolute performance on the fixed subset approximates the global expectation. • Representative contrasts: We assume that the performance differentials between programs are preserved on the subset, even if absolute performance is not.
not address the potential bias and non-vanishing variance caused by the uncontrolled state.
•
10.7 Taking the Minimum Another option is to take the minimum measurement instead of the mean, based on the idea that the environment can only slow programs down. Chen and Revels [2016] justify the minimum estimator and propose an automated scheme to find the optimal number of loop iterations (blocking) to balance timer resolution against noise probability, empirically demonstrating that this minimum estimator converges robustly to what they deem the true execution time. However, their method implicitly relies on the noise process being memoryless and sparse.
10.5 Combining Experiments The results presented consider estimates ˆ𝐿 ( 𝑓 ) and ˆ𝐿 ( 𝑔 ) obtained from the same experiment. In practice, we may have only a subset of F available, as is the case in a continuous integration pipeline where all versions of a program up to the present are to be compared [Alcocer and Bergel, 2015, Grambow et al., 2019]. We could then benchmark, for example, each new version against only the previous one, and to compare versions further apart, we would sum a chain of deltas across different experiments. As long as the set of configurations is the same, and our assumptions hold, the deltas are additive in expectation7 due to asymptotic unbiasedness, and we can plot performance changes relative to an arbitrary reference point. The resulting estimator is consistent, but in the finite case, care should be taken because this procedure may accentuate experimental noise. The resulting decrease in confidence can be accounted for by the Bonferroni correction (based on the chain length) in the worst case. For plotting the performance over the course of development, we can instead benchmark all versions against the same reference point. However, if distant versions are very different – say, disk-based caching was added to a previously completely CPU-bound algorithm – then the ceteris paribus assumptions may not hold.
11 conclusions We argued that the prevalence of uncontrolled states renders the estimation of individual program performance intractable. In response, we formalized benchmarking as a decision problem and developed a largely self-contained framework based on blocked and simple randomized experiment designs. We showed that focussing on deltas enables consistent estimation at an asymptotically optimal rate, sufficient to identify the fastest program while providing probabilistic guarantees in the finite regime. We also analyzed alternative benchmarking methodologies (§7.4.1, §7.4.2) within the class of blocked experiments and found them theorectically less robust in the absence of strong assumptions about noise dynamics. On the surface, these methods are appealing, as they empirically reduce the sample variance of the estimates; however, they account for neither the bias nor the asymptotic variance. This oversight may render them inconsistent under unknown environmental dynamics. Moreover, it precludes the development of probabilistic guarantees for the decision-making process. Future work could focus on improving sample efficiency by relaxing the assumption of bounded noise magnitude. Incorporating ancillary statistics offers a promising path forward. Additionally, our theoretical results rely on the assumption that uncontrolled states affect all programs additively. Where this does not hold, additional factors must be controlled [Mytkowicz et al., 2009]; detecting the presence of these factors, identifying them, and determining when they are significant remains an open challenge. In summary, by enabling the reliable detection of small performance differences, our method supports the optimization of critical software infrastructure, including compilers, machine learning frameworks, and database systems.
10.6 Differential Timing Alexandrescu [2015] mentions a benchmarking technique where the performance ratio of the baseline and the contender programs are estimated from two measurements: 𝑡2𝑛𝑏 , the run time of 2𝑛 runs of baseline, and 𝑡𝑛𝑏+𝑛𝑐 , the run time of 𝑛 runs of the baseline followed by 𝑛 runs of the contender. Denoting the true runtimes with 𝑏 and 𝑐, the proposed formula to estimate the performance ratio is 2𝑛𝑏 𝑏 𝑡2𝑛𝑏 ≈ = , 2𝑡𝑛𝑏+𝑛𝑐 − 𝑡2𝑛𝑏 2𝑛𝑏 + 2𝑛𝑐 − 2𝑛𝑏 𝑐 with the idea that “some overhead noises cancel out”. The crucial difference from our proposal is that running the baseline 𝑛 times and then the contender 𝑛 times does 7 Indicating different experiments with a subscript, E [ ˆ𝐿1 ( 𝑓 ) − ˆ𝐿1 ( 𝑔 ) + ˆ𝐿2 ( 𝑔 ) − ˆ𝐿2 ( ℎ ) ] = E [ ˆ𝐿 ( 𝑓 ) − ˆ𝐿 ( 𝑔 ) ] + E [ ˆ𝐿 ( 𝑔 ) − ˆ𝐿 ( ℎ ) ] = E [ ˆ𝐿 ( 𝑓 ) − ˆ𝐿 ( ℎ ) ] .
17
acknowledgements
istically rigorous Java performance evaluation. ACM SIGPLAN Notices, 42(10):57–76, 2007.
We thank William Cohen for the valuable review. Joseph Yossi Gil, Keren Lenz, and Yuval Shimron. A microbenchmark case study and lessons learned. In Proceedings of the compilation of the co-located workshops on DSM’11, TMC’11, AGERE! 2011, AOOPES’11, NEAT’11, & VMIL’11, pages 297–308, 2011.
references Juan Pablo Sandoval Alcocer and Alexandre Bergel. Tracking down performance variation against source code evolution. ACM SIGPLAN Notices, 51(2):129–139, 2015.
Claude Godreche. Longest interval between zeros of the tied-down random walk, the Brownian bridge and related renewal processes. Journal of Physics A: Mathematical and Theoretical, 50(19):195003, 2017.
Andrei Alexandrescu. Writing fast code, 2015. URL https:// www.youtube.com/watch?v=vrfYLlR8X8k&t=914s. Accessed: 2024-08-25. Joshua D Angrist, Guido W Imbens, and Donald B Rubin. Identification of causal effects using instrumental variables. Journal of the American statistical Association, 91 (434):444–455, 1996.
Google Benchmark library, 2020. URL https://github. com/google/benchmark/. Accessed: 2024-04-14. Constantinos Goutis and George Casella. Frequentist postdata inference. International Statistical Review/Revue Internationale de Statistique, pages 325–344, 1995.
Edd Barrett, Carl Friedrich Bolz-Tereick, Rebecca Killick, Sarah Mount, and Laurence Tratt. Virtual machine warmup blows hot and cold. Proceedings of the ACM on Programming Languages, 1(OOPSLA):1–27, 2017.
Martin Grambow, Fabian Lehmann, and David Bermbach. Continuous benchmarking: Using system benchmarking in build pipelines. In 2019 IEEE International Conference on Cloud Engineering (IC2E), pages 241–246. IEEE, 2019.
George Casella. Conditional inference from confidence sets. Lecture Notes-Monograph Series, pages 1–12, 1992.
Wilhelm Hasselbring. Benchmarking as empirical standard in software engineering research. In Proceedings of the 25th International Conference on Evaluation and Assessment in Software Engineering, pages 365–372, 2021.
Jiahao Chen and Jarrett Revels. Robust benchmarking in noisy environments. arXiv preprint arXiv:1608.04295, 2016. Tianshi Chen, Qi Guo, Olivier Temam, Yue Wu, Yungang Bao, Zhiwei Xu, and Yunji Chen. Statistical performance comparisons of computers. IEEE Transactions on Computers, 64(5):1442–1455, 2014.
Walter Katzenbeisser and Peter Hackl. An alternative to the kolmogrov-smirnov two-sample test. Communications in Statistics-Theory and Methods, 15(4):1163–1177, 1986. Walter Katzenbeisser and Wolfgang Panny. A note on the higher moments of the random variable t associated with the number of returns of a simple random walk. Advances in applied probability, 18(1):279–282, 1986.
David Roxbee Cox. Planning of experiments. Wiley, 1958. Charlie Curtsinger and Emery D Berger. Stabilizer: Statistically sound performance evaluation. ACM SIGARCH Computer Architecture News, 41(1):219–228, 2013.
Thomas S Kuhn. The structure of scientific revolutions, volume 962. University of Chicago press Chicago, 1997.
Denis Bazhenov. Paired benchmarking: How to measure performance, 2023. URL https://www.bazhenov.me/ posts/paired-benchmarking/. Accessed: 2024-03-03.
John R Mashey. War of the benchmark means: Time for a truce. ACM SIGARCH Computer Architecture News, 32(4): 1–14, 2004.
William Feller. An introduction to probability theory and its applications. John Wiley & Sons, 3 edition, 1968. ISBN 978-0-471-25708-0.
Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, and Peter F Sweeney. Producing wrong data without doing anything obviously wrong! ACM Sigplan Notices, 44(3): 265–276, 2009.
Andy Georges, Dries Buytaert, and Lieven Eeckhout. Stat-
18
John von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton University Press, Princeton, NJ, USA, 1944. Susan Elliott Sim, Steve Easterbrook, and Richard C Holt. Using benchmarking to advance research: A challenge to software engineering. In 25th International Conference on Software Engineering, 2003. Proceedings., pages 74–83. IEEE, 2003. SPEC. SPEC CPU2006 Benchmarks, 2006. URL http:// www.spec.org/cpu2006/. Accessed: 2024-08-20. Janson Svante. Some pairwise independent sequences for which the central limit theorem fails. Stochastics: An International Journal of Probability and Stochastic Processes, 23(4):439–448, 1988. Walter F Tichy. Should computer scientists experiment more? Computer, 31(5):32–40, 1998. Wikipedia. Dynamic frequency scaling, 2024. URL https://en.wikipedia.org/w/index.php?title= Dynamic_frequency_scaling&oldid=1215993085. Accessed: 2024-08-20. Yuhang Wu, Zeyu Zheng, Guangyu Zhang, Zuohua Zhang, and Chu Wang. Non-stationary A \B tests. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2079–2089, 2022.
19
1
a figures for experimental results 0.2
𝛾
𝛾
0.9
0.1
𝛼 DP10 𝛼 Martingale
0.8 𝛼 DP10 𝛼 Martingale
𝛼 Asymmetric 𝛽 DP10
20
40
80
60
𝛼 Asymmetric 𝛽 DP10
100
120
140
𝑛
0 20
40
80
60
100
120
140
Figure 13: Estimates of the worst-case confidence 𝛾 for 𝐾 = 4.
𝑛 Figure 10: Estimates √ of the worst-case confidence 𝛾 for 𝐾 = 1, where 𝐾 = 𝜔 𝑛/M𝑐 . For a given 𝐾 , the Asymmetric and Martingale approximations are constant, while both the 𝛼 and √ 𝛽 -designs are asymptotically 𝑂𝑝 ( 𝑛 ) , so their curves flatten out. Note that the confidence for the 𝛽 -design is constant zero here. Also, the crossover point (as in Figure 9) is at low confidences.
1
𝛾
0.98 0.96
0.6
0.94
0.5
0.92
𝛼 DP10 𝛼 Martingale
20
40
80
60
𝛼 Asymmetric 𝛽 DP10
100
120
140
𝛾
𝑛
0.4 Figure 14: Estimates of the worst-case confidence 𝛾 for 𝐾 = 5.
0.3
𝛼 DP10 𝛼 Martingale
𝛼 Asymmetric 𝛽 DP10
0.2
1 20
40
80
60
100
120
140
𝑛
𝛾
Figure 11: Estimates of the worst-case confidence 𝛾 for 𝐾 = 2. At 𝑛 = 2,√we have 𝑛 𝑓 = 𝑛𝑔 = 1 for both the 𝛼 and 𝛽 -designs and that 𝜔 = 2M𝑐 . This limit can only be exceeded if the adversarial noise process guesses the order of the single runs of 𝑓 and 𝑔 , which has probability 0.5. As 𝑛 increases, the 𝛼-design stabilizes around that level as there is minimal information to exploit. On the other hand, the 𝛽 -design gets increasingly more exploitable.
0.99 𝛼 DP10 𝛼 Martingale
0.98
20
40
80
60
𝛼 Asymmetric 𝛽 DP10
100
120
140
𝑛 Figure 15: Estimates of the worst-case confidence 𝛾 for 𝐾 = 6.
1
𝛾
𝛼 DP10 𝛼 Martingale
𝛼 Asymmetric 𝛽 DP10
0.8
0.6 20
40
80
60
100
120
140
𝑛 Figure 12: Estimates of the worst-case confidence 𝛾 for 𝐾 = 3.
20
b proofs for section deltas to dections
𝑃 ( Δ̂ ( 𝑓, 𝑔 ) − 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑈𝑛 ) ⩾
If the true deltas for some 𝑓 ∈ F are in the corresponding unambiguous region, meaning and 𝛿 ( 𝑓, 𝑔 ) < 0
for all 𝑔 ≠ 𝑓 , then this 𝑓 is the unique fastest program, and the decision rule picks 𝑓 with probability at least 𝛾 . Proof. The condition 𝛿 ( 𝑓, 𝑔 ) < 0 for all 𝑔 ≠ 𝑓 directly implies that 𝑓 is strictly faster than any other program. Uniqueness follows from the antisymmetry of 𝛿 ( 𝑓, 𝑔 ) . We now prove that the decision rule picks 𝑓 with probability at least 𝛾 . By Remark 8, 𝑓 is picked if 𝛿ˆ( 𝑓, 𝑔 ) ⩽ ′ ( 𝑔, 𝑓 ) for all 𝑔 ≠ 𝑓 . Expanding Δ̂ ( 𝑓, 𝑔 ) = 𝛿 ( 𝑓, 𝑔 ) + −𝑄𝛾dec 𝑍 ( 𝑓, 𝑔 ) , the condition for a given 𝑔 becomes
∑︁
max ( 0, 𝑈𝑛 ) = max 0,
′ ( 𝑔, 𝑓 ) . 𝛿 ( 𝑓, 𝑔 ) + 𝑍 ( 𝑓, 𝑔 ) ⩽ −𝑄𝛾dec
⩽ 𝐾𝜙 ( 𝑛)
,
𝑐 ∈S′
𝑃 ( 𝑐)𝑈𝑛𝑐 ⩽
∑︁
𝑐 ∈C
𝑐 ∈C
∑︁
𝑃 ( 𝑐) = 𝐾𝜙 ( 𝑛) .
𝑃 ( 𝑐) max ( 0, 𝑈𝑛𝑐 )
𝑐 ∈C
Substituting the upper bound for the true delta, 𝛿 ( 𝑓, 𝑔 ) ⩽ ′ ( 𝑔, 𝑓 ) , the above condition is 𝑆𝛾 ( 𝑓, 𝑔 ) = −𝑄𝛾′ ( 𝑓, 𝑔 ) − 𝑄𝛾dec implied by
Thus, max ( 0, 𝑈𝑛 ) = 𝑂 ( 𝜙 ( 𝑛)) .
□
Proposition 13 (Consistency of the decision rule). Assume there is a unique fastest program 𝑓 ∈ F . If the estimator Δ̂ is upper consistent, then
′ ( 𝑔, 𝑓 ) + 𝑍 ( 𝑓, 𝑔 ) ⩽ −𝑄𝛾 ′ ( 𝑔, 𝑓 ) , −𝑄𝛾′ ( 𝑓, 𝑔) − 𝑄𝛾dec dec
which simplifies to 𝑍 ( 𝑓, 𝑔 ) ⩽ 𝑄𝛾′ ( 𝑓, 𝑔 ) . We need this sufficient condition to hold for all F − 1 programs 𝑔 ≠ 𝑓 . By the definition of the quantile, 𝑃 ( 𝑍 ( 𝑓, 𝑔 ) ⩽ 𝑄𝛾′ ( 𝑓, 𝑔 )) ⩾ 𝛾 ′ for any single 𝑔 . Taking a union bound, the probability that the condition fails for at least one 𝑔 is at most
𝑔≠ 𝑓
𝛼𝑐
Proof. Let 𝐸 𝑐 be the failure event Δ̂𝑐 ( 𝑓, 𝑔 ) − 𝛿𝑐 ( 𝑓, 𝑔 ) > 𝑈𝑛𝑐 , where 𝑃 ( 𝐸 𝑐 ) ⩽ 𝛼𝑐 . For any part S ′ ∈ S , arbitrary dependencies may exist between configurations (Definition 2). By Boole’s inequality, the probability that at least one configuration in S ′ fails is bounded by the sum of their individual S P failure probabilities: 𝑃 ( 𝑐 ∈ S ′ 𝐸 𝑐 ) ⩽ min ( 1, 𝑐 ∈ S ′ 𝛼𝑐 ) . Consequently, the probability that all configurations within S ′ P succeed is at least 1 − min ( 1, 𝑐 ∈ S ′ 𝛼𝑐 ) . By the independence of parts, their success probabilities combine multiplicatively, yielding the stated probabilistic upper bound. For the second claim, by the linearity of the estimators and the true deltas, we have Δ̂ ( 𝑓, 𝑔 ) − 𝛿 ( 𝑓, 𝑔 ) = P 𝑐 𝑐 𝑐 𝑐 ∈ C 𝑃 ( 𝑐) ( Δ̂ ( 𝑓, 𝑔 ) − 𝛿 ( 𝑓, 𝑔 )) . If the success event Δ̂ ( 𝑓, 𝑔 ) − 𝑐 𝑐 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑈𝑛 occurs for all 𝑐 ∈ C , then their convex comP bination guarantees Δ̂ ( 𝑓, 𝑔 ) − 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑐 ∈ C 𝑃 ( 𝑐)𝑈𝑛𝑐 = 𝑈𝑛 . Since max ( 0, 𝑈𝑛𝑐 ) ⩽ 𝐾𝜙 ( 𝑛) for some 𝐾 independent of 𝑐, P and 𝑐 ∈ C 𝑃 ( 𝑐) = 1, it follows that
′ ( 𝑔, 𝑓 ) . 𝑆𝛾 ( 𝑓, 𝑔 ) = −𝑄𝛾′ ( 𝑓, 𝑔 ) − 𝑄𝛾dec
( 1 − 𝛾 ′ ) = ( F − 1)
∑︁
and max ( 0, 𝑈𝑛 ) = 𝑂 ( 𝜙 ( 𝑛)) .
Proposition 9 (Unambiguous region). Let 𝛾 ⩾ 𝛾dec (the “detection confidence”), and let 𝛾 ′ = 1 − ( 1 − 𝛾 )/( F − 1) . We define the separation threshold 𝑆𝛾 ( 𝑓, 𝑔 ) as
∑︁
1 − min 1,
S′ ∈S
Here and in the following sections, we restate theorems and provide proof. The proofs in this section accompany §5.
𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑆𝛾 ( 𝑓, 𝑔 )
Y
lim 𝑃 ( decision rule picks 𝑓 ) = 1.
𝑛→∞
Proof. By Proposition 9, the decision rule picks 𝑓 with probability at least 𝛾 if 𝛿 ( 𝑓, 𝑔 ) ⩽ 𝑆𝛾 ( 𝑓, 𝑔 ) for all 𝑔 ≠ 𝑓 , where ′ ( 𝑔, 𝑓 ) . By Proposition 11, both 𝑆𝛾 ( 𝑓, 𝑔 ) = −𝑄𝛾′ ( 𝑓, 𝑔 ) − 𝑄𝛾dec ′ 𝑄𝛾′ and 𝑄𝛾dec vanish at rate 𝑂 ( 𝜙 ( 𝑛)) , thus 𝑆𝛾 ( 𝑓, 𝑔 ) → 0. Since 𝑓 is the unique fastest program, 𝛿 ( 𝑓, 𝑔 ) < 0 for all 𝑔 ≠ 𝑓 . For any 𝛾 < 1, there exists an 𝑁 such that for all 𝑛 > 𝑁 , 𝑆𝛾 ( 𝑓, 𝑔 ) ⩾ 𝛿 ( 𝑓, 𝑔 ) holds for every 𝑔 ≠ 𝑓 . Consequently, the probability of picking 𝑓 is at least 𝛾 for any 𝛾 < 1, which implies the limit is 1. □
1−𝛾 = 1 − 𝛾. F−1
Thus, the probability that the condition holds for all 𝑔 (and 𝑓 is picked) is at least 𝛾 . □ Proposition 11 (Suitewise upper consistency and rates). Let 𝑓, 𝑔 ∈ F . Assume that for each configuration 𝑐 ∈ C , the estimator Δ̂𝑐 ( 𝑓, 𝑔 ) of 𝛿𝑐 ( 𝑓, 𝑔 ) admits an upper bound 𝑈𝑛𝑐 such that 𝑃 ( Δ̂𝑐 ( 𝑓, 𝑔 ) − 𝛿𝑐 ( 𝑓, 𝑔 ) ⩽ 𝑈𝑛𝑐 ) ⩾ 1 − 𝛼𝑐 for some failure probability 𝛼𝑐 ∈ ( 0, 1) . Assume further that max ( 0, 𝑈𝑛𝑐 ) = 𝑂 ( 𝜙 ( 𝑛)) uniformly for all 𝑐 ∈ C . Let the suitewise bound be P 𝑈𝑛 = 𝑐 ∈ C 𝑃 ( 𝑐)𝑈𝑛𝑐 . Then, provided the sum and product exist, 𝑈𝑛 is a probabilistic upper bound satisfying
21
ignoring the clamping of E𝑖 to 𝜖′ when generating E 𝑖< . These two distributions define Σ𝑛 | 𝐶 ′ in the alternative model. Denoting the expectation under the alternative model with E′ , we have that
c proofs for blocked experiments The following subsections parallel those of §7 and provide proofs for the theorems stated there.
E′ [ Σ𝑛2 | 𝐶 ′ ] = E [( Σ𝑛 + Λ𝑖 𝛿) 2 | 𝐶 ]
c.1 Proofs for Single-Block Experiments
= E [ Σ𝑛2 | 𝐶 ] + 𝛿2 + 2𝛿 E [ Σ𝑛 Λ𝑖 | 𝐶 ] , where the sign of the third term is 𝜖′ sign ( E [ Σ𝑛 Λ𝑖 | 𝐶 ]) , so at least one of 𝜖′ = 1 and 𝜖′ = −1 makes it non-negative. Since 𝜖 ≠ 𝜖′, we have that 𝛿2 > 0, so
Here, we prove the theorems stated in §7.1 about the contraction rates of the variance and the bias of the Δ̂𝑐 estimator. To bound the bias and the variance of our estimators in single-block experiments, we explicitly construct the most adversarial noise processes E, which maximize | E [ Λ · E ] | or Var [ Λ· E ] and are closely related to the bias and the variance of the estimator Δ̂𝑐 in blocked designs via the unscaled P partial sum Σ𝑖 = 𝑗𝑖=1 Λ𝑗 E𝑗 (thus Σ𝑛 = Λ · E = Δ̂𝑐 ( 𝑓, 𝑔 ) F𝑛 ). We denote realizations of Σ𝑖 with 𝜎𝑖 . For simplicity, we assume that M𝑐 = 1, so | E𝑖 | ⩽ 1 for all 𝑖; our results apply to other cases modulo rescaling.
E′ [ Σ𝑛2 | 𝐶 ′ ] > E [ Σ𝑛2 | 𝐶 ] , strictly increasing the expectation for any non-extreme 𝜖, which contradicts either that the original model was optimal or that it assigns non-zero probability to | E𝑖 | < 1. □ Definition 44 (Greedy noise). In a delta design, we call the noise E greedy if E1 is drawn from a uniform distribution over {−1, 1}, while for 𝑖 ∈ [ 2, 𝑛] , given any 𝝀<𝑖 , 𝜎𝑖 −1 and 𝜖𝑖 −1 , with the shorthands 𝜓𝜎𝑖 = sign ( 𝜎𝑖 − 1 ) and 𝜓𝑖𝜆 = sign ( E [ Λ𝑖 | 𝝀<𝑖 ]) , the noise E𝑖 = 𝜓𝜎𝑖 𝜓𝑖𝜆 unless that is 0, in which case E𝑖 = 𝜖𝑖 − 1 .
c.1.1 Worst-Case Variance in Single-Block Experiments Aiming to characterize the worst case variance Var [ Λ · E ] = E [ Σ𝑛2 ] − E [ Σ𝑛 ] 2, we focus on how to maximize E [ Σ𝑛2 ] . First, we show that optimal (i.e. worst-case) noise can only take extreme values, which goes by the name of bang–bang control in control theory. Then, we identify the greedy strategy that maximizes the local expectation of Σ𝑖2 given the state after run 𝑖 − 1. Finally, we show that the greedy strategy is globally optimal and that E [ Σ𝑛 ] = 0 with it, so it also maximizes the variance. Also, since there is a fixed number of Λ𝑖 = 0 terms in a block, which affect neither the expectation nor the variance of Σ𝑛 = Λ · E , without loss of generality, we assume F = 2 in the proofs.
Although E𝑖 is conditioned only on 𝑈𝑖 in delta designs, the greedy strategy can be understood as encoding Λ<𝑖 , Σ𝑖 − 1 and E𝑖 −1 in 𝑈𝑖 . As we next show, greedy noise myopically maximizes the squared distance from the origin in all steps as its name suggests. Proposition 45 (Greedy step optimality). In a delta design, choosing E𝑖 greedily maximizes E [ Σ𝑖2 | 𝝀<𝑖 , 𝜎𝑖 − 1 ] for all 𝑖 ∈ [1, 𝑛] , 𝝀<𝑖 and 𝜎𝑖 −1 . Proof. Under the event ( 𝝀<𝑖 , 𝜎𝑖 − 1 ) , E [ Σ𝑖2 ] = E [( Σ𝑖 −1 + Λ𝑖 E𝑖 ) 2 ]
Proposition 43 (Optimality of bang–bang control). In a delta design, for any choice of distribution for E that maximizes E [( Λ · E ) 2 ] , the noise must be extreme almost surely, that is, 𝑃 (| E𝑖 | = 1) = 1 for all 𝑖 ∈ [ 1, 𝑛] .
= 𝜎2𝑖 −1 + E [ Λ2𝑖 E𝑖2 ] + 2𝜎𝑖 −1 E [Λ𝑖 E𝑖 ] = 𝜎2𝑖 −1 + E [ Λ2𝑖 E𝑖2 ] + 2𝜎𝑖 −1 E [Λ𝑖 ] E [ E𝑖 ] , where we used that Λ𝑖 ⊥ ⊥ E𝑖 | 𝝀<𝑖 in delta designs. Here, the first term is constant, and the second term is maximized by any E𝑖 ∈ {−1, 1}. As to the other non-constant term, 2𝜎𝑖 − 1 E [ Λ𝑖 ] E [ E𝑖 ] , it is maximized when E [ E𝑖 | 𝝀<𝑖 , 𝜎𝑖 − 1 ] = 𝜓𝜎𝑖 𝜓𝑖𝜆 , unless that is 0, in which case it is always 0 regardless of E𝑖 . Since the greedy strategy meets these conditions, it maximizes E [ Σ𝑖2 | 𝝀<𝑖 , 𝜎𝑖 − 1 ] for all 𝑖 ∈ [ 1, 𝑛] , 𝝀<𝑖 . □
Proof. Suppose that some choice of E maximizes E [ Σ𝑛2 ] , but 𝑃 (| E𝑖 | = 1) < 1 for some 𝑖. Then, there exists some 𝝀<𝑖 and 𝜎𝑖 − 1 such that 𝑃 ( 𝝀<𝑖 , 𝜎𝑖 − 1 ) > 0 and 𝑃 (| E𝑖 | < 1 | 𝝀<𝑖 , 𝜎𝑖 − 1 ) > 0. Observe that due to the delta design’s sequential structure, E also maximizes E [ Σ𝑛2 | 𝝀<𝑖 , 𝜎𝑖 − 1 ] . We are going to show that if E𝑖 = 𝜖 ∈ (−1, 1) , then its expectation can be increased under an alternative model with E𝑖 = 𝜖′ = ±1, so it cannot be optimal. Denote the events ( 𝝀<𝑖 , 𝜎𝑖 −1 , E𝑖 = 𝜖) and ( 𝝀<𝑖 , 𝜎𝑖 − 1 , E𝑖 = 𝜖′ ) with 𝐶 and 𝐶 ′ , respectively, and let 𝛿 = 𝜖′ − 𝜖. In the alternative model, we keep Λ𝑖⩽ | 𝝀<𝑖 the same as in the original, and we let E 𝑖< | 𝐶 ′ be the same as E 𝑖< | 𝐶 in the original as if
Assumption 4 (No flip). The more likely draw cannot flip sign in one step: Ψ𝑖𝜆 Ψ𝑖𝜆+1 ≠ −1 under any ( 𝝀<𝑖 , 𝜎𝑖 − 1 ) . Note that this assumption is true for all Λ based on sampling without replacement, which includes all block designs.
22
Proposition 46 (Greedy zero crossing). In a delta design with greedy noise satisfying Assumption 4 after runs [ 1, 𝑖 − 1] (𝑖 ∈ [ 1, 𝑛 − 1] ), 𝜓𝜎𝑖 ≠ 0 and 𝜓𝑖𝜆 ≠ 0 implies E𝑖+1 = E𝑖 under ( 𝝀<𝑖 , 𝜎𝑖 −1 ) .
and the non-greedy strategy, respectively, to determine the noise E𝑖 in run 𝑖: 𝐺 𝑖 ( 𝝀<𝑖 , 𝜎𝑖 − 1 )
= E [𝑉𝑖+1 (( 𝝀<𝑖 , Λ𝑖 ) , 𝜎𝑖 −1 + Λ𝑖 Ψ𝑖 ) | 𝝀<𝑖 , 𝜎𝑖 −1 ] 𝑁𝑖 ( 𝝀<𝑖 , 𝜎𝑖 − 1 ) = E [𝑉𝑖+1 (( 𝝀<𝑖 , Λ𝑖 ) , 𝜎𝑖 −1 − Λ𝑖 Ψ𝑖 ) | 𝝀<𝑖 , 𝜎𝑖 −1 ] ,
Proof. Let 𝝀𝑖 ∈ {−1, 1}. The greedy strategy deterministically sets 𝜖𝑖 = 𝜓𝜎𝑖 𝜓𝑖𝜆 since neither sign is 0. Greedy noise is ±1, so | 𝜎𝑖 − 𝜎𝑖 −1 | = | 𝝀𝑖 𝜖𝑖 | = 1. Furthermore, it follows that all sums are integer, so 𝜓𝜎𝑖+1 ∈ {𝜓𝜎𝑖 , 0} because 𝜎𝑖 − 1 ≠ 0. Similarly, from 𝜓𝑖𝜆 𝜓𝑖𝜆+1 ≠ −1 and 𝜓𝑖𝜆 ≠ 0, we have 𝜓𝑖𝜆+1 ∈ {𝜓𝑖𝜆 , 0}. If neither 𝜓𝜎𝑖+1 or 𝜓𝑖𝜆+1 is zero, then 𝜓𝑖+1 = 𝜓𝜎𝑖+1 𝜓𝑖𝜆+1 = 𝜓𝜎𝑖 𝜓𝑖𝜆 = 𝜓𝑖 . If either one is zero, then the greedy strategy repeats the noise from the most recent step where neither was zero, which is step 𝑖 in this case, so we have E𝑖+1 = E𝑖 for all 𝝀𝑖 . □
where Ψ𝑖 denotes the greedy noise. We also define 𝐺𝑛+1 ( 𝝀⩽ 𝑛 , 𝜎𝑛 ) = 𝑁𝑛 ( 𝝀⩽ 𝑛 , 𝜎𝑛 ) = 𝜎𝑛2 . From Ψ𝑖+1 = Ψ𝑖 by Proposition 46 and the exchangeability of Λ, we have that taking a non-greedy then a greedy step is the same as taking a greedy then a non-greedy step, but the induction hypothesis states that in the latter step, greedy is not worse than non-greedy, so it must be not worse in the former step, either. Formally, under the event ( 𝝀<𝑖 , 𝜎𝑖 − 1 ) ,
Proposition 47 (Worst-case noise). In any delta design, greedy noise that satisfies Assumption 4 maximizes Var [ Λ · E ] .
𝑁𝑖 ( 𝝀<𝑖 , 𝜎𝑖 − 1 )
= E [𝑉𝑖+1 (( 𝝀<𝑖 , Λ𝑖 ) , 𝜎𝑖 −1 − Λ𝑖 Ψ𝑖 )]
Let 𝑉𝑖 ( 𝝀<𝑖 , 𝜎𝑖 − 1 ) = maxE𝑖⩽ E [ Σ𝑛2
↓ by the induction hypothesis, 𝐺 𝑖+1 is optimal
Proof. | 𝝀<𝑖 , 𝜎𝑖 −1 ] be the maximum squared distance achievable from the given state by any noise strategy for the remaining runs. By Proposition 43, we restrict our attention to bang–bang strategies and show by backward induction that the greedy strategy maximizes 𝑉1 (∅, 0) = maxE E [ Σ𝑛2 ] . In the inductive base cases 𝑛 + 1 and 𝑛, 𝑉𝑛+1 ( 𝝀⩽ 𝑛 , 𝜎𝑛 ) = 𝜎𝑛2 leaves no noise to choose, making all strategies optimal, while for 𝑉𝑛 , Proposition 45 establishes greedy optimality for choosing E𝑛 . Inductive step. Let 1 ⩽ 𝑖 < 𝑛, and suppose that greedy E𝑗 is optimal for all 𝑗 > 𝑖 in all states 𝝀< 𝑗 , 𝜎𝑗 − 1 . Let 𝜎𝑖 − 1 and 𝝀<𝑖 be any state, 𝜓𝜎𝑖 = sign ( 𝜎𝑖 − 1 ) (𝑖 ∈ [ 1, 𝑛] ), the direction from 𝜎𝑖 − 1 leading away from zero, and 𝜓𝑖𝜆 = sign ( E [ Λ𝑖 | 𝝀<𝑖 ]) , the more likely flip. • If 𝜓𝜎 = 0 (i.e. 𝜎𝑖 − 1 = 0), then | 𝜎𝑖 | = 1 under any bang– 𝑖 bang control. By symmetry, 𝑉𝑗 ( 𝝀< 𝑗 , 𝜎𝑗 − 1 ) is an even function of 𝜎𝑗 , yielding 𝑉𝑖+1 (( 𝝀<𝑖 , 𝝀𝑖 ) , 1) = 𝑉𝑖+1 (( 𝝀<𝑖 , 𝝀𝑖 ) , −1) . Consequently, all bang–bang strategies are optimal. • If 𝜓 𝜆 = 0, then 𝑃 ( Λ𝑖 = 1 | 𝝀<𝑖 ) = 𝑃 ( Λ𝑖 = −1 | 𝝀<𝑖 ) , so 𝑖 Λ𝑖 E𝑖 | 𝝀<𝑖 has the same distribution for any bang–bang E𝑖 . Hence, once again, all bang–bang controls have the same value and are optimal. • This leaves the case where 𝜓𝜎 ≠ 0 and 𝜓 𝜆 ≠ 0. Note 𝑖 𝑖 that 𝑖 ≠ 1 here because 𝑖 = 1 implies 𝜎0 = 0 and 𝜓𝜎1 = 0. First, we address the deterministic case. With bang–bang strategies, there are only two values for E𝑖 to consider: −1 and 1. One of these corresponds to the greedy choice and the other to the opposite, non-greedy choice. We now show that the greedy choice is always at least as good as the non-greedy choice. For 𝑖 ∈ [ 2, 𝑛] , let 𝐺 𝑖 and 𝑁𝑖 be the maximum achievable when using the greedy
= E [𝐺 𝑖+1 (( 𝝀<𝑖 , Λ𝑖 ) , 𝜎𝑖 −1 − Λ𝑖 Ψ𝑖 )] = E [𝐺 𝑖+2 (( 𝝀<𝑖 , Λ𝑖 , Λ𝑖+1 ) , 𝜎𝑖 −1 − Λ𝑖 Ψ𝑖 + Λ𝑖+1 Ψ𝑖+1 )] ↓ since Ψ𝑖 = Ψ𝑖+1 and Λ𝑖⩽ | 𝝀<𝑖 is exchangeable
= E [𝐺 𝑖+2 (( 𝝀<𝑖 , Λ𝑖 , Λ𝑖+1 ) , 𝜎𝑖 −1 + Λ𝑖 Ψ𝑖 − Λ𝑖+1 Ψ𝑖+1 )] = E [ 𝑁𝑖+1 (( 𝝀<𝑖 , Λ𝑖 ) , 𝜎𝑖 −1 + Λ𝑖 Ψ𝑖 )] ↓ by the induction hypothesis again
⩽ E [𝐺 𝑖+1 (( 𝝀<𝑖 , Λ𝑖 ) , 𝜎𝑖 −1 + Λ𝑖 Ψ𝑖 )] = 𝐺 𝑖 ( 𝝀<𝑖 , 𝜎𝑖 −1 ) . Since the greedy value is always at least as good as the non-greedy one, the deterministic greedy strategy is not worse than any non-deterministic mixture, either. We have thus shown that if greedy is optimal for steps 𝑗 > 𝑖, then it is optimal for 𝑖, which concludes the induction. Hence, greedy is optimal for all 𝑖 ∈ [ 1, 𝑛] and maximizes 𝑉1 (∅, 0) = maxE E [ Σ𝑛2 ] . Since greedy maximizes E [ Σ𝑛2 ] and E [ Σ𝑛 ] = 0 by the symmetry provided by the first step, it follows that greedy also maximizes Var [ Σ𝑛 ] = E [ Σ𝑛2 ] − E [ Σ𝑛 ] 2 . □ Proposition 48. For the 𝛽 ( 𝑛) design, Var [ Λ · E ] = 𝑂 ( 𝑛) . Proof. We can restrict our attention to the greedy strategy because the no-flip assumption (Assumption 4) holds for blocked designs; thus, by Proposition 47, greedy noise maximizes variance. With the greedy algorithm, Σ𝑖 is a random walk that takes steps Λ𝑖 E𝑖 and is biased away from the simple random walk 𝑊𝑖 that takes ±1 steps with uniform probability. The greedy first step is randomized, and E [ Σ𝑖 ] = 0 for all 𝑖 due to the resulting symmetry. In-
23
Theorem 23. For the 𝛽 ( 𝑛) design, Var [ Δ̂𝑐 ] is 𝑂 ( 𝑛−1 ) .
tuitively, Var [ Σ𝑛 ] ⩾ Var [𝑊𝑛 ] = 𝑂 ( 𝑛) . However, what we need to show is that it is at most of that order. Let the rv 𝑍 𝑛𝜎 = { 𝑖 ∈ [ 1, 𝑛] : Ψ𝑖𝜎 = 0} and 𝑍 𝑛𝜆 = { 𝑖 ∈ [ 1, 𝑛] : Ψ𝑖𝜆 = 0}. • We first show that | Σ𝑛 | ⩽ 2 ( 𝑍 𝜎 + 𝑍 𝜆 ) . Split runs (indices) 𝑛 𝑛 into segments where Ψ𝑖𝜆 ≠ 0, and observe that each segment has the same number of 1s and −1s among its Λ𝑖 . Note that as long as 𝜓𝜎𝑖 ≠ 0, the number of hits and misses are almost equal. Almost because the first Λ𝑖 in the segment is going to be the rare one (equally likely at the time though), but we may get lucky and get it correct, turning a miss into a hit. Thus, the number of hits is either equal to the number of misses or greater by 2. Note that when the sum is zero, a miss has the same effect as a hit: it increases the sum by one in absolute value. So every time the sum is zero, a miss may be turned into a hit in effect. • Next, we show that E [( 𝑍 𝜎 ) 2 ] = 𝑂 ( 𝑛) . Recall that Ψ 𝜎 = 𝑛 𝑖 sign ( Σ𝑖 − 1 ) . For 𝛽 -designs, Σ𝑖 is a random walk whose distance from zero is biased to increase due to the greedy construction. Specifically, conditional on any history, the probability of Σ𝑖 moving away from zero is always at least 1/2, meaning 𝑃 (| Σ𝑖 | = | Σ𝑖 −1 | + 1 | | Σ𝑖 −1 | > 0) ⩾ 1/2. Because this outward probability is bounded from below by that of a simple symmetric random walk 𝑊𝑖 , the conditional distribution of the duration of any excursion from zero for Σ𝑖 is stochastically lower-bounded by the excursion duration of 𝑊𝑖 . By induction over the excursions, the time of the 𝑘-th return to zero for Σ𝑖 is stochastically larger than that for 𝑊𝑖 . Consequently, the total number of returns by step 𝑛 is stochastically 𝑊 2 smaller, meaning 𝑍𝑛𝜎 ⪯st 𝑍𝑊 𝑛 . Since E [( 𝑍 𝑛 ) ] is 𝑂 ( 𝑛) by Lemma 51, it follows that E [( 𝑍𝑛𝜎 ) 2 ] is also 𝑂 ( 𝑛) . P𝑖 • Third, we show that E [( 𝑍 𝜆 ) 2 ] = 𝑂 ( 𝑛) . Let 𝐿𝑖 = Λ 𝑛 𝑗=1 𝑗 for 𝑖 ∈ [ 0, 𝑛] . Observe that due to the balancedness of blocks, 𝐿𝑖 = 0 iff Ψ𝑖𝜆+1 = 0, so the number of times 𝐿𝑖 returns to zero is equal to 𝑍𝑛𝜆 . For 𝛽 -designs, 𝐿𝑖 is a tieddown random walk (i.e. 𝐿𝑛 = 0), and from Lemma 50 [Godreche, 2017], we have that E [( 𝑍𝑛𝜆 ) 2 ] = 𝑂 ( 𝑛) . Using the above,
Proof. Connecting greedy to the overall estimator variance for the balanced case yields Var [ Δ̂𝑐 ] = Var [ Λ̂ · 𝑻 ] = Var [ Λ̂ · T + Λ̂ · E ] Applying the law of total variance to the first term yields Var [ Λ̂ · T ] = Var E [ Λ̂ · T | 𝑭 ] + E Var [ Λ̂ · T | 𝑭 ] ↓ T are i.i.d given 𝑭 , so E [ Λ̂ · T | 𝑭 ] is constant
= E Var [ Λ̂ · T | 𝑭 ] ↓ by T being i.i.d given 𝑭 and by balancedness
= 𝑂 ( 𝑛−1 ) . Second, Var [ Λ · E ] is maximized by greedy as per Proposition 47, and we have shown it to be 𝑂 ( 𝑛) in Proposition 48. For blocked designs, Var [ Λ̂ · E ] = F2 𝑛−2 Var [ Λ · E ] , and consequently Var [ Λ̂ · E ] = 𝑂 ( 𝑛−1 ) . Finally, the covariance is upper bounded by the geometric mean of the first two terms: Cov [ Λ̂ · T , Λ̂ · E ] ⩽
□
c.1.2 Worst-Case Bias in Single-Block Experiments Here, we prove the rate of decay for the bias, via the construction of the worst-case noise process, which also allows to bound the bias in the finite regime. Theorem 24. For the 𝛽 ( 𝑛) design, E [ Δ̂𝑐 − 𝛿𝑐 ] = 𝑂 ( 𝑛−1/2 ) . Proof. We first show that since the noise is additive, the P bias is proportional to 𝑛𝑖=1 E [ Λ𝑖 E𝑖 ] : E [ Δ̂𝑐 − 𝛿𝑐 ] = E [( T̄ 𝑓 + Ē 𝑓 ) − ( T̄ 𝑔 + Ē 𝑔 ) − 𝛿𝑐 ]
= E [Ē 𝑓 − Ē 𝑔 + ( T̄ 𝑓 − T̄ 𝑔 ) − 𝛿𝑐 ] ↓ by E [ T̄ 𝑓 − T̄ 𝑔 ] = ( 𝑙 ( 𝑓, 𝑐 ) − E𝑈 [ E ] ) − ( 𝑙 ( 𝑔, 𝑐 ) − E𝑈 [ E ] ) = 𝛿𝑐
= E [ Ē 𝑓 − Ē 𝑔 ] 𝑛 F ∑︁ E [ Λ𝑖 E𝑖 ] . =
= E [( Λ · E ) 2 | 𝑛]
𝑛 𝑖=1
⩽ E [( 2𝑍𝑛𝜎 + 2𝑍𝑛𝜆 ) 2 ]
The terms of the sum can be maximized individually, which also maximizes the absolute value of E [ Δ̂𝑐 − 𝛿𝑐 ] . The ceteris paribus assumptions (Assumptions 1 and 2) posit that E𝑖 is generated from 𝑈𝑖 , but since Λ𝑖 ⊥ ⊥ 𝑈𝑖 | Λ<𝑖 , it suffices to choose E𝑖 based on Λ<𝑖 only. The law of total expectation gives E [ Λ𝑖 E𝑖 ] = E [ E [ Λ𝑖 E𝑖 | Λ<𝑖 ]] , where the inner expectation is maximized by E𝑖 = sign ( E [ Λ𝑖 | Λ<𝑖 ]) = − sign ( 𝐿𝑖 − 1 ) , P where 𝐿𝑖 − 1 = 𝑗𝑖=−11 Λ𝑗 is the sign of the more likely value of Λ𝑖 given the history so far.
↓ by the geometric–arithmetic mean inequality
⩽ 4 E [( 𝑍𝑛𝜎 ) 2 ] + E [( 𝑍𝑛𝜆 ) 2 ] + E [( 𝑍𝑛𝜎 ) 2 + ( 𝑍𝑛𝜆 ) 2 ] = 8 E [( 𝑍𝑛𝜎 ) 2 ] + E [( 𝑍𝑛𝜆 ) 2 ]
↓ because both expectations are 𝑂 ( 𝑛 )
= 𝑂 ( 𝑛) .
Var [ Λ̂ · T ] Var [ Λ̂ · E ] = 𝑂 ( 𝑛−1 ) .
Hence, Var [ Δ̂] is 𝑂 ( 𝑛−1 ) .
Var [ Λ · E | 𝑛]
= 4 E [( 𝑍𝑛𝜎 ) 2 ] + E [( 𝑍𝑛𝜆 ) 2 ] + 2 E [ 𝑍𝑛𝜎 𝑍𝑛𝜆 ]
√︃
□
24
weighted by 𝑃 ( 𝑘) = P𝑏𝑖𝑘𝑏𝑖 . Based on these observations, we can view individual blocks as per-configuration experiments, 𝑃 ( 𝑘) as the prior over these pseudo-configurations, and Δ̂𝑐 as the suitewise estimate Δ̂. To account for the dependencies between the initial states, we choose the trivial partition {[1, 𝑘]} for S . With these substitutions, Proposition 27 states that the bounds for the blocks combine linearly. □
With these optimal E𝑖 , the terms in the sum can be resolved as follows. E [ Λ𝑖 E𝑖 ] = E [ E [ Λ𝑖 E𝑖 | Λ<𝑖 ]] = E [ E𝑖 E [Λ𝑖 | Λ<𝑖 ]] − 𝐿𝑖 − 1 = E − sign ( 𝐿𝑖 −1 ) 𝑛−𝑖+1 E [| 𝐿𝑖 − 1 |] = . 𝑛−𝑖+1
c.3 Proofs Combining Per-Configuration Bounds
Plugging these back into the sum yields Here, we prove the theorems stated in §7.3.
𝑛−1 F ∑︁ E [| 𝐿𝑘 |] E [ Δ̂ − 𝛿 ] ⩽ 𝑛 𝑘=0 𝑛 − 𝑘 𝑐
𝑐
Proposition 27 (Δ̂𝑐 bounds to Δ̂). Assume that | E [ Δ̂𝑐 ] − 𝛿𝑐 | ⩽ 𝑏𝑐 and Std [ Δ̂𝑐 ] ⩽ 𝑠𝑐 for all 𝑐 ∈ C . Then, under the benchmark suite model with partition S of C ,
√︁ ↓ by E [ 𝐿𝑘 ] = 0 and Jensen’s inequality, E [ | 𝐿𝑘 | ] ⩽ Var [ 𝐿𝑘 ] 𝑛−1 F ∑︁ ⩽ 𝑛 𝑘=0
√︁
Var [ 𝐿𝑘 ]
E [ Δ̂] − 𝛿 ⩽
𝑛−𝑘
=
𝑛−1 F ∑︁ 1 𝑛 𝑘=0 𝑛 − 𝑘
= √
F
𝑛−1 ∑︁
∑︁ ∑︁
Var [ Δ̂] ⩽
𝑘 ( 𝑛 − 𝑘) 𝑛−1
√︂
2
𝑃 ( 𝑐) 𝑠𝑐 .
S′ ∈S 𝑐 ∈S′
Proof. From Δ̂ = 𝑐 ∈ C 𝑃 ( 𝑐) Δ̂𝑐 , then from 𝛿 = E [ 𝛿𝐶 ] and the law of total expectation with respect to 𝑈1𝑐 , we have
P
𝑘 . 𝑛−𝑘
E [ Δ̂] − 𝛿 =
∑︁
=
∑︁
c.2 Proofs for Multi-Block Experiments
⩽
∑︁
Here, we prove the theorems stated in §7.2.
=
𝑛 𝑛 − 1 𝑘=0
𝑃 ( 𝑐) 𝑏𝑐,
𝑐 ∈C
↓ ( 𝐿𝑘 + 𝑘 )/2 follows a hypergeometric distribution
√︂
∑︁
𝑃 ( 𝑐) E [ Δ̂𝑐 ] − 𝛿
𝑐 ∈C
As shown in Lemma 52, the sum is 𝑂 ( 𝑛) , from which the claim follows immediately. □
𝑃 ( 𝑐) E [ Δ̂𝑐 ] − 𝛿𝑐
𝑐 ∈C
𝑃 ( 𝑐) E [ Δ̂𝑐 ] − 𝛿𝑐
𝑐 ∈C
∑︁
𝑃 ( 𝑐) E E [ Δ̂𝑐 | 𝑈1𝑐 ] − 𝛿𝑐
𝑐 ∈C
Proposition 25 (Multi-block bounds). Let 𝒃 be a blocking and 𝑐 ∈ C . Assume that the per-block biases and standard deviations are bounded as E [ Δ̂𝑐 | 𝛽 ( 𝑏𝑘 )] − 𝛿𝑐 ⩽ 𝐵𝑘 ,
⩽
|𝒃| ∑︁ 𝑏𝑘 P 𝐵𝑘 , 𝑘=1
𝑖 𝑏𝑖
|𝒃| ∑︁ 𝑏𝑘 P 𝑆𝑘 . 𝑘=1
i
𝑐 ∈C
Std [ Δ̂𝑐 | 𝛽 ( 𝑏𝑘 )] ⩽ 𝑆𝑘
Std [ Δ̂𝑐 ] ⩽
h
𝑃 ( 𝑐) E E [ Δ̂𝑐 | 𝑈1𝑐 ] − 𝛿𝑐 .
Although 𝑏𝑐 is a bound in the context of the measurement model, with the initial state marginalized out, the distribution of 𝑈1 (as provided by the execution environment) is unknown and arbitrary. Hence, the bound must apply to any distribution, including deterministic ones, from which it follows that | E [ Δ̂𝑐 | 𝑈1𝑐 ] − 𝛿𝑐 | ⩽ 𝑏𝑐. Taking the expectation and a convex combination with respect to 𝑃 ( 𝑐) maintains this bound, establishing the first claim. Next, using Var [ 𝑋 +𝑌 ] = Var [ 𝑋 ]+Var [𝑌 ] for independent, and Var [ 𝑋 + 𝑌 ] ⩽ ( Std [ 𝑋 ] + Std [𝑌 ]) 2 by Cauchy–Schwarz for non-independent rvs, we get
for all 𝑘 ∈ [ 1, | 𝒃 |] . Then, these bounds combine linearly as E [ Δ̂𝑐 ] − 𝛿𝑐 ⩽
∑︁
𝑖 𝑏𝑖
Proof. We express Δ̂𝑐 as the sum of the per-block terms using the balancedness of blocks. Under 𝑐, |𝒃| |𝒃| ∑︁ F ∑︁ F 𝑏𝑘 Λ𝑘 · 𝑻 𝑘 = Δ̂𝑐 = P Λ · 𝑻 = P P Δ̂𝑘, 𝑖 𝑏𝑖 𝑖 𝑏𝑖 𝑘=1 𝑖 𝑏𝑖 𝑘=1
Var Δ̂ = Var
h ∑︁ ∑︁
𝑃 ( 𝑐) Δ̂𝑐
i
𝑃 ( 𝑐) Δ̂𝑐
i
S′ ∈S 𝑐 ∈S′
where Δ̂𝑘 = 𝑏F𝑘 Λ𝑘 · 𝑻 𝑘. Since Δ̂𝑘 is normalized by the number of runs of 𝑓 and 𝑔 (they are all 𝑏F𝑘 ), it is equivalent to Δ̂𝑐 | 𝛽 ( 𝑏𝑘 ) , the estimator for configuration 𝑐 in a single-block experiment of size 𝑏𝑘 except for its initial uncontrolled state. Furthermore, Δ̂𝑐 is a convex combination of the Δ̂𝑘 terms,
=
∑︁ S′ ∈S
⩽
Var
h ∑︁ 𝑐 ∈S′
∑︁ ∑︁ S′ ∈S 𝑐 ∈S′
25
2
𝑃 ( 𝑐) Std Δ̂𝑐
.
□
d proofs for simple randomized experiments
Proposition 28 ( 𝛽 moment-based noise quantile). Let 𝑏 ( 𝑛) and 𝑠 ( 𝑛) denote the respective suitewise bounds on the absolute bias and standard deviation of Δ̂ for a blocked design 𝛽 ( 𝑛) , where 𝑏 ( 𝑛) = 𝑂 ( 𝑛−1/2 ) and 𝑠 ( 𝑛) = 𝑂 ( 𝑛−1/2 ) . For any confidence level 𝑝 ∈ ( 0, 1) , the adversarial noise quantile 𝑄 𝑝adv is bounded as √︂ 𝑝 adv , 𝑄 𝑝 ⩽ 𝑏 ( 𝑛) + 𝑠 ( 𝑛) 1− 𝑝
The proofs in this section accompany §8. Proposition 36. Under the 𝛼-design with F = 2, we can express the noise difference as Ē 𝑓 − Ē 𝑔 =
2𝑛Σ𝑛 − 2 𝐿𝑛 𝐸𝑛
which contracts at a rate of 𝑂 ( 𝑛−1/2 ) .
𝑛2 − 𝐿2𝑛
.
Proof. We express Ē 𝑓 and Ē 𝑔 in terms of 𝐸𝑛 , 𝐿𝑛 and Σ𝑛 as
Proof. Applying Lemma 49 to the noise random variable 𝑍 = Δ̂ − 𝛿, we obtain the desired bound. From Theorem 23 and Theorem 24, combined through Proposition 27, we establish that both 𝑏 ( 𝑛) and 𝑠 ( 𝑛) are 𝑂 ( 𝑛−1/2 ) . Hence, their □ positive linear combination also scales as 𝑂 ( 𝑛−1/2 ) .
P𝑛 𝟙 E ( 𝐸𝑛 + Σ𝑛 )/2 𝐸𝑛 + Σ𝑛 𝑖=1 𝐹𝑖 = 𝑓 𝑖 Ē 𝑓 = P𝑛 = = , 𝟙 ( 𝑛 + 𝐿𝑛 )/2 𝑛 + 𝐿𝑛 𝑖=1 𝐹𝑖 = 𝑓 P𝑛 𝟙 E ( 𝐸𝑛 − Σ𝑛 )/2 𝐸𝑛 − Σ𝑛 𝑖=1 𝐹𝑖 =𝑔 𝑖 Ē 𝑔 = P𝑛 = = . 𝟙 ( 𝑛 − 𝐿𝑛 )/2 𝑛 − 𝐿𝑛 𝑖=1 𝐹𝑖 =𝑔 Combining Ē 𝑓 and Ē 𝑔 , we get Ē 𝑓 − Ē 𝑔 =
𝐸 𝑛 − Σ𝑛 𝐸 𝑛 + Σ𝑛 − . 𝑛 + 𝐿𝑛 𝑛 − 𝐿𝑛
Finding the common denominator yields the claim.
□
√
Theorem 37 (𝛼 noise 𝑛-consistency). For any configuration 𝑐 ∈ C and programs 𝑓, 𝑔 ∈ F , with the 𝛼-design, Ē 𝑓 − Ē 𝑔 = 𝑂𝑝 ( 𝑛−1/2 ) given 𝑵 > 0. Proof. We first prove the claim for the case F = 2. In this proof, we expediently ignore the condition 𝑵 > 0, whose probability tends to 1 exponentially fast. We first establish probabilistic rates for 𝐿𝑛 , 𝐸𝑛 and Σ𝑛 . √ • By the central limit theorem, 𝐿𝑛 = 𝑂𝑝 ( 𝑛) . • 𝐸 𝑛 , a sum of bounded terms, is trivially 𝑂𝑝 ( 𝑛) . • Since E [ Λ𝑖 E𝑖 | Λ<𝑖 , E <𝑖 ] = E [ Λ𝑖 ] E [ E𝑖 | Λ<𝑖 , E <𝑖 ] = 0, the sum Σ𝑛 is a martingale with bounded increments | Λ𝑖 E𝑖 | ⩽ √ M𝑐 . By the Azuma–Hoeffding inequality, Σ𝑛 = 𝑂𝑝 ( 𝑛) . For the numerator in Proposition 36, a valid asymptotic rate (an upper bound) is the highest of the stochastic orders of the terms 2𝑛Σ𝑛 and 2 𝐿𝑛 𝐸𝑛 . Using the previously established rates, both terms scale as 𝑛3/2 , so the numerator is 𝑂𝑝 ( 𝑛3/2 ) . P Moving on to the denominator, since 𝐿𝑛 = 𝑛𝑖=1 Λ𝑖 is a sum of bounded i.i.d. variables, the strong law of large numbers guarantees 𝐿𝑛 /𝑛 → 0 almost surely. We use concentration inequalities (Hoeffding’s or Chernoff ’s) to show that for any 𝑑 ∈ ( 0, 1) ,
√ 𝑃 (| 𝐿𝑛 | ⩾ 𝑛 1 − 𝑑 ) → 0
exponentially as 𝑛 → ∞.
This implies that 𝑃 ( 𝐿2𝑛 < ( 1 − 𝑑 ) 𝑛2 ) → 1. Therefore, the 2
denominator is bounded below by 𝑑𝑛 with probability approaching 1, establishing the necessary stochastic stability for division: 𝑛2 − 𝐿2𝑛 = Ω𝑝 ( 𝑛2 ) .
26
Finally, combining the numerator, which is bounded in probability at rate 𝑛3/2 , with the denominator, which is bounded away from zero at rate 𝑛2 , we get that Ē 𝑓 − Ē 𝑔 =
𝑂𝑝 ( 𝑛3/2 ) Ω𝑝 ( 𝑛2 )
i.i.d. Rademacher variables, 𝐿𝑛 follows a simple symmetric random walk with 𝐿𝑛 = 𝑂𝑝 ( 𝑛1/2 ) . We approximate the denominator as 1/𝑛2 with error 1
= 𝑂𝑝 ( 𝑛3/2−2 ) = 𝑂𝑝 ( 𝑛−1/2 ) ,
𝑛2 − 𝐿2𝑛
−
𝐿2 1 = 2 2 𝑛 2 = 𝑂𝑝 ( 𝑛−3 ) . 2 𝑛 𝑛 ( 𝑛 − 𝐿𝑛 )
Considering that the numerator is 𝑂𝑝 ( 𝑛3/2 ) , we approximate the noise difference as 2𝑛Σ𝑛 − 2 𝐿𝑛 𝐸𝑛
which completes the proof for F = 2. For F > 2, we consider the subsequence of runs where 𝐹𝑖 ∈ { 𝑓, 𝑔 }. Let 𝑀 be the random count of such runs. Conditioned on these runs, the experiment is equivalent to the F = 2 case with sample size 𝑀 , so the difference is 𝑂𝑝 ( 𝑀 −1/2 ) . Since 𝐹𝑖 is uniform, 𝑀 ∼ Binomial ( 𝑛, 2/F) , implying 𝑀 = Θ𝑝 ( 𝑛) . Therefore, the rate 𝑂𝑝 ( 𝑛−1/2 ) holds generally. □
Ē 𝑓 − Ē 𝑔 =
𝑛2 − 𝐿2𝑛 2𝑛Σ𝑛 − 2 𝐿𝑛 𝐸𝑛
+ 𝑂𝑝 𝑛−3/2 𝑛2 ˜ − 𝐶˜ + 𝑂𝑝 𝑛−3/2 , =𝑀 =
which proves the first claim. Note that this approximation slightly underestimates the variance for finite 𝑛; thus, the results derived here apply only for sufficiently large 𝑛, which we determine empirically. Next, we calculate Var [𝐶˜] . By the independence assumption from the theorem statement and using E [ 𝐿𝑛 ] = 0 as well P P as E [ 𝐿2𝑛 ] = E [( 𝑖 Λ𝑖 ) 2 ] = E [ 𝑖 Λ2𝑖 ] = 𝑛 (since E [ Λ𝑖 Λ𝑗 ] = 0 for 𝑖 ≠ 𝑗), we express the variance of the correction term as
√
Theorem 38 (𝛼 𝑛-consistency). For any configuration 𝑐 ∈ C and programs 𝑓, 𝑔 ∈ F , with the 𝛼-design, Δ̂𝑐 − 𝛿𝑐 = 𝑂𝑝 ( 𝑛−1/2 ) given 𝑵 > 0. Proof. Once again we ignore the exponentially decaying effect of the 𝑵 > 0 condition. Expanding the definitions of Δ̂𝑐 and 𝛿𝑐 and regrouping, we get
Var [𝐶˜] = E [𝐶˜2 ] − E [𝐶˜] 2 4 = 2 E [ 𝐿2𝑛 Ē 2 ] − E [ 𝐿𝑛 Ē ] 2 𝑛 4 = 2 E [ 𝐿2𝑛 ] E [ Ē 2 ] − E [ 𝐿𝑛 ] 2 E [ Ē ] 2 𝑛 4 = E [ Ē 2 ] . 𝑛
Δ̂𝑐 − 𝛿𝑐 = ( Ē 𝑓 − Ē 𝑔 ) + [( T̄ 𝑓 − 𝑙 ( 𝑓, 𝑐)) − ( T̄ 𝑔 − 𝑙 ( 𝑔, 𝑐))] . From Theorem 37, we already know that the first term is 𝑂𝑝 ( 𝑛−1/2 ) . As to the second term, we apply Theorem 37 a second time, with Ē 𝑓 = ( T̄ 𝑓 − E [ T | 𝐹 = 𝑓 ]) and Ē 𝑔 = ( T̄ 𝑔 − E [ T | 𝐹 = 𝑔 ]) , which have expectation zero. Since the theorem holds for any noise process, it holds in our case where T 𝑖 | 𝐹𝑖 = 𝑓 are independent by the properties of delta designs. Considering that 𝑙 ( 𝑓, 𝑐) = E [ T | 𝐹 = 𝑓 ] + 𝐶𝑈 and 𝑙 ( 𝑔, 𝑐) = E [ T | 𝐹 = 𝑔 ] + 𝐶𝑈 , where 𝐶𝑈 = E𝑈 [ E ] , we have □ that the second term is also 𝑂𝑝 ( 𝑛−1/2 ) .
Since independence implies Cov [ Λ𝑖 E𝑖 , Λ𝑗 Ē ] = 0 for 𝑖 ≠ 𝑗, we rewrite the covariance as ˜ 𝐶˜] = Cov [ 𝑀,
Proposition 39 (𝛼-approximation). Under an 𝛼-design with ˜ = 2 Σ𝑛 and 𝐶˜ = 2 𝐿𝑛 Ē . Assume F = 2 and 𝑛 runs, let 𝑀 𝑛 𝑛 worst-case noise and that the mean noise is independent of the program choices, Ē ⊥ ⊥ Λ. Then,
=
4 𝑛2 4 𝑛
=
˜ − 𝐶˜ + 𝑂𝑝 ( 𝑛−3/2 ) , Ē 𝑓 − Ē 𝑔 = 𝑀 ˜ 𝐶˜] = Var [𝐶˜] , Cov [ 𝑀,
=
and consequently for the variance ˜ ] + 𝑂 ( 𝑛−2 ) . Var [ Ē 𝑓 − Ē 𝑔 ] ⩽ Var [ 𝑀
=
Cov [ Σ𝑛 , 𝐿𝑛 Ē ]
Cov 2
h∑︁ 𝑖
4 ∑︁ ∑︁ 𝑛2
𝑖
4 ∑︁ 𝑛2
Λ𝑖 E𝑖 ,
Proof. We consider the noise difference 2𝑛Σ𝑛 − 2 𝐿𝑛 𝐸𝑛 𝑛2 − 𝐿2𝑛
from Proposition 36, where Σ𝑛 and 𝐿𝑛 are martingales. First, we approximate the denominator. Since the Λ𝑖 are
∑︁
i
Λ𝑗 Ē
𝑗
Cov [ Λ𝑖 E𝑖 , Λ𝑗 Ē ]
𝑗
Cov [ Λ𝑖 E𝑖 , Λ𝑖 Ē ]
𝑖
4 ∑︁ E [ Λ2𝑖 E𝑖 Ē ] − E [ Λ𝑖 E𝑖 ] E [ Λ𝑖 Ē ] 2 𝑛 𝑖 | {z } |{z} (±1 ) 2
Ē 𝑓 − Ē 𝑔 =
=
4 ∑︁ E [ E𝑖 Ē ] 𝑛2 𝑖
=
4 E [ Ē 2 ] . 𝑛
0
˜ 𝐶˜] = Var [𝐶˜] . Thus, we have proved that Cov [ 𝑀,
27
factors. First, if the martingale 2𝑛 Σ𝑖 > 𝜔 at any 𝑖, the adversary can set the rest of the noise to 0 to guarantee that ˜ > 𝜔 . Hence, we need the probability that the final value 𝑀 the running maximum of the martingale never exceeds the tolerance. By the reflection principle and using that the worst-case noise for the martingale is bang–bang, this is
Substituting these evaluations back into the variance expansion, we have ˜ − 𝐶˜ + 𝑂𝑝 𝑛−3/2 Var [ Ē 𝑓 − Ē 𝑔 ] = Var 𝑀
˜ − 𝐶˜] + Var 𝑂𝑝 𝑛−3/2 = Var [ 𝑀 ˜ − 𝐶, ˜ 𝑂𝑝 𝑛−3/2 + 2 Cov 𝑀 ˜ − 𝐶˜] + 𝑂 𝑛−3 = Var [ 𝑀 + 2 Cov 𝑂𝑝 𝑛−1/2 , 𝑂𝑝 𝑛−3/2 √︃ ˜ − 𝐶˜] + 𝑂 ( 𝑛−3 ) + 2 𝑂 𝑛−1 𝑂 𝑛−3 ⩽ Var [ 𝑀 ˜ ] + Var [𝐶˜] − 2 Cov [ 𝑀, ˜ 𝐶˜] + 𝑂 𝑛−2 = Var [ 𝑀 ˜ ] − Var [𝐶˜] + 𝑂 𝑛−2 . = Var [ 𝑀 Since Var [𝐶˜] ⩾ 0, the third claim follows.
𝑃 ∀𝑖 : 𝑘Σ𝑖 ⩽ 𝜔 = 2 𝑃 ( 𝑘𝑊𝑛 ⩽ 𝜔 ) − 1
= 2 𝑃 (𝑊𝑛 ⩽ 𝑘 −1 𝜔) − 1, where 𝑊𝑛 is the simple symmetric random walk and 𝑘 = 2M𝑐 𝑛−1 . Second, the optimal adversarial noise to push 𝐶˜ = 2𝑛 𝐿𝑛 Ē below −𝜔 is E𝑖 = − sign ( 𝐿𝑛 ) M𝑐 for all 𝑖. Since zero crossings in a random walk are rare by the arcsine law, an adversary can predict the final sign of the imbalance with high probability early in the sequence and commit to a sign for Ē that maximizes the error. Thus, we must bound the magnitude of the imbalance to ensure the correction term stays above −𝜔 . Noting that 𝐿𝑛 also behaves as a simple symmetric random walk, we derive
□
Approximation 40 (Martingale approximation). Under an 𝛼-design with F = 2, 𝑛 runs, with any 𝜔 > 0,
−𝑛𝜔2 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 1 − exp . 8M2𝑐
𝑃 ( 𝐶˜ ⩾ −𝜔 ) ⩾ 𝑃 ( 𝑘 | 𝐿𝑛 | ⩽ 𝜔 )
= 𝑃 (|𝑊𝑛 | ⩽ 𝑘 −1 𝜔) = 2 𝑃 (𝑊𝑛 ⩽ 𝑘 −1 𝜔) − 1. Derivation. While decreased variance does not strictly imply a tighter exponential tail, motivated by the variance bound ˜ ] from Proposition 39, we heuristically Var [ Ē 𝑓 − Ē 𝑔 ] ≲ Var [ 𝑀 posit that the concentration of the noise difference is no ˜ . We worse than that of its martingale approximation 𝑀 therefore bound the success probability using the Azuma– Hoeffding inequality, yielding ˜ ⩽ 𝜔 ) ⩾ 1 − exp 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 𝑃 ( 𝑀
Leveraging the positive correlation to treat the product as a conservative lower bound, we combine the previously derived bounds and take a normal approximation. Thus, our asymmetric bound is 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 )
⩾ 𝑃 (∀𝑖 : 𝑘Σ𝑖 ⩽ 𝜔) 𝑃 (𝐶˜ ⩾ −𝜔) 2 = 2 𝑃 (𝑊𝑛 ⩽ 𝑘 −1 𝜔) − 1 2 √ 𝑛 𝜔 −1 . ≈ 2Φ 2M𝑐
−𝑛𝜔2 . 8M2𝑐
Approximation 41 (Asymmetric approximation). Under an 𝛼-design with F = 2, 𝑛 runs, with any 𝜔 > 0,
𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 2Φ
√
Approximation 42 (Martingale approximation for F > 2). Under an 𝛼-design with 𝑛 runs and any 𝜔 > 0, provided that the martingale approximation (Approximation 40) holds,
2
𝑛 𝜔 −1 . 2M𝑐
𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 1 − 𝑝𝑒−K + 1 − 𝑝 ,
𝑛
where K = 𝜔 2 /( 8M2𝑐 ) and 𝑝 = 2/F.
Derivation. We begin with the simple product bound ˜ ⩽ 𝜔 /2) 𝑃 ( 𝐶˜ ⩾ −𝜔 /2) . 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ⩾ 𝑃 ( 𝑀
Derivation. Under an 𝛼-design with any 𝜔 > 0, provided that the martingale approximation (Approximation 40) holds,
Because it treats the two failure modes as independent, this bound is overly conservative, as we verified against the dynamic programming solution for 𝑛 < 200. Given ˜ and 𝐶˜ established in the positive covariance between 𝑀 Proposition 39, we might be tempted to write
𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≳ 1 − 𝑝𝑒−K + 1 − 𝑝 ,
𝑛
where K = 𝜔 2 /( 8M2𝑐 ) and 𝑝 = 2/F. Note that with two programs, 𝑝 = 1 and the above recovers the martingale bound. We prove the proposed bound by expressing the tail
˜ ⩽ 𝜔 ) 𝑃 ( 𝐶˜ ⩾ −𝜔 ) , 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩽ 𝜔 ) ≈ 𝑃 ( 𝑀 but this simple form overlooks two important adversarial
28
e mathematical preliminaries
probability as the expectation over 𝑁𝑓 + 𝑁𝑔 ∼ Binomial ( 𝑛, 𝑝) and using the two-program martingale bound, yielding
Lemma 49 (Bounded estimator to stochastic upper bound). Let 𝜃ˆ be an estimator of 𝜃 ∈ ℝ with bounded absolute bias and standard deviation. That is, | E [ 𝜃ˆ] − 𝜃 | ⩽ 𝑏 and Std [ 𝜃ˆ] ⩽ 𝑠. Then, for all 0 < 𝑝 < 1, we have that
𝑃 ( Ē 𝑓 − Ē 𝑔 ⩾ 𝜔 )
=
𝑛 ∑︁
𝑃 ( 𝑁 𝑓 + 𝑁𝑔 = 𝑚) 𝑃 ( Ē 𝑓 − Ē 𝑔 ⩾ 𝜔 | 𝑁 𝑓 + 𝑁𝑔 = 𝑚)
𝑚=0
≲
𝑛 ∑︁ 𝑛 𝑚 𝑚=0
𝑚
=
ˆ − 𝜃 ⩽ 𝑚 ⩾ 𝑝, 𝑃 𝜃
𝑝 ( 1 − 𝑝) 𝑛 − 𝑚 𝑒 − 𝑚K
𝑛 ∑︁ 𝑛 𝑚=0
where 𝑚 = 𝑠 𝑝𝑒−K
𝑚
( 1 − 𝑝) 𝑛− 𝑚
√︃
𝑝 1 − 𝑝 + 𝑏.
Proof. The claim follows from Cantelli’s inequality and a bias correction. For any 𝑘 > 0, the inequality states that Var [ 𝜃ˆ] ˆ − E [ 𝜃ˆ] ⩾ 𝑘 ⩽ . 𝑃 𝜃 Var [ 𝜃ˆ] + 𝑘2
𝑚
↓ by the binomial theorem
𝑛 = 𝑝𝑒−K + 1 − 𝑝 .
Because the function 𝑥 ↦→ 𝑥 /( 𝑥 + 𝑘2 ) is monotonically increasing for 𝑥 > 0, it then follows that
𝑠2
ˆ − E [ 𝜃ˆ] ⩾ 𝑘 ⩽ 𝑃 𝜃
𝑠2 + 𝑘2
.
Taking the complement yields
𝑠2
ˆ − E [ 𝜃ˆ] < 𝑘 ⩾ 1 − 𝑃 𝜃
𝑠2 + 𝑘2
.
We decompose the estimation error into the centered variable and the bias as ˆ − 𝜃 = ( 𝜃ˆ − E [ 𝜃ˆ]) + ( E [ 𝜃ˆ] − 𝜃) . 𝜃 By assumption, E [ 𝜃ˆ] − 𝜃 ⩽ 𝑏, so the event 𝜃ˆ − E [ 𝜃ˆ] < 𝑘 implies the event 𝜃ˆ − 𝜃 < 𝑘 + 𝑏, which ensures that
ˆ − 𝜃 < 𝑘 + 𝑏 ⩾ 𝑃 𝜃ˆ − E [ 𝜃ˆ] < 𝑘 . 𝑃 𝜃 Combining the inequalities and relaxing the strict inequality to a non-strict one yields
𝑠2
ˆ−𝜃 ⩽ 𝑘+𝑏 ⩾ 1− 𝑃 𝜃
𝑠2 + 𝑘2
.
We set the right-hand side to equal 𝑝 and solve for 𝑘, getting
√︂ 𝑘=𝑠
𝑝
1− 𝑝
.
Substituting this 𝑘 yields the desired form
ˆ−𝜃 ⩽ 𝑠 𝑃 𝜃
√︂
which concludes the proof.
𝑝
1− 𝑝
+ 𝑏 ⩾ 𝑝, □
The following lemma basically restates results from Katzenbeisser and Panny [1986], Katzenbeisser and Hackl [1986] and (2.49) from [Godreche, 2017] for the first two uncentered moments of the number of returns to the origin in tied-down
29
simple random walks. Note that although the cited works state this result for independent rvs, the conditioning on balanced block counts (tying down) renders them only exchangeable, and this is what we require here. Lemma 50 (Number of returns in tied-down random walks). Let 𝑛 be an even number. Consider the tied-down random walk ( 𝑆𝑖 )0𝑛 , a sequence of partial sums of exchangeable rvs taking the values ±1 subject to 𝑆𝑛 = 0. Let 𝑍𝑛 = |{ 𝑖 ∈ [ 1, 𝑛] : 𝑆𝑖 = 0}| , the number of returns to the origin. Then,
√
E [ 𝑍𝑛 | 𝑆𝑛 = 0] = 𝑂 ( 𝑛) , E [ 𝑍𝑛2 | 𝑆𝑛 = 0] = 𝑂 ( 𝑛) . Lemma 51 (Number of returns in simple random walks). Let 𝑛 ∈ ℕ. Consider the tied-down random walk ( 𝑆𝑖 )0𝑛 , a sequence of partial sums of independent rvs taking the values ±1. Let 𝑍𝑛 = |{ 𝑖 ∈ [1, 𝑛] : 𝑆𝑖 = 0}| , the number of returns to the origin. Then,
√
E [ 𝑍𝑛 ] = 𝑂 ( 𝑛) , E [ 𝑍𝑛2 ] = 𝑂 ( 𝑛) .
√
Proof. For E [ 𝑍𝑛 ] = 𝑂 ( 𝑛) , see e.g. Chapter III in Feller [1968]. As for E [ 𝑍𝑛2 ] = 𝑂 ( 𝑛) , we can split the random walk at the last return (or at 0 if it does not exist) and use the result from Lemma 50. □ Lemma 52.
P𝑛 − 1
√︃
𝑘=0
𝑘 = 𝑂 ( 𝑛) . 𝑛− 𝑘
√︁
Proof. We bound the sum by an integral. Since 𝑓 ( 𝑥 ) = 𝑛 −𝑥 𝑥 is an increasing function on [ 0, 𝑛) , the left Riemann sum is bounded by the integral: 𝑛−1 ∑︁ 𝑘=0
√︂
∫ 𝑛 √︂
𝑘 𝑛−𝑘
⩽ 0
𝑥 𝑑𝑥 𝑛−𝑥
We evaluate this integral using the substitution 𝑥 = 𝑛 sin2 𝜃 (where 𝑑𝑥 = 2𝑛 sin 𝜃 cos 𝜃 𝑑𝜃):
∫ 𝑛 √︂ 0
𝑥 𝑛−𝑥
√︄ ∫ 𝜋/2 𝑑𝑥 = 0
= 2𝑛
𝑛 sin2 𝜃 𝑛 cos2 𝜃
· 2𝑛 sin 𝜃 cos 𝜃 𝑑𝜃
∫ 𝜋/2 𝜋 𝑛𝜋 sin2 𝜃 𝑑𝜃 = 2𝑛 = . 4 2 0 □
30