Unsupervised domain adaptation is the problem setting where data generating distributions in the source and target domains are different and labels in the target domain are unavailable. An important question in unsupervised domain adaptation is how to measure the difference between the source and target domains. Existing discrepancy measures for unsupervised domain adaptation either require high computation costs or have no theoretical guarantee. To mitigate these problems, this paper proposes a novel discrepancy measure called source-guided discrepancy (S-disc), which exploits labels in the source domain unlike the existing ones. As a consequence, S-disc can be computed efficiently with a finitesample convergence guarantee. In addition, it is shown that S-disc can provide a tighter generalization error bound than the one based on an existing discrepancy measure. Finally, experimental results demonstrate the advantages of S-disc over the existing discrepancy measures.
Pairwise similarities and dissimilarities between data points are often obtained more easily than full labels of data in real-world classification problems. To make use of such pairwise information, an empirical risk minimization approach has been proposed, where an unbiased estimator of the classification risk is computed from only pairwise similarities and unlabeled data. However, this approach has not yet been able to handle pairwise dissimilarities. Semisupervised clustering methods can incorporate both similarities and dissimilarities into their framework; however, they typically require strong geometrical assumptions on the data distribution such as the manifold assumption, which may cause severe performance deterioration. In this letter, we derive an unbiased estimator of the classification risk based on all of similarities and dissimilarities and unlabeled data. We theoretically establish an estimation error bound and experimentally demonstrate the practical usefulness of our empirical risk minimization method.
Optimal transport is a mathematical tool that has been a widely used to measure the distance between two probability distributions. To mitigate the cubic computational complexity of the vanilla formulation of the optimal transport problem, regularized optimal transport has received attention in recent years, which is a convex program to minimize the linear transport cost with an added convex regularizer. Sinkhorn optimal transport is the most prominent one regularized with negative Shannon entropy, leading to densely supported solutions, which are often undesirable in light of the interpretability of transport plans. In this paper, we report that a deformed entropy designed by q-algebra, a popular generalization of the standard algebra studied in Tsallis statistical mechanics, makes optimal transport solutions supported sparsely. This entropy with a deformation parameter q interpolates the negative Shannon entropy () and the squared 2-norm (), and the solution becomes more sparse as q tends to zero. Our theoretical analysis reveals that a larger q leads to a faster convergence when optimized with the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm. In summary, the deformation induces a trade-off between the sparsity and convergence speed.
Causal inference plays a critical role in decision-making processes about whether to provide treatment to individuals across various domains, such as education, medicine, and e-commerce. One of the fundamental tasks in causal inference is to estimate the individual treatment effect (ITE), which represents the effect of a treatment on an individual outcome. Recently, many studies have focused on estimating ITE from graph data taking into account not only the covariates of units but also connections among them. In such a case, the outcome of a unit can be affected by not only its own covariates and treatment but also those of its neighbors, which is referred to as interference. Existing methods have utilized graph neural networks (GNNs) to capture interference and achieved improvements in estimating ITE on graph data. However, these methods are not computationally efficient and therefore cannot be applied to large graph data. To overcome this problem, we propose a novel method that reduces redundant computation in interference modeling while maintaining the prediction performance of ITE estimation. Our key idea is to model the propagation of interference by aggregating the information of neighbors before training and preserve the aggregated results for training our networks. We conduct intensive experiments on graph data consisting of up to a hundred thousand units and millions of edges. We show that the proposed method achieves superior or comparable performance to the existing GNN-based methods in ITE estimation, while the proposed method can be executed much faster than GNN-based methods.