Summary
This paper studies active learning in a multi-group setting, in which the learner performs adaptive sampling over groups of distributions for solving a binary classification task. The performance of the learner is measured by its maximal loss over the groups. The main goal is to extend the disagreement-based active learning approaches to the multi-group setting. To achieve this, the paper proposes a novel worst-case (over groups) loss estimator for the learner. The theoretical analyses on the sample complexity of the algorithms using this new loss estimator are provided.
Strengths
- The paper considers the multi-group extension of the active learning problem, which is likely a hard problem of high interest for the active learning community. The setting considered in the problem can also be seen as a variant of the Group-DRO problem in which the set of hypotheses and the loss function are not assumed to be convex.
- The paper shows rigorously why the traditional disagree-based active learning approaches in the multi-group setting, and proposes a novel multi-group loss estimator with reasonable theoretical guarantees.
- For the most parts, the writing is clear and easy to follow.
Weaknesses
Major:
1. The main algorithm, Algorithm 1, seems computationally intractable. A thorough computational complexity analysis is lacking, especially in the most important steps in Algorithm 1 on line 4 (computing $R_i$), line 21 (computing $\hat{h}_i$) and line 22. These steps involve filtering two sets ($\mathcal{X}$ and $\mathcal{H}_i$) that are possibly uncountably infinite, however no explanation is given on how these steps are done. This reduces the impact of the proposed approach to practical scenarios.
2. It is not clear why the sample complexity bound given in Theorem 1 is an improvement over passive and collaborative learning. The bound in Theorem 1 still depends on $d/\epsilon^2$, which is confusing since the text wrote ``the interaction between $d$ and $1/\epsilon^2$ is removed". In fact, the additional multiplicative factor $G\theta_g^2\log(1/\epsilon)\nu$ can be larger than 1, which makes the bound in Theorem 1 worse than the collaborative learning bound shown in Table 1.
3. A lower bound is lacking, which makes it impossible to judge how tight the upper bounds are.
4. Empirical evaluation is lacking.
Minor:
1. Throughout the paper, the references to various technical lemmas are missing. In Section 5.2, the paper wrote "it is a lemma of ours that...", with no references. Similarly, the proof of Lemma 1 in the Appendix (line 433) mentions "a lemma of Vapnik [28]", which is meaningless because Vapnik [28] is a 700-page book.
2. One the same line 433 - 434, the $1/m$ term in the uniform convergence bound looks redundant. Mathematically it might be correct, but a tighter (and simpler) bound that only depends on $\sqrt{\frac{\ln(8/\delta) + d\ln(2em/d)}{m}}$ (up to constants) are well-known and can be found in any standard machine learning texts (e.g. see [1], section 28.1, page 393).
3. This factor of $1/m$ is missing in the second equation on line 440, the first term.
4. In the main text: "with the ability decide" -> with the ability to decide; "not enough infer" -> not enough to infer; "would chose" -> would choose.
5. Typo in the equations in Example 1: it should be $\ell(h, i, A)$, not $\ell(h, i, S)$.
[1] Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA.
Questions
1. Can the authors comment on the computational complexity issue above regarding the computation of $R_i$ and $\mathcal{H}_{i+1}$?
2. How exactly is the bound in Theorem 1 better than the existing bounds in related settings?
3. How can we compare the results in the paper with the sample complexity lower bound for adaptive sampling strategies in the Group-DRO setting [1]? I am aware that the two settings have different assumptions on the convexity and compactness of $\mathcal{H}$ and $\ell$, so my question is restricted to compact convex $\mathcal{H}$ and convex $\ell$ only. In other words, would the lower bound in [1] apply if $\mathcal{H}$ is compact convex and $\ell$ is convex in your active learning setting?
[1] Optimal algorithms for group distributionally robust optimization and beyond. Soma et al., 2022.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
I suggest the authors to include more detailed discussion of the limitations of the proposed algorithms in the main text. These include any computational as well as theoretical issues raised above.