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

Authors: samuel  deng
daniel  hsu
jingwen  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:01:14

Abstract: We study the problem of online multi-group learning, a learning model in which an online learner must simultaneously achieve small prediction regret on a large collection of (possibly overlapping) subsequences corresponding to a family of groups. Groups are subsets of the context space, and in fairness applications, they may correspond to subpopulations defined by expressive functions of demographic attributes. In this paper, we design such oracle-efficient algorithms with sublinear regret under a variety of settings, including: (i) the i.i.d. setting, (ii) the adversarial setting with smoothed context distributions, and (iii) the adversarial transductive setting.

Main paper: 
 introduction: 
 We study the problem of online multi-group learning, originally introduced by [BL20] (adapting the specialists/time-selection setup of [Blu97; Fre+97; BM07] ). In this learning model, we consider a collection of groups G, which are (possibly intersecting) subsets of a context space X , as well as a hypothesis class H of functions defined on X . Contexts x 1 , x 2 , . . . , x T arrive one-by-one over a sequence of T rounds, and the learner must make a prediction associated with each x t . The learner's goal is to perform well on every subsequence of rounds corresponding to each group g ∈ G. Here, performance is measured relative to the predictions of the best-in-hindsight hypothesis h ∈ H for the specific subsequence under consideration.A common interpretation of multi-group learning-which is natural when considering fairness in machine learning (ML)-identifies contexts x ∈ X with individuals, each group g ∈ G with a subpopulation (perhaps defined by a combination of various demographic features such as age and gender), and each hypothesis h ∈ H with a classifier that makes predictions about individuals [RY21] . The goal of the learner, then, is to predict as well as the best subpopulation-specific hypothesis, for all subpopulations simultaneously. The standard benchmark in online learning is regret, which compares the performance of the learner on all rounds to that of the single best hypothesis in hindsight. But such a benchmark is only meaningful if there is a hypothesis that performs well in all contexts. At the other extreme, we may hope that the learner performs as well as using the best context-specific hypothesis in every round. However, this may be impossible if no context is ever repeated. The group-wise notion of regret in online multi-group learning naturally interpolates between these two extremes: the former is recovered when G = {X }, and the latter when G = {{x} : x ∈ X }.We are particularly interested in scenarios where G may be extremely large (and perhaps even infinite). In such cases, it is too time-consuming to explicitly enumerate the groups in G, and this precludes the use of the algorithmic solutions from prior works [BL20; Ach+23] . The use of highly expressive families of groups has been a recent focus in the ML fairness literature, where fairness with respect to such rich families of groups is seen as compromise between coarse notions of statistical fairness that ignore intersectionality, and individualized notions of fairness that are typically difficult to ensure [Kea+18; Heb+18; KGZ19; GKR22; Glo+23]. For example, if groups are defined by simple combinations of demographic attributes (e.g., linear threshold functions), then the number of subsequences determined by these groups may grow exponentially with the number of attributes. To deal with the intractability of explicit enumeration of groups, these prior works rely on optimization oracles that implicitly search through the family of groups. In this work, we seek to do the same, but for the online (as opposed to batch) problem at hand.Another motivation for multi-group learning with rich families of groups comes from the literature on "subgroup robustness" [Sag+20] , where one is concerned with the test-time distribution shifting from the training distribution by restricting to subsets (or "subgroups") of the feature space. Such scenarios have been practically motivated, for instance, in medical domains where training data sets are constructed to include data from all patients (healthy and sick) as a matter of convenience, but the population relevant to the application is only a subset of the sick patients for which an intervention is potentially possible [Oak+20] . It may be difficult to anticipate which subgroup will ultimately be relevant (or even to provide an explicit shortlist of such subgroups), but multi-group learning with a very rich and expressive family of groups G ensures that, as long as a subgroup is well-approximated or within the collection G, it obtains our theoretical guarantees. This motivates dealing with large or potentially infinite G to provide guarantees for as many subgroups as possible.We construct an end-to-end oracle-efficient online learning algorithm that is oracle-efficient in all the problem parameters. Namely, it is oracle-efficient in both H and G. In the case of finite H or G, this admits an exponential computational speedup over the previous algorithms; in the case of infinite G, this is the first algorithm that achieves multi-group online learning. With this in mind, we can even think of G as representing a binary-valued function class that takes in contexts and selects subsequences S ⊆ [T ] based on those contexts in possibly complex ways.Previous work has shown that the basic goal of designing a computationally efficient algorithm (in all problem parameters) to achieve o(T ) regret for fully worst-case adversaries is impossible [HK16; Blo+22] . Research has therefore focused on natural structural assumptions in which computational efficiency and sublinear regret is possible, albeit in the traditional setting without groups [SKS16; Hag+22; HRS22; Blo+22] . Because the multi-group online adversarial setting is strictly harder than the standard setting in which this lower bound applies (simply consider multi-group learning with one group: the entire sequence), we must also take similar assumptions to circumvent the computational hardness result. In this work, we consider the same structural assumptions in the multi-group scenario. Specifically, we make the following contributions (with Õ(•) suppressing log factors):1. Group-wise oracle efficiency for the smoothed setting. We present an oracle-efficient algorithm that achieves Õ( dT /σ) regret on every group g ∈ G for a binary-valued action space for the smoothed online learning setting of [HRS22; Blo+22] , where d is a bound on the VC dimension of H and G, and σ is a parameter interpolating between the scenarios in which contexts are generated by a worst-case adversary and a benign, fully i.i.d. adversary. 2. Group-wise oracle-efficiency through generalized follow-the-perturbed leader. If a sufficient condition referred to as γ-approximability in previous literature ( [Wan+22] ) is met, a variant of our oracle-efficient algorithm achieves, for each particular g ∈ G, a regret of Õ( N T g log |H||G|)for finite H and G, where N corresponds roughly to a required number of perturbations, and T g is the number of rounds t ∈ [T ] in which x t ∈ g. The dependence on T g as opposed to T is preferable if some groups do not appear frequently over the T rounds. As a special case, our T is the number of rounds of online learning, T g is the number of rounds for a particular group g, H is the hypothesis class, G is the collection of groups, and σ is the smoothness parameter defined in Definition 4.1. d is an upper bound on the VC dimension of H. In our σ-smooth result in the fifth row, d is also an upper bound on the VC dimension of a possibly infinite collection of groups, G. In the γ-approximable setting of the sixth row, N is the number of perturbations.algorithm also achieves Õ(N 1/4 T g log |H||G|) in the transductive setting of [BKM97; KK05] , where the adversary must reveal a set of N future contexts before learning begins.Table 1 summarizes our results in relation to existing work. Our algorithms follow a more general algorithm design template based on the adversary moves first (AMF) framework of [Lee+22] . We extend this framework with the following technical enhancements: sparsifying the implicit distributions over the hypothesis spaces used by follow-the-perturbed-leader (FTPL) algorithms, and simplifying the min-max game that is solved in every iteration of AMF.In particular, the AMF framework allows us to have low-regret with respect to all group-hypothesis pairs; the multi-objective regret guarantees are useful for our purposes because we want to guarantee simultaneous low regret over all g ∈ G. However, naively applying AMF requires us to enumerate these objectives, in turn enumerating G, the main issue we want to avoid. FTPL comes to the rescue and allows us to have low-regret to all pairs implicitly without enumerating them. So AMF allows us to compete with all g ∈ G; FTPL ensures this is efficient. The algorithmic details and main technical challenges can be found in Section 4.2. These techniques allow us to adapt this framework to the scenario where the number of groups is too large to enumerate, and they may find use in other multi-objective learning problems.[BL20] showed that it is possible to achieve sublinear multi-group regret by reducing to the specialists framework of [Blu97; Fre+97; BM07] (a.k.a. sleeping experts). The multi-group regret they achieve scales logarithmically in both H and G; this recovers the minimax regret when specializing to the standard online learning setting (with finite H) with only a single group. The paper focuses on regret rather than computational considerations; a direct implementation of their algorithm uses time and space linear in |H| × |G|, and there are no stated guarantees for infinite H or G.[Ach+23] show how to avoid enumeration of H using an optimization oracle for H. They achieve this by applying a meta-algorithm atop a black-box oracle-efficient online learning algorithm, but this meta-algorithm ultimately requires explicit enumeration of G. Our work, in contrast, uses an optimization oracle for G × H jointly and hence avoids explicit enumeration of either G or H.Multi-group (agnostic) learning has also been studied in the batch setting [RY21; TH22; GKR22; HJZ24]. In this setting, training data is drawn i.i.d. from a fixed distribution, and the learner's goal is to find a single hypothesis ĥ (possibly outside of H) that ensures small excess risk E[ℓ( ĥ(x), y) | x ∈ g] -inf h∈H E[ℓ( ĥ(x), y) | x ∈ g] for every group g ∈ G simultaneously. The works of [RY21; HJZ24] design algorithms for achieving this learning criterion under a certain "multi-PAC compatibility" assumption on H and G. [GKR22; TH22] design multi-group learning algorithms that remove the need for this assumption. One of the algorithms of [TH22] , which enjoys near optimal sample complexity for general but finite H and G, is based on the the online multi-group learning approach of [BL20] combined with online-to-batch conversion.The proof of our algorithm builds on two primary technical frameworks studied in previous literature: the adversary moves first (AMF) framework of [Lee+22] , and a line of work designing followthe-perturbed leader style algorithms [KV05] for adversarial online learning in the oracle-efficient learning model [KK05; SKS16; Hag+22; Blo+22; Wan+22].Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The three main theorems of the paper and their respective problem settings are laid out in the abstract and Section 1.1, the Summary of Results section, of the introduction. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
