On-Demand Sampling: Learning Optimally from Multiple Distributions
Authors: Nika Haghtalab
Michael Jordan
Eric Zhao
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sample Complexity
Distributionally Robust Optimization
Collaborative Learning
Learning Theory
Minmax Equilibria
Online Mirror Descent

Abstract: Societal and real-world considerations such as robustness, fairness, social welfare and multi-agent tradeoffs have given rise to multi-distribution learning paradigms, such as collaborative [Blum et al. 2017], group distributionally robust [Sagawa et al. 2019], and fair federated learning [Mohri et al. 2019]. In each of these settings, a learner seeks to minimize its worstcase loss over a set of $n$ predefined distributions, while using as few samples as possible. In this paper, we establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Importantly, our sample complexity bounds exceed that of the sample complexity of learning a single distribution only by an additive factor of $\frac{n\log(n)}{\epsilon^2}$. These improve upon the best known sample complexity of agnostic federated learning by Mohri et al. 2019 by a multiplicative factor of $n$, the sample complexity of collaborative learning by Nguyen and Zakynthinou 2018 by a multiplicative factor $\frac{\log(n)}{\epsilon^3}$, and give the first sample complexity bounds for the group DRO objective of Sagawa et al. 2019. To achieve optimal sample complexity, our algorithms learn to sample and learn from distributions on demand. Our algorithm design and analysis extends stochastic optimization techniques to solve zero-sum games in a new stochastic setting.

On-Demand Sampling: Learning Optimally from Multiple Distributions
Nika Haghtalab, Michael I. Jordan, and Eric Zhao
University of California, Berkeley
Abstract
Societal and real-world considerations such as robustness, fairness, social welfare and multi-agent tradeoffs have given rise to multi-distribution learning paradigms, such as collaborative [5], group distributionally robust [36], and fair federated learning [27]. In each of these settings, a learner seeks to minimize its worst- case loss over a set of predefined distributions, while using as few samples as possible. In this paper, we establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Importantly, our sample complexity bounds exceed that of the sample complexity of learning a
single distribution only by an additive factor of n mlog(m) These improve upon the best known sample complexity of agnostic federated learning by Mohri al. [27] by multiplicative factor of n. the sample complexity of collaborative learning by
Nguyen and Zakynthinou [29] by multiplicative factor log and give the first sample complexity bounds for the group DRO objective of Sagawa al. [36]. To
23
achieve optimal sample complexity, our algorithms learn to sample and learn from distributions on demand. Our algorithm design and analysis extends stochastic optimization techniques to solve zero-sum games in new stochastic setting.
1
Introduction
Pervasive needs for robustness, fairness, and multi-agent collaboration in learning have given rise to multi-distribution learning paradigms (c.g., [5, 36, 27, 12]). In these settings, seek to learn a model that performs well on any distribution in pre-defined set of interest. For fairness considerations, these distributions may represent heterogeneous populations of different protected socio-economic attributes; in robustness applications, they may capture a learner's 's uncertainty regarding the true underlying task; and in muti-agen collaborative or federated applications, they may represent agent- specific learning tasks. In these applications, the performance and optimality of a model is measured by its worst test-time performance distribution in the set. We are concerned with this fundamental problem of designing sample-efficient multi-distribution learning algorithms.
The sample complexity of diltiiiiittibttoonn learning differs from that of learning single distribution in several ways. On one hand, learning tasks of varying difficulty require different numbers of samples. On the other hand, similarity or overlap among learning tasks may obviate the need to sample from some distributions. This makes the use a fixed per-distribution sample budget highly inefficient and suggests that optimal multi-distribution learning algorithms should sample demand. That is, algorithms should take additional samples whenever they need them and from whichever distribution they want them. On-demand sampling is especially appropriate when some population data scarce (as in fairness mechanisms in which samples are amended [32]); when the designer can actively
Authors are ordered alphabetically. Addresses: mika@berkeley.edue jordanΩcs. berkeley.eee.. edu,
eric wwwberkeeeey.eeeee. edu.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Problem
Sample Complexity
Thm
Best Previous Result
Collab. Learning UB
(log |H| log()))
[4.1]
log (t)
[H] + r)) [29]
Collab. Learning LB
(log [7d] + log( ())
[4.2]
n (og(k [5]
GDRO/AFL UB
(log |H| + n log ())
[4.1]
(n [H] + + no ()) [27]
GDRO/AFL UB
--2 (Dx + n log(
[5.1] N/A
(Training error convg.)
s-3 (Dx + n log(
[5.2]
D (expected convergence only) [36]
Table 1: This table gives upper (UB) and lower bounds (LB) on the sample complexity of learning model class H on n distributions. For the collaborative learning and AFL settings, the sample complexity upper bounds refer to the problem of learning a randomized model of worst-case error OPT + E or deterministic classifier of worst-case error 2OPT For the GDRO setting, sample complexity refers to learning a deterministic model with worst-case error of R-OPT + E, where R-OPT is the best worst-case error attainable in convex compact model space H. Dy denotes the Bregman radius of H, and of Collaborative and Agnostic federated learning in existing works, extend to VC dimension and Rademacher complexity. Our results also extend to VC dimension under some assumptions.
min {n, log [H Sample complexity bounds
perturb datasets towards rare atypical instances (such as in robustness applications [21, 44]); or when sample sets represent agents' contributions to an interactive multi-agent system [27, 6].
Blum et al. [5] demonstrated the benefit of on-demand sampling in the collaborative learning setting, where all data distributions are realizable with respect to the same target classifier. This line of work established that learning n distributions on-demand takes Ô (log(n)) times the sample complexity of learning a single realizable distribution [5, 8, 29], whereas relying on batched uniform convergence takes Ω (n) times that of learning single distribution [5]. However, beyond the realizable setting, the best known multi-distribution learning results fall short of this promise: existing on-demand sample complexity bounds for agnostic collaborative learning have highly suboptimal dependence on E, requiring Ô (log(n)/E*) times the sample complexity of agnostically learning a single distribution [29]. On the other hand, agnostic federated learning bounds [27] have been studied only for algorithms that sample in one large batch and thus require Ω (n) times the sample complexity of single learning task. Moreover, the test-time performance of some key multi-distribution methods, such group distributionally robust optimization [36]. have not been studied from a provable or mathematical perspective before.
In this paper, we give general framework for obtaining optimal and on-demand sample complexity for three multi-distribution learning settings. Table summarizes our results. All three settings consider set 'D of n distributions and model class H. They evaluate the performance of model h (or distribution over models) by its worst-case performance, max Risk (h). As benchmark, they consider the worst-case loss of the best model, i.e., OPT mink EH MaXDeD Risk Importantly, all of our sample complexity upper bounds demonstrate only an additive increase of e-2n log(n/ 6) over the sample complexity of single learning task, compared to the multiplicative factor increase required by existing works.
Collaborative learning of Blum et al. [5]: For agnostic collaborative learning, our Theo- rem 4.1 gives a randomized and deterministic model that achieve performance guarantees of OPT + E and 2OPT + E, respectively. Our algorithms have an optimal sample complexity of O ( (log( HI) + n log ()). This improves upon the work of Nguyen and Zakynthinou [29] in two ways. First, it provides error bounds of OPT + = for randomized classifiers. where only 2OPT + was previously established. Second, it improves the upper bound of Nguyen and Zakynthinou [29] by a multiplicative factor of log(n)/e*) In Theorem 4.2, we give a matching lower bound on this sample complexity, thereby establishing the optimality of our algorithms.
Group distributionally robust learning (group DRO) of Sagawa et al. [36]: For group DRO, we consider convex and compact model space H. Our Theorem 5.1 studies a model that achieves an OPT + e guarantee on the worst-case test-time performance of the model with an on-demand sample complexity of O (D# + n log( )). Our results also imply bigh--robability bound
2

---

for the convergence of group DRO training enror that improves upon the (expected) convergence guarantees of Sagawa al. [36] by factor of n.
Agnostic federated learning of [27]: For agnostic federated learning, we consider a finite class of hypotheses. Our Theorems 4.1 and 5.1 show that on-demand sampling can accelerate the generalization of agnostic federated learning by factor of compared to batch results established by Mohri et al. [27]. Our results also imply matching high-probability bounds to Mohri et al. [27] on the convergence of the training error in the batched setting.
To achieve these results, contribute new insights and techniques for solving stochastic zero-sum games with sources of randomization that differ in both cost and quality. We frame the multi- distribution learning problems as a stochastic zero-sum game with uncertain payoffs and utilize stochastic mirror descent and a variational perspective to solve the game. In this case, the maximizing player can be interpreted future on on-demand samples should be taken. These on-demand samples form a stochastic gradient for the players. However, the quality of these estimators, the number of samples needed for them, and whether they can be reused later on, differs between the two players. We extend the Stochastic Mirror Descent framework to optimally trade off these asymmetric needs for samples. Section 3 we give an overview of this approach and its technical challenges and contributions.
weight vector for distributions D, specifying from which distributions
1.1 Related Work
Learning models. There are many lines of work that study multi-distribttinn learning but which have evolved independently in separate communities. The field of collaborative learning concerns the learning of a shared machine learning model by multiple stakeholders that each desire a model with low error their own data distribution. The line of work initiated by Blum al. [5] studies on-demand sample complexity bounds for realizable collaborative learning and was later extended to several related settings (e.g.. [29, 8, 7, 30J. The agnostic federated learning framework of Mohri et al. [27] poses an equivalent of the malti-diisribution learning objective as a fair and intuitive target for federated learning algorithms, and studies it in the offline setting with data-dependent analysis. multi-distribution learning also arises in distributionally robust optimization [4] as the Group DRO problem [17], which is is motivated by deep learning applications with multiple deployment domains or protected demographics. These works focus on an empirical perspective, but have discussed training error convergence in offline settings [17, 36, 37J. Multi-distribution learning also related to line of work on multi-source domain adaptation (e.g., [3, 24)) and multi-gre group faireess notions (e.g., [35, 38, 13)). We describe these parallel threads in more detail in Section A.
Stochastic game equilibria. Our approach relates a line of research using online algorithms to find min-mat max equilibria by playing no-regret algorithms against one another [34, 15, 31, 9, 10]. Online mirror descent (OMD) is minima of convex functions, and also approximate min-max equilibria of convex-concave games, with high probability using noisy first-order information [33, 28, 16, 2]. We bring these online learning tools to bear on the problem of finding saddle points in robust optimization formulations. The primary technical difference between multi-distribution learning and traditional saddle-point optimization problems is that we have sample access to distributions instead of noisy local gradients.
well-studied family of methods that find approximate
2 Preliminaries
Let X' be an instance space, y label space, and 2 = x'x a space of datapoints. A data distribution D is a joint probability distribution over Z. We consider a hypothesis class H. of a subset of functions mapping X' to y. With each distribution D. define a loss function LD H. x Z + [0, 1] measuring the loss of hypothesis h on data point 2 E Z. We write tD as l when 1) is clear from context. We denote the expected loss, i.e. risk, of a hypothesis h E H under a data distribution D E D by:
(iskp(h) = E (x.0)~
[&D (h, (z, v))].
Importantly, we only assume that e are bounded and make no other assumptions on losses or distributions. For distribution over the hypothesis class, p E AH, and distribution over data distributions, g AD, we refer to their expected loss by Risk, (p) == ED-y [En~p [Ri]k
3

---

Collaborative Learning. We will use the collaborative PAC learning model of Blum et al. [5] and its agnostic extensions by Nguyen and Zakynthinou [29]. In this setting, the goal is to guarantee small risk for every distribution in a collection. Formally, given set of data distributions DD = {Di,.... Dn), the goal of the learner is to learn a hypothesis h such that, with probability 1-6. 6,
max Risk & OPT + e, where OPT == min max (h). DED
(1)
NEW DED
Group Distribution Robustness. We will also study the closely related setting of group distribu- tionally robust optinization (Group DRO) of Sagawa et al. [36]. Formally, the group DRO setting considers model set ④ that is convex compact subset of the Euclidean space and a convex loss function E : θ x Z- + [0, 1] that is assumed to be differentiable over G. Given set of data distributions D == (Di .D.....; D. the learner seeks model E O, such that, with probability 1 1- 8,
max E [e(0, (zr, y))] < R-OPT + where R-OPT == min max DED (2.0)~>
E
[e(0, ())) (2)
65 DED (a.D))~
There is a close relationship between the Group DRO setting and collaborative learning. In particular, when θ = A and H is finite, the two goals are analogous but with two exceptions: first, the Group DRO could return distribution over functions while collaborative learning requires the solution to be a deterministic function, and second, R-OPT is potentially more competitive than OPT since allows randomization. We note that the group DRO setting is equivalent to the agnostic federated learning framework of [27], thus our results for DRO extend to that setting as well.
Sample complexity. We are interested in the design of algorithms that achieve the above goals while using a small number of samples from distributions Di...., Dn. We formalize the sample complexity by the total number of calls made to example oracles EX(D,). Each call EX(D) produces an i.i.d. sample from D. We note that these example oracles also allow us to sample from any mixture distribution q AD, e.g., by first selecting D, according to the mixture and then calling EX(D,).
2.1 Technical Background
We will use tools and definitions from the literature on zero-sum games and no-regret learning throughout the paper. This section provides a brief overview of these concepts.
Zero-Sum Games. finite wwo-player zero-sum game described by the tuple (A. A,, Φ) where
A. = (1....,, ] and A. = {1...., m are finite sets of actions and where Ø A. x A, + [o, C]. In this game, the players choose mixed strategies over actions sets. These are distributions that are denoted by a vector of probabilities p E AA, and E AA,. The expected payoff of mixed strategies denoted by p(p. q) Em-ps-n (i) The goal of the minimizing player is to minimize this expected payoff and the maximizer seeks to maximize the expected payoff; that is, to solve
min max (pp.9). PEAA PEAA,
A pair (p. 9) that solves this optimization problem is called min-max equilibrium. Similarly, solution is called an e-min-max equilibrium if neither player can unilaterally improve their objective by more than e. Formally, (p. 9) is an s-min-mas max equilibrium if both players' regrets are at most e, i.e. Reg-Min(p, q) == o(p. q) min;- EAA o(i", g) I E and Reg-Max(p, q) == max, EA, o(p. o(p.g) S E. We will next describe methods that find e-min-max equilibria by finding solutions (p, q) for which Reg-Min(p q) + Reg-Max Max 9) is at most E. We describe a more general formulation for convex-coneanl zero-sum games in Appendix B.I which we will use for the Group DRO problem.
No-Regret Learning. We consider an online setting where an arbitrary set of operators, E E*, is revealed sequentially to a learner who must choose a matching sequence of actions, w(()) ,........ w!!), from a convex compact set Z S E. Here, and E* respectively refer to an arbitrary Euclidean space and its dual. We focus on a setting where an online learner commits to action wn(() E 7 before seeing g()) g ((++1)... .... and aims to achieve vanishing variational error Erry (try(w(1:T)) defined by
T
(ur((w(1)T))
= max
g (t)
(t) - w
(3)
w EZ
T
1=1

---

We will denote no-regret algorithms by their update rule Q (Z x 8 Z, where {z x E denotes the space of arbitrary length sequences of action-operatee pairs. Given a history sequence w()), w(t) Z and operator sequence g( ..... ( e", the algorithm returns w(++1)
Q ((w(l)) g())) ....., {w(t), (("))) When the history is clear from context, write w((+1) Q (wlo, ))))) as shorthand. For the particular case where Z A is probability simplex, one such algorithm is Exponential Gradient Descent (also known as Hedge):
Quedge (f
W
(8) where ūŪ; w (1) exp 19: J 7. E.ERR R" (4)
|
where 77 is user-defined step size, and wi user-defined initial iterate. By default, we take [1] a The following lemma is a classical result on the variational error of exponential gradient n.
w1 descent.
Lemma 2.1 ([40]). Let 9dd) " ( R and Z A Further assume ||g S C for all timesteps 1 = ,. Choosing 1 v /lg n/T, after T iterations of exponential gradient descent, T.
the outputs w ....., w() satisfies,
3C 2
KL (wll))/2(())
Erry (w (TTT)
3 Technical Overview of Our Approach
In this section, we provide an overview of our technical approach for addressing the sample complexity of collaborative learning and group DRO problems. In later sections, we will refer to the approach outlined this section to sketch proofs and design algorithms. We will focus our exposition on collaborative learning and briefly indicate how the same approach applies to the group DRO setting.
At high level, we first frame collaborative learning and aim to use variational perspective to learn its minmax equilibrium. We specifically choose the variational perspective (instead of an arbitrary online learning approach), since it allows to linearize the effect of uncertain payoffs on the resulting error. We then use stochastic gradients to solve the variational problem. Our stochastic gradients will rely on i.i.d. samples from the distributions to estimate gradients both with respect to distributions over Ht and mixtures over 'D but with an asymmetric bound on the bias and variance of the estimates. Along the way, we develop tools and formalisms that handle the asymmetric cost of stochastic gradients and obtain optimal sample complexity results. We now address these steps more detail.
zero-sum game with uncertain payoffss
Collaborative Learning as Zero-Sum Games. When the hypothesis class H. is finite, the collab- orative learning problem with distribution set D corresponds to a zero-sum game (A., A,, o) with A. = H. A, D, and ((i j) Risk,(0) (i), where E A. and j E A,. Observe that the value of the min-max solution is equivalent to R- R-OPT. It is not hard see that any s s-mm--ma equilibrium (p.g) q) of this game corresponds to 2= collaborative learning solution, i.e.,
E kmp
max Rh) DED
< OPT 2
This enables us to use tools that have been developed for solving zero-sum games in order to address collaborative learning and group DRO settings. We will use a similar construction when hypothesis class H has finite VC dimension, where A. will instead refer an appropriate E-cover of H.
Using the Variational Error to deal with Payoff Uncertainty. A sufficient condition for minimiz- ing regret, and thus finding s-min-man max equilibrium, minimizing the variational error (Equation 3). In particular, for any finite zero-sum game (A., A., 6), defining Z = [AA, AA,] and operators
(0)
(0p, ((p()) ((()))gg)))) )) rea {-0 (1
JEA. .g. ) )EA
(6)
ensures that variational error provides upper bound on regret: (rr((w():))) > Reg-Min(p, q) Reg-Max(p. g), where (p.g) (see Fact C.I). In collaborative learning, when p!1) is the min- player's distribution over hypotheses and (()) is max-player's distribution over the mixtures, the
5

---

gradient vectors refer to the risks of each hypothesis or distribution under g(t) or pl respectively:
g0) = Lo 9+ g! = Risk (h) new: g = (Risko()) DED
(7)
In the collaborative learning setting, we can only create noisy estimates 9 for these gradients from samples. No-regret algorithms are advantageous in this setting as they choose their tth iterate w(th before seeing the łth gradient g()) This means that w(t) is independent of gradient noise, e(t) = g( g( We can thus linearize the noise and decompose variational error into the training and generalization errors as follows
T w E"EA" T (09) w -00)-ww) wn) + max E"A T
T Σ (c (0(0 w0)
Erryww (1:T) -
max
1
(8)
In contrast, generic no-regret algorithms that do not solve the variational inequality (e.g., when one player plays Hedge and another plays clairvoyant best-response as used in existing work in collaborative learning due Blum et al. [5], Nguyen and Zakynthinou [29], Chen et al. [8] nest the generalization and training errors which leads to a multiplicative increase in sample complexity.
Leveraging Noisy Stochastic Gradients. We will work with stochastic estimators of g. These functions 9 & x AA. x AA, of some external source of randomness, & E &, and a strategy profile of interest. For collaborative learning, the randomness source is i..d.-sampled data point from an appropriate mixture of distributions and the estimator I is then the empirical loss on this sample, which is unbiased and bounded estimator in the range of the loss function, i.e., [0, 1].
Interestingly, estimators of these stochastic gradients have an asymmetric need for data. As seen in Equation 7, the min-player's gradient g- (p, q) includes the risk of every hypothesis h E H for the same data distribution q. Therefore, an unbiased estimator ğ. (p, 4) can be constructed from a single call to example oracle EX(g). We call this source of randomness ç and say that its cost is r- 1. While <a costs unit, the randomness it provides is specialized to the point of inquiry, that is, cannot be used for estimating other [p(p.g q¹). We call this source of randomness and its associated unbiased estimation a locally unbiased estimator.
On the other hand, the max-player's gradient (+ g) includes the risk of the same hypothesis on every distribution D E D. Therefore, an unbiased estimator (+, q) requires n samples, i.e., a call to every example oracle EX)D;) We call this source of randomness producing samples & and say that its cost is r- = n. Importantly, while & costs n unit, the randomness it provides can be reused for estimating other gradients, that is, it can provide all (1', g'). We call this source of randomness and its associated unbiased estimator a globally unbiased estimator. To emphasize the fact that this source of randomness is agnostic to (p, q) refer to it by &L hereafter. We refer the reader to Appendix B.2 for a more formal definition and description of these asymmetries.
unbiased and bounded estimators for
Minimizing Regret with Asymmetric Cost. With the goal of minimizing sample complexity in mind, it is essential that we reuse randomness g- across time steps of variational algorithms. To do this, we introduce a stochastic variational approach in Algorithm I that accommodates different sampling frequencies for the minimizing and maximizing players. This will decouple the sample complexity of the minimizing agent (who requires time horizon of at least log(A.) z log (H) and the maximizing agent. Lemma 3.1 proves this decoupling allows us find an m-in-max equilibrium with an additive n + log(?) sample complexity instead of a multiplicative n log(H).
Algorithm uses the same randomness g (a) of cost r for estimating (+'p', q²) for all E [ar+ I..... a(r + 1)]. On the other hand, the algorithm uses fresh randomness g(t) of cost to estimate (p', .gt) for every time step t. The total randomness cost of this algorithm is thus 2T because iteration of the outer loop incurs 2r cost.
Lemma 3.1. Let (A., A., Φ) be a finite zero-sum game, Assume there exists gd of cost providing locally unbiased estimates g-() and there exists ç (a) of cost r providing globally unbiased estimates (-).
With probability 1 6, Algorithm returns an E-min-max equilibrium of the game, so long as
18
9 log |A|
(=+1)
9
AA
8r
r++1
}))
T
max
8 log
+ max
r+1
log
8
(9)
Moreover, the total cost of randomness incurred by the algorithm is most 2T.

---

Algorithm 1 Finding Equilibria in Finite Zero-Sum Games with Asymmetric Costs.
Output: Mixed strategy profile (p, q) AA. x AA.;
Input: Action sets A., A., cost E 24, timesteps T, iterates p(), ,0(h, gradient estimators D.
for a = 1,2..... [T/r] do
Realize g- (n) at cost r;
// Sample datapoints from every distribution.
for = ar + - r, -...... ar do
Realize g0 at cost 1;
1/ Sample from adversary-selected distribution.
Estimate gradients: g. 0+ (fL()) ppl1) (000)g10) T = (50 -p(1) g())
Run Hedge updates: p(++1) Quodge (p()). ggg)gg) (((+1) Qnodgo (9(),
=!1)
,
end for end for
Return the uniformly mixed strategies p T Ei=pp and q T EE 9')
Proof sketch. Our approach uses Equation decompose the variational error into training error and generalization error. Since exponential gradient descent is known to bound the training error (as shown in Lemma C.4), it only remains to bound the generalization error (the second term in Equation 3). We note that in expectation each summand (E(*), w(() w²) ) is zero. This is because e(*) = g()) - g and git)) are unbiased estimators. Therefore, the sum of these terms has an intuitive martingale interpretation and could be bounded by the Azuma-HHefffee
inequality.
There is a subtlety here, however. When we reuse the maximizing player's randomness over r rounds, we create correlations between these terms in the generalization error that cannot be directly accommodated by a martingale. The trick here to note that these correlations are entirely contained in r-length periods. So, we can partition sequence to martingales and bound each one. This completes the proof. See Appendix C. for detailed proof of this lemma.
Derandomization. The c-min-max equilibria (p. q) returned by Exponentiated Gradient Descent gives probability distribution p over the hypothesis class that achieves the collaborative learning bound. To obtain a deterministic hypothesis, we can instead work with hafaa whose predictions are p-weighted majority votes over the hypotheses in H. As stated below, the error of this deterministic classifier is approximately bounded by the expected error of
Lemma 3.2. For any p AH, maxDeD Risk (hi Ma)) < 2 MAXDED Riskn(p).
This lemma in particular implies that for any e-min-max equilibria (p. q). have
max Risk (h (aa) < 2R-OPT + 4. < 2OPT + 4s.
DED
4
Collaborative Learning Bounds
In this section, we characterize the sample complexity of collaborative learning by providing tight upper and lower bounds for this problem. We describe Algorithm 2, which attains near-optimal sample complexity by on-demand sampling: iteratively selecting distributions to sample from.
4.1 Sample Complexity Upper Bounds
We are now prepared to describe our collaborative learning algorithm and guarantees, using the tools we developed in Section 3. Algorithm 2 a direct application of Algorithm 1 to a zero-sum game with action sets A. = H. A, = D and payoff Φ(h, D) = Riskp (h). Here, eo(") makes one call to (X) and g! (a) makes one call to EX(D) for each D E D. In other words, Algorithm 2 constructs
distributions (()) E AMl and (()) E AD by running the Hedge update. The gradient estimators used by Hedge the empirical losses a set of independent random variables. In particular,
the minimizing player uses gradients é ((1) for all h E H for single sample 2()) ~ EX(
with D (9) and the maximizing player uses gradients L (p 2B) for all distributions D D
7

---

Algorithm 2 On-Demand Agnostic Collaborative Learning.
Input: Hypothesis class H. distribution D with n |P];
Initialize: p( [1/ | (22) [1/n]", and iterations T 2 (9l ((H)) + 35n log(n/0));
for a = ,,, [T/n]] do
For all D E D. sample datapoint 2 from EX(D).
for t = an + ...... an do
Sample 2(t) from EX(D) with D q() and estimate g [e 2 M
Run Hedge updates: p(t+1) Qhodge (.") git+t) Qnedge (q(t), ((1) end for end for Return: probability distribution over H given by the uniform mixture + Ei=Iph
where a single sample 2 EX(D) is drawn per distribution and is reused for all time steps t t [(a
1) + L...., an)
Our main result in this section bounds the sample complexity of Algorithm 2.
Theorem 4.1. For any finite hypothesis class H and unknown set of distributions D, with probability 1 6, Algorithm 2 returns a distribution p E AH such that
max Riskp (1i) S + and max maxRisk (1 Mad) S 20PT+
E
hewp
DED
DED
using a number of samples that is O tn log
gd
Proof sketch. By construction, Lemma 3.1 guarantees that with probability at least 6, the pair (p. 9) is e/2-min-mas max equilibrium for the corresponding zero-sum game. As shown by Equation 5, is a randomized classifier that meets the collaborative learning objective, i.e., its expected worst-case error is OPT + c. By Lemma 3.2, the corresponding deterministic classifier 1, has worst-case error of 20PT + E. This bounds the error of the resulting classifier.
To bound the sample complexity, Lemma 3.1 shows that the randomness cost of Algorithm 1 is at most 21. Since the cost of randomness is exactly the total number of samples we take from our example oracles, the total sample complexity of Algorithm 2 is 2/ E O (s (log [H| + n log(n/8))). n
An analogue of Theorem 4.1 (Theorem C.3) holds for the case of infinite hypothesis classes of bounded Littlestone dimension with a sample complexity of O (s-2 (Little(H) + n log(n/5))). A similar result also holds with dependence on the VC dimension of H only (which is smaller than its Littlestone dimension) when additional assumptions hold. For example, if hypothesis class H' known advance that is an e-net of H with respect to every distribution D, one can instead run Algorithm with a hypothesis class H'. Such an g-net of size ne (VVCD(H)) necessarily exists; for example, the union of c-nets with respect to each distribution D E 'D. It is also not strictly necessary to know an g-net in advance. Instead, one can compute net from samples or from other information about distributions in D. In Appendix C.5, we explore range of assumptions that allow us to compute such an e-net from samples, without incurring a significant increase in the sample complexity of Theorem 4.1.
We end this subsection with a few remarks about our sample complexity upper bound.
Remark 4.1. One question left open by these results is. for agnostic multi- dittriddistribution learning. whether it is possible to achieve sample complexity rates of (s [log())VCD(I)))) without any additional assumptions or priori knowledge of an E-net. It also remains open whether the log(n) factor the log(n) VCD(H)/ term necessary for some VC classes, as Theorem 4.1 proves it is not necessary for some (e.g.. fiitt) VC classes.
log(n/ (
Remark 4.2. Theorem 4.1 improves over the best-known sample complexity for agnostic collab- orative learning by Nguyen and Zakynthinou [29] in two ways, giving an OPT + e bound for randomized classifiers instead of their 20PT + e bound, and improving their sample complexity of O (1t (log(n) log([H) log (1) + log (3 )))) by a multiplicative factor of 2 log (n) log (!).
8

---

Remark 4.3. For constants E and 6, our sample complexity of O (log((HL)) + n nogn) appears to violate the lower bound of Ωt (log([H)) log + n noo log (Hl) due to Chen, Zhang, and Zhou [8]. This discrepancy is due to small error in the proof of that lower bound, which we have verified in private communications with the authors. In the next subsection, we give lower bounds on the sample complexity of collaborative learning that match our upper bounds.
4.2 Sample Complexity Lower Bound
We now provide matching lower bounds for agnostic collaborative learning. Our lower bounds hold for collaborative learning algorithms obtaining enror of R-OPT + e, using randomized deterministic hypothesis. We call an algorithm an (c, collaabboret learning algorithm for any collaborative instances attains an error of R-OPT + with probability at least 1-
Theorem 4.2. Take any n, d Z4, e, E (0, 1/8), and (e, collabbrare learning algorithm A.
There exists a collaborative learning problem (H, D) with [D] and [H] 24, which A takes at least Q (1z (log [ + [D] log (min { log [H]] /6)) samples.
Proof sketch. We defer the formal proof of this theorem Appendix C.3 and sketch the main ideas here. Let X' = [l......................
........e d}. y/ {+. -.. and H. be the set of all functions X' + y. Our construction combines sets of hard distributions. Consider the case when d 1j for some 1) Z. First, we can reduce to a d-armed multi-arm bandit exploration problem giving us an S2 (dlog(1/0) Second, construct hard instances on y) corresponding points. Since the learning algorithms has to solve each problem it has to incur a loss of doog dd
5 Group DRO and Agnostic Federated Learning
The results we describe in the collaborative learning setting can be generalized to the group DRO setting, and equivalently, agnostic federated learning.
Theorem 5.1. Consider group distributionally robust problem (0, D) with convex compact unit- diameter parameter space & of Bregman radius De (Definition B.11), and convex loss E θ x Z + [0, C}. A variant of Algorithm 2 (in particular Algorithm 4 in Appendix 4. 4.1), returns F E θ such that maxDeD E.-D [E(0, 2)] < R-OPT + E, using a number of samples that O (DaCA log(n/8)
The proof of this lemma is deferred Appendix 4.1 and is similar the proof of Theorem 4.1 except that it uses a generalization of Lemma 3.1 for general convex-concave games. This theorem establishes generalization bound for the problem of group distributionally robust optimization [36] and improves, by factor of n. existing sample complexity bounds for agnostic federated learning [27]. This improvement is attained by sampling data on-demand, whereas [27] only chooses fixed distribution over groups/clients to sample from; this highlights the importance of adapting one's sampling strategy on-the-fly when learning robust models.
Another important question how fast the training error of stochastic gradient descent converges for the group DRO/AFL settings and was considered by Sagawa al. [36]. We can transfer generalization guarantees for on-demand settings into batch settings and achieve the following corollary, which improves the convergence guarantees of Sagawa al. [36] by factor of n.
Corollary 5.2. Under the same assumptions of Theorem 5.1, give a procedure (see Appendix 4.1) that minimizes GDRO/AFL. training error within e of R-OPT with probability at least 1 in fewer (DaC* +nC² log(n/8)
samples than O
6 Empirical Analysis of On-Demand Sampling for Group DRO
This section describes experiments where we adapt our on-demand sampling- based multi-distributian learning algorithm for deep learning applications. In particular, we compare our algorithm against the de-facto standard multi-distribution learning algorithm for deep learning, Group DRO (GDRO) [36]. As GDRO designed for use with offline-collected datasets, to provide an accurate comparison, we modify our algorithm to work on offline datasets (i.e., with on-demand sample access).

---

Resampling Multi-Distributiin Learning (R-MDL). To adapt our multi cilliiddistrbbbtiinn learning algorithm, Algorithm 2, for deep learning applications, we replace learning algorithm with minibatch gradient descent algorithm. We can further adapt our algorithm to offline datasets by simulating on-demand sampling on the empirical distributions of datasets. This modified algorithm, R-MDL,, is described in full in Algorithm 5.
spothesis--eleettin no-regret
In contrast, the GDRO algorithm is also minibatch gradient descent but samples minibatches uniformly from all distributions. Datapoints in each minibatch are importance weighted according to their distribution of origin, where no-regret algorithm adversarially weights each distribution. Though effective, this GDRO method is brittle and requires tricks like unconventionally strong regularization [36]. Our theory of on-demand sampling suggests that R-MDL should mollify this brittleness.
Experiment Setting In Table 2, we replicate the Group DRO experiments of Sagawa et al. [36] and compare the standard GDRO algorithm with our R-MDL algorithm (Algorithm 5). We fine- tune Resnet-50 models (convolutional neural networks) [18] and BERT models (transformer based network) [1 on the image classification datasets Waterbirds [36, 41] and CelebA [23] and the natural language dataset MultiNLI [42] respectively. We train these models in 3 settings: with standard hyperpameters, under strong weight decay (f-2) regularization, or under early stopping.
Wosst-Gronp Accunccy
Gap in Avg. Worst-Group Ace.
FRM
GDRO
R-MDI.
FRM
GDRD
R-MDI
Sundard Reg.
Waterbirds
60.0
(1.7)
(1.44
(1.9)
20.5 (1.7)
(1.4)
CelebA
41.1 (3.7)
(3.7)
88.9 (2.3)
(3.7)
(3.7).
3.4
MobiNI.1
(1.6
66.6(1.6)
70.3 (1.5)
(1.66
(1.66
(1.5)
Strong Reg.
Waterbirds
(1.3
(1.6
(1.2)
74.4 (1.6)
12.41.)
(.33)
CelebA
(3.6
(2.5)
(2.3)
688 (2.5)
12.3)
Early Stop
Waterbirds
6.(1100)
(1.4)
87.1 (1.3)
87.1 (1.0)
7.4(1.4)
(1.31
CakebA
(3.0
(2.4)
(2.2)
(2.44
MuliNLI
(1.66
(1.4)
45.1 (1.7)
16.8
3.7 (1.4)
(8.7
Table 2: Worst-group accuracy (our primary performance metric) and the gap between worst-grous group accuracy and average accuracy, of empirical risk minimization (ERM), Group DRO (GDRO), and R-MDL algorithm three experiment settings- standard hyperparameters (Standard Reg.). inflated weight decay regularization (Strong Reg.), and early stopping (Early Stop)-ann and on three datascts-Watorbiee Watcrbirds, CelebA, and MultiNLL. Figures are percentages evaluated on the test split of cach dataset, with standard deviation in parentheses. R-MDL consistently outperforms GDRO and performs reliably with without strong regularization.
R-MDL consistently outperforms GDRO and ERM. In every dataset and in almost every setting, R-MDL. R-MDII.sgnnifcan significantly outperforms GDRO and ERM in worst-group accuracy. In addition, whereas GDRO and ERM have large gaps between worst-group accuracy and average accuracy, R-MDL has almost matching worst-group and average accuracies. This indicates that R-MDL is more effective at prioritizing learning on difficult groups.
R-MDL robust to regularization strength. R-MDL retains high worst-group accuracy even without strong regularization. These results challenge the observation of Sagawa et al. [36] that strong regularization is critical for the performance of Group DRO methods. This suggests that the brittleness of GDRO is due to reweighting rendering the adversary too weak. In contrast, R-MDL provides a robust multi-distribution learning method with significantly less hyperparameter sensitivity.
7 Acknowledgments
This work was supported in part by the National Science Foundation under grant CCF-2145898. C3.AI Digital Transformation Institute grant, and the Mathematical Data Science program of the Office of Naval Research. This work was partially done while Haghtalab and Zhao were visitors at the Simons Institute for the Theory of Computing.
10

---

References
[1] N. Alon, Ben-Fliezer, Y. Dagan, S. Moran, M. Naor, and Yogev. Adversarial laws of large numbers and optimal regret in online classification. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 447-455. ACM, 2021.
[2] A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett., 31(3):167-175, 2003.
[3] S. Ben-David and R. Schuller. Exploiting task relatedness for multiple task learning. In Learning theory and kernel machines, pages 567-580. Springer, 2003.
[4] A. Ben-Tal. Tal, L. El Ghaoui, and A. Nemirovski. Robust optimization, volume 28. Princeton university press, 2009.
[5] A. Blum, N. Haghtalab, A. D. Procaccia, and M. Qiao. Collaborative PAC Learning. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS). pages 2392-2401, 2017.
[6] A. Blum, N. Haghtalab, R. L. Phillips, and H. Shao. One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning. In Proceedings of the International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 1005-1014. PMLR. 2021.
[7] A. Blum, S. Heinecke, and L. Reyzin. Communication-Aware Collaborative Learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), volume 35, pages 6786- 6793, 2021.
[8] Chen, Q. Zhang, and Y. Zhou. Tight Bounds for Collaborative PAC via Multiplicative Weights, In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurlPS), pages 3602-3611, 2018
[9] C. Daskalakis, A. Deckelbaum, and A. Kim. Near-Optimal No-Regret Algorithms for Zero-Sum Games. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 235-254. SIAM, 2011.
[10] C. Daskalakis, M. Fishelson, and N. Golowich. Near-Optimal No-Regret Learning in General Games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), volume 34, pages 27604-27616. Curran Associates, Inc., 2021.
[11] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the Conference of the North Amer- ican Chapter of the Association for Computational Linguistics, pages 4171-4186, Minneapolis, Minnesota, 2019. Association for Computational Linguistics.
[12] J. C. Duchi and H. Namkoong. Learning Models with Uniform Performance via Distributionally Robust Optimization. CoRR, abs/1810.08754 2018. arXiv: 1810.08750.
[13] C. Dwork, M. P. Kim, O. Reingold, G. N. Rothblum, and G. Yona. Outcome indistinguishability In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pages 1095-
1 1108. ACM, 2021.
[14] A. Ehrenfeucht, D. Haussler, M. J. Kearns, and L. G. Valiant. A General Lower Bound on the Number of Examples Needed for Learning. Inf. Comput., 82(3):247-261 1989.
[15] Y. Freund and R. E. Schapire. A Decision-TThoreee Generalization of On-Line Learning and an Application to Boosting. J. Comput. Syst. Sci., 55(1): 19-199,, 1997.
[16] S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 6855):127-11155 2000. Publisher: Wiley Online Library.
[17] T. B. Hashimoto, M. Srivastava, H. Namkoong, and Liang. Fairness Without Demographics in Repeated Loss Minimization. In Proceedings of the International Conference Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 1934-1943. PMLR, 2018
11

---

[18] K. He. X. Zhang. S. Ren, and J. Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778. IEEE Computer Society, 2016.
[19] L.. Hu, C. Peale, and O. Reingold. Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability. In Proceedings of the Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 515-552. PMLR, 2022.
[20] A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalities with stochastic mirxor-prox algorithm. Stochastic Systems, 1(1):17-58, 2011. Publisher: INFORMS.
[21] A. Kar, A. Prakash, M.-Y. Liu, E. Cameracci, J. Yuan, M. Rusiniak, D. Acuna, A. Torralba, and Fidler. Meta-Sim: Learning to Generate Synthetic Datasets. In Proceedings of the International Conference Computer Vision, pages 4550-4559. IEEE, 2019.
[22] R. M. Karp and R. Kleinberg. Noisy binary search and its applications. In Proceedings of the Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 881-890. SIAM, 2007.
[23] Z. Liu, Luo, X. Wang, and X. Tang. Deep Learning Face Attributes in the Wild. In Proceedings of the International Conference Computer Vision, pages 3730-3738. IEEE Computer Society, 2015.
[24] Y. Mansour, M. Mohri, and A. Rostamizadeh. Domain Adaptation with Multiple Sources. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 1041-1048 Curran Associates, Inc., 2008
[25] S. Marcel and Y. Rodriguez. Torchvision the machine-vision package torch. In Proceedings of the International Conference Multimedia, pages 1485-1488. ACM, 2010.
[26] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communication-EEficcie Learning of Deep Networks from Decentralized Data. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 54 Proceedings of Machine Learning Research, pages 1273-1282. PMLR, 2017.
[27] M. Mohri, G. Sivek, and A. T. Suresh. Agnostic Federated Learning. In Proceedings of the International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 4615-4625. PMLR, 2019.
[28] A. S. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley-Intersciencee, 1983.
[29] H. L. Nguyen and L. Zakynthinou. Improved Algorithms for Collaborative PAC Learning. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7642-7650, 2018.
[30] M. Qiao. Do Outliers Ruin Collaboration? In Proceedings of the International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 4177-4184. PMLR, 2018.
[31] A. Rakhlin and K. Sridharan. Optimization, Learning, and Games with Predictable Sequences. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 2066-3074, 2013.
[32] V. V. Ramaswamy, S. S. Kim, and O. Russakovsky. Fair attribute classification through latent space de-biasing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9301-9310 2021.
[33] H. Robbins and S. Monro. stochastic approximation method. The annals of matheraticaal statistics, pages 400-407, 1951. Publisher: JSTOR
[34] Robinson. An iterative method of solving game. Annals of mathematics, pages 296-301, 1951. Publisher: JSTOR
12

---

[35] G. N. Rothblum and G. Yona. Multi-group Agnostic PAC Learnability. In Proceedings of the International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 9107-9115. PMLR, 2021.
[36] S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang. Distributionally Robust Neural Net- works. In Proceedings of the International Conference on Learning Representations (ICLR). OpenReview.net, 2020.
[37] S. Sagawa, A. Raghunathan, P. W. Koh, and P. Liang. An Investigation of Why Overparameteri- zation Exacerbates Spurious Correlations. In Proceedings of the International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 3346-8356. PMLR, 2020.
[38] J. Tosh and D. Hsu. Simple and near-optimal algorithms for hidden stratification and multi- group learning. Proceedings of the International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 21633-21657. PMLR, 2022.
[39] L. G. Valiant. A Theory of the Learnable. In Proceedings of the Annual ACM Symposium Theory of Computing (STOC), pages 436-445, ACM, 1984.
[40] N. K. Vishmoi. Algorithms for Convex Optimization. Cambridge University Press, 2021.
[41] C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie. The caltech-uesd birds-200-2011 dataset. Technical report, California Institute of Technology, 2011. Publisher: California Institute of Technology.
[42] A. Williams, N. Nangia, and S. Bowman. A Broad- Coverage Challenge Corpus for Sentence Understanding through Inference. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics, pages 1112-1122, New Orleans, Louisiana, 2018. Association for Computational Linguistics.
[43] Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jemite, J. Plu, C. Xu, T. Le Scao, S. S.uuge M. Drame, Q. Lhoest, and A. Rush. Transformers: State-of-the- Art Natural Language Processing. In Proceedings of the Conference Empirical Methods in Natural Language Processing, pages 38-45, Online, 2020. Association for Computational Linguistics.
[44] S. Zakharov, W. Kehl, and S. Ilic. DeceptionNet: Network-Driven Domain Randomization. In Proceedings of the International Conference on Computer Vision, pages 532-541. IEEE, 2019.
[45] C. Zhang. Information theorrttcc lower bounds of PAC sample complexity, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "yIT9zuR8l-4", "reviewer": "Reviewer_XJ3a", "summary": "This paper gives improved algorithms for three settings of learning from multiple distributions: collaborative, group distributionally robust, and fair federated learning. Previous results usually bounds the sample complexity by a certain overhead factor multiplied by the number of samples needed for learning a single distribution. In contrast, the sample complexity bounds derived in this work only have *additive* overheads.\n\nIn more detail, for $(\\epsilon, \\delta)$-collaborative learning on hypothesis class $\\mathcal{H}$ and $n$ distributions, Theorem 4.1 gives an upper bound of $O(\\epsilon^{-2}(\\log|\\mathcal{H}| + n\\log(n/\\delta)))$, which exceeds the $O(\\epsilon^{-2}\\log(|\\mathcal{H}|/\\delta))$ bound for single-distribution learning by an additive term of $(n\\log n)/\\epsilon^2$ (when $\\delta = \\Omega(1)$). In contrast, the previous best bound of Nguyen and Zakynthinou (2018) is at least $(\\log n)\\cdot(\\log|\\mathcal{H}|/\\epsilon^5)$. Theorem 4.3 gives an improved lower bound, which matches the upper bound when $n$ and $\\log|\\mathcal{H}|$ are polynomially related.\n\nThe approach taken by the authors (which is implicit in prior work) is to view the collaborative learning setting as a zero-sum game between the learner (which selects a hypothesis) and an adversary (which chooses one of the $n$ data distributions). The major task is then to find an (approximate) equilibrium of this game, using as few samples as possible. The key technical observation is an asymmetry between the two players in terms of how much data is needed for getting an unbiased estimate of the gradient, and to what extent these data can be reused for estimating the gradient at different locations.", "questions": "1. Are there any natural/simple/structured hypothesis classes for which that the algorithm could be efficiently implemented?\n\n2. The algorithm outputs a (weighted) majority vote of hypotheses. Are previous algorithms also improper, and are there evidence that the problem becomes hard for proper learning?\n\nMinor comments:\n- Line 195: What is \"VI\"?", "limitations": "Limitations were not discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work introduces new tools to the line of research on learning from multiple distributions and further closes the gap between the upper and lower bounds. Both the results and the techniques should be interesting to the community. The new algorithm and its analysis seem highly nontrivial, and I thought the authors did a good job in sketching the proof in the main paper. In summary, this is a solid and well-presented work and should be accepted.\n\nOne weakness of the paper is that the algorithms are computationally inefficient. While the main focus is sample complexity, some discussion on the computational aspect seems necessary.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "evnp5tLoEI7", "reviewer": "Reviewer_2WVF", "summary": "This paper investigates the on-demand sample complexity of multi-distribution learning. The authors establish the optimal sample complexity of collaborative, group distributionally robust, and agnostic federated learning. These results improve upon the best-known sample complexity in the prior work. The main approach is to regard the problem as a stochastic zero-sum game and apply a variant of stochastic mirror descent approach.", "questions": "The paper considers n predefined distributions. \n- Can the result generalize to a family of distributions that has a certain bounded capacity, e.g., all exponential distributions?\n- Can we reduce the dependence on n if these distributions have some relations, e.g., each one is a uniform distribution on a certain subset of k elements?", "limitations": "Not", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The studied problem is important in the machine learning area.\n- The theoretical results are optimal, which closes this direction.\n- The approaches are standard, which widens the application of stochastic mirror descent.\n\nWeaknesses:\n- It may be better to provide some empirical results on the proposed algorithms. The theoretical results will be more convincing if the performance beats the baselines in prior works. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YYKuEn_RrS2", "reviewer": "Reviewer_pzrG", "summary": "This paper studies the problem of multi-distribution learning. Specifically, the paper proposes several sample complexity bounds for on-demand learning. The central contribution of the paper is to first frame collaborative learning as a zero-sum game with stochastic payoff and then use tools from the framework of stochastic mirror descent to obtain sharp rates for various collaborative learning settings. The authors obtain near-optimal rates for agnostic collaborative learning, group DRO, and agnostic federated learning.\n\n", "questions": "- I am curious to know if it is possible to obtain data-dependent bounds for the 3 settings under this framework?", "limitations": "The authors have not explicitly discussed limitations of their approach. Since this work is theoretical, it is unlikely it will have potential negative societal impacts.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The paper is well organized and very easy to understand. The main contributions are listed clearly, and the authors provide a good overview of the approach as well.\n+ The approach appears to be novel and is a general technique to handle learning from multiple distributions. The authors provide near-optimal rates for a variety of problems that improve over the prior state-of-the-art by a significant amount.\n+ The experimental results confirm an improvement in worst-case accuracy on 3 datasets. It would be beneficial to see performance on a dataset with larger variation than WaterBirds and Celeb-A (e.g., YFCC), but that is beyond the scope of this paper.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NbE7hkXnyvc", "reviewer": "Reviewer_mxyZ", "summary": "The authors propose learning algorithms for multi-distribution learning problems and establish optimal sample complexity bounds for the proposed algorithms. The authors improve upon the existing results and also correct an error in an existing result to provide lower bounds for their framework. Specifically, the authors present results for two settings of collaborative learning and group DRO formulation. The developed algorithms rely on the stochastic algorithms utilized to solve stochastic zero-sum games.  ", "questions": "This is a theoretical work that improves upon the existing results. The paper is very dense which makes it a little difficult to read, the authors might consider updating the paper by moving some redundant parts to the appendix for improving the readability of the paper. ", "limitations": "Yes. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is well written and the presented results are strong. The authors improve upon the state-of-the-art complexity bounds (both upper and lower bounds) by significant factors. The paper feels a bit difficult to read and dense, the authors should try to make the paper more reader-friendly. Here are some comments the authors might consider addressing. \n\n1. The algorithms authors have proposed for solving the problems are based on popular min-max formulations and the algorithms are similar to stochastic gradient descent ascent algorithms. Please comment. \n\n2. It is not clear what is the difference between Algorithm 1 and 2. Both the algorithms look more or less similar. Why both the algorithms are required in the main text of the paper. \n\n3. In lines 198-199 it is not clear why $\\text{Err}_v(w^{(1:T)}) \\geq \\text{Reg-Min}(p,q) + \\text{Reg-Max}(p,q)$. Please add a discussion/reference. \n\n4. In eq (7), why the gradients are defined by loss functions. It would be helpful if the authors can clarify. \n\n5. In Line 203 the authors mention with noisy estimates of the gradients the no-regret algorithms become advantageous. Please clarify why this is the case?\n\n6. The authors should discuss the relevance of Lemma 3.1. Moreover, it is not clear why the total cost of randomness is 2t, specifically, why the total cost of randomness is independent of $T$?\n\n7. In Theorem 5.1, why compactness of parameter space $\\Theta$ is required? For general optimization problems, this compactness is not required in general. \n\n8. The context of on-demand sampling is not clear from the Algorithms, maybe the authors can add some discussion about the on-demand sampling after stating the algorithms. \n\n#### **Minor Comments:**\n\n- Please define the dimension of $\\tilde{w}$ in eq. (4). I assume that $\\tilde{w}$ is a constructed by stacking $\\tilde{w}_i$'s. \n- The use of the term \"multi-agent tradeoffs\" in the first sentence of the abstract is not clear. \n- In the statement of Lemma 2.1 please correct the notation $\\\\{ w\\\\}_{t = 1}^T$\n- In line 189 $\\phi(i,j)$ is not properly defined please clarify that $i \\in \\mathcal{H}$ and $j \\in \\mathcal{D}$.\n- The definition of the deterministic estimator $h_p^{Maj}$ is not clear. \n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept