Oracle Efficient Algorithms for Groupwise Regret
Authors: Krishna Acharya
Eshwar Ram Arunachaleswaran
Sampath Kannan
Aaron Roth
Juba Ziani
Venue: ICLR 2024 poster (2024)
Keywords: Oracle efficiency
online learning
groupwise regret
sleeping experts
Primary area: learning theory

Abstract: We study the problem of online prediction, in which at each time step $t \in \{1,2, \cdots T\}$, an individual $x_t$ arrives, whose label we must predict. Each individual is associated with various groups, defined based on their features such as age, sex, race etc., which may intersect. Our goal is to make predictions that have regret guarantees not just overall but also simultaneously on each sub-sequence comprised of the members of any single group. Previous work such as  [Blum & Lykouris][1] and [Lee et al][2] provide attractive regret guarantees for these problems; however, these are computationally intractable on large model classes (e.g., the set of all linear models, as used in linear regression). We show that a simple modification of the sleeping experts technique of [Blum & Lykouris][1] yields an efficient *reduction* to the well-understood problem of obtaining diminishing external regret *absent group considerations*. 
Our approach gives similar regret guarantees compared to [Blum & Lykouris][1]; however, we run in time linear in the number of groups, and are oracle-efficient in the hypothesis class. This in particular implies that our algorithm is efficient whenever the number of groups is  polynomially bounded and the external-regret problem can be solved efficiently, an improvement on [Blum & Lykouris][1]'s stronger condition that the model class must be small. Our approach can handle online linear regression and online combinatorial optimization problems like online shortest paths. Beyond providing theoretical regret bounds, we evaluate this algorithm with an extensive set of experiments on synthetic data and on two real data sets --- Medical costs and the Adult income dataset, both instantiated with intersecting groups defined in terms of race, sex, and other demographic characteristics. 
We find that uniformly across groups, our algorithm gives substantial error improvements compared to running a standard online linear regression algorithm with no groupwise regret guarantees.

Published as a conference paper at ICLR 2024
ORACLE EFFICIENT ALGORITHMS FOR GROUPWISE RE- GRET
Krishna Acharya', Eshwar Ram Arunachaleswaran' Sampptt Kannan', Aaron Ziani' GGerrgia Institute of Technology, PUniversity of Pennsylvania
[kacharya33, 3ziani3Jegatech. edu, "(eshwar, kannan, aaroth]@sead upenn, edu
ABSTRACT
We study the problem of online prediction, in which at each time step 1 E T. individual X arrives, whose label we must predict. Bach in- dividual is associated with various groups, defined based on their features such as age, sex, race etc., which may intersect. Our goal is make predictions that have regret guarantees not just overall but also simultaneously on each sub-sequence comprised of the members of any single group. Previous work (Blum & Lykouris] 2020) provides attractive regret guarantees for these problems; however, these are computationally intractable on large model classes (e.g., the set of all linear models, used in linear regression). We show that simple modification of the sleeping-experts based approach of Blum & Lykouris| (2020) yields an efficient reduction to the well-understown problem of obtaining diminishing external regret absent group considerations. Our approach gives similar regret guarantees com- pared to Blum & Lykouris (2020); however, groups, and are oracle-efficient in the hypothesis class. This in particular implies that our algorithm
in time linear in the number of
efficient whenever the number of groups is polynomially bounded and the external-rege regret problem can be solved efficiently, an improvement on Blum & Lykouris (2020)'s 's stronger condition that the model class must be small. Our approach can handle online linear regression and online combinatorial optimization problems like online shortest paths. Beyond providing theoretical regret bounds, we evaluate this algorithm with an extensive set of experiments on synthetic data and on two real data sets Medical costs and the Adult income dataset, both instantiated with intersecting groups defined in terms of race, sex, and other demographic characteristics. We find that uniformly across groups, our algorithm gives substantial error improvements compared to running a standard online linear regression algorithm with no groupwise regret guarantees.
INTRODUCTION
Consider the problem of predicting future healthcare costs for a population of people that arriving dynamically and changing over time. To handle the adaptively changing nature of the problem, we might deploy an online learning algorithm that has worst-case regret guarantees for arbitrary sequences. For example, we could run the online linear regression algorithm of of/Azuury & Warmuth (2001), which would guarantee that the cumulative squared eгror of our predictions is at most (up to low-order terms) the squared error of the best fixed linear regression function in hindsight. Here we limit ourselves to a simple hypothesis class like linear regression models, because in general, efficient no-regret algorithms
not known to exist for substantially more complex hypothesis classes. It is likely however that the underlying population is heterogenous: not all uub-populations are best modeled by the same linear function. For example, "the best" linear regression model in hindsight might be different for different subsets of the population as broken out by sex, age, race, occupation, or other demographic characteristics. Yet because these demographic groups overlap- an individual belongs to some group based on race, another based on sex, and still another based on age, etc- - we cannot simply run a different algorithm for each demographic group. This motives the notion of groupwise regret, first studied by Blum & Lykouris (2020). A prediction algorithm guarantees diminishing groupwise regret with respect to a set of groups G and a hypothesis class H, if simultancously for every group in G, on the subsequence of rounds consisting of individuals who are members of that group, the squared error is at most (up to low-order regret terms) the squared error of the best model in H on that subsequence. Blum & Lykouris (020 gave algorithm for

---

Published as a conference paper at ICLR 2024
solving this problem for arbitrary collections of groups G and hypothesis classes H see Lee et al.
(2022) for an alternative derivation of such an algorithm. Both of these algorithms have runming times G and [H] for example, the algorithm given in Blum & Lykouris (2220) is a reduction to a sleeping experts problem in which there is one expert for every pairing of groups in G with hypotheses in H. Hence, neither algorithm would be feasible run for the set H consisting of c.g. all linear functions, which is continuously large - and which is exponentially large in the dimension even under any reasonable discretization.
that depend polynomially
Our first result is an "oracle efficient" algorithm for obtaining diminishing groupwise regre( for any polynomially large set of groups G and any hypothesis class H: In other words, it an efficient reduction from the problem of obtaining groupwise regret over G and H to the easier problem of obtaining diminishing (external) regret to the best model in H ignoring group structure. This turns out to be a simple modification of the sleeping experts construction of [Blum & Lykouris (2020). Because there are efficient, practical algorithms for online linear regression, a consequence of this is that we get the first efficient, practical algorithm for online linear regression for obtaining groupwise regret for any reasonably sized collection of groups G (our algorithm needs to enumerate over the groups at each round and so has running time linear in |G). We can instantiate our algorithm for groupwise regret in any setting in which we have an efficient no (external) regret learn- ing algorithm. For example, we can instantiate it for online classification problems when the benchmark class has a small separator set, using the algorithm of Syrggaassss et al. (2016); for online linear optimization problems, we can instantiate it using the "Follow the Perturbed Leader" (FTPL) algorithm of Kalai & Vempala (2005). For online linear regression problems, we can instantiate it with the online regression algorithm of Afzuur & Warmuth (2001).
Danogagnic spMpcarg ridil
20
(a) Groups based on age, sex
With our algorithm in hand, we embark an extensive set of experiments in which the learning task is linear regression, both synthetic data and on real datasets. In the synthetic data experiment, we construct a distribution with different in- tersecting groups. Each group is associated with (different) underlying linear model; individuals who belong to multiple groups have labels that are generated via an aggregation func- tion using the models of all of the containing groups We experiment with different aggregation functions (such as us- ing the mean, minimum, maximum generated label, as well as the label of the first relevant group in a fixed lexicographic ordering). We find that consistently across all aggregation rules, our algorithm for efficiently obtaining groupwise regret when instantiated with the online regression algorithm of Azoory & Warmuth (200T) has substantially lower cumulative loss and regret on each group compared when we run the online re- gression algorithm of Azoury & Warmuth (200T) alone, on the entire sequence of examples. In fact, when using our algorithm. the regret to the best linear model in hindsight when restricted to fixed group is often negative, which means we make predictions that are more accurate than that of the best linear model tailored for that group, despite using linear learners as our underlying hypothesis class. This occurs because there are many individuals who are members of multiple groups, and our algorithm must guarantee low regret each group separately, which requires ensembling different linear models across groups whenever they intersect. This ensembling leads to an accuracy improvement. We then run comparisons medical costs, and the task in the second is to predict income from demographic attributes recorded in Census data. We define intersecting groups using attributes like age, sex, race etc. Here too, our algorithm, instantiated with the online regression algorithm of Azoury & Warmuth| (2001), has consistently lower groupwise regret than the baseline of just running the algorithm of Azoury & Warmuth (2001) alone on the entire sequence of examples. Thus, even though algorithms with worst-
Gr sonerccee
Giver (hveter)
13
(b) Groups based on smoking habits
Figure 1: Regret vs. time (as frac- tion of subsequence length), for de- mographic groups based on age, sex in la] and 2 demorraggaiiiic groups based on smoking habits in
two real datasets: the prediction task in the first is to predict patient
'Lc., guarantceing sub-linear groupwise regret in the number of time steps, implying that the time-average regret vanishes and goes to 0
2

---

Published as a conference paper at ICLR 2024
case regret guarantees are not known for hypothesis classes substantially beyond linear regression. we can use existing online linear regression algorithms to efficiently obtain substantially lower error while satisfying natural fairness constraints by demanding groupwise regret guarantees. In Figure [ we plot the performance of our algorithm instantiated with the online linear regression algorithm of Azoury & Warmuth| (200T), compared the haseline of running Azoury & Warmuth (2001) alone on all data points, on a medical cost prediction task. We divide the population into a number of intersecting groups, on the basis of age (young, middle, and old), sex (male and female) and smoking status (smoker and non- smoker). We plot the regret (the difference between the squared error obtained, and the squared error obtainable by the best linear model in hindsight) of our algorithm compared to the baseline on each of these demographic groups (in the top panel for age and sex groups, and in the bottom panel for smoking related groups). Since the number of individuals within each group is different for different groups, we normalize the axis to represent the fraction of individuals within each group seen so far, which allows us to plot all of the regret curves on the same scale. In these computations, the performance of our algorithm comes from single run though the data, whereas "the best model in hindsight" is computed separately for each group. The plot records average performance over 10 runs. Here medical costs have been scaled to lie in [o, 1] and so the absolute numbers are not meaningful; it is relative comparisons that are important. What we see is representative on all of our experiments: the groupwise regret across different groups is consistently both lower and growing with time at lower rate than the regret of the baseline. The regret can even be increasingly negative as seen the age and sex groups.
1.1 RELATED WORK
The problem of obtaining diminishing groupwise regret in sequential decision-matee -making setting was introduced by [Blum & Lykouris (2020) (see also Rothblum & Yona (2021) who introduce a related problem in the batch setting). The algorithm Blum & Lykouris| (2020) a reduction to the sleeping experts problem: Lee et al. (202)) derive another algorithm for the same problem from first principles as part of a general online multi-objective optimization framework. Both of these algorithms have
running time that scales at least linearly with (the product of) the number of groups and the cardinality of the benchmark hypothesis class. In the batch setting, Tosh & Hsu (202) use an online-to-batee reduction together with the sleeping-exper state-of-ther -ort--artthttttttt batch sample complexity bounds. None of these algorithms are oracle efficient, and as far we are aware, none of them have been implemented - in fact, Tosh & Hsu (022)) explicitly list giving an efficient version of Blum & Lykouris (2020) that avoids enumeration of the hypothesis class as open problem. Globus- Hoobus-Harriss Harris et al. (2022) derive algorithm for obtaining group-wiss wise optimal guarantees that can be made to be "oracle efficient" by reduction to a ternary classification problem, and they give an experimental evaluation in the batch setting- but their algorithm does not work in the sequential prediction setting.
style algorithm of Bllum & Lykouris (2020) to obtain
Multi-group regret guarantees are part of the "multi-group" fairness literature, which originates with Kearns et al. (2018) and Hébert-Johnson et al. (2018). In particular, multicalibration Hébert- jet al. (2018) is related to simultaneously minimizing prediction loss for benchmark class, on subsets of the data Gopalan et al. (2022) )023); Globus-Harte et al.] (2023). One way to get groupwise regret guarantees with respect to set of groups G and a benchmark class H would be to promise "multicalibration" with respect to the class of functions G x H. Very recently, et al. (2023) gave an oracle efficient algorithm for obtaining multicalibration in the sequential prediction setting by reduction to an algorithm for obtaining diminishing external regret guarantees. However, to apply this algorithm to our problem, we would need an algorithm that promises external regret guarantees over the functions in the class G x H. We do not have such algorithm: For example the algorithm of Azoury& & Warmuth| (2001) can be used to efficiently obtain diminishing regret bounds with respect to squared error and the class of linear functions: but even when H the set of linear functions, taking the Cartesian product of H with a set of group indicator functions will result in class of highly non-linear functions for which online regret bounds are not known. In contrast to Garg et al. (2023). our approach can be used to give groupwise regret using a learning algorithm only for H (rather than an algorithm for G x H), which lets us give an efficient algorithm for an arbitrary polynomial collection of groups, and the benchmark class of linear functions.
2 MODEL
We study model of online contextual prediction against an adversary in which we compare to bench- marks simultancously across multiple subsequences of time steps in {1...., T). Each subsequence
3

