Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions
24. července 2023
Řečníci
Chenyi Zhang
Řečník · 0 sledujících
Tongyang Li
Řečník · 0 sledujících
O prezentaci
Quantum computing is an emerging technology that has been rapidly advancing in the past decades. In this paper, we conduct a systematic study of quantum lower bounds on finding ϵ-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to p-th order derivatives; or 2) having access to stochastic gradients.The classical query lower bounds are Ω(ϵ^-1+p/p) regarding the first setting and Ω(ϵ^-4) regarding the second setting (or Ω(ϵ^-3) if the stochastic gradient function is mean-squared smooth). In this paper, we extend all these classical lower bounds to the quantum setting. They match the classical algorithmic results respectively, demonstrating that there is no quantum speedup for finding ϵ-stationary points of nonconvex functions with p-th order derivative inputs or stochastic gradient inputs, whether with or without the mean-squared smoothness assumption. Technically, we prove our quantum lower bounds by showing that the sequential nature of classical hard instances in all these settings also applies to quantum queries, preventing any quantum speedup other than revealing information of the stationary points sequentially.Quantum computing is an emerging technology that has been rapidly advancing in the past decades. In this paper, we conduct a systematic study of quantum lower bounds on finding ϵ-approximate stationary points of nonconvex functions, and we consider the following two important settings: 1) having access to p-th order derivatives; or 2) having access to stochastic gradients.The classical query lower bounds are Ω(ϵ^-1+p/p) regarding the first setting and Ω(ϵ^-4) regarding the second setting (or Ω(ϵ…
Baví vás formát? Nechte SlidesLive zachytit svou akci!
Profesionální natáčení a streamování po celém světě.
Sdílení
Doporučená videa
Prezentace na podobné téma, kategorii nebo přednášejícího
Formal Control Synthesis for Stochastic Neural Network Dynamic Models
Zhlédnout později
Steven Adams, …
Bidirectional Adaptation for Robust Semi-Supervised Learning with Inconsistent Data Distributions
Zhlédnout později
Lin-Han Jia, …
Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methods
Zhlédnout později
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons
Zhlédnout později
Banghua Zhu, …
Sequential Strategic Screening
Zhlédnout později
Lee Cohen, …
Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization
Zhlédnout později
Quanqi Hu, …