論文の概要: Quantum Lower Bounds for Finding Stationary Points of Nonconvex
Functions
- arxiv url: http://arxiv.org/abs/2212.03906v1
- Date: Wed, 7 Dec 2022 19:02:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 18:06:00.903092
- Title: Quantum Lower Bounds for Finding Stationary Points of Nonconvex
Functions
- Title（参考訳）: 非凸関数の定常点を求めるための量子下界
- Authors: Chenyi Zhang, Tongyang Li
- Abstract要約: 非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。
最初の設定について、Omegabig(frac-1+ppp)$。
第二設定については、おめがの()$。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
Omega()$ if 勾配関数は滑らかである。
- 参考スコア（独自算出の注目度）: 8.495749905129278
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum algorithms for optimization problems are of general interest. Despite
recent progress in classical lower bounds for nonconvex optimization under
different settings and quantum lower bounds for convex optimization, quantum
lower bounds for nonconvex optimization are still widely open. In this paper,
we conduct a systematic study of quantum query lower bounds on finding
$\epsilon$-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 is $\Omega\big(\epsilon^{-\frac{1+p}{p}}\big)$ regarding the first
setting, and $\Omega(\epsilon^{-4})$ regarding the second setting (or
$\Omega(\epsilon^{-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
$\epsilon$-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, our quantum lower bounds are
obtained 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.
- Abstract（参考訳）: 最適化問題に対する量子アルゴリズムは一般に興味深い。
異なる設定下での非凸最適化の古典的下界と凸最適化の量子的下界の最近の進歩にもかかわらず、非凸最適化の量子的下界は依然として広く開放されている。
本稿では,非凸関数の定常点である $\epsilon$-approximate を求める量子問合せ下限を体系的に研究し,次の2つの重要な設定を考察する。
1) $p$-th order デリバティブへのアクセスを有すること,又は
2)確率勾配へのアクセス。
古典的なクエリの下界は、第一設定に関して$\Omega\big(\epsilon^{-\frac{1+p}{p}}\big)$、第二設定に関して$\Omega(\epsilon^{-4})$である(あるいは、確率勾配関数が平均二乗滑らかであれば$\Omega(\epsilon^{-3})$)。
本稿では、これらの古典的な下界を量子設定に拡張する。
彼らはそれぞれ古典的なアルゴリズムの結果と一致し、平均二乗滑らか性仮定の有無にかかわらず、$p$-階微分入力または確率勾配入力を持つ非凸関数の$\epsilon$-stationary点を求める量子スピードアップがないことを示した。
技術的には、これらのすべての設定における古典的ハードインスタンスのシーケンシャルな性質が量子クエリにも適用されることを示し、定常点の情報の逐次的な開示以外の量子スピードアップを防止している。
関連論文リスト
- A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳（メタデータ） (2022-12-05T19:10:32Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。
応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
論文 参考訳（メタデータ） (2022-09-26T03:19:40Z) - Quantum Semidefinite Programming with the Hadamard Test and Approximate
Amplitude Constraints [62.72309460291971]
半定値プログラムに対して最大$N=2n$変数と$M=2n$制約を持つ変分量子アルゴリズムを導入する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
本稿では,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
論文 参考訳（メタデータ） (2022-06-01T03:40:56Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Quantum algorithms for escaping from saddle points [7.191453718557392]
本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。
我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。
また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
論文 参考訳（メタデータ） (2020-07-20T16:42:53Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。