論文の概要: Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
- arxiv url: http://arxiv.org/abs/2402.12745v1
- Date: Tue, 20 Feb 2024 06:23:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 16:45:08.198365
- Title: Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
- Title（参考訳）: 最大損失最小化のための近似量子アルゴリズム
- Authors: Hao Wang, Chenyi Zhang, Tongyang Li
- Abstract要約: 我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。
我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
- 参考スコア（独自算出の注目度）: 16.91814406135565
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of minimizing the maximum of $N$ convex, Lipschitz functions
plays significant roles in optimization and machine learning. It has a series
of results, with the most recent one requiring $O(N\epsilon^{-2/3} +
\epsilon^{-8/3})$ queries to a first-order oracle to compute an
$\epsilon$-suboptimal point. On the other hand, quantum algorithms for
optimization are rapidly advancing with speedups shown on many important
optimization problems. In this paper, we conduct a systematic study for quantum
algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz
functions. On one hand, we develop quantum algorithms with an improved
complexity bound of $\tilde{O}(\sqrt{N}\epsilon^{-5/3} + \epsilon^{-8/3})$. On
the other hand, we prove that quantum algorithms must take
$\tilde{\Omega}(\sqrt{N}\epsilon^{-2/3})$ queries to a first order quantum
oracle, showing that our dependence on $N$ is optimal up to poly-logarithmic
factors.
- Abstract（参考訳）: 最大$N$凸の最小化の問題として、リプシッツ関数は最適化と機械学習において重要な役割を果たす。
一連の結果があり、直近では$o(n\epsilon^{-2/3} + \epsilon^{-8/3})$クエリを1次オラクルに渡して$\epsilon$-suboptimal pointを計算する必要がある。
一方、最適化のための量子アルゴリズムは、多くの重要な最適化問題に対する高速化によって急速に進歩している。
本稿では,Lipschitz関数の最大値である$N$凸を最小化するために,量子アルゴリズムと下位境界の体系的研究を行う。
一方、複雑性を改良した量子アルゴリズムは、$\tilde{O}(\sqrt{N}\epsilon^{-5/3} + \epsilon^{-8/3})$である。
一方、量子アルゴリズムは1次量子オラクルに$\tilde{\omega}(\sqrt{n}\epsilon^{-2/3})のクエリを行なわなければならないことを証明し、我々は$n$への依存が多対数因子に最適であることを示した。
関連論文リスト
- 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - 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) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。