論文の概要: No quantum speedup over gradient descent for non-smooth convex
optimization
- arxiv url: http://arxiv.org/abs/2010.01801v1
- Date: Mon, 5 Oct 2020 06:32:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-29 22:42:52.657775
- Title: No quantum speedup over gradient descent for non-smooth convex
optimization
- Title（参考訳）: 非滑らか凸最適化のための勾配降下による量子スピードアップ
- Authors: Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
- Abstract要約: ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
- 参考スコア（独自算出の注目度）: 22.16973542453584
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the first-order convex optimization problem, where we have black-box
access to a (not necessarily smooth) function $f:\mathbb{R}^n \to \mathbb{R}$
and its (sub)gradient. Our goal is to find an $\epsilon$-approximate minimum of
$f$ starting from a point that is distance at most $R$ from the true minimum.
If $f$ is $G$-Lipschitz, then the classic gradient descent algorithm solves
this problem with $O((GR/\epsilon)^{2})$ queries. Importantly, the number of
queries is independent of the dimension $n$ and gradient descent is optimal in
this regard: No deterministic or randomized algorithm can achieve better
complexity that is still independent of the dimension $n$.
In this paper we reprove the randomized lower bound of
$\Omega((GR/\epsilon)^{2})$ using a simpler argument than previous lower
bounds. We then show that although the function family used in the lower bound
is hard for randomized algorithms, it can be solved using $O(GR/\epsilon)$
quantum queries. We then show an improved lower bound against quantum
algorithms using a different set of instances and establish our main result
that in general even quantum algorithms need $\Omega((GR/\epsilon)^2)$ queries
to solve the problem. Hence there is no quantum speedup over gradient descent
for black-box first-order convex optimization without further assumptions on
the function family.
- Abstract（参考訳）: 我々は、(必ずしも滑らかではない)関数 $f:\mathbb{r}^n \to \mathbb{r}$ とその (sub)gradient へのブラックボックスアクセスがある一階凸最適化問題を研究する。
我々のゴールは、$\epsilon$-approximate minimum of $f$ を、真の最小値から少なくとも$R$の距離から始めることである。
もし$f$が$g$-lipschitzであれば、古典的な勾配降下アルゴリズムはこの問題を$o((gr/\epsilon)^{2})$クエリで解く。
重要なことに、クエリの数は次元$n$とは独立であり、勾配降下はこの点において最適である。
本稿では、以前の下界よりも単純な引数を用いて、$\Omega((GR/\epsilon)^{2})$のランダム化された下界を再現する。
次に、下限で使われる関数ファミリはランダム化アルゴリズムでは難しいが、$o(gr/\epsilon)$量子クエリを用いて解くことができることを示す。
次に、異なるインスタンスの集合を用いて量子アルゴリズムに対する改善された低境界を示し、その問題を解くのに一般に量子アルゴリズムでさえ$\Omega((GR/\epsilon)^2)$クエリが必要であることを主要な結果を確立する。
したがって、ブラックボックス一階凸最適化の勾配降下の量子スピードアップは、関数族に対するさらなる仮定なしには存在しない。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。
我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
論文 参考訳（メタデータ） (2024-02-20T06:23:36Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。