notation: 
 Throughout, X denotes a context space, and Y denotes an action space. For example, in a typical (online) supervised learning setup, X is the feature space, and Y is the label space. A group g is a subset of the context space X . We overload the notation g for a group by using it as an indicator function g(x) := 1 {x ∈ g} for group membership. Let 2 X denote all subsets of the context space X , and let Y X denote all possible mappings from X to Y. For an integer n, denote [n] := {1, 2, . . . , n}.For simplicity of exposition, we will focus on the setting where Y is binary throughout, i.e. Y = {-1, 1}. We note that our techniques are more general, however, and may be adapted to the case of finite, multi-class action spaces (see Appendix C for details).We formally define the multi-group learning model as follows. Let G ⊂ 2 X be a collection of (possibly non-disjoint) groups, and let H ⊂ Y X be a hypothesis class of functions h : X → Y mapping from contexts to actions. Let ℓ : Y × Y → [0, 1] be a bounded loss function. In each round t ∈ [T ]:1. Nature chooses (x t , y t ) ∈ X × Y and reveals x t . 2. The learner chooses an action ŷt ∈ Y.3. Nature reveals y t ∈ Y.The main challenge posed in this work is to design computationally efficient algorithms that work with both large hypothesis classes H and large collections of groups G. The prior work of [Ach+23] shows how to use the following optimization oracle to avoid explicitly enumerating the hypothesis class H (but still require enumerating G).Definition 2.1 (Optimization Oracle). For some error parameter α ≥ 0 and function class F ∈ Z X , an α-approximate optimization oracle OPT takes a collection of pairs (x 1 , z 1 ), . . . , (x m , z m ) ∈ X × Z, a sequence of weights w 1 , . . . , w m ∈ R, and a sequence of m loss functionsℓ i : Z × Z → [-1, 1] and outputs a function f := OPT({(x i , z i , w i )} m i=1 ) ∈ F satisfying: m i=1 w i ℓ i ( f (x i ), z i ) ≤ inf f ∈F m i=1 w i ℓ i (f (x i ), z i ) + α.Instantiating (in Definition 2.1) Z as our action space Y, each ℓ i as the given loss ℓ of our problem, and F as our hypothesis class H gives a standard empirical risk minimization (ERM) oracle over a dataset {(x i , y i )} m i=1 . We present this more general definition to distinguish the action space Y of the problem from the output space of the oracle (see Definition 2.2).The optimization oracle is regarded as a natural computational primitive because, for many problems in machine learning, various heuristic methods (e.g., stochastic gradient descent) appear to routinely solve such problem instances despite the worst-case intractability of such problems.The work of [Ach+23] still relies on explicit enumeration of G. We show how this can be avoided using a joint optimization oracle for G × H, defined as follows. Definition 2.2 ((G, H)-optimization oracle). Fix an error parameter α ≥ 0. For a collection of groups G ∈ 2 X , a collection of hypotheses H ⊆ Y X , and a sequence of m loss functionsEQUATION)If Y = {-1, 1} (which we assume in the main paper body), this oracle outputs a group-hypothesis pair (g, h) that maximizes the batch loss over m examples (x i , (y i , y ′ i )) in X × {-1, 1} 2 . [GKR22] also made such an assumption and gave two implementations: one based on cost-sensitive classification oracles for G and H separately, the other a heuristic algorithm that is empirically effective. Details of these oracle instantiations are included in Appendix B.3.We also require an optimization oracle for H itself, defined similarly. This can be thought of simply as (exact) empirical risk minimization over H.1 Definition 2.3 (H-optimization oracle). For a collection of hypotheses H ⊆ Y X , and a sequence of m loss functionsℓ i : Y × Y → [-1, 1], an H-optimization oracle OPT H is a 0-approximation optimization oracle (Definition 2.1, with α = 0) that outputs a hypothesis h ∈ H satisfying m i=1 w i ℓ i (h(x i ), y i ) ≤ inf h * ∈H m i=1 w i ℓ i (h * (x i ), y i ).3 Warm-up: I.I.D. SettingIn this section, as a warm-up, we consider a setting where Nature is stochastic and oblivious: the (x t , y t ) are drawn i.i.d. from a single fixed (but unknown) distribution µ, independent of any choices of the learner. In a standard online prediction setting with i.i.d. data, it suffices to use a "follow-theleader" (FTL) strategy (see, e.g., [Haz22] ), which can be easily implemented using an optimization oracle for H. However, such a strategy only guarantees low regret on g = X . To achieve low regret on all (possibly intersecting) groups g ∈ G simultaneously, we need a multi-group analogue of FTL.What makes FTL work in the standard online prediction setting is the instantaneous expected regret bound of empirical risk minimization (ERM) on i.i.d. data. Therefore, it is natural to replace ERM with a batch multi-group algorithm [TH22; GKR22]; this will ensure the requisite instantaneous guarantee on all groups g ∈ G. We show how to use the oracle-efficient algorithm LISTUPDATE of [GKR22] for the online multi-group problem.Throughout this section, we assume ℓ is the zero-one loss (for simplicity), and that H and G both have VC dimension at most d ≥ 1. For any g ∈ G, let P (g) := E (x,y)∼µ [g(x)] be the probability mass of group g. Theorem 3.1 (Theorem 16 of [GKR22] ). For any δ ∈ (0, 1), given n i.i.d. training samples {(x i , y i )} n i=1 from µ, the LISTUPDATE algorithm2 returns a function f : X → Y such that, with probability 1 -δ, for any group g ∈ G,E[ℓ(f (x), y) | x ∈ g] ≤ min h∈H E[ℓ(h(x), y) | x ∈ g] + 1 P (g) • O d log n + log(1/δ) n 1/3. Moreover, LISTUPDATE makes poly(n, d, log(1/δ)) calls to a (G, H) optimization oracle.Our algorithm, ONLINE LISTUPDATE, forms its prediction ŷt in round t as follows:• Run LISTUPDATE on the samples from previous rounds (x 1 , y 1 ), . . . , (x t-1 , y t-1 ). E[Reg T (H, g)] = O (d log T ) 1/3 T 2/3 + dT log T .The proof of Theorem 3.2 is given in Appendix A.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss the technical assumptions needed to design oracle-efficient algorithms in Sections 3, 4, and 5 (respectively, i.i.d. assumption, smooth assumption, and existence of perturbation matrix assumption). We also note that our work does not address group-dependent o(T g ) regret for infinite G and H, as mentioned in Section 6. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]Justification: All theorems are formally stated in the main body and proved in the Appendix. Each main theorem, Theorem 3.2, Theorem 4.1, and Theorem 5.1, are stated in the main body and proven in the Appendix. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
the learner incurs loss: 
 ℓ(ŷ t , y t ) ∈ [0, 1].The choices of Nature and the learner may be randomized. In the standard online prediction setting, the regret of the learner is the difference between the cumulative loss of the learner and that of the best-in-hindsight hypothesis from H:Reg T (H) := T t=1 ℓ(ŷ t , y t ) -min h∈H T t=1 ℓ(h(x t ), y t ).The goal of the learner is to achieve sublinear (in T ) expected regret.In multi-group online learning, we consider the regret of the learner on subsequences of rounds (t ∈ [T ] : x t ∈ g) defined by the groups g ∈ G and the sequence of contexts x 1 , . . . , x T . Specifically, the (multi-group) regret of the learner on group g isReg T (H, g) := T t=1 g(x t )ℓ(ŷ t , y t ) -min h∈H T t=1 g(x t )ℓ(h(x t ), y t ).(1)Crucially, the best hypothesis for one group may differ from that of another group. Further, groups may intersect, precluding the strategy of simply running a separate no-regret algorithm for each group. The learner seeks to achieve achieve sublinear expected regret, on all groups g ∈ G simultaneously.In this section, we first describe a natural problem setting in which oracle-efficient online multi-group learning is possible: the smoothed online learning setting (Section 4.1), for which the i.i.d. setting of Section 3 is a special case. We then present our main algorithm, Algorithm 1, for achieving oracleefficient online multi-group learning (Section 4.2). Easy modifications of this main algorithm will admit oracle-efficient online multi-group learning for other common online learning specifications, as described in Section 5.We We denote the set of all σ-smooth distributions on X with respect to the measure B as S σ (X , B). If B is clear from context, we simply write S σ (X ). We assume that we have sample access to B throughout. For simplicity, one may assume B is uniform on X .Definition 4.1 interpolates between the benign setting where x t are drawn i.i.d. from µ when σ = 1, and the fully adversarial setting when σ approaches 0. In this sense, the warm-up result of Section 3 is a special case of this setting when σ = 1 and µ is fixed for all rounds. Note that this definition does not restrict the choice of y t at all; y t may still be chosen adversarially.With this definition in hand, consider the following specification of the learning game outlined in Section 2.2, henceforth refered to as the σ-smooth online learning setting. For each round t ∈ [T ]:1. Nature fixes a distribution µ t ∈ S σ (X ) that may depend in any way on the entire history prior to round t. Nature samples x t ∼ µ t and chooses y t ∈ Y adversarially; x t is revealed to the learner. 2. The learner (randomly) chooses an action ŷt ∈ Y. 3. Nature reveals y t ∈ Y, and the learner incurs the loss ℓ(ŷ t , y t ) ∈ [0, 1].We now depart from the previous literature that considers oracle-efficient algorithms in this setting ([HRS22; Blo+22]), as we focus on the more difficult objective of minimizing multi-group regret over a collection G, as in Equation (1). This setting will allow us to employ our (G, H)-optimization oracle in Definition 2.2; a full description of our algorithm is now in order in Section 4.2.In this section, we present Algorithm 1, our main algorithm for multi-group online learning for the σ-smooth setting. At a high level, our algorithm takes inspiration from the very general adversarymoves-first (AMF) framework for multiobjective online learning of [Lee+22] . Our algorithm can be thought of as a sequential game between two competing players: an adversarial (G, H)-player and the learner, referred to, in the context of Algorithm 1 as the H-player. On each round t, the (G, H)-player employs a (G, H)-optimization oracle, OPT α (G,H) , to play a distribution over group-hypothesis pairs that maximizes the misfortune of the H-player, based on the history up until t. Upon receiving this distribution (and the context x t from Nature), the H-player chooses ŷt randomly according to a distribution obtained by solving a simple constant-size linear program, and then incurs the loss ℓ(ŷ t , y t ). The (G, H)-player, taking this new loss into account, can now adjust his strategy to foil the H-player in the next round by putting mass on the groups on which the H-player performs poorly. Crucially, neither G nor H is ever accessed directly, although our proofs need to maintain a distribution over G × H. In order to do this, we make the crucial observation that FTPL maintains an implicit distribution over G × H and we sparsely approximate that distribution through repeatedly querying the OPT α (G,H) oracle. (For clarity, we use the tilde decoration, h and g, on hypotheses and groups obtained by the (G, H)-player using OPT α (G,H) .)Main algorithm. For any x ∈ X , define lx :EQUATIONwhere ℓ(•, •) is the loss given by the learning problem. The quantity lx is the loss that the (G, H)player is maximizing; it corresponds to the single-round regret of the learner on group g to the hypothesis h if the context on that round is x.The (G, H)-player will employ the FTPL style strategy of [Blo+22] , adapted to our setting. For each round t, this requires generating n perturbation examples as extra input to OPT α (G,H) . To generate these hallucinated perturbation examples, we independently draw z t,j ∼ B and γ t,j ∼ N (0, 1), samples j ∈ [n] from the base measure and the standard Gaussian, respectively. In this section, Y = {-1, 1} and H ⊆ {-1, 1} X , so we use the perturbations in their FTPL variant for binary-valued action spaces (outlined in Appendix B.6),EQUATIONRemark. We focus on the setting where Y = {-1, 1} for ease of exposition, but settings in which Y is a general finite set can be handled with easy modifications. See Appendix C for details. (G, H)-player: Draw n hallucinated examples as in Equation (4) to construct π bin t,n .(G, H)-player: Using the entire history {(ŷ s , y s )} t-1 s=1 so far, call OPT α (G,H) to obtain (g(i) t , h(i) t ) ∈ G × H satisfying: t-1 s=1 lxs ((g (i)t , h(i) t ), (ŷ s , y s )) + π bin t,n (g(i) t , h(i) t , η) ≥ sup (g * ,h * )∈G×H t-1 s=1 lxs ((g * , h * ), (ŷ s , y s )) + π bin t,n (g * , h * , η) -α (5) 6:end for 7:H-player: Call OPT H twice on the singleton datasets {(x t , 1)} and {(x t , -1)}, with the 0-1 loss, obtaining: p lxt ((gh ′ 1 ∈ arg min h * ∈H 1 {h * (x t ) ̸ = 1} , h ′ -1 ∈ arg min h * ∈H 1 {h * (x t ) ̸ = -1} .(i) t , h(i) t ), (h ′ 1 (x t ), y)) + (1 -p) lxt ((g (i) t , h(i) t ), (h ′ -1 (x t ), y)) ≤ λ ∀y ∈ {-1, 1} 0 ≤ p ≤ 1. 9: Sample b ∼ Ber(p) where b ∈ {-1, 1}, let h t = h ′ b .10:Learner commits to the action ŷt = h t (x t ); Nature reveals y t .11:Learner incurs the loss ℓ(ŷ t , y t ). 12: end for algorithm with access to OPT α (G,H) . Examples of such variants are given in Section 5, and the general framework for such modifications is given in Appendix B.Remark. With appropriate modifications, one can instantiate the (G, H)-player with the FTPL style strategy of [Hag+22] instead, inheriting the σ -1/4 dependence summarized in Table 1 . Our focus in this paper is not on the dependence on σ, however, so our main exposition centers around the similar algorithmic techniques of [Blo+22] .It is clear that G and H are never accessed except through OPT α (G,H) and OPT H . We make M oracle calls to OPT α (G,H) and two oracle calls to OPT H at each round. Theorem 4.1. Let Y = {-1, 1} be a binary action space, H ⊆ {-1, 1} X be a binary-valued hypothesis class, G ⊆ 2 X be a (possibly infinite) collection of groups, and ℓ : {-1, 1} × {-1, 1} → [0, 1] be a bounded loss function. Let the VC dimensions of H and G both be bounded by d. Let α ≥ 0 be the approximation error of the oracle OPT α (G,H) . If we are in the σ-smooth online learning setting, then, for M = poly(T ), n = poly(T /σ), and η = poly(T /σ), Algorithm 1 achieves, for each g ∈ G:E[Reg T (H, g)] ≤ O dT log T σ + αT ,where the expectation is over all the randomness of the (G, H)-player's perturbations and the H-player's Bernoulli choices. (See Corollary B.7.1 for precise settings of M , n, and η.)Technical details. We solve three main difficulties toward ensuring that our algorithm achieves diminishing multi-group regret while maintaining computational efficiency for large or infinite G, which we outline here. The full proof of Theorem 4.1 is in Appendix B.First, although the general framework of casting online learning problems with multiple objectives as two-player games is not new ([Lee+22; HJZ24; HPY23]), previous works have employed a multiplicative weights algorithm to hedge against the multiple objectives, requiring explicit enumeration. Departing from previous literature, however, our (G, H)-player uses a follow-the-perturbed leader (FTPL) style algorithm (see, e.g., [KV05] ) with OPT (G,H) . The particular follow-the-perturbed leader variant of [Blo+22] constructs "perturbations" via a set of fake examples drawn from the the base measure B on X , and, is thus suitable for our oracle and problem setting.Second, a key property needed by the proof of Algorithm 1 is that the H-player must receive a distribution over G × H to reduce the complex multi-objective criterion of performing well against all (g, h) ∈ G × H to a scalar quantity. Previous work directly supplied this distribution through the multiplicative weights algorithm. However, this would involve explicitly enumerating G and H. On the other hand, using an FTPL algorithm as is would only output a single action from G × H, which is insufficient. To remedy this, we make the crucial observation that FTPL algorithms implicitly maintain a distribution over G × H through the randomness of their perturbations, and, thus, we construct the empirical approximation of this distribution through repeatedly calling OPT (G,H) .Standard uniform convergence arguments are used to bound the number of oracle calls needed. An argument employing the minimax theorem shows that the final regret guarantee of the entire algorithm essentially inherits the regret of the FTPL algorithm, plus sublinear error terms.Finally, the H-player chooses a distribution over Y by by solving an exceedingly simple linear program (LP) with two optimization variables, p and λ. The value p ∈ [0, 1] corresponds to the parameter of a Bernoulli distribution from which we sample to choose ŷt . This choice of action corresponds exactly to choosing the minimax optimal strategy against the worst-case y that Nature could select. We employ similar techniques as [Lee+22] , analyzing the value of this min-max game as if Nature (the max in the min-max) had gone first instead. The two calls to OPT H are used just to find the actions achievable by H on x t . (Note that it is possible that h ′ y ′ (x t ) ̸ = y ′ for some y ′ ∈ Y, in which case the Learner will always play -y ′ , regardless of the value of p.)Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [NA] Justification: This is a theory paper, where the main contributions are towards novel algorithmic design principles for a learning-theoretic model. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
