---
abstract: 'We present a new discriminative technique for the multiple-source adaptation, MSA, problem. Unlike previous work, which relies on density estimation for each source domain, our solution only requires conditional probabilities that can easily be accurately estimated from unlabeled data from the source domains. We give a detailed analysis of our new technique, including general guarantees based on Rényi divergences, and learning bounds when conditional Maxent is used for estimating conditional probabilities for a point to belong to a source domain. We show that these guarantees compare favorably to those that can be derived for the generative solution, using kernel density estimation. Our experiments with real-world applications further demonstrate that our new discriminative MSA algorithm outperforms the previous generative solution as well as other domain adaptation baselines.'
bibliography:
- 'mad.bib'
title: 'A Discriminative Technique for Multiple-Source Adaptation'
---

Introduction
============

Learning algorithms are applied to an increasingly broad array of problems. For some tasks, large amounts of labeled data are available to train very accurate predictors. But, for most new problems or domains, no such supervised information is at the learner's disposal. Furthermore, labeling data is costly since it typically requires human inspection and agreements between multiple expert labelers. Can we leverage past predictors learned for various domains and combine them to devise an accurate one for a new task? Can we provide guarantees for such combined predictors? How should we define that combined predictor? These are some of the challenges of *multiple-source domain adaptation*.

The problem of domain adaptation from multiple sources admits distinct instances defined by the type of source information available to the learner, the number of source domains, and the amount of labeled and unlabeled data available from the target domain [@MansourMohriRostamizadeh2008; @MansourMohriRostamizadeh2009; @hoffman2018algorithms; @pan_tkda2010; @MuandetBalduzziScholkopf2013; @xu_eccv14; @hoffman_eccv12; @gong_icml13; @gong_nips13; @zhang2015multi; @ganin2016domain; @tzeng2015simultaneous; @motiian2017unified; @motiian2017few; @wang2019few; @konstantinov2019robust; @liu2015multiple; @saito2019semi; @wang2019transfer]. The specific instance we are considering is one where the learner has access to multiple source domains and where, for each domain, they only have at their disposal a predictor trained for that domain and some amount of unlabeled data. No other information about the source domains, in particular no labeled data is available. The target domain or distribution is unknown but it is assumed to be in the convex hull of the source distributions, or relatively close to that. The *multiple-source adaptation (MSA) problem* consists of combining relatively accurate predictors available for each source domain to derive an accurate predictor for *any* such new mixture target domain. This problem was first theoretically studied by @MansourMohriRostamizadeh2008 [@MansourMohriRostamizadeh2009] and subsequently by @hoffman2018algorithms, who further provided an efficient algorithm for this problem and reported the results of a series of experiments with that algorithm and favorable comparisons with alternative solutions.

As pointed out by these authors, this problem arises in a variety of different contexts. In speech recognition, each domain may correspond to a different group of speakers and an acoustic model learned for each domain may be available. Here, the problem consists of devising a general recognizer for a broader population, a mixture of the source domains [@liao_icassp13]. Similarly, in object recognition, there may be accurate models trained on different image databases and the goal is to come up with an accurate predictor for a general domain, which is likely to be close to a mixture of these sources [@efros_cvpr11]. A similar situation often appears in sentiment analysis and various other natural language processing problems where accurate predictors are available for some source domains such as TVs, laptops and CD players, each previously trained on labeled data, but no labeled data or predictor is at hand for the broader category of electronics, which can be viewed as a mixture of the sub-domains [@blitzer_acl07; @dredze_nips08].

An additional motivation for this setting of multiple-source adaptation is that often the learner does not have access to labeled data from various domains for legitimate reasons such as privacy or storage limitation. This may be for example labeled data from various hospitals, each obeying strict regulations and privacy rules. But, a predictor trained on the labeled data from each hospital may be available. Similarly, a speech recognition system trained on data from some group may be available but the many hours of source labeled data used to train that model may not be accessible anymore, due to the very large amount of disk space it requires. Thus, in many cases, the learner cannot simply merge all source labeled data to learn a predictor.

**Main contributions.** In Section \[sec:solutions\], we present a new *discriminative technique* for the MSA problem, Previous work showed that a *distribution-weighted combination* of source predictors benefited from favorable theoretical guarantees [@MansourMohriRostamizadeh2008; @MansourMohriRostamizadeh2009; @hoffman2018algorithms]. However, that *generative solution* requires an accurate density estimation for each source domain, which, in general, is a difficult problem. Instead, our solution only needs conditional probabilities, which is easier to accurately estimate from unlabeled data from the source domains. We also describe an efficient DC-programming optimization algorithm for determining the solution of our discriminative technique, which is somewhat similar to but distinct from that of previous work, since it requires a new DC-decomposition.

In Section \[sec:theory\], we give a new and detailed theoretical analysis of our technique, starting with new general guarantees that depend on the Rényi divergences between the target distribution and mixtures of the true source distributions, instead of mixtures of estimates of those distributions (Section \[sec:solutions\]). We then present finite sample learning bounds for our new discriminative solution when conditional Maxent is used for estimating conditional probabilities. We also give a new and careful analysis of the previous generative solution, when using kernel density estimation, including the first finite sample generalization bound for that technique. We show that the theoretical guarantees for our discriminative solution compare favorably to those derived for the generative solution in several ways. While we benefit from some of the analysis in previous work [@hoffman2018algorithms], our proofs and techniques for both solutions are new and non-trivial.

We further report the results of several experiments with our discriminative algorithm both with a synthetic dataset and several real-world applications (Section \[sec:experiments\]). Our results demonstrate that, in all tasks, our new solution outperforms the previous work's generative solution, which had been shown itself to surpass empirically the accuracy of other domain adaptation baselines @hoffman2018algorithms. They also indicate that our discriminative technique requires fewer samples to achieve a high accuracy than the previous solution, which matches our theoretical analysis.

**Related work.** There is a very broad literature dealing with single-source and multiple-source adaptation with distinct scenarios. Here, we briefly discuss the most related previous work, in addition to [@MansourMohriRostamizadeh2008; @MansourMohriRostamizadeh2009; @hoffman2018algorithms]. The idea of using a domain classifier to combine domain-specific predictors has been suggested in the past. @jacobs1991adaptive and @nowlan1991evaluation considered an adaptive mixture of experts model, where there are multiple expert networks, as well as a gating network to determine which expert to use for each input. The learning method consists of jointly training the individual expert networks and the gating network. In our scenario, no labeled data is available, expert networks are pre-trained separately from the gating network, and our gating network admits a specific structure. @hoffman_eccv12 learned a domain classifier via SVM on all source data combined, and predicted on new test points with the weighted sum of domain classifier's scores and domain-specific predictors. Such linear combinations were later shown by @hoffman2018algorithms to perform poorly in some cases and not to benefit from strong guarantees. More recently, @xu2018deep deployed multi-way adversarial training to multiple source domains to obtain a domain discriminator, and also used a weighted sum of discriminator's scores and domain-specific predictors to make predictions. @zhao2018adversarial considered a scenario where labeled samples are available, unlike our scenario, and learned a domain classifier to approximate the discrepancy term in a MSA generalization bound, and proposed the MDAN model to minimize the bound.

We start with a description of the learning scenario we consider and the introduction of notation and definitions relevant to our analysis (Section \[sec:setup\]).

Learning Scenario {#sec:setup}
=================

We consider the MSA problem in the general stochastic scenario studied by @hoffman2018algorithms and adopt the same notation.

Let ${{\mathscr X}}$ denote the input space, ${{\mathscr Y}}$ the output space. We will identify a *domain* with a distribution over ${{\mathscr X}}\times
{{\mathscr Y}}$. There are $p$ source domains ${{\mathscr D}}_1, \ldots, {{\mathscr D}}_p$. As in previous work, we adopt the assumption that the domains share a common conditional probability ${{\mathscr D}}(\cdot | x)$ and thus ${{\mathscr D}}_k(x, y) = {{\mathscr D}}_k(x) {{\mathscr D}}(y | x)$, for all $(x, y) \in {{\mathscr X}}\times {{\mathscr Y}}$ and $k \in [p]$. This is a natural assumption in many common machine learning tasks. For example, in image classification, the label of a picture as a *dog* may not depend much on whether the picture is from a personal collection or a more general dataset. Nevertheless, as discussed in @hoffman2018algorithms, this condition can be relaxed and, here too, all our results can be similarly extended to a more general case where the conditional probabilities vary across domains. Since not all $k$ conditional probabilities are equally accurate on the single $x$, better target accuracy can be obtained by combining the ${{\mathscr D}}_k(x)$s in an $x$-dependent way.

For each domain ${{\mathscr D}}_k$, $k \in [p]$, the learner has access to some unlabeled data drawn i.i.d. from the marginal distribution ${{\mathscr D}}_k$ over ${{\mathscr X}}$, as well as to a predictor $h_k$. We consider two types of predictor functions $h_k$, and their associated loss functions $\ell$ under the *regression model (R)* and the *probability model (P)* respectively: $$\begin{aligned}
  & h_k \colon {{\mathscr X}}\to \Rset
  && \ell \colon \Rset \times {{\mathscr Y}}\to \Rset_+ & \text{(\emph{R})} \\
  & h_k  \colon {{\mathscr X}}\times {{\mathscr Y}}\to [0, 1]
  && \ell \colon [0, 1] \to \Rset_+ & \text{(\emph{P})}\end{aligned}$$ In the probability model, the predictors are assumed to be normalized: $\sum_{y \in {{\mathscr Y}}} h(x, y) = 1$ for all $x \in {{\mathscr X}}$. We will denote by ${\mathcal{L}}({{\mathscr D}}, h)$ the expected loss of a predictor $h$ with respect to the distribution ${{\mathscr D}}$: $$\begin{aligned}
  {\mathcal{L}}({{\mathscr D}}, h) & = \operatorname*{\mathbb{E}}_{(x, y) \sim {{\mathscr D}}} \big[\ell( h(x), y) \big] 
\quad\text{(\emph{R})}, \\
  {\mathcal{L}}({{\mathscr D}}, h) & = \operatorname*{\mathbb{E}}_{(x, y) \sim {{\mathscr D}}} \big[\ell(h(x, y)) \big] 
\quad\text{(\emph{P})}.\end{aligned}$$ Our theoretical results are general and only assume that the loss function $\ell$ is convex, continuous. But, in the regression model, we will be particularly interested in the squared loss $\ell(h(x), y) = (h(x) - y)^2$ and, in the probability model, the cross-entropy loss (or $\log$-loss) $\ell(h(x, y)) = -\log h(x, y)$.

We will also assume that each source predictor $h_k$ is ${\epsilon}$-accurate on its domain for some ${\epsilon}> 0$, that is, $\forall k \in [p], {\mathcal{L}}({{\mathscr D}}_k, h_k) \leq {\epsilon}$. Our assumption that the loss of $h_k$ is bounded, implies that $\ell(h_k(x), y) \leq M$ or $\ell(h_k(x,y))\leq M$, for all $(x, y) \in {{\mathscr X}}\times {{\mathscr Y}}$ and $k \in [p]$.

Let $\Delta = { \{ \lambda = (\lambda_1, \ldots, \lambda_p) \colon \sum_{k
    = 1}^p \lambda_k = 1, \lambda_k \geq 0  \} }$ denote the simplex in $\Rset^p$, and let ${\mathcal{D}}= { \{ {{\mathscr D}}_\lambda \colon {{\mathscr D}}_\lambda = \sum_{k = 1}^p \lambda_k
  {{\mathscr D}}_k, \lambda \in \Delta  \} }$ be the family of all mixtures of the source domains, that is the convex hull of ${{\mathscr D}}_k$s.

Since not all $k$ source predictors are necessarily equally accurate on the single input $x$, better target accuracy can be obtained by combining the $h_k(x)$s dependent on $x$. The MSA problem for the learner is exactly how to combine these source predictors $h_k$ to design a predictor $h$ with small expected loss for any unknown target domain ${{\mathscr D}}_T$ that is an element of ${\mathcal{D}}$, or any unknown distribution ${{\mathscr D}}_T$ close to ${\mathcal{D}}$.

Our theoretical guarantees are presented in terms of *Rényi divergences*, a broad family of divergences between distributions generalizing the relative entropy. The Rényi Divergence is parameterized by $\alpha \in [0, +\infty]$ and denoted by ${{\mathsf D}}_\alpha$. The $\alpha$-Rényi Divergence between two distributions ${{\mathscr P}}$ and ${{\mathscr Q}}$ is defined by: $${{\mathsf D}}_\alpha({{\mathscr P}}\parallel {{\mathscr Q}}) = \frac{1}{\alpha - 1}
  \log \mspace{-2mu} \bracket[\Bigg]{ \sum_{(x, y) \in {{\mathscr X}}\times {{\mathscr Y}}}
  \mspace{-20mu} {{\mathscr P}}(x, y)  \left[ \frac{{{\mathscr P}}(x, y)}{{{\mathscr Q}}(x, y)}
  \right]^{\alpha - 1} }\mspace{-3mu},$$ where, for $\alpha \in { \{ 0, 1, +\infty  \} }$, the expression is defined by taking the limit [@arndt]. For $\alpha = 1$, the Rényi divergence coincides with the relative entropy. We will denote by ${{\mathsf d}}_\alpha({{\mathscr P}}\parallel {{\mathscr Q}})$ the exponential of ${{\mathsf D}}_\alpha({{\mathscr P}}\parallel {{\mathscr Q}})$: $${{\mathsf d}}_\alpha({{\mathscr P}}\parallel {{\mathscr Q}}) 
= \bracket[\Bigg]{ \sum_{(x, y) \in {{\mathscr X}}\times {{\mathscr Y}}} 
\frac{{{\mathscr P}}^\alpha(x, y)}{{{\mathscr Q}}^{\alpha - 1}(x, y)}
}^{\frac{1}{\alpha - 1}}.$$

In the following, to alleviate the notation, we abusively denote the marginal distribution of a distribution ${{\mathscr D}}_k$ defined over ${{\mathscr X}}\times {{\mathscr Y}}$ in the same way and rely on the arguments for disambiguation, e.g. ${{\mathscr D}}_k(x)$ vs. ${{\mathscr D}}_k(x, y)$.

Discriminative MSA solution {#sec:solutions}
===========================

In this section we present our new solution for the MSA problem and give an efficient algorithm for determining its parameter. But first we describe the previous solution.

Previous Generative Technique
-----------------------------

In previous work, it was shown that, in general, standard convex combinations of source predictors can perform poorly [@MansourMohriRostamizadeh2008; @MansourMohriRostamizadeh2009; @hoffman2018algorithms]: in some problems, even when the source predictors have zero loss, no convex combination can achieve a loss below some constant for a uniform mixture of the source distributions. Instead, a *distribution-weighted* solution was proposed to the MSA problem. That solution relies on density estimates ${\widehat}{{\mathscr D}}_k$ for the marginal distributions $x \mapsto {{\mathscr D}}_k(x)$, which are obtained via techniques such as kernel density estimation, for each source domain $k \in [p]$ independently.

Given such estimates, the solution is defined as follows in the regression and probability models, for all $(x, y) \in {{\mathscr X}}\times {{\mathscr Y}}$: $$\begin{aligned}
{\widehat}h_z(x) & = \sum_{k = 1}^p \frac{z_k {\widehat}{{\mathscr D}}_k(x) }
{\sum_{j = 1}^p z_j {\widehat}{{\mathscr D}}_j(x) } h_k(x), 
\label{eq:h_reg} \\
{\widehat}h_z(x, y) & = \sum_{k = 1}^p\frac{z_k {\widehat}{{\mathscr D}}_k(x) }{
\sum_{j = 1}^p z_j {\widehat}{{\mathscr D}}_j(x) } h_k(x, y),
\label{eq:h_prob}\end{aligned}$$ with $z \in \Delta$ is a parameter determined via an optimization problem such that $h_z$ admits the same loss for all ${{\mathscr D}}_k$. We are assuming here that the estimates verify ${\widehat}{{\mathscr D}}_k(x) > 0$ for all $x \in {{\mathscr X}}$ and therefore that the denominators are positive. Otherwise, a small positive number $\eta > 0$ can be added to the denominators of the solutions, as in previous work. We are adopting this assumption only to simplify the presentation. For the probability model, the joint estimates ${\widehat}{{\mathscr D}}_k(x, y)$ used in [@hoffman2018algorithms] can be equivalently replaced by marginal ones ${\widehat}{{\mathscr D}}_k(x)$ since all domain distributions share the same conditional probabilities.

Since this previous work relies on density estimation, we will refer to it as a *generative solution to the MSA problem*, in short, <span>`GMSA`</span>. The technique benefits from the following general guarantee [@hoffman2018algorithms], where we extend the Rényi divergences to divergences between a distribution ${{\mathscr D}}$ and a set of distributions ${\mathcal{D}}$ and write ${{\mathsf D}}_\alpha({{\mathscr D}}\parallel {\mathcal{D}}) = \min_{{{\mathscr D}}\in {\mathcal{D}}} {{\mathsf D}}_\alpha({{\mathscr D}}\parallel {{\mathscr D}})$.

\[th:nestimate\] For any $\delta > 0$, there exists a $z \in \Delta$ such that the following inequality holds for any $\alpha > 1$ and arbitrary target distribution ${{\mathscr D}}_T$: $${\mathcal{L}}({{\mathscr D}}_T, {\widehat}h_z) 
\leq \left[({\widehat}{\epsilon}+ \delta) \, {{\mathsf d}}_\alpha({{\mathscr D}}_T \parallel {\widehat}{\mathcal{D}})
\right]^{\frac{\alpha- 1}{\alpha}} M^{\frac{1}{\alpha}},$$ where ${\widehat}{\epsilon}= \max_{k \in [p]} \Big[{\epsilon}\, {{\mathsf d}}_\alpha({\widehat}{{\mathscr D}}_k \parallel {{\mathscr D}}_k)
\Big]^{\frac{\alpha - 1}{\alpha}} M^{\frac{1}{\alpha }}$, and ${\widehat}{\mathcal{D}}= \left\{ \sum_{k = 1}^p \lambda_k {\widehat}{{\mathscr D}}_k\colon \lambda \in \Delta \right\}$.

The bound depends on the quality of the density estimates via the Rényi divergence between ${\widehat}{{\mathscr D}}_k$ and ${{\mathscr D}}_k$, for each $k \in [p]$, and the closeness of the target distribution ${{\mathscr D}}_T$ to the mixture family ${\widehat}{\mathcal{D}}$. For $\alpha = +\infty$, for ${{\mathscr D}}_T$ close to ${\widehat}{\mathcal{D}}$ and accurate estimates of ${{\mathscr D}}_k$, ${{\mathsf d}}_\alpha({{\mathscr D}}_T \parallel {\widehat}{\mathcal{D}})$ and ${{\mathsf d}}_\alpha({\widehat}{{\mathscr D}}_k \parallel {{\mathscr D}}_k)$ are close to one and the upper bound is as a result close to ${\epsilon}$. That is, with good density estimates, the error of $h_z$ is no worse than that of the source predictors $h_k$s. However, obtaining good density estimators is a difficult problem and in general requires large amounts of data. In the following section, we provide a new and less data-demanding solution based on conditional probabilities.

New Discriminative Technique {#subsec:gz}
----------------------------

Let ${{\mathscr D}}$ denote the distribution over ${{\mathscr X}}$ defined by ${{\mathscr D}}(x) = \frac{1}{p} \sum_{k = 1}^p {{\mathscr D}}_k(x)$. We will assume and can enforce that ${{\mathscr D}}$ is the distribution according to which we can expect to receive unlabeled samples from the $p$ sources to train our discriminator. We will denote by ${{\mathscr Q}}$ the distribution over ${{\mathscr X}}\times [p]$ defined by ${{\mathscr Q}}(x, k) = \frac{1}{p} {{\mathscr D}}_k(x)$, whose ${{\mathscr X}}$-marginal coincides with ${{\mathscr D}}$: ${{\mathscr Q}}(x) = {{\mathscr D}}(x)$.

Our new solution relies on estimates ${\widehat}{{\mathscr Q}}(k | x)$ of the conditional probabilities ${{\mathscr Q}}(k | x)$ for each domain $k \in [p]$, that is the probability that point $x$ belongs to source $k$. Given such estimates, our new solution to the MSA problem is defined as follows in the regression and probability models, for all $(x, y) \in {{\mathscr X}}\times {{\mathscr Y}}$: $$\begin{aligned}
{\widehat}g_z(x) 
& = \sum_{k = 1}^p \frac{z_k {\widehat}{{\mathscr Q}}(k | x) }
{\sum_{j = 1}^p z_j {\widehat}{{\mathscr Q}}(j | x) } h_k(x),
\label{eq:g_reg} \\
{\widehat}g_z(x, y) & = \sum_{k = 1}^p\frac{z_k {\widehat}{{\mathscr Q}}(k | x) }{
\sum_{j = 1}^p z_j {\widehat}{{\mathscr Q}}(j | x) } h_k(x, y),
\label{eq:g_prob}\end{aligned}$$ with $z \in \Delta$ being a parameter determined via an optimization problem. As for the <span>`GMSA`</span> solution, we are assuming here that the estimates verify ${\widehat}{{\mathscr Q}}(k | x) > 0$ for all $x \in {{\mathscr X}}$ and therefore that the denominators are positive. Otherwise, a small positive number $\eta > 0$ can be added to the denominators of the solutions, as in previous work. We are adopting this assumption only to simplify the presentation. Note that in the probability model, ${\widehat}g_z(x, y)$ is normalized since $h_k$s are normalized: $\sum_{y \in {{\mathscr Y}}} g_z(x, y) = 1$ for all $x \in {{\mathscr X}}$.

Since our solution relies on estimates of conditional probabilities of domain membership, we will refer to it as a *discriminative solution to the MSA problem*, <span>`DMSA`</span> in short.

Observe that, by the Bayes' formula, the conditional probability estimates ${\widehat}{{\mathscr Q}}(k | x)$ induce density estimates ${\widehat}{{\mathscr D}}_k(x)$ of the marginal distributions $x \mapsto {{\mathscr D}}_k(x)$: $$\label{eq:estimate_D_k}
{\widehat}{{\mathscr D}}_k(x) = \frac{{\widehat}{{\mathscr Q}}(k | x) {{\mathscr D}}(x)}{{\widehat}{{\mathscr Q}}(k)}$$ where ${\widehat}{{\mathscr Q}}(k) = \sum_{x \in {{\mathscr X}}} {\widehat}{{\mathscr Q}}(k | x) {{\mathscr D}}(x)$. For an exact estimate, that is ${\widehat}{{\mathscr Q}}(k | x) = {{\mathscr Q}}(k | x)$, the formula holds with ${\widehat}{{\mathscr Q}}(k) = \sum_{x \in {{\mathscr X}}} {{\mathscr Q}}(x, k) = \frac{1}{p}$. In light of this observation, we can establish the following connection between the <span>`GMSA`</span> and <span>`DMSA`</span> solutions.

\[prop:hzgz\] Let ${\widehat}h_z$ be the <span>`GMSA`</span> solution using the estimates ${\widehat}{{\mathscr D}}_k$ defined in . Then, for any $z \in \Delta$, we have ${\widehat}h_z = {\widehat}g_{z'}$ with $z'_k = \frac{z_k/{\widehat}{{\mathscr Q}}(k)}{\sum_{j = 1}^p z_j/{\widehat}{{\mathscr Q}}(j)}$, for all $k \in [p]$.

First consider the regression model. By definition of the <span>`GMSA`</span>solution, we can write: $$\begin{aligned}
{\widehat}h_z(x) 
& = \sum_{k = 1}^p \frac{z_k \frac{{\widehat}{{\mathscr Q}}(k | x) {{\mathscr D}}(x)}{{\widehat}{{\mathscr Q}}(k)}}{\sum_{j = 1}^p z_j \frac{{\widehat}{{\mathscr Q}}(j | x) {{\mathscr D}}(x)}{{\widehat}{{\mathscr Q}}(j)}} h_k(x) \\
& = \sum_{k = 1}^p \frac{\frac{z_k}{{\widehat}{{\mathscr Q}}(k)} {\widehat}{{\mathscr Q}}(k | x) }{\sum_{j
  = 1}^p \frac{z_j}{{\widehat}{{\mathscr Q}}(j)} {\widehat}{{\mathscr Q}}(j | x)} h_k(x) 
= g_{z'}(x).\end{aligned}$$ The probability model's proof is syntactically the same.

In view of this result, the <span>`DMSA`</span> technique benefits from a guarantee similar to <span>`GMSA`</span> (Theorem \[th:nestimate\]), where for <span>`DMSA`</span> the density estimates are based on the conditional probability estimates ${\widehat}{{\mathscr Q}}(k | x)$. We refer readers to the full version of the paper for all the proofs.

\[th:nestimate-bis\] For any $\delta > 0$, there exists a $z \in \Delta$ such that the following inequality holds for any $\alpha > 1$ and arbitrary target distribution ${{\mathscr D}}_T$: $${\mathcal{L}}({{\mathscr D}}_T, {\widehat}g_z) 
\leq \left[({\widehat}{\epsilon}+ \delta) \, {{\mathsf d}}_\alpha({{\mathscr D}}_T \parallel {\widehat}{\mathcal{D}})
\right]^{\frac{\alpha- 1}{\alpha}} M^{\frac{1}{\alpha}},$$ where ${\widehat}{\epsilon}= \max_{k \in [p]} \Big[{\epsilon}\, {{\mathsf d}}_\alpha({\widehat}{{\mathscr D}}_k \parallel {{\mathscr D}}_k)
\Big]^{\frac{\alpha - 1}{\alpha}} M^{\frac{1}{\alpha }}$, and ${\widehat}{\mathcal{D}}= \left\{ \sum_{k = 1}^p \lambda_k {\widehat}{{\mathscr D}}_k\colon \lambda
  \in \Delta \right\}$, with ${\widehat}{{\mathscr D}}_k(x, y) 
= \frac{{\widehat}{{\mathscr Q}}(k | x) {{\mathscr D}}(x, y)}{{\widehat}{{\mathscr Q}}(k)}$.

Optimization Algorithm {#subsec:alg}
----------------------

By Proposition \[prop:hzgz\], to determine the parameter $z'$ guaranteeing the bound of Theorem \[th:nestimate-bis\] for ${\widehat}g_{z'}$, it suffices to determine the parameter $z$ that yields the guarantee of Theorem \[th:nestimate\] for ${\widehat}h_z$, when using the estimates ${\widehat}{{\mathscr D}}_k = \frac{{\widehat}{{\mathscr Q}}(k | x) {{\mathscr D}}(x)}{{\widehat}{{\mathscr Q}}(k)}$. As shown by @hoffman2018algorithms, the parameter $z$ is the one for which ${\widehat}h_z$ admits the same loss for all source domains, that is ${\mathcal{L}}({\widehat}{{\mathscr D}}_k, {\widehat}h_z) = {\mathcal{L}}({\widehat}{{\mathscr D}}_{k'}, {\widehat}h_z)$ for all $k, k' \in [p]$, where ${\widehat}{{\mathscr D}}_k$ is the joint distribution derived from ${\widehat}{{\mathscr D}}_k$: ${\widehat}{{\mathscr D}}_k(x, y) = {\widehat}{{\mathscr D}}_k(x) {{\mathscr D}}(y | x) = \frac{{\widehat}{{\mathscr Q}}(k | x) {{\mathscr D}}(x,
  y)}{{\widehat}{{\mathscr Q}}(k)}$, with ${{\mathscr D}}(x, y) = \frac{1}{p} \sum_{k = 1}^p {{\mathscr D}}_k(x, y)$. Note, ${\widehat}{{\mathscr D}}(x, y)$ is abusively denoted the same way as ${\widehat}{{\mathscr D}}(x)$ to avoid the introduction of additional notation, but the difference in arguments should suffice to help distinguish the two distributions.

Thus, using ${\widehat}g_{z'} = {\widehat}h_z$, to find $z$, and subsequently $z'$, it suffices to solve the following optimization problem in $z$: $$\begin{aligned}
\label{eq:minmax}
\min_{z \in \Delta}\max_{k \in [p]}  \quad
{\mathcal{L}}({\widehat}{{\mathscr D}}_k ,{\widehat}g_{z'})  - {\mathcal{L}}({\widehat}{{\mathscr D}}_z, {\widehat}g_{z'}),\end{aligned}$$ where $z'_k = \frac{z_k/{\widehat}{{\mathscr Q}}(k)}{\sum_{j = 1}^p z_j/{\widehat}{{\mathscr Q}}(j)}$ and ${\widehat}{{\mathscr D}}_z = \sum_{k = 1}^p z_k {\widehat}{{\mathscr D}}_k$. As in previous work, this problem can be cast as a DC-programming (difference-of-convex) problem and solved using the DC algorithm [@TaoAn1997; @TaoAn1998; @SriperumbudurLanckriet2009]. However, we need to derive a new DC-decomposition here, both for the regression and the probability model, since the objective is distinct from that of previous work. A detailed description of that DC-decomposition and its proofs, as well as other details of the algorithm are given in the full version of the paper.

Learning Guarantees {#sec:theory}
===================

In this section, we prove favorable learning guarantees for the predictor ${\widehat}g_z$ returned by <span>`DMSA`</span>, when using conditional maximum entropy to derive domain estimates ${{\mathscr Q}}(k | x)$. We first extend Theorem \[th:nestimate\] and present a general theoretical guarantee which holds for <span>`DMSA`</span> and <span>`GMSA`</span> (Section \[sec:general\]). Next, in Section \[sec:maxent\], we give a generalization bound for conditional Maxent and use that to prove learning guarantees for <span>`DMSA`</span>. We then analyze <span>`GMSA`</span> using kernel density estimation (Section \[sec:compare\]), and show that <span>`DMSA`</span> benefits from significantly more favorable learning guarantees than <span>`GMSA`</span>.

General Guarantee {#sec:general}
-----------------

Theorem \[th:nestimate\] gives a guarantee in terms of a Rényi divergence of ${{\mathscr D}}_T$ and ${\widehat}{\mathcal{D}}$, which depends on the empirical estimates. Instead, we derive a bound in terms of a Rényi divergence of ${{\mathscr D}}_T$ and ${\mathcal{D}}$ and, as with Theorem \[th:nestimate\], the Rényi divergences between the distributions ${{\mathscr D}}_k$ and their estimates ${\widehat}{{\mathscr D}}_k$.

To do so, we first prove an inequality that can be viewed as a triangle inequality result for Rényi divergences.

<span>proposition</span><span>TriangleInequalityProposition</span> \[prop:tri\_ineq\] Let ${{\mathscr P}}$, ${{\mathscr Q}}$, ${{\mathscr R}}$ be three distributions on ${{\mathscr X}}\times
{{\mathscr Y}}$. Then, for any $\gamma \in (0, 1)$ and any $\alpha > \gamma$, the following inequality holds: $$\begin{aligned}
\Big[{{\mathsf d}}_\alpha({{\mathscr P}}\parallel {{\mathscr Q}}) \Big]^{\alpha-1}
\leq \Big[{{\mathsf d}}_{\frac{\alpha}{\gamma}}({{\mathscr P}}\parallel {{\mathscr R}})
\Big]^{\alpha-\gamma}
\Big[{{\mathsf d}}_{\frac{\alpha-\gamma}{1-\gamma}}({{\mathscr R}}\parallel {{\mathscr Q}})
\Big]^{\alpha-1}.\end{aligned}$$

This result is used in combination with Theorem \[th:nestimate\] to establish the following.

<span>theorem</span><span>GuaranteeTheorem</span> \[th:guarantee\] For any $\delta > 0$, there exists $z \in \Delta$ such that the following inequality holds for any $\alpha > 1$ and arbitrary target distribution ${{\mathscr D}}_T$: $$\begin{aligned}
{\mathcal{L}}({{\mathscr D}}_T, {\widehat}g_z) 
\leq [({\widehat}{\epsilon}+ \delta) \, {\widehat}{{\mathsf d}}']^{\frac{\alpha-1}{\alpha}} 
[{{\mathsf d}}_{{2\alpha}}({{\mathscr D}}_T \parallel {\mathcal{D}})]^{\frac{2\alpha-1}{2\alpha}} M^{\frac{1}{\alpha}},\end{aligned}$$ where ${\widehat}{\epsilon}=  ({\epsilon}{\widehat}{{\mathsf d}})^{\frac{\alpha - 1}{\alpha}}
M^{\frac{1}{\alpha }}$, ${\widehat}{{\mathsf d}}= \max_{k\in[p]} 
{{\mathsf d}}_\alpha({\widehat}{{\mathscr D}}_k \parallel {{\mathscr D}}_k)$, and ${\widehat}{{\mathsf d}}' = \max_{k\in[p]} {{\mathsf d}}_{{2\alpha-1}}
({{\mathscr D}}_{k} \parallel {\widehat}{{\mathscr D}}_{k})$, with ${\widehat}{{\mathscr D}}_k = \frac{{\widehat}{{\mathscr Q}}(k | x) {{\mathscr D}}(x)}{{\widehat}{{\mathscr Q}}(k)}$.

The theorem holds similarly for <span>`GMSA`</span> with ${\widehat}{{\mathscr D}}_k$ a direct estimate of ${{\mathscr D}}_k$. This provides a strong performance guarantee for <span>`GMSA`</span> or <span>`DMSA`</span> when the target distribution ${{\mathscr D}}_T$ is close to the family of mixtures of the source distributions ${{\mathscr D}}_k$, and when ${\widehat}{{\mathscr D}}_k$ is a good estimate of ${{\mathscr D}}_k$.

Conditional Maxent {#sec:maxent}
------------------

The distribution ${{\mathscr D}}= \frac{1}{p} \sum_{k = 1}^p {{\mathscr D}}_k$ over ${{\mathscr X}}\times {{\mathscr Y}}$ naturally induces the distribution ${{\mathscr Q}}$ over ${{\mathscr X}}\times [p]$ defined for all $(x, k)$ by ${{\mathscr Q}}(x, k) = \frac{1}{p} D_k(x)$. Let $S = ((x_1, k_1), \ldots, (x_m, k_m))$ be a sample of $m$ labeled points drawn i.i.d. from ${{\mathscr Q}}$.

Let $\Phi\colon {{\mathscr X}}\times [p] \to \Rset^N$ be a feature mapping with bounded norm, $\| \Phi \| \leq r$, for some $r > 0$. Then, the optimization problem defining the solution of conditional Maxent (or multinomial logistic regression) with the feature mapping $\Phi$ is given by $$\label{eq:LogisticRegression}
\min_{w \in \Rset^N} \mu \| w \|^2 
- \frac{1}{m} \sum_{i = 1}^m \log {\mspace{1mu} {\mathsf p}}_w [k_i |x_i],$$ where ${\mspace{1mu} {\mathsf p}}_w$ is defined by ${\mspace{1mu} {\mathsf p}}_w[k | x] = \frac{1}{Z(x)} \exp(w \cdot \Phi(x, k))$, with $Z(x) = \sum_{k \in [p]} \exp(w \cdot \Phi(x, k))$, and where $\mu \geq 0$ is a regularization parameter. Then, conditional Maxent benefits from the following theoretical guarantee.

<span>theorem</span><span>LogisticRegressionTheorem</span> \[th:LogisticRegression\] Let ${\widehat}w$ be the solution of problem and $w^*$ the population solution of the conditional Maxent optimization problem: $$\begin{aligned}
  w^* = \operatorname*{\rm argmin}_{w\in\Rset^N} \, \mu \lVert w \rVert^2 
  - \operatorname*{\mathbb{E}}_{(x, k) \sim {{\mathscr Q}}} \bracket[\big]{\log {\mspace{1mu} {\mathsf p}}_w [k | x]}.\end{aligned}$$ Then, for any $\delta > 0$, with probability at least $1 - \delta$, for any $(x, k) \in {{\mathscr X}}\times [p]$, the following inequality holds: $$\abs[\Big]{ \log {\mspace{1mu} {\mathsf p}}_{{\widehat}w}[k | x] - \log {\mspace{1mu} {\mathsf p}}_{w^*}[k | x] }
\leq \frac{2\sqrt{2} \mspace{1mu} r^2}{\mu\sqrt{m}} 
\bracket*{1 + \sqrt{\log (1/\delta)}}.$$

The theorem shows that the pointwise log-loss of the conditional Maxent solution ${\mspace{1mu} {\mathsf p}}_{{\widehat}w}$ is close to that of the best-in-class ${\mspace{1mu} {\mathsf p}}_{w^*}$ modulo a term in $O(1/\sqrt{m})$ that does not depend on the dimension of the feature space.

Comparison of the Guarantees for <span>`DMSA`</span> and <span>`GMSA`</span> {#sec:compare}
----------------------------------------------------------------------------

We now use Theorem \[th:guarantee\] and the bound of Theorem \[th:LogisticRegression\] to give a theoretical guarantee for <span>`DMSA`</span> used with conditional Maxent. We show that it is more favorable than a guarantee for <span>`GMSA`</span> using kernel density estimation.

\[<span>`DMSA`</span>\]<span>theorem</span><span>GZTheorem</span> \[th:gz\] There exists $z \in \Delta$ such that for any $\delta > 0$, with probability at least $1 - \delta$ the following inequality holds <span>`DMSA`</span> used with conditional Maxent, for an arbitrary target mixture ${{\mathscr D}}_T$: $$\begin{aligned}
{\mathcal{L}}({{\mathscr D}}_T, {\widehat}g_z)
& \leq {\epsilon}\, p \, e^{\frac{6\sqrt{2}r^2}{\mu\sqrt{m}} 
\bracket*{ 1 + \sqrt{\log (1/\delta)} }} 
\, {{\mathsf d}}^* \, {{\mathsf d}}'^*,\\[.2cm]
\text{with} \quad {{\mathsf d}}^* & = \sup_{x \in {{\mathscr X}}} {{\mathsf d}}_\infty
\left({{\mathscr Q}}^*[\cdot | x] \parallel {{\mathscr Q}}(\cdot | x) \right),\\
{{\mathsf d}}'^* & = \sup_{x \in {{\mathscr X}}} {{\mathsf d}}^2_\infty
\left( {{\mathscr Q}}(\cdot | x) \parallel {{\mathscr Q}}^*[\cdot | x] \right),\end{aligned}$$ where ${{\mathscr Q}}^*(\cdot | x) = {\mspace{1mu} {\mathsf p}}_{w^*}[\cdot | x]$ is the population solution of conditional Maxent problem (statement of Theorem \[th:LogisticRegression\]).

The theorem shows that the expected error of <span>`DMSA`</span> with conditional Maxent is close to ${\epsilon}$ modulo a factor that varies as $e^{1/\sqrt{m}}$, where $m$ is the size of the total unlabeled sample received from all $p$ sources, and factors ${{\mathscr Q}}^*$ and ${{\mathscr Q}}'^*$ that measure how closely conditional Maxent can approximate the true conditional probabilities with infinite samples.

Next, we prove learning guarantees for <span>`GMSA`</span> with densities estimated via kernel density estimation (KDE). We assume that the same i.i.d.sample $S = ((x_1, k_1), \ldots, (x_m, k_m))$ as with conditional Maxent is used. Here, the points labeled with $k$ are used for estimating ${{\mathscr D}}_k$ via KDE. Since the sample is drawn from ${{\mathscr Q}}$ with ${{\mathscr Q}}(x, k) = \frac{1}{p} {{\mathscr D}}_k$, the number of samples points $m_k$ labeled with $k$ is very close to $\frac{m}{p}$. ${\widehat}{{\mathscr D}}_k$ is learned from $m_k$ samples, via KDE with a normalized kernel function $K_\sigma(\cdot, \cdot)$ that satisfies $\int_{x\in{{\mathscr X}}} K_\sigma(x, x') \, dx = 1$ for all $x' \in {{\mathscr X}}$.

\[`GMSA`\]<span>theorem</span><span>SimpleEstimateHZTheorem</span> \[th:simple\_estimate\_hz\] There exists $z \in \Delta$ such that, for any $\delta > 0$, with probability at least $1 - \delta$ the following inequality holds for <span>`GMSA`</span> used KDE, for an arbitrary target mixture ${{\mathscr D}}_T$: $$\begin{aligned}
{\mathcal{L}}({{\mathscr D}}_T, {\widehat}h_z) \leq
{\epsilon}^{\frac{1}{4}} M^{\frac{3}{4}}
e^{\frac{6 \kappa}{\sqrt{2(m/p)}} \sqrt{\log p + \log (1/\delta)}}
{{\mathsf d}}^*
{{\mathsf d}}'^*,\end{aligned}$$ with $\kappa = \max_{x, x', x'' \in {{\mathscr X}}} 
\frac{K_\sigma(x, x')}{K_\sigma(x, x'')}$, and $$\begin{aligned}
{{\mathsf d}}^* & = \max_{k \in [p]} \operatorname*{\mathbb{E}}_{x \sim {{\mathscr D}}_k} [
{{\mathsf d}}_{+\infty}\big(K_\sigma(\cdot, x) \parallel {{\mathscr D}}_k\big) ], \\
{{\mathsf d}}'^* & = \max_{k \in [p]} \operatorname*{\mathbb{E}}_{x \sim {{\mathscr D}}_k} [
{{\mathsf d}}_{+\infty}\big({{\mathscr D}}_k \parallel K_\sigma(\cdot, x) \big)].\end{aligned}$$

In comparison with the guarantee for <span>`DMSA`</span>, the bound for <span>`GMSA`</span>admits a worse dependency on ${\epsilon}$. Furthermore, while the dependency of the learning bound of <span>`DMSA`</span> on the sample size is of the form $O(e^{1/\sqrt{m}})$ and thus decreases as a function of the full sample size $m$, that of <span>`GMSA`</span> is of the form $O(e^{1/\sqrt{m/p}})$ and only decreases as a function of the per-domain sample size. This further reflects the benefit of our discriminative solution since the estimation of the conditional probabilities is based on conditional Maxent trained on the full sample. Finally, the bound of <span>`GMSA`</span> depends on $\kappa$, a ratio that can be unbounded for Gaussian kernels commonly used for KDE.

The generalization guarantees for <span>`DMSA`</span> depends on two critical terms that measure the divergence between the population solution of conditional Maxent and the true domain classifier ${{\mathscr Q}}(\cdot | x)$: $$\begin{aligned}
{{\mathsf d}}_{+\infty} \big({{\mathscr Q}}^*(\cdot | x) \parallel {{\mathscr Q}}(\cdot | x) \big) 
\quad \text{and} \quad
{{\mathsf d}}_{+\infty} \big({{\mathscr Q}}(\cdot | x) \parallel {{\mathscr Q}}^*(\cdot | x)\big).\end{aligned}$$ When the feature mapping for conditional Maxent is sufficiently rich, for example when it is the reproducing kernel Hilbert space (RKHS) associated to a Gaussian kernel, one can expect the two divergences to be close to one. The generalization guarantees for <span>`GMSA`</span>  also depend on two divergence terms: $$\begin{aligned}
{{\mathsf d}}_{+\infty} \big(K_\sigma(\cdot, x)
\parallel {{\mathscr D}}_k\big)
\quad \text{and} \quad
{{\mathsf d}}_{+\infty}\big({{\mathscr D}}_k \parallel K_\sigma(\cdot, x)\big).\end{aligned}$$ Compared to learning a domain classifier ${\widehat}{{\mathscr Q}}(\cdot | x)$, it is more difficult to chose a good density kernel $K_\sigma(\cdot, \cdot)$ to ensure that the divergence between marginal distributions is small, which shows another benefit of <span>`DMSA`</span>.

The next section shows that, in addition to these theoretical advantages, <span>`DMSA`</span> also benefits from more favorable empirical results.

\[t\]

.0in \[table:sa\] -.15in

Experiments {#sec:experiments}
===========

We evaluated our <span>`DMSA`</span> technique on the same datasets as those used in [@hoffman2018algorithms], as well as with the UCI adult dataset. Since @hoffman2018algorithms has shown that <span>`GMSA`</span> empirically outperforms various alternative MSA solutions, in this section, we mainly focus on demonstrating improvements over <span>`GMSA`</span> under the same experimental setups.

**Sentiment analysis.** To evaluate the <span>`DMSA`</span> solution under the regression model, we used the sentiment analysis dataset [@blitzer_acl07], which consists of product review text and rating labels taken from four domains: `books` (B), `dvd` (D), ` electronics` (E), and $\texttt{\small kitchen}$ (K), with $2\mathord,000$ samples for each domain. We adopted the same training procedure and hyper-parameters as those used by @hoffman2018algorithms to obtain base predictors: first define a vocabulary of $2\mathord,500$ words that occur at least twice in each of the four domains, then use this vocabulary to define word-count feature vectors for every review text, and finally train base predictors for each domain using support vector regression. We use the same word-count features to train the domain classifier via logistic regression. We randomly split the $2\mathord,000$ samples per domain into $1\mathord,600$ train and $400$ test samples for each domain, and learn the base predictors, domain classifier, density estimations, and parameter $z$ for both MSA solutions on all available training samples. We repeated the process 10 times, and report the mean and standard deviation of the mean squared error on various target test mixtures in Table \[table:sa\].

We compared our technique, <span>`DMSA`</span>, against each source predictor, $h_k$, the uniform combination of the source predictors (` unif`), $\frac{1}{p}\sum_{k = 1}^p h_k$, and <span>`GMSA`</span>with kernel density estimation. Each column in Table \[table:sa\] corresponds to a different target test mixture, as indicated by the column name: four single domains, and uniform mixtures of two, three, and four domains, respectively. Our distribution-weighted method <span>`DMSA`</span> outperforms all baseline predictors across almost all test domains. <span>Observe that, even when the target is a single source domain, such as `K`, `B`, `E`, our method can still outperform the predictor which is trained and tested on the same domain, showing the benefits of ensembles.</span> Moreover, <span>`DMSA`</span> improves upon ` GMSA` by a wide margin on all test mixtures, which demonstrates the advantage of using a domain classifier over estimated densities in the distribution-weighted combination.

**Recognition tasks with the cross-entropy loss.** To evaluate the <span>`DMSA`</span> solution under the probability model, we considered a digit recognition task consists of three datasets: Google Street View House Numbers (SVHN), MNIST, and USPS. For each individual domain, we trained a convolutional neural network (CNN) with the same setup as in @hoffman2018algorithms, and used the output from the softmax score layer as our base predictors $h_k$. Furthermore, for every input image, we extracted the last layer before softmax from each of the base networks and concatenated them to obtain the feature vector for training the domain classifier. We used the full training sets per domain to train the source model, and used $6\mathord,000$ samples per domain to learn the domain classifier. Finally, for our DC-programming algorithm, we used a $1\mathord,000$ image-label pairs from each domain, thus a total of $3\mathord,000$ labeled pairs to learn the parameter $z$.

We compared our method <span>`DMSA`</span> against each source predictor ($h_k$), the uniform combination, <span>`unif`</span>, a network jointly trained on all source data combined, <span>`joint`</span>, and <span>`GMSA`</span> with kernel density estimation. Since the training and testing datasets are fixed, we simply report the numbers from the original <span>`GMSA`</span> paper. We evaluated these baselines on each of the three test datasets, on combinations of two test datasets, and on all test datasets combined. The results are reported in Table \[table:digits\]. Once again, <span>`DMSA`</span> outperforms all baselines on all test mixtures, and when the target is a single test domain, <span>`DMSA`</span> admits a comparable performance to the predictor that is trained and tested on the same domain. And, as in the sentiment analysis experiments, <span>`DMSA`</span> outperforms <span>`GMSA`</span> by a wide margin on all test domains.

![Average test accuracy of <span>`GMSA`</span> (blue) and <span>`DMSA`</span> (orange) on the digits dataset as a function of the number of samples used in domain adaptation. <span data-label="fig:digits_num_samples"></span>](digits_num_samples.png "fig:") -.2in

To illustrate the efficiency of <span>`DMSA`</span> we further evaluated <span>`DMSA`</span>and <span>`GMSA`</span> on the digits dataset when only a small amount of data is available for domain adaptation. We varied $m$, the number of samples per domain and evaluated both <span>`DMSA`</span> and <span>`GMSA`</span>, see Figure \[fig:digits\_num\_samples\]. As expected, <span>`DMSA`</span> consistently outperforms <span>`GMSA`</span>, thus matching our theoretical analysis that <span>`DMSA`</span> can succeed with fewer samples.

<span>l cccccccg</span> &\
& `svhn`& `mnist` & `usps` & `mu` & `su` & `sm` & `smu` & mean\
CNN-`s` & **<span>92.3</span> & <span>66.9</span> & <span>65.6</span> & <span>66.7</span> & <span>90.4</span> & <span>85.2</span> & <span>84.2</span> & <span>78.8</span>\
CNN-`m` & <span>15.7</span> & **<span>99.2</span> & <span>79.7</span> & <span>96.0</span> & <span>20.3</span> & <span>38.9</span> & <span>41.0</span> & <span>55.8</span>\
CNN-`u` & <span>16.7</span> & <span>62.3</span> & **<span>96.6</span> & <span>68.1</span> & <span>22.5</span> & <span>29.4</span> & <span>32.9</span> & <span>46.9</span>\
CNN-<span>`unif`</span>& <span>75.7</span> & <span>91.3</span> & <span>92.2</span> & <span>91.4</span> & <span>76.9</span> & <span>80.0</span> & <span>80.7</span> & <span>84.0</span>\
CNN-<span>`joint`</span>& <span>90.9</span> & <span>99.1</span> & <span>96.0</span> & <span>98.6</span> & <span>91.3</span> & <span>93.2</span> & <span>93.3</span> & <span>94.6</span>\
<span>`GMSA`</span>& <span>91.4</span> & <span>98.8</span> & <span>95.6</span> & <span>98.3</span> & <span>91.7</span> & <span>93.5</span> & <span>93.6</span> & <span>94.7</span>\
<span>`DMSA`</span> (ours) & <span>92.3</span> & <span>99.2</span> & <span>96.6</span> & **<span>98.8</span> & **<span>92.6</span> & **<span>94.2</span> & **<span>94.3</span> & **<span>95.4</span>\
****************

\[table:digits\]

**Adult dataset**. We also experimented with the UCI adult dataset [@blake1998uci]. It contains $32,561$ training samples with numerical and categorical features, each representing a person. The task consists of predicting if the person's income exceeds $50,000$ dollars. Following [@mohri2019agnostic], we split the dataset into two domains, the doctorate, `Doc`, domain and non-doctorate, `NDoc`, domain and used categorical features for training linear classification models. We froze these models and experimented with domain adaptation. Here, we repeatedly sampled $400$ training samples from each domain for training, keeping the test set fixed.

The results are in Table \[tab:adult\]. <span>`DMSA`</span> achieves higher accuracy compared to <span>`GMSA`</span>  on the `NDoc` domain and also in the average of two domains. The difference in performance is not statistically significant for the `Doc` domain as it has very few test samples.

<span>l ccg </span> Test data & `Doc` & `NDoc` & `Doc-NDoc`\
<span>`GMSA`</span>  &70.2 $\pm$ 1.2 &76.4 $\pm$ 1.6 & 73.3 $\pm$ 0.8\
<span>`DMSA`</span>  &70.0 $\pm$ 0.8 &**<span>80.5 $\pm$ 0.5</span> & **<span>75.3 $\pm$ 0.4</span>\
****

\[tab:adult\]

We finally conducted simulations on a small synthetic dataset to illustrate the difference between <span>`GMSA`</span>and <span>`DMSA`</span>. We used the `sklearn` toolkit for these experiments. Let ${{\mathscr D}}_1$ and ${{\mathscr D}}_2$ be Gaussian mixtures in one dimensions as follows: ${{\mathscr D}}_1 = 0.9 \cdot N(-20, 8) + 0.1  \cdot N(0, 0.1)$ and ${{\mathscr D}}_2 = 0.75  \cdot N(3, 0.1) + 0.25 \cdot N(5, 0.1) + 0.05  \cdot N(0, 0.1)$, see Figure \[fig:illustration\]. The two domains are similar around $0$ but are disjoint otherwise. Let the labeling function $f(x) = -1 \text{ if } x \in [-0.5, 0.5] \cup [3.5, \infty)$. The example is designed such that if their estimates are good, then both <span>`GMSA`</span> and <span>`DMSA`</span> would achieve close to $100\%$ accuracy. We first sampled $1000$ examples and trained a linear separator $h_k$ for each domain $k$. For <span>`GMSA`</span>, we trained kernel density estimators and chose the bandwidth based on a five-fold cross-validation. For <span>`DMSA`</span>, we trained a conditional Maxent threshold classifier. We first illustrate the kernel density estimate using $1000$ samples in Figure \[fig:illustration\]. For $x \in [-0.5, 0.5]$, ${{\mathscr D}}_1(x) > {{\mathscr D}}_2(x)$, but the kernel density estimates satisfy ${\widehat}{{\mathscr D}}_2(x) \geq {\widehat}{{\mathscr D}}_1(x)$, which shows the limitations of kernel density estimation with a single bandwidth. On the other hand, <span>`DMSA`</span> selected a threshold around $0.3$ for distinguishing between ${{\mathscr D}}_1$ and ${{\mathscr D}}_2$ and achieves accuracy around $100\%$. We varied the number of examples available for domain adaptation and compared <span>`GMSA`</span> and <span>`DMSA`</span>. For simplicity we found the best $z$ using exhaustive search for both <span>`GMSA`</span> and <span>`DMSA`</span>. The results show that <span>`DMSA`</span> consistently outperforms <span>`GMSA`</span> on both the domains and hence on all convex combinations, see Figure \[fig:artificial\]. The results also show that <span>`DMSA`</span> converges quickly in accordance with our theory.

![Left: Illustration of the true densities and kernel density estimates for <span>`GMSA`</span> for domains ${{\mathscr D}}_1$ and ${{\mathscr D}}_2$ with $1000$ samples. The labeling function $f(x) = -1$ in the green regions and $1$ otherwise. Right: Same estimates zoomed in at $x=0$. <span data-label="fig:illustration"></span>](density_estimate.pdf "fig:") ![Left: Illustration of the true densities and kernel density estimates for <span>`GMSA`</span> for domains ${{\mathscr D}}_1$ and ${{\mathscr D}}_2$ with $1000$ samples. The labeling function $f(x) = -1$ in the green regions and $1$ otherwise. Right: Same estimates zoomed in at $x=0$. <span data-label="fig:illustration"></span>](density_estimate_zoom.pdf "fig:") -.2in

-.1in

![Comparison of <span>`GMSA`</span> and <span>`DMSA`</span> on the synthetic dataset. <span>`DMSA`</span> performs better than <span>`GMSA`</span> on both the domains and hence on any convex combination. The experiments are averaged over $10$ runs. The error bars show one standard deviation.<span data-label="fig:artificial"></span>](D1_synthetic.png "fig:") ![Comparison of <span>`GMSA`</span> and <span>`DMSA`</span> on the synthetic dataset. <span>`DMSA`</span> performs better than <span>`GMSA`</span> on both the domains and hence on any convex combination. The experiments are averaged over $10$ runs. The error bars show one standard deviation.<span data-label="fig:artificial"></span>](D2_synthetic.png "fig:") -0.2in

-.1in

Conclusion
==========

We presented a new algorithm for the important problem of multiple-source adaptation, which commonly arises in applications. Our algorithm was shown to benefit from favorable theoretical guarantees and a superior empirical performance, compared to previous work. Moreover, our algorithm is practical: it is straightforward to train a multi-class classifier in the setting we described and our DC-programming solution is very efficient.

Providing a robust solution for the problem is particularly important for under-represented groups, whose data is not necessarily well-represented in the classifiers to be combined and trained on source data. Our solution demonstrates improved performance even in the cases where the target distribution is not included in the source distributions. We hope that continued efforts in this area will result in more equitable treatment of under-represented groups.

{'source': 'arXiv_out/2008'}