Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 

strength_and_weaknesses: 
Strength: 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.

Weakness: The proposed hierarchical structure alternative is with limited applicability (due to huge computational complexity).

clarity,_quality,_novelty_and_reproducibility: The paper talks about interesting and important topics related to  dynamic benchmarks with good quality and clarity. The idea is novel as far as I know.
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”.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: The strengths of this paper are as follows:
- the notion of dynamic benchmarks is novel to me. 
- this paper shows the limitation of the popular path dynamic benchmark, which is interesting and instructive.

My concerns about the paper are as follows:

- 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.

- 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.

- 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. 

- 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?

clarity,_quality,_novelty_and_reproducibility: - Clarity: the paper is generally well-structured, but some parts are still unclear to me (please see the first point of weakness for more details).
- Quality: the theorems seem correct. But I am confused about in which case the annotators can access $\mathcal{D}$ and why they do not just collect the data from $\mathcal{D}$ at once.
- Novelty: the notion of the dynamic benchmark is novel to me. 
- Reproducibility: proofs of the theorems are provided.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

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.

Moreover, 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.

I 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.

I would like to conclude with some questions for the authors: 

Q1. 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?

Q2. 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)?

clarity,_quality,_novelty_and_reproducibility: The paper is quite clear and the results are very well presented and explained. 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This is a theoretical paper of general interest: collecting datasets to challenge models provides up to now for a given task. Although this basic idea of dynamic benchmarking may sound appealing as a way of avoiding to label unnecessary points, many pitfalls exist, including just drifting away from covering typical but originally easier cases.

Strengths: a rigorous formulation of ways by which the problem can be solved (including what it means to solve it), leading to the introduction to new ways of looking at the problem via the concept of hierarchical dynamic benchmarks.

Weaknesses: it is no immediately obvious what the practical implications of these theory are in the short term.

justification_for_why_not_higher_score: It is no immediately obvious what the practical implications of these theory are in the short term.
justification_for_why_not_lower_score: The paper provides a rigorous formulation of ways by which the problem can be solved (including what it means to solve it), leading to the introduction to new ways of looking at the problem via the concept of hierarchical dynamic benchmarks.
Decision: Accept: poster