---

Published as a conference paper at ICLR 2024
is defined by time selection function I {I...., T - 100 which specifies whether or not each round t is a member of the subsequence or not. In each round, the learner observes a context I, X where X S [0, 1 based on this context, he chooses a prediction pt AA C [0. 1 Then, the learner observes a cost (chosen by an adversary) for each possible prediction in A. The learner is aware of benchmark class of policies H; each I H is function from X to A and maps contexts to predictions. The learner's ' goal is to achieve loss that is as low as the loss of the best policy in hindsight - not just overall, but also simultaneously on each of the subsequences (where "the best policy in hindsight" may be different on different subsequences).
More precisely, the interaction as follows. The loss function é maps actions of the learner and the adversary to a real valued loss in [0, 1]. The time selection functions I {11, 12, ... /1z) } are the indicator function for the corresponding subsequence. In rounds E (1....,T}:
1. The adversary reveals context De E X (representing any features relevant to the prediction task hand), as well as (t) for each 7 E I, the indicator for whether each subsequence contains round t.
2. The learner (with randomization) picks a policy Pt X + A Fl and makes prediction Pr( E A. Simultancously, the adversary selects action ye taken from known set V.
3. The learner learns the adversary's action y/ and obtains loss (xx) De) E [0.
We define the regret on any subsequence against a policy I E H as the difference in performance of the algorithm and that of using f in hindsight to make predictions. The regret of the algorithm on subsequence 1 is measured against the best benchmark policy in hindsight (for that subsequence):
Regret on Subsequence 1 1- E Σ (())
min Σ (())))))))))))) FIEH
Here, E I,,, (())e(p:(z)) vt)] is the expected loss obtained on subsequence / by an algorithm that uses policy Pt at time step t. and minsis E, (f)))() yt) represents the smallest loss achievable in hindsight on this subsequence given a fixed policy f E H. This regret mcasures, on the current subsequence, how well our algorithm is doing compared to what could have been achieved had we known the contexts I2 and the actions Y/ in advance-is we could have made predictions for this subsequence in isolation. Of course the same example can belong to multiple subsequences, which complicates the problem. The goal is to upper bound the regret on each subsequence / by some sublinear function o(y)) where T, = E. I(1) is the 'length' of In the context of our original motivation, the subsequences map to the groups care about the subsequence for a group is active on some round if the round t individual is a member of that group. Our benchmark class can be, e.g., the set of all linear regression functions. Obtaining low subsequence regret would be straightforward if the subsequences were disjoin The main challenge is that in our setting, the subsequences can intersect, and we cannot treat them independently anymore.
In aid of our techniques, we briefly describe the problem of external regret minimization, a problem that is generalized by the setup above, but which consequently admits stronger results (better bounds in running time/ regret) in various settings.
External Regret Minimization In this problem, the learner has access to a finite set of experts E, and picks an expert e, E E with randomization in each round / E {1,2 .. 7). in each round. An adversary then reveals a loss vector 4 E TR. EI with the learner picking up loss of ((e.). The learner's 's objective is to minimize the overall regret, called external regret, on the entire sequence as measured against the single best expert in hindsight. Formally:
External Regret- E
Σ (c(e))
min
Ee((e). eEE
An online learning algorithm is called a no-regret algorithm if its external regret is sublinear in T. i.c. o(T"), and its running time and regret are measured in terms of the complexity of the expert set E.
"Our results hold without significant modification for fractional time selection, i.e., I: I [0, 1]. 'For most of our applications, the policy is in fact picked from the benchmark class, however in one of our applications. online least regression, the analysis is simplified by allowing policies beyond the benchmark.
*One could just run separate no-regret learning algorithm on all subsequences separately.
4

---

Published as a conference paper at ICLR 2024
3 SUBSEQUENCE REGRET MINIMIZATION VIA DECOMPOSITION
We outline our main algorithm for online subsequence regret minimization. Algorithm I maintains [Z] experts, each corresponding to single subsequence, and aggregates their predictions suitably at each round. Each expert runs their own external regret minimizing or no-regret algorithms (each measuring regret against the concept class ft). However and as mentioned above, the challenge is that any given time step might belong simultaneously to multiple subsequences. Therefore, it is not clear how to aggregate the different suggested policies corresponding to the several currently "active" subsequences (or experts) to come up with prediction. To aggregate the policies suggested by each expert or subsequence, we use the AdaNormalHedge algorithm of Luo & Schapire (2013) with the above no-regret algorithms forming the set of k meta-experts for this problem.
Parameters: Time Horizon T
1. Initialize instance N of an external regret minimization algorithm for the subse- quence corresponding to each time selection function E Z, with the policy class H the set of experts.
2. Initialize an instance of AdaNormalHedge with {Zihez as the set of policies, which we call meta-experts.
3. For t 1,2,
(a) Subsequence-leve prediction step: Observe context Zt. Each meta-expert 3, recommends a randomized policy p with realization zf (from H).
(b) Prediction aggregation step: Using the information from the subsequence indi- cators and fresh randomness, use AdaNormalHedde to sample meta-expert z Set the policy P. of the algorithm to be policy z₁. offered by this meta-expert (L.e. pick action 2/,, (zt)).
(c) Update step: Observe the adversary's 's action y/. Update the state of algorithm Z by treating the loss of meta-expert 2 as (z (zx), y:) For each subsequence that is "active" in this round (i.e., with (tt) = 1), update the internal state of the algorithm 3 using 2e and yt-
"AdaNormalllede in fact samples from only the set of meta-experts corresponding to active subse- quenees
Algorithm 1: Algorithm for Subsequence Regret Minimization
For each subsequence I, assume there is an online learning algorithm Z, that picks amongst policies in H mapping contexts to actions and has external regret (against H) upper bounded by aj. Then, there exists an online learning algorithm (Algorithm 77. that given [I] subsequences I, has total runtime (on per round basis) equal to the sum of runtimes of the above algorithmss
Theorem 1.
and a term that is a polynomial in [Z] and d and obtains a regret of oi + O (VTi log IT) for any Jorany subsequence with associated length Tj.
In the interest of space, the proof has been moved to Appendix C As an immediate consequence of this theorem, we obtain the main result of our paper as a corollary (informally stated).
Theorem 2.
Any online learning problem with a computationally efficient algorithm for obtaining vanishing regret also admits a computationally efficient algorithm for vanishing subsequence regret over subsequences defined by polynomially many time selection functions.
Improved computational efficiency compared to Blum & Lykouris (2020) We remark that our method is similar Blum & Lykouris (2020) in that relies on using AdaNormalHedge to decide between different policies. However, it differs in the set of actions or experts available to this algorithm, allowing us to obtain better computational efficiency in many settings.
In our algorithm, we use exactly [Z] experts; each of these experts corresponds to a single subsequence and makes recommendations based on a regret minimization algorithm run only on that subsequence. Their construction instead instantiates an expert for each tuple (f, I), where f E H is policy and E a subsequence; a consequence is that their running time is polynomial hypothesis class. We avoid this issue by delegating the question of dealing with the complexity of the policy class to the external regret minimization algorithm associated with each subsequence, and by only enumerating []] experts (one for each subsequence). Practical algorithms are known for the
the size of the
5

---

Published as a conference paper at ICLR 2024
external regret minimization sub- nub-problem (that must be solved by each expert) for many settings of interest with large (or infinite) but structured policy classes (expanded upon in Section 4).
4 APPLICATIONS OF OUR FRAMEWORK
4.1 ONLINE LINEAR REGRESSION
Our first application online linear regression with multiple groups. At each round t, a single individual arrives with context 2; and belongs to several groups; the learner observes this context and group membership for each group and must predict a label.
Formally, the context domain is X
[0, 1] where a context is individual's 's feature vector; the learner makes a prediction yi in A = [0, 1], the predicted label; ; the adversary. for its action, picks Y/ y [0, 1] as his action, which is the true label; and the policy class H is the set of linear regressors in d dimensions, i.e. H consists of all policies E Rd where (xxe) == (0. mx) Va, E X. Each subsequence I corresponds to single group 9 within the set of groups G = {91 92: -. 9|61 in each round the subsequence indicator functions (tt are substituted by group membership indicator functions g(t), for each g E G. The goal is to minimize regret (as defined in Section 2 with respect the squared error loss: i.e., given that yt is the true label at round I, Dr is the label predicted by the
learner, the loss accrued in round is simply the squared error E(in, yt) = (ýt - )1)²
The notion of subsequence regret measured against policy 0 H in this setting leads exactly the following groupwise regret metric for any given group g (against 0):
Regret of Group y against policy 0- = E Σ
Σ ((0(1, - -v))². (1)
Our goal is to bound this quantity for each group g in terms Tf == E,g(t) which we refer to the length of subsequence associated with group g. and in terms of the size 0f For each subsequence I, we use the online ridge regression algorithm of Azoury & Warmuth (200I) to instantiate the corresponding meta-expert 3, in Algorithm [ We note that our algorithm obtains the following groupwise regret guarantees as direct corollary from Theorem
There exists efficient algorithm with groupwise regret guarantees for online linear regression with squared loss. This algorithm runs in time polynomial in [G] and and guarantees that the regret for group g as measured against any policy O H is upper- bounded by
Corollary 1.
o o (d + IT In([G))) +100))++)+))))))
where T, denotes the length of group subsequence g.
4.2 ONLINE CLASSIFICATION WITH GUARANTEES FOR MULTIPLE GROUPS
We now study online multi-label classification under multiple groups. We perform classification on an individual arriving in round based upon the individual's context x, and his group memberships Formally, the context domain is X C {0, 13 and each context describes an individual's feature vector; the prediction domain is A {0, 1)", with the prediction being a multi-dimensional label; and the adversary's 's action domain is Y = {0, 1}" with the action being the true multi muuti-diimnnsioal label that we aim to predict. Each subsequence I corresponds to group g. with the set of groups being denoted by G (01, 92. ) We assume that the learner has access to an optimization oracle that can solve the corresponding, simpler, offline classification problem: i.e., given t context- label pairs (z., y=) an oracle that finds the policy f E that minimizes Σ.m {(f(x)) ys) for the desired loss function f(.).
Our subsequence regret is equivalently the groupwise regret associated with group g. Formally:
Regret of Group g
E Σ (0(t)e(paa
min SEH
'While these predictions may lie outside J0. 1]. we allow our instantiation of AdaNormalHedge to clip predictions outside this interval the nearest endpoint ensure the final prediction lies in [0. 1,, since this can only improve its performance. We also note that the algorithm of Azoury & Warmuth (2001) has reasonable bounds on the predictions. which is reflected in the corresponding external regret bounds (See Besa-Bianchi Lugosi (2066) for details).

---

Published as a conference paper at ICLR 2024
We describe results for two special settings of this problem, introduced by Syngkanis et al. (2016) for the external regret minimization version of this problem.
Small Separator Sets: A set S C X of contexts is said to be separator set of the policy class H for any two distinct policies f, f & H, there exists a context x E 5 such that (x) * (x)). We present groupwise regret bounds assuming that H has separator set of size separator set implies that the set H is also finite (upper bounded by |A|*).. Transductive setting the transductive setting, the adversary reveals set S of contexts with |S| to the learner before the sequence begins, along with the promise that all contexts in the sequence are present in the set S. Note that the order and multiplicity of the contexts given for prediction can be varied adaptively by the adversary.
note that a finite
When plugging in the online classification algorithm of SSygkaanis et al. (2016) as the regret minimiz- ing algorithm ž for each subsequence / (here, equivalently, for each group in Algorithm [ we obtain the following efficiency and regret guarantees:
Corollary 2. There exists an oracle efficient online classification algorithm (that runs in time polynomial in [G], d, n. and s) for classifiers with small separator sets (size s) with groupwise regret upper bounded by O (5322/33 log H + vlgg ( (lg for each group 9.
Corollary 3. There exists an oracle efficient online classification algorithm (running in time polyno- mial in |G], d, n, and 8) for classifiers in the transductive setting (with transductive set size s) with groupwise regret upper bounded by O (VTg(V53/2npg log H v /log [[l] for each group g-
Note that in the above corollaries, "oracle efficient" means an efficient reduction to a (batch) ERM problem-thh the above algorithms are efficient whenever the ERM problem can be solved efficiently. We also briefly mention how the ideas of & Lykouris (2200) lift the results in this section for binary classification to the "apple-tasting model" where we only see the true label yt if the prediction is Pt- 1. For sake of brevity, this discussion is moved to Appendix G
4.3 ONLINE LINEAR OPTIMIZATION
Our framework gives us subsequence regret guarantees for online linear optimization problems, which, among other applications, includes the online shortest path problem. each round t, the algorithm picks a prediction a, from A S [0, 1] and the adaptive adversary picks cost vector ye from Y C Rd as its action. The algorithm obtains a loss of E(ae, M/e) = (at, Mt).. Unlike the previous applications, there is context, and the policy class H is directly defined as the set of all possible predictions The algorithm is assumed to have access to an optimization oracle that finds some prediction in arg min.e.4 (a,c) c) for any e Rd. The objective is to bound the regret associated with each subsequence / (described below) in terms of T, = E, T()), the length of the subsequence.
Regret of Subsequence 1 - IE Σ (()((aes un))
min
Σ E((()a,y))) acA
Kalai & Vempala 2005) show an oracle efficient algorithm that has regret upper bounded by AdT where A maxa, E.A ||u a'll2 and C = maxesy ||c//1. Using this algorithm for minimizing external regret for each subsequence in Algorithm we obtain the following corollary:
Corollary There is an oracle efficient algorithm for online linear optimization (of polynomial time in ( with the regret of subsequence (of length Tí) upper bounded by OC O(VTiCCd++ TT log (Z]))
EXPERIMENTS
We empirically investigate the performance of our algorithm in an online regression problem. We present our experimental results on two datasets in the main body. First, we run experiments synthetic dataset in Section Second, we perform experiments on real data in Section [5.3 using dataset (Lantz) 2013) for medical cost prediction tasks. We provide additional experiments the
census-based Adult income dataset [ DDing et al. 2021 Flood et al. 2020 Appendix D.5
"adult reconstruction csv is available at : http://www...../.cccaattttaaaaaa
Eolktables
7

---

Published as a conference paper at ICLR 2024
5.1 ALGORITHM DESCRIPTION AND METRIC
Learning task: In our experiments, we run online linear regression with the goal of obtaining low subsequence regret. We focus on the case where subsequences are defined according to group membership, and we aim to obtain low regret in each group for the sake of faimess. Our loss functions and our regret metries are the same as described in Section 4.1
Our algorithm: We aim to evaluate the performance of A Algorithm foo groupwise regret minimiza- tion. Given |G] groups, our algorithm uses |G] + subsequences: for each group g E G, there is a corresponding subsequence that only includes the data of individuals in group g; further, we consider an additional "always active" subsequence that contains the entire data history. We recall that our algorithm uses an inner no-regret algorithm for each meta-expert or subsequence, and AdaNormal Hedge to choose across active subsequences on a given time step. We choose online ridge regression from Azoury & Warmuth ) for the meta-experts' algorithm as per Section 4.1
Baseline: We compare our results to a simple baseline. At every time step 4, the baseline uses the entire data history from the first / 1 rounds, without splitting the data history across the |G] + 1 subsequences defined above. (Recall that since the subsequences intersect, there is no way to partition the data points by group). The baseline simply runs traditional online Ridge regression: at every f.
estimates 0, - arg ming 1 1 ((8, x²)) - yr )² + [10122, then predicts label g. é (0,.
Note that both our algorithm and the baseline have access to group identity (we concatenate group
indicators to the original features), thus the baseline can learn models for different groups that differ
by a linear shif
5.2 SYNTHETIC DATA
Feature and group generation Our synthetic data is comprised of 5 groups: 3 shape groups (circle, square, triangle) and 2 color groups (red, green). Individual features are 20-dimensional; they are independently and identically distributed and taken from the uniform distribution over support [0, 1|20. Each individual is assigned to one of the shape groups and one of the 2 color groups randomly; this is described by vector a E {0, 135 which concatenates categorical distribution over Pshape = [0.5, 0.3, 0.2] and one over Peotor = [0.6, 0.4].
Label generation Individual labels are generated as follows: first, draw weight vector Wy for each group g uniformly at random on [0, 1] Then, we assign an intermediary label to each individual in group g; this label is given by the linear expression w x. Note that each individual has two intermediary labels by virtue of being in two groups: one from shape and one from color. The true label of an individual is then chosen to be a function of both intermediary labels, that we call function. We provide experiments from the following aggregation functions: mean of the intermediary labels; minimum of the intermediary labels; maximum of the intermediary labels; and another aggregation rule which we call the permutation model (described in Appendix D.3). Our main motivation for generating our labels in such a manner is the following: first, we pick linear models to make sure that linear regression has high performance in each group, which allows to separate considerations of regret performance of our algorithm from considerations of performance of the model class we optimize on. Second, with high probability, the parameter vector Wy significantly differs across groups; thus it is important for the algorithm to carefully ensemble models for individuals in the intersection of two groups, which is what makes it possible to out-perform the best linear models in hindsight and obtain negative regret.
the label fegregationfuunctonn
Results Here, we show results for the mean aggregation function described in Section 5.2 Results for the other three (min, max, and permutation) are similar and provided in Appendix DD. D.I.D.2aadd [D.3 respectively, Across all the groups we can see that our algorithm has significantly lower regret than the baseline, which in fact has linearly increasing regret. Note that this is not in conflict with the no-regret guarantee of AAzuury & Warmuth (2001) as the best fixed linear model in hindsight is different for each group: indeed we see in box (f) that [Azoury& & Warmuth (200T) does have low regret on the entire sequence, despite having linearly increasing regret on every relevant subsequence. Further, we note that our algorithm's 's groupwise regret guarantees sometimes vastly outperform our already strong theoretical guarantees. In particular, while show that algorithm guarantees that the regret evolves linelinerrly, we note that in several of our experiments, it is in fact negative and decreasing over time (e.g. for the colors green and red). This means that our algorithm performs even better than the best linear regressor in hindsight; This is possible because by necessity, our algorithm
"We know of no implementable algorithms other than ours that has subsequence regret guarantees for lincar regression (or other comparably large model class) that would provide an alternative point of comparison.
8

---

Published as a conference paper at ICLR 2024
trangh
Shape: Cirele
Shape: Square
(c) Shape: Trianglc
-0-
10:00 ubo aodo aVd
2i00
(d) Color: Green
(e) Color: Red
(1) Always
Figure 2: Regret for baseline (blue) & our algorithm (orange) on synthetic data with mean of intermediary
labels, our algorithm always has lower regret than the bascline.
ensembling linear models for individuals who members of multiple groups, giving it access to more expressive (and more accurate) model class.
Quantitatively, the rough 87 magnitude of the cumulative least-squared loss (for the best performing linear model in hindsight) is 33. Our algorithm's cumulative loss is roughly lower than the baseline by an additive factor of 20, which represents substantial improvement compared the loss of the baseline. This implies that our regret improvements in Figure 2 are of a similar order of magnitude as the baseline loss itself, hence significant.
5.3 MEDICAL COST DATA
Dataset description The "Medical Cost" dataset Lantz 2013) looks at individual medical cost prediction task. Individual features are split into numeric {age, BMI, #children] and categoric features {sex, smoker, region}. The dataset also has real-valued medical charges column that we use as our label.
Data prepprocsssngg All the numeric columns are min-max scaled the range [0, 1] and all the categoric columns are one-hot encoded. We also pre-process the data to limit the number of groups we are working with for simplicity of exposition. In particular, we simplify the following groups:
1. We divide age into groups: young (age S 35), middle (age (35, 50), old (age>> 50)
2. For sex, we directly the 2 groups given in the dataset male, female
3. For smoker, we directly use the 2 groups given in the datset smoker, non-smoker
4. We divide BMI (Body Masss Index) into 4 groups: underweight (BMI < 18.5), healthy (BMI E [18.5, 25)), overweight (BMI [25, 30)), obese (BMI 2 30)
Results The results for age, sex and smoker groups discussed earlier, in Section | Figure [ We remark that the BMI group results are similar: the groupwise regret is consistently lower and growing with time at lower rate than the baseline. We provide detailed plots (including error bars) for all groups in Appendix D.4 Quantitatively, the rough magnitude") of the cumulative loss of the best linear model hindsight 4. and our algorithm's cumulative loss is 1.9 units lower than the baseline, which is a significant decrease.
@
A Exxact values provided in Appendix E table
Exact values provided in Appendix F. taalle

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
We briefly describe information about the data sequence, data processing and algorithms. The code is available at httpt::: //ggtttt....t///////////. com /rri iataaacarrammmltiiiie
Data sequence: The sequence in which the online algorithms receive data can impact the empirical regret. We fix random seeds and use these shuffle each of our datasets. The mean and standard deviation of regret across these shuffles is available in Appendix E
Dataset specific processing: For the synthetic data we use a fixed seed (available in README. . md) to generate the 100k samples, the aggregate labels are then min-max scaled to [0, 1]. For the two real datasets we min-max scale the numeric features to [0, 1] and one-hot encode the categoric features. Algorithms: Online ridge regression and AdaNormalHedge are implemented in ORidge py and Anh. respectively.
ACKNOWLEDGMENTS
Supported in part by NSF grant IIS-2147212 and the Simons Collaboration on Algorithmic Fairness.
REFERENCES
Katy Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine learning, 43:211-246, 2001.
Avrim Blum and Thodoris Lykouris. Advancing subgroup fairness via sleeping experts. Innovations in Theoretical Computer Science Conference (ITCS), volume 11, 2020.
Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
Nicolo Desa-Biaacch and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Sarah Flood, Miriam King, Renae Rodgers, Steven Ruggles, and J. Robert Warren. D030. V8.0- IPUMS ipums.org. atttps//wwat ipums wwappuus.orgg.ooooooo wwt.ooogg//o/eeoo http://s....ppppecc////opppppuee wtspppuuuussssssspeeeeeeeeeeeees cps/dd30s. 3030. 2020.
Yoav Freund, Robert E. 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. STOC '97. pp. 334-343, New York. NY. USA, 1997. Association for Computing Machinery. ISBN 08979 19999918886 8886. doi: 10.1145/258333.2586111 /ttps:
1145/258533.1 258616
Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multicali- bration and omniprediction. arXiv preprint (=XXi:230700899) 2023.
Ira Globus-Harte Michael Kearns, and Aaron Roth. An algorithmic framework for bias bounties. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 1106-1124, 2022.
Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Mul- ticalibration as boosting for regression. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Confer- ence on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 11459-11492 PMLR, 2023. URL s23a. htm
https::/proceest: ing.eeniingg........ m wttpppesse//////obsssssssee http://cceecciagg...rrrrrss////p
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Om- nipredictors. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Schloss Dagstuhl-LLeibin Liibii--eebbniieeeuuu für Informatik, 2022.
Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistiguuisaabiiiyy. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss Heaistuul-LeibiiiZeeeeee für Informatik, 2023.
10

---

Published as a conference paper at ICLR 2024
Ursula Hébert-Johnson. Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cali- bration for the cnapputationlll--innftttaa masses. In International Conference on Machine Learning, pp. 1939-1948. PMLR, 2018.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307 2005.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International conference on machine learning, pp. 2572-2572. PMLR, 2018.
Brett Lantz. Medical Cost Personal Datasets kaggle.com, 2013. URL httpp::/www.....
com/ hoom/datasets//mm richoii 00110/ /ai////nnnanneeeee
Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. Online minimax multiobjective optimiza- tion: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 35:29051-29063, 2022.
Haipeng Luo and Robert E, Schapire. Achieving all with no parameters: Adaptive normalhedge, 2015.
Guy N Rothblum and Gal Yona. Multi-group agnostic pac learnability. In International Conference Machine Learning, pp. 9107-9115. PMLR, 2021.
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning, In International Conference on Machine Learning, pp. 2159-2168. PMLR,
2016.
Christopher Tosh and Daniel Hsu. Simple and near-optimal algorithms for hidden stratification and multi-group learning. In International Conference on Machine Learning, pp. 21633-21657. PMLR, 2022.
A ORGANIZATION
The Appendix is organized as follows. Appendix B contains description of the sleeping experts setting and the AdaNormalHedge algorithm. Appendix Contains the proof of Theorem Regret curves for the synthetic data with the 3 other label aggregations functions: min, max, permutation are in Appendix D.I D.2 and D.3 respectively. In Appendix (.4 D.5 we provide detailed plots for the 2 real datasets: Medical cost and Adult income respectively. Appendix Fi provides tables with regret at the end of each subsequence, along with cumulative loss of the best linear model for all the experiments. Appendix
Appendix[Fccompares []compares including/cxcluding the always active expert in our algorithm. Lastly, Appendix G Conntains the binary classification with apple-tasting feedback results.
B SLEEPING EXPERTS, ADANORMALHEDGY
For completeness, here describe the sleeping experts setting (Freund et al. 1997) and the AdaNor- malHedge algorithm of Luo & Schapire (2015) with its regret guarantee. Infact, Nddoornale provides a regret guarantee even in the confidence-rated setting i.e., (t) E [0, 1] (Blum Mansour
2007 Luo & Schapire, 2015), a generalization of sleeping experts. The following is the interaction protocol in the sleeping experts setting.
1. At the start of each round t., each expert (I I) reports if it's awake asleep i.e., will it make prediction (t) 1) or not (1) = 0)
2. The learner plays each expert according to a probability distribution pt. with the natural restriction that if the expert / is asleep Pt. = 0.
3. The loss L,, for those experts who made predictions are revealed and the player suffers loss
' (p: f.). The instantaneous regret to expert I, r., e T(I) ler))
We overload to denote both the index of the sleeping expert as well as the indicator representing whether the expert is awake or not.
11

---

Published as a conference paper at ICLR 2024
AdaNormalHedge (Sec 4, Luo & Schapire (2015) sets the probability distribution
Pt, x
(tt) w (Be-1,1, C2-1.1)
(2)
Where R1- - - ft, is the sum of instantaneous regret; and C,-1,1 of absolute values of instantaneous regret. The weight function w C) R R is defined as
[ the sum
wRR, C) _ exp
(exp (=xx(.
(3C+1]] ("((()1)))) Note that at the start, i.e., 0. for all
3(+1)
exp
experts Ro. = Co.1 =
With the probability set in equation 2 AdaNormalHedge provides the following regret guarantee to each expert I, which scales sublinearly in the total number of times expert / is awake:
T
T
Σ ((t) (pr, ki) - Σ E
((t) lus s O log( I
(3)
1=1
C PROOF OF THEOREM
Our algorithm uses the AdaNormalHedge algorithm of Luo & Schapire 2015). AdaNormalHcdge is an online prediction algorithm, that given finite benchmark set of [Z] policies and [Z] time selection functions, guarantees subsequence regret upper bound of O( (TV TT log [ with running time that polynomial in [Z] and the size of the contexts that arrive in each round. We refer to meta-experts ierzz as policies even though they themselves algorithms, and not policies mapping contexts to predictions, however, the output of each one of these algorithms in any time step are policies in H mapping contexts predictions. Therefore, when algorithm picks Z r as the policy to play in round, it is in fact picking the policy 2/ that is the output of algorithm 2 in that round.
Thus, the running time claim follows from the construction of Algorithm[] [
We introduce notation separating the independent random coins used by each of the algorithms used in our procedure. In the 1-th round, each meta-expert algorithm 3, draws a randomized policy pd using random coins D The instantiation of ANH picks policy Pr from among the above policies based upon random coins D. Each algorithm's 's random coins are independent of cach other. By appealing to the regret guarantees of each algorithm Z and taking the expectation only over the random coins used by these algorithms, we get the following for each subsequence I:
ED [(t)))l())))))) min
JEH Σ E(0e)(())))))) S a1
(4)
where pf the (randomized) policy suggested by the algorithm 3, and T =, T(t). Note that the actual prediction (x(x)) made by Algorithm | might differ from p (zx). however since the can still call upon it to measure the
regret guarantee holds for arbitrary adversarial sequences, expected regret of hypothetically using this algorithm's prediction on the corresponding subsequence. Importantly, update the algorithm 2 with the true label ye every round only where the subsequence is active.
Next, we appeal the regret guarantee of algorithm Z. Before doing so, fix the realization of the offered expert pf as z/ from each meta-expert 3, i.e. we do the analysis conditioned upon the draw of internal randomness used by each meta-expert. In particular, our analysis holds for every possible realization of predictions pf offered by each of the meta-experts over all the rounds. Since our algorithm updates the loss of each meta-expert with respect these realized draws of the meta-experts, therefore, we use the subsequence regret guarantee of Z (i.e the results about AdaNormalHedge in Luo & Schapire (2015) for each subsequence I to get:
ED Σ ((t))(p((zz))
Σ r(eees (x)), 0 ( (VTT)oo(((I)
(5)
where the expectation is taken only over the random coins D used by AA to select which meta-expert to use in each round. Since the inequality (nequality5hholds holld for every realization of the randomness used by the meta-experts, the same inequality holds in expectation over the random coins D used by the corresponding meta-expert:
12

---

Published as a conference paper at ICLR 2024
EIDSDD Σ ((())) Epr Σ {
E((eeee) oo
( (VTr
(6)
Inequality 4 will also hold when we additionally take the expectation over the random coins used by the copy of ANH, since D' is independent of D. Thus, putting together 4nd 6 this proof gives us (for each subsequence I):
Bie.D'eD Σ (())(p(
min Σ ((OEL(()))))))) S s + O log((Z)) /EH
where the expectation is taken over the product distributions of random coins used by all the algorithms.
D ADDITIONAL FIGURES
On the synthetic data with the 3 other aggregation rules: min, max, permutation; the plots and qualitative inferences are similar to the mean aggregation Section 5.2 i.e., across all the groups see that our algorithm has significantly lower regret than the baseline, which in fact has linearly increasing regret Thus, here, we only discuss quantitative values such as the magnitudes of the cumulative loss, and difference between the cumulative loss of the baseline and our algorithm.
D.1 SYNTHETIC DATA MIN
Recall here that the label of any individual is the minimum of the intermediary labels of the groups it's a part of. Quantitatively, the rough magnitude [2 of the cumulative loss of the best linear model in hindsight is ~ 79, and our algorithm's cumulative loss is ~ 48 units lower than the baseline, which is significant decrease.
(a) Shape: Circle
(b) Shape: Square
(c) Shape: Triangle
14400
30740
45700
600 124 (140 3780 Vilar wile
2750
(d) Color:
Green
(c) Color: Red
(f) Always on
Figure 3: Regret for the baseline (blue) & algorithm (orange) synthetic data with minimum of intermediary labels, our algorithm always has lower regret than the baseline.
D.2 SYNTHETIC DATASET MAX
Recall here that the label of any individual is the maximum of the intermediary labels of the groups it's a part of. Quantitatively, the rough magnitude [3] of the cumulative loss of the best linear model in
"On the always group, the baseline has sublinear growth, have discussed this phenomenon in See 5.2
12 Exact values provided in Appendix F
table
Exact values provided in Appendix F table
13

---

Published as a conference paper at ICLR 2024
hindsight is 59, and our algorithm's cumulative loss is ~ 34 units lower than the baseline, which is a significant decrease.
1208
26
1868
LOGE
(a) Shape: Circle
(b) Shape: Square
(c) Shape: Triangle
Fdd
-10
60/00
12.00 T140 2na0 p0an yola
2500
(d) Color:
Green
(c) Color: Red
(f) Always on
Figure 4: Regret for the baseline (blue) & algorithm (orange) on synthetic data with maximum of intermediary
labels, algorithm always has lower regret than the baseline.
D.3 SYNTHETIC DATASET PERMUTATION
Recall here there is an underlying fixed ordering or permutation over the groups, and the label of any individual is decided by the linear model corresponding to the first group in the ordering that this individual a part of. The permutation (chosen randomly) for experiments in Figure 3 (1:green, 2:square, 3:red, 4:triangle, 5:circle). Let's see two simple examples to understand this aggregation: For an individual which which is green square we use the intermediary label for green.
red square we use the intermediary label for square, for an individual
Quantitatively, the rough magnitude 14 of the cumulative loss of the best linear model hindsight 94, and our algorithm's cumulative loss is 93 units lower than the bascline, which is significant decrease.
14 Exact values provided in Appendix E Etable
14

---

Published as a conference paper at ICLR 2024
spand
trange
Shape: Circle
Shape: Square
(c) Shape: Trianglc
-15
10000
10:0 ubo aodo aVD
(d) Color: Green
(e) Color: Red
(1) Always
Figure 5: Regret baseline (blue) our algorithm (orange) on synthetic data with permutation aggregation of intermediary labels, our algorithm always has lower regret than the baseline
D.4 MEDICAL COSTS DATASET
For the medical cost data we have already discussed the rough quantitative results in Section 5.3 for Here discuss regret curves for the baseline and our algorithm
exact values Appendix table 5 on all the groups
Regret on age, sex groups On all three age groups: young, middle, old (Fig 6). and both groups: male, female (Fig [ our algorithm has significantly lower regret than the baseline, in fact, our algorithm's 's regret negative and decreasing over time. i.c. our algorithm outperforms the best linear regressor in hindsight. This qualitatively matches the same phenomenon occurring in the synthetic data.
324
-22
-330
43
(a) Age: Young
(b) Age: Middle
(c) Age: Old
Figure Age groups
15

---

Published as a conference paper at ICLR 2024
0.0
-18
(a) Sex: Male
(b) Sex: Female
Figure 7: Sex groups
Regret on smoker, bmi groups For both smokers and non smokers (Fig 8). and all four bmi groups: underweight, healthyweight, overweight, obsese (Fig our algorithm has significantly lower regret than the baseline, which in fact has linearly increasing regret.
028
(a) Smoker: Yes
(b) Smoker: No
Figure Smoking groups
incewiggt
commagtt
1.80
1.0
(a) Bmi: Underweight
(b) Bmi: Healthyweight
(c) Bmi: Overweight
(d) Bmi: Obese
Figure Bmi groups
Regret on the always-on group Fig 10 our algorithm's 's regret is negative and decreasing with time, i.c., it outperforms the best linear regressor in hindsight. The baseline's regret evolves sublinearly, this matches the same phenomenon occurring in the synthetic data in Section Fig (f).
16

---

Published as a conference paper at ICLR 2024
Figure 10: Always on
D.5 ADULT INCOME DATASET
Dataset description The Adult income dataset is targeted towards income prediction based on census data. Individual features are split into: 5 numeric features, (hours-per-wedd age, capital-gain, capital-loss, educaticn-num); and 8 categoric features, (workclass, education, native couutrr,, occupation). The dataset also contains a real-valued income column that we use as our label.
relationsh.
race, sex,
Data pre-processing All the numeric columns are min-max scaled [0,1], while all the categoric columns are one-hot encoded We also pre-process the data to limit the number of groups we are working with for simplicity of exposition. In particular, we simplify the following groups:
1. We divide the age category into three groups: young (age S 35), middle (age e (35, 50]), old (age>> 50)
2. We divide the education level into groups: at most high school versus college or more.
3. For sex, we directly use the 2 groups given in the dataset: male, female.
4. For race, we directly use the 5 groups given in the dataset: White, Black, Asian-Pac- Pac--sannerrr Amer--ndiaan-skimng Other.
Quantitatively, the rough magnitude 16 of cumulative loss of the best linear model in hindsight is 568, and our algorithm's cumulative loss is 14 units lower than the baseline, there is decrease but not as significant as for the other datasets. This may be because in this case, conditional on having similar features, group membership is not significantly correlated with income; in fact, observe in our data that different groups have relatively similar best fitting models. This explains why ane-size-fits-all external regret approach like Azoury & Warmuth (200T) has good performance: one can use the same model for all groups and does not need to fit a specific, different model to each group.
Regret on age groups On all three age groups: young, middle, old (Fig 11 our algorithm has lower regret than the baseline.
yourg
(a) Age: young
(b) Age: middle
(c) Age: old
Figure 11: Age groups
Regret on education level groups For both the education level groups: atmost high school and college or more (Fig 12). our algorithm has lower regret than the baseline.
15 adull reconstruction.csv at https: ://:///// //gtthb.... cow/social foundat foundations/folkaatlee.
16Fxact values provided in Appendix P table
17

---

Published as a conference paper at ICLR 2024
Do ayatba
Cokgosmnrr
14-
Education: most High school
(b) Education: college more
Figure 12: Education level groups
Regret on sex groups On both the sex groups: male and female (Fig 13 our algorithm has lower regret than the baseline
(a) Sex: male
(b) Sex: female
Figure 13: Sex groups
Regret on race groups On all race groups: White, Black, Asian-Pac-Ishae Pac-Islander, Amer-Indian- Indian-Eskimoo Other (Fig 14 our algorithm has lower regret than the baseline.
(a) Race: White
(b) Race: Black
(c) Race: Asian-Padd Pac--Paa---eeeeeee Islanderr
140
250
340
(d) Race: Amer-Indian-Eskimo
(c) Race: Other
Figure 14: Race groups
Regret always-on group In Fig 15 our algorithm's 's regret is negative and decreasing with time, ie., it outperforms the best linear regressor in hindsight. The baseline's s regret evolves sublinearly, this matches the same phenomenon occurring in the synthetic data in Section 5.2 Fig 2 (f)
18

---

Published as a conference paper at ICLR 2024
Figure 15:
Always on
E TABLES
these tables, for given group we record: its size, regret for the baseline, regret for our algorithm, and the cumulative loss of the best linear model in hindsight. Since the baseline and our algorithm are online algorithms we feed the data one-by-one using 10 random 17 shuffles, and standard deviation. Note that the cumulative loss of the best linear model in hindsight will be the same across all the shuffles, since it's just solving for the least squares solution on the entire group subsequence.
"andon""shuffllss, recording the mean
Cumulative loss of best linear model in hindsight
Baseline's regret
Our algorithm's regret
Group name
Group size
circle
49857
15.25 + 0.22
0.73 0.09
23.57
square
30044
15.43 + 0.13
0.63 + 0.06
14.12
triangle
20099
12.13 0.10
0.76 + 0.04
9.43
green
59985
10.02 + 0.15
-14.13 + 0.19
38.81
red
40015
14.75 + 0.16
-1.80 + 0.17
26.37
always on
100000
0.76 + 0.06
-39,93 + 0.10
89.18
Table Synthetic data with mean of intermediary labels
Cumulative loss
Baseline's regret
Our algorithm's regret
Group name
Group size
of best linear
model in hindsight
circle
49857
21.62 + 0.28
0.81 + 0.10
63.49
square
30044
64.21 +0.31
0.94 1 0.05
15.17
triangle
20099
12.47 + 0.13
0.57 + 0.07
26.37
green
59985
14.55 + 0.19
-43.10 + 0.23
97.42
red
40015
21.64 + 0.20
-16.69 1 0.23
69.72
always_on
100000
1.04 1 0.06
-94.94 1 0.08
202.29
Table 2: Synthetic data with min of intermediary labels
available http:////hhta..oooooooooooaaaaaa
19

---

Published as a conference paper at ICLR 2024
Cumulative loss
Baseline's regret
Our algorithm's regret
Group name
Group size
of best linear
model in hindsight
circle
49857
22.78 + 0.32
0.91 + 0.07
32.46
square
30044
17.86 + 0.14
0.52 + 0.08
36.92
triangle
20099
29.51 + 0.22
0.87 + 0.05
9,42
green
59985
8.65 + 0.20
-23.25 = 0.24
65.38
red
40015
12.48 + 0.22
-23,46 + 0.29
62.42
always_on
100000
0.86 0.08
-66.98 + 0.13
148.08
Table 3: Synthetic data with max of intermediary labels
Cumulative loss
Baseline's regret
Our algorithm's s regret
Group name
Group size
of best linear
model in hindsight
circle
49857
28.84 + 0.45
-38.63 + 0.17
77.14
square
30044
92.10 + 0.64
-0.28 = 0.27
54.87
triangle
20099
12.03 + 0.20
-15.15 + 0.09
30.67
green
59985
75.89 + 0.89
1.31 = 0.07
28.95
red
40015
112.49 + 0.88
0.04 0.26
78.32
always on
T00000
1.26 + 0.09
-185.77 + 0.25
294.39
Table 4: Synthetic data with permutation of intermediary labels
Cumulative loss
Baseline's s regret
Our algorithm's regret
Group name
Group size
best linear
model in hindsight
young
574
0.55 + 0.14
-1.58 = 0.18
5.40
middle
408
0.38 = 0.15
-0.97 0.16
3.34
old
356
0.44 0.18
-0.64 0.19
3.13
underweight
20
0.16 + 0.02
0.11 + 0.02
0.03
healthyweight
225
1.59 0.14
0.36 0.07
1.00
overweight
386
1.55 0.17
0.43 0.07
1.84
obese
707
0.31
1.25 0.12
3.65
smoker
274
5.06
1.47 = 0.09
0.90
non-smoker
1064
0.15
0.73 0.13
5.57
male
676
0.65 0.21
-1.75 + 0.21
6.11
female
662
0.59 0.24
-1.57 0.24
5,88
always_on
1338
1.13 + 0.09
-3.43 0.13
12.10
Table 5: Medical costs data
20

---

Published as a conference paper at ICLR 2024
Cumulative loss of best linear model hindsight
Baseline's regret
Our algorithm's regret
Group name
Group size
young
22792
37.40 1.04
14.01 0.41
421.89
middle
16881
20.11 + 1.11
14.93 = 0,63
608.15
old
9858
22.99 + 0.74
14.81 0.75
414.61
HighSchool&less
22584
33.02 + 1.21
14.38 0.51
499.55
College&more
26947
28.67 + 1.54
10.55 = 1.08
963.92
Male
33174
20.95 0.86
-2.17 + 0.77
1171.06
Female
16357
18.82 + 0.54
5.19 + 0.69
314.32
White
42441
14.67 + 0.76
-17.42 + 0.98
1325.50
Asian-Pacc -alaner
1519
5.82 0.23
4.66 + 0.21
55.05
Amer-Indian- Eskimo
471
3.55 0.12
3,48 + 0.44
9.04
Other
406
3.28 = 0.24
3.21 + 0.24
7.50
Black
4694
6.16 = 0.39
2.79 + 0.36
94.58
always_on
49531
18.25 + 0.66
-18.51 + 0.94
1506.92
Tahle 6: Adult income data
EFFECT OF ADDING AN ALWAYS ACTIVE EXPERT OR NOT ON OUR ALGORITHM
Throughout in the earlier sections, we include an "always on" expert in Algorithm as in terms of theory, doing so provides a regret bound over the entire sequence, which does not follow generically from having regret bounds for subsequences [8] Here in tables algorithm when including/excluding the "always on" expert and see that the effect is marginal, with both these variants being much better than the baseline.
12 we compare the regret of our
Regret of our algorithm including always active
Regret of our algorithm excluding always active 0.66 = 0.09
Cuml loss of best linear model
Baseline's ss regret
Group name
Group size
circle
49857
15.25 + 0.22
0.73 + 0.09
23.57
square
30044
15.43 = 0.13
0.63 + 0.06
0.56 = 0.06
14.12
triangle
20099
12.13 0.10
0.76 + 0.04
0.73 + 0.04
9.43
green
59985
10.02 0.15
-14.13 0.19
-14.23 0.16
38.81
red
40015
14.75 + 0.16
-1.80 + 0.17
-1.86 + 0.14
26.37
always_on
100000
0.76 + 0.06
-39.93 1 0.10
-40.10 1 0.09
89.18
Table Synthetic with mean intermediary labels
Regret of our algorithm including always active
Regret of our algorithm excluding always active
Cuml loss of best linear model
Baseline's regret
Group name
Group size
circle
49857
21.62 +0.28
0.81 + 0.10
0.77 1 0.10
63.4 43.49
square
30044
64.21 + 0.31
0.94 + 0.05
0.83 + 0.05
15.17
triangle
20099
12.47 + 0.13
0.57 +:2 0.07
0.60 = 0.06
26.37
green
59985
14.55 + 0.19
-43.10 = 0.23
-43.19 + 0.21
97.42
red
40015
21.64 = 0.20
0.20
-16.69 = 0.23
-16.72 + 0.21
69.72
always_on
100000
1.04 + 0.06
-94.94 = 0.08
-95.06 + 0.08
202.29
Table 8: Synthetic data with min of intermediary labels
If there are subsequences that partition the entire sequence, then one gets a regret bound on the entire sequence that follows from summing up the regret bounds on the partition, but this is wasteful. If the subsequences do not partition the space, then there is not necessarily regret bound on the entire sequence without including the "always on" on" expert
21

---

Published as a conference paper at ICLR 2024
Regret of algorithm including always active
Regret of algorithm excluding always active
Cuml loss of best linear model
Baseline's regret
Group name
Group size
circle
49857
22.78 + 0.32
0.91 +0007
0.86 + 0.07
32.46
square
30044
17.86 + 0.14
0.52 + 0.08
0.45 +0.07
36.92
triangle
20099
29.51 = 0.22
0.87 + 0.05
0.80 = 0.05
9.42
green
59985
8.65 + 0.20
-23.25 + 0.24
-23.30 1 0.23
65.38
red
40015
12.48 = 0.22
-23.46 0.29
-23.59 0.28
62.42
always_on
100000
0.86 = 0.08
-66.98 = 0.13
-67.17 = 0.12
148.08
Table 9: Synthetic data with max of intermediary labels
Regret our algorithm including
Regret of our algorithm excluding always active
Cuml loss of best linear model
Baseline's regret
Group name
Group size
always active
circle
49857
28.84 0.45
-38.63 + 0.17
-38.66 0.21
77.14
square
30044
92.10 0.64
-0.28 0.27
-0.33 + 0.32
54.87
triangle
20099
12.03 + 0.20
-15.15 + 0.09
-15.11 + 0.08
30.67
green
59985
75.89 0.89
1.31 + 0.07
1.27 + 0.07
28.95
red
40015
112.49 + 0.88
0.04 0.26
0.05 = 0.27
78.32
always_on
100000
1.26 + 0.09
1185.77 = 0.25
-185.81 + 0.25
294.39
Table 10: Synthetic data with permutation of intermediary labels
Regret of our algorithm including always active
Regret of our algorithm excluding always active -1.33 0. 1.18
Cuml loss best linear model
Baseline's regret
Group name
Group size
young
574
0.55 + 0.14
-1.58 + 0.18
5.40
middle
408
0.38 + 0.15
-0.97 + 0.16
-0.99 + 0.17
3.34
old
356
0)44 + 0.18
-0)64 + 0.19
-0.64 + 0.19
3.13
underweight
0.16 + 0.02
0.11 = 0.02
0.11 0.02
0.03
healthyweight
225
1.59 + 0.14
0.36 = 0.07
0.34 1 0.06
1.00
overweight
386
1.55 $55:000 0.17
0.43 + 0.07
0.40 + 0.06
1.84
obese
707
3.42 0.31
1,25 = 0.12
1.24 0.12
3.65
smoker
274
5.06 0.17
1.47 0.09
1,43 1 0.09
0.90
non-smoker
1064
1.70
0.73 + 0.13
0.71 + 0.14
5.57
male
676
0.65 + 0.21
-1.75 + 0.21
-1.79 0.21
6.11
female
662
0.59 1 0.24
-1.57 + 0.24
-1.59 0.24
5.88
always
1338
1.13 + 0.09
-3.43 + 0.13
-3.49 + 0.13
12.10
Table 11: Medical costs data
22

---

Published as a conference paper at ICLR 2024
Regret of our algorithm including always active
Regret of algorithm excluding always active
Cuml loss of best linear model
Baseline's regret
Group name
Group size
young
22792
37.40 + 1.04
14.01 + 0.41
13.79 + 0.40
421 .99
middle
16881
20.11 + 1.11
14.93 0.63
14.70 0.82
608.
old
9858
22.99 + 0.74
14.81 = 0.75
14.59 + 0.97
414.61
HighSchool&less
22584
33.02 + 1.21
14.38 1 0.51
14.05 1 0,42
499.55
College&more
26947
28.67 + 1.54
10.55 1.08
10.21 1.03
963.92
Male
33174
20.95 + 0.86
-2.17 = 0.77
-3,46 + 0.63
1171.06
Female
16357
18.82 + 0.54
5.19 + 0.69
5.81 + 0.81
314.32
White
42441
14.67 0.76
-17.42 + 0.98
-19.10 = 0.93
1325.50
Asian-Pac Paatt-Pac-sslaaer
1519
5.82 + 0.23
4.66 0.21
5.06 + 0.42
55.05
Amer-Indiang Eskimo
India--Eskimoo
471
3.55 + 0.12
3.48 1: 0.44
3,80 0.41
0.41
9.04
Other
406
3.28 0.24
3.21 + 0.24
3.41 + 0.27
7.50
Black
4694
6.16 = 0.39
2.79 + 0.36
2.88 = 0.44
94.58
always_on
49531
18.25 1 0.66
-18,51 + 0.94
-19.18 = 0.99
1506,92
Table Adult income data
G APPLE TASTING MODEL
In the apple tasting model for binary classification (n 1), we only see the label Ye at the end the t-th round if the prediction Pr is to "accept", i.c..p = 1. We present results in generalization of this model, introduced by Blum & Lykouris (020), called the Pay-for-feedbar algorithm is allowed pay the maximum possible loss of 1 at the end of the t-th round to the label yt- The sum of all the payments is added to the regret expression to create a new objective that wish to upper bound. For some notation e is the indicator variable that is set if pay to view the label at the end of round I. This new objective is written down below-
model. this model,
Groupwise Regret with Pay-for-feeback
E Σ ge (((()((p mx)
min Σ ())(())((())).)))) SEF,
Blum & Lykouris (0200) introduce a blackbox method that converts any online algorithm with regret for group g upper bounded by O(vTg) (other terms not dependent on T. multiply with this expression) into an algorithm with a corresponding bound in the pay-for-feedback model. This method is based upon splitting the time interval T' into number of equal length contiguous sub- intervals and randomly sampling a time step in each sub-interval for which pays for feedback. Using this method on top of our algorithm, we derive the following corollary.
Corollary 5. There exists oracle efficient online classification algorithm in the pay-for-feedbee model for concept classes with small separator sets (size 8) with groupwise regret upper bounded by O (T)/0 / (V..VV3)
(Ty.
23/2log /////2
[F|] /log [GI) (for group gt).
23


Reviews:
[{"review_id": "3Yq5dtDhFH", "reviewer": "Reviewer_6fRD", "summary": "The paper considers the problem of minimizing the group regret, where the goal is to minimize the regret with respect to each subsequence of trials in the pre-defined group simultaneously. Based on AdaNormalHedge, the authors propose an algorithm for the problem. The experimental results are also shown.", "questions": "It would be nice if you could comment on my concerns about the proof of Theorem 2.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "The topic is relevant to the machine learning community as it reflects the multi-objective nature of online prediction problems. The experimental results show the proposed method works well in practice. The experimental results show the superiority of the proposed method against baselines.", "weaknesses": "I am afraid that the proof of the main theorem (Theorem 2) might be wrong, or at least incomplete. Simply put, the algorithm aggregates sleeping experts where each sleeping expert is awake only when the trial belongs to a designated subsequence of trials. Then, the theorem trivially holds when each subsequence of trials is disjoint to each other, as mentioned in the paper. On the other hand, if subsequences intersect, it is not fully clear if the proof is correct.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Ftw2WRxVT4", "reviewer": "Reviewer_vWf7", "summary": "The paper studies the problem of online prediction, where at each time step, a new example arrives, and the learner has to make a prediction. The goal is to minimize regret not just overall, but also simultaneously for different subgroups defined based on features. A previous algorithm for this problem (Blum & Lykouris, 2019) provides regret guarantees but is computationally inefficient when the hypothesis class is large. The work proposes a modification to the algorithm of Blum & Lykouris (2019) that reduces the problem to the problem of external regret minimization. The new algorithm uses a significantly smaller number of experts for making the decision at the time step. The algorithm is applied to problems like online linear regression, classification with small separator sets, and linear optimization. Experiments on synthetic and real datasets show substantially lower error and regret compared to standard online learning algorithms.", "questions": "See questions.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "While building on prior work by Blum & Lykouris (2019), the paper introduces a simple yet meaningful modification that enhances computational efficiency. This facilitates the use of large hypothesis classes, such as linear models. The reduction to standard external regret minimization, while expected, remains theoretically novel.\n\nThe algorithm's design and analysis are technically sound, and the paper offers a comprehensive set of experiments.\n\nThe paper is well-written and easy to follow, with the problem being well-motivated.\n\nAchieving regret guarantees across groups is pivotal. This paper renders it feasible for large model classes, broadening the applicability of these methods.\n\nIn summary, this paper presents a theoretically grounded, significant contribution, backed by robust experimental validation.", "weaknesses": "I believe that including an experimental comparison with the Blum & Lykouris (2019) approach would better justify the superiority of the new method. Is it possible to conduct such a comparison using a smaller model class?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "yr0aMBsyZ8", "reviewer": "Reviewer_eJaJ", "summary": "The paper studies efficient and practical algorithms for group-wise regret-minimization online learning. The problem is a variate of the classical online problem, in which a hypothesis class $H$ is fixed, and a sequence of individuals/features ${x_{1}, \\cdots, x_{T}}$ and their labels ${y_1, \\cdots, y_T}$ are chosen by an adversary. The algorithm has to make predictions at each time step $t \\in [T]$. The classical notion of measuring a ''good’’ algorithm is *regret*, which is defined as the cumulative gap between the cost induced by the online learning algorithm and the cost induced by the best fixed model in the hypothesis class. The group-wise regret minimization problem further requires binding the regret for each group, which, mathematically, can be viewed as a collection of subsequences indexed by the ``mapping’’ of different groups. \n\nThe work of BL [ITCS’20] has shown that it is possible to achieve small regret w.r.t. the best model $f_{g}$ for every fixed group $g$ by reducing the problem to the sleeping expert problem. This implies for a large family of online learning problems, there exist algorithms with group-wise $1+o(1)$-multiplicative regret that run in time polynomial of $|G|$ and $|H|$. However, while the size of $G$ is usually small, even some ``elementary’’ models, e.g., linear models, have quite large sizes of $H$, which prevents the algorithm of BL [ITCS’20] from being practical. \n\nThe main contribution of the paper is to improve the runtime of the group-wise regret minimization algorithm of BL [ITCS’20], and, in particular, remove the dependence on $|H|$ for the run time. To this end, the paper observes that we can actually solve each policy sub-sequence by external regret algorithms, which require far less time to compute, and treat each ``expert’’ in the overall algorithm as the output of the external regret algorithms. In doing so, the algorithm avoids enumerating over the hypothesis class $|H|$, and only scales w.r.t. $|G|$. The paper then provides some implementations on both synthetic and real-world datasets, and the experimental results of their algorithms are strong.", "questions": "Is your notion of computationally efficient in Theorem 1 defined as polynomial time in $T$, $d$, and $n$ (or some other input-related size)? If I understand correctly, what you want to say is that it is reasonable to assume $|G|$ is of polynomial sizes of the input, but $|H|$ is usually quite large. Therefore, your algorithm that does not scale with $|H|$ implies poly-time efficiency.\n\nI don’t quite understand the term ``diminishing/vanishing regret’’ – in your Theorem 2, the term $\\sqrt{T_{T} \\log(|G|)}$ is not $o(1)$ itself. Are you implicitly enforcing a lower bound on the $\\alpha_{I}$? \n\nA MISC comments: The discussion on the technical front by comparing your work with BL [ITCS’20] looks nice. I think you can expand this discussion to give more details, and present it earlier in the paper.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "Overall, I like this paper as it provides the practical algorithm for a problem where the existence of the solution (or even, a theoretically-efficient algorithm) has been known, but no practically-efficient algorithm was proposed. This serves as a nice ``bridge’’ between theory and practice. As the paper itself has mentioned, practical group-wise regret-minimization algorithms have various downstream applications, including algorithmic fairness. \n\nI also read through the analysis in Appendix B, and I think they are correct, barring some presentation issues (mentioned in the ``weakness’’ section). Although the technical idea is simple and somehow straightforward to come up with, I do think the result itself is neat and cute. Finally, the experimental results of the paper are quite strong, although the comparison is somehow tailored to your algorithm since the benchmark as they are not designed for group-wise regret minimization.", "weaknesses": "One criticism I have when reading the paper is that the paper is not presented in a fully self-contained and rigorous manner. For instance, the proposed algorithm uses AdaNormalHedge as a black box, but the guarantee of such an algorithm is never formally described. (I am aware of the description in Appendix B, but there is no proposition + proper citation for this.) Similarly, when citing external regret minimization algorithms for applications, the formal quantifiers and guarantees for those algorithms are not provided.\n\nSimilarly, the introduction is written in a very informal way. I understand this might be a result for the authors to accommodate the broader readership of the conference; however, I think it actually adds to confusion. For instance, when defining the notion of diminishing group-wise regret, it would be much more helpful to include the actual mathematical definition of ''squared error’’ and ''best model in H on that sequence’’. (Also, why the notion is limited to squared error but not general loss functions?) \n\nThe same applies to the statement of Theorem 1, in which the notion of ``computationally efficient’’ is not defined(!) The phrase ''best model on hindsight’’ is used in a very informal way – I think you should properly define this notion (overall vs. on group-wise sequences) with the proper quantifiers. \n\nA note for presentation problems in Appendix B: the usage of expectation notation $\\mathbb{E}[]$ is rather confusing in this section. Your derivation crucially relies on the control of which coins the expectation is taken upon. I think in this case, the expectation notation should have subscript explicitly stating the source of randomness. Furthermore, the way you talk about $p_{t}^{I} $ vs $z_{t}^{I}$ is not rigorous enough. If I understand it correctly, $p_{t}^{I}$ is a random variable whose supports are some realizations denoted as $z_{t}^{I}$. In light of this, should the term in the first inequality be $\\mathbb{E}[\\sum_{t} I(t) \\ell(p_{t}^{I}, y_{t})]$? Overall, I do think this section has quite some room for improvement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "H5wOJj8TG4", "reviewer": "Reviewer_1CJx", "summary": "This work studies an online learning problem in which at each time step a context is obtained that indicates the point belongs to some groups (possibly more than one at the same time). At the end of the game we want to have low regret on all subsequences of points belonging to the same group. The point of this work is that a solution can be build in cases in which the model class is large. A previous algorithm existed that would only handle small model classes. An empirical evaluation is provided.", "questions": "It is not obvious that you should have an \"always active\" subsequence in order to perform well empirically. It would be good if it is reported that the algorithm does not work so well if this is not present, so others people that want to implement this can take this fact into account.\n\nTheorem 1 and Theorem 3 say essentially the same. It's redundant.\n\nMinor\n\nIn the abstract there is \"\\{1, 2, \\cdots T\\}\" comma missing after \\cdots.\n\n\"low order regret terms\" -> \"low-order regret terms\" \n\nThm 1 (informal): contains \"of of\"\n\n\"to each Individual\" remove capitalization.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The strength of this paper is obtaining what is claimed in theorem 1 about algorithm 1. Another one is the empirical evidence provided, that checks that the algorithm indeed behaves how it was supposed to do.", "weaknesses": "The main weakness of this work is its marginal contribution. Beyond their empirical evidence their contribution is limited to the proof of theorem 2, which is a small step on top of the existing framework of Blum and Lykouris, almost a remark. Still, it could be a publication, I'm giving a weak accept because of this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)