»ã±¨±êÌâ (Title)£ºSampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes (»ùÓÚ²ÉÑùµÄ´«Êä¶àÃæÌå¶à¿éÓÅ»¯ÎÊÌâµÄ²½Öè)

»ã±¨ÈË (Speaker)£ºÁõì§ ×êÑÐÔ±£¨Öйú¿ÆѧԺÊýѧÓëϵͳ¿Æѧ×êÑÐÔº£¬¹ú¶È׿ԽÇàÄê»ù½ð»ñµÃÕߣ©

»ã±¨¹¦·ò (Time)£º2024Äê5ÔÂ27ÈÕ (ÖÜÒ») 15:30

»ã±¨µØÖ· (Place)£ºÐ£±¾²¿GJ303

Ô¼ÇëÈË(Inviter)£ºÐì×Ë¡¢Ó೤¾ý

Ö÷°ì²¿ÃÅ£ºÀíѧԺÊýѧϵ

»ã±¨ÌáÒª£ºThis work focuses on multi-block optimization problems over transport polytopes, which underlie various applications including strongly correlated quantum physics and machine learning. Conventional block coordinate descent-type methods for the general multi-block problems store and operate on the matrix variables directly, resulting in formidable expenditure for large-scale settings. For another, optimal transport problems, as a special case, have attracted extensive attention and numerical techniques that waive the use of the full matrices have recently emerged. However, it remains nontrivial to apply these techniques to the multi-block, possibly nonconvex problems with theoretical guarantees. In this work, we leverage the benefits of both sides and develop novel sampling-based block coordinate descent-type methods, where each iteration solves subproblems restricted on the sampled degrees of freedom. Consequently, these methods involve only sparse matrices, which amounts to considerable complexity reductions. We explicitly characterize the sampling-induced errors and establish convergence and asymptotic properties for the proposed methods. Numerical experiments on typical strongly correlated electrons systems corroborate their superior scalability over the existing ones. Compared with the previous works, we are able to push the limit of simulations to finer meshes and higher dimensions, and offer the first visualization of optimal transport maps between electron positions in three-dimensional contexts.