科学研究
报告题目:

Importance Sparsification for Sinkhorn Algorithm in Optimal transport problems

报告人:

孟澄 助理教授(中国人民大学)

报告时间:

报告地点:

腾讯会议 ID:882 987 622

报告摘要:

Sinkhorn algorithm has been used pervasively to approximate the solution to optimal transport (OT) and unbalanced optimal transport (UOT) problems. However, its application in practice is limited due to its high computational complexity. To alleviate the computational burden, we propose a novel importance sparsification method, called Spar-Sink, to approximate regularized OT and UOT distances efficiently. Specifically, we leverage natural upper bounds for unknown optimal transport plans to construct effective sampling probabilities, and construct a sparse kernel matrix to accelerate Sinkhorn iterations, reducing the cost from O(n^2) to around O(n) for a sample of size n. Theoretically, we show the proposed estimators for the regularized OT and UOT distances are consistent under mild regularity conditions. Experiments on various synthetic datasets demonstrate Spar-Sink leads to smaller estimation errors compared with mainstream competitors.