A Theory of Dynamic Benchmarks
Authors: Ali Shirali
Rediet Abebe
Moritz Hardt
Venue: ICLR 2023 poster (2023)
Keywords: Dynamic Benchmarks
Adversarial Data Collection

Abstract: Dynamic benchmarks interweave model fitting and data collection in an attempt to mitigate the limitations of static benchmarks. In contrast to an extensive theoretical and empirical study of the static setting, the dynamic counterpart lags behind due to limited empirical studies and no apparent theoretical foundation to date. Responding to this deficit, we initiate a theoretical study of dynamic benchmarking. We examine two realizations, one capturing current practice and the other modeling more complex settings. In the first model, where data collection and model fitting alternate sequentially, we prove that model performance improves initially but can stall after only three rounds. Label noise arising from, for instance, annotator disagreement leads to even stronger negative results. Our second model generalizes the first to the case where data collection and model fitting have a hierarchical dependency structure. We show that this design guarantees strictly more progress than the first, albeit at a significant increase in complexity. We support our theoretical analysis by simulating dynamic benchmarks on two popular datasets. These results illuminate the benefits and practical limitations of dynamic benchmarking, providing both a theoretical foundation and a causal explanation for observed bottlenecks in empirical work.

Published as a conference paper at ICLR 2023
A THEORY OF DYNAMIC BENCHMARKS
Ali Shirali
University of California, Berkeley
Rediet Abebe
Harvard Society of Fellows
Moritz Hardt
Max-Planck Institute for Intelligent Systems, Tübingen
ABSTRACT
Dynamic benchmarks interweave model fitting and data collection in an attempt mitigate the limitations of static benchmarks. In contrast to an extensive theoreti- cal and empirical study of the static setting, the dynamic counterpart lags behind due to limited empirical studies and no apparent theoretical foundation to date. Responding this deficit, we initiate a theoretical study of dynamic benchmark- ing. We examine two realizations, one capturing current practice and the other modeling more complex settings. In the first model, where data collection and model fitting alternate sequentially, we prove that model performance improves initially but can stall after only three rounds. Label noise arising from, for in- stance, annotator disagreement leads to stronger negative results. Our second model generalizes the first to the case where data collection and model fitting have hierarchical dependency structure. We show that this design guarantees strictly more progress than the first, albeit at a significant increase in complexity. We sup- port our theoretical analysis by simulating dynamic benchmarks two popular datasets. These results illuminate the benefits and practical limitations of dynamic benchmarking, providing both theoretical foundation and a causal explanation for observed bottlenecks in empirical work.
INTRODUCTION
In response to concerns around the limitations of static datasets as benchmarks, researchers have proposed dynamic benchmarking
setting where data collection and model building happen iter- atively in tandem-at as an alternative (Nie et al. 2020) Potts et al. 2021 Kiela et al. 2021 Ma et al.) 2021 Gehrmann et al., 202T). In dynamic benchmarking, model builders fit models against the current dataset, while annotators contribute new data points selected to challenge previously built models. In doing so, the hope is that the iterative process results in a more diverse set of test cases that can help induce better model performance.
Though proponents argue "dynamic adversarial data collection, where annotators craft examples that challenge continually improving models, holds promise as an approach for generating such diverse training sets," there is also a recognition that "the long-term benefits or drawbacks of adopting it as core dataset creation paradigm remain poorly understood." (Wallace et al. 2022) A major concern that adversarial data collection proliferates idiosyncratic examples that do well in fooling models
but climinate coverage of necessary yet easier test cases. This can, in turn, reduce dataset diversity and limit external validity (Bowman & Dahl 2021).
A growing line of theoretical and empirical research static benchmarks has improved our under- standing of the strengths and limitations of this setting. In contrast, similar research on dynamic benchmarks has been limited. The high complexity and cost of studying live benchmarks impede experimental work. A stronger theoretical foundation for dynamic benchmarks could help guide em- pirical explorations of the vast design space, avoiding costly trial-and-error experiments. However

---

Published as a conference paper at ICLR 2023
there has been no apparent theory of dynamic benchmarking that could offer provable guarantees about their performance and clarify how issues such as label noise interact with this setting.
1.1 OUR CONTRIBUTIONS
In this work, we initiate theoretical study of dynamic benchmarks. We contribute versatile formal model of dynamic benchmarks that serve as the basis for our investigation. We start with a fundamental question:
Question 1: Can we design dynamic benchmarks in such a way that models continue to improve as the number of rounds data collection grows?
We start from theoretical model capturing existing implementations of dynamic benchmarking. This model proceeds in multiple rounds interweaving data collection and model building sequen- tially. In round I, model builders face a distribution Dr and are tasked with finding classifier he that performs well on Dr. We assume that model fitting succeeds in minimizing risk up to a positive classification error >> O. We further assume that annotators succeed in identifying the failure cases of the current model lu, giving us access to the uniform distribution D, over the error cases of the model h, We determine the new distribution D++1 by mixing D, and D, in some proportion.
We assume a starting distribution Do on the instances of interest. We can think of Du as the distribu- tion corresponding standard data collection. Mirroring the motivation for dynamic benchmarking, this distribution might assign little to no weight to important families of instances. In particular, an error of measure which we assume can achieve from the get-go, might contain many rel- evant instances. The goal is therefore to converge to well below the (-error level guaranteed by the above assumption. We assume the distribution admits perfect classifier so that process could, in principle, converge to 0 error.
In this setting, we show that three rounds guaranteed converge to O(e²) error. Unfortunately, this is where it ends. In general, there is no reason to expect this dynamic benchmark to progress below (2)²) error. Put differently, there is no provable benefit dynamic data collection beyond three rounds. The cause of our negative result is form of catastrophic forgetting that mirrors the concerns quoted earlier. As the benchmark moves beyond three rounds, there provably no way to retain knowledge of instances correctly classified at earlier stages.
Furthermore, we show through experiments that this lower bound may also be encountered in prac- tice, preventing dynamic benchmarks from progressing beyond small number of rounds. In doing so, we propose a concrete way to simulate the performance of dynamic benchmark that may be of independent interest in the empirical study of dynamic benchmarks.
There is yet another impediment to successful dynamic benchmarking: Above we considered the case where the underlying learning problem is realizable, meaning that there exists model that achieves 0 error on the distribution. In practice, unrealizable settings where we have label noise commonplace. Unrealizability can result from, for instance, annotator disagreement where there an emerging line of work aiming to understand their impact on data diversity. label noise, and model performance. We show that in this unrealizable setting, dynamic benchmarks concentrate on mislabeled instances, losing their representativeness of the underlying distribution.
Though pessimistic, the above negative results may be inherent the simple sequential design of dynamic benchmarks currently used in practice. To further probe this issue, we ask:
Question 2: Are there more sophisticated dynamic benchmark designs that can guarantee convergence below the error barrier of the standard setting?
We answer this question the affirmative by considering hierarchical model, which recursively uses the above sequential setting as a building block. In this setting. the organizer of benchmark creates multiple instances of dynamic data collection and combines the outcomes a particular way, e.g., by ensembling the resulting models and feeding the output into a new instance. We study the setting where the hierarchy has depth two and show that this setting guarantees convergence to error O(e)), providing strict separation with the standard model. Despite the improved performance, this depth-two setting significantly complicates the benchmarking process, and executing a design with further depth may be prohibitive in practice.
2

---

Published as a conference paper at ICLR 2023
In search of alternative designs that consistently improve the model's performance, study complementary design to dynamic benchmarks in Section [ of Appendix. Instead of accumulating adversarial examples in dynamic benchmark, here the model-in moodel-i--te-loopp carries the information by directly using new examples and becoming more complex throughout the process. We also make natural connection to boosting methods. Despite achieving
risk theoretically, this alternative has limited applicability due to either slow convergence or computational infeasibility.
In sum, our results indicate that current bottlenecks observed in empirical settings under the sequen- tial model are inherent to the set-up. This can alert practitioners to the limitations of current practice before many rounds of data are collected. Further, more complex designs such as the hierarchical setting can result in improved performance but may suffer from the organizational complexity of data collection. Combined, these results highlight stark tradeoffs in switching from static to dy- namic settings and suggest that exploration of the design space for modeling dynamic benchmarks can play an important role.
1.2 RELATED WORKS
For an introduction to datasets as benchmarks, see Chapter Hardt Recht (2022). Concerns around static benchmarks summarized in recent works, including adaptivity (Dwork et al. 2015), violation of sample independence in sequentially generated data (Shirali (2022). and issues of anno-
tator disagreement (Pavlick& & Kwiatkowski 2019 Prabhakaran al. 202 Davani et al. 2022).
Numerous new benchmarks and benchmarking systems have recently been proposed that integrate some aspects of dynamic data collection. Adversarial data collection continually adds challenging examples found by annotators for an existing model (Dinan et al. 22199 Nie et al. [2020] Kiela et al, 2021 Potts et al., 2021; Wallace et al.) 2022). Empirical studies show this does not necessarily lead to better performance or robustness (Kaushik et al. 2021; Wallace et al., 2022). A dynamic leader- board periodically renews the test set [Zellers et al. 2021). In response the fast growth of dynamic benchmarking, various tools and platforms are also developed. For example, platforms for adversar- ial data collection (Kiela et al. 202T), assistance of annotators find challenging examples (Bartolo) et al. (021), personalized benchmarking (Narayan et al. 22021), and automatic crowdsourcing of leaderboard submissions (Khashabi et al. 2021). Adversarial filtering, which filters out examples from a static dataset that are identified to be easy for given model, is another related technique (Pa- perno et al. [016)] Zellers et al., [0188] Le Bras et al.) 2020). Such datasets are susceptible to being biased (Phang et al.) 2022) saturate faster than static datasets (Taori et al. 2020). Le Bras et al. (2020) include theoretical considerations on eliminating bias. The flurry of newly minted bench- marks stands in stark contrast with the scarcity of theory on the topic. Our work was inspired by the thought-provoking discussion of dynamic benchmarks by Booman & Dahl (2021).
2 PROBLEM FORMULATION
Our primary goal in this work is understand the population-level dynamics that benchmark de- sign induces. We are centrally interested in capturing what the iterative process of model building and data collection converges and focus on distributions rather than samples. We assume that model builders successfully mini- mize risk approximately. While risk minimization may be computationally hard in the worst case, this assumption reflects the empirical reality that machine learning practitioners seem to be able to make consistent progress on fixed benchmarks. While we focus on population- dynamics the design of benchmarks, we restrict ourselves to operations with standard finite sample counterparts.
Consequently, we ignore finite sample issues in our formulation
dynamic benchmark design can be represented as a directed acyclic graph where the nodes and edges correspond to classifiers, distributions, and the operations defined below:
1. Model building: Given distribution, find an approximate risk minimizer.
2. Data collection: Given a model, find a new distribution.
Model combination:
Combine a set of models into a single model.
4. Data combination:
Combine set of distributions into single distribution.
3

