Speaker: Tongyang Li Peking University
Time: 2021-12-17 14:30-2021-12-17 15:30
Venue: FIT 1-315 + Tencent Meeting （ID: 514-319-021）
Abstract:
The theories of optimization answer foundational questions in machine learning and lead to new algorithms for practical applications. In this talk, I will introduce two quantum algorithms that we recently developed for convex optimization and nonconvex optimization, respectively. Both achieve polynomial quantum speedup compared to the best-known classical algorithms. Our quantum algorithms are built upon two techniques: First, we replace the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the polynomial speedup in $n$ for escaping from saddle points. Second, we show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our quantum speedup.
The full version of the papers are available at https://arxiv.org/abs/1809.01731 (convex optimization) and https://arxiv.org/abs/2007.10253 (nonconvex optimization). The convex optimization paper was accepted as a contributed talk at QIP 2019, journal version Quantum, 4:221, 2020. The nonconvex optimization paper was accepted as a contributed talk at QIP 2021 (see our presentation at https://www.youtube.com/watch?v=xbHqktWa354), journal version Quantum, 5:529, 2021.
Short Bio:
Tongyang Li is currently an assistant professor at the Center on Frontiers of Computing Studies and the School of Computer Science, Peking University. Previously he was a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology. He received Master and Ph.D. degrees from the Department of Computer Science, University of Maryland in 2018 and 2020, respectively. He received Bachelor of Engineering from Institute for Interdisciplinary Information Sciences, Tsinghua University and Bachelor of Science from Department of Mathematical Sciences, Tsinghua University, both in 2015. Dr. Tongyang Li's research focuses on designing quantum algorithms for machine learning and optimization. In general, he is interested in better understanding about the power of quantum algorithms, including topics such as quantum query complexity, quantum simulation, and quantum walks. He was a recipient of the IBM Ph.D. Fellowship, the NSF QISE-NET Triplet Award, and the Lanczos Fellowship.
