Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Utilizing recent formulations/results, the authors propose MutliBoost, a multi-source ensemble learning algorithm where: (1) it is assumed that any target domain is a mixture of the source domain distributions and (2) the learned function form is a convex combination of base functions weighted by a domain identification classifier, Q(k|x), and referred to as Q-ensembles. The domain identification classifier can be learned from unlabeled data (other than the domain label) and an important innovation as it leads to a more natural multi-source Boosting objective and generalizes many existing (and widely-used) multi-source Boosting works. This formulation aligns with recent results regarding agnostic loss [Mohri, Siven, and Suresh; Agnostic Federated Learning, ICML19] and is able to use related findings to prove favorable theoretical properties wrt previous work and leads to FedMultiBoost, a federated learning variant. Experiments are conducted on five binary datasets converted to multi-domain settings (sentiment analysis, hand-writing recognition, object recognition, and UCI adult tabular data) against natural single domain transfer and combined domain data baselines, showing statistically significant improvements. Several additional experiments are included in the Appendices to also show further results (e.g., domain-identification classifier, FedMultiBoost) that addresses multiple natural questions in the paper.

main_review: As previously stated, this submission primarily builds on recent multi-domain and federated learning finding to revisit and reformulate a multi-domain Boosting algorithm with improved properties relative to existing formulations. Given that this is a well-visited area, the formulation is notable in that it does provide practical advantages (training for all target mixtures) and preferable theoretical properties. Additionally, it is an elegant formulation and has potential to restart work in an area that has become somewhat saturated. The theoretical analysis is sound, concise, and sufficiently thorough. The empirical results are promising, but would benefit from additional comparisons to existing work and, if possible, a ‘real-world’ (non-benchmark) dataset to demonstrate practical strengths of (Fed)MultiBoost. Below, I will evaluate the work along the requested dimensions, but overall think that this is a worthwhile contribution with sufficient originality, quality, clarity, and potential significance (with strengths in theoretical analysis and presentation outweighing weaknesses in empirical evaluations) and lean toward accepting.

== Originality ==
The multi-source Boosting problem is not new, but this formulation provides a generalization to existing approaches that is theoretically more broadly applicable (given the weak learning assumption can be satisfied, the domain-identification classifier is sufficiently accurate, and sufficient training data exists). Additionally, the analytical methods are primarily derived from existing work — so this isn’t the strength of originality either. Specifically, core findings are largely derived from earlier margin-based analysis of Boosting or agnostic learning results in federated learning scenarios (i.e., this is not an analytical breakthrough). However, while I think many people could have put these ideas together if I were to say “adapt [Mohri, Siven, and Suresh; Agnostic Federated Learning, ICML19] to create a multi-source Boosting algorithm”, I don’t think making this connection was obvious nor was the analysis trivial.

== Quality ==
The scholarship and theoretical analysis is solid. The paper is well-contextualized wrt the first generation of Boosting work, application of this work to domain adaptation/multi-source learning, and application of recent work in multi-source/federated learning. The development of the theory is self-contained and answers most of the relevant questions. From a practical perspective, the underlying assumptions in [lines 101-108] seem potentially overly strong as a weak learner must exist for any target-mixture — which may limit it’s practical application. While the empirical results are good in terms of what is presented, they also don’t establish that this is a clearly practical algorithm since: (1) it is not clear why there aren’t results comparing to [Yao & Doretto, 2010] for the single-target case as it would demonstrate the sensitivity of accurate domain identification to some degree and (2) there is no (non-benchmark) ‘real-world’ dataset to prove it is clearly practical. AdaBoost-all is a natural baseline, but it would be surprising if MutliBoost didn’t perform better. Additionally, while space is a problem, but additional discussion of the experimental results would be useful as it is presently a “we outperform fairly weak baselines”. This is somewhat mitigated by the appendices that add to the results and are of quality similar to the body of the main paper. Also, FedMultiBoost is an extension of this connection additional considerations with softmax explored — which may influence other related works.

== Clarity ==
Overall, the paper is well-developed and clear. While reading the most directly related works does help with understanding, a famliar reader will likely view the paper as self-contained and well-focused on the most important new results. Again, the appendices add to the paper (without being strictly necessary) although I think there are opportunities to better reference them with short summary statements in context. Also, from a scholarship perspective, better references in Sections 3 (to older Boosting work, etc.) would be helpful and maybe a bit more forward/in context in section 4 (although lines 218-223 are sufficient). However, I believe clarity is a strength of this work.

== Significance ==
Multi-source is popular and the tie to federated learning increases the potential for impact; I would expect this to be the preferred starting point for multi-source Boosting approaches. The primary limitation that potentially impedes significant is that it isn’t clear that it is the SoTA since thorough empirical comparisons to existing multi-source settings or a ‘real-world’ setting. From a theoretical perspective, the analysis draws heavily from existing work, but after (re-)reading those papers, I liked this presentation and I believe will influence other analyses
limitations_and_societal_impact: == Technical Limitations ==
While the primary limitations are stated, there isn’t an explicit section and/or discussion of the ramifications of the relatively strong assumptions. Additionally, as stated, the empirical results don’t have a notable discussion section.