---

Published as a conference paper at ICLR 2023
A D
h1 Do
Dj
D,
>D2
>12
Figure Example of a path dynamic benchmark. Symbol A represents risk minimization, represents human data collection, and @ shows distribution mixing.
We describe these operations in turn First, we explain model building by defining the notion risk and risk minimization. The risk of classifier h: X on distribution supported the data universe x y with respect to the zero-one loss is defined as
Rp (h) = (2 1 (M(x) # w)
An e-approximate risk minimizer A is an algorithm that takes a distribution P as input and returns a classifier h: X' y such that
(p(h) S min (h) + WER
where H is family of classifiers. In the benchmark setting, risk minimization is collective effort
of numerous participants. The algorithm A represents these collective model-building efforts.
We abstract data collection tion D, returns new distribution D. In the context of adversarial data collection, we assume that annotators find the conditional distribution over instances which h errs D D)a(a) This is an idcalized representation of data collection, that ignores numerous real-world issues. Nonetheless, this idcalized assumption will make our negative results even stronger.
operation that takes classifier h and, for underlying distribu-
Model combination happens via a weighted majority vote among multiple classifiers, Distribution combination takes mixture of multiple given distributions according to some proportions.
The final piece in our problem formulation is the ultimate success criterion for benchmark design. One natural goal of a dynamic benchmark to output classifier that minimizes risk on fixed underlying distribution D. We envision that this distribution represents all instances of interest. There is a subtle aspect this choice of a success criterion. If we already assume we have an e-approximate risk minimizer on D, why are not done from the get-go? The reason is that the error term might cover instances crucially important for the success of a classifier in real tasks. After all, a 95% accurate classifier can still perform poorly in practice if real-world instances concentrate on a set of small measure in DD The goal is therefore to find classifiers achieving risk significantly below the error level guaranteed by assumption. By asking for successively higher accuracy, ensure that the benchmark continues to elicit better-performing models as time goes on.
Notation. We define error set of classifier h as E,, {(x, y) E X' y that (h) = Pr Ex). We drop P from Pry(-) when this is clear from the context. We say realizable on distribution
h(x) o y). Note
a classification problem Rp(J) 0. Here, H is the hypothesis class and f is called the true classifier. For realizable problems, no uncertainty will be left over y when x X' drawn, so we use P referring to the distribution over X and define error sets subset of X. Let pp be the probability density function associated with P. We say P. is conditioned on E' C. X and denote it by P|E for (x) For notational convenience,
if there is a classifier f H such that
any x X' we have (*) in place of (x)). The support (P) of distribution P is the largest subset of X' such that P(x) > for all x E supp(P). Given probability distributions P1, Pz,.... "2.....,I, Pr, we denote the mixture distribution with weights we 2 0 such that Σ, Wi 1 by mix(Pi,
sometimes use P(x:)
Pr), where Pmix (x) = Di= Wi Pe(x). For a set of classifiers h1, /12, ..., . hT, we denote the weighted majority vote classifier by maj(hı, he,..,....... .hr).
PATH DYNAMIC BENCHMARKS
The simplest case of dynamic benchmark corresponds to the design of a directed path interleaving model building and data collection as illustrated in Figure [ This is the design most similar to current proposals of dynamic benchmarks and adversarial data collection (Nie et al. 2020 Kiela
4

---

Published as a conference paper at ICLR 2023
Starting from initial distribution, each round, new classifier is obtained from the latest distribution. The annotators are then asked to find the vulnerabilities of this model. This new insight will be leveraged towards updating the latest distribution. We call this procedure path dynamic benchmarking.
et al. 2021).
Path dynamic benchmarking: For an underlying distribution D with true classifier S, given initial distribution Do and approximate risk minimizer A, each round
1. ha = A(Di)
2. D. =2)==in,,<+f11 (+)
3. Di+1 mix Do. Dh.DD.DD. D2. D.)
We first formalize the rationale behind path dynamic benchmarks. Ideally, given a perfect, i.e. O-approximate, risk minimizer, every time the current classifier misclassifies some part of the under- lying distribution, annotators reveal that part and the updated classifier will avoid repeated mistakes. Since errors will be repeated across the sequence, there classifiers. The following simple lemma formalizes this intuition for a target error level a >> 0.
be limited number of very bad
Lemma 3.1. For any hypothesis class H. true classifier f H. perfect risk minimizer A, underlying supp(D), let (ha) be any
distribution D. and initial distribution Do such that supp(Do) sequence of classifiers obtained in path dynamic benchmark with equally weighted mix(-). Then, for any a > 0, there are most classifiers of risk more than a. In other words, Ht <
(hy a) S
See proof page 15
The lemma does not guarantee the latest classifier's risk, but it is straightforward to see a random selection of the classifiers after many rounds accurate with high probability (see Corollary C.1 more effective way to construct an accurate classifier from the sequence classifiers to take their majority vote. In this case, three rounds of model building suffice find a perfect classifier.
Proposition 3.2. Under the conditions Lemma 3.1 let (b+)T-) be any sequence of clas- sifiers obtained in a path dynamic benchmark with uniform mixture weights. If T 2 3, RD majj(hg hi. (.....),,))))
Proof. From the proof of Lemma 3.1 we know E, supp(D;) 0. So, E for every < t. The majority vote of h,s will misclassify æ if half or more of h,s misclassify But no two distinct h,s make a common mistake, So, for three or more classifiers, the majority vote classifier always correct.
So far, path dynamic benchmarking seems to be a promising choice when a perfect risk minimizer is available and the problem realizable. The situation changes significantly when go approxi- mate risk minimizers.
We first study three-round path dynamic benchmark. We then show how results would generalize for an arbitrary number of rounds. Our results apply to the case where the initial and underlying distributions Do do not need be identical to the target distribution D. measure the distance between distributions with respect to hypothesis class, we use the following notion.
Definition 3.3 (See Ben-David et al. (2010)). For a hypothesis class and distributions Pı and Pz, the H.AH-distance between Pi and P2 is defined
dHAH (P1,P2)= = sup K.KEH
Ex-P, [1 M(x))) Eg (1 (M(x) + (((x)))
(1)
The next theorem discusses how path dynamic benchmarking with three rounds performs in the case of an 6-approximate risk minimizer.
Theorem 3.4. For any hypothesis class H. true classifier f H. underlying distribution D. initial distribution Do with (D)) S supp(D), and any e-approximate risk minimizer A, let by, hn, and
5

---

Published as a conference paper at ICLR 2023
hy be the three classifiers obtained after three model building rounds in path dynamic benchmark with uniform mixture weights. Then, the risk of the majority vote classifier is bounded by
Ri (oomma(hoo.u h1, h2)) S (e² ednan D)).
(2)
Note that for sufficiently similar Do and D, i.e., (No D) O(c), risk is bounded by O(e²).
See peeoproofoo on page 15
The obtained (c²²) error with only three rounds of model building is significant improvement to the (e)) error that could be achieved with static benchmarks and an e-approximate risk minimizer. We then consider what happens if continue dynamic benchmarking for many rounds.
Theorem 3.5. For any e-approximate risk minimizer A with VCdim(H) -. and any path dynamic benchmark with L 2 3 rounds of model building and arbitrary mixture weights, there exists an underlying distribution DD such that for any true classi- fier E H and initial distribution Do with supp(Do) S supp(D), there exists a sequence (he) of classifiers consistent with path dynamic benchmark where the risk of their weighted majority vole is lowerbounded by
N, hypothesis class H with
2
RD maj(ho,
(3)
8
for any weighting of maj(.). Further, Theorem C.2 shows for any path dynamic benchmark, there exists H with constant VC dimension such that similar fower-bound holds.
See proof page 16
Theorem 3.5 shows that 52(c²) error serves as lower bound in the approximate risk minimizer setting for any path design (any mixture weighting and weighted majority). Then Theorem 3.4 shows three rounds of model building with uniform weights can achieve the lower bound, so is optimal, and continuing dynamic benchmarking for more rounds might not be helpful.
3.1 CHALLENGES NON-REALIZABLE SETTINGS
For many reasons, our problem may not be realizable. For example, class of functions that is not complex enough to explain the true model constitutes an unrealizable setting. Even for a complex enough class, annotators might fail to label instances correctly. In simplified model for unreal- izable problems, we assign random labels to a small part of the distribution and let the rest of the distribution be realizable. Formally, let 2 be the randomly labeled subset of X' and X = X' 2 be the rest of the domain labeled with f. Since no classifier can do well on X dynamic bench- marks are prone to overrepresent X This intuition is formalized in Theorem 3.6 where show significant portion of Dr will be concentrated on X
Theorem 3.6. For any hypothesis class H. true classifier f. e-approximate risk minimizer A, and any underlying distribution D such that o-proportion of D is labeled randomly and the rest is labeled by f. i > e, as long as t = O(E), at least (11) pproporrono Dr obtained through path dynamic benchmark will be concentrated around the unrealizable instances, i.e., PID, (x E xx) = (11).
See proof on page 18
As direct consequence, classifiers trained on a path dynamic benchmark lose their sensitivity to realizable instances and might show an unexpectedly bad performance on the rest of the distribution.
HIERARCHICAL DYNAMIC BENCHMARKS
Thus far, we have observed that given an e-approximate risk minimizer, the smallest achievable risk through path dynamic benchmarks is ())²). This observation evokes the idea of possibly achiev- ing a squared risk by adding a new layer to the benchmarking routine, which calls path dynamic benchmarking as a subroutine. Figure (shows shows such structure with three steps. At each step, path dynamic benchmarks are obtained starting from a mixture the initial distribution and error distri- butions of all previous steps. In the second layer, models found in different steps aggregated. We

---

Published as a conference paper at ICLR 2023
A
A.11
A.
A
A. 11
A.11
A
Do
Ro
-
R1
>
-
lts
11
H
D
H
>
Do
Figure 2:
Depth-2 width-3 hierarchical dynamic benchmark. Symbols in Figure 1 with M repre- senting majority vote.
call the dynamic benchmark of Figure 2 depth-2 hierarchical dynamic benchmark. In an extended form, depth-k hierarchical dynamic benchmark can be designed by adding new layer on top of the models obtained from some depth-(k: - 1) benchmarks.
Hierarchical dynamic benchmarking: For underlying distribution D and true classifier S, given an initial distribution Do and an approximate risk minimizer A, depth-k width-w hierar- chical dynamic benchmarks are constructed recursively:
def. A (Do):
1. hn = AA
2. For 1, ...., ,
(a) D.-1 =D| -Dlm (())
(b) D. mix(Puy Du, "I,..., ;D,11)
(c) h4 = 1A(
3. return maj(ho, f1,, .... 11
where (0)) A.
Note that this setting does not mean that different steps of path dynamic benchmarking can be done in isolation. Running two benchmarking tasks independently does not yield benefits since humans in the loop might return similar vulnerabilities. In the depth-2 hierarchy of Figure we have bold-faced arrows corresponding to the sequence of steps that should be taken. So, any reasonable dynamic benchmarking based on our model is a sequential process, and the name hierarchy is meant to carry the intuition on how the aggregation of classifiers is happening.
Also note that (A)) calls annotators for w rounds. Since no known empirical dynamic bench- marking study has ever had more than rounds (as studied in Wallace et al. (2022), we limit our analysis to depth-2 width-3 structure (Figure 2 Here w 2 3 is the necessary and sufficient number of rounds for path dynamic benchmarks to ensure O(e2) risk when A c-approximate risk minimizer and Do is sufficiently similar to D.
The next theorem provides an upper bound on the risk of any classifier obtained through hierarchical data dynamic benchmarks of Figure 2
Theorem 4.1. For any hypothesis class H. true classifier H. underlying distribution D. initial distribution Do with supp(Du) S supp(D), and any c-approximate risk minimizer A, the risk of any classifier obtained from a hierarchical dynamic benchmark with depth-2 and width-3 (Figure where mix(.) and maj(-) uniformly weight the inputs, is bounded by
Rp (mmaa(ggo 91, (2)) S O + dnnnn((D (Do, D))
(4)
Note that for sufficiently similar Do and D, i.e,, dHAH D) O(e), risk is bounded by O(e3).
See proof on page 19
The hope in adding a new layer to dynamic benchmarking was to obtain a squared risk of the previ- layer's risk. So, ideally, depth-2 hierarchical dynamic benchmark could achieve O(e") error.

---

Published as a conference paper at ICLR 2023
But this is not the case; next, we show that the upper bound of Theorem 4.1 is tight up constant, and the conjecture of squared risk per layer does not hold.
Theorem 4.2. For any e-approximate risk minimizer A with 1 N, hypothesis class H with VCdim(H) 2 2. and any hierarchical dynamic benchmark with depth-2 and width-3 (Figure 2 with arbitrary mixture and majority weights, there exists underlying distribution 'D such that for any true classifier f E H and initial distribution Do with supp(Do) S supp(D), there exists classifiers consistent with hierarchical dynamic benchmark for which
RD maj(go: -1-22)
(5)
Further, Theorem C.3 shows for any hierarchical dynamic benchmark, there exists H. with constant VC dimension such that similar lower-bound holds.
See proof on page 20
Combined, these results show that design structures that are more intricate than the current prac- tice, as captured by the path dynamic benchmark, can yield improved results but also have strong limitations and are challenging to implement in practice.
5 EXPERIMENTS
Theorem 3.5
provides an (2(c²) lower bound on the risk achievable with an c-approximate risk minimizer. The proof of this theorem is constructive, introducing a bad sequence of distributions and classifiers consistent with the path design with @(c²) error. But the theorem does not rule out the existence of a good sequence achieving arbitrarily small risk. An important question is how frequently bad sequences appear in practice, retaining the eπrоr above zero even after many rounds.
We study this question by simulating path dynamic benchmarks on two popular static benchmarks, CIFAR- 10 (Krizhevsky et al. 2009) and SNLI (Bowman et al. 2015). The details of the data and models are reported in Section B.I of Appendix. Our aim in these experiments is not to obtain a state-of-the -frtt----ttttttt model. Instead, we want to study the effectiveness of path dynamic benchmarks in controlled experimental setting with light models. Our simulation design is similar for both datasets:
1. Train a base classifier on the whole dataset and fix for the next steps.
2. Construct new dataset from samples correctly classified by the base model and define the true and initial distributions as a uniform (point mass) distribution over these samples. Note that in this case empirical risk samples weighted according point distribution is equivalent to risk on that distribution. Since the base model correctly labels all selected samples, the problem is also realizable.
3. Draw multiple rollouts of path dynamic benchmarks. A rollout from path dynamic benchmark a sequence of distributions and models obtained by alternatingly training a new classifier on the weighted extracted dataset and up- up- weighting (digh-weighhing) the distribution over misclas- sified (correctly classified) samples according to mixture rule with uniform weights. Note that the base model is fixed, and the randomness across rollouts solely comes from different initial- izations of new classifiers and possible randomness in optimization methods.
There are two deviations from our theoretical study in this design: First, we studied binary classifi- cation, but both CIFAR-10 10 and SNLI define multi-label problems. We believe our main arguments hold for multi-label tasks as well. Second, although the problem is realizable, the solution is un- likely to have zero risk as training a new classifier at each round of a rollout typically consists of non-convex optimization. This is addressed in our theoretical framework as e-approximate risk min- imization. Our analysis requires fixed across all rounds which approximately holds in practice.
Figure shows results from 100 rollouts of path dynamic benchmarks simulated on CIFAR-10, At each round, the value on the vertical axis shows the risk of the majority vote of all the classifiers obtained in a rollout so far. The solid line is the average of the majority vote's 's risk all rollouts, and the shaded area shows the standard deviation. There is attainable, path dynamic benchmarks fail to reach it. Second, the variance across rollouts is quite consistent each round. This shows good rollout keeps being good, and likewise with a bad
few observations: First, although zero risk
8

---

Published as a conference paper at ICLR 2023
0.14
risk of rollouts
0.08
avg. risk rellouts
0.12
rolicut
best rollout
worst rollout
of majority vote
0.10
0.06
of majority
0.08
0.06
0.04
0.04
0.02
0.02
0.00
15
20
25
10
15
20
round
round
(a) CIFAR-10
(h) SNLI
Figure 3: Path dynamic benchmark is simulated. The base model is kept fixed for all rollouts. The y-axis shows the risk of the majority vote of all classifiers obtained until that round.
rollout, so contimuing dynamic benchmarking does not help. We further discuss why a rollout turns out to be good or bad one and how this is related to our theoretical negative example in Section B.2 of the Appendix.
Figure 3b shows the results from 50 rollouts of path dynamic benchmarks simulated SNLI A similar observation regarding non-zero risk in limit can be made here. Compared to the image classification task, path dynamic benchmarks in the NLJ task show more fluctuation through rounds which might be due to the harder nature of the problem or a more complex model.
Summarizing these observations, path dynamic benchmarks, matter how long them for, confront a lower bound even in simple realizable settings. This provides empirical evidence that our negative results are not contrived, but point at what may be inherent limitations dynamic benchmarking.
DISCUSSION
The scientific foundation of traditional benchmarks is the holdout method, whereby we split the dataset into a training and testing component. Although the machine learning community routinely operates well outside the statistical guarantees of the holdout method, at least there is some cogniz- able theoretical framework for static datasets as benchmarks. Moreover, more recent works have found new support for static benchmarks (Blum & Hardt 2015) Recht et al., 2019)..
Dynamic benchmarks provide an intriguing proposal aimed at mitigating known issues with static benchmarks. Platforms for dynamic benchmarks are already up and running. However, machine learning theory has little to offer in the way of guiding the principled design of valid dynamic benchmarks. Responding to this lack of theoretical foundations, we propose formal model of dynamic benchmarks that allows to combine model building and data collection steps in a flexible manner. We focus on what think is the first-order concern in the design of benchmark: Does the benchmark, in principle, induce the creation of better models?
While our results show provable benefit dynamic benchmarking, is arguably more subtle than hoped and comes at a significant increase in complexity. Our negative results are particularly con- cerning given that we optimistically assume that both model builders and annotators have significant competence. In practice, dynamic benchmarks likely face additional obstacles neglected by our ide- alized assumptions. As a result, it is less clear to what extent our positive results have prescriptive value. On the other hand, our positive results make it clear that the design space for dynamic bench- marks is larger than currently utilized, thus pointing at a range of interesting open problems. Finally, lowering risk or improving the accuracy of the induced models is the ultimate success criterion of a benchmark, however, there are other concerns including the robustness of the models that can be the topic of future works based proposed framework.

---

Published as a conference paper at ICLR 2023
REFERENCES
Max Bartolo, Tristan Thrush, Sebastian Riedel, Pontus Stenetorp, Robin Jia, and Douwe Kiela. Models in the loop: Aiding crowdworkers with generative annotation assistants. CORR, abs/2112.09062. 2021. URL BRLLttts:///axxi.. org www.oog/////.//oo/////........a/ abs /2122. 09062
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 79(1):151-175, 2010.
Avrim Blum and Moritz Hardt. The ladder: A reliable leaderboard for machine learning competi- tions. In International Conference Machine Learning, pp. 1006-1014. PMLR, 2015.
Samuel Bowman and George Dahl. What will it take to fix benchmarking in natural language understanding? In Proc. of NAACL, pp. 4843-4855, 2021.
Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher Manning. large an- notated corpus for learning natural language inference. In Proceedings of the 2015 Confer- ence on Empirical Methods in Natural Language Processing, pp. 632-642, Lisbon, Portugal, September 2015, Association for Computational Linguistics. doi: 10.18653/v1/D15- 1075. URL
Aida Mostafazadeh Davani, Mark Diaz, and Vinodkumar Prabhakaran. Dealing with disagreements: Looking beyond the majority vote in subjective annotations. Transactions of the Association for Computational Linguistics, 10:92-110, 2022.
Emily Dinan, Samuel Humeau, Bharath Chintagunta, and Jason Weston. Build it break it fix it for dialogue safety: Robustness from adversarial human attack. In Proceedings of the 2019 Con- ference on Empirical Methods in Natural Language Processing and the 9th International Joins pp. 4537-4546 Hong Kong, China, November 2019. Association for Computational I Linguistics. doi: 10.18653/v1/11--11
Conference on Natural Language Processing JEMNLP-IJCNLAN
URL http::: /wwwwwwwwwwwwwwww C. web. .rw.b.org//eeoo aathoooogyy D1 9-1461
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium Theory of computing, pp. 117-126, 2015.
Sebastian Gehrmann, Tosin Adewumi, Karmanya Aggarwal, Pawan Sasanka Ammanamanchi, Anuoluwapo Aremu, Antoine Bosselut, Khyathi Raghavi Chandu, Miruna-Adriana Clinciu, Dipanjan Das, Kaustubh Dhole, Wanyu Du, Esin Durmus, Ondrej Dušek, Chris Chinenye Emezue, Varun Gangal, Cristina Garbacea, Tatsunori Hashimoto, Yufang Hou, Yacine Jer- nite, Harsh Jhamtani, Yangfeng Ji, Shailza Jolly, Mihir Kale, Dhruv Kumar, Faisal Ladhak, Aman Madaan, Mounica Maddela, Khyati Mahajan, Saad Mahamood, Bodhisattwa Prasad Ma- jumder, Pedro Henrique Martins, Angelina -cMillan-Major, Simon Mille, Emiel van Miltenburg, Moin Nadeem, Shashi Narayan, Vitaly Nikolaev, Andre Niyongabo Rubungo, Salomey Osei, Ankur Parikh, Laura Perez- Beltrachll,, Niranjan Ramesh Rao, Vikas Raunak, Juan Diego Ro- driguez, Sashank Santhanam, João Sedoc, Thibault Sellam, Samira Shaikh, Anastasia Shimo- rina, Marco Antonio Sobrevilla Cabezudo, Hendrik Strobelt, Nishant Subramani, Wei Xu, Diyi Yang. Akhila Yerukola, and Jiawei Zhou. The GEM benchmark: Natural language generation, its evaluation and metrics. In Proceedings of the 1st Workshop on Natural Language Generation, Evaluation, and Metrics (GEM 2021), pp. 96-120, Online, August 2021. Association for Com- putational Linguistics. doi: 10. 00.18633/v1/200 12233/11/2221112 -em---emmmm 1.10. URL. tiktps://accaathon org/ 22222021220 1e0m1.10m..........
Moritz Hardt and Benjamin Recht. Patterns, predictions, and actions: Foundations of machine learning. Princeton University Press, 2022.
Divyansh Kaushik, Douwe Kiela, Zachary C. Lipton, and Wen-tau Yih. On the efficacy of adver- sarial data collection for question answering: Results from a large-scale randomized study. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 6618-6633, Online, August 2021. Association for Computational Linguistics. doi: 10. v1/2021 lo1- URL. httths:///ccaaaaeee attt:s///cclaamcooooo..oor//////
acl wol.llloo...111
10

---

Published as a conference paper at ICLR 2023
Daniel Khashabi, Gabriel Stanovsky, Jonathan Bragg, Nicholas Lourie, Jungo Kasai, Yejin Choi, Noah A Smith, and Daniel S Weld. Genie: A leaderboard for human-in in-the-loop evaluation of text generation. arXiv preprint arXiv:2101.06561 2021.
Douwe Kiela, Max Bartolo, Yixin Nie, Divyansh Kaushik, Atticus Geiger, Zhengxuan Wu, Bertie Vidgen, Grusha Prasad, Amanpreet Singh, Pratik Ringshia, Zhiyi Ma, Tristan Thrush, Sebas- tian Riedel, Zeerak Waseem, Pontus Stenetorp, Robin Jia, Mohit Bansal, Christopher Potts, and Adina Williams. Dynabench: Rethinking benchmarking in NLP. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 4110-4122, Online, June 2021. Association for Computa- tional Linguistics. doi: 10.18653/v 105/33/11222/2 1/2021 maacl-main.324 URL https: httt::://aclamthooooyyy
orq www.c-nainnnnn... 324
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ronan Le Bras, Swabha Swayamdipta, Chandra Bhagavatula, Rowan Zellers, Matthew Peters, Ashish Sabharwal, and Yejin Choi. Adversarial filters of dataset biases. In International Confer- ence on Machine Learning, pp. 1078-1088. PMLR, 2020.
Zhiyi Ma, Kawin Ethayarajh, Tristan Thrush. Somya Jain, Ledell Wu, Robin Jia, Christopher Potts, Adina Williams, and Douwe Kicla. Dynaboard: An avaluation-as-a-sevvee platform for holistic next-generation benchmarking. Advances Neural Information Processing Systems, 34, 2021.
Avanika Narayan, Piero Molino, Karan Goel, Willie Neiswanger, and Christopher Re. Personal- ized benchmarking with the ludwig benchmarking toolkit. In Thirty-fifth Conference Neu- ral Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021. URL https: https///ppeeeeeeeeee net/ Forum?id= www.ww/wwwwwwww...m
Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. Adver- sarial NLI: A new benchmark for natural language understanding. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguisties, 2020.
Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Ngoc Quan Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. The LAMBADA dataset: Word prediction requiring a broad discourse context. In Proceedings of the 54th An- mual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v1/P166 1144. URL
Ellie Pavlick and Tom Kwiatkowski. Inherent disagreements in human textual inferences. Transac- tions of the Association for Computational Linguistics, 7:677-694 0974 2019.
Jason Phang, Angelica Chen, William Huang, and Samuel R. Bowman. Adversarially constructed evaluation sets are more challenging, but may not be fair. In Proceedings of the First Workshop on Dynamic Adversarial Data Collection, pp. 62-62 22-62, Seattle, WA, July 2022. Association for Com- putational Linguistics. doi: 10.18653/w1/2022.ooom dadc-- URL /tttps://aclatthoologg
org/2022. dadc 1.8.
Christopher Potts, Zhengxuan Wu, Atticus Geiger, and Douwe Kiela. DynaSent: A dynamic benchmark for sentiment analysis. In Proceedings of the 59th Annual Meeting of the Asso- ciation for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pp. 2388-2404, Online, August 2021. Asso- ciation for Computational Linguisties. doi: 10. 1e.1186///ll 118653/1/20211111 wac.o.....l-oog..... 186. URL https:
//aclanthology.ozq wwtp//2l..loooo...oo 2tt.:/2221..cl111ooo acl-lon.. 186
Vinodkumar Prabhakaran, Aida Mostafazadeh Davani, and Mark Diaz. On releasing annotator- level labels and information in datasets. In Proceedings of the Joint 15th Linguistic Annotation Workshop (LAW) and 3rd Designing Meaning Representations (DMR) Workshop, pp. 133-138, Punta Cana, Dominican Republic. November 2021. Association for Computational Linguistics. doi: 10.18653/v122221..m 1.14. URL htt.pps://accaattcoooooooor////p 1aw 14

---

Published as a conference paper at ICLR 2023
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning, pp. $389-5400. PMLR, 2019.
Robert E Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predic- tions. Muchine learning, 37(3):297-336, 1999.
Ali Shirali. Sequential nature of recommender systems disrupts the evaluation process. In Ad- vances in Bias and Fairness in Information Retrieval: Third International Workshop, BIAS 2022, Stavanger, Norway, April 10, 2022, Revised Selected Papers. pp. 21 21-34. Springer, 2022.
Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification. Advances in Neural Information Processing Systems, 33:18583-18558 2020.
Eric Wallace, Adina Williams, Robin Jía, and Douwe Kiela. Analyzing dynamic adversarial training data in the limit. Findings of the Association for Computational Linguistics: ACL 2022, pp. 202-217, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653/ #1/2022.findings-
URL /ttpps//aaet httpss//allaatthooooooo oothhloog..rgg//22...... org/2022. wer.ffiidiiggg acl....gss......................
Rowan Zellers, Yonatan Bisk, Roy Schwartz, and Yejin Choi. SWAG: A large-scale adversar- ial dataset for grounded commonsense inference. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 93-104, Brussels, Belgium, October- November 2018. Association for Computational Linguistics. doi: 1011855//1/DI1--110 URL
https: www wwwp://w..ww.bbrrrrcccccc hwtp://wwwww...r/.a.ooooooo///-.
Rowan Zellers, Ari Holtzman, Elizabeth Clark, Lianhui Qin, Ali Farhadi, and Yejin Choi. Turing vice: A generative and dynamic evaluation of language use. In Proceedings of the 2021 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 4856 4880, Online, June 2021. Association for Computational Lin- guistics. URL https::////.......t.. /wwww aclweb. act.wee..rr//manoooooo////////ee naa.ammaan..aaaaa.. 386
A DYNAMIC GRADIENT-BASED UPDATE
The current practice of dynamic benchmarking aims at diversifying the benchmark by dynamically adding new hard examples to it. The hope is to obtain better models from the benchmark every time new samples added. As observed, despite the initial benefit this method has, there exist arbitrarily long dynamic benchmarks with no significant improvement after the first few steps.
But if the ultimate goal is obtain improved models, there is of keeping all the adversarial feedback the form of a dynamic benchmark, the model-in-the-logg itself can carry all the information by becoming more and more complex throughout the process. In other words, rather than updating the benchmark by adversarial examples, these examples can be collected in way that can be directly used to update the model. Dynamic adversarial feedback from annotators is helpful here by providing fresh examples at each round that prevent overfitting. This phenomenon is also close the boosting technique in machine learning.
direct way do it. Instead
In this section, we discuss how directly updating the model using adversarial data can be formulated within our framework and why they are not practical. Since we use gradient-based techniques to update the model, we call these methods dynamic gradient-based updating. We first formally introduce a vector notation for functions and distributions, which makes our arguments easier to follow. Then we discuss how classifier's risk with respect to the zero-one loss would be represented with this notation. In search classifier that minimizes this risk, we minimize surrogate convex losses rather than directly optimizing for zero-one risk. Here we discuss two popular choices, to be named hinge and exponential losses, and for each, discuss the corresponding method with its strengths and limitations.
12

---

Published as a conference paper at ICLR 2023
A >
11 A hn
11 >D,
>>
Do
Do
hg
h1
h h2
Figure 4: Dynamic gradient- based update: hinge loss minimization.
Notation. Let h X' + {-1.1} be a binary classifier defined on the finite set A. The vector representation of h in X is = (h(=))=Ex* 2EX Similarly, let P be a probability distribution over X. The vector representation of in X' is P (P(x))=Exx The entrywise product of two vectors h1 and h2 is denoted by h1 h2. For an underlying distribution D and true classifier f. we can use vector representations to write the risk with respect to the zero-one loss. Risk of a binary classifier on D (h) = 3 (1 h f, D). For a general h - IR, still we can define the risk with respect to the zero-one loss as (h(h) = 21 sign(h f), D), where sign(-) is an entrywise operator.
Upper-bounded risk. There are many ways to upper-bound RD (h). For example, for any entry- wise function ((-) such that 1(x) 2 1 0} 2 - sign(x) for all x E I, the risk of h with respect to the zero-one loss can be upper-bounded by
RD(h)= & (h) = (I(h D).
(6)
A.1 MINIMIZING HINGE LOSS
A popular function upper-bound the zero-one risk is the hinge loss: 1(x) max(1 x, x2
Plugging ((-) into Equation 6 gives:
(h) S Reline (h) = (max(1 h f. D),
(7)
where max(.) is clement-wise maximization. Let g R. hinge Looking for update of the form h = h + Ah reduce Rhinse (h). any direction such that (g, Ah) < will be a descent direction and small step size guarantees consistent decrease of phingge As we will show in the proof of Lemma A.I directly applying gradient descent, i.c., Ah = -ng. is not practical, as incorporates summation of distribution and a classifier vector. Unlike classifiers which are known for every point the domain, in practice, distributions are limited to the available samples and this summation is not implementable. Alternatively, let Es, {xr X (()){(x) < 1] be the set of
margin errors of classifier h. We task annotators to return Dn, = DD F, given h. Let h = A(Dr) be the model built on the vulnerabilities of h. Next lemma shows h is descent direction for the hinge loss.
Lemma A.1. For any hypothesis class H. true classifier e-approximate risk minimizer A, and any underlying distribution D, the vector representation h of the classifier h A(()lnc))(()))) is descent direction for phinge (h))
H. current classifier h H.
See proof on page 22
This lemma lets us write the updating rule h = h + Rhinge (h) h. depicted graphically in Figure 4 Since gradient dominance condition holds for this update and hinge loss 1-Lipschitz, h will con- verge to f with the rate of O (x)). Although this method guarantees convergence, the dependence on the domain size makes the bound useless for continuous very large domains.
A.2 MINIMIZING EXPONENTIAL LOSS
Another candidate function to upper-bound the zero-one risk is the exponential loss: [(x) exp(-z). This leads similar analysis as the AdaBoost algorithm (Schapire Singer 1999) Plugging I(-) into Equation 6 gives:
Rh(h) < Re (h) = (exp(-h f), D),
where exp(.) is wlement-wise exponential function. Similar to the hinge loss minimization, we show in the proof of Lemma A.2 that directly updating h with gradient term is not implementable. So,
13

---

Published as a conference paper at ICLR 2023
search in the hypothesis class for a classifier h such that h minimizes g).g), where g Vn R. Next lemma finds such a classifier along with the optimal step size.
Lemma A.2. For any hypothesis class H. true classifier I E H. current classifier E H. c-approximate risk minimizer A, and any underlying distribution DD h A(Dn) ) is the solu- tion of minjgn (h,g): Here Du(a) & D(x) exp( exp((h(())((x)) and g = V.RD. Further, ? log( Ro, (1)) 1) is the best step size for the update rule h h + 17 h.
See proof on page 23
Let ht be the final classifier obtained after updates according to the updating rule of Lemma A.2
An analysis similar to the analysis of AdaBoost shows (b)h) S exp(- (1=2+)"t). This method, despite the exponential convergence rate, is not practical for two reasons. First, it is computationally
hard as reweighting distribution requires the calculation of normalization factor which is sum over the whole domain. Second, it requires sampling from D which might not be possible.
In summary, gradient-based updates guarantee convergence of the updated classifier to the true clas- sifier; however, they either suffer from slow convergence or computational hardness.
B MORE ON EXPERIMENTS
We elaborate the details of datasets, models, and further observations from the simulation of path dynamic benchmarks in this section.
B. DATA AND MODELS
The CIFAR-10 dataset contains 60, 000 of 32 x 32 color images in 10 different classes, commonly used static benchmark for image classification. We use a shallow feed-forward Convolutional Neural Network (CNN) consisting of two convolution layers (with 32 and 64 filters), interleaved with two max-pooling layers, followed by a dropout layer and a dense layer with 10 units at the output, increasing total number of trainable parameters to 40k. We use the same architecture to train a base model and train classifiers drawing rollouts. The base classifier achieves 73% accuracy after 30 epochs on the training data, reasonably above the chance level of about 10%.
The Stanford Natural Language Inference (SNLI) corpus (version 1.0) is a popular NLI benchmark consisting of 570k human-written English sentence pairs manually labeled for balanced classifi- cation with the labels entailment, contradiction, and neutral. We restrict our simulation to a 50k random subset of this data. Our model is a slightly modified model of Bowman et al. (2015) where words are represented with pre-trained 100d Vlo vectors, and two parallel Bidirectional Long Short-Term Memory layers (BiLSTM) are used to extract sentence embeddings. The concatenated embeddings are then fed into three more hidden dense layers (each has 128 units) before going to the last dense layer with 3 units. The model has total number of 1 120k trainable parameters, and the base model achieved an accuracy of 68% on the training data and 61 % on the test data, consistent with the original study when the number of samples was limited.
B.2 FURTHER OBSERVATIONS
The observations had in Section 5 raise another question: what makes a rollout a bad rollout? Do bad rollouts share common characteristic? We hypothesize the more similar a rollout to the bad sequence constructed in the proof of Theorem 3.5] the worse its final risk. A unique feature of the negative example in Theorem 3.3 is that initial classifiers in the sequence cleverly choose their error sets to only overlap on a fixed part of the distribution, which will turn out be the error set of the majority. We define a score that captures this behavior without being directly related to the accuracy of the final majority vote model. Let Fm be the error set for the majority vote classifier and ER, be the error set of the round t classifier. Then for every pair of distinct rounds t < T [Eng DEN, nEm! Fo,e, n.
of rollout, define 24,12
We use 2T -(- En,0 2tz=0, Zt. to
TT T-
http://nlp.stanfin
6.. zip
14

---

Published as a conference paper at ICLR 2023
0.062
0.024
risk of majority vote round 25
0.023
0.022
0.050
0.021
0.020
0.056
0.019
0.018
0.052
0.46
0.48
0.50
0.52
0.54
0.20
0.22
0.24
0.26
(a) CIFAR-10
(h) SNLI
Figure 5: Similarity to the theoretical negative example measured by 2T can partially explain the risk the majority vote classifier of all rounds. The blue dashed line is the minimum squared error fit.
quantify similarity of a rollout to the theoretical negative example. The proof of Theorem 3.5 shows that as long as T < 2. the theoretical negative example gives 27 =
Figure 5a depicts the risk of the majority vote the end of the rollout (round 25) 24
The correlation is positive and statistically significant (Pearson r = 0.46, < 0.001). So, the more similar rollout the theoretical bad example terms the defined score, the more likely it will be a bad rollout. Interestingly, at round 4, the risk of the majority vote classifier can barely explain the risk after 25 rounds (Pearson r 0.18, p > 0.05). This shows our negative example construction has not only introduced worst-case example but might have identified an important characteristic that naturally appears in dynamic benchmarks and limits their effectiveness.
Figure 55 also shows significant positive correlation (Pearson r 0.68, p 0.001) between the final risk of rollout and its similarity the theoretical negative example measured early at round 6. At this round, the risk of the current majority vote classifier is barely informative about the risk after 20 rounds (Pearson r -0277. p > 0.05). Once more, shows the negative example constructed theoretically can explain the natural failure of dynamic benchmarking in different contexts.
C ADDITIONAL STATEMENTS AND PROOFS
Corollary C.1. Under conditions of Lemma 3.1 let i be one of the h4s selected uniformly at ran- dom. For any and 0, ifT 2 8n with probability at least 1- a-accurate.
Proof. From Lemma 3.1 the probability that h is o-bad is less than 1/2 < 8.
Proof of Lemma 3.1 As supp(Po) C supp(D), running the path dynamic benchmarking will pre- serve (u,)(D,) S supp(D) for any t. On the other hand, we know RD(f) = 0. So, have RD, (f) = 0. As A is perfect risk minimizer and H. we should have Rp, (h₂) = 0. Therefore, errors of h2 should happen outside of supp(D,):
E, 1 supp(D,) 0.
(9)
where F, is the error set of hG, Now assume / one of the indices where h4 is a-bad, i.e., (rD(F.)
Then have
Pr(x supp(D:+1)) Pr(# supp(D.)) Pr(æ E E,) 2 Pr(x supp(D:)) ta. D
(10)
This cannot happen more than times.
15

---

Published as a conference paper at ICLR 2023
Proof of Theorem 3.4 Starting from Do where (up)(Do) S supp(D), path dynamic benchmarks will preserve supp(D;) S supp(D) for any t. Since the problem is realizable and A is e- approximate risk minimizer, for any consistent h, we should have RD. (h+) I e. The distribu- tion D, itself is mixture of the initial and error distributions: Dr mix(Do; Do. DD-1)- So, we can expand Rp, (.) as a linear combination of the risks under mixture components. Note that the risk of he under an error distribution Dyr where < t, can equivalently be written as RD, (I+) Pro [E Be). For 0, 1, 2 we have:
RD, (ho) S
1
1
Ro. (11) + Pr( Bmu Bno) S
2
2
1
1
RD. (h2) + Pr Pr(En, Bno) + Pr( Pr(Ehn Bh,) S.
3
3
3
The above constraints impose RD, (h+) = PRD. (Ei) S +t+ 1)E and Pro(Ed Ee) I (t + 1)e. However, to limit the joint error probability of two classifiers need to bound Pro (E:):
Pr(E.) (h z RD. (h) + duan((oo D).
P
(11)
Finally, by union bound, the error probability of maj(ho. 1,, h2) is less than the sum of all pairwise joint error probabilities. Putting these all together:
RD ( maj(ho, hn, h2)) S Pr( (no n EN,) + Pr((Fnn n ENg) + Pr(En, O Eng)
D
D
s 11c² + Sedzax
(12)
Proof of Theorem 3.5 For given domain X, we define a new finite domain Xa E X such that Na can be shattered by H. For an arbitrary but fixed order on Xd. we can define equivalent vector representations of functions and distributions the new domain. Particularly, let be binary classifier defined on X. The vector representation of h in Xa is h = (h(z))=Exa e {-1, 13d. Similarly, let P be probability distribution over X. The vector representation of P in Xa P (P(x))eEXx k elements. We also use P(C) as a shorthand for ΣBEK P(x). Throughout the proof we use interval notation for discrete intervals. For example, (a,, b) denotes {a, + I,...,b 1}. Finally, h1 o h2 denotes the entrywise product of h1 and h2.
1
A(xa). Throughout the proof, we use K. to show subset of Xa with
The four allowed operations on classifiers and distributions have new interpretations in the new domain:
1. D. A, hy: The fact that is an e-approximate risk minimizer imposes the following constraint:
(h4 D.)
Σ D((1)
Σ
Dz(x) = - -2RDD (ha) 2 1 - 2c. (13)
((())(()==1
hr(=))(a)=-1
2. hr to see
H Dr: Let Kr, be the set of indices that h4 and f disagree. Then, it straightforward
D. = D(C,))
D h D).
(14)
3. (ho, hi,.... .h)) maj h: This is equivalent to per dimension voting: h(x)) =
maj(hn(2), h, (z), (x)) for x E X...
4. (Do, Do, DI,... .....,,D.)) D.-1) mix D,: This is simply equivalent to the weighted sum of
D, = wro Do + Σ Wr.DDDe
(15)
where are the weights of the mixture components, summing up 1.
16

---

Published as a conference paper at ICLR 2023
Note that in all of the operations ht and f have appeared only h, f. Since Xy can be shattered by H. without loss of generality, we assume f is all one and use h, instead of h ff in the following.
Next, start from the initial distribution Do as the input the path dynamic benchmarks and find the constraints imposed over variables throughout the process:
Do A hg: In this case (ho; Du) -1 (Do((K)) and Equation 13 requires:
Do(Ko) S..
(16)
Di A hy: For Dr defined in Equation 15 we have:
(h1, D.) wr,0 (hr, Do)
Σ
Ewwr Ter Dr>,
(17)
Pat
where (he, Do) 1 (Koo and
(h1, Dr) 2D((Gr)
(hv, - (he by, Di)
(1-2D(K)) -(1 -11-
UKe - -K
2D((K,,)
=1 D(C, nke)
(18)
D(Cr))
Here we used D(K, U.p - Kr n KGr) = D(K.) + D(C.)) - 2D(K, n Krr). Plugging
(hs, Dz)) into Equation 17 and requiring (h,, D.) 21 26 from Equation 13
impose
D(K, S..
Wr.DDo(K..) + Σ Wi, D(Kr)
(19)
d't
In the following, we propose KGS such that constraints of Equations 16 and 19 are satisfied. These are the necessary and sufficient conditions to have h&s consistent with path dynamic benchmarks.
For < / < T = 2: Consider KGs such that Kr, n Kr K. for any l' t. Sufficient conditions to satisfy Equations 16 and are
Kg Krp K. D(K) k
(20)
(21)
D(K,) K 2
Dol(e) S 2
(22)
at every time step. Let's reorder axes in an ascending order of Do and name them from to d. Also assume this results in an ascending order of D as well. For example, D unif(Xa) always
satisfies this. We set K. [1, k) and Ko [1, k') where k 26 Then for s T
we
K, = KU (K' + (t- (k k), k' + l(k' k)):
K:: A
22
Ko :
Ki +
W-k
K₂ : 4
N/ Ae
is straightforward to see that this assignment satisfies Equations 20 and 21 Since axes are ordered
ascendingly according to Do, sufficient condition to satisfy Equation 22 for all rounds is
2k
Do((Gr-)) S (K' + (T 1)(k's - -))) K'' Do(TK') = Do
S 2
(23)
17

---

Published as a conference paper at ICLR 2023
2k', " the above condition is Du(v) - J, Again, since axes are ordered in an ascending order of Do. Do(u)= S d-g+1 (otherwise, the sum of Do elements will go above 1). Then simple calculations show d 2 2y = _ is sufficient to hold Equation 23 Since k is an integer, this is
For y
y'
possible for d 2 2 which requires VCdim(H) 2. For d 24 this gives / =
For t 2 T: We set h = hage) where & : [T, 00) + [0,T - 1] is an assignment function working as follows. We define updated weights for 0 S T < T:
0t,0 = W0.0
(24)
1rr = 1 +
Σ TEU
We (,((((((t)) = T}.
(25)
Then (0-) assigns round t according to
(t) =
arg min Ut 0ST<T
(26)
The sum of the updated weights satisfies
Σ
Tt.
Σ
Ue +
Σ TSUSI
WEN Σ (((()) -
Σ
TeF S 1,
(27)
OST<T
OSTET
UST<T
where we used the identity Eoster (b((')) [} 1. This guarantees
1 E r(,(()) S T 2
(28)
Plugging he = hep()) into Equation 19 gives:
D(K)
D(K)
wr,0 (o,oDo((Es +
WhAT
D(K+)
Σ
Wif D(Ko(())
0ST<T
TSPKE
D(K))
D(K))
=or,oD((Cote)) + (WEDir) +
Σ
war)
+ Σ
Σ
Wh. D(K+)
WEF
D(K)()))
Tst'st
OSTET T(((())
TeP oit (((())()))
((t)=((())
$ <(w,,0 [w000+ +
Σ Der +
Σ
W1,
+ (t,((t) Se
(29)
2
OSTET T#P(())
TEt's ((())(())
Here used the following observations. Since h, satisfies DK( I 5 for all 7 t, he also D(K) [[C,] and DiKoce)) are bounded by &
satisfies Do,,,) = Do(()))))) < 5. Also all the ratios D(K)
according to Equation 21 We finally applied Equation 28 to bound Vc,0(t)- This completes our argument that h2 is consistent for 2 T.
So far, we have introduced a sequence of classifiers (hę), which are consistent with path dynamic benchmarks and all misclassify XC. We also showed for the selection of d .. we have _ = g The only required assumption is that the element of Do and D are both ascending. For the special case of DD = unif(Xa). D(K)= a Since elements of I. are misclassified by all the classifiers, no matter how the majority vote of them is calculated, K. will be in the error set:
k 2²
Rp ha. 2 D(K) d
(30)
This completes the theorem.
Proof of Theorem 3.6 Let Dj- Drlexx and DJ Dil Also let 6, PrD, (1r 23). So, we can write D. as mixture of its restricted distributions: D, = 6.D, + (1-6,)D? The classifier he trained on D, should satisfy
8, + (1 - 5.) (hz)
RD, (1x) = 6, Roy (lu) + (1 - R (1x)
2
< min Rv, (h) + = 8t
+c,
(31)
keH
2
18

---

Published as a conference paper at ICLR 2023
which requires (1 (1 R (h+) S c. Here used the fact that labels of 2 are equiprobable to be 1 or -1. So, risk of any classifier under DI is z. The inequality comes from A being e-approximate risk minimizer and the last equality is due the realizability DĀ. The error distribution of h2 is
D. Dr + R) (he) D 51 5 (h+)
(32)
where DD = Dl Plagxe Dj = Dleext (x) D = Dlagx' ((()) and 5 = Pro(# E x*). Note that again we used the fact that labels of X are random. Since Do D has weight of 7+1 in Dj:
R (h+) S (t
S
(33)
6;
So, the weight of Dj component in D. (Equation 32 will be greater than or equal to (1 + 2(t +
1) (-)))) ) Then the total weight given to X by distribution D141 = 142 Dr + 442 Dr will be
t t+1 be + ++2 1 2(t 1)
1
6i+1 2 +
(34)
The first observation from the above equation is
1
61 21+25
(35)
where we used 6g = 6. For sufficiently large 4. 81 goes above which means more than half of the benchmark will be focused on the unrealizable instances. Next, we show this not limited to the first round, and & maintains large proportion of DD as we progress. Recursively expanding Equation 34 and assuming I
8
Σ 1+ at
5e
t+1
t+1 F=1
8
In(1 + a(t+ + 1))
In(1 +
8
In(1 + + a(t+ +1)
+
+
++1
a(t+1)
+(t+1)
t+1
8
at at/(1 + =/(1ta]]
8 t
>
+
1) 1) at/ (1)) a)) t+1
(36)
t+1 all
[+1
1 a( +1
where a= 45 5). We applied In(1 + x) 2 to obtain the last inequality. This shows the upperbound cannot decrease faster than f2 ((t)))
). For > we have
1
8, 2 2(1 + 2at)
(37)
2(1 + 8gt))
So, for 3.3 & 2 21488J This completes the proof.
Proof of Theorem 4.7 the proof of Theorem 3.4 Also for notation convenience duan D).
We use the same notation as Figure 2 and follow similar arguments as the shorthand Ag to denote
Starting from the first path dynamic benchmarking step (ho hı - h2), in Theorem 3.4 observed: Now we can bound (go by
Rp( S 11e² + SEAo.
(38)
For the second path dynamic benchmarking step (hs - h4s - hs) we have:
1
RD. (ha) +
Pr(
Fr, 1Fgo) 6
(39)
2
2
1
1
1
Rp. (ha) +
Pr( Er, (...))
+ Pr Eh Eb,) S
(40)
3
3
3
1
1
1
RD, (h5) + Pr( Eng (ETO0)
+
Pr Eng Eng) +
Pr Eng BBa)) S..
(41)
4
4 D
4
D
D
19

---

Published as a conference paper at ICLR 2023
These equations let bound Rx(91) and Pr Ego):
RD(g1) - Pr(Enn n Bhha) ) + Pr( Phs n Ebs) + Pr(ERs n Ehs)
D
D
D
S 3e(E + Ao) + 4E(2c + Ao) + 4E(3E + Ao) =26E² 1ledo,
(42)
and
Pr(En, (B00 S (B))) + Pr(Ena (gg) + Pr(Ens (ng S 2e + 3E + 4e = 9c.
(43)
D
D D
Finally, for the third path dynamic benchmarking step (hs - h7 - hg) we have:
RD (ho) +
Pr
Pr(Ehu Ego) + Pr
Pr(Eng D
Ehe 1g1)5c
(44)
3
3
D
3
Rp. (17) + Pr Pr(Eny Eg0) +
Pr Bhy (g + Pr(En, [bhe Se
(45)
4
4
D
D
RD (hs) + Pr(
[Fhgl Fggo)
+
Pr(
Fhg Fgg)) + Pr( (hn (Fho) + #5 D
Pr Pr((Fng [mg) Se. (46)
D
D
D
This lets us bound Pr ) and Prp Eg)):
Pr Pr Ego) < Pr(Enn (oo) Pr(En, po.) Pr Pr(En, (go) S 3E + 4e + 5c 12e,
(47)
D
and a similar calculation shows Pro Egg Eg,) I 12c. Putting these all together, we can bound the risk of maj(go. 91:00/99.92 91. by
(m(maa(go, 91. 92))
Pr Eg n Egg Pr(Egg Egg
Pr( (r(FF 0 Egg))
s (g) Pr(Eg, Ego) (g0 Pr (r E..) Rp(gi) Pr(Egu D
s 9e(11e² + 8ADE) + 12e(11e2 + 8Auc) + 12e(26e² + 11Agc)
543e + 300e An.
(48)
which completes the proof.
and define equivalent vector representa- tions of functions and distributions in finite domain X 2 such that X² can be shattered by H (so, d < 3). ). We also name variables according to Figure For a true classifier f. Kr, denotes the set of indices where h, and ff disagree. Similarly, K,,, the set of indices where f and 9, disagree.
Proof of Theorem 4.2) We follow the proof of Theorem 3.5
First of all, we reorder axes in an ascending order of D Also assume this results in an ascending order of D well. For example, D unif(Xa always satisfies this. Naming axes from to d and
20

---

Published as a conference paper at ICLR 2023
showing them on the horizontal line, assign Kis and gg according to:
Ko:
K1
K2
Kgn
-1
K3 : A
K4:4 :
Ks H
Kgi : x
1-1
KB : 4
K7; 4
Kg: it
Kgg= : +
Next, we discuss each path dynamic benchmarking step and find sufficient conditions under which K,s are consistent with the dynamic benchmarking routine.
1. For the first path dynamic benchmarking step (ho - h, - h2), let Ko [1, 2 Kn
[1, ( 3 }. and K2 u2 2. - 2/ We have
Kg Konk no nK 11
(49)
D(Kgo) D(Kgo) Se. D(KG)
S D(Ko)
(50)
With a similar reasoning as the proof of Theorem 3.5 the only remaining condition to ensure ho. h1, and fi2 are consistent with path dynamic benchmarks, regardless of the weightings, is Do((2) < 6. The output of this step has the error set of Kgg = [1, no matter how the weighted majority vote is calculated.
2. For the second path dynamic benchmarking step (h3 + h4 + hs). let let K. KG
1 1], K. = [ 1] ( + 1, 2 - 11, and Ks = [1] u
13 -
1, - -1], 1]. We have
- 2
Kg = = = kinks [1]
(51)
D(Km)) D(K)))
Se
(52)
D(K4)
D(K3)
D(Ks)
D(K())
D(Ks))
S.
(53)
D(K,n))
D(C)))
D(K
21

---

Published as a conference paper at ICLR 2023
It is easy to check that for any weighting of mixture components, if Do((s) I e. h3, has and hy will be consistent with path dynamic benchmarks and the output of this step has the enror set of ggg. [1] J ( 11. Note that Po(Ks) guarantees (K())) as well.
3. For the third path dynamic benchmarking step (he h7 - hg), let Ko u
1. 2 2]. Kr
[1] ( 1-5-1, 1 2] U ( + 2. + - and Ks8
[ 1, - 2 2]. We have
=o nky = Ko nKs KG = [1] (- -----11- 1,-
3 2]
(54)
E
m)
- D(K
Se
(55)
D(KG)
D(Ko)
D(Ko) D(K7) D(Ka)
S
(56)
D(Cmo) D( ((C)o)
D(Ko) D(KG) D(Ks)
D(Kg.) D(K,,) ((Cg,)) S.
(57)
Again, it is straightforward to see that for any weighting, if Do(CC) c, ha, hgg and hg will be consistent with path dynamic benchmarks and the output of this step has the error set of gg [1] ( 1, 2 2]. Note that (K( I guarantees Do(Ks) well.
Putting these all together, to make the provided classifiers consistent with hierarchical dynamic benchmarking, it suffices to show Do(Ks) Se
3 1 1 )) sc. (
Do(Ks)) s Dol
2)
(58)
2
Since axes are ordered in an ascending order of Do. Do(l)= S J-I+1
Otherwise, the sum of the
Do elements would go above 1. So, we have:
- Se
(59)
which imposes d 2 1 + 3/2 1. For any valid i.c. e < 1/2 d= ? satisfies this condition. It also
satisfies the other limitation we had on VCdim(H). In this case
Rp maj](go 91. (2)) 2 D(C n Kg nk = D((1))
(60)
For the choice of D unif(Xa), this risk is = which completes the proof.
Proof of Lemma A. The derivative of R
Rhings (N) w.r. h.r. is:
althing
Mx)f(x) 21 ff(x)D((x) o.w.
g(x)
(61)
ah(x))
We can write g with vector representations
- Pr(EE) (f Dr) = - -Rhiige (h) (f Dr))
(62)
As mentioned earlier, updates of the form h == h 79 are infeasible as in practice Dj is only available at limited samples. To make it practical, let h = A(Dx). As A is an e-approximate risk minimizer,
1 ho S. 2 2
1 ho
RD, (h) 2 (1-
DWY D.)SE. Sc
(63)
So, we have (h. f Dr)) 2 1 2r. For < 0.5, h will be descent direction.
n
22

---

Published as a conference paper at ICLR 2023
Proof of Lemma A.2
The derivative of RD (h) w.r.t h(x))(()))))))))) is
g(x)
( ōh(z)
(64)
or in the vector space
g - -- D exppppphho
(65)
To find a good descent direction, we solve for
min (h. g) = (- D exp( f)).
(66)
NER
The solution this problem is the minimizer of Rp, (h) where D, is the true distribution weighted according to Dr, Z, D(x) (x)())(x))(x=)) and Zn is normalization factor make sure Dr will be probability distribution. Let A(Dr). Given A is e-approximate risk minimizer,
1 2 (1 ho f.))) = 2 2Zh
RD, (h)
( o f.Doo o exp(- f)) c.
(67)
2
So, we have (h o f, Do expl f)) 2 Zn (1 2e). For E < 0.5, h will be descent direction and the updating rule
h = h + h..
(68)
Finally, in order to find the optimum step size we plug the updated h into Equation g and solve for
min (b + + h) (exp(- (h + h) f), D).
(69)
7
Since the objective is a convex function of 7). it suffices to check the first order condition:
0Rp(h nh) (h f exp(-(h + h)) f), D)
On
(h f o exp(-n f), D exp( ho f))
= Zn exp( (1) Ro, (h)) - Zn exp(1) Ro, (h)= 0.
(70)
Solving the last equation gives
1 log(
1
1).
(71)
2
RD, (h)
Theorem C.2. For any c-approximate risk minimizer A with 1 E N, and path dynamic bench- mark with 3 rounds of model building and arbitrary mixture weights, there exists a hypothesis class H with (Cdim(H) < 4 such that for any true classifier f E H. there exists an underly- ing distribution DD where for any initial distribution Dy with supp(Du) S supp(D) that satisfies D(x2)) 2 D(x1) = Do(xz) 2 Do(x1), there exists sequence (h+ of classifiers consistent with the path dynamic benchmark where a similar lower-bound as Theorem 3.5 holds.
Proof. The proof is straightforward given the results obtained so far in the proof of Theorem 3.5 The way we constructed KG, is equivalent to selecting two subsets of R+ and changing their pre- dicted labels. So, let H' be the class of such functions, i.c., the class of unions of two intervals (VCdim(H') = 4). For any f f H', we select d points from the real line such that f(x) is all 1 or all -1. Let Xa Rd be the set of the selected points. Then induce probability distribution D on Xa such that D(x) å + a(x) where a(x) is an ascending function of r and E a(x) = 0. Then all of arguments in the first part of the proof will be true for any Da which is ascending or descending w.r.t æ. In the limit we have
2²
lim lD maj(ho. ... ....-)))
"hra 2 lim D(K) a 8
(72)
This completes the proof.
23

---

Published as a conference paper at ICLR 2023
Theorem C.3. For any e-approximate risk minimizer A with 1 N, and hierarchical dynamic benchmark with depth-2 and width-3 (Figure 2 with arbitrary mixture and majority weights, there exists hypothesis class H. with (Cdim(H) S such that for any tree classifier f H. there exists an underlying distribution 'D where for any initial distribution Do with supp(Do) S supp(D) that satisfies D(x2)= 2 D(11)) > Do((22) 2 Do((1), there exists classifiers consistent with the hierarchical dynamic benchmark for which similar lower-bound as Theorem 4.2 holds.
Proof. Given the results obtained the proof of Theorem 4.2 the proof of this theorem is pretry straightforward The way chose K,s in the proof of Theorem 4.2 is equivalent choosing three intervals from the real line. So, let H' be such class of function (VCdim (H') = 6). For any f E H'' select points from the real line such that f()) is all 1 all -1. Let Xa E IR be the set of the selected points. Then we induce a probability distribution on X such that D(x) = 2 + a(x) where o(x) is ascending function of and Exex, axx) 0. All of our arguments in the first part of the proof hold for any Do which is ascending or descending w.r.t æ. In the limit we have
lim RD (mai(go 91, (1l9g))) 2 lim D([ a-0
(73)
a-0
2
which completes the proof.
24


Reviews:
[{"review_id": "p1ckkE7q-E", "reviewer": "Reviewer_nUdN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the benefits and limitations of dynamic benchmarking from a theoretical view. For the model where data collection and model fitting alternate sequentially, the authors show the model performance improves initially but can stall after only three rounds for the commonly used path dynamic benchmarking. The authors propose a new model with a hierarchical dependency structure to circumvent this issue. The authors prove the proposed model enjoys a better theoretical guarantee than the former one, albeit with a significant increase in complexity. The empirical results support the theoretical analysis well.", "summary_of_the_review": "Overall, the notion of dynamic benchmarking is novel to me and the proposed theorems on path dynamic benchmarking and hierarchical benchmarking are interesting. But, I am still a little bit confused about the difference between this line of research and other research fields for improving data collection efficiency (like active learning). Besides, the ability of the annotator to access the unknown distribution $\\mathcal{D}$ is not clearly justified. I will raise my score if the author could address the above concerns.", "strength_and_weaknesses": "The strengths of this paper are as follows:\n- the notion of dynamic benchmarks is novel to me. \n- this paper shows the limitation of the popular path dynamic benchmark, which is interesting and instructive.\n\nMy concerns about the paper are as follows:\n\n- About the readability: I am a little bit concerned about the readability of this paper, particularly about the insufficient background introduction. As mentioned in the introduction, the dynamic benchmark is proposed to address the limitation of the static benchmark. But, a clear definition of the static benchmark and the motivation to study it is not provided in the paper. The authors have provided some references, but I think it would be better to at least include some basic definitions to make the paper self-containedness.\n\n- About the ability of the annotator: this paper assumes that annotators can access the conditional density of the misclassified instance over the unknown underlying distribution $\\mathcal{D}$. When is this assumption satisfied? If $\\mathcal{D}$ is accessible, why do the annotators not just collect the data at once? It would be nice if the authors could provide some practical examples.\n\n- About the related work: I think It would be nice to provide some discussion on the difference between active learning since both work aim to improve the data collection efficiency to improve the model's performance on a fixed unknown distribution. \n\n- Is there any theoretical result for the general depth-$k$ structure? Can this hierarchical structure continuously improve performance with deeper layers or stall with a certain depth?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YADt-9DvCPp", "reviewer": "Reviewer_SkQx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper initiates a theoretical study of dynamic benchmarking. It is proved that model performance could stall with alternative data collection and model fitting. Therefore, a new model where data collection and model fitting have a hierarchical dependency structure is proposed and proved a better progress but with much larger complexity. Some simulations are provided to support the theoretical findings. \n", "summary_of_the_review": "Overall, I think that the studied model in this paper is well-motivated. The idea behind the hierarchical structure is novel despite the complexity issues. Therefore, I recommend “weak accept”.\n", "strength_and_weaknesses": "\nStrength: This paper is well written and the topic of dynamic benchmarking is important and interesting. The theoretical results are sound and illuminate the benefits and practical limitations of dynamic benchmarking.\n\nWeakness: The proposed hierarchical structure alternative is with limited applicability (due to huge computational complexity).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KHXNxhamz9A", "reviewer": "Reviewer_8sGC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper theoretically studies dynamic benchmarking. Given that static datasets raise various concerns when used as ML benchmarks, dynamic benchmarks are proposed by researchers. In this setting, the ML model is trained against the current dataset, while the next dataset will contain new data points chosen to challenge previously built models. The main question is whether one can design such dynamic benchmarks so that the model's performance will improve as more and more difficult instances are added to the dataset. The authors provide a theoretical model for this problem and prove some negative and positive results, which are presented in the next section.\n", "summary_of_the_review": "This paper adopts a theoretical viewpoint regarding dynamic benchmarking and provides interesting lower and upper bounds for the proposed theoretical models, which are natural. I found this paper very interesting and I vote for acceptance.", "strength_and_weaknesses": "The paper first introduces the natural and intuitive path dynamic benchmarking architecture and provides the following results: in the realizable setting under the proposed  sequential architecture, it is shown that the trained model will get $O(\\epsilon^2)$ error in 3 rounds and there is an $\\Omega(\\epsilon^2)$ lower bound for any larger number of rounds. Namely, there is no provable benefit to dynamic data collection beyond 3 rounds in the path model. The authors also show some negative results when one has label noise.\n\nMoreover, since the above sequential model has provable limitations, it is asked whether there exist different ways to design dynamic benchmarking architectures. In particular, a “hierarchical” model is proposed that achieves error $O(\\epsilon^3)$ when used with depth 2.\n\nI find this paper extremely interesting. I really enjoyed reading the paper and I believe that the result constitutes an important contribution to learning theory. At a technical level, the lower bound for the path dynamic model is very nice and perhaps surprising. The paper is clearly written and the problem and results are clearly organized.\n\nI would like to conclude with some questions for the authors: \n\nQ1. In Theorem 3.5, the statement says that there exists a sequence of classifiers that is consistent but whose weighted majority has high error. Is it possible to lower bound the probability of observing such a bad sequence?\n\nQ2. Is it possible to extend the negative result for any Boolean function (in particular, Boolean functions that could potentially satisfy a variant of Proposition 3.2)?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster