Boosting with Multiple Sources
Year: 2022

Abstract:
We study the problem of learning accurate ensemble predictors, in particular boosting, in the presence of multiple source domains. We show that the standard convex combination ensembles in general cannot succeed in this scenario and adopt instead a domain-weighted combination. We introduce and analyze a new boosting algorithm, MULTIBOOST, for this scenario and show that it benefits from favorable theoretical guarantees. We also report the results of several experiments with our algorithm demonstrating that it outperforms natural baselines on multi-source text-based, image-based and tabular data. We further present an extension of our algorithm to the federated learning scenario and report favorable experimental results for that setting as well. Additionally, we describe in detail an extension of our algorithm to the multi-class setting, MCMULTIBOOST, for which we also report experimental results.

heading: 1 Motivation
text: Ensemble methods such as Bagging, AdaBoost, Stacking, error-correction techniques, Bayesian averaging, AdaNet or other adaptive methods for learning neural networks are general machine learning techniques used to combine several predictors to devise a more accurate one (Breiman, 1996; Freund and Schapire, 1997; Smyth and Wolpert, 1999; MacKay, 1991; Freund et al., 2004; Cortes et al., 2014; Kuznetsov et al., 2014; Cortes et al., 2017). These techniques are often very effective in practice and benefit from favorable margin-based learning guarantees (Schapire et al., 1997). These algorithms assume access to a training sample drawn from the target distribution. But, in many applications, the learner receives labeled data from multiple source domains that it seeks to use to find a good predictor for target domains, which are typically assumed to be mixtures of source distributions (Mansour et al., 2008, 2009a; Hoffman et al., 2018, 2021; Cortes et al., 2021; Muandet et al., 2013; Xu et al., 2014; Hoffman et al., 2012; Saito et al., 2019; Wang et al., 2019a). How can we generalize ensemble methods such as boosting to this scenario?
Several related problems have been tackled in previous work. In the special case of a single target domain, boosting solutions have been derived (Dai et al., 2007; Yao and Doretto, 2010). These algorithms have been further improved by boosting base predictors jointly with source features (or feature views) that are predictive in the target (Yuan et al., 2017; Cheng et al., 2013; Zhang et al., 2014; Xu and Sun, 2012, 2011). Such methods have been widely adopted in various domain adaptation scenarios for different types of data. For example, Huang et al. (2010, 2012) showed that by selecting a base learner jointly with a feature that is predictive across multiple domains at every boosting step, one can achieve higher accuracy than standard transfer learning methods. Moreover, the margin
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
provided by boosting-style algorithms can aid in transfer learning where target domain is unlabelled. Habrard et al. (2013) have developed an algorithm that jointly minimizes the source domain error and margin violation proportion on the target domain. Wang et al. (2019a) have demonstrated that boosting classifiers from different domains can be carried out online. Taherkhani et al. (2020) and Becker et al. (2013) have shown that multi-source boosting can be combined with Deep Neural Networks for multi-task learning on large scale datasets.
We give a more detailed discussion of this related prior work in Appendix A. However, as we demonstrate in this paper, several critical questions related to the presence of multiple domains have not been fully addressed by existing boosting methods from both the algorithmic and the theoretical point of view. First, what should be the form of the ensemble solutions? We show that, in general, the standard convex combinations used in much of previous work may not succeed in this problem (Section 2). 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 is inspired by similar Q-ensembles (Cortes, Mohri, Suresh, and Zhang, 2021) or distributionweighted combinations (Mansour, Mohri, and Rostamizadeh, 2008, 2009a; Hoffman, Mohri, and Zhang, 2018, 2021) used in the context of multiple-source adaptation and crucially differentiates our work from that of past studies of ensemble methods. Our learning scenario strictly generalizes previous algorithms. In the special case of a single domain, the form of our ensemble solutions coincides with that of the familiar ensembles used in AdaBoost. In Appendix J, we further compare our results and guarantees with the multiple-source adaptation algorithms of (Hoffman, Mohri, and Zhang, 2018, 2021; Cortes, Mohri, Suresh, and Zhang, 2021), when using AdaBoost to derive a predictor for each domain.
Second, what should be the form of the objective? Unlike existing boosting methods which optimize for a specific target distribution or domain, we seek a solution that is accurate for any mixture of the source distributions, where the mixture weights may be constrained to be in a subset of the simplex. This conforms with the learning goal in this scenario where the target distribution is typically assumed to be a mixture of the source ones and is further inspired by the formulation of the agnostic loss in the related context of federated learning (Mohri, Sivek, and Suresh, 2019). Additionally, this formulation can be viewed as more risk-averse and robust, and it also ensures more favorable fairness properties, since it does not favor any distribution possibly biased towards some subset of the source domains. In Section 3, we introduce and analyze an algorithm, MULTIBOOST, that is based on such an objective. This further distinguishes our boosting algorithm from related prior work. In Appendix L, we further give a detailed description of a multi-class extension of our algorithm, MCMULTIBOOST, including its pseudocode, the discussion of some of its properties, and the results of several experiments.
Third, in Section 4, we present a theoretical analysis of our MULTIBOOST algorithm, including margin-based generalization bounds that hold for any target mixture of the source distributions. In Appendix F, we derive finer and more flexible learning bounds that can provide more favorable guarantees, in particular when the family of target mixtures is more constrained.
Fourth, in Section 5, we describe FEDMULTIBOOST, an extension of our MULTIBOOST algorithm adapted to the distributed learning scenario of federated learning, which is increasingly important in a wide array of applications (Kairouz et al., 2021), including healthcare (Brisimi et al., 2018). FEDMULTIBOOST allows the server to train ensemble models that benefit from clients’ data, while the data remains with clients. We provide a detailed description of our algorithm, as well as a brief analysis of the communication costs, which are critical in this scenario. Appendix G contains experimental results comparing FEDMULTIBOOST with several baselines.
Finally, in Section 6, we report the results of extensive experiments with our MULTIBOOST algorithm. We start with a detailed description of the learning scenario we consider.

heading: 2 Learning scenario
text: Let X denote the input space and Y = {−1,+1} the output space associated to binary classification. We consider a scenario where the learner receives labeled samples from p source domains, each defined by a distribution Dk over X × Y, k ∈ [p]. We denote by Sk = ((xk,1, yk,1), . . . , (xk,mk , yk,mk)) ∈ ( X× Y
)mk the labeled sample of size mk received from source k, which is drawn i.i.d. from Dk. For any function f : X → R and distribution D over X × Y, let
L(D, f) be the expected loss of f , that is L(D, f) = E(x,y)∼D[`(f(x), y)], where ` is the binary loss `(f(x), y) = I(yf(x) ≤ 0). For any k ∈ [p], let Hk denote a hypothesis set of functions mapping from X to [−1,+1], |Hk| = Nk. The objective of the learner is to find a predictor f that is accurate for any target distribution Dλ that is a mixture of the source distributions, where λ may be in a subset Λ of the simplex. Thus, Dλ can written as Dλ = ∑p k=1 λkDk, with λ = (λ1, . . . , λp) ≥ 0 and ∑p k=1 λk = 1. This leads to the following agnostic loss of a predictor f (Mohri et al., 2019):
L(DΛ, f) = max λ∈Λ L(Dλ, f). (1)
To come up with a predictor f , the learner seeks an ensemble of functions from the base classes Hk. What should be the form of such ensembles? A natural solution is a convex combinations of the form
f = p∑ l=1 Nl∑ j=1 αl,jhl,j , (2)
where hl,j ∈ Hl and αl,j ≥ 0, ∑p l=1 ∑Nl j=1 αl,j = 1, as in prominent algorithms such as BAGGING (Breiman, 1999) or ADABOOST (Freund and Schapire, 1997). It is not hard to show, however, that for some distributions, any such convex combination of base predictors would lead to a poor solution. Proposition 1. There exist distributions D1 and D2 and hypotheses h1 and h2 with L(D1, h1) = 0 and L(D2, h2) = 0 such that L ( 1 2 (D1 + D2), αh1 + (1− α)h2 ) ≥ 12 for any α ∈ [0, 1],
This result is similar to (Mansour et al., 2008, Theorem 1) or similar statements in (Mansour et al., 2008, 2009a; Hoffman et al., 2018, 2021; Cortes et al., 2021), however, there are some technical differences. In particular, we are considering here a binary classification loss and not the absolute loss. The proof is given in Appendix B.
Note that in the example of the proposition, the base predictors h1, h2 are both perfect for their respective domains. Nevertheless, unlike the common case of a single source domain, standard convex combinations in general may perform poorly. Thus, we will consider instead the following form for the ensembles of base predictors:
∀x ∈ X, f(x) = p∑ l=1 Nl∑ j=1 αl,jQ(l|x)hl,j(x), (3)
where Q(l|x) denotes the conditional probability of domain l given x. This helps us account for the fact that the learner combines base predictors from different domains. For a given point x, experts from the domains where x is more likely to appear are allocated more weight in the voted combination. The following result further substantiates the hope for this method to succeed. Proposition 2. For the same distributions D1 and D2 and hypotheses h1 and h2 as in Proposition 1, the equality L(Dλ, (αQ(1|·)h1 + (1− α)Q(2|·)h2)) = 0 holds for any λ ∈ ∆ and any α ∈ (0, 1).
The proof is also given in Appendix B. Thus, our Q-ensembles can be substantially more effective in the multiple-source adaptation problem considered. Note that, in the special case of a single domain, the Q-combinations coincide with standard convex combinations, since Q(k|x) = 1 for all x. As in the standard boosting scenario, we will adopt a weak-learning assumption. However, our assumption here must hold for each source domain: for each domain k ∈ [p] and any distribution D over Sk, there exists a base classifier h ∈ Hk such that the weighted loss of h is γ-better than random: 1 2 [1− Ei∼D[yk,ih(xk,i)] ≤ 1 2 − γ, for some edge value γ > 0. This is equivalent to the existence of a weak-learning algorithm for each domain, which is a mild assumption. As in the standard boosting scenario, this corresponds to the existence of a a good rule of thumb for each domain. Unlike the standard scenario, however, here, we seek a Q-ensemble and further require that ensemble to be accurate for any target mixture Dλ, λ ∈ Λ. Note that the definition of the hypothesis set Hk and the weak-learning assumption for domain k are intimately related: the elements of Hk are typically simple predictors sufficient to guarantee the weak-learning assumption for that domain.
In the next section, we present an algorithm, MULTIBOOST, for deriving an accurate Q-ensemble for any target mixture domain that belongs to the convex combination of the source domains. In Appendix L, we further present a multi-class extension of our algorithm, MCMULTIBOOST.

heading: 3 Algorithm
text: Let Φ be a convex, increasing and differentiable function such that u 7→ Φ(−u) upper-bounds the binary loss u 7→ 1u≤0. Φ could be the exponential function as in ADABOOST or the logistic function, as in logistic regression. Using Φ to upper-bound the agnostic loss leads to the following objective function for an ensemble f defined by (3) for any α = (αl,j)(l,j)∈[p]×[Nl] ≥ 0:
F (α) = max λ∈Λ p∑ k=1 λk mk mk∑ i=1 Φ ( −yk,i p∑ l=1 Nl∑ j=1 αl,jQ(l|xk,i)hl,j(xk,i) ) . (4)
Since a convex function composed with an affine function is convex and a sum of convex functions is convex, F is convex as the maximum of a set of convex functions. In this section, we will consider the case where the set Λ coincides with the full simplex, that is Λ = ∆. F can then be expressed more simply as F = maxpk=1 Fk, with Fk(α) = 1 mk ∑mk i=1 Φ ( −yk,i ∑p l=1 ∑Nl j=1 αl,jQ(l|xk,i)hl,j(xk,i) ) .
It is known that ADABOOST coincides with coordinate descent applied to an exponential loss objective function (Duffy and Helmbold, 1999; Schapire and Freund, 2012; Mohri et al., 2018). Our algorithm similarly applies coordinate descent to the objective just described, as with other boosting-type algorithms (Mason et al., 1999; Cortes et al., 2014; Kuznetsov et al., 2014). While convex, F is not differentiable and, in general, coordinate descent may not succeed in such cases (Tseng, 2001; Luo and Tseng, 1992). This is because the algorithm may be stuck at a point where no progress is possible along any of the axis directions, while there exists a favorable descent along some other direction. However, we will show that, under the weak-learning assumption we adopted, at any point α and for each active function Fk, that is Fk such that Fk(α) = F (α), there exists a coordinate direction along which a descent progress is possible. We will assume that these directions are also descent directions for F . More generally, it suffices in fact that one such direction admits this guarantee. Alternatively, one can replace the maximum with a soft-max, that is the (x1, . . . , xk) 7→ 1µ log( ∑p k=1 e
µxk) for µ > 0, which leads to a continuously differentiable function with a close approximation for µ sufficiently large.
Description. Let αt−1 denote the value of the parameter vector α = (αl,j) at the end of the (t− 1)th iteration and ft−1 the corresponding function: ft−1 = ∑p l=1 ∑Nl j=1 αt−1,l,jQ(l|·)hl,j . Coordinate descent at iteration t consists of choosing a direction eq,r corresponding to base classifier hq,r and a step value η > 0 to minimize F (αt−1 + η eq,r).
To select a direction, we consider the subdifferential of F along any eq,r. Since functions Fk are differentiable, by the subdifferential calculus for the maximum of functions, the subdifferential of F at αt−1 along the direction eq,r is given by: ∂F (αt−1, eq,r) = conv{F ′k(αt−1, eq,r) : k ∈ Kt}, where F ′k(αt−1, eq,r) is the directional derivative of Fk at αt−1 along the direction eq,r and where Kt = {k ∈ [p] : Fk(αt−1) = F (αt−1)}. We will therefore consider the direction eq,r with the largest absolute directional derivative value |F ′k(αt−1, eq,r)|, k ∈ Kt, but will restrict ourselves to q = k since, as we shall see, that will suffice to guarantee a non-zero directional gradient. To do so, we will express F ′k(αt−1, ek,r) in terms of the distribution Dt(k, ·) over Sk defined by Dt(k, i) = Φ′(−yk,ift−1(xk,i)) Zt,k , with Zt,k = ∑mk i=1 Φ ′(−yk,ift−1(xk,i)), for all i ∈ [mk]:
F ′k(αt−1, hk,r) = 1
mk mk∑ i=1 −yk,iQ(k|xk,i)hk,r(xk,i)Φ′ ( −yk,ift−1(xk,i) ) = Zt,k mk [2 t,k,r − 1],
where t,k,r = 12 [ 1− Ei∼Dt(k,·)[yk,iQ(k|xk,i)hk,r(xk,i)] ] denotes the weighted error of Q(k|·)hk,r. For any s ∈ [mk], since xk,s is a sample drawn from Dk, we have Q(k|xk,s) > 0 and therefore we have: Qt,k = ∑mk s=1 Dt(k, s)Q(k|xk,s) > 0. Thus, we can write Ei∼Dt(k,·)[yk,iQ(k|xk,i)hk,r(xk,i)] as mk∑ i=1 Dt(k, i)Q(k|xk,i)yk,ihk,r(xk,i) Qt,k Qt,k,= E i∼D′t(k,·) [yk,ihk,r(xk,i)]Qt,k,
where D′t(k, i) = Dt(k,i)Q(k|xk,i)
Qt,k . By our weak-learning assumption, there exists r ∈ Nk such that
Ei∼D′t(k,·)[yk,ihk,r(xk,i)] ≥ γ > 0. For that choice of r, we have t,k,r < 1 2−γ, with γ = γQt,k > 0.
In view of that, it suffices for us to search along the directions hk,r and we do not need to consider the directional derivative of Fk along directions hq,r with q 6= k. The direction chosen by our coordinate descent algorithm is thus defined by: argmaxk∈Kt,r∈[Nk] Zt,k mk
[1− 2 t,k,r]. Given the direction ek,r, the optimal step value η is argminη>0 F (αt−1 + ηek,r). The pseudocode of our algorithm, MULTIBOOST, is provided in Figure 1. In the most general case, η can be found via a line search or other numerical methods.
Step size. In some special cases, the line search can be executed using a simpler expression by using an upper bound on F (αt−1 + ηek,r). Using the convexity of Φ, since yl,iQ(k|xl,i)hk,r(xl,i) = 1+yl,iQ(k|xl,i)hk,r(xl,i)
2 · (+1) + 1−yl,iQ(k|xl,i)hk,r(xl,i) 2 · (−1), the following holds for all η ∈ R:
Φ(−yl,ift−1(xl,i)− η yl,iQ(k|xl,i)hk,r(xl,i)) ≤ 1+yl,iQ(k|xl,i)hk,r(xl,i)2 Φ(−yl,ift−1(xl,i)− η)
+ 1−yl,iQ(k|xl,i)hk,r(xl,i)
2 Φ(−yl,ift−1(xl,i) + η).
In the case of exponential and logistic functions, the following upper bounds can then be derived.
Lemma 1. For any k ∈ [p], the following upper bound holds when Φ is the exponential or the logistic function:
F (αt−1 + ηek,r) ≤ max l∈[p] Zt,l ml
[ (1− t,l,k,r)e−η + t,l,k,reη ] ,
where t,l,k,r = 12 [ 1− Ei∼Dt(l,·)[yl,iQ(k|xl,i)hk,r(xl,i)] ] .
For any k, function η 7→ (1− t,l,k,r)e−η + t,l,k,reη reaches its minimum for η = 12 log 1− t,l,k,r t,l,k,r
. When the maximum is achieved for l = k, the solution coincides with the familiar expression of the step size ηt = 12 log 1− t,k,r t,k,r used in ADABOOST.
MULTIBOOST(S1, . . . , Sp) 1 α0 ← 0 2 for t← 1 to T do 3 ft−1 ← ∑p l=1 ∑Nl j=1 αt−1,l,jQ(l|·)hl,j
4 Φ̃k ← 1mk ∑mk i=1 Φ(−yk,ift−1(xk,i))
5 Kt ← { k : k ∈ argmaxk∈[p] Φ̃k } 6 for k ∈ Kt do 7 Zt,k ← ∑mk i=1 Φ
′(−yk,ift−1(xk,i)) 8 for i← 1 to mk do 9 Dt(k, i)← Φ ′(−yk,ift−1(xk,i)) Zt,k
10 (k, r)← argmax k∈Kt,r∈[Nk] Zt,k mk [1− 2 t,k,r] 11 ηt ← argminη>0 F (αt−1 + ηek,r) 12 αt ← αt−1 + ηtek,r 13 f ← ∑p l=1 ∑Nl j=1 αT,l,jQ(l|·)hl,j 14 return f
Figure 1: Pseudocode of the MULTIBOOST algorithm. t,k,r = 1 2
[ 1− Ei∼Dt(k,·)[yk,iQ(k|xk,i)hk,r(xk,i)] ] de-
notes the weighted error of Q(k|·)hk,r .
Q-function. The conditional probability functions Q(k|·) are crucial to the definition of our algorithm. As pointed out earlier, Qensembles can help achieve accurate solutions in some cases that cannot be realized using convex combinations. Furthermore, for any k ∈ [p], since Dt(k, ·) is a distribution over the sample Sk, it is natural to assume that for any j 6= k we have Es∼Dt(k,·)[Q(k|xk,s)] ≥ Es∼Dt(k,·)[Q(j|xk,s)]. This implies the following lower bound: Es∼Dt(k,·)[Q(k|xk,s)] ≥ 1 p , which in turn implies γ ≥ γ p , since for
any x ∈ X, ∑p j=1 Q(j|x) = 1. In the special case where all domains coincide, we have Q(k|xk,s) = 1p for all s and this lower bound is reached. At another extreme, when all domains admit distinct supports, we have Q(k|xk,s) = 1 for all s ∈ [mk] and thus γ = γ.
In practice, we do not have access to the true conditional probabilities Q(k|·). Instead, we can derive accurate estimates Q̂(k|·) using large unlabeled samples from the source do-
mains, the label used for training being simply the domain index. This can be done using algorithms such as conditional maximum entropy models (Berger et al., 1996) (or multinomial logistic regression), which benefit from strong theoretical guarantees (Mohri et al., 2018, Chapter 13), or other rich models based on neural networks.
Other variants of MULTIBOOST. In Appendix D, we present and discuss other variants of our algorithm, including their convergence guarantees.

heading: 4 Theoretical analysis
text: In this section, we present a theoretical analysis of our algorithm, including margin-based learning bounds for multiple-source Q-ensembles.
For any k ∈ [p], define the family Gk as follows: Gk = { Q(k|·)h : h ∈ Hk } . Then, the family of
ensemble functions F that we consider can be defined as F = conv( ⋃p k=1 Gk). For any λ ∈ ∆,
let Dλ be the distribution defined by Dλ = ∑p k=1 λkD̂k, where D̂k is the empirical distribution associated to an i.i.d. sample Sk drawn from Dk. Dλ is distinct from the distribution associated to Dλ. We seek to derive margin-based bounds for ensemble functions f ∈ F with respect to target mixture distributions Dλ, while the empirical data is from multiple source distributions Dk, or from Dλ. Thus, these guarantees differ from standard learning bounds where the source and target distribution coincide.
For any distribution D over X × Y and ρ > 0, let Lρ(D, f) denote the expected ρ-margin loss of f with respect to D: Lρ(D, f) = E(x,y)∼Dk [I(yf(x) ≤ ρ)]. We denote by Rm(F) the Rademacher complexity of F for samples S = (x1, . . . , xm) of size m, defined by Rm(F) = ES∼Dm
σ [supf∈F
∑m i=1 σif(xi)], with σis independent random variables taking values in {−1,+1}.
The following gives a margin-bound for our multiple-source learning with Q-ensembles. Theorem 1. Fix ρ > 0. Then, for any δ > 0, with probability at least 1−δ over the draw of a sample S = (S1, . . . , Sp) ∼ Dm11 ⊗ · · · ⊗D mp p , the following inequality holds for all ensemble functions
f = ∑T t=1 αtQ(kt|·)ht ∈ F and all λ ∈ ∆:
L(Dλ, f) ≤ Lρ(Dλ, f) + p∑ k=1 λk 2 ρ max l∈[p] Rmk(Hl) + √ log pδ 2mk . (5) Note that the complexity term depends only on the Rademacher complexities of the families of based predictors Hl and does not involve the domain classification function Q. Theorem 1 improves upon previous known bounds of Mohri et al. (2019). In particular, it provides a dimension-independent margin guarantee for the zero-one loss, while the bound of Mohri et al. (2019), when applied to the zero-one loss, is dimension-dependent (Mohri et al., 2019, Lemma 3). Additionally, our bound holds for Q-ensembles. Our margin bound can be straightforwardly generalized to hold uniformly for all ρ ∈ (0, 1), at the cost of an additional mild term depending on log log2(2/ρ) (see Theorem 4 in Appendix E). For the ensemble functions returned by our algorithm, the bound applies to x 7→ f(x)‖α‖1 . These learning guarantees suggest choosing α ≥ 0 and ρ to minimize the following:
max λ∈Λ p∑ k=1 λk
{ E
(x,y)∼Sk
[ I ( y
T∑ t=1 αt ‖α‖1 Q(kt|·)ht(x) ≤ ρ )] + rk ρ } ,
where rk = 2 maxl∈[p] Rmk(Hl). Choosing 1 ρ = ‖α‖1 and upper bounding the binary loss using a convex function Φ, the problem can then be equivalently cast as the following unconstrained minimization, for example in the case of the exponential function:
min α≥0 max λ∈Λ p∑ k=1 λk
{ E
(x,y)∼Sk
[ exp ( −y
T∑ t=1 αtQ(kt|·)ht(x)
)] + rk‖α‖1 } .
Thus, the learning guarantees justify a posteriori an `1-regularized version of our algorithm. It is straightforward to derive that extension of our algorithm and its pseudocode. This is similar to the extension to the `1-ADABOOST (Rätsch et al., 2001) of the original unregularized ADABOOST (Freund and Schapire, 1997). Let us add that finer learning guarantees such as those for DEEP BOOSTING (Cortes et al., 2014) ones can be derived similarly here, which would lead to a weighted `1-regularization, where the weights are the Rademacher complexities of the families Hk. For the sake of simplicity, we do not detail that extension. Let us point out, however, that such an extension would also lead to an algorithm generalizing ADANET (Cortes et al., 2017) to multiple sources.
In some applications, prior knowledge can be used to constrain Λ to a strict subset of the simplex ∆. Finer margin-based learning guarantees can be derived to cover that scenario. Let Λ be the set of
vertices of a subsimplicial cover of Λ, that is a decomposition of a cover of Λ into subsimplices and let Λ be the set of λs -close to Λ in `1-distance. Then, the following guarantees hold. Theorem 2. Fix ρ > 0 and > 0. Then, for any δ > 0, with probability at least 1− δ over the draw of a sample S = (S1, . . . , Sp) ∼ Dm11 ⊗ · · · ⊗D mp p , each of the following inequalities holds:
1. for all ensemble functions f = ∑T t=1 αtQ(kt|·)ht ∈ F and all λ ∈ Λ :
L(Dλ, h) ≤ Lρ(Dλ, h) + 2
ρ max r∈[p]
Rm(Hr, λ) + 3
2 + √√√√ p∑ k=1 λ2k 2mk log |Λ| δ . (6)
2. for all ensemble functions f = ∑T t=1 αtQ(kt|·)ht ∈ F and all λ = ∑p k=1 µkβk ∈ conv(Λ):
L(Dλ, h) ≤ Lρ(Dλ, h) + 2
ρ p∑ l=1 µk max r∈[p] Rm(Hr, βl) + p∑ k=1 µk √√√√ p∑ l=1 β2l,k 2mk log |Λ| δ . (7)
The proof of the theorem and further discussion are presented in Appendix F. Here, Rm(Hr, λ) is the λ-weighted Rademacher complexity of Hr (see Appendix F). For Λ a strict subset of the simplex, these learning bounds suggest an algorithm with a regularization term of the form ∑p k=1 λ 2 k/mk. Our analysis and learning guarantees can be similarly extended to cover the multi-class setting.
5 Federated MULTIBOOST algorithm
In this section, we present an extension of our algorithm to the federated learning scenario, called FEDMULTIBOOST. The pseudocode is given in Figure 2. Federated learning is a distributed learning scenario where a global model is trained at the server level, based on data remaining at clients (Konečnỳ et al., 2016b,a; McMahan et al., 2017; Yang et al., 2019). Clients are typically mobile phones, network sensors, or other IoT devices. While the data remains at the clients, the trained model significantly benefits from user data, as demonstrated, for example, in next word prediction (Hard et al., 2018; Yang et al., 2018) and healthcare applications (Brisimi et al., 2018). We refer the reader to (Kairouz et al., 2021) for a more detailed survey of federated learning.
A widely used algorithm in this scenario is federated averaging, where the server trains the global model via stochastic updates from the clients (McMahan et al., 2017). It has been argued by Mohri et al. (2019), however, that minimizing the expected loss with respect to a particular training distribution, as done by standard federated learning algorithms, may be riskprone and benefit only a specific subset of clients. This compromises fairness,
which is one of the critical questions in federated learning, where clients are often heterogeneous (Bickel et al., 1975; Hardt et al., 2016; Abay et al., 2020; Li et al., 2020). This issue can be further
accentuated when the set of participating clients during inference may significantly differ from those used in training. Such cases may occur, for example, when clients loose access to network connection during training, which results in distinct training and test distributions.
To overcome these problems, we adopt the agnostic federated learning approach suggested by Mohri et al. (2019) and Ro et al. (2021). Following the client-partition approach of Ro et al. (2021), let each client belong to one of p domains. The domains can be, for example, based on the type of device or their geographical location. In this setting, the global model is optimized for all convex combinations of domain distributions as in the objective of MULTIBOOST (Equation 4), by taking the maximum over the mixtures weights λ. This ensures that the solution obtained is risk-averse and reduces the worst-case mismatch between the inference and training distributions. We propose FEDMULTIBOOST, a communication-efficient modification of MULTIBOOST, that can overcome the communication bottleneck in federated learning (Konečnỳ et al., 2016b).
Before presenting our algorithm, we first describe the learning scenario and the notation we adopt. Let n be the number of clients, which in the cross-device setting can be in the order of millions. Let mc denote the number of samples in client c and (xc,i, yc,i) denote the ith sample of client c. The server has access to a set of base-predictor classes Hk for k ∈ [p] and a domain classifier Q that assigns for each sample x, the likelihood of it belonging to each of the p domains. The base classifiers can be obtained by training on public data or training on client data with federated learning. The domain classifier Q can be trained using unlabeled client data.
Additional discussion of the algorithm as well as experimental results can be found in Appendix G. At each round, the algorithm randomly selects r clients and s base classifiers from each domain. Next, it chooses the best classifier out of the previously selected subset, based on the data from the subsampled clients. Since FEDMULTIBOOST operates only on a small set of base classifiers at each round, the algorithm is communication-efficient. At round t, the server needs to send Q, ft−1, and s base classifiers to the selected clients. Hence, the server-to-client communication cost at round t is O((t+ s)K +K ′), where K is the number of parameters in a single base classifier and K ′ is the number of parameters required to specify Q. Furthermore, the clients communicate only the aggregate statistics Φ̃c, Zt,c, βt,c,r to the server and hence the client-to-server communication is O(p · s) real numbers, which is independent of the number of parameters of the base classifiers. We note that FEDMULTIBOOST can be extended to the multi-class setting using techniques presented in Appendix L.

heading: 6 Experiments
text: In this section, we present experimental results for the MULTIBOOST algorithm on several multiplesource datasets. Our study is restricted to learning an ensemble of decision stumpsHstumps using the exponential surrogate loss Φ(u) = e−u. To estimate the probabilities Q(k|·) for k ∈ [p], we assigned the label k to each sample from domain k and used multinomial logistic regression. This step can be facilitated with unlabeled examples, as only their domain membership information is required.
We compare MULTIBOOST with a set of boosting-style algorithms that operate on the same hypotheses class Hstumps. Those include ADABOOST-k for k ∈ [p] and ADABOOST-all. The former is a standard ADABOOST algorithm trained only on a single source Sk and the latter is ADABOOST trained on the union of all sources ∪pk=1Sk. It is natural to compare MULTIBOOST against ADABOOST-all, since both of them have access to all sources during training. The difference is that while ADABOOSTall treats ∪pk=1Sk as a single dataset, MULTIBOOST trains base learners separately for each source and weights examples by domain probabilities Q(k|·). We used T = 100 boosting steps for all benchmarks. T up to 1,000 were explored, but did not change any results significantly.
We also compare our results with the a multiple-source adaptation algorithm, DMSA, designed for a scenario where no labeled data is available, and where only an accurate predictor per domain and unlabeled data are supplied. DMSA was shown to outperform other algorithms designed for that scenario. To apply DMSA, we use the domain predictors ADABOOST-k, k ∈ [p]. We report classification errors on the test data for various mixtures of the source distributions λ1, . . . , λp, including: errors for λ on the simplex ∆ edges (errors on each domain separately); errors on the uniform mixture ∀k : λk = 1p ; agnostic error, which is the maximum error across all sources. The errors and their standard deviations are reported based on 10-fold cross validation. Each source
Sk is independently split into 10 folds S1k, . . . , S 10 k . For the i-th cross-validation step, the test set is {Si1, . . . , Sip}, while the rest is used for training. Datasets and preprocessing steps used are described below with additional dataset details provided in Appendix H. Note, that all datasets are public and do not contain any personal identifiers or offensive information. The experiments were performed on Linux and Mac workstations with Quad-Core Intel Core i7 2.9 GHz and Intel Xeon 2.20 GHz respectively. The time taken to perform 10-fold cross-validation varies per dataset: from roughly 1 hour on CPU for all benchmarks on tabular data to 8 hours on CPU for all benchmarks on digits data. The run-times of a single MULTIBOOST iteration is almost identical to that of ADABOOST-all when a closed form solution is used for step size ηt (line 12 in Figure 1) for the exponential surrogate loss function. Alternatively, for some experiments we used line search with 100 steps. If training time is critical, one can use ηt = C/ √ t instead, at the cost of slightly worse convergence guarantee. Convergence plots are illustrated in Appendix I.
Sentiment analysis. The Sentiment dataset (Blitzer et al., 2007) consists of text reviews and rating labels for products sold on Amazon in various categories. We selected p = 3 sources from this dataset, where k = 1 corresponds to books, k = 2 means dvd, and k = 3 is electronics.
We converted the 5-star rating to binary labels, assigning y = +1 for a positive review and y = −1 for a negative one. Neutral reviews with 3-star labels are removed from the dataset. The benchmarks are trained using bigram features generated from the raw text reviews. Since the Sentiment dataset contains only 2,000 instances for each domain, we used random train/test splits with 10 different seeds instead of the 10-fold cross-validation. To illustrate the importance of the conditional domain probabilities Q(K|x), for each domain, we illustrate its values along the projections of x onto the first principal component of the joint Sentiment dataset in Figure 3. The figure shows that our domain classifiers are able to provide coherent separation between the three domains and narrow the applicability of the base classifiers.
In Appendix K, we further discuss the importance of obtaining a high-quality Q function and illustrate the performance degradation resulting from a lower-quality Q function.
Digits recognition. For this problem, we aggregated 32x32 pixel handwritten digits images from p = 3 sources: MNIST (k = 1), SVHN (k = 2), MNIST-M (k = 3). We compared algorithms on two binary classification problems: digits 4 vs. 9 and digits 1 vs. 7.
Object recognition. We divided images of clothes items from Fashion-MNIST (Xiao et al., 2017) dataset into two classes: tops and bottoms from p = 3 sources. k = 1 consists of t-shirts, pullovers, trousers; k = 2 consists of dresses, coats, sandals; k = 3 consists of shirts, bags, sneakers, ankle-boots.
Tabular data. In addition to text and images, we tested MULTIBOOST on tabular data. We used the Adult dataset (Kohavi, 1996), which consists of numerical and categorical features describing an individual’s socioeconomic characteristics, given the task to predict if an person’s income exceeds USD 50, 000. We divided this dataset into p = 3 sources based on individual’s educational background. Source k = 1 consisted of individuals with a university degree (BSc, MS or PhD), source k = 1 those with only a High School diploma, and source k = 2, none of the above.
Discussion As can be seen from Table 4, MULTIBOOST provides agnostic and uniform errors that are significantly better than the baselines on all datasets. While ADABOOST-k predictors on digits recognition and object recognition tasks each show the lowest error on their specific domains D1,D2,D3, they fail to generalize to other target distribution in conv{D1,D2,D3}. Moreover, as suggested by the discussion in Section 2, the standard convex combination of domain-specific predictors (ADABOOST-all) also performs poorly on several target distributions in conv{D1,D2,D3}, such as the uniform and agnostic targets. As the experimental results confirm, MULTIBOOST, by leveraging domain predictors Q(k|·) and the agnostic loss, is able to produce an ensemble of domain-specific predictors that generalizes to different targets. Appendix I provides additional illustrations of Q(k|·) by projecting each domain on the first principal component of the joint data.
Moreover, for tabular data and the digits (4 vs. 9) classification problem, MULTIBOOST benefits from positive knowledge transfer and obtains an error on individual domains that is even smaller than that
ADABOOST-1 0.326 ± 0.019 0.300 ± 0.008 0.360 ± 0.017 0.329 ± 0.017 0.360 ± 0.019 ADABOOST-2 0.354 ± 0.020 0.266 ± 0.009 0.336 ± 0.023 0.318 ± 0.019 0.357 ± 0.019 ADABOOST-3 0.402 ± 0.015 0.334 ± 0.008 0.258 ± 0.015 0.331 ± 0.016 0.402 ± 0.018 ADABOOST-all 0.354 ± 0.020 0.325 ± 0.011 0.313 ± 0.022 0.324 ± 0.021 0.354 ± 0.016 DMSA 0.332 ± 0.021 0.308 ± 0.017 0.314 ± 0.015 0.318 ± 0.019 0.332 ± 0.021 MULTIBOOST 0.332 ± 0.027 0.288 ± 0.018 0.284 ± 0.027 0.301 ± 0.027 0.332 ± 0.024
Digits Recognition (4 vs. 9)
ADABOOST-1 0.044 ± 0.007 0.615 ± 0.012 0.476 ± 0.022 0.379 ± 0.008 0.615 ± 0.012 ADABOOST-2 0.455 ± 0.014 0.299 ± 0.011 0.504 ± 0.015 0.420 ± 0.011 0.504 ± 0.015 ADABOOST-3 0.549 ± 0.034 0.488 ± 0.015 0.300 ± 0.013 0.446 ± 0.013 0.549 ± 0.034 ADABOOST-all 0.060 ± 0.009 0.374 ± 0.015 0.353 ± 0.012 0.262 ± 0.009 0.374 ± 0.015 DMSA 0.069 ± 0.005 0.351 ± 0.012 0.310 ± 0.011 0.243 ± 0.009 0.351 ± 0.015 MULTIBOOST 0.096 ± 0.008 0.283 ± 0.028 0.246 ± 0.014 0.209 ± 0.013 0.284 ± 0.027
Digits Recognition (1 vs. 7)
ADABOOST-1 0.005 ± 0.002 0.613 ± 0.007 0.519 ± 0.012 0.379 ± 0.004 0.613 ± 0.007 ADABOOST-2 0.431 ± 0.022 0.252 ± 0.009 0.479 ± 0.012 0.387 ± 0.010 0.479 ± 0.012 ADABOOST-3 0.680 ± 0.031 0.490 ± 0.014 0.244 ± 0.012 0.474 ± 0.013 0.680 ± 0.031 ADABOOST-all 0.014 ± 0.003 0.286 ± 0.010 0.306 ± 0.012 0.202 ± 0.005 0.306 ± 0.011 DMSA 0.012 ± 0.003 0.288 ± 0.017 0.286 ± 0.015 0.195 ± 0.013 0.288 ± 0.017 MULTIBOOST 0.026 ± 0.004 0.261 ± 0.013 0.257 ± 0.015 0.181 ± 0.005 0.261 ± 0.011
Objects Recognition (Fashion-MNIST)
ADABOOST-1 0.015 ± 0.003 0.251 ± 0.026 0.602 ± 0.028 0.288 ± 0.017 0.602 ± 0.028 ADABOOST-2 0.435 ± 0.007 0.015 ± 0.002 0.169 ± 0.012 0.173 ± 0.003 0.435 ± 0.007 ADABOOST-3 0.311 ± 0.018 0.097 ± 0.005 0.014 ± 0.002 0.140 ± 0.006 0.311 ± 0.018 ADABOOST-all 0.036 ± 0.004 0.020 ± 0.002 0.025 ± 0.003 0.027 ± 0.002 0.036 ± 0.004 DMSA 0.033 ± 0.008 0.015 ± 0.002 0.022 ± 0.003 0.023 ± 0.007 0.033 ± 0.009 MULTIBOOST 0.028 ± 0.003 0.015 ± 0.003 0.022 ± 0.002 0.021 ± 0.001 0.028 ± 0.003
Tabular Data (Adult Data)
ADABOOST-1 0.201 ± 0.012 0.249 ± 0.021 0.215 ± 0.014 0.222 ± 0.012 0.249 ± 0.021 ADABOOST-2 0.298 ± 0.011 0.131 ± 0.009 0.142 ± 0.006 0.190 ± 0.007 0.298 ± 0.011 ADABOOST-3 0.225 ± 0.015 0.138 ± 0.010 0.133 ± 0.011 0.165 ± 0.008 0.225 ± 0.015 ADABOOST-all 0.221 ± 0.013 0.134 ± 0.007 0.131 ± 0.010 0.155 ± 0.004 0.221 ± 0.013 DMSA 0.195 ± 0.014 0.137 ± 0.005 0.131 ± 0.008 0.154 ± 0.005 0.195 ± 0.014 MULTIBOOST 0.190 ± 0.014 0.132 ± 0.008 0.130 ± 0.009 0.150 ± 0.005 0.190 ± 0.014
of the domain-specific predictors. From Figure 6 in Appendix I it can be seen that the α-weight for the MULTIBOOST classifier in the 4 vs. 9 problem is heavily centered on D2, but contributions from D1 and D3 adds to the stronger performance. The same figure also illustrates the α-mass distribution for the other classification tasks. The standard convex ensemble ADABOOST-all, however, does not seem to exhibit the positive transfer property. Similar conclusions carry over for other target distributions in conv{D1,D2,D3}, for the sake of simplicity we do not present them here.

heading: 7 Conclusion
text: We presented a new boosting algorithm, MULTIBOOST, for a multiple-source scenario – a common setting in domain adaptation problems – where the target distribution can be any mixture of the source distributions. We showed that our algorithm benefits from strong theoretical guarantees and exhibits favorable empirical performance. We also highlighted the extension of our work to the federated learning scenario, which is a critical distributed learning setting in modern applications.

heading: Acknowledgments
text: This work was partly supported by NSF CCF-1535987, NSF IIS-1618662, and a Google Research Award.

Review summaries:
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. 

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. 

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. 

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.