== Potentially Negative Societal Impact ==
No concerns in this regard — it is an ML algorithms paper with a theoretical focus. Nothing that isn’t beyond standard ML concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the domain adaptation setting where we are given training examples from $k$ different distributions $D_1, \cdots, D_k$. We assume a hypothesis class $H_k$ the at is good for each domain (in the weak learning sense). At test time, the samples are drawn from a convex combination $D = \sum_i \lambda_i D_i$. The goal is to find one linear combination of  weak learners which will perform well for any convex combination. It turns out that this is not possible, but that if you allow the weights to depend on the conditional probability of coming from a particular domain $D(j|x)$, then a single learner is possible. This I believe is already proved in the paper of Mansour-Mohri-Rostemizadeh 2008, although the result there relies on a fixed-point theorem and perhaps does not give an efficient algorithm.    

The main contribution of this work is a boosting style algorithm that achieves this  guarantee. The algorithm does simple co-ordinate wise gradient descent like in Adaboost. They show theoretical margin-based guarantees for their algorithm, and experimental results showing that it outperforms more naive boosting-based approaches. 
main_review: I am a little concerned about the relation between this paper, and the work of Mansour-Mohri-Rostemizadeh 2008 [MMR]. At the very least, I have problems with how this paper credits that paper without adequate citations. It is possible that there is some substantial overlap in terms of ideas. 

1. The notion of $Q$-ensembles:
This paper says: *Instead, we put forward Q-ensembles, which are convex combinations weighted by a domain classifier Q, that is, Q(k|x) is the conditional probability of domain k given input point x. This crucially differentiates our work from that of past studies*

I am not sure I agree with this statement. It appears that the notion of $Q$-predictors is present (or at the very least implicit) in [MMR]). In Section 5.2, the predictor $h_z^0$ they use is exactly the $Q$-weighted predictor where the conditionals are computed for the convex combination of distributions with coefficient $z$).  
In that paper the setting is that there is a single hypothesis $h_l$ for each $l \in [k]$, and we do not get access to samples. It seems that if one considers $h_l = \sum_j \alpha_{l, j}h_{l,j}$ as a single predictor that does well for domain $D_l$, then you get exactly the form of predictors considered in this paper:
$$ f(x) = \sum_{l =1}^pQ(l|x)\sum_{j \=1}^{N_l}\alpha_{l, j}h_{l, j}(x) $$
In particular, this paper never spells out explicitly whether these conditionals are being computed with regard to the uniform convex combination of some other combination, it would be nice to clarify this.

2. Existence of good $Q$-ensembles:
Beyond the notion of $Q$- suggests that the existence of the kind of predictor that this paper gives is implied [MMR]. It seems that their linear combinations are not explicit owing to a fixed point argument, whereas this paper gives an explicit algorithm using boosting.  

3. The negative results:
Proposition 1 in this paper seems identical to Theorem 1 in MMR08, similarly I believe Proposition 2 is just Theorem 2. But there is no citation or acknowledgement, and a reader might think this is a new contribution. While this was probably just oversight, it is not good writing. 

While I like aspects of this paper, I am going with a weak reject for now based on these issues. This is only meant as a placeholder. I would be open to revising my scores if the authors can give a rebuttal that:
- Accurately acknowledges what is derived (directly or easily) from prior work.
- Conditioned on this, emphasizes what is truly novel here.


----------------------------------------------------------------------------------------------------------

After reading the responses, I am convinced that this paper makes a substantial original contribution. I am raising my score to accept. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper addresses the question of learning an accurate classifier using ensemble methods and based on multiple sources. The purpose of the classifier is to achieve good prediction on a set of possible future domains, modelled as linear combinations of the source domains. This is done by minimizing an agnostic loss function over the weights of a linear combination of source predictors, such as traditionally done in ensemble methods. The paper proposes a main algorithm solving this problem, as well as a version for the federated setting. A theoretical analysis and experimental validation are also proposed. 
main_review: Originality: Although the overall idea takes inspiration from various existing lines of work, the idea of building an ensemble predictor from multiple sources is to me novel. It builds upon two main well-known results: (1) the theory of ensemble learning, which states that a combination of weak classifiers can be a strong classifier; (2) transfer learning and domain adaptation, in which it is classical to weight the decision by the probability of the sources. The state of the art is briefly introduced in the main paper, but a bit more elaborated in the appendix. Maybe I would encourage the authors to insist a bit more on the transfer learning aspect which is only briefly discussed in the main paper. 

