Date: 3/9/2021, 12pm
Speaker: Dr. Tongyang Li, Center for Theoretical Physics, Massachusetts Institute of Technology
Topic: Quantum algorithms for escaping from saddle points
QSEC’s quantum computing subgroup will organize and host a seminar series throughout the upcoming semester. These events are free and open to the public. For any questions, contact qsec@gmu.edu.
Abstract
We initiate the study of quantum algorithms for escaping from saddle points with a provable guarantee. Given a function f: R^{n} -> R, our quantum algorithm outputs an $\epsilon$-approximate local minimum using $\tilde{O}(\log^{2} n/\epsilon^{1.75})$ queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al. with $\tilde{O}(\log^{6} n/\epsilon^{1.75})$ queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of $n$ and matches its complexity in terms of $1/\epsilon$. Our quantum algorithm is 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 in nonconvex optimization by quantum evaluation queries with the same complexity, extending the same result from convex optimization due to van Apeldoorn et al. and Chakrabarti et al. Finally, we also perform numerical experiments that support our quantum speedup.
Speaker’s Bio:
Tongyang Li is currently a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology. He received Master’sand PhD degrees from the Department of Computer Science, the University of Maryland in 2018 and 2020, respectively. He received B.E. from the Institute for Interdisciplinary Information Sciences, Tsinghua University and B.S. from the Department of Mathematical Sciences, Tsinghua University, both in 2015. He was a recipient of the IBM Ph.D. Fellowship, the NSF QISE-NET Triplet Award, and the Lanczos Fellowship. His research focuses on designing quantum algorithms for machine learning and optimization.
Meeting Information
Join Zoom Meeting ID:609 431 5466
https://gmu.zoom.us/j/6094315466