論文の概要: Fast Convex Optimization with Quantum Gradient Methods

• arxiv url: http://arxiv.org/abs/2503.17356v1
• Date: Fri, 21 Mar 2025 17:58:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-24 15:40:10.562469
• Title: Fast Convex Optimization with Quantum Gradient Methods
• Title（参考訳）: 量子勾配法による高速凸最適化
• Authors: Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shouvanik Chakrabarti, Marco Pistoia,
• Abstract要約: 雑音評価オラクルを用いた量子(サブ)次次推定に基づく量子アルゴリズムについて検討する。 古典的勾配勾配の1次クエリ複雑度は,雑音評価オラクルのみを用いて一致した。 我々は、これらのアルゴリズムをユークリッド以外の設定で動作させるように一般化する。
• 参考スコア（独自算出の注目度）: 2.5094874597551913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study quantum algorithms based on quantum (sub)gradient estimation using noisy evaluation oracles, and demonstrate the first dimension independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. We match the first-order query complexities of classical gradient descent, using only noisy evaluation oracles, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. Specifically, for the smooth case, zeroth-order quantum gradient descent achieves $\widetilde{\mathcal{O}}(LR^2/\varepsilon)$ and $\widetilde{\mathcal{O}} \left( \kappa \log(1/\varepsilon \right))$ query complexities, for the convex and strongly convex case respectively; for the nonsmooth case, the zeroth-order quantum subgradient method attains a query complexity of $\widetilde{\mathcal{O}}((GR/\varepsilon)^2 )$. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent, dual averaging and mirror prox. We demonstrate how our algorithm for nonsmooth optimization can be applied to solve an SDP involving $m$ constraints and $n \times n$ matrices to additive error $\varepsilon$ using $\widetilde{\mathcal{O}} ((mn^2+n^{\omega})(Rr/\varepsilon)^2)$ gates, where $\omega \in [2,2.38)$ is the exponent of matrix-multiplication time and $R$ and $r$ are bounds on the primal and dual optimal solutions, respectively. Specializing to linear programs, we obtain a quantum LP solver with complexity $ \widetilde{\mathcal{O}}((m+\sqrt{n}) (Rr/\varepsilon)^2).$ For zero-sum games we achieve the best quantum runtimes for any $\varepsilon > 0$ when $m = \mathcal{O}(\sqrt{n})$. We obtain the best algorithm overall (quantum or classical) whenever we further impose $\varepsilon=\Omega((m+n)^{-1/4})$.
• Abstract（参考訳）: 雑音評価オラクルを用いた量子(サブ)勾配推定に基づく量子アルゴリズムについて検討し、滑らかかつ非滑らかな設定でゼロ階凸最適化のための1次元独立なクエリ複雑度(多対数因子まで)を実証する。 古典的勾配勾配の1次クエリ複雑度をノイズ評価オラクルのみを用いてマッチングし、量子と古典的ゼロ階最適化の指数関数的分離を示す。 具体的には、滑らかな場合において、ゼロ階量子勾配勾配は$\widetilde{\mathcal{O}}(LR^2/\varepsilon)$および$\widetilde{\mathcal{O}} \left( \kappa \log(1/\varepsilon \right))$クエリ複雑さをそれぞれ、凸と強凸のそれぞれに対して達成する。 次に、量子(サブ)勾配推定を用いて、これらのアルゴリズムを非ユークリッド環境での動作に一般化し、ミラー降下、双対平均化、ミラープロキシをインスタンス化する。 我々は、m$制約を含むSDPと$n \times n$行列を加算誤差に$\varepsilon$ using $\widetilde{\mathcal{O}} ((mn^2+n^{\omega})(Rr/\varepsilon)^2)$ gates, where $\omega \in [2,2.38)$は行列乗算時間の指数であり、$R$と$r$はそれぞれ原始最適解と双対最適解に有界であることを示す。 線形プログラムに特化して、複雑性 $ \widetilde{\mathcal{O}}((m+\sqrt{n}) (Rr/\varepsilon)^2) を持つ量子LPソルバを得る。 ゼロサムゲームに対しては、$m = \mathcal{O}(\sqrt{n})$ が任意の$\varepsilon > 0$に対して最高の量子ランタイムを達成する。 さらに$\varepsilon=\Omega((m+n)^{-1/4})$を課すと、全体的なアルゴリズム(量子または古典)を得る。

関連論文リスト

• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• 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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
  量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。 また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
  論文  参考訳（メタデータ） (2022-12-05T19:10:32Z)
• 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)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。