論文の概要: Quantum Lower Bounds for Finding Stationary Points of Nonconvex
Functions
- arxiv url: http://arxiv.org/abs/2212.03906v2
- Date: Sun, 4 Jun 2023 18:33:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 03:57:07.872113
- 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点を求める量子スピードアップがないことを示した。
技術的には、これらのすべての設定における古典的ハードインスタンスのシーケンシャルな性質が量子クエリにも適用されることを示し、定常点の情報の逐次的な開示以外の量子スピードアップを防止している。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、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 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) - 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) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
論文 参考訳（メタデータ） (2020-10-05T06:32:47Z) - 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) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。