group oracle-efficiency in other settings: 
 In the previous section, we presented an algorithm that achieves o(T ) expected regret for all g ∈ G, satisfying our main desideratum from Section 2.2. However, in some cases, we may want something more. Suppose that some groups are rarer than others; in this case, a natural extension would be to ensure a stronger "adaptive" regret bound that instead scales with T g := T t=1 g(x t ), the number of times group g appeared in the T rounds. We note that the algorithm of [BL20] achieves such a multi-group regret guarantee (for finite H and G), but their algorithm is not oracle-efficient. So a question that remains is whether such guarantees can be achieved in an oracle-efficient manner.In this section, we are back in the general fully adversarial multi-group online learning setting of Section 2.2 (without i.i.d. or smoothness assumptions). We discuss how to modify Algorithm 1 via the Generalized Follow-the Perturbed-Leader (GFTPL) framework of [Dud+20; Wan+22] to obtain regret guarantees on group g where the dependence on T is replaced (at least in part) with T g . Due to space limitations, we give a sketch here; the full details are in Appendix C.We first make a simple observation that motivates our use of more advanced oracle-efficient online learning techniques. Recall the g-specific per-round regret to h of playing h(x t ) at round t ∈ [T ]:lxt ((g, h), (h(x t ), y)) = g(x t ) ℓ(h(x t ), y) -ℓ( h(x t ), y) .The job of the (G, H)-player is to run a no-regret algorithm to maximize this quantity in aggregate, as described in Section 4.2 and detailed in Appendix B.5. The online learning literature for small-loss regret focuses on developing algorithms that have regret depending on cumulative loss in hindsight instead of the number of rounds T [HP05; CL06; GSV14]; this has the advantage of giving a tighter regret bound when losses are small in magnitude. It is immediate that lxt ((g, h), (h(x t ), y)) = 0 whenever g(x t ) = 0, so a small-loss regret would immediately give a o(T g ) guarantee.We focus on the case where G and H are finite, and G × H is the set of experts the (G, H)-player has access to. Most small-loss regret algorithms would require prohibitive enumeration of G × H [HP05; CL06; GSV14; LS15], but the GFTPL with small-loss bound algorithm of [Wan+22] has the property that it is oracle-efficient and enjoys small-loss regret. This algorithm follows the GFTPL design template of [Dud+20] , which, similar to the classic FTPL algorithm of [KV05] , generates a noise vector to perturb each each decision of expert. However, whereas the classic FTPL algorithm generates |G| × |H| independent random noise variables, GFTPL only generates N ≪ |G| × |H| independent random variables and uses a perturbation matrix (PM) Γ ∈ [-1, 1] |G||H|×N to translate the noise vector back to |G| × |H| dependent perturbations.The main challenge in instantiating a GFTPL algorithm is to construct a suitable Γ for the problem at hand. [Wan+22] provide two sufficient conditions for Γ that, respectively, imbue the GFTPL algorithm with oracle-efficiency and small-loss regret: implementability and approximability. In our setting, implementability requires that every column of Γ correspond to a dataset of "fake examples" suitable to OPT α (G,H) . Approximability with parameter γ > 0 guarantees the stability property that the ratio P[(g t , ht ) = (g, h)]/P[(g t+1 , ht+1 ) = (g, h)] ≤ exp(γη t ) for all (g, h) ∈ G × H, where η t > 0 is the per-round learning rate of GFTPL. If such a Γ exists, then instantiating the (G, H)-player in Algorithm 1 with GFTPL (instead of the algorithm of [Blo+22] ) gives us the stronger o(T g ) regret guarantee. Full definitions and the proof, with the precise setting of M , can be found in Appendix C and Proposition C.3.1.Theorem 5.1. Assume H, G are finite and there exists a γ-approximable and implementable perturbation matrix Γ ∈ [-1, 1] |G||H|×N . Let α ≥ 0 be the approximation parameter of OPT α (G,H) . Let the no-regret algorithm for the (G, H)-player in Algorithm 1 be the GFTPL algorithm of [Wan+22] instantiated with Γ, with parameter M = poly(T ). Then, for each g ∈ G:E[Reg T (H, g)] ≤ O T g max γ, log |H||G|, N log |H||G| + αTWe give a particular setting in which one can easily construct an approximable and implementable Γ.Transductive Setting. In the transductive setting of [SKS16; Dud+20], Nature reveals a set X ⊂ X to the Learner at the beginning of the learning process; then at each round t ∈ [T ], Nature can only choose x t from X. Let N := |X| denote the number of different contexts that Nature chooses from.For this setting, we can explicitly construct Γ to get the following result.Corollary 5.1.1 (Transductive setting). In the transductive setting, there exists a perturbation matrix Γ ∈ [-1, 1] |G||H|×4N such that Algorithm 1 with GFTPL parameterized with M = poly(T ) and OPT α (G,H) with error parameter α ≥ 0 satisfies:E[Reg T (H, g)] ≤ O T g max log |H||G|, N log |H||G| + αT for all g ∈ G.Suppose that N ≤ T (which is the case in the transductive learning setting from [KK05] ). Then the regret bound (ignoring the dependence on log(|H||G|)) on group g is O( T g T 1/4 ), which is asymptotically smaller than√ T whenever T g = o( √ T ). If N is fixed independent of T , then the regret bound is O( T g ).Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: This is a theory paper (see above).Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/ guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion and future work: 
 In this paper, we design algorithms for online multi-group learning that are oracle-efficient and achieve diminishing o(T ) expected regret for all groups g ∈ G simultaneously, even when G is too large to explicitly enumerate. The most interesting future directions that we leave open in this work include designing oracle-efficient algorithms that achieve o(T g ) group-specific regret for infinite H and G and in more general settings.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: This is a theory paper (see above). Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] Justification: This is a theory paper (see above). Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Our paper does not include any trained models or data. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Our paper does not use any licensed code, data, or models. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: Our paper does not use any new assets (no experiments). Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
 
 Appendix: The goal is to prove that ONLINE LISTUPDATE satisfies, for all g ∈ G,E[Reg T (H, g)] ≤ O (d log T ) 1/3 T 2/3 + dT log T . Fix any g ∈ G. For each h ∈ H, define Reg T (h, g) := T t=1 g(x t )(ℓ(ŷ t , y t ) -ℓ(h(x t ), y t )).By linearity of expectation, Theorem 3.1, and an elementary integral bound, ThenE[Reg T (h, g)] = T t=1 E[g(x t )ℓ(ŷ t , y t ) -E[g(x t )ℓ(h(x t ), y t )] ≤ 1 + T t=2 P (g) • (E[ℓ(f t (x t ), y t ) | x t ∈ g] -E[g(x t )ℓ(h(x t ), y t ) | x t ∈ g]) ≤ 1 + T t=2 (1 -δ) • O d log(t -1) + log(1/δ) t -1 1/3 + δ = 1 + O (d log T + log(1/δ)) 1/3 T 2/3 + δT . Plug-in δ = 1/T to obtain E[Reg T (h, g)] ≤ O (d log T ) 1/3 T 2/E[Reg T (H, g)] = max h∈H E[Reg T (h, g)] + E T t=1 g(x t )(ℓ(h g (x t , y t ) -ℓ( ĥg (x t ), y t )) .Since H has VC dimension at most d, a standard uniform convergence argument impliesE max h∈H T E (x,y)∼µ [g(x)ℓ(h(x), y)] - T t=1 g(x t )ℓ(h(x t ), y t ) ≤ O dT log T .Using the definitions of h g and ĥg , we obtainE T t=1 g(x t )(ℓ(h g (x t , y t ) -ℓ( ĥg (x t ), y t )) ≤ O dT log T .Therefore, we conclude thatE[Reg T (H, g)] ≤ O (d log T ) 1/3 T 2/3 + dT log T .This finishes the proof of Theorem 3.2.In this section, we prove the multi-group regret guarantee of our main algorithm, Algorithm 1. To restate the theorem, we aim to show, for all g ∈ G,E[Reg T (H, g)] ≤ O dT log T σ + αT .More explicitly, we aim to show that:T t=1 E[g(x t ) (ℓ(h t (x t ), y t ) -ℓ(h * (x t ), y t ))] ≤ O dT log T σ + αT ,where h * ∈ min h∈H T t=1 g(x t )ℓ(h(x t ), y t ). We follow a generalization of the online minimax multiobjective optimization framework of [Lee+22] , with techniques inspired by [HPY23] .We first restate their "adversary-moves-first" AMF algorithm of [Lee+22] and its main regret guarantee for convenience, as we will need to adapt and generalize it to our setting. Let A t denote a general action space of the learner, and let Z t denote the general action space of the adversary at round t ∈ [T ]. In full generality, A t and Z t are allowed to change with the rounds t ∈ [T ]. We differentiate this from the action space Y of the main body. For each round t = 1, . . . , T , consider the following setting, which we refer to as the multiobjective online optimization problem:1. The adversary selects a continuous, d-dimensional loss function r t :A t × Z t → [-1, 1] d . Each component r j t : A t × Z t → [-1, 1] is convex in A t and concave in Z t . 2.The learner selects an action a t ∈ A t . 3. Nature observes the learner's action a t and responds with z t ∈ Z t . 4. The learner incurs the d-dimensional loss r t (a t , z t ).In this setting, the learner's goal is to minimize the value of the maximum dimension of the accumulated loss vector after T rounds:max j∈[d] T t=1 r j t (a t , z t ).To benchmark the learner's performance, we consider the following quantity, which we refer to as the adversary-moves-first (AMF) value at round t. Definition B.1 (Adversary-Moves-First (AMF) Value at Round t, [Lee+22] ). The adversary-movesfirst (AMF) value at round t is the value:EQUATION)We conceive of the value v A t in (6) as the aspirational smallest value of the maximium coordinate of r t the learner could guarantee if the adversary had to reveal z t first and the learner could best respond with a t . Per how the multiobjective online optimization problem is set up, however, the opposite is true -the learner must commit to an action a t ∈ A t first, and then the adversary is allowed to play z t ∈ Z t in response to maximize the learner's misfortune. Regardless, we can define a notion of regret with respect to this particular benchmark. Definition B.2 (Adversary-Moves-First (AMF) Regret). Over T rounds of the above multiobjective online optimization problem, the adversary-moves-first regret of the learner is:AMFReg T := max j∈[d] T t=1 r j t (a t , z t ) -v A t .This notion measures the cumulative regret the learner has for not playing the action a t ∈ A t achieving the aspirational value v A t at round t over all d coordinates of the loss vector.Algorithm 2 AMF Algorithm of [Lee+22] 1: for t = 1, 2, 3, . . . , T do 2:Receive adversarially chosen action spaces A t and Z t and the d-dimensional loss functionr t : A t × Z t → [-1, 1] d . 3: Let q j t := exp η t-1 s=1 r j s (a s , z s ) i∈[d] exp η t-1 s=1 r i s (a s , z s ) for j ∈ [d].For t = 1, let q j t = 1/d for all j ∈ [d].Solve the min-max optimization problem:EQUATIONCommit to the action a t ∈ A t , observe Nature's choice z t ∈ Z t , and incur loss r t (a t , z t ). 6: end for A natural question, then, is to wonder if such a regret can be made to diminish sublinearly. That is, does there exist an algorithm such that AMFReg T ≤ o(T )? [Lee+22] answer this in the affirmative, presenting Algorithm 2.It is not immediately clear at first glance how Algorithm 2 translates to our multi-group online learning setting. In the next section, we will show a reduction from our setting to the this AMF framework. We will specialize Algorithm 2 to our setting and prove a "meta-theorem" similar to the original guarantee of Algorithm 2 and proceed to control the regret via that meta-theorem in subsequent sections.Recall that, in this paper, we actually care about the online multi-group learning setting described in Section 2.2. We restate the objective here for convenience.In multi-group online learning, the learner has access to a hypothesis class H taking contexts from X and outputting actions in Y, a common action space for the learner and Nature. There is a common loss function for the problem, ℓ(•, •) : Y × Y → [0, 1]. To allay confusion, we refer to the adversary in the multi-group online setting of Section 2.2 as "Nature" and the adversary in the online multiobjective optimization problem of Section B.1 as "the adversary." The learners in both settings correspond to one another, so we just use "the learner." For clarity of exposition, we let Y = {-1, 1} be a binary action space for the remainder of Appendix B. The generalization to the case where Y takes K discrete values is sketched in Appendix C.We consider the regret of the learner on subsequences of rounds (t ∈ [T ] : x t ∈ g) defined by the groups g ∈ G and the sequence of contexts x 1 , . . . , x T . Specifically, the (multi-group) regret of the learner on group g isEQUATIONCrucially, the best hypothesis for one group may differ from that of another group. The learner seeks to achieve achieve sublinear expected regret, on all groups g ∈ G simultaneously.We now show a reduction from the multi-group online learning setting to the general multiobjective online optimization problem of the previous Section B.1. An important observation is that, when Y = {-1, 1}, varying h t ∈ H only affects the regret at round t ∈ [T ] insofar as its behavior on x t . That is, for a fixed x t ∈ X and y ∈ Y, ℓ(h t (x t ), y) ∈ {ℓ(-1, y), ℓ(1, y)}. Note that it is possible for the set {h(x t ) : h ∈ H} ⊆ Y to be a singleton set, in which case the learner will always take this unique action.• Let A t , the learner's action space for round t ∈ [T ] in Section B.1, be the simplex ∆(Y).• Let Z t , the adversary's action space in Section B.1, be Z t = [0, 1] for all t ∈ [T ], which will correspond to the parameter of a Bernoulli distribution over the binary-valued action space Y of Nature in the multi-group online learning problem. • Let r t : A t × Z t → [-1, 1] d , the adversarially chosen loss function, be G × H-dimensional, with each coordinate corresponding to a pair (g, h) ∈ G × H. Consider any p, γ ∈ [0, 1], each determining a Bernoulli distribution over Y = {-1, 1}. As in Section 4.2, for any x ∈ X : lx ((g, h), (y ′ , y)) := g(x) ℓ(y ′ , y) -ℓ( h(x), y) .Then, define: rEQUATIONAbove, the loss ℓ(•, •) is the fixed loss of the multi-group online learning problem, and x t ∈ X is the context chosen by Nature at round t, which indexes r t .It may now be slightly clearer how Algorithm 1 maps to Algorithm 2, but we provide a high-level overview here to prepare the reader for the subsequent sections.• The distribution q t ∈ ∆[d] in Line 3 of Algorithm 2 corresponds to the implicit distribution formed by querying OPT α (G,H) M times to generate {(g i , hi )} M i=1 , i.e. the (G, H)-player. • Solving the min-max optimization problem in Line 4, Equation (7) of Algorithm 2 corresponds to the two calls to the simple optimization problem solved by the H-player and solving the simple one-dimensional linear program in Line 8 of Algorithm 1.We make these correspondences formal in the subsequent sections. To organize this, we first formally show the correspondence between the (G, H)-player and the construction of q t , and the H-player and Equation (7) in Algorithm 2.The computational primitive our algorithm assumes access to is a (G, H)-optimization oracle, defined in Definition 2.2, and requoted here for ease of reference. Definition B.3 ((G, H)-optimization oracle). Fix an error parameter α ≥ 0. For a collection of groups G ∈ 2 X , a collection of hypotheses H ⊆ Y X , and a sequence of m loss functionsℓ i : ({0, 1} × Y) × (Y × Y) → [-1, 1], an α-approximate (G, H)-optimization oracle OPT α (G,H) is an α-approximation optimization oracle (Definition 2.1) that outputs a pair (g, h) ∈ G × H satisfying:EQUATIONA common assumption in the literature on oracle-efficient online learning is positing the existence of some reasonable optimization oracle, typically commensurate to the ability to solve ERM. Although it is well-known that ERM is computationally hard in the worst-case, a bedrock of modern machine learning is the assumption that ERM is at least heuristically and approximately solvable. Although, for the purposes of our work, we assume access to this oracle as a black-box, it is natural to wonder if such an oracle can be instantiated. [GKR22] gives two such instantiations which we quote here for completeness.We consider the specific instantiation of the (G, H)-oracle in Algorithm 1 for a specific round t ∈ [T ], which aims to solve the following optimization problem for some (g t , ht ) ∈ G × H:EQUATIONwhereOPT := sup g * ,h * ∈(G,H) t-1 s=1 g * (x s ) (ℓ(ŷ s , y s ) -ℓ(h * t (x s ), y s )).In both instantiations of the oracle in [GKR22] , the oracle aims to find a (g, h) ∈ (G, H) competitive to some reference model, f : X → {0, 1}. For simplicity, as in the main body, we assume that Y = {0, 1}, and the "reference model" we compete with is given by the Learner's history of actions up to round t: (x 1 , ŷ1 ), . . . , (x t-1 , ŷt-1 ). That is, we compare with the function f : X → {0, 1} that maps f (x s ) = ŷs for all s = 1, . . . , t -1.Reduction to ternary classification. The first instantiation of a (G, H) oracle in [GKR22] reduces the optimization oracle to the existence of a solver for a weighted ternary classification problem. The exposition here is quoted directly from [GKR22] .Start with a class K of ternary valued functions p : X → {0, 1, ?}. For each p ∈ K, define the p-derived group and p-derived hypothesis as:g p (x) = 1 if p(x) ∈ {0, 1} 0 if p(x) =? h p (x) = p(x) if p(x) ∈ {0, 1} 0 if p(x) =?This class K induces a set of pairs (g p , h p ) and a product class (G, H) K := {(g p , h p ) : p ∈ K}. We may now define a cost-sensitive classification problem over K as follows, given an existing model f : X → {0, 1}, with the following costs:c f ((x, y), z) :=        0 if z =? 1 if f (x) = y ̸ = z -1 if z = y ̸ = f (x) 0 otherwise .For any distribution µ over X × {0, 1}, the associated cost-sensitive classification problem for costs c f ((x, y), z) defined above is:EQUATIONMany efficient algorithms that heuristically solve such optimization problems exist.The main theorem from [GKR22] , restated here, is the following: Theorem B.1. Fix any arbitrary distribution µ over X × {0, 1}. Let K be a class of ternary-valued functions p : X → {0, 1, ?} and let f : X → {0, 1} be any binary-valued model. Let p * be the solution to the cost-sensitive classification problem in Equation (12). Then,(g * p , h * p ) ∈ arg max (g,h)∈(G,H) K E (x,y)∼µ [g(x) (ℓ(f (x), y) -ℓ(h(x), y))] .When µ is the empirical distribution over x 1 , . . . , x t-1 , the solution (g * p , h * p ) forms a solution to the optimization problem in Equation (11) when (G, H) K = G × H.We refer the reader to Section 4.2 in [GKR22] for a proof.Reduction to alternating maximization. Another instantiation of the (G, H)-oracle in [GKR22] is an alternating maximization approach. The reduction to ternary classification quoted above relies on an oracle for the class K and supplies guarantees for the derived class (G, H) K . However, if we wish to begin with G × H, we can take an "EM-style" alternating maximization approach that only requires ERM oracles for G and H separately. This approach only guarantees a saddle point local optimum.The main idea is that, by holding g fixed and solving for h * , and vice versa, the following optimization problems are no harder than ERM over G and H individually:EQUATIONIn Equation (13), h is fixed and we solve for g * ; in Equation ( 14), g is fixed, and we solve for h * . With appropriate modifications to the distribution µ we can construct ERM problems for g * and h * comensurate to solving Equations ( 13) and ( 14). We refer the reader to Lemmas 21 and 22 in [GKR22] for the proofs.This allows us to state an alternating maximization algorithm for finding a saddle point (g, h) ∈ G ×H that gives a local optimum to Equation (11) in Algorithm 3. The corresponding theorem, restated from [GKR22] is:Theorem B.2. Let ϵ > 0. Fix any empirical distribution over (x 1 , y 1 ), . . . , (x m , y m ), let f : X → {0, 1} be an arbitrary model, and let G and H be arbitrary group and hypothesis classes. After solving at most 2/ϵ ERM problems over each of G and H (in Equations (13) and (14), respectively), Algorithm 3 returns a pair (g * , h * ) with the properties that:1. For every h ∈ H,m i=1 g * (x i ) (ℓ(f (x i ), y i ) -ℓ(h(x i ), y i )) ≤ m i=1 g * (x i ) (ℓ(f (x i ), y i ) -ℓ(h * (x i ), y i )) + ϵ. 2. For every g ∈ G, m i=1 g(x i ) (ℓ(f (x i ), y i ) -ℓ(h * (x i ), y i )) ≤ m i=1 g * (x i ) (ℓ(f (x i ), y i ) -ℓ(h * (x i ), y i )) + ϵ. Algorithm 3 Alternating Maximization for G × H Oracle Input: Dataset {(x i , y i )} m i=1 , a model f : X → {0, 1}, error parameter ϵ. 1: Initialize (g * , h * ) ∈ G × H arbitrarily. 2: Let VAL := m i=1 g * (x i ) (ℓ(f (x i ), y i )) -ℓ(h * (x i ), y i ))3: Use ERM oracle for Equations ( 13) and ( 14) to solve for:g * ∈ arg max g∈G m i=1 g(x) (ℓ(f (x), y) -ℓ(h * (x), y)) h * ∈ arg max h∈H m i=1 g * (x) (ℓ(f (x), y) -ℓ(h(x), y)) 4: while m i=1 g * (x) (ℓ(f (x), y) -ℓ(h * (x), y)) ≥ VAL + ϵ do 5: Let VAL := m i=1 g * (x i ) (ℓ(f (x i ), y i )) -ℓ(h * (x i ), y i )) 6:Use ERM oracle for Equations ( 13) and ( 14) to solve for:g * ∈ arg max g∈G m i=1 g(x) (ℓ(f (x), y) -ℓ(h * (x), y)) h * ∈ arg max h∈H m i=1 g * (x) (ℓ(f (x), y) -ℓ(h(x), y)) 7: end while 8: Return (g * , h * ) ∈ G × H.We believe that it is an interesting and worthwhile open question to develop more specific instantiations of this (G, H)-oracle for more specific problem settings that are computationally efficient and have provable optimization guarantees.We formally define how the (G, H)-player corresponds to the weights q t ∈ ∆[d] in Algorithm 2. The crucial observation here is that the perturbations of the FTPL algorithm of [Blo+22] used in our setting form an implicit distribution over G × H that can be approximated by calling the OPT α (G,H) oracle M times.In the proceeding sections, we denote ∆(G × H) as the (possibly infinite-dimensional) space of measures over the functions G × H. However, we will always only access sparse distributions on this space, with a finite number of (g, h) pairs in G × H obtaining nonzero mass. The following definition should make this clear.For any round t ∈ [T ], let {(g i , hi )} M i=1 be the M samples drawn from querying OPT α (G,H) in Algorithm 1. Let the empirical distribution qt ∈ ∆(G × H) be the distribution of the (G, H)-player at round t.It is easy to see that qt is a valid distribution over (G, H), with measure over A ⊆ G × H, defined by:P M (A) := 1 M M i=1 δ (gi, hi) (A),where δ (gi, hi) is the Dirac measure of (g i , hi ) falling into the set A. The stochasticity of (g i , hi ) is over the random perturbations described in Section 4.2, Equation (4). Equipped with this definition, we can take empirical expectations over qt ∈ ∆(G × H) in the usual way. Observe that, in Algorithm 2, Equation (7), the optimization problem at round t, is equivalent to:a t ∈ arg min a∈A max z∈Z E j∼qt r j t (a, z) .Because the d objectives in our reduction (Section B.2) correspond to each group-hypothesis pair (g, h) ∈ G × H, A t corresponds to ∆(Y), and Z t always corresponds to [0, 1], we can equivalently consider the min-max optimization problem at round t ∈ [T ]:EQUATIONwhere r (g, h) t is defined in Equation 9. The next lemma relates the optimization procedure of the H-player in Algorithm 1 to the min-max optimization procedure of Equation (7) in Algorithm 2. p i = 1 p ⊤ Le i ≤ λ ∀i ∈ [2] p i ≥ 0 ∀i ∈ [2]where the payoff matrix L ∈ [-1, 1] 2×2 has the coordinates (y ′ , y):L(y ′ ,y) := 1 M M i=1 lxt ((g (i) t , h(i) t ), (y ′ , y)),and e i is the ith coordinate vector of R 2 . Let ∆(Y) denote the space of probability distributions over Y. Let p = (p, 1 -p) and z = (γ, 1 -γ), and, as shorthand, denote p(-1) = 1 -p, p(1) = p, z(-1) = 1 -γ, and z(1) = γ.By the equivalence of linear programs (LPs) to zero-sum min-max games (see, e.g., [BT97; Haz22]), obtaining the optimal p for this LP is the equivalent to solving:min p∈∆(Y) max z∈∆(Y) p ⊤ Lz = min p∈∆(Y) max z∈∆(Y) 1 M y∈Y y ′ ∈Y M i=1 p(y ′ )z(y) lxt ((g (i) t , h(i) t ), (y ′ , y)) = min p∈∆(Y) max z∈∆(Y) y∈Y y ′ ∈Y p(y ′ )z(y)E (g, h)∼qt lxt ((g, h), (y ′ , y)) = min p∈∆(Y) max z∈∆(Y) E y ′ ∼p E y∼Ber(γ) E (g, h)∼qt lxt ((g, h), (y ′ , y) = min p∈∆(Y) max γ∈[0,1] E y ′ ∼Ber(p) E y∼Ber(γ) E (g, h)∼qt lxt ((g, h), (y ′ , y) = min p∈∆(Y) max γ∈[0,1] E (g, h)∼qt r (g, h) t (p, γ)Above, the first equality just comes from definition of L, the second equality is from the Definition B.4 of the empirical distribution qt , the third and fourth equalities are from the definition of p and z in the previous paragraph. The final equality is just from interchanging the order of expectation and the definition of r (g, h) t (p, γ) in Equation (9). By this chain of inequalities, we see that obtaining the optimal p for the original LP corresponds exactly to the choice of p t in Equation (15). Lemma B.3 tells us that the strategy of the H-player (i.e., Lines 8 and 9 in Algorithm 1) to obtain h t is exactly the same as obtaining the minimizing p t in Equation (15). From the exposition above, this corresponds to the min-max optimization problem in Equation ( 7) when q t is qt , the distribution over G × H. We now proceed to prove a more general "meta-theorem" from which the regret guarantee of Algorithm 1 will follow once we plug in a specific FTPL algorithm for the (G, H)-player.Algorithm 4 Meta-algorithm for Online Multi-group Learning (Y = {-1, 1}) Input: M ∈ N, the number of samples to take from q t at each step.1: for t = 1, 2, 3, . . . , T do 2:Receive a context x t from Nature.For any y ′ , y ∈ Y, construct the loss: lxt ((g, h), (y ′ , y)) := g(x t ) ℓ(y ′ , y) -ℓ( h(x t ), y) .(G, H)-player: With access to the entire history of the past t -1 rounds and x t , with access to OPT α (G,H) , run a no-regret algorithm over the benchmark class G × H to output a distribution q t ∈ ∆(G × H).Construct an empirical approximation qt of q t by sampling from q t M times, obtaining a collection of pairs {(h(i) t , g(i) t )} M i=1 from G × H. 6:H-player: Call OPT H twice on the singleton datasets {(x t , -1)} and {(x t , 1)} with the 0-1 loss, obtaining: p lxt ((g Learner commits to the action ŷt = h t (x t ); Nature reveals y t .h ′ 1 ∈ arg min h * ∈H 1 {h * (x t ) ̸ = 1} , h ′ -1 ∈ arg min h * ∈H 1 {h * (x t ) ̸ = -1} .(i) t , h(i) t ), (h ′ 1 (x t ), y)) + (1 -p) lxt ((g (i) t , h(i) t ), (h ′ -1 (x t ), y)) ≤ λ ∀y ∈ {-1, 1} 0 ≤ p ≤ 1.10:Learner incurs the loss ℓ(ŷ t , y t ).The (G, H)-player draws (g, h) ∼ qt and incurs the loss lxt ((g, h), (ŷ t , y t )). 12: end for Then, with expectation over any randomness of the (G, H)-player and Nature, Algorithm 1 obtains the multi-group regret guarantee of:EQUATIONfor all g ∈ G, whereEQUATIONand ϵ t (M ) is the error incurred from estimating q t with qt with M samples at step t ∈ [T ].Proof. From the perspective of the (G, H)-player, who is running a regret maximization algorithm, the following game is being played. For t = 1, 2, 3, . . . , T :• Receive a context x t ∈ X from Nature, possibly adversarially and depending on the past t -1 rounds. • Play a pair ( ht , gt ) ∈ H × G, possibly randomly and dependent on the last t -1 rounds, where pairs are functions (h, g) : X → Y × {0, 1}.• Commit to the action ỹt := ( ht (x t ), gt (x t )) ∈ Y × {0, 1}.• An adversary (the H-player's prediction and Nature) reveals (ŷ t , y t ) ∈ Y × Y, and we incur the loss: l((g, h), (ŷ t , y t )) := g(x t ) ℓ(ŷ t , y t ) -ℓ( ht (x t ), y t ) .Here, ŷt = h t (x t ), which is a random variable depending on sampling from p t , the Bernoulli distribution of the H-player at round t.Note that the (G, H)-player is attempting to maximize this loss.Let h 1 , . . . , h T be the sequence of hypotheses chosen by the H-player, and let y 1 , . . . , y T be the sequence of adversarially chosen outcomes. Then, by the regret guarantee of the (G, H)-player's no-regret algorithm algorithm, for any (h * , g * ) ∈ H × G:T t=1 E l((g * , h * ), (h t (x t ), y t )) - T t=1 E (gt, ht)∼qt l((g t , ht ), (h t (x t ), y t )) ≤ R(T ),where the expectation is over the distributions q t over ∆(H × G) that the (G, H)-player commits to at each round and the random choices of Nature and the H-player's random choice of ŷt at each round.To ease notation, we keep the subscript in the expectation over h t hidden, noting that h t (x t ) ∼ p t is a random variable throughout. For instance, in the case of Theorem 4.1, this is a random process determined by the (G, H)-player sampling n perturbation terms and calling the (G, H)-oracle to obtain the random variable (g t , ht ). Instantiating the regret bound for all (h * , g * ) gives us:max (h * ,g * )∈H×G T t=1 E l((g * , h * ), (h t (x t ), y t )) ≤ T t=1 E (gt, ht)∼qt l((g t , ht ), (h t (x t ), y t )) + R(T ).However, we do not have direct access to q t , the implicit distribution over G × H, but we have an approximation qt . In Algorithm 2, (g t , ht ) is drawn according to qt , the empirical distribution overEQUATIONt } M i=1 from qt . Fixing x t , y t , and h t (x t ), let ϵ t (M ) be the error we incur from replacing the true distribution q t by the empirical distribution qt , which we can handle through uniform convergence on the samples {( h(i) (18) The inner expectations are linear in p t and γ, and taking the outer expectation over qt maintains linearity. Therefore, this is a convex and concave min-max optimization problem, and von Neumann's minimax theorem [NMR44] applies, allowing us to swap the order of minimization and maximization. Thereforemin pt∈∆(Y) max γ∈[0,1] E (gt, ht)∼qt E ht(xt)∼pt E y∼Ber(γ) gt (x t ) ℓ(h t (x t ), y) -ℓ( ht (x t ), y)) = max γ∈[0,1] min pt∈∆(Y) E (gt, ht)∼qt E ht(xt)∼pt E y∼Ber(γ) gt (x t ) ℓ(h t (x t ), y) -ℓ( ht (x t ), y)) ≤ max γ∈[0,1] min pt∈∆(Y) max (g, h)∈G×H E ht(xt)∼pt,y∼Ber(γ) g(x t ) ℓ(h t (x t ), y) -ℓ( h(x t ), y) = v A twhere the first equality is from the minimax theorem and the second inequality is just because averages are less than or equal to maximums. Combining all the inequalities, we obtainmax (h * ,g * )∈H×G T t=1 l((g * , h * ), (h t (x t ), y t )) ≤ T t=1 v A t + T t=1 ϵ t (M ) + R(T ),and our theorem follows from taking an expectation on both sides and substituting back the definition of l((g * , h * ), (h(x t ), y t )) := g * (x t ) (ℓ(h(x t ), y t ) -ℓ(h * (x t ), y t )) ,because each l((g * , h * ), (h(x t ), y t )) is simply the per-round regret.With Theorem B.4 in hand, it remains to make sure that the two termsT t=1 v A t and T t=1 E[ϵ t (M )] are both o(T ).Then, if we have a no-regret algorithm with o(T ) regret while only accessing G and H through the OPT α (G,H) oracle, we will have a multi-group online learning algorithm. The next two lemmas show that both terms are, indeed, o(T ).First, we bound the values v A t , which are known as the "AMF values" in the framework of [Lee+22] . Lemma B.5. For any t ∈ [T ], the AMF value of the game at round t, is nonpositive, i.e.v A t := max γ∈[0,1] min pt∈∆(H) max (h,g)∈H×G E[g(x t )(ℓ(h t (x t ), y) -ℓ(h(x t ), y))] ≤ 0,where the expectation is taken over h t ∼ p t and y ∼ Ber(γ).Proof. Fix any parameter γ ∈ [0, 1] for the max player. Then, for any (h, g) ∈ H × G,E [g(x t )(ℓ(h t (x t ), y) -ℓ(h(x t ), y))] =γE ht∼pt [g(x t )(ℓ(h t (x t ), 1) -ℓ(h(x t ), 1))] + (1 -γ)E ht∼pt [g(x t )(ℓ(h t (x t ), -1) -ℓ(h(x t ), -1))].Expanding the expectation over h t ∼ p t , this is equivalent to:g(x t ) h ′ ∈H p t h ′ (γℓ(h ′ (x t ), 1) + (1 -γ)ℓ(h ′ (x t ), 0)) -g(x t )(γℓ(h(x t ), 1) + (1 -γ)ℓ(h(x t ), 0)), so it suffices to find p t ∈ ∆(H) such that, for all (h, g) ∈ H × G, g(x t ) h ′ ∈H p t h ′ (γℓ(h ′ (x t ), 1) + (1 -γ)ℓ(h ′ (x t ), 0)) ≤ g(x t )(γℓ(h(x t ), 1) + (1 -γ)ℓ(h(x t ), 0)).The g(x t ) value is the same for both sides, so it really suffices to find the p t ∈ ∆(H) such that, for all h ∈ H,p t h ′ (γℓ(h ′ (x t ), 1) + (1 -γ)ℓ(h ′ (x t ), 0)) ≤ γℓ(h(x t ), 1) + (1 -γ)ℓ(h(x t ), 0). Because we know γ, the Bernoulli parameter for the true distribution of y | x t , we can choose p t ∈ ∆(H) to put all its mass on the h * ∈ H that minimizes this risk, i.e.h * ∈ arg min h∈H E y [ℓ(h(x t ), y) | x t ].This is, by definition, exactly the h * such that, for any h ∈ H, γℓ(h * (x t ), 1) + (1 -γ)ℓ(h * (x t ), -1) ≤ γℓ(h(x t ), 1) + (1 -γ)ℓ(h(x t ), -1).Therefore, we have that:v A t = max γ∈[0,1] min pt∈∆(H) max (h,g)∈H×G E h ′ ∼pt,y∼Ber(γ) [g(x t )(ℓ(h ′ (x t ), y) -ℓ(h(x t ), y))] ≤ max γ∈[0,1],(h,g)∈H×G E y∼Ber(γ) [g(x t )(ℓ(h * (x t ), y) -ℓ(h(x t ), y))] ≤ 0.The final inequality follows from our argument above.Next, we bound the expected approximation error we incur from replacing q t with the empirical distribution qt obtained from the M samples {(g(i) t , h(i) t } M i=1, which we denoted as ϵ t (M ). This comes from a standard uniform convergence argument.Lemma B.6. Let t ∈ [T ] and x t ∈ X be fixed, and consider the function lxt ((g, h), (y ′ , y)):= g(x t )(ℓ(y ′ , y) -ℓ(h(x t ), y)). Let |Y| = k < ∞. If M ≥ T 1+δ , where δ = Ω( log(log T +log k) log T), then over the randomness of drawing M samples {(g(i) t , h(i) t } M i=1to construct the empirical distribution qt described in Definition B.4, for all y ′ , y ∈ Y, let ϵ t (M ) be defined as the supremumϵ t (M ) := sup (y ′ ,y)∈Y×Y E (g, h)∼qt [ lxt ((g, h), (y ′ , y))] -E (g,h)∼qt [ lxt ((g, h), (y ′ , y))] ,and, over all T rounds,E T i=1 ϵ t (M ) ≤ 2 √ T .Proof. Fix any round t ∈ [T ]. We use a standard uniform convergence argument to ensure that the empirical distribution qt and the true distribution q t are close for the function lxt ((g, h), (y ′ , y)) for all y ′ , y ∈ Y. We assume that Y is finite, and denote k := |Y|.Let {(g(i)t , h(i) t )} M i=1 denote the M random samples from G × H. We note that the expectation over qt is the same as:E (g, h)∼qt l((g, h), (y ′ , y)) = 1 M M i=1 l (g (i) t , h(i) t ), (y ′ , y) .Consider the empirical processsup (y ′ ,y)∈Y 2 1 M M i=1 l((g (i) t , h(i) t ), (y ′ , y)) -E (g,h)∼qt l((g, h), (y ′ , y))Zi(y ′ ,y).For notational simplicity, let us refer to this empirical process as:sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) = ϵ t (M ). Because ℓ(•, •) ∈ [0, 1], we know l ∈ [-1, 1]. Moreover, |Y 2 | = k 2 .We can now use Hoeffding's inequality and a union bound to obtain:P sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) ≥ ε ≤ k 2 exp(-2M ε 2 ) ≤ k 2 exp(-2T 1+δ ε 2 ).By the elementary integral inequality E[X] ≤ ∞ 0 P[X ≥ t]dt, we obtain:E sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) ≤ ∞ 0 P sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) ≥ t dt ≤ w 0 P sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) ≥ t dt + ∞ w k 2 exp(-2T 1+δ t 2 )dt ≤ w + ∞ w k 2 exp(-2T 1+δ t 2 )dt ≤ w + k 2 exp(-2T 1+δ w 2 ),where w > 0 is an arbitrary parameter. Set w= 1 T . If δ ≥ log(2 log(k)+ 1 2 log(T )) 2 log T , then: E sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) = E[ϵ t (M )] ≤ 2 1 T .Therefore, summing up over all T rounds, we obtainT t=1 E[ϵ t (M )] ≤ 2 √ T .B.6 Instantiating the meta-algorithm for Theorem 4.1Finally, we instantiate Theorem B.4 with a concrete no-regret algorithm for the (G, H)-player to obtain Theorem 4.1. We employ the specific no-regret algorithm of [Blo+22] for our (G, H)-player, restated here for reference. Theorem B.7 (Smoothed FTPL of [Blo+22] ). Let F : X → [-1, 1] be a function class and let ℓ be a loss function that is L-Lipscchitz in both arguments. Suppose further that we are in the smoothed online learning setting (see Section 4.1) where each x i are drawn from a distribution that is σ-smooth with respect ot some base measure B on X . Letπ t,n (f ) := n i=1 f (z t,i )γ t,i √ n ,where z t,i ∼ B are independent and the γ t,i are independent standard Gaussian variables. Suppose that α ≥ 0 and consider the algorithm which uses an α-approximate oracle for F (see Definition 2.1) to choose f t according tot-1 s=1 ℓ(f t (x s ), y s ) + ηπ t,n (f t ) ≤ inf f * ∈F t-1 s=1 ℓ(f * (x s ), y s ) + π t,n (f * ) + α,and let ŷt = f t (x t ). If F and y t are binary valued, with the VC dimension of F bounded by d ≥ 1,then for n = T / √ σ and η = T log(T L/σ) σ E[Reg T (f t )] ≤ C dT log T σ + αT ,where C > 0 is some absolute constant.This is precisely what the (G, H)-player does in Algorithm 1. Let G := {g ⊆ X : g ∈ G} be a collection of groups, represented as Boolean functions g : X → {0, 1}. Let H be a hypothesis class of binary-valued functions h : X → {-1, 1}. To be clear, the we map Theorem B.7 to our Algorithm 1 in the following way:• Let F of Theorem B.7 be the class of functions in [-1, 1] X defined by:F := {x → g(x) h(x) : g ∈ G, h ∈ H}.Note that each f ∈ F maps to {-1, 0, 1}.• Let the loss function in Theorem B.7 be the loss of the (G, H)-player on x ∈ X : l((g, h), (h(x), y)) := g(x) ℓ(h(x), y) -ℓ( h(x), y) .In terms of F above, we can rewrite this as:l(f (x), (y ′ , y)) :=    0 if f (x) = 0 ℓ(y ′ , y) -ℓ(-1, y) if f (x) = -1 ℓ(y ′ , y) -ℓ(1, y) if f (x) = 1.This loss function has the signature l :{-1, 0, 1} × {-1, 1} 2 → [-1, 1] because ℓ(•, •) ∈ [0, 1].It is also 2-Lipschitz in both arguments. • It remains to make sure that ternary-valued functions taking values in {-1, 0, 1} do not break the proof of Theorem B.7. In the proof of Theorem B.7 in [Blo+22] , the binary-valued function case where f has range {-1, 1} is handled by embedding {-1, 1} into the real line. There are two main parts of the proof that rely on this assumption that f has range {-1, 1} that easily maintain when f has range {-1, 0, 1}.-First, in Lemma 34 of [Blo+22] , the authors use L-Lipschitzness and the simple fact that|f (x) -f ′ (x)| ≤ (f (x) -f ′ (x)) 2 when f ∈ {-1, 1}. This still holds when f ∈ {-1, 0, 1}. -Second, [Blo+22] also use the fact that ∥f ∥ L2 = 1 for all f ∈ F, which is also true for f ∈ {-1, 0, 1}.Finally, the rest of the proof in Lemma 35 of [Blo+22] relies only on the Lipschitzneess of l to employ standard smoothness arguments and Rademacher contraction, which we have already established. • Putting all this together, the (G, H)-player in Algorithm 1 essentially runs the algorithm of B.7, with the caveat that it calls the OPT α (G,H) oracle M times to get the empirical approximation qt of the true implicit distribution q t over G × H. This implicit distribution is defined by the random process of drawing the n perturbations and calling the optimization oracle. Therefore, by Lemmas B.6, B.5, and Theorem B.7 applied to the "meta-theorem" Theorem B.4, we immediately obtain our main theorem, Theorem 4.1. We now restate Theorem 4.1 as Corollary B.7.1 with the specified choices of parameters. Corollary B.7.1 (Theorem 4.1, with parameters specified). Let Y = {-1, 1} be a binary action space, H ⊆ {-1, 1} X be a binary-valued hypothesis class, G ⊆ 2 X be a (possibly infinite) collection of groups, and ℓ : {-1, 1}×{-1, 1} → [0, 1] be a bounded loss function. Let the VC dimensions of H and G both be bounded by d. Let α ≥ 0 be the approximation error of the oracle OPT α (G,H) . If we are in the σ-smooth online learning setting, then, forM ≥ T 1+δ , δ ≥ log(2 log(k)+ 1 2 log(T )) 2 log T , n = T / √ σ,and η = T log(T /σ) σ , Algorithm 1 achieves, for each g ∈ G:E[Reg T (H, g)] ≤ dT log T σ + αT,where the expectation is over all the randomness of the (G, H)-player's perturbations and the H-player's Bernoulli choices.It is be clear from the statement of Theorem B.4 that our "meta-algorithm" Algorithm 4 straightforwardly applies for other online learning settings as well, so long as we adopt an appropriate strategy for the (G, H)-player. In this section, we give a few examples of this flexibility for discrete action spaces in the smoothed online setting and theInstead of |Y| = 2, we can let |Y| = K, more generally. In this case, a straightforward extension of Theorem B.7 allows us to embed Y ∪ {0, 1} into the real line, and we generalize to considering the Natarajan dimension [Nat89] of H instead of the VC dimension. Rademacher contraction and Lipschitzness still apply to l, so with just a difference in the absolute constant, we obtain the following multi-class analogue of Theorem 4.1 as a corollary. Thus, for the (G, H)-player in Algorithm 1, we can just use the same exact algorithm outlined in Theorem B.7.We make a small change to the H-player in Algorithm 1. In the multi-class action space setting, we need to make K calls to the OPT H oracle and solve a K × K size linear program for the H-player at each step. For completeness, we present the algorithm for the K-class action spaces here, as Algorithm 5.Algorithm 5 Algorithm for Group Oracle Efficiency (multi-class)Input: Perturbation strength η > 0; number of OPT α (G,H) calls M ∈ N. 1: for t = 1, 2, 3, . . . , T do 2:Receive a context x t ∼ µ t from Nature.3:for i = 1, 2, 3, . . . , M do 4:(G, H)-player: Draw n hallucinated examples as in Equation (4) to construct π bin t,n .(G, H)-player: Using the entire history {(ŷ s , y s )} t-1 s=1 so far, call OPT α (G,H) to obtainEQUATIONH-player: Call OPT H K times on the singleton datasets {(x t , k)} for action k ∈ [K] with the 0-1 loss, obtaining:h ′ k ∈ arg min h * ∈H 1 {h * (x t ) ̸ = k} 8:H-player: Using the M samples {(gEQUATIONH-player: Solve the linear programmin p∈R K ,λ∈R λ s.t. p ⊤ Le y ≤ λ ∀y ∈ [K] p k ≥ 0 ∀k ∈ [K] p i = 1(where e y is the y-th coordinate vector in R K ) 10:Sample k ∼ p, let h t = h ′ k .11:Learner commits to the action ŷt = h t (x t ); Nature reveals y t .12:Learner incurs the loss ℓ(ŷ t , y t ). 13: end for Theorem C.1. Let Y = {1, . . . , K} be a K-class action space, H ⊆ Y X be a K-valued hypothesis class, G ⊆ 2 X be a (possibly infinite) collection of groups, and ℓ : Y × Y → [0, 1] be a bounded loss function. Let the Natarajan dimension [Nat89] of H and the VC dimension of G both be bounded by d. Let α ≥ 0 be the approximation error of the oracle OPT α (G,H) . If we are in the σ-smooth online learning setting, then, for appropriate choices of M ∈ N, n ∈ N, and η > 0, Algorithm 5 achieves, for each g ∈ G:E[Reg T (H, g)] ≤ O dT log T σ + αT ,where the expectation is over all the randomness of the (G, H)-player's perturbations.In this section, we give the details on how to achieve the desired group-dependent regret guarantees of Section 5. Throughout this section, for any g ∈ G, let T g := T t=1 g(x t ). The results in this section hinge on the GFTPL with small-loss bound algorithm of [Wan+22] . The main idea will be to instantiate the (G, H)-player in our meta-algorithm, Algorithm 4 using the GFTPL with small-loss bound algorithm so Theorem B.4 allows us to directly inherit its regret guarantee. We quote the algorithm here, adapted to our setting, for reference. Throughout this section, we use the familiar notation from Section 4.2 of the main body:EQUATIONwhere ℓ(•, •) is the fixed loss of the entire multi-group online learning setting.Algorithm 6 GFTPL with small-loss boundInput: Perturbation matrix Γ ∈ [-1, 1] |G||H|×N 1: Draw i.i.d. vector ν = (ν (1) , . . . , ν (N ) ) ∼ Lap(1) N , i.e., p(ν (i) ) = 1 2 exp(-|ν (i) |). 2: for t = 1, 2, 3, . . . , T do 3: Set ν t ← νηt where η t > 0 is a parameter computed online.Using the entire history up to t -1 so far, call OPT α (G,H) to obtain (g, h) ∈ G × H sastisying:t-1 s=1 lxs ((g, h), (ŷ s , y s )) + ⟨Γ (g, h) , ν t ⟩ ≥ sup (g * ,h * )∈G×H t-1 s=1lxs ((g * , h * ), (ŷ s , y s )) + ⟨Γ (g, h) , ν t ⟩ -α, (21)where Γ (g, h) is the (g, h)th row of Γ. 5: end for In our setting, the classical FTPL algorithm of [KV05] draws |G| × |H| independent perturbations at each round, which requires enumeration of both G and H. In order to remedy this, the GFTPL algorithm of [Dud+20] uses a |G||H| × N perturbation matrix Γ to generate dependent "shared randomness." The transformation Γ applies to a perturbation vector ν ∈ R N , where N is much smaller than |G||H|. Running FTPL with these perturbations, then, results on an oracle-efficient algorithm. [Wan+22] extends this by showing that, under certain conditions on Γ, this oracleefficient algorithm can also achieve a small-loss regret, where the regret diminishes based on the total magnitude of the losses over the T rounds instead of the number of rounds. Specifically, a small loss regret looks like the following. It is well-known that, in the worst-case, a regret of O T log |G||H| is minimax optimal [CL06] . However, stronger bounds have been obtained for problems with "small losses" (see, e.g., [HP05; GSV14; LS15]), where, for a loss function f : (G × H) × Y → [0, 1], one can achieve:O   T t=1 f ((h t , g t ), y t ) log |H||G|   ,which is sharper than the O T log |H||G| bound when f ((h t , g t ), y t ) < 1 on some rounds. We desire this property to achieve a regret bound in the multi-group online learning setting that is sublinear in terms of the number of rounds a group appears T g . Following [Wan+22] , we require the perturbation matrix to have two sufficient conditions for 6 to obtain the desired small-loss regret. The first is γ-approximability, which is a condition that ensures the stability choices of (g t , ht ) and (g t+1 , ht+1 ) across rounds. In particular, the stability needed is a bound on the ratio:P[(g t , ht ) = (g, h)] P[(g t+1 , ht+1 ) = (g, h)] ≤ exp(γη t )for all (g, h) ∈ G × H, where η t > 0 is the per-round leraning rate of GFTPL. By Lemma 2 of [Wan+22] , the following condition is sufficient to ensure this property. We restate it here, translated to our setting.Definition C.1 (γ-approximability [Wan+22] ). Let Γ ∈ [-1, 1] |G||H|×N , where N is the dimension of the noise vector, ν in Algorithm 6. Define B 1 γ := {s ∈ R N : ∥s∥ 1 ≤ γ}. Γ is γ-approximable if, for all (g, h) ∈ G × H and (x, y ′ , y) ∈ X × Y × Y, there exists s ∈ R N with ∥s∥ 1 ≤ γ such that the following holds for all (g ′ , h ′ ) ∈ G × H: ⟨Γ (g,h) -Γ (g ′ ,h ′ ) , s⟩ ≥ lx ((g, h), (y ′ , y)) -lx ((g ′ , h ′ ), (y ′ , y)).The second property is implementability. This property actually allows us to use our optimization oracle (in our case, OPT α (G,H) ) to access Γ without explicitly representing it. In essence, it requires that we can generate a small number of "fake examples" that effectively implement the perturbation needed by Algorithm 6.Definition C.2 (Implementability [Dud+20]). A matrix Γ ∈ [-1, 1] |G||H|×N is implementable with complexity M if for each j ∈ [N ]there exists a dataset S j with |S j | ≤ M such that, for all pairs of rows (g, h), (g ′ , h ′ ) ∈ G × H, Γ ((g,h),j) -Γ ((g ′ ,h ′ ),j) = (w,(x,y,y ′ ))∈Sj w lx ((g, h), (y ′ , y)) -lx ((g ′ , h′ ), (y ′ , y)) .In the above definition, the fake examples are tuples of a context x ∈ X and two outcomes y, y ′ ∈ Y. Finally, with the sufficient conditions of implementability and approximability, we quote the main regret guarantee of Algorithm 6in [Wan+22] here. Theorem C.2 (Regret guarantee of 6 [Wan+22] ). Let {1, . . . , K} be the action space of the Learner and let Z be the action space of the adversary. Suppose that, at each round, the Learner chooses action x t ∈ [K], the adversary chooses action z t ∈ Z, and the loss function is f :[K] × Z → [0, 1]. Let L * T = min k∈[K]T t=1 f (k, y t ). Then, if there exists a γ-approximable matrix Γ, Algorithm 6 instantiated with Γ and η t := min 1 γ ,C √ L * t-1 +1achieves the following regret bound:E[Reg T ] ≤ 4 √ 2 max{2 log K, √ N log K} C + 2γ C + 1 C L * T + 1 + 8γ log 1 C L * T + 1 + γ + 2γ 2 + 4 √ 2 max{2 log K, N log K}γ.With an appropriate choice of C > 0, we may obtain the regret bound:O L * T max γ, log K, N log K (22)If Γ is also implementable with complexity M , then Algorithm 6 is oracle-efficient, making O(T + N M ) oracle calls per round, where N is the number of columns of Γ.Finally, we need one more lemma using a standard uniform convergence argument to bound the approximation error from sampling with OPT α (G,H) M times. This is essentially the same as Lemma B.6, but we obtain a sharper bound on E T t=1 ϵ t (M ) at the cost of making polynomially (in T ) more calls to the oracle.Lemma C.3. Let t ∈ [T ] and x t ∈ X be fixed, and consider the function lxt ((g, h), (y ′ , y)) := g(x t )(ℓ(y ′ , y) -ℓ(h(x t ), y)). Let |Y| = k < ∞. If M ≥ T 2 log(k 2 T ), then over the randomness of drawing M samples {(g(i) t , h(i) t } M i=1to construct the empirical distribution qt described in Definition B.4, for all y ′ , y ∈ Y, let ϵ t (M ) be defined as the supremum ϵ t (M ) := sup (y ′ ,y)∈Y×Y E (g, h)∼qt [ lxt ((g, h), (y ′ , y))] -E (g,h)∼qt [ lxt ((g, h), (y ′ , y))] ,and, over all T rounds,E T i=1 ϵ t (M ) ≤ 2.Proof. The proof of this lemma follows the proof of Lemma B.6 exactly, except for the choice of M . Therefore, just using the exact same notation as Lemma B.6, we have:P sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) ≥ ε ≤ k 2 exp(-2M ε 2 )By the same exact argument usingE[X] ≤ ∞ 0 P[X ≥ t]dt, we obtain E sup (y ′ ,y)∈Y 2 1 M M i=1 Z i (y ′ , y) ≤ w + k 2 exp(-2M w 2 ),where w > 0 is an arbitrary parameter. Set w = 1 T 2 . Then, if M ≥ T 2 log(kT ), we getE[ϵ t (M )] = E sup (y ′ ,y)∈Y 2 1 M i=1 Z i (y ′ , y) ≤ 2/T.The lemma follows from summing over T.Proof of Theorem 5.1. We can now prove Theorem 5.1. The main idea is that the small loss regret translates directly into a o(T g ) regret due to how we defined our loss function, lx , so we simply instantiate the (G, H)-player in the general algorithm template of Algorithm 4 with Algorithm 6. This allows us to directly inherit the o(T g ) regret guarantee. We restate it here, with parameters specified, as Proposition C.3.1.Proposition C.3.1 (Theorem 5.1, with parameters specified). Assume H, G are finite and there exists a γ-approximable and implementable perturbation matrix Γ ∈ [-1, 1] |G||H|×N . Let |Y| = k. Let α ≥ 0 be the approximation parameter of OPT α (G,H) . Let the no-regret algorithm for the (G, H)player in Algorithm 1 be the GFTPL algorithm of [Wan+22] instantiated with Γ, with parameter M = T 2 log(k 2 T ). Then, for each g ∈ G:E[Reg T (H, g)] ≤ O T g max γ, log |H||G|, N log |H||G| + αTProof. Armed with approximability and implementability, we are ready to prove Theorem 5.1. Suppose that there exists a γ-approximable and implementable perturbation matrix Γ ∈ [-1, 1] |G||H|×N . In the setting of Theorem C.2, we instantiate K = |G||H|, Z = X × Y × Y, and the loss function f (•, •) as:f ((g, h), (x, y ′ , y)) := lx ((g, h), (y ′ , y)) = g(x) (ℓ(y ′ , y) -ℓ(h(x), y)) .Observe that, with the loss instantiated as lx , we have: L * T = min (g,E[Reg T ] ≤ O L * T max γ, log |G||H|, N log |G||H| ≤ O T g max γ, log |G||H|, N log |G||H| .However, this is just the regret guarantee of Algorithm 6, not the regret guarantee of our end-toend multi-group online learning algorithm, Algorithm 1. We replace the algorithm of [Blo+22] in Algorithm 1 with Algorithm 6. That is, we use the Algorithm 6 for the (G, H)-player in Algorithm 4; a full description of this substitution is in Algorithm 7. By our meta-theorem, Theorem B.4, this entire algorithm achieves the multi-group regret guarantee, for all g ∈ G: One possible setting in which a Γ matrix is easily constructible is the transductive setting. Here, we explicitly show how to construct Γ to obtain Corollary 5.1.1.EQUATIONProof of Corollary 5.1.1. Let X ⊆ X be the set the adversary fixes beforehand in the transductive setting, where N := |X|. We can construct a 1-approximable and implementable Γ ∈ [-1, 1] |G||H|×4N by creating a row for each (g, h) ∈ G × H and a column for each (x, y, y ′ ) ∈ X × Y × Y, and setting each entry as Γ ((g,h),(x,y,y ′ )) := lx ((g, h), (y ′ , y)).Algorithm 7 Algorithm for Group Oracle Efficiency (with GFTPL)Input: Perturbation matrix Γ ∈ [-1, 1] |G||H|×N ; number of OPT α (G,H) calls M ∈ N. 1: for t = 1, 2, 3, . . . , T do 2:Receive a (possibly adversarial) context x t ∼ µ t from Nature. (G, H)-player: Draw i.i.d. vector ν = (ν (1) , . . . , ν (N ) ) ∼ Lap(1) N , i.e., p(ν(i) ) = 1 2 exp(-|ν (i) |). 5: (G, H)-player: Set ν t ← ν ηt where η t := min 1 γ , C √ L * t-1 +1 . 6:(G, H)-player: Using the entire history {(ŷ s , y s )} t-1 s=1 so far, call OPT α (G,H) to obtain (g, h) ∈ G × H satisfying:EQUATIONwhere Γ (g, h) is the (g, h)th row of Γ.end for 8:H-player: Call OPT H twice on the singleton datasets {(x t , -1)} and {(x t , 1)} with the 0-1 loss, obtaining: h ′ 1 ∈ arg min h * ∈H 1 {h * (x t ) ̸ = 1} h ′ -1 ∈ arg min h * ∈H 1 {h * (x t ) ̸ = -1} .EQUATION11:Learner commits to the action ŷt = h t (x t ); Nature reveals y t .12:Learner incurs the loss ℓ(ŷ t , y t ). 13: end for NeurIPS Paper Checklist38th Conference on Neural Information Processing Systems (NeurIPS 2024).In fact, it will suffice to have a substantially simpler oracle that, given a single (x, y) ∈ X × Y, determines if there exists h ∈ H such that h(x) = y.Technically, we use the TRAINBYOPT variant of LISTUPDATE from Theorem 16 of[GKR22].A probability measure µ is absolutely continuous to another measure B if, for every B-measurable set A, B(A) = 0 implies µ(A) = 0. 


Decision: The reviewers are in agreement that this paper is a solid piece of work that designs computationally efficient algorithms for online multi-group learning. In comparison with previous works, this paper avoids the enumeration of groups (and assuming access to a (G,H) offline learning oracle) which results in a reduced computational complexity. 

In the final version, the authors are encouraged to incorporate discussions, e.g. comparison table, the feasibility of (G,H) offline learning oracle, and regret lower bounds.

Reviews: review: paper_summary: paper_summary: This paper studies the online multi-group learning problem, and considers it in both smoothed context and general ($\gamma$-approximatable) settings. Unlike the traditional online learning setting, this paper considers achieve low regrets for all groups (subsequences). It utilizes the adversary moves first (AMF) framework for multi-objective online learning from [Lee+22] and the follow-the-perturbed-leader (FTPL) algorithm to handle the large number of groups. Through subtle algorithmic design and analysis, the paper achieved computationally-efficient and oracle-efficient learning.
strength_weakness: strength_weakness: The main text in Section 2 and after are fine, while Section 1 needs improvement. Specifically, some descriptions are unclear. 

For example, the bound $\tilde{O}(\sqrt{NT_{g}\log\lvert H\rvert \lvert G\rvert})$ is achieved for each group $g$, but this is not brought forward in summary of result (Line 76) and the last time $g$ is mentioned as one group is in Line 18. 

Line 54-55, if $G$ is rich and expressive, then all subgroups well-approximated by a group $g$ in $G$ will be "covered" by whom? What does this sentence mean?
questions: questions: See Weaknesses.
limitations: limitations: No concerns.
paper_summary: paper_summary: The paper provides oracle efficient algorithms for online multi-group learning. The goal is to obtain sublinear regret for each group subsequence $g \in G$ simultaneously. 
[BL20] showed that $o(T_g)$ regret is possible with finite $H$ and $G$ but must enumerate both $H$ and $G$. [Ach+23] showed $o(T_g)$ regret while being oracle efficient in the hypothesis class, but must enumerate over $G$.  In this work, the authors use an optimization oracle for $G \times H$ jointly and avoid explicit enumeration for either G or H.

To do so, they reduce the multigroup online learning to Adversary moves first framework of [Lee+22], and adapt results from oracle efficient online learning in the standard (no-groups) setting.
strength_weakness: strength_weakness: - For the $G \times H$ oracle mentioned in definition 2.2 the authors defer to [GKR22] who in turn provide two constructions: one based on ternary classification and another alternating minimization heuristic.  It would be beneficial to add a longer discussion on this in the main body or the appendix to make the paper self contained.
- Computational efficiency of the $G \times H$ oracle, this hasn't been discussed explicitly, are there group structures for which the optimization over G is efficient and doesn't involve enumeration?Algorithm 6 in [GKR22], doesn't discuss this either, it seems like without any further assumptions, enumeration is the best we can do in practice.
questions: questions: Please address the above.

Also, the appendix describes multi-class action space, what would change with real valued labels?
limitations: limitations: The authors discuss limitations of their paper.
paper_summary: paper_summary: This paper studies the problem of online multi-group learning where the algorithm should achieve sublinear regret with respect to all groups. They propose a group-wise oracle-efficient algorithm that avoids enumerating all groups by accessing the group oracle. An $\tilde{O}(\sqrt{dT/\sigma})$ regret bound is derived for $\sigma$-smoothed online learning setting.
strength_weakness: strength_weakness: 1. The discussion of related work for online multi-group learning is not adequate. It would be better if the author included the regret bound and online learning setting in the related work. I think listing a table for comparison among these works is better.
2. The motivation of using the AMF framework and FTPL is still not clear and needs more discussion. Moreover, it would be better if the author could clarify the novelty in the analysis.
3. It would be better if the author could also show the lower bound of this problem. Thus we can see how tight regret is obtained and which part can be improved in future work.
4. The computational efficiency of the $(G, H)$-optimization oracle is not discussed. It seems that this oracle is much harder than the ERM problem in [Ach23+] since this oracle optimizes over both $G$ and $H$.
questions: questions: Please see the weaknesses part.
limitations: limitations: The authors have addressed the limitations and societal impact.
paper_summary: paper_summary: Multi-group learning has been attracted attention and solutions for small-sized groups are already available. This paper further studies the online learning case when the group $\mathcal{G}$ is large or even possibly infinite. In addition to designing an algorithm, the paper also provides extensive theoretical analysis on the results in three settings: the i.i.d. setting, the adversarial setting with smoothed context distributions, and the adversarial transductive setting.
strength_weakness: strength_weakness: 1. The theoretical analysis is restricted on binary case, i.e. $\mathcal{Y} = \{ -1, 1 \}$. I am aware that the multi-class case would be much difficult to analyze, but this certainly shall be one of the possible directions in the future.

2. (minor) Definition 4.1 uses measure theory that is in a graduate-level course in real analysis and is likely a rarely appearing concept for the majority audience. To keep the paper self-contained, it might be helpful to thoroughly define all concepts such as essential supremum and the differentiation of measures.
questions: questions: I do not have any questions at this moment.
limitations: limitations: Yes.

Comments: title: Thanks for the response
Official Comment by Reviewer K3De
comment: I appreciate the concise response by the authors. I am happy to keep my score.
Thanks for your response. You have addressed my concerns about the related work, lower bound, and computational efficiency of the oracle. Hence, I will raise my score to 6.
Thank you very much for the response. Please include the discussions in revision for better readability. I will keep the current review.
Thanks for the addressing my comments, I stand with my original assessment for accepting this paper.  I appreciate the discussion on oracles for GxH and highlighting this in the main body and providing some concrete though not always computationally efficient heuristic in the appendix would be great, these should also address the other reviewer's concern.