- [SNU GSAI Seminar 초대] SGD with shuffling: optimal convergence rates and more
- 날짜2020-11-30 13:19:34
서울대학교 협동과정 인공지능전공, AI연구원, 컴퓨터공학부에서 공동 주최하는 「SNU GSAI Seminar」 개최를 아래와 같이 안내드리니, 관심 있는 분들의 많은 참여를 바랍니다.
주 제: SGD with shuffling: optimal convergence rates and more
발표자: 윤철희(Chulhee Yun) MIT 박사과정
일 시: 2020.12.3.(목) 10:00 AM - 11:00 AM
장 소: 비대면 https://snu-ac-kr.zoom.us/j/9368166137
호스트: 컴퓨터공학부 김건희 교수
Without-replacement stochastic gradient descent (SGD) is prevalent in solving finite-sum optimization problems including empirical risk minimization. However, due to nontrivial issues arising in without-replacement sampling, theoretical analyses have been largely devoted to with-replacement SGD. In this paper, we show tight convergence rates for without-replacement SGD. Specifically, depending how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shufflelyce) algorithms. First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors. Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely the convexity of individual component functions unlike existing optimal convergence results. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.
Chulhee Yun is a fifth-year Ph.D. student in the Laboratory for Information and Decision Systems, Department of Electrical Engineering and Computer Science, at Massachusetts Institute of Technology. He studies theory of optimization and machine learning, under joint supervision of Prof. Suvrit Sra and Prof. Ali Jadbabaie. Specifically, Chulhee is focusing the theoretical aspects of deep learning from optimization and expressive power points of view. Before joining MIT, he was a master’s student in Electrical Engineering at Stanford University, where he worked with Prof. John Duchi. He finished his undergraduate program in Electrical Engineering at KAIST, South Korea.