Group-wise oracle-efficient algorithms for online multi-group learning
Authors: Samuel Deng
Jingwen Liu
Daniel Hsu
Venue: NeurIPS 2024 poster (2024)
Keywords: multi-group learning
online learning
oracle-efficient
Primary area: learning_theory
TL;DR: We develop algorithms for achieving sublinear regret in online multi-group learning when the collection of groups is exponentially large or infinite.

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.

Group-wise oracle-efficient algorithms for online multi-group learning
Samuel Deng
Daniel Hsu
Department of Computer Science
Department of Computer Science
Columbia University samdeng0cs. columbia. edu
Columbia University
d whssuccs.oouubbeee columbia. edu
Jingwen Liu
Department of Computer Science
Columbia University jngwenliu@cs columbia. edu
Abstract
We study the problem of online multi-group learning, learning model in which online learner must simultaneously achieve small prediction regret 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 contrast previous work on this learning model, we consider scenarios in which the family of groups is too large to explicitly enumerate, and hence seek algorithms that only access groups via an optimization oracle, 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.
Introduction
We study the problem of online multi-group learning, originally introduced by [BL20) (adapting the specialists/time-seeeede
setup of (Blu97 Fre+97 BM07)) In this learning model, consider collection of groups G, which are (possibly intersecting) subsets of context space X, as well as hypothesis class H of functions defined on X' Contexts Ii 22 .2, 2r arrive one-by-one sequence of rounds, and the learner must make a prediction associated with each zy- The learner's goal is to perform well on every subsequence of rounds corresponding 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.
common interpretation of multi-group learning- which is natural when considering fairness in machine learning iidenifiiss contexts X' with individuals, each group g G with subpopulation (perhaps defined by a combination of various demographic features such as age and gender). and each hypothesis 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-speeil hypothesis, for all subpopulations simultaneously.
The standard benchmark in online learning is regret, which compares the performance of the learner all rounds to that of the single best hypothesis in hindsight. But such benchmark is only meaningful there is a hypothesis that performs well in all contexts. At the other extreme, we may hope that the learner performs well using the best context-specifie hypothesis in every
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 = ) and the latter when 9 = {{2) ) x E ).
We are particularly interested in scenarios where 9 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 typically difficult to ensure [Kea+18 18 Heb+18 KGZI9; 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 constructed to include data from all patients (healthy and sick) as 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 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 subgroup 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.
1.1 Summary of Results
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 as representing binary-valued function class that takes in contexts and selects subsequences S C [Z'] 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()) regret for fully worst-case adversaries is impossible [HK 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 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):
Hag+22 HRS22
1. Group- oracle efficiency for the smoothed setting. We present an oracle-efficient algorithm that achieves Ō( D(/dT/o) regret every group g E G for binary-valued action space for the smoothed online learning setting of (HRS22 Blo+22), where d is a bound on the VC dimension parameter interpolating between the scenarios in which contexts are
of H and G. and generated by a worst-case adversary and a benign, fully i.i.d. adversary.
2. Group-wise oracle-efficiency through generalized gellow-the-perturhhe leader. If a sufficient condition referred to as 7-approximability previous literature ( ([Wan+22)) met, a variant of our oracle-efficient algorithm achieves, for each particular g E G, a regret of ÖVNT,, log H|] for finite H and G, where N corresponds roughly to required number of perturbations, and T is the number of rounds E [7] in which 2; E 9. The dependence on T, as opposed to T is preferable if some groups do not appear frequently over the T rounds. As a special case, our

---

Work
Setting
Regret
Computation
Oracle- Oracle- efficient
efficient in
H.
BL20
Adversarial
V Tg log [ for all
Time:
((H)))))
No
No
DEB G
Space:
0
g)
Ach+23
Adversarial
To 1 log [ for E
Time:
(( Space:
Yes
O((g))
Blo+22
a-Smooth
dT log (does not
Time: poly(T) calls
Yes
N/A
handle multi-group
to optimization oracle
ting)
H2
a-Smooth
dT log 0l/2
(does not
Time: poly(T) calls
Yes
N/A
handle multi-group set- ting)
to optimization oracle
Ours (The- 4.1
a-Smooth
AT do T for all g e
Time: poly(T) calls
Yes
Yes
orem
to optimization oracle
Ours (The-
7-approximable
NTg log G for all g
Time: poly(T) calls
Yes
Yes
orem 5.1
optimization oracle
Ours
Transductive
N1/4 v TT log [
Time: poly(T)) calls Yes to optimization oracle
Yes
(Corollary
for all E g
[51.1]
Table 1: In the table above, T the number of rounds of online learning, Tg is the number of rounds for particular group H is the hypothesis class, G is the collection of groups, and is the smoothness parameter defined Definition 4.1 d is an upper bound on the VC dimension of H. In our a-smooth result in the fifth row, d is also upper bound on the VC dimension of a possibly infinite collection of groups, G. the y-approximable setting of the sixth row, N is the number of perturbations.
algorithm also achieves O(N1/4 VT, log (H[[g] in the transductive setting of [BM997 KK05 where the adversary must reveal a set of N future contexts before learning begins.
Table [ ssummarizes 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 ex- tend this framework with the following technical enhancements: sparsifying the implicit distributions over the hypothesis spaces used by the min-max game that is solved in every iteration of AMF.
(FTPL) algorithms, and simplifying
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 E G. However, naively applying AMF requires us to enumerate these objectives, turn enumerating G. the main issue we want to avoid. FTPL comes 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 E G; FTPL ensures this 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.
1.2
Related Work
BL20 showed that it possible achieve sublinear multi-group regret by reducing to the specialists framework of (Blu97) [Fre+97; Fre-97) BM07] (a.k.a. sleeping experts). The multi group regret they achieve scales logarithmically in both and G; this recovers the minimax regret when specializing to the
standard online learning setting (with finite H) with only single group. The paper focuses regret rather than computational considerations; a direct implementation of their algorithm uses time and space linear in [H] [9]. and there stated guarantees for infinite H or G.

---

[cch+33] show how to avoid enumeration of H. using an optimization oracle for H. They achieve this by applying a meta- allgoiitg 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 9 x H jointly and hence avoids explicit enumeration of either G or H.
GKR22 HJZ24] In this setting, training data is drawn i.i.d. from a fixed distribution, and the learner's s goal find single hypothesis h (possibly outside of H)) that ensures small excess risk B[((h(z), y)
Multi-group (agnostic) learning has also been studied in the batch setting RY21 TH22
x E g) knf ((((h(()) 3) I E g] for every group E G simultancously. The works of RY21 HJZ24) design algorithms for achieving this learning criterion under certain "multi-PAC multi-group group learning algorithms that remove the need for this assumption. One of the algorithms of (TH22J, 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.
compatibility assumption on H. and G. [GKR22] TH22 design multi
The proof of our algorithm builds on two primary technical frameworks studied in previous literature: the adversary moves first (AMF) framework of (Lec+22), and line of work designing follow- the- perturruurdd leader style algorithms [KV05) for adversarial online learning in the oracle-efficient learning model [K055 SKS16 Hag+22 B Blo+22 Wan+22].
2 Preliminaries
2.1 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 the label space. A group g is subset of the context space X. We overload the notation for a group by using it as an indicator function / := 1 f E g} for group membership. Let 2 denote all subsets of the context space X, and let y denote all possible mappings from X' to V. For an integer n. denote [n] := (1.2..... n).
For simplicity of exposition, we will focus the setting where is binary throughout, i.e. y 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 Cfor details).
2.2 Online Multi-Group Learning
We formally define the multi-group learning model as follows. Let g C 2 be collection of (possibly non-disjoint groups, and let H C )x be a hypothesis class of functions h X - y mapping from contexts to actions. Let é y y + [o, 1] be bounded loss function. In each round t E [
1. Nature chooses (z,, Mt) E X' x y and reveals Zt.
2. The learner chooses an action ÿt e.
3. Nature reveals ye E y.
4. The learner incurs loss E(je. yc) E [0,
The choices of Nature and the learner may be randomized. In the standard online prediction setting, the regret of the learne is the difference between the cumulative loss of the learner and that of the best-in- -hindsghh hypothesis from H: Regr-(H) ;= Σi E(Gr, Vt) minncH ΣT E(h(az). 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 E [T] I E g) defined by the groups E G and the sequence of contexts II,...,,yy 2r. Specifically, the (multi-group) regret of the learner on group g
Regr (H, =- - (()))) ve) min Σ (((l))(((())))))
KER
Crucially, the best hypothesis for one group may differ from that of another group. Further, groups may intersect, precluding the strategy of simply running separate no-regret algorithm for each group. The learner seeks to achieve achieve sublinear expected regret, all groups g e G simultaneously.

---

2.3 Group Oracle-Efficiency
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 9).
Definition 2.1 (Optimization Oracle), For some error parameter a 2 0 and function class F E Z" an a-approximate optimization oracle OPT takes a collection of pairs (I1; 21), (Im, 2m) E X' 2, a sequence of weights w1,--. Wmn E IR, and a sequence of m loss functions & 2 2 and outputs a function f = OPT (f 24, w)))==)) E F satisfying:
(-1,111
w. wrlr(f(m;)))) 2)) E inf JEF
w w(((((()),2z ta.
Instantiating (in Definition 2.1 Z as our action space y, each l; as the given loss of our problem, and F as our hypothesis class H gives standard empirical risk minimization (ERM) oracle over dataset {< yı) ) 1= We present this more general definition to distinguish the action space y the problem from the output space of the oracle (see Definition 2.2
The optimization oracle regarded
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 H. defined follows.
Definition 2.2 ((G, H) optiiiizinnnnnnn oracle). Fix error parameter 2 O. For collection of groups 9 E 2* a collection of hypotheses H _ y*, and a sequence of m loss functions 4 : (40. x )) x ()' x )) + [-1, a-approximate (G, -opotiiiiziiionnn oracle OPT (PT( (G.H1) is
an a-approximation optimization oracle (Definition 2.1 that outputs a pair (g. h) E G x H satisfying:
(y1, v()) 2
sup (9* E
wilills" (rs)) (xx)), (3i, v()) a.
(2)
= (which we assume in the main paper body), this oracle outputs a group-hypothesis pair (ō. h) that maximizes the batch loss over m examples (æz, (Vi, v()) in X' x {-1, [GKR22] also made such an assumption and gave two implementations: one based on cost-sensitive classification oracles for G and H separately, the other 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
Definition 2.3 (H-optimization oracle). For collection of hypotheses H y and sequence of m loss functions & : y x y + [-1, 1), an H-optimization oracle OPTh is a O-approximation optimization oracle (Definition 2.7 with
0) that outputs hypothesis h. E H satisfying 1 ()(x()())), 9:) < infx cH Ex 1i=1 (x:)),,,
E m
3 Warm-up: LLD. Setting
In this section, as a warm-up, we consider a setting where Nature is stochastic and oblivious: the (Ne, ye) drawn i.i.d. from single fixed (but unknown) distribution μt, independent of any choices of the learner. In standard online prediction setting with i...d. data, it suffices to use a "follow-the- leader" (FTL.) strategy (see, e.g., (Haz22]). ), which 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 E G simultaneously, we need a multi- multi-group analogue of FTL.
In fact, it will suffice to have substantially simpler oracle that, given single (x,, y) E X x y, determines if there exists h H. such that h(x) y.
5

---

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-gron 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 both have VC dimension at most d 2 1. For any E 9, let P(g)= == [[(]) be the probability mass of group g.
Theorem 3.1 (Theorem 16 of [GKR22]. For any E (0. given i.i.d. training samples UX y4 1= from μ,, the LISTUPDATE algorithm returns a function : X + y such that, with probability - 6, for any group E g.
1.00
1
((
(
(alogn + log(1/0) 1/3
[[(((()) v) E < min E(((h(x)))) v) [
P(g)
MEN
Moreover: LISTUPDATE makes pnly(n, d, log(1/6)) calls to a (G, H) optimization oracle.
Our algorithm, ONLINE LISTUPDATE, forms its prediction Dt in round / as follows:
Run LISTUPDATE on the samples from previous rounds (I1 21 )1), J1),.... ...., (Ir-1: (11--13B-1))
Lett f. denote the function returned by LISTUPDATE, and predict ğ. fe(z)).
Using Theorem 3.1 we obtain the following multi-group group regret bound for ONLINE LISTUPDATE.
Theorem 3.2. (fr, We) are drawn ii.dd from fixed distribution over X' ),, ONLINE LISTUP- DATE achieves the following expected multi-g group regret bound: for all g E G.
E E[Reg (H. g)] = =0 (ddlog 13 22/3 + vdT log
The proof of Theorem 3.2 is given in Appendix A
4 Group Oracle-Efficieng, with Smooth Contexts
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.idd. setting of Section B is a special case. We then present our main algorithm, Algorithm [ for achieving oracle- efficient online multi-group learning (Section (.22). Easy modifications of this main algorithm will admit oracle-efficient online multi multi-group learning for other common online learning specifications, described in Section
4.1
Smoothed Online Learning
We now describe smoothed online learning. prevalent model in recent literature in computation- ally efficient online learning that formalizes the natural relaxation that Nature is not maximally adversarial [SSTI]/HRS22] Hag+22 Blo+22]. The main assumption is that, instead of choosing arbitrary (possibly worst-case) examples (It, Vr E X' x ) at every round, Nature adversarially fixes a distribution μlr over X' and draws Iı ~ (4t, while still drawing 3/+ adversarially. Formally, we restrict such distributions to be o-soooth, following the definitions of [Bo++2 HRS22).
Definition 4.1 (a-smooth distribution). Let p be some probability measure on X. and let B be a base measure on X. The distribution is omotoh (with respect to B) if is absolutely continuou with respect to B and
dp dB
ess sup
<
We denote the set of all a-smooth distributions on X with respect to the measure B as Sa (X, B). B is clear from context, simply write (X.) We assume that have sample access to B throughout. For simplicity, one may assume is uniform on X.
Techhnically, we use the TRAINBYOPT variant of LISTUPDATE from Theorem 16 of [GK222 A probability measure is absolutely continuous to another measure B if, for every B B-measurable set A. B(A) = 0 implies p(A)= 0.

---

Definition 4.1 interpolates between the benign setting where is are drawn i..d. from when o and the fully adversarial setting when o approaches In this sense, the warm-up result of Section is special case of this setting when a and /a is fixed for all rounds. Note that this definition does not restrict the choice of ye at all; yt 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 as the o-smooth online learning setting. For each round E [2]]
1. Nature fixes a distribution E S (Ze) that may depend in any way on the entire history prior to round Nature samples z2 ~ fe and chooses y/+ 3 adversarially; xy revealed the learner.
2. The learner (randomly) chooses an action ÿt. E y
3. Nature reveals Yt E y, and the learner incurs the loss E(jt, ye) E [0, 1].
We now depart from the previous literature that considers oracle-efficient algorithms in this setting ([HS222, Blo+22),, ), as we focus on the more difficult objective of minimizing multi-group regret over collection G, in Equation ( This setting will allow to employ our (G, -optimiizaniionn
oracle in Definition 2.2. a full description of our algorithm is now in order in Section 4.2
4.2 Algorithm for Smooth Contexts
In this section, we present Algorithm [ our main algorithm for multi-group online learning for the a-smooth setting. At a high level, our algorithm takes inspiration from the very general adversary- moves-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| as the H-player. On each round the (G. H-lplayer employs a (g, -otopiiiizttion oracle, OPT H)) to play a distribution over group-hypothesi pairs that maximizes the misfortune of the H-player, based on the history up until t. Upon receiving this distribution (and the context Te from Nature), the H-player chooses It randomly according to a distribution obtained by solving a simple constant-size linear program, and then incurs the loss ((Ue, 3r). The (G, Hll-payer,, taking this new loss into account, can now adjust his strategy 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 ever accessed directly, although our proofs need to maintain distribution over G x H. In order to do this, we make the crucial observation that FTPL maintains an implicit distribution over G x H. and we sparsely approximate that distribution through repeatedly querying the OPT H) oracle. (For clarity, we use the tilde decoration, h and ÿ. on hypotheses and groups obtained by the (G, H)-player using OPT(g.))))
Main algorithm. For any E X, define &. (40, 1 x )) x (1) )) + [-,,]] as:
(C Ri), (s', v) = 5(x) (1ss/ v) {(h(z)
where ((s,)) .) is the loss given by the learning problem. The quantity E, the loss that the (G, H)- player is maximizing; it corresponds to the single-round regret of the learner group g to the hypothesis h if the context on that round 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 To generate these hallucinated perturbation examples, we independently draw 2,, ~ B and "t.j N 1), samples j E [m] from the base measure and the standard Gaussian, respectively. In this section, y = (-1, 1) and H S 1_,, so we use the perturbations in their FTPL variant for binary-valued action spaces (outlined in Appendix B.6).
== (taag(E Vn
bin π Ttn (g, I1 11)
j=1
Remark. We focus the setting where y = 1) for ease of exposition, but settings in which y is a general finite set can be handled with easy modifications. See Appendix Corr details.
Remark. group online learning settings other than the o a-smooth setting can be handled appropriately simply by replacing the strategy of the (G, H) -layye by an appropriate no-regret
7

---

Algorithm Algorithm for Group-wise Oracle Efficiency (for smoothed online learning)
Input: Perturbation strength 0: perturbation count N; number of oracle calls M N. 1: for t 1,2, ....... do
2: Receive context 2, bi from Nature.
3: for = 1.2.3..... do
4:
(G, Hl-plyyrr: Draw n hallucinated examples in Equation 4 to construct "t,"
5:
(g, Hll-ylyye: Using the entire history {(Ds, No))a=1 so far, call OPT ()) to obtain
( (()) E EG x H satisfying:
La (Cat (1) _1()), (Be, vo)) + "en (9i
bin
1( ,
Σ El (lg" h)), (Us. Fiin (g", ,,,h,))) (5)
(9' x s=1
6: end for
7: H-player: Call OPT twice on the singleton datasets { 1)} and {(2r, 1]]; with the 0-1
loss, obtaining:
M1 E argg min (x+)) #1,, M-1 E arg min (x+e # -1}.
MEN
K-EH
8: H-player: Solve the linear program
min PRER
M Σ plz, ((0) (()))))))
subj. to
+ (1-p)),, ((06" ((0)), (A))(())) s
1=1
Vy E {-1,1}
0 PSP
9: Sample Ber(p) where E {-1, 1), let h4 = hig-
10: Learner commits to the action jt. = h,(xx) Nature reveals V/-
Learner incurs the loss E(ge. yr)-
12: end for
algorithm with access to OPT Examples of such variants are given in Section 5 and the general framework for such modifications is given in Appendix
Remark. With appropriate modifications, strategy of (2)g+22) instead, inheriting the -144 dependence summarized in Table ! Our focus in this paper is not on the dependence on a, however, so our main exposition centers around the similar algorithmic techniques of [Blo+22V.
instantiate the (9, Hlypyyyer with the FTPL style
It is clear that G and H never accessed except through OPT (g.x) and OPT.. We make M oracle calls OPT.g 20) and two oracle calls OPT each round.
1-1,1} be binary action space, S {-1,1)& a binary-valued hypothesis class, G _ 2x be (possibly infinite) collection of groups, and E: (-1,1} x {-1,1} [0, 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.wc- If we in the a a-smooth online learning (o))(T/o), and n7 poly(T/o). Algorithm I Machieves, for
Theorem 4.1. Let
setting. then, for M poly(T), each g E G:
dT log T
+ aT aT).
E|Reg, g)) 00
8

---

where the expectation is over all the randomness of the (g, playyrr'''s perturbations and the H-player's Bernoulli choices. (See Corollary B.7.I for precise settings of M, n, and ny.)
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 multi- plicative weights algorithm hedge against the mulriple objectives, requiring explicit enumeration. Departing from previous literature, however, our (g. -playyy uses a follow-ther -hereture-- leader (FTPL. style algorithm (see, e.g., (KV05)) with OPT (g.H)- The particular follow-the- follow-the-perturred 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 T is that the H-player must receive a distribution over G x H to reduce the complex multi-objectivy criterion of performing well against all (g. h) E G x H to 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 x H. which is insufficient. To remedy this, make the crucial observation that FTPL algorithms implicitly maintain a distribution over G x H through the randomness of their perturbations, and, thus, we construct the empirical approximation of this distribution through repeatedly calling (g 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 distribution over )' by by solving exceedingly simple linear program (LP) with two optimization variables, p and X. The value p E [o, 1] corresponds to the parameter of a Bernoulli distribution from which 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 [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 are used just to find the actions achievable by H on 2y. (Note that it is possible that (xx) A y for some y y, in which case the Learner will always play -y', regardless of the value of p.)
5 Group Oracle-Efficiency in Other Settings
In the previous section, we presented an algorithm that achieves o(T)) expected regret for all g E 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, natural extension would be to
ensure stronger "adaptive" regret bound that instead scales with Ta >D - g(x)), 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 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 modify Algorithm [ via the Generalized Follow-the Perturbed-Leatee regret guarantees on group g where the dependence on T is replaced (at least part) with Ty. Due to space limitations, we give sketch here; the full details are in Appendix [
(GFTPL) frameworrk of [Dud+20) Wan+22] to obtain
We first make a simple observation that motivates our use of more advanced oracle-efficient online learning techniques. Recall the ğ-specific per-round regret h of playing M(x,)) round E (T]:
t. ((g, h), (h(x)), ) b)) = =xxx) (((h(z)), v) - ((((z)))))
The job of the (G, H) -layye 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 regrel 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 tighter

---

regret bound when losses are small in magnitude. is immediate that Ex, ((g. h), (h(z)), v) 0 whenever g(x,) = 0, small-loss regret would immediately give a o(Tg) guarantee.
We focus on the case where 9 and H are finite, and 9 x H is the set of experts the (g, H))player has access to. Most small-loss regret algorithms would require prohibitive enumeration of g x H (HP05) CL06 GSV14 LS15). but the GFTPL with small-loss bound algorithm of [Wan+22] has the property that 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 (KVO5), generates a noise vector to perturb each each decision of expert. However, whereas the classic FTPL algorithm generates [g] x [H|] independent random noise variables, GFTPL only generates N < |9] x [M]
independent random variables and uses a perturbation matrix (PM) I' E [-1, [] N to translate the noise vector back [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 I 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 I correspond
dataset of "fake examples" suitable to OPT (.) Approximability with parameter > 0 guarantees the stability property that
the ratio P( h₂) = (g. h))//P((@++11 h1+1) (g. h)] S exp(>m:) for all h) G x H. where Mh > 0 is the per-round learning rate of GFTPL. If such a I" exists, then instantiating the (G, H))-layer
in Algorithm| with GFTPL (instead of the algorithm (Blo+22) gives us the stronger o(Tg) regret
guarantee. Full definitions and the proof, with the precise setting of M, can be found in Appendix C and Proposition C.3.I
Theorem 5.1. Assume H. G are finite and there exists apppprooximbll and implementable pertur-
bation matrix I E [-1,1]]911H)
Let a 2 0 be the approximation parameter of OfT. (G.H) (g.H) Let
the no-regret algorithm for the (g, H)-player in Algorithm Tbe the GFTPL algorithm of [Wan+22) instantiated with r, with parameter M poly(T). Then, for each g G:
E[Regr S0 COOVVT max {7: (7:1og|711 [H|lg] / log H aT)
We give a particular setting in which one can easily construct approximable and implementable F. Transductive Setting. In the Iransductive setting of [SKS16 Dud+20), Nature reveals set X X to the Learner at the beginning of the learning process; then at each round E (T), Nature can only choose oe from X. Let N := | denote the number of different contexts that Nature chooses from. For this setting, we can explicitly construct I' to get the following result.
Corollary 5.1.1 (Transductive setting). In the transductive setting, there exists perturbation matrix E 1-1, 1]91111)))) such that Algorithm with GFTPL parameterized with M =T' and OPT (9.M0 with error parameter & 2 O satisfies:
(R,,gr(H, 5o (vT max {log [H[] V N log H||6 aT)
for all g E G.
Suppose that N < T (which is the case in the transductive learning setting from KK05 D. Then the regret bound (ignoring the dependence on log(HH[[9))) on group is O O(TT,T774 which is asymptotically smaller than vT whenever T o(v()) If N is fixed independent of T, then the regret bound (TT)).
Conclusion and Future Work
In this paper, we design algorithms for online multi-group learning that are oracle-efficient and achieve diminishing oT) expected regret for all groups g E 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,) group-specific regret for infinite H and G and in more general settings.
10

---

Acknowledgments
We are grateful to Abhishek Shetty for pointing out possible improvements to the dependence on We acknowledge funding support from a Google Faculty Research Award to Daniel Hsu, the NSF under grants IIS-2040971 and CCF-2008733, and the ONR under grants N00014-24-1-23 1-2700 and N00014-22-1-2713. Samuel Deng acknowledges funding from the Avanessians Doctoral Fellowship for Engineering Thought Leaders and Innovators in Data Science.
References
[Ach+23]
Krishna Acharya, Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, and Juba Ziani. Oracle Efficient Algorithms for Groupwise Regret. arXiv:2310.04652 [cs]. Oct. 2023.
[BKM97]
Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. "Online Learning versus Offline Learning.. In: Machine Learning 29.1 (Oct. 1997), pp. 45-63.
[BL20]
Avrim Blum and Thodoris Lykouris. "Advancing Subgroup Fairesss via Sleeping Ex- perts". In: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Ed. by Thomas Vidick. Vol. 151. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl Leibniz-Zentrumn für Informatik, 2020, 55:1-55:24.
[Blo+22]
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. "Smoothed Online Learning is as Easy as Statistical Learning", In: Proceedings of Thirty Fifth Conference on Learning Theory. Ed. by Po-Ling Loh and Maxim Raginsky. Vol. 178. Proceedings of Machine Learning Research. PMLR, July 2022, pp- 1716-1786.
[Blu97]
Avrim Blum. "Empirical support for winnow and beiigted-maajoinn algorithms: Results on calendar sched uling domain".. In: Machine Learning 26.1 (1997), pp. 5-23. Avrim Blum and Yishay Mansour. "From External to Internal Regret", In: Journal of Machine Learning Research 8.47 (2007), pp. 1307-1324.
[BM07]
[BT97]
Dimitris Bertsimas and John N. Tsitsiklis. Introduction linear optimization. Vol. 6. Athena scientific optimization and computation series. Athena Scientific, 1997, pp. I-XV, 1-587.
[CL06]
Nicolo Cesa- Desa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[Dud+20]
Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. "Oracle-efficient Online Learning and Auction Design". In: A.M 67.5 (Sept. 2020).
[Fre+97]
Yoav Freund, Robert Schapire, Yoram Singer, and Manfred K Warmuth. "Using and combining predictors that specialize", In: Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing. 1997, pp. 334-343.
[GKR22]
Ira Globus-Harris, Michael Kearns, and Aaron Roth. "An Algorithmic Framework for Bias Bounties". In: Pruceedings of the 2022 ACM Conference Fairness, Accountabil- ity, and Transparency. FAccT '22. New York, NY, USA: Association for Computing Machinery, June 2022, pp. 1106-1124.
[Glo+23] Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. "Multicalibration as boosting for regression". In: Proceedings of the 40th International Conference on Machine Learning. ICML'23. JMLR.org. 2023.
[GSV14] Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. "A second-order bound with excess losses". In: Conference on Learning Theory. PMLR. 2014, pp. 176-196.
[Hag+22]
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. "Oracle-efficient online learning for smoothed adversaries". In: Advances in Newral Information Processing Systems 35 (2022), pp. 4072-4084.
[Haz22]
Elad Hazan. Introduction to Online Convex Optimization. 2nd ed. MIT Press, Sept. 2022. Ursula ficbert-Johnson Michael Kim, Omer Reingold, and Guy Rothblum. "Multicali- bration: Calibration for the (Computationally -ddntfiiiie Masses". In: Proceedings of the 35th International Conference on Machine Learning. PMLR, July 2018, pp. 1939-
[Heb+18]
1948.

---

[HJ224]
Nika Haghtalab, Michael Jordan, and Eric Zhao. "A unifying perspective on multi- calibration: Game dynamics for multi-objective learning". In: Advances in Neural Infor- mation Processing Systems 36 (2024).
[HK16]
Elad Hazan and Tomer Koren. "The computational power of optimization in online learning". In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. STOC '1.. New York, NY, USA: Association for Computing Machinery, June 2016, pp. 128-141.
[HPO5]
Marcus Hutter and Jan Poland. "Adaptive Online Prediction by Following the Perturbed Leader". In: Journal of Machine Learning Research 6.22 (2005), pp. 639-660. Nika Haghtalab, Chara Podimata, and Kunhe Yang. "Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents". In: Advances in Neural Information Processing Systems 36 (Dec. 2023), pp. 61645-61677.
[HPY23]
[HRS22) Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. "Smoothed Analysis with Adaptive Adversaries". In: 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Feb. 2022, pp. 942 953.
[8ea+18] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. "Preventing fairness ger- rymandering: Auditing and learning for subgroup fairness". In: International conference on machine learning. PMLR. 2018, pp. 2564-2572
[KGZ19]
Michael P Kim, Amirata Ghorbani, and James Zou. "Multiaccuracy: Black-box post- processing for fairness in classification". In: Proceedings of the 2019 AAAI/ACM Con- ference on AI, Ethics, and Society. 2019, pp. 247-254.
[KK05]
Sham Kakade and Adam Tauman Kalai. "From Batch to Transductive Online Learning". In: Advances in Neural Information P Processing Systems. Vol. 18. MIT Press, 2005. Adam Kalai and Santosh Vempala. "Efficient algorithms for online decision problems". In: Journal of Computer and System Sciences 71.3 (Oct. 2005), pp. 291-307.
[KV05]
[Lee+22]
Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. "Online minimax multiob- jective optimization: Multicalibeating and other applications". In: Advances in Newral Information Processing Systems 35 (2022), pp. 29051-29063
[LS15]
Haipeng Luo and Robert E Schapire. "Achieving all with no parameters: Adanormal- hedge". In: Conference on Leurning Theory. PMLR. 2015, pp. 1286-1304. B. K. Natarajan. "On learning sets and functions". In: Machine Learning 4.1 (Oct. 1989),
[Nat89]
pp. 67-97.
[NMR44]
John von Neumann, Oskar Morgenstern, and Ariel Rubinstein. Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition). Princeton University Press, 1944.
[Oak+20]
Luke Oakden- Rayner. Jared Dunnmon, Gustavo Carneiro, and Christopher Ré. "Hidden stratification causes clinically meaningful failures in machine learning for medical imaging". In: Proceedings of the ACM conference on health, inference, and learning. 2020, pp. 151-159.
[RST11] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. "Online Learning: Stochastic, Constrained, and Smoothed Adversaries". In: Advances in Neural Information Process- ing Systems. Vol. 24. Curran Associates, Inc., 2011.
[RY21] Guy N. Rothblum and Gal Yona. "Multi-group Agnostic PAC Learnability". In: Pro- ceedings of the 38th International Conference on Machine Learning. PMLR, July 2021, pp. 9107-9115
[Sag+20]
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. "Distribution- ally robust neural networks for group shifts: On the importance of regularizat ion for worst-case generalization". In: International Conference on Learning Representations. 2020.
[SKS16]
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire, "Efficient Algorithms for Adversarial Contextual Learning". In: Proceedings of The 33rd International Con- ference on Machine Learning. Ed. by Maria Florina Balcan and Kilian Q. Weinberger. Vol. 48. Proceedings of Machine Learning Research. New York, New York, USA: PMLR, June 2016, pp. 2159-2168
[TH22)
Christopher J. Tosh and Daniel Hsu. "Simple and near-optimal algorithms for hid- den stratification and multi-group learning". In: Proceedings of the 39th International Conference on Machine Learning. PMLR, June 2022, pp. 21633-21657.
12

---

[Wan+22]
Guanghui Wang, Zihao Hu, Vidya Muthukumar, and Jacob D. Abernethy. "Adaptive Online Learning.. In: Advances in Neural Information Processing Systems 35 (Dec. 2022), pp. 23398-23411
13

---

A Proof of Theorem 3.2
The goal is to prove that ONLINE LISTUPDATE satisfies, for all y E g.
[egg, (H, g)] s ((dlog + VdT
Fix any E G. For each h E H. define
T
Regr (h.9) = Σ ((t))))( v1)).
By linearity of expectation, Theorem 3.1 and an elementary integral bound,
Reegr (h, 9)] =
Σ Rlg( (()e.))) (eii))BBg((((((() B)g(x:))(((((r)..)))))
T
<
$14 +
P(a) (B(e((e(Te)) vi) x E - ([g((z))((h()))) yr) xx E g))
((thogg 1) ( (
1/3
11
Σ
61-
-
1-1
1=2
= =1+0
(dlogg (0g(1/ +88)
Plug-in ò 1/TT to obtain
E[Regy (h, 0 ((11gg))1/371113
It remains to relate maxseH (h, g)] to Reg, (H, (), Define
hg arg min ((c)))=)ll(())((((())))))))))))) and hg E arg min hCH
mig kEH
Σ
g(aa (( ve).
Then
E (?1.g) = max B (h, 9)] E
Σ ((1)))(()( - e(hg(
kcH
Since H has VC dimension at most d, standard uniform convergence argument implies
Σ (((x))((()))...) un))
s svVTTlog
E
max TE (B NEW
Using the definitions hy and hgs we obtain
T
Σ (lx)))((h, -() < <
E
Therefore, we conclude that
E E[gg, (H, < (d + /dT /dTlogg]
This finishes the proof of Theorem 3.2
14

---

B Proof of Main Theorem 4.1
In this section, prove the multi-group regret guarantee of our main algorithm, Algorithm To restate the theorem, we aim to show, for all E g
dT log T
E[ (H. So
+ at'
More explicitly, we aim to show that:
(
T log?
Elg(zr) (e(he(aze) - (x,h 0o
+ aT
where ht E minnew E ((xa))( v.). We follow generalization of the online minimax multiobjective optimization framework of Lee+22), with techniques inspired by [HPY23)
B.1 The AMF Algorithm Framework
We first restate their "adversary- moveny--moo-iiiii wirstssssst"t AMF algorithm of [Lee+22] and its main regret guarantee for convenience, as we will need adapt and generalize it to our setting. Let Ar denote a general action space of the learner, and let 2, denote the general action space of the adversary
round
t [T]. In full generality, A, and 2, are allowed to change with the rounds E [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 multiobjectiive online optimization problem:
1. The adversary selects a continuous, d-dimensional loss function :A, x 2, + [-1, 1] Each component r A,, Z, [-1, is convex in A, and concave in Z..
2. The learner selects an action a, Ar.
3. Nature observes the learner's action a, and responds with 2; E 2,.
4. The learner incurs the d-dimensional loss ri (a 24)
In this setting, the learner's goal is to minimize the value of the maximum dimension of the accumu- lated loss vector after T rounds:
T
(ar, 22).
max JELN
To benchmark the learner's performance, we consider the following quantity, which we refer to as adversary-moves-ffee (AMF) value ul round I.
Definition B.1 (Adversary-Moves-Teee -iiss-FFittttt (AMF) Value at Round L. Lee++2)) )) The adversary-moves-
first (AMF) value at round & the value:
A = max min
maxx rf (ax, (/ (2)
2.2, a.EA.
jE[d]
We conceive of the value via in (6) as the aspirational smallest value of the maximium coordinate of the learner could guarantee if the adversary had to reveal first and the learner could best respond with a, Per how the multiobjective online optimization problem is set up, however, the opposite is true --tht the learner must commit to action a; E Ar first, and then the adversary is allowed to play 2, E Zg in response to maximize the learner's misfortune. Regardless, we can define a notion of regret with respect this particular benchmark.
Definition B.2 Adversary-Moves- (AMF) Regret). Over T rounds of the above multiobjective online optimization problem, the adversary-moves-fine first regret of the learner is:
AMFRegr
max JE(4]
Σ (a), 2x) vi vtt)
This notion measures the cumulative regret the learner for not playing the action ar E A, achieving the aspirational value o/ at round over all coordinates of the loss vector.
15

---

Algorithm 2 AMF Algorithm of [Lee+22]
1: for 1,2,3..... ...,, T do Receive adversarially chosen action spaces A, and 2, and the d-dimensional loss function
2:
A, x 2 [-1
3: Let
exp
1) - (as, (a)
of
for j E [d].
Eielq exp
(1) D rg (as
For f 1, let of = 1/d for all j E [d]. 4: Solve the min-max optimization problem:
ag arg min max aEAr 2E2; jEId
Σ (r,
(7)
5: Commit to the action a, E Ar, observe Nature's choice 24 Ze, and incur loss re(ae, 21).
6: end for
A natural question, then, is wonder if such regret can be made to diminish sublinearly, That is, does there exist an algorithm such that AMFRegr S o(T)? Lee+22 answer this the affirmative, presenting Algorithm 2
not immediately clear first glance how Algorithm translates our multi-group online learning setting. In the next section, we will show reduction from our setting to the this AMF framework. We will specialize Algorithm 2 our setting and prove a "meta-theoremm similar to the original guarantee of Algorithm and proceed to control the regret via that meta-theorem in subsequent sections.
B.2 Reduction of multi-group online learning to AMF Framework
Recall that, in this paper, we actually care about the online multi-gron learning setting described in Section 2.2 We restate the objective here for convenience.
In multiugggoooo group online learning, the learner has access to hypothesis class H. taking contexts from X' and outputting actions in V, common action space for the learner and Nature. There is common loss function for the problem, E(:,)) y x 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 one another, so we just "the learner:" For clarity of exposition, let y = 1-1,1} be a binary action space for the remainder of Appendix B The generalization to the case where y takes K discrete values sketched Appendix C
We consider the regret of the learner on subsequences rounds E [T] : at E g) defined by the groups g G and the sequence of contexts ,1,-..,2yT. Specifically, the (multi-group)) regret of the learner on group g is
Regr (H = Σ Egrr))(( - min Σ (())))
AER 1=1
Crucially, the best hypothesis for one group may differ from that of another group. The learner seeks to achieve achieve sublinear expected regret, all groups g E & 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.I An important observation is that, when y = (-1, 1}. varying lú, E H only affects the regret at round / [T] insofar as its behavior on & That is, for a fixed x, X' and E V, ((h,(z)) 2) {f(-1, ((I, v)). Note that it is possible for the set {h(x;) E H} C y to be a singleton set, in which case the learner will always take this unique action.
Let As, the learner's action space for round t [T] in Section B.1 be the simplex A()).
16

---

Let 2,, the adversary's 's action space in Section B.1 be 2, = [0 for all E [T], which will correspond the parameter of a Bernoulli distribution over the binary-valued action space of Nature in the multi-group online learning problem.
Let r: A x 2 + |-1, 112 the adversarially chosen loss function, be 9 x H-dimensional, with each coordinate corresponding a pair hg E 9 x H. Consider any p. E [0. 1], each determining a Bernoulli distribution over y = 1-1,1. As in Section 4.2 for any x: E 2':
hi, (v',8)) == 3(x) (((''v) --((())))))
Then, define:
(g)h) rt (p: == Buy.
E2, ((ā, h), (v/ w/)
Above, the loss ((:-)) is the fixed loss of the multi-group online learning problem, and xy E X' is the context chosen by Nature at round I, which indexes fz-
may now be slightly clearer how Algorithm | maps to Algorithm but we provide a high-level overview here prepare the reader for the subsequent sections.
The distribution E A A|d in Line 3 of Algorithm corresponds to the implicit distribution
formed by querying OPT (G.H) M times to generate { (ū: M i.e. the (g, -llpayer..
Solving the min-max optimization problem in Line 4 Equation (7) of Algorithm corresponds to the two calls to the simple optimization problem solved by the Hl-player and solving the simple oinedimnnsi linear program in L Algorithm
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 qt, and the H-player and Equation 7 in Algorithm] 2
B.3 Instantiations of the OPT (G.H) oracle (G.H)
The computational primitive our algorithm assumes access to is a (G, oppoimiiznnnionn oracle, defined Definition 2.2, and requoted here for ease reference.
Definition B.3 ((,, H))ootiimzzttion oracle). Fix an error parameter 2 O. For collection
of groups g E 2* a collection of hypotheses H. S y and a sequence of m loss functions 4 (f0, x] x (>' x )) 1-1,11 an a-approximate (g, -optmiiiizaaoonnn oracle OPT
an a-approximation optimization oracle (Definition 2.1 that outputs pair (g.h) h) E G x H satisfying:
(,l,((((z)) (vi, v()) 2
sup
(xx() (xx),, (Vi, v(2) a. (10)
(0 h E9
common assumption in the literature oracle-efficient online learning is positing the existence of some reasonable optimization oracle, typically commensurate to the ability to solve ERM. Although is well-known that ERM computationally hard in the worst-case, 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 this oracle black-box, it natural to wonder such an oracle can be instantiated. [GKR22] gives two such instantiations which we quote here for completeness.
We consider the specific instantiation of the (9, Ho-oralle in Algorithm 1 for a specific round E [T].
which aims to solve the following optimization problem for some (ğt, hr) E G x H:
Σ (as)) (E(U.. Mo) -(h, (.)) > OPT a,
(11)
where OPT := sup, _ (G.HH) Ei=lg 9d (x.) (E()., Us) - E(h; (x.).
In both instantiations the oracle in GKR22 , the oracle aims to find a (g, h) E (G, H) competitive to some reference model. f X {0, lj. For simplicity, as in the main body, assume that
17

---

(0,1), 1.. and the "reference model" we compete with is given by the Learner's history of actions up round t: (x) .1.................... ........... (1 Dr 1). That is, we compare with the function X {0, that maps f(x,) = Us for all 8 =
1
Reduction to ternary classification. The first instantiation of (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 of ternary valued functions p X - [0, For each E K, define the p-derived group and p-derived hypothesis
(x = {
if p(x) E (0,1) if p(z) =?
1p(x)= -(0))((0)) p(x) E (0, 1) p(z) =?
[p(x)
This class induces a set of pairs (gp. hyp) and product class (9, H)x == {(gp. hp) :p E K). We may define cost-sensitive classification problem over K. as follows, given existing model f: + 10. with the following costs:
i
if if f(x) =
(,(((,)))2) =
y f(x)
0
otherwise
For any distribution over X' x {0, 1}. the associated cost-sensitive classification problem for costs of v) defined above is:
p² E arg min E(z.)) (())))
(12)
PEK
Many efficient algorithms that heuristically solve such optimization problems exist.
The main theorem from GKR22 restated here, the following:
Theorem B.1. Fix any arbitrary distribution μ over X x {0,1}, Let K. be class of termar-vvaludd
functions p= X - (0, 1, and let f - {0, 13 be any binary-valued model. Let p be the solution to the cost-sensitive classification problem in Equation (12. Then,
hg) E arg E(ma))= [9(x)) (e(f(1), v) e(h(z).))).
(g.))E(S,HH)c
When p is the empirical distribution over F1.... Tt 1, the solution (gp, h()) forms solution the optimization problem in Equation 11) when (G, H)x
H.
We refer the reader to Section 4.2 GKR22] for a proof.
Reduction to alternating maximization. Another instantiation of the (g. -o-oracle in GKR22 is an alternating maximization approach. The reduction ternary classification quoted above relies on an oracle for the class K. and supplies guarantees for the derived class (G, H) However, if we wish begin with G x H. we can take an "FM-style" alternating maximization approach that only requires ERM oracles for G and H separately. This approach only guarantees saddle point local optimum.
The main idea is that, by holding fixed and solving for h², and vice versa, the following optimization problems are harder than ERM over and H individually:
arg max E (e (x) (E("(x),)) v) E(h(o),
(13)
EG
h" E arg max E (g(x)) (E((()).)) (x)" v))]
(14)
bER
In Equation [13). h is fixed and solve for g"; in Equation (4p. y is fixed, and solve for ht. With appropriate modifications to the distribution j we can construct ERM problems for g" and
h" comensurate 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) E G H that gives local optimum Equation (TT) in Algorithm The corresponding theorem, restated from [KR222 is:
18

---

Theorem B.2. L O. Fix any empirical distribution over (21.31)..... (Im. let f X + (0, 13 be an arbitrary model, and let G and H be arbitrary group and hypothesis classes. After solving at most 2/c ERM problems over each of 9 and H (in Equations (3) and (14). respectively), Algorithm 3 returns a pair (g" hC) with the properties that:
1. For every h H.
(z. (e(f(z:),)) E(h(z:). 2
g (2.) (e(f(z)). (x:" ((())))))))))((())))))) te.
i=1
2. For every E EG.
m
g(a;) (((f(r:), ((10(1))))))))))))))))))())) v)) (x:) (e(f(())))))) e +
Algorithm 3 Alternating Maximization for 9 x H Oracle
Input:
Dataset {3 yi 1 model f : {0, 1}, error parameter
1: Initialize (g", h²) E G x H arbitrarily.
2: Let
VAL =
Σ g" u))
3: Use ERM oracle for Equations
13 and
(14 solve for:
g E arg max DEG
g(x) ((11))))))))((()))))))))))))))))
m
h" E arg max BEH
9 (x)) (E((())) -(((x).))))
4: while D 0d (x) (E(((2))) - e(h (x), 2 VAL
5: Let
VAL
Σ
g (x.) (C(f())), u.)) e(h"
1=1
6: Use ERM oracle for Equations
13 and
14 to solve for:
9"
E arg max
-(( (())))))))
gEg
h arg max
(x)) ([(f()).)) E(h(x),))) ((((()))))
KCH
7: end while 8: Return (g", E
We believe that it is an interesting and worthwhile open question to develop more specific instantia- tions of this (G, -o-oracle for more specific problem settings that are computationally efficient and have provable optimization guarantees.
B.4 The group-hypothesis and hypothesis players
We formally define how the (G, Hl-player corresponds to the weights q: E A Aid in Algorithm 2 The crucial observation here is that the perturbations of the FTPL algorithm of [Bl++22] used in our setting form implicit distribution over H that can be approximated by calling the OPT. oracle M times.
In the proceeding sections, we denote Ag x H) as the (possibly infiite-diimenioonal) space of measures over the functions G H. However, will always only access sparse distributions this
19

---

space, with a finite number of hg. pairs in 9 x H. obtaining nonzero mass. The following definition should make this clear.
Definition B.4 (The distribution of the (G, H)-player). For any round [T], let { h.) i=1 be the M samples drawn from querying OPT 20) in Algorithm 7 Let the empirical distribution Tt. E Ag x H) be the distribution of the (9, -llyye at round I.
It is easy see that dr is valid distribution over (9, H), with measure over A C H. defined by:
PM (A) M Σ k.. (A),
where (g. is the Dirac measure of (ūs, h2)) falling into the set A. The stochasticity of (gt, h&) is over the random perturbations described in Section 4.2 Equation ( Equipped with this definition,
can take empirical expectations over E A(g H) in the usual way. Observe that, in Algorithm Equation (7). the optimization problem at round f, is equivalent to:
Gg arg min max E firqs [r((a,2)] aEA
2E2
Because the d objectives in reduction (Section B.2 correspond to each group-hypothesis pair (g. h) E 9 x H. A, corresponds to A(),, and 2, a always corresponds to [o, 1], we can equivalently consider the min-mat min-max optimization problem at round t [T]:
[ ( (p,7))
Pt E arg min max E (g.h))a pεA()) 7E[0,1]
(15)
where (ā.h) is defined in Equation The next lemma relates the optimization procedure of the H-player in Algorithm To the min-max optimization procedure of Equation (7) in Algorithm
Lemma B.3 (The optimization of the H-player). For any round I E [T), let (āi, 1 denote the M samples obtained by calling OPT(G. M times in Algorithml 7 and denote E A(g H) denote the corresponding empirical distribution (Definition B.4). Then, Pt A()) defined in
Equation (15) above is equivalent to the distribution (p, 1 p) E ( (1-1,1) obtained from solving the linear program of the H-player in Algorithm
Proof. Consider any round [T]. Observe that Line of Algorithm 1 is equivalent to solving the linear program for À E R and = (p, 1 p) E R
min
s.t. Σp:=1 =1
Le, S A Vi [2]
p. 2 ViE [2]
where the payoff matrix L. E [-1, has the coordinates (y',
1 M
L m) =
La (Go (.. ()).)))
M
i=1
and e; is the ith coordinate vector of RR2 Let A())) denote the space of probability distributions over
y. Let p- = (p. 1 p) and = (7, 7), and, as shorthand, denote p(-1) = 1 P. p(1) = p.
x(-1) = 1 - 7, and x(1) 7.
20

---

By the equivalence of linear programs (LPs) to zum min max games (see, e.g., obtaining the optimal p for this LP is the equivalent to solving:
BT97 Haz22
min p 1== min pEA()) =EA())
1 EEEΣ
p P( (, (0')),)))))))
PEAO) xED(V) M VEY D'EE'EYE
min max PEA()) =EA())
Σ Σ
p()')=()) (()
(g.h)mme (e.((o,)) (v/ [/)]
yCy V'E
min max By Bar(1) [ (m. (v', (v'. PEA()) #EA())
min max By' Ber (Bre.i)ma [en (GG hi, (v's
pEA()) TE
( (0.,)) ( (p:
min max E (a, (E
Above, the first equality just comes from definition of L. the second equality is from the Definition of the empirical distribution q. the third and fourth equalities are from the definition of p and in the previous paragraph. The final equality is just from interchanging the order of expectation and
the definition of r (().)) (p. 7) 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 pe in Equation [5)
Lemma B.3 tells us that the strategy of the H-player (i.e., Lines 8 and 9 in Algorithm 1 to obtain he exactly the same as obtaining the minimizing Pt in Equation T.).. From the exposition above, this corresponds to the min-max optimization problem in Equation 7 when g: is qt, the distribution over H. We now proceed to prove a more general "meta-theorem" from which the regret guarantee of Algorithm will follow once we plug in specific FTPL algorithm for the (G, H) -llyayyer.
B.5
Meta-algorithm for Online Multi-group Learning
We now present meta-algorithm, Algorithm 4 and its corresponding Theorem B.4 the "meta- theorem" for online multi-group learning from which Theorem 4. follows. This is more general, however, than the guarantee in Theorem 4.1 and we emphasize that, through changing the no-regret algorithm for the (g, H))-layer, we can obtain regret guarantees for settings other than the smoothed online learning setting of Theorem 4.1 Section gives couple of examples, which we elaborate in Appendix C
Note that approximating the distribution of the (G, Hl-player is crucial to obtain computational efficiency, as we cannot hope to enumerate G and H by explicitly representing & in Algorithm 4 Thus, sampling M times
crucial "sparsification" step that allows us to implicitly access the distribution over G x H. that the (G, H.)-plyeer maintains.
We prove Theorem B.4 through techniques similar the regret guarantee proof of Algorithm in [ee+22). Namely, we observe that by using the reduction outlined in Section B.2 with the 7-ddimensional loss
( ((((zz), Tt (p.7) En Ber-)) ((x.)) )
(2.8)
-p Eyy Bor(y) (h)z.))
may obtain bound the multi-group regret of our Algorithm by obtaining adversary- moves-firee first regret guarantee (Definition B.2). For simplicity, we prove this for the case of binary actions y {-1,1}; outline how to obtain similar theorem for multi-class action spaces in Appendix
Theorem B.4 Seeta-Theorem for Online Multi Multi-group Learning). Let X be a context space, ler ) [-1, be binary action space, and let H be a hypothesis class functions h: X - Y, and lei be a collection of groups, x - {0, 1). Let E: y y + [0, 1] be a bounded loss function. Suppose the (g, Hlyylyyer of Algorithm 4 instantiated with no-regret (maximization) algorithm operating over H G that has the guarantee that for any sequence of losses of length T bounded in [-1, 11, by playing (a possibly implicit distribution) qr. it has regret at most R(T) in expectation.
21

---

Algorithm 4 Meta-algorithm for Online Multi-group Learning (0' - (-1,1))
Input: M N, the number of samples take from q at each step.
I: fort= = 2, ... ......TT do
2: Receive a context æ; from Nature.
3: For any 1/ ) construct the loss:
ex (G. h). (v' v)) = 5(1)) (ew''u) - e(h((z))v))
4: (G, H)-player: With access the entire history of the past t rounds and zt, with access OPT (G.1)- run a no-regret algorithm over the benchmark class G x H to output distribution E A(g x H).
5: Construct an empirical approximation d of qe by sampling from ge M times, obtaining
collection of pairs {(At') (1) (*)) ) from G x H.
6: H--layer: Call OPTx twice on the singleton datasets {(re. -1) and {(T,, 1)} with the 0-1 loss, obtaining:
h1 E arg min 1 (1x) + 13,
M-1 E arg arg min (xx) # -1}.
EEEH
K*
7: H-player: Solve the linear program
min P.E
M Σ pêz, ((Tt A(O),, (M(())) + p)é,, ((Tl)) (1 ((12(()), w)) SA
subj. to
1=1
Vy E {-1,1}
0SPSI.
8: Sample Ber(p), where E (-1,1), let h4 = h²g
9: Learner commits to the action ÿt = (xx); Nature reveals Ve-
Learner incurs loss E()t, yt)-
11: The (G, H)-player draws (g, h) ~ qe and incurs the loss Eu, ((g, h), (Dc. vt)).
12:
end for
Then, with expectation over any randomness of the (9, Hlyplyyer and Nature, Algorithm 7 obbaain the multi-group regret guarantee of:
E[Reg, (H, <
11 +
[M)((M)]++(()
(16)
for all g E G, where
2i == max min
max (E,0.11 (EE)(H) (
Ehepp.
()(=:) -(h(x)).)))))
(17)
and (M) is the error incurred from estimating with qe with M samples at step t E [2].
Proof. From the perspective of the (G, H)-player, who is running regret maximization algorithm, the following game is being played. For t =
Receive a context E X from Nature, possibly adversarially and depending the past 1 rounds.
Play pair (Te, Tt) E H x G. possibly randomly and dependent on the last / - rounds, where pairs are functions
(h, : X y (0, 1)
Commit to the action 5r := (f.()x)) 10.
22

---

An adversary (the H--paaye's prediction and Nature) reveals (bt: vo) E V x V. and we incur the loss:
E((g, hi,, (Dc, 9t)) = g(ze) (else. Ue)
Here, dr = hxx))), which is a random variable depending on sampling from pt, the Bernoulli distribution of the H-player round t.
Note that the (G, H)-player is attempting to maximize this loss.
Let h, be the sequence of hypotheses chosen by the H-player, and let y/,..... yr 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") E H. x G:
Σ EE "(ll",h") (ho((z), u.)]]
EB Bon [e(lr, he), (he(2s), wd)] R(T),
where the expectation is over the distributions 9. over A(H x 9) 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, a random variable throughout. For instance, in the case of Theorem 4.1 this is random process determined by the (G, H)-player sampling n perturbation terms and calling the (G, Ho-oracle to obtain the random variable (ğe, he). Instantiating the regret bound for all (h", ."") gives us:
keep the subscript in the expectation over h hidden, noting that ha(r))) p
T
Σ
((lo",")) (he(2e)) vc)) S
Σ (en [CCCE, (i),,,h),
ha), (he vc)) + R(T).
max (h* EEXX
However, we do not have direct access to gt. the implicit distribution over 9 x H. but we have an approximation qt. In Algorithm 2 (g., hu) is drawn according to q.. the empirical distribution over A(H x G) formed by drawing M samples {(h,) (8) _o. J from d-- Fixing Ft, V/s and h, (22), let (M) be the error we incur from replacing the true distribution qe by the empirical distribution q-
which we can handle through uniform convergence the samples {(hb)) ((i) 1M
Jim1 (see Lemma B.6)
E (y (é(()) R), (Ie())e), vx)) Egghh (,((,, h), (Nr()))) mt)I|| s (M(M).
Adding the estimation error at each e [T]. our regret bound becomes:
T E
T
E((o", h²), (he(2:), vii)| S
E Feg [(((o,,h)) he), (he(zz), vi)) + R(T)
max (h+ (E)
1=1
B he. [((Grr he), (he ve))) + Σ (x(M) + R(T).
At round & [7'. Algorithm 4 chooses the best response h2 E H. by solving linear program for a Bernoulli parameter p and then sampling/ h from Ber(p). This is equivalent to sampling he ~ Pt. where p. := (p. 1 p) on
Now, we aim to bound the terms ( R.) [( RT), (ho(#e), (.)))) vt))
A())). We use sampling from this Bernoulli distribution and sampling from pt interchangeably. By
Lemma B.3
this is equivalent to solving the min-max optimization problem in Equation (15)
[ (r (p.7))
Pt. E arg min max E Ko) pEA()) 7E(0.1)
which, by definition of (g.h) (p. y). is equivalent to:
Pc E arg min max E. Te Fn(((e))p Ey-Ber(()) (xx) (e(h(())),)) (((((())))))((((ttt))))))))
p.EA()) rE(0.1
(18)
The inner expectations are linear in Pt and 7, and taking the outer expectation over qr maintains linearity. Therefore, this is convex and concave min-max optimization problem, and von Neumann's
23

---

minimax theorem NMR44 Therefore
applies, allowing us to swap the order of minimization and maximization.
min max E (1).h.)~p) ~ Bn. E Bar(()))) (ā.(ar)) (e(h,(ar)) v) (aap))))-((hhhhe (()((())))))) (rEA()) YE 001)
((h,
= max min TE (E)())
E ( ((ar.i)aa
Eh Bar(y) (T(((e)) (e(he(ze): - ((h((z))
S max TE (g.A)Eg*H
min max
(((x))
- ((((())))))) =
where the first equality from the minimax theorem and the second inequality is just because averages are less than or equal to maximums. Combining all the inequalities, we obtain
max 99 J
Σ ECCo" (a.(2)). S
+
and our theorem follows from taking an expectation on both sides and substituting back the definition of
E((o" h²), (h(())) u.)) == (2x) (e(h(2)), u.) - e(h [x+))
because each (((g", h,), (h(2)), vx)) is simply the per-round regret.
With Theorem 4.4m in hand, it remains to make sure that the two terms Σ of and Σ (M)) are both (T)) Then, if we have a no-regret algorithm with o(T) regret while only accessing 9 and H. through the (G.()) oracle, we will have multi-group online learning algorithm. The next two lemmas show that both terms are, indeed, o(T).
First, we bound the values v/A, which are known as the "AMF values" in the framework of Lee+22 Lemma B.S. For any t [T], the AMF value of the game round is nonpositive, i.e.
max min max (lg(s))((((h(<))))v))))))))) ((h(x:)))))) < 0, PE (h.g)ENG
where the expectation is taken over ha Pr. and y Ber(7).
Proof. Fix any parameter y E [0, 1] for the max player. Then, for any (h, g) E H x g,
E ((g()))((((h(()))))))) v) e(h(zz), v)) -i-h,
+ (1 (1-11)
-1)()((()))))))) -1)1 -1)]
Expanding the expectation over he Pt. this is equivalent to:
g(xe) Σ (T (1-7) (10raa/00000000aoe000(0000000000
MEH
so it suffices to find Pt E AHH) such that, for all (h,g) E x G.
g(xx)
phe(( (x:), 1) (1-7)((M(()), 0)) < ((=x))((((((xz)))) (
NEW
The g(z,) value is the same for both sides, so it really suffices to find the pe A(H) such that, for all E H.
Plo()e(N( (1->))(())))))
S >e(h(=)))))))) (1 (1)))))(()))))))
Because we know 7, the Bernoulli parameter for the true distribution of y | xt, we can choose pd E A(H) to put all its mass on the h² E H that minimizes this risk, i.e.
h E arg min Ryy KEH
y) xz)-
This is, by definition, exactly the h²* such that, for any H.
(l(h" + (1 ()((h((x))) -1) 7((h(z)), 1) + (1 -))(((())))))
24

---

Therefore, we have that:
max min max 7E PHEA(H) (
((((2)))))))
E (x= (x))))))))) ((((()))))))
max
0.
The final inequality follows from our argument above.
Next, bound the expected approximation error incur from replacing de with the empirical distribution & obtained from the M samples {(g Hr ( M
fi=ls which we denoted as (M). This
comes from standard uniform convergence argument.
Lemma B.6. Let & E (T) and xt E X be fixed, and consider the function Êx, ((g, h), (v', v)) g(xx)( v) ((h(z)).)), y)). Let | = k < 0o. If M T1 where S2 log(log T + k)) ), then
log T
1 over the randomness of drawing M samples {(g.)) h4 13=1 to construct the empirical distribution described in Definition B.4 for all y' V. let e (M) be defined as the supremum
(M)
sup (s/ x
B Cn ((o, h), (v' w))l (e Ka (1),),, h), (v/ v))1
and, over all T rounds,
E
(M)
22VT.
Proof. Fix any round E [T]. We use a standard uniform convergence argument to ensure that the empirical distribution é and the true distribution q: are close for the function &x, ((g, h), (y', .)) for all y', y E V. We assume that Y is finite, and denote A := (//.
Let ((gt (4) A(()) ) denote the M random samples from & x H. We note that the expectation over is the same as:
M
E (a.by~
[((o, (o',
1 M
Σ i=1
(0
T(0) (1/.)))))))
1(0
Consider the empirical process
M M Σ to.
( (()). (V/ v)) - 1Egg [((g,))) (v',
sup (y' x
2.(0'.0)
For notational simplicity. let us refer to this empirical process as:
M Z(V. =M(M).
1
sup (v' x)
M
1=1
Because : E [0, 1J. we know غ E [-1, 1]. Moreover, ||/2| = k2, We can now use Hoeffding's inequality and union bound to obtain:
M
sup E)
1 M
Σ
Zil
26
< 22
S 22 (2exp((22 -272622
1=1
25

---

By the elementary integral inequality E[X] - r P[X 2 tldt, we obtain:
M
M Z.(y', y)
1
sup (0)=
Σ i=1
Zo (v'' y)
P
sup
2 dt
M
00
(V''
Y=1
M
0c
sup
Zi .3)
2 t dt +
k2 exp( exp(-221++ (
0
(1'3))
M
==1
k² exp( - 22 (
10
$ w k2a exp(- -200-22 w²²)
where w >> is an arbitrary parameter. Set w = V / Ir
loge (og((A) log(T)
then:
2og
E
sup wEE?
M Σ Zlv' v)
Blee(MM s 2 \
Therefore, summing up all T rounds, obtain E/ B[c( s 2VT..
B.6 Instantiating the meta-algorithm for Theorem 4.1
Finally, we instantiate Theorem B.4 with a concrete no-regret algorithm for the (9, H Hllplye to obtain Theorem 4.1 We employ the specific no-regret algorithm of [Bo++22] for our (G, H.) H.)-player, restated here for reference.
Theorem B.7 (Smoothed FTPL of Blo+22)), Let F
x be a function class and let i be loss function that is L-Lipscchitz in both arguments. Suppose further that we are in the smoothed online learning setting (see Section where each x; are drawn from a distribution that a-smooth with respect of some base measure B on X. Let
12
(f) ==) Σ
where 21,3 are independent and the "r are independent standard Gaussian variables. Suppose that 2 0 and consider the algorithm which uses a-approximate oracle for F (see Definition
2.1 to choose ft according to
1-1
((e((s)) + (ft) S inf (ar))))) + (T,) + a,
EE a=l
and let Dr = fe(x)) F and are binary valued, with the VC dimension of F. bounded by d 2 1, then for T/ /a and n / L//(T
(v do' OT
E. Regr (fo) SC
(f
where C' > 0 is some absolute constant.
This is precisely what the (G, H--player does in Algorithm Let == C : 9} be collection of groups, represented Boolean functions g X - 10, Let 7/ be hypothesis
class of binary-valued functions : X' + (11,1}. To be clear, the we map Theorem B.7 to our
Algorithm inn the following way:
Let J of Theorem B.7 be the class of functions in [-1, defined by:
F (i ((=)(())) : G, H).
Note that each F maps (,10
26

---

Let the loss function in Theorem B.7 be the loss of the (G, H.- player on &:
E(( h), (l(x). v) = ū(x) (e(h(z)) - ((h(x).u))
In terms of F above, we can rewrite this as:
0 (ly' ((-1,y)
ffr = =0 f() -1 if f(x) =
(ff())
(()''.) ((1.))
This loss function has the signature E: (-1,0,1, [-1, 1-1, because E(.,)) )) E [0, 1].
It is also 2-1 2-L.ischitz both arguments.
It remains to make sure that ternary-valued functions taking values in (,1,0, do not break the proof of Theorem B.7 In the proof of Theorem [B.7 [Blo+22]. , the binary-valued function case where f has range { 1 1. 1] is handled by embedding 1 into the real line. There are two main parts of the proof that rely on this assumption that has range {-1,1} that easily maintain
when f has range 0,)
First, in Lemma 34 of [Bo++22, the authors L--Lipcchitzess and the simple fact that [f(x) - (x)) < (f(z) [x)) when f E 111,1}. This still holds when f f-1, 0, 1}. Second, [Blo+22] also use the fact that [[ = 1 for all E F, which is also true for {-,,
Finally, the rest of the proof in Lemma 35 of Blo+22 relies only on the Lipschitzneess of to employ standard smoothness arguments and Rademacher contraction, which we have already established.
Putting all this together, the (9, -P)-layer in Algorithm Jssentially runs the algorithm of B.7 with the caveat that it calls the OPT (G.H) oracle M times to get the empirical approximation q of the true implicit distribution q over 9 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 We now restate Theorem 4.1 Corollary B.7.J with the specified choices of parameters.
be a binary action space, H C (-1, 1)x be vanary hypothesis class, G C 2 be (possibly infinite) collection of groups, and L: (-1,1) 11-1,, + [0, [] be a bounded loss function. Let the VC dimensions of H and G both be bounded by d. Let a 2 0 be the approximation error of the oracle OPT we are log(2 (og(k))))++) 1 log(T))
Corollary B.7.1 (Theorem 4.1 with parameters specified). Let ( (-1,1)
in the a-smooth online learning setting, then, for M > T1+6,6 ,522
T/
2log
and 1)
[Too(T//)
Algorithm achieves, for each g E G:
0
do'log T
E[Regr ER.egr(H. =
+ aT,
where the expectation is over all the randomness of the (g, Hlypyyyrr's perturbations and the H-player's Bernoulli choices.
C Other instantiations of the meta-algorithm
is be clear from the statement Theorem B.4 that our "meta-algorithm"" Algorithm straightfor wardly applies for other online learning settings well, long adopt appropriate strategy for the (G, Hl-ylayer. In this section, we give few examples this flcxibility for discrete action spaces in the smoothed online setting and the
C.1 Multi-class action spaces
Instead of | = 2, we can let | K, more generally. In this case, a straightforward extension of Theorem B.7 allows to embed yu {0, 1} into the real line, and we generalize to considering
27

---

the Natarajan dimension Nat89] of H. instead of the VC dimension. Rademacher contraction and Lipschitzness still apply to f, so with just a difference in the absolute constant, we obtain the following multi-class analogue of Theorem 4. as a corollary. Thus, for the (G, -l)player in Algorithm we can just use the same exact algorithm outlined in Theorem B.7
We make small change the H-player in Algorithm [ In the multi-class action space setting, need to make K calls to the OPTx oracle and solve K x K size linear program for the H-player each step. For completeness, we present the algorithm for the K-class action spaces here, as Algorithm
Algorithm 5 Algorithm for Group Oracle Efficiency (multi-class)
Input: Perturbation strength > O; number of OPT(g.0 calls A E N.
1: for frrt= 1, 2, ...... T do
2: Receive a context 24 N4 from Nature.
3: for = .... .M do
4:
(G, H0)-layer:: Draw hallucinated examples in Equation 4 to construct whin
5:
(9, Hllpyye::: Using the entire history {(D., No)) so far, call OPT to obtain
(1), ((0) E E x satisfying:
bin e. ((ō. hi, (0s, vo)) + Ten (ő, h
Σ La (('"""")) (for + " "0",""""", n) -a (19) (o h J
sup
6: end for
7: H-player: Call OPTH K times on the singleton datasets {(x,, k)} for action k E [K] with
the 0-1 loss, obtaining:
R1 arg min (1* (2r)) {}
ME
8: H player: Using the M samples ((o (1) h
M construct the K x K payoff matrix L
[- 1, 1) K indexed by (hi, y) E [K] [K]:
M
Luy
Ln ((ot A,()), (MA()))
9: H-player: Solve the linear program
min PERA,XER
A
s.t. p Ley SA
Vy [K]
pk 2 0
Wk [K]
Σ Pt P
(where ey the y-th coordinate vector in F
10: Sample k ~ p, let h2 = hig-
Learner commits to the action ÿt (xx);;; Nature reveals yt. 12: Learner incurs the loss E(Ut, Ve).
end for
Theorem C.I. Let y .). be a K-class action space, H C y be a K-valued hypothesis class, G C 2 be a (possibly infinite) collection of groups, and é: y y x y + [0. 1] be bounded loss function. Let the Natarajan dimension (Nat89) of H and the VC dimension of g both be bounded by d. Let 2 0 be the approximation error of the oracle OPT (G. we are in the o-smooth online learning setting, then, for appropriate choices of M E N. N, and 17 0, Algorithm achieves,
28

---

for each G:
(v dI log'T
E[Regr (H, g)) S so
+ aT
where the expectation is over all the randomness of the (G, -lypyaye''s perturbations.
C.2 Group-dependent regret
In this section, we give the details how achieve the desired group-dependent regrer guarantees
of Section 5 Throughout this section, for any g E G, let T. := E g(z)) 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 our meta-algorithm, Algorithm Jusing the GFTPL with small-loss bound algorithm so Theorem B.4 allows 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:
(C, h), (w's v)) gهx) (lly v) ((h(z),))
(20)
where ((:))) is the fixed loss of the entire multi groti online learning setting.
Algorithm 6 GFTPL with small-loss bound
Input: Perturbation matrix E [|111]111
1: Draw i.i.d. vector (L))), ..... (()) ~ Lap(1) i.e., p(x(0) = exp(-lu(()),
2: for / = 1, ...., do
3: Set 14 + &. where 7t >> is parameter computed online.
4: Using the entire history up to so far, call (G.(G.H) to obtain (ğ, h)) E G x sastisying:
Ln, (Cō. h), Uz)) (T(i,)) v))
Σ 22. (0), + (T(t)),,,, m) a. (21)
sup (g N
where ((a.h) is the (ū. b)th row of 5: end for
In our setting, the classical FTPL algorithm of KV05 draws [g] x |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 |||| x N perturbation matrix I to generate dependent "shared randomness." "The transformation I applies to a perturbation vector v E N where is much smaller than | Running FTPL with these perturbations, then, results on an oracle-efficient algorithm. [Wan+22) extends this by showing that, under certain conditions on I, this oracle- efficient algorithm can also achieve 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, small loss regret looks like the following. It is well-known that, in the worst-case, regret of O (VTlog (9 [77]] is minimax optimal CL06). However, stronger bounds have been obtained for problems with "small losses" (see, e.g., HP05 GSV14 LS15),, where, for loss function f (g H) x y- [0, 1], one can achieve:
T f((he, gt), y6) log H||l|
Σ
which is sharper than the O (Tllo log [ bound when f((h,, 0t), y1) < 1 on some rounds.
We desire this property to achieve regret bound in the multi-group online learning setting that sublinear in terms of the number of rounds a group appears Tg
29

---

Following Wan+22], we require the perturbation matrix I' to have two sufficient conditions for Algorithm to obtain the desired small-loss regret. The first is y-approximability which a condition that ensures the stability choices of (ōe, he) and (Øc+1, h+41) across rounds. In particular, the stability needed is a bound on the ratio:
P( h2) = hg.
exp(1me)
Pl hv-1) = (g. h)]
for all (g. h) E g X H. where 7/+ > 0 is the per-round leraning rate of GFTPL. By Lemma of [Wan+22], the following condition is sufficient ensure this property. We restate here, translated to our setting.
Definition C.1 (1-approximability of the noise vector, v in Algorithm
Wan+22 ). Let E [-1.1] x where N is the dimension
Define B == {s e B || S 7}. T is aapppooimmbll if.
for all (g. ht) G x H and (x, y'.
E x y V, there exists IR with ||s|| S such that the
following holds for all (g', h/) E H:
(T(9.)) - p)
M) .) (l, (yl E. (L), (v'( w)).
The second property is implementability. This property actually allows us use our optimization oracle (in our case, OPT to access without explicitly representing it. In essence, it requires that we can generate small number of "fake examples" that effectively implement the perturbation needed by Algorithm 6
Definition C.2 (Implementability [Dud+20)). matrix I [-1, 11911 is implementable with complexity M for each j E [N] there exists dataset Sy with [S S M such that, for all pairs of rows (g, h), (g', h/)
H.
((lsh) P(ls N)))
Σ w (E,((o,)), (/ ((0' (N. N)....)))
(w..(
In the above definition, the fake examples are tuples of a context x E X' and two outcomes y, // E y. Finally, with the sufficient conditions of implementability and approximability, quote the main regret guarantee Algorithm n [an+22 here.
Theorem C.2 (Regret guarantee 6f W ). Let (1....,K] K} be the action space of the Learner and let 2 be the action space the adversary. Suppose that, at each round, the Learner chooses action Ft E [K, the adversary chooses action 2t E 2, and the loss function is f [K] x 2 - [0, 1) Jk (t). Then, if there exists "upproximable matrix I, Algorithm
Let Li- = minke(K]
instantiated with I and m min
achieves the following regret bound:
77 (.L.+T
4v max (2 (2 K, v Vlogg) + C+ d))
Rogy s
V Li +1
(o (VVi+++H) + 222 + 442 max K, / Nlog Kby.
+ +8y log
With an appropriate choice of C > O, we may obtain the regret bound:
o (VL Li max { log K, K.VNKWW log K
(22)
T is also implementable with complexity M, then Algorithm iis oracle-efficient, making O(T NM) oracle calls per round, where N is the number of columns I.
Finally, we need one more lemma using standard uniform convergence argument to bound the approximation error from sampling with OPT (g.H)) M times. This is essentially the same Lemma
B.6. but we obtain a sharper bound on E Σr (M) the cost of making polynomially (in T)
more calls to the oracle.
30

---

Lemma C.3. Lert E [T] and 2, E X' be fixed, and consider the function &. ((g h.) (3). g(zx) y) ((h(zz). y)). Let |> sc. If 2 T (o) then over the randomness of M drawing M samples ((ee) hr Ji-1 to construct the empirical distribution qe described in Definition B.4 for all y', E V let (MM be defined as the supremum
((M)= =
sup
E (og. Re (10, h), (v' ,i)1 B (o ((.
and, over all T rounds,
T Σ
E
(MM)
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:
M
1 M
Z,(y', 3) 2 k2 exp(-2x2M
sup ()
i=1
By the same exact argument using [[X] S J0² P| 2 tjdt, we obtain
1
Σ
M
Zily' . w)
S w + 12 exp((- exp(-2Mw²)
sup E)
M
1=1
where >> 0 is arbitrary parameter. Set #.. Then, if M > T log(hT)) we get
M
[[)( =
sup ())
Σ Z(y', v) i=1
2//T.
M
The lemma follows from summing over T.
We can now prove Theorem 5.1 The main idea is that the small loss regret translates directly into a o(Ty) regret due to how we defined our loss function, &z so we simply instantiate the (G, -llayerr in the general algorithm template of Algorithm with Algorithm This allows us to directly inherit the oT,) regret guarantee. We restate it here, with parameters specified, Proposition C
Proof of Theorem 5.7
Proposition C.3.1 (Theorem 5.1 with parameters specified), Assume H. G are finite and there exists a a-ppproximable and implementable perturbation matrix I E 1- (H xN Let [V] k. Let 2 0 be the approximation parameter of OPT H). player in Algorithm be the GFTPL algorithm of (Wan+22) instantiated with I, with parameter M 2 log(k?T). Then, for each g 9:
(g.H). Let the no-regret algorithm for the (G. H)-
E[Reg (H, S0 (0 (VT, max (7, [Hll)) /N log [ } aT)
Proof. Armed with approximability and implementability. we are ready to prove Theorem 5.T Sup- pose that there exists 7-approximable and implementable perturbation matrix I' E [-1, 1 x In the setting of Theorem C.2 we instantiate K H Z X x y x V. and the loss function f(s as:
f(lg, (x,
(x, v)) i,((g, h), (2) g(x) (L(v' .)) -(h(2))))))) v))
31

---

Observe that, with the loss instantiated as lxs we have:
LT
min x
& ((g, (1s, (1...1..6))
Llg, h), (1e. ve)) for all (g g H
Σ
v0) (())(())d..)))(((0)...)))) for all (g. h) g H.
T 1 Σ g(x)) = TT
for all g E G. The last inequality just comes from the fact that ((.,) E [0, 1]. By directly applying obtain the regret guarantee for Algorithm of
Theorem C.2
E[Regr] So (VT.) max {
7, log ||]| H|, v N log [
0 (T
Tg max 75 log 9 [7], v Nog G
However, this is just the regret guarantee of Algorithm 6 not the regret guarantee of our end-to- end multi multi-group online learning algorithm, Algorithm | We replace the algorithm of [Blo+22] in Algorithm with Algorithm 6 That is, use the Algorithm 6 for the (g. H'-player in Algorithm By our meta- theoremmemm Theorem B.4 this entire algorithm achieves the multi-group regret guarantee, for all g E G:
4 full description of this substitution in Algorithm 7
B[Regy-(H. <
E +
(23)
< ([e((M) + 0 (VT, T, max r, log [9], v /N log [9
(24)
Equation (24 follows from applying Lemma B.5 and using the regret bound for Algorithm
established above. It remains to ensure that Σ [[c( I o(Tg). Simply applying Lemma B.6
results in >x1 [M)) 2,T, which is insufficient for our purposes. Instead, we use Lemma C.3
which ensures that Σ _ Elfe (M)) S O(1) at the cost of increasing M to be M 2 T
T log (?:
making polynomially more oracle calls to OPT (g. per-round. This gives us the final regret guarantee of
10:+00( (Tr, max {7. log 191 VN log 191111))
E ([Reg 2
as desired.
One possible setting which a matrix easily constructible is the transductive setting. Here, explicitly show how to construct I' to obtain Corollary 5.1.1
Proof of Corollary 5.1.1 Let X S be the the adversary fixes beforehand in the transductive set-
ting, where N : | We construct 1-approximable and implementable I [-1, 1|11
by creating a row for each (g, h) E g x H. and column for each (x, k....v' y') E X x y x V, and setting each entry
(asse') L- (2( 1), (v/.
32

---

Algorithm 7 Algorithm for Group Oracle Efficiency (with GFTPL)
Input: Perturbation matrix E [-1, 1-111] XN; number of OPT (g.x) calls M E N.
1: for = 2, ...... T do
2: Receive (possibly adversarial) context zt 14 from Nature.
3: for = 1... . do
.3...,,M
4:
(G, -laaayr: Draw i.id. vector (u(1), ,...., (()) Lap(1) ie., p(v())
2 exp((-b(()).
5:
(G, plaaye: Set v4 + de where Th min (4i-i+1
6:
(9, -laayer::: Using the entire history {(s., Uo) b= so far, call OPT to obtain
(ğ. h) 9 H satisfying:
L. ((ğ, ((g,h), (f., vo)) + (1(5.h) vi)
((g", (1), + (T(o.)) uz) - a, (25)
sup (0
E
where [(ūhh) the (g, hith row of T.
7: end for
8: H-player: Call OPT н twice on the singleton datasets ((x+; 1}} and {(xre 1)) with the 0-1
loss, obtaining:
M/ E arg min (xx) + 1}
1_1 E arg min 1 {h (xx) # -1}.
M
ME
9: H-player: Solve the linear program
min D.AER
M
Σ
pl ((9) (())), (M)))) v)) + (1 p) ((o.)) (,(()) (IL,())) SA (-
s.t.
1=1
0SPS1.
10:
Sample b ~ Ber(p) where E (-1, 1), let b1 lig- Learner commits to the action d/2 h,(x)); ); Nature reveals y/-
11:
12:
Learner incurs the loss E(g,, yr).
13: end for
33

---

NeurIPS Paper Checklist
1. Claims
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 contribu- tions 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.
2. Limitations
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-efficint algorithms
in Sections 3 g and (respectively, i.idd assumption, smooth assumption, and existence of perturbation matrix assumption). We also note that our work does not address group-dependent o(T)) 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 not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 few datasets with 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 low or images are taken in low lighting. Or 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by review- ers 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
34

---

Justification: All theorems are formally stated in the main body and proved in the Appendix. Each main theorem, Theorem 3.2 3.2 proven in the Appendix.
Theorem 4.1 and Theorem 5.1 are stated in the main body and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs 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 short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data provided or not)?
Answer: [NA]
Justification: This is 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, No answer to this question will not 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible 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 specific model and empirical evaluation, may be necessary
suffice, or if the contribution to either make it possible for others to replicate the model with the same dataset, or provide access to the model. 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 model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., large language model), then there should either be way to access this model for reproducing the results way to reproduce the model (c.g., with an open-source dataset or instructions for how to construct the datasct).
(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.. registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This is theory paper (see above).
35

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips..cc/pbb)) for more details.
guides Stwlaess/CoeSSmiissiiiiooo
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 new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
to
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 reproduce all experimental results for the new proposed method and baselines. If only a subset experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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 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 other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is 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 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.
1 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
It OK to report
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are 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 tables in the text.
36

---

8. Experiments Compute Resourees
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification: This is theory paper (see above).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:// httpeh/hhh/////rrraaaaaaaaaaaaaa inees
Answer: [Yes]
Justification: This paper mainly focuses on a theoretical problem that does not involve the use any real-world datasets. Insofar as the proofs go, we have attempted to make them clear and easily checkable.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The main contribution of this work towards algorithmic techniques for learning theory problem. We see the societal impacts of such techniques as minimal.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, there a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
37

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility MI.).
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 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 not require this, but encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators 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, models. Guidelines:
The answer NA means that the paper does not 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 URL.
The name the license (c.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, paperswi www.de.thcc....cm. com/ 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 not available online, the authors are encouraged to reach out the asset's creators.
13. 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/moodll as part of their sub- missions 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 include anonymized zip file.
38

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not conduct any experiments on human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According to the NeurlPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not conduct any experiments on human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "sMDUWXkbDt", "reviewer": "Reviewer_K3De", "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.", "questions": "See Weaknesses.", "limitations": "No concerns.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper studied the multi-group online learning problem, which is related to fair learning and subgroup robustness literature, both are significant. Under the smoothed setting, it achieves $\\tilde{O}(\\sqrt{dT/\\sigma})$ regret; while under the general setting where $\\gamma$-approximability is guaranteed, it achieves $\\tilde{O}(\\sqrt{NT_{g}\\log\\lvert H\\rvert \\lvert G\\rvert})$ for each group $g$.\n\nIt first considers the i.i.d setting (both offline and online) then quickly moves forward to the smoothed online setting. Under the AMF framework, it considers two players: $(G,H)$-player (adversary that has access to an optimization oracle $\\text{OPT}^{\\alpha}_{(G,H)}$ that maximizes the learner's loss) and the $H$-player. Under such a game-theoretic perspective, the paper proposes algorithms that achieves bounded regret. It then adapts the algorithm to broader settings (non-smoothed settings), where the $\\gamma$-approximability is assumed. For groups with different densities, the algorithm can achieve low regret for each group $g$. The algorithmic designs are subtle and the analysis is sound to the review.", "weaknesses": "The main text in Section 2 and after are fine, while Section 1 needs improvement. Specifically, some descriptions are unclear. \n\nFor 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. \n\nLine 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper.\n\nWe will take care in the camera-ready version to make revisions to Section 1 that improve its clarity. In particular, the additional space of a page should allow us to address these issues adequately.\n\n- Lines 54-55: In this line, we mean that if $\\mathcal{G}$ is expressive enough, then any potentially relevant subgroup should be well-approximated by some $g \\in \\mathcal{G}$, and, therefore, any individual $x \\in g$ should be ensured that the quality of their predictions are as good as the best possible prediction for their group. When we wrote that those subgroups would be \"covered,\" we meant that those subgroups should be included in, or, at least, well-approximated by some $g \\in \\mathcal{G}$, so our guarantees apply to that subgroup. We will make this wording more clear in the revision, replacing this clause with \"...but multi-group learning with a very rich and expressive family of groups $\\mathcal{G}$ ensures that, as long as a subgroup is well-approximated or within the collection $\\mathcal{G}$, it obtains our theoretical guarantees. This motivates dealing with large or potentially infinite $\\mathcal{G}$ to provide guarantees for as many subgroups as possible.\"\n- Line 18 + Line 76: Thank you for bringing this to our attention. We will clarify early in the introduction that $g$ (lowercase) denotes a single subset of $\\mathcal{X}$. In the \"Summary of Results,\" we will clarify that our regret guarantee is specific to each $g \\in \\mathcal{G}$ by starting the claim in Line 75 with, \"...for each particular group $g \\in \\mathcal{G}$.\"\n\nIn addition to the comments you raised, we will clarify the descriptions in the Summary of Results using the added space. In particular, we will add sentences describing the parameters in the regret bounds, and, potentially, if there's still space, add a table to compare to results from previous work. We included a draft of such a table in the global Author Rebuttal PDF.\n\nPlease let us know, if, in addition to the proposed modifications above, there are any other clarity issues you noticed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mmZA13a8Yl", "reviewer": "Reviewer_wskr", "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. \n[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.\n\nTo 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.", "questions": "Please address the above.\n\nAlso, the appendix describes multi-class action space, what would change with real valued labels?", "limitations": "The authors discuss limitations of their paper.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is technically solid and a substantial contribution to online learning with multi group regret gurantees, and is the first to be oracle efficient in both G and H.\n- The reduction of multi group regret to AMF regret and the resulting minmax game simplification is novel.\n- They provide multigroup regret analogs of smoothed online learning, generalized FTPL.", "weaknesses": "- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper.\n\nWe definitely agree that a main open question in our work is the nature of the $(\\mathcal{G}, \\mathcal{H})$-optimization oracle. To our knowledge, [GKR22] is the only work to have explicitly stated instantiations for such an oracle. On a high-level note, our work follows a long line of work that exploit oracle primitives *assumed* to be computationally efficient (referenced in our work), so we don't expect to get end-to-end computational efficiency. There are a plethora of well-known hardness results for agnostic learning with various concept classes, and multi-group learning is a generalization of agnostic learning, so the need to assume such primitives is necessary in many cases (and models the empirical success of ERM despite hardness results).\n\nTo your first point in \"Weaknesses,\" we agree that it would be very helpful to the presentation of the paper to include the algorithm description for the $(\\mathcal{G}, \\mathcal{H})$-optimization oracle in our paper so it can be easily referenced. In the camera-ready version, we will include the algorithms for the ternary classification oracle and the alternating minimization oracle, as well as their main guarantees from [GKR22] in the appendix or main body. We will also briefly discuss some heuristic possibilities for instantiating such an oracle.\n\nTo your second point in \"Weaknesses,\" it is not entirely clear to us what the computational efficiency of such an oracle would be, at least in the theoretical sense. From a heuristics standpoint, the aforementioned ternary classification instantiation from [GKR22] can be instantiated so long as we have access to weighted multi-class classification, which, at least in practice, can be implemented with cost-sensitive classification packages. In this case, $\\mathcal{G}$ is a byproduct of the class upon which this ternary classifier outputs a \"defer\" label. On the other hand, if there's a specific $\\mathcal{G}$ we want to address, the aforementioned alternating maximization oracle from [GKR22] can be implemented with ERM access to $\\mathcal{G}$. Of course, ERM is computationally hard in the worst-case, but heuristics for ERM exist and it is a common assumption in the literature to assume that, at the very least, approximate ERM is feasible. Because $\\mathcal{G}$ is class of group indicators, this is equivalent to assuming that we have ERM heuristics for binary classification. However, we should mention that the alternating maximization heuristic can only be guaranteed to supply saddle points, not true global maxima. In both these cases, heuristics (either for multi-class weighted classification or ERM) exist that avoid enumeration. However, it's clear that both these methods have limitations, and we will point out these limitations in the camera-ready version, along with the algorithm descriptions, as we mentioned in the point above. We believe that it is an interesting and worthwhile open question to develop more specific instantiations of this $(\\mathcal{G}, \\mathcal{H})$-oracle for more specific problem settings that are computationally efficient and have provable optimization guarantees.\n\nTo your final point about real-valued action spaces, the main challenge is that our $\\mathcal{H}$-player must solve a $|\\mathcal{Y}| \\times |\\mathcal{Y}|$ size linear program, ultimately playing a distribution over possible actions which are of the order $|\\mathcal{Y}|$. Because the $\\mathcal{H}$-player must hedge against all possible $\\mathcal{Y}$ the adversary could select in its linear program, we were only able to implement this step with discrete, finite label spaces. We believe it is an interesting open problem to extend our techniques to real-valued action spaces. One naive route might be to take a discretization approach, but a fine-enough discretization would defeat the purpose of the simple LP the $\\mathcal{H}$-player must solve at every round. [Blo+22] does give an approach for the (single group) case for real-valued labels in the smooth setting, but the challenge remains to design a feasible game for the $\\mathcal{H}$-player to solve at every round to hedge against the maximally adversarial choice in a continuous $\\mathcal{Y}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kcZaiOOLYh", "reviewer": "Reviewer_sHAP", "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.", "questions": "Please see the weaknesses part.", "limitations": "The authors have addressed the limitations and societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses the problem of avoiding enumeration of groups, which improves the efficiency of the algorithm when the space of group is large.\n2. The reduction from online multi-group learning to the AMF framework is novel and interesting.", "weaknesses": "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.\n2. 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.\n3. 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.\n4. 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper. In particular, we appreciate your feedback on the presentation of our results and related work, and we believe that addressing these issues will greatly improve clarity.\n\nTo your first point on related work, space limitations did not allow us to include a table in the preliminary submission, but we agree that a table of existing results would help presentation. Please see the attached rebuttal PDF for our draft of this table. For multi-group learning in the online, sequential setting, the only two works that provide comparable regret bounds are, to our knowledge, [BL20] and [Ach+23], which both obtain a $\\sqrt{T_g \\log |\\mathcal{H}| |\\mathcal{G}|}$ regret requiring enumeration of $\\mathcal{H}$ and $\\mathcal{G}$ or $\\mathcal{G}$ itself with an oracle for $\\mathcal{H}$. We will state this in our table in the camera-ready version, making specific note how the algorithms fare in terms of space and computationally complexity, our main concern. In the online learning setting without group considerations, we can include the existing results for smoothed online learning from [Blo+22] in our table, which, to our knowledge, are the best possible regret bounds for the smoothed setting. \n\nTo your second point on AMF and FTPL, we appreciate the feedback and believe it is important that the intuition of these two main ingredients is clear. In a nutshell, the AMF framework allows us to have low-regret with respect to all $\\mathcal{G} \\times \\mathcal{H}$ pairs; the multi-objective regret guarantees are useful for our purposes because we want to guarantee simultaneous low regret over all $\\mathcal{G}$. However, naively applying AMF requires us to enumerate these objectives, in turn enumerating $\\mathcal{G}$, the main issue we want to avoid. FTPL comes to the rescue and allows us to have low-regret to all $\\mathcal{G} \\times \\mathcal{H}$ pairs implicitly without enumerating them. So AMF allows us to compete with all $g \\in \\mathcal{G}$; FTPL ensures this is efficient. We see that perhaps this needed more description in the Introduction, namely around line 82 in Section 1.1 (Summary of Results), so, in the camera-ready version, we will include the main novelty of using these techniques in the intro. We will also refer the interested reader to \"Technical Details\" in Section 4.2 for the main high-level description of the analysis and techniques. Then, in the \"Technical Details\" in Section 4, on line 258 and below, we will make sure this high-level description of our analysis is clear and that each component, the AMF and the FTPL, have a clear purpose.\n\nTo your third point about lower bounds, we agree that it is important to state the existing known limits, and we will provide details about existing lower bounds in the camera-ready work where we have more space. Statistical and computational lower bounds exist from [Blo+22], [HK16], and [HHSY22] for the oracle-efficient online learning setting without groups, so they immediately apply to our setting, as the group setting is a strictly harder generalization. We will include such lower bounds in our work. The lower bound of [HK16] motivates the line of work in oracle-efficient online learning, demonstrating that, in the fully adversarial online setting, even when given an oracle for $\\mathcal{H}$, regret must be $\\Omega(T)$ unless we our time complexity is $\\mathrm{poly}(|\\mathcal{H}|)$. This motivates working with an optimization oracle in more restricted settings, such as the *smoothed* setting we extensively study in our paper. Lower bounds for the oracle-efficient *smoothed* setting from [Blo+22] without groups show that, in the classification setting we consider, the $\\sqrt{\\frac{dT \\log T}{\\sigma}}$ regret is essentially tight. In particular, they show that *any* online algorithm with access to an ERM oracle cannot achieve sublinear regret against a $\\sigma$-smooth adversary unless $T \\geq \\tilde{\\Omega}(\\sigma^{-1/2})$. So in the smoothed classification setting, our main result is essentially optimal.\n\nTo your fourth point, we definitely agree that a main open question in our work is the nature of the $(\\mathcal{G}, \\mathcal{H})$-optimization oracle. To our knowledge, [GKR22] is the only work to have explicitly stated instantiations for such an oracle. There are many computational intractability results for agnostic learning, and multi-group learning is at least as hard as agnostic learning, so we don't expect to get end-to-end computationally efficient multi-group learning algorithms in general.\n\nTo address Reviewer wskr, as well, we believe it would be very helpful to the presentation of the paper to include the algorithm description for the $(\\mathcal{G}, \\mathcal{H})$-optimization oracle in our paper so it can be easily referenced. Currently, we only make a passing mention to [GKR22], but we will include a lengthier discussion in the camera-ready version. There are two existing algorithms that reduce optimizing over $(\\mathcal{G}, \\mathcal{H})$ to weighted multi-class classification or alternating ERM over $\\mathcal{G}$ and $\\mathcal{H}$. Both suggest implementable heuristics in practice. In the camera-ready version, we will include the algorithms for the ternary classification oracle and the alternating minimization oracle, as well as their main guarantees from [GKR22] in the appendix or full body. We will also briefly discuss some heuristic possibilities for instantiating such oracles. We note that, due to the computational hardness of ERM in the worst-case, the oracle in [Ach+23] requires access to similar heuristics.\n\nFor more on the computational efficiency of this oracle, please see our response to Reviewer wskr. We believe that we have addressed all the weaknesses in this response and will make the appropriate additions in the camera-ready version. Please let us know if anything was insufficient or unclear.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hQ7Z5fStKk", "reviewer": "Reviewer_TY8p", "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.", "questions": "I do not have any questions at this moment.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The paper studies an interesting and important problem. The size of possible groups may indeed be very large in real cases, and infinite as the sample size infinitely grows.\n\n2. The paper, while using relatively advanced mathematics, tackles the problem with well-known and intuitive techniques in optimization and game theory, and consequently achieves satisfying theoretical results.\n\n3. The presentation is very readable: the definitions, results, and remarks are presented in a nice order and achieves the level of rigor for a theoretical paper.\n\nOverall I am in favor of this work because of the elegant solutions for an important problem.", "weaknesses": "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.\n\n2. (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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insight and helpful review. Your comments will be very helpful in improving the presentation of the final paper.\n\nTo your first point about the multi-class case, we actually do address this in Appendix C. In the main body, we only included a Remark on line 248, but Appendix C includes all the details for a finite, $K$-valued discrete action space $\\mathcal{Y}$. Our main theoretical guarantee for such a case is Theorem C.1, and the algorithm for this case is Algorithm 4.\n\nTo your second point about the measure theoretic Definition 4.1, we agree that this may be overly technical. We do need the definition to properly define our setting, but we will take care to define essential supremum and absolute continuity. We will also emphasize that thinking about the results in terms of our simple example where the base measure $\\mathcal{B}$ is uniform on $\\mathcal{X}$ is sufficient for understanding our results.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We have included a draft of the table that will appear in the Introduction section of the camera-ready version of our work to address Reviewers K3De and sHAP. This table includes a summary of existing results in comparison to ours.

Meta-review: 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.
Decision: Accept (poster)