◆ 주제:Efficient Sampling and Distributed Optimization over Graphs: from MCMC to Nonlinear Markov Chains

◆  발표자: 은도영 교수(North Carolina State University 전기·전자공학부)

◆  일시: 2024년 10월 22일 화요일 16:00~17:00

◆  장소: 301동 105호

◆  사전 참가신청:https://forms.gle/JzAXoJKhDW9MdUK16

1. 발표 내용

Random walk on graph, together with Markov Chain Monte Carlo (MCMC) on a discrete state space, is a fundamental component in graph sampling via crawlers, randomized algorithms for approximate solutions, stochastic and distributed optimization, statistical inference, and machine learning tasks where evaluation of objective functions or their gradients based on full dataset with graphical constraints is practically infeasible. While MCMC has been the most popular techniques to generate/sample/estimate components in such applications for its versatility and distributed implementation, it is still fundamentally limited by the underlying topology, and most of all, being Markovian itself.

In this talk, I will present how to effectively utilize past history into the kernel design via “nonlinear” Markov chains, by making a given random walk (Markov chain) “self-repellent”. The constructed self-repellent random walk (SRRW) can be a drop-in replacement for all the MCMC applications employing random walk on graph, e.g. Metropolis-Hastings random walk, and achieve near-zero variance of (i) the samples for general inference by random walkers and (ii) the iterates of stochastic approximation (e.g., stochastic gradient descent) for distributed optimization over the graph with local information. A brief introduction to MCMC and random walk on graph will also be given. This talk is based on our recent works in NeurIPS’22, ICML’23 (outstanding paper award), and ICLR’24 (oral presentation).

2. 은도영 교수님 소개

Do Young Eun received his B.S. and M.S. degree from KAIST, Korea, in 1995 and 1997, respectively, and Ph.D. from Purdue University, West Lafayette, IN, in 2003. Since then, he has been with the Department of Electrical and Computer Engineering at North Carolina State University, Raleigh, NC, where he is currently a professor. His research interests include efficient sampling and distributed optimization for machine learning, network modeling and performance analysis, distributed and randomized algorithms for large social networks and wireless networks, epidemic modeling and analysis, graph analytics and mining techniques with network applications. He has been a member of TPC of various conferences including ACM Sigmetrics, MobiHoc, IEEE INFOCOM, ICC, Globecom. He served on the editorial board of IEEE/ACM Transactions on Networking, IEEE Transactions on Network Science and Engineering, and Computer Communications Journal, and was TPC co-chair of WASA’11. He received the National Science Foundation CAREER Award 2006, best paper awards in IEEE ICCCN 2005, IEEE IPCCC 2006, IEEE NetSciCom 2015, and the best student paper award in ACM MobiCom 2007, and the outstanding paper award in ICML 2023.

3. 사전 참가신청

사전 참가신청을 완료한 학생들에게다과 및 음료를 우선적으로 나눠드릴 예정입니다.

사전 참가신청 링크는 https://forms.gle/JzAXoJKhDW9MdUK16입니다.