Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.


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.
+ 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.
+ 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.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.  
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. 

1. 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. 

2. 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. 

3. 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. 

4. In eq (7), why the gradients are defined by loss functions. It would be helpful if the authors can clarify. 

5. 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?

6. 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$?

7. In Theorem 5.1, why compactness of parameter space $\Theta$ is required? For general optimization problems, this compactness is not required in general. 

8. 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. 

#### **Minor Comments:**

- Please define the dimension of $\tilde{w}$ in eq. (4). I assume that $\tilde{w}$ is a constructed by stacking $\tilde{w}_i$'s. 
- The use of the term "multi-agent tradeoffs" in the first sentence of the abstract is not clear. 
- In the statement of Lemma 2.1 please correct the notation $\\{ w\\}_{t = 1}^T$
- In line 189 $\phi(i,j)$ is not properly defined please clarify that $i \in \mathcal{H}$ and $j \in \mathcal{D}$.
- The definition of the deterministic estimator $h_p^{Maj}$ is not clear. 


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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- The studied problem is important in the machine learning area.
- The theoretical results are optimal, which closes this direction.
- The approaches are standard, which widens the application of stochastic mirror descent.

Weaknesses:
- 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. 
questions: The paper considers n predefined distributions. 
- Can the result generalize to a family of distributions that has a certain bounded capacity, e.g., all exponential distributions?
- 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

In 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.

The 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.
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.

One 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.
questions: 1. Are there any natural/simple/structured hypothesis classes for which that the algorithm could be efficiently implemented?

2. 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?

Minor comments:
- Line 195: What is "VI"?
limitations: Limitations were not discussed.
review_title: null

Meta-review: metareview: This paper studies multi-distribution learning; it formulates the problem as a zero-sum game with the stochastic payoff and then uses tools from the framework of stochastic mirror descent to obtain optimal sample complexities for various collaborative learning settings.  All reviewers are very positive about this paper: interesting problems, nice techniques, and optimal results.
confidence: Certain
Decision: Accept