No quantum speedup over gradient descent for non-smooth convex optimization

No quantum speedup over gradient descent for non-smooth convex optimization

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=_JpxJ8ufEKg


Duration: 24:11
311 views
12

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
http://itcs-conf.org/

No quantum speedup over gradient descent for non-smooth convex optimization

Ankit Garg (Microsoft Research)
Robin Kothari (Microsoft Quantum)
Praneeth Netrapalli (Microsoft Research)
Suhail Sherif (School of Technology and Computer Science, TIFR, Mumbai)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15Training (Overparametrized) Neural Networks in Near-Linear Time
2021-01-15Communication memento: Memoryless communication complexity
2021-01-15Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
2021-01-15An O(n) time algorithm for finding Hamilton cycles with high probability
2021-01-15Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
2021-01-15Sensitivity Analysis of the Maximum Matching Problem
2021-01-15On Distributed Differential Privacy and Counting Distinct Elements
2021-01-15A Generalized Matching Reconfiguration Problem
2021-01-15Agnostic learning with unknown utilities
2021-01-15Quantum versus Randomized Communication Complexity, with Efficient Players
2021-01-15No quantum speedup over gradient descent for non-smooth convex optimization
2021-01-15Sequential Defaulting in Financial Networks
2021-01-15Non-quasi-linear Agents in Quasi-linear Mechanisms
2021-01-15Online Search With a Hint
2021-01-15Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
2021-01-15Robust Quantum Entanglement at (nearly) Room Temperature
2021-01-15Pseudobinomiality of the Sticky Random Walk
2021-01-15Black-Box Uselessness: Composing Separations in Cryptography
2021-01-15Tiered Random Matching Markets: Rank is Proportional to Popularity
2021-01-15Relaxing Common Belief for Social Networks
2021-01-15Total Functions in the Polynomial Hierarchy