Speaker: Yancheng Yuan
Zoom Meeting ID: 881 0309 9426
Password:540575
Abstract:
This talk introduces HOT, an efficient Halpern accelerating algorithm for solving the optimal transport (OT) problems with finite supports in R^n, where the involved linear systems in the HOT algorithm can be efficiently solved in linear time complexity. Consequently, we can obtain an ε-approximate solution (in terms of the Karush-Kuhn-Tucker residual) to the OT problem with M supports in O(M^2/ε) flops, which improves the best-known computational complexity for the OT problem. For a class of important OT problems where the supports are in R^2 with ground distances calculated by the squared Euclidean norm, we prove that HOT can obtain an ε-approximate solution (in terms of the Karush-Kuhn-Tucker residual) to the OT problem with M supports in O(M^1.5/ε) flops by solving an equivalent reduced model of the discrete OT problem. We further propose an efficient procedure to recover an optimal transport plan for the original OT problem based on a solution to the reduced model, thereby overcoming the limitations of the reduced OT model in applications that require the transport plan. We implement the HOT algorithm in PyTorch and numerical results show the superior performance of the HOT algorithm compared to existing state-of the-art algorithms for solving the OT problems. This talk is based on the joint works with Guojun Zhang, Zhexuan Gu, and Defeng Sun from The Hong Kong Polytechnic University.
Introduction to the speaker:
Yancheng Yuan is an Assistant Professor at the Department of Applied Mathematics, The Hong Kong Polytechnic University. His research focuses on continuous optimization, the mathematical foundation of data science, and data driven applications. His research has been published in prestigious academic journals and conferences, including SIAM Journal on Optimization, Mathematical Programming Computation, Journal of Machine Learning Research, IEEE Transactions on Pattern Analysis and Machine Intelligence, NeurIPS, ICML, ICLR, ACM WWW, ACM SIGIR. His papers have been selected in Best Paper Award Finalist of ACM WWW 2021 and ACM SIGIR 2024.
English 
简体中文