A Homotopy Algorithm for Optimal Transport
The optimal transport problem has many applications in machine learning, physics, biology, economics, etc. Although its goal is very clear and mathematically well-defined, finding its optimal solution can be challenging for large datasets in high-dimensional space. Here, we propose a homotopy algorithm that first transforms the problem into an easy form, by changing the target distribution. It then transforms the problem back to the original form through a series of iterations, tracing a path of solutions until it finds the optimal solution for the original problem. We define the homotopy path as a subspace rotation based on the orthogonal Procrustes problem, and then we discretize the homotopy path using eigenvalue decomposition of the rotation matrix. Our goal is to provide an algorithm with complexity bound $\mathcal{O}(n^2 \log(n))$, faster than the existing methods in the literature.
Code (0)
등록된 구현이 없습니다.
Tasks
FormMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Homotopy Continuation Approaches for Robust SV Classification and Regression
In support vector machine (SVM) applications with unreliable data that contains a portion of outliers, non-robustness of SVMs often causes considerable performance deterioration. Although many approaches for improving th…
ClassificationGeneral ClassificationModel Selectionregression+1Homotopy-Guided Self-Supervised Learning of Parametric Solutions for AC Optimal Power Flow
Learning to optimize (L2O) parametric approximations of AC optimal power flow (AC-OPF) solutions offers the potential for fast, reusable decision-making in real-time power system operations. However, the inherent nonconv…
Self-Supervised LearningHomotopy Analysis for Tensor PCA
Developing efficient and guaranteed nonconvex algorithms has been an important challenge in modern machine learning. Algorithms with good empirical performance such as stochastic gradient descent often lack theoretical g…
global-optimizationFast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
We study the policy evaluation problem in multi-agent reinforcement learning where a group of agents, with jointly observed states and private local actions and rewards, collaborate to learn the value function of a given…
Multi-agent Reinforcement LearningReinforcement LearningStochastic OptimizationFast Screening Rules for Optimal Design via Quadratic Lasso Reformulation
The problems of Lasso regression and optimal design of experiments share a critical property: their optimal solutions are typically \emph{sparse}, i.e., only a small fraction of the optimal variables are non-zero. Theref…
Experimental Designregression