Quality: The paper is technically correct, even though I have some reservations about the use of the term “boosting”. The main argument is based upon the result that AdaBoost corresponds to a greedy minimization of an exponential loss function. Following this idea, the authors build their own method around the minimization of a loss (which can be exponential, but not only) and minimization of this objective by application of coordinate descent. This is completely correct, but I wonder whether it is possible to really call that boosting. In its definition, boosting is meant to proceed to a sequential update of the predictor by sequential reweighting of the data according to the misclassification of previous models. It also builds upon the idea of applying a learning algorithm producing weak classifiers on several successive datasets (actually a same reweighted dataset). These aspects are of course present in the paper, but completely hidden in a very complex paragraph in Section 3. This comment is not fundamental and does not affect the overall quality of the paper, but I think a stronger discussion is needed here, and maybe I suggest that the authors weaken the importance of the word “boosting” in the paper. Also, I think that a short explanation about the connection between boosting and coordinate descent over exponential loss would be a very good thing to add, to be more accessible to a general ML audience which may ignore this connection. (While re-reading my review, I realize this comment is maybe more to be read from the “clarity” point of view than from the “quality” angle, but I still think that making the effort to explicitly show that the method is actual boosting would improve the quality of the paper). 
The theoretical results seem correct to me, even though I have not reviewed (yet) the full proof of the two theorems. 
Regarding the experimental validation, it is, in my opinion, sufficient to validate the interest of the method. However, I think that it may have been even more interesting to present results relative to other transfer learning / domain adaptation techniques which do not rely on boosting. In essence, the addressed problem is a transfer learning question and boosting is only a tool to solve this problem. I would find it more relevant to compare the results to TL algorithms which focus on the transfer of knowledge from the sources to the target, rather than to boosting methods which are designed to be single-task. 
A point which would benefit from further discussion is the choice of the distribution Q(l|x). It is shortly mentioned that its choice is not direct, but I would have expected maybe more comments on that (which would be required for instance for a complete reproducibility). In the theoretical results, I am a bit surprised that the impact of this term is not visible in Theorems 1 and 2. After reading propositions 1 and 2, it was clear that this term was important for the quality of the predictions, and yet it seems not to play any role in the margin bounds. Could the authors comment on that point? Finally, if not done in theory (which I understand would be difficult – if even possible), I regret that the influence of this term is not highlighted in the empirical section, pointing out how a wrong choice of Q could affect the overall algorithm. 

Clarity: The paper is rather well-written, even though the notations may be sometimes difficult to follow. Unfortunately, this is mostly due to the addressed problem itself and I do not have any real correction suggestions for that. Maybe section 2 could be slightly corrected to introduce the notations in a more readable way? This is only a detail, but I think it would significantly help the reader. During my reading, I had to go back to the notations multiple times and had some difficulties retrieving them. 
In terms of introduction of the ideas, I particularly enjoyed the first two propositions which are a smart way to introduce the Q(l|x) term. Minor comment, though: “probability of a domain given an input point” seems quite ambiguous. I suggest it to be replaced by a clearer description, for instance “probability that an input point belongs to a domain”. 

Significance: The results are somehow significant. The main scenario is probably the weakest in terms of its induced advances in the state of the art, but the federated learning version is extremely important in my opinion and offers a clean and well-justified solution to a very important problem.

limitations_and_societal_impact: The main limitation of the paper is, as said earlier, the strong role played by Q which is not discussed much. 
The paper being more about solving a general task rather than focusing on specific applied problems, there is no societal impact in my opinion, neither positive nor negative.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the problem of learning boosted classifiers with data from multiple source domains. The authors propose Q-ensembles to deal with it and seek a solution for any mixture of the source distribution. They propose the algorithm MultiBoost to solve it inspired by coordinate descent. They present theoretical analysis in terms of margin-based learning bounds. Moreover, they present an extension to the federated learning scenario. In experiments, they compare experimental results with AdaBoost. 
main_review: -	Originality: The method is new since MultiBoost adopts Q-ensemble. 

-	Quality: For binary classification, the authors propose the complete optimization method. However, I doubt if it can generalize to the multi-class case. The algorithm also needs unlabeled data to estimate the conditional probability $Q(k|\cdot)$. 

-	Clarity: The submission is clearly written except for the Section 3 Algorithm. Some errors occur in the description part of Section 3. For example, the definition of $F_k(\alpha)$ in line 130 should remove $\sum_{k=1}^p$. The equation below line 138 is a confusion notation for $F’_k(\alpha_{t-1}, e_{k,r})$. 

-	Significance: The theoretical result is not novel and the guarantee can be anticipated.
For the multiple source dataset that the authors use to conduct experiments, some people propose the neural network-based methods, which can naturally cope with the multi-classification problem and have higher accuracy than boosting. Moreover, the authors should compare with other boosting methods to cope with multiple source problems, not just AdaBoost. 

If the authors can use boosting to cope with multi-class classification and achieve high accuracy, I will consider changing my rate on the paper. 
limitations_and_societal_impact: The authors adequately addressed the limitations. The authors consider a more practical scene, federated learning scenario. Their FedMultiBoost algorithm, to some extent, makes the solution fair and risk-averse.
review_title: null

Meta-review: This paper introduces and analyzes a new boosting algorithm for learning in the presence of multiple source domains. We were persuaded by the author response to the concerns expressed in the reviews, especially about novelty wrt MMR.
Decision: Accept (Poster)