Group-wise oracle-efficient algorithms for online multi-group learning

Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper.

To your first point about the multi-class case, we actually do address this in Appendix C. In the main body, we only included a Remark on line 248, but Appendix C includes all the details for a finite, $K$-valued discrete action space $\mathcal{Y}$. Our main theoretical guarantee for such a case is Theorem C.1, and the algorithm for this case is Algorithm 4.

To your second point about the measure theoretic Definition 4.1, we agree that this may be overly technical. We do need the definition to properly define our setting, but we will take care to define essential supremum and absolute continuity. We will also emphasize that thinking about the results in terms of our simple example where the base measure $\mathcal{B}$ is uniform on $\mathcal{X}$ is sufficient for understanding our results.

Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper. In particular, we appreciate your feedback on the presentation of our results and related work, and we believe that addressing these issues will greatly improve clarity.

To your first point on related work, space limitations did not allow us to include a table in the preliminary submission, but we agree that a table of existing results would help presentation. Please see the attached rebuttal PDF for our draft of this table. For multi-group learning in the online, sequential setting, the only two works that provide comparable regret bounds are, to our knowledge, [BL20] and [Ach+23], which both obtain a $\sqrt{T_g \log |\mathcal{H}| |\mathcal{G}|}$ regret requiring enumeration of $\mathcal{H}$ and $\mathcal{G}$ or $\mathcal{G}$ itself with an oracle for $\mathcal{H}$. We will state this in our table in the camera-ready version, making specific note how the algorithms fare in terms of space and computationally complexity, our main concern. In the online learning setting without group considerations, we can include the existing results for smoothed online learning from [Blo+22] in our table, which, to our knowledge, are the best possible regret bounds for the smoothed setting.

To your second point on AMF and FTPL, we appreciate the feedback and believe it is important that the intuition of these two main ingredients is clear. In a nutshell, the AMF framework allows us to have low-regret with respect to all $\mathcal{G} \times \mathcal{H}$ pairs; the multi-objective regret guarantees are useful for our purposes because we want to guarantee simultaneous low regret over all $\mathcal{G}$. However, naively applying AMF requires us to enumerate these objectives, in turn enumerating $\mathcal{G}$, the main issue we want to avoid. FTPL comes to the rescue and allows us to have low-regret to all $\mathcal{G} \times \mathcal{H}$ pairs implicitly without enumerating them. So AMF allows us to compete with all $g \in \mathcal{G}$; FTPL ensures this is efficient. We see that perhaps this needed more description in the Introduction, namely around line 82 in Section 1.1 (Summary of Results), so, in the camera-ready version, we will include the main novelty of using these techniques in the intro. We will also refer the interested reader to "Technical Details" in Section 4.2 for the main high-level description of the analysis and techniques. Then, in the "Technical Details" in Section 4, on line 258 and below, we will make sure this high-level description of our analysis is clear and that each component, the AMF and the FTPL, have a clear purpose.

To your third point about lower bounds, we agree that it is important to state the existing known limits, and we will provide details about existing lower bounds in the camera-ready work where we have more space. Statistical and computational lower bounds exist from [Blo+22], [HK16], and [HHSY22] for the oracle-efficient online learning setting without groups, so they immediately apply to our setting, as the group setting is a strictly harder generalization. We will include such lower bounds in our work. The lower bound of [HK16] motivates the line of work in oracle-efficient online learning, demonstrating that, in the fully adversarial online setting, even when given an oracle for $\mathcal{H}$, regret must be $\Omega(T)$ unless we our time complexity is $\mathrm{poly}(|\mathcal{H}|)$. This motivates working with an optimization oracle in more restricted settings, such as the smoothed setting we extensively study in our paper. Lower bounds for the oracle-efficient smoothed setting from [Blo+22] without groups show that, in the classification setting we consider, the $\sqrt{\frac{dT \log T}{\sigma}}$ regret is essentially tight. In particular, they show that any online algorithm with access to an ERM oracle cannot achieve sublinear regret against a $\sigma$-smooth adversary unless $T \geq \tilde{\Omega}(\sigma^{-1/2})$. So in the smoothed classification setting, our main result is essentially optimal.

To your fourth point, we definitely agree that a main open question in our work is the nature of the $(\mathcal{G}, \mathcal{H})$-optimization oracle. To our knowledge, [GKR22] is the only work to have explicitly stated instantiations for such an oracle. There are many computational intractability results for agnostic learning, and multi-group learning is at least as hard as agnostic learning, so we don't expect to get end-to-end computationally efficient multi-group learning algorithms in general.

To address Reviewer wskr, as well, we believe it would be very helpful to the presentation of the paper to include the algorithm description for the $(\mathcal{G}, \mathcal{H})$-optimization oracle in our paper so it can be easily referenced. Currently, we only make a passing mention to [GKR22], but we will include a lengthier discussion in the camera-ready version. There are two existing algorithms that reduce optimizing over $(\mathcal{G}, \mathcal{H})$ to weighted multi-class classification or alternating ERM over $\mathcal{G}$ and $\mathcal{H}$. Both suggest implementable heuristics in practice. In the camera-ready version, we will include the algorithms for the ternary classification oracle and the alternating minimization oracle, as well as their main guarantees from [GKR22] in the appendix or full body. We will also briefly discuss some heuristic possibilities for instantiating such oracles. We note that, due to the computational hardness of ERM in the worst-case, the oracle in [Ach+23] requires access to similar heuristics.

For more on the computational efficiency of this oracle, please see our response to Reviewer wskr. We believe that we have addressed all the weaknesses in this response and will make the appropriate additions in the camera-ready version. Please let us know if anything was insufficient or unclear.

Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper.

We definitely agree that a main open question in our work is the nature of the $(\mathcal{G}, \mathcal{H})$-optimization oracle. To our knowledge, [GKR22] is the only work to have explicitly stated instantiations for such an oracle. On a high-level note, our work follows a long line of work that exploit oracle primitives assumed to be computationally efficient (referenced in our work), so we don't expect to get end-to-end computational efficiency. There are a plethora of well-known hardness results for agnostic learning with various concept classes, and multi-group learning is a generalization of agnostic learning, so the need to assume such primitives is necessary in many cases (and models the empirical success of ERM despite hardness results).

To your first point in "Weaknesses," we agree that it would be very helpful to the presentation of the paper to include the algorithm description for the $(\mathcal{G}, \mathcal{H})$-optimization oracle in our paper so it can be easily referenced. In the camera-ready version, we will include the algorithms for the ternary classification oracle and the alternating minimization oracle, as well as their main guarantees from [GKR22] in the appendix or main body. We will also briefly discuss some heuristic possibilities for instantiating such an oracle.

To your second point in "Weaknesses," it is not entirely clear to us what the computational efficiency of such an oracle would be, at least in the theoretical sense. From a heuristics standpoint, the aforementioned ternary classification instantiation from [GKR22] can be instantiated so long as we have access to weighted multi-class classification, which, at least in practice, can be implemented with cost-sensitive classification packages. In this case, $\mathcal{G}$ is a byproduct of the class upon which this ternary classifier outputs a "defer" label. On the other hand, if there's a specific $\mathcal{G}$ we want to address, the aforementioned alternating maximization oracle from [GKR22] can be implemented with ERM access to $\mathcal{G}$. Of course, ERM is computationally hard in the worst-case, but heuristics for ERM exist and it is a common assumption in the literature to assume that, at the very least, approximate ERM is feasible. Because $\mathcal{G}$ is class of group indicators, this is equivalent to assuming that we have ERM heuristics for binary classification. However, we should mention that the alternating maximization heuristic can only be guaranteed to supply saddle points, not true global maxima. In both these cases, heuristics (either for multi-class weighted classification or ERM) exist that avoid enumeration. However, it's clear that both these methods have limitations, and we will point out these limitations in the camera-ready version, along with the algorithm descriptions, as we mentioned in the point above. We believe that it is an interesting and worthwhile open question to develop more specific instantiations of this $(\mathcal{G}, \mathcal{H})$-oracle for more specific problem settings that are computationally efficient and have provable optimization guarantees.

To your final point about real-valued action spaces, the main challenge is that our $\mathcal{H}$-player must solve a $|\mathcal{Y}| \times |\mathcal{Y}|$ size linear program, ultimately playing a distribution over possible actions which are of the order $|\mathcal{Y}|$. Because the $\mathcal{H}$-player must hedge against all possible $\mathcal{Y}$ the adversary could select in its linear program, we were only able to implement this step with discrete, finite label spaces. We believe it is an interesting open problem to extend our techniques to real-valued action spaces. One naive route might be to take a discretization approach, but a fine-enough discretization would defeat the purpose of the simple LP the $\mathcal{H}$-player must solve at every round. [Blo+22] does give an approach for the (single group) case for real-valued labels in the smooth setting, but the challenge remains to design a feasible game for the $\mathcal{H}$-player to solve at every round to hedge against the maximally adversarial choice in a continuous $\mathcal{Y}$.

Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper.

We will take care in the camera-ready version to make revisions to Section 1 that improve its clarity. In particular, the additional space of a page should allow us to address these issues adequately.

• Lines 54-55: In this line, we mean that if $\mathcal{G}$ is expressive enough, then any potentially relevant subgroup should be well-approximated by some $g \in \mathcal{G}$, and, therefore, any individual $x \in g$ should be ensured that the quality of their predictions are as good as the best possible prediction for their group. When we wrote that those subgroups would be "covered," we meant that those subgroups should be included in, or, at least, well-approximated by some $g \in \mathcal{G}$, so our guarantees apply to that subgroup. We will make this wording more clear in the revision, replacing this clause with "...but multi-group learning with a very rich and expressive family of groups $\mathcal{G}$ ensures that, as long as a subgroup is well-approximated or within the collection $\mathcal{G}$, it obtains our theoretical guarantees. This motivates dealing with large or potentially infinite $\mathcal{G}$ to provide guarantees for as many subgroups as possible."
• Line 18 + Line 76: Thank you for bringing this to our attention. We will clarify early in the introduction that $g$ (lowercase) denotes a single subset of $\mathcal{X}$. In the "Summary of Results," we will clarify that our regret guarantee is specific to each $g \in \mathcal{G}$ by starting the claim in Line 75 with, "...for each particular group $g \in \mathcal{G}$."

In addition to the comments you raised, we will clarify the descriptions in the Summary of Results using the added space. In particular, we will add sentences describing the parameters in the regret bounds, and, potentially, if there's still space, add a table to compare to results from previous work. We included a draft of such a table in the global Author Rebuttal PDF.

Please let us know, if, in addition to the proposed modifications above, there are any other clarity issues you noticed.