Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization

• URL: http://arxiv.org/abs/2410.02628v1
• Date: Thu, 3 Oct 2024 16:12:59 GMT
• Title: Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization
• Authors: Mikhail Persiianov, Arip Asadulaev, Nikita Andreev, Nikita Starodubcev, Dmitry Baranchuk, Anastasis Kratsios, Evgeny Burnaev, Alexander Korotin,
• Abstract summary: conditional distributions is a central problem in machine learning. We propose a new learning paradigm that integrates both paired and unpaired data. Our approach also connects intriguingly with inverse entropic optimal transport (OT)
• Score: 65.8915778873691
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning conditional distributions $\pi^*(\cdot|x)$ is a central problem in machine learning, which is typically approached via supervised methods with paired data $(x,y) \sim \pi^*$. However, acquiring paired data samples is often challenging, especially in problems such as domain translation. This necessitates the development of $\textit{semi-supervised}$ models that utilize both limited paired data and additional unpaired i.i.d. samples $x \sim \pi^*_x$ and $y \sim \pi^*_y$ from the marginal distributions. The usage of such combined data is complex and often relies on heuristic approaches. To tackle this issue, we propose a new learning paradigm that integrates both paired and unpaired data $\textbf{seamlessly}$ through the data likelihood maximization techniques. We demonstrate that our approach also connects intriguingly with inverse entropic optimal transport (OT). This finding allows us to apply recent advances in computational OT to establish a $\textbf{light}$ learning algorithm to get $\pi^*(\cdot|x)$. Furthermore, we demonstrate through empirical tests that our method effectively learns conditional distributions using paired and unpaired data simultaneously.

Related papers

• On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
  We study the problem of computing pairwise statistics, i.e., ones of the form $binomn2-1 sum_i ne j f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc.
  arXiv  Detail & Related papers  (2024-06-24T04:06:09Z)
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  We consider the problem of learning a sparse graph underlying an undirected Gaussian graphical model. We propose GraphL0BnB, a new estimator based on an $ell_0$-penalized version of the pseudolikelihood function. Our numerical experiments on real/synthetic datasets suggest that our method can solve, to near-optimality, problem instances with $p = 104$.
  arXiv  Detail & Related papers  (2023-07-18T15:49:02Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912]
  Group distributionally robust optimization (GDRO) Online learning techniques to reduce the number of samples required in each round from $m$ to $1$, keeping the same sample. A novel formulation of weighted GDRO, which allows us to derive distribution-dependent convergence rates.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  We study the problem of learning nonparametric distributions in a finite mixture. We establish tight bounds on the sample complexity for learning the component distributions in such models.
  arXiv  Detail & Related papers  (2022-03-28T23:53:48Z)
• An Improved Analysis of Gradient Tracking for Decentralized Machine Learning [34.144764431505486]
  We consider decentralized machine learning over a network where the training data is distributed across $n$ agents. The agent's common goal is to find a model that minimizes the average of all local loss functions. We improve the dependency on $p$ from $mathcalO(p-1)$ to $mathcalO(p-1)$ in the noiseless case.
  arXiv  Detail & Related papers  (2022-02-08T12:58:14Z)
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data [8.55881355051688]
  We provide the first study on the problem of DP-SCO with heavy-tailed data in the high dimensional space. We show that if the loss function is smooth and its gradient has bounded second order moment, it is possible to get a (high probability) error bound (excess population risk) of $tildeO(fraclog d(nepsilon)frac13)$ in the $epsilon$-DP model. In the second part of the paper, we study sparse learning with heavy-tailed data.
  arXiv  Detail & Related papers  (2021-07-23T11:03:21Z)
• Mediated Uncoupled Learning: Learning Functions without Direct Input-output Correspondences [80.95776331769899]
  We consider the task of predicting $Y$ from $X$ when we have no paired data of them. A naive approach is to predict $U$ from $X$ using $S_X$ and then $Y$ from $U$ using $S_Y$. We propose a new method that avoids predicting $U$ but directly learns $Y = f(X)$ by training $f(X)$ with $S_X$ to predict $h(U)$.
  arXiv  Detail & Related papers  (2021-07-16T22:13:29Z)
• Inductive Mutual Information Estimation: A Convex Maximum-Entropy Copula Approach [0.5330240017302619]
  We propose a novel estimator of the mutual information between two ordinal vectors $x$ and $y$. We prove that, so long as the constraint is feasible, this problem admits a unique solution, it is in the exponential family, and it can be learned by solving a convex optimization problem. We show that our approach may be used to mitigate mode collapse in GANs by maximizing the entropy of the copula of fake samples.
  arXiv  Detail & Related papers  (2021-02-25T21:21:40Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  We show that the average-case teaching complexity is $Theta(d)$, which is in sharp contrast to the worst-case teaching complexity of $Theta(n)$. Our insights allow us to establish a tight bound on the average-case complexity for $phi$-separable dichotomies.
  arXiv  Detail & Related papers  (2020-06-25T19:59:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.