論文の概要: Statistical Estimation in the Spiked Tensor Model via the Quantum
Approximate Optimization Algorithm
- arxiv url: http://arxiv.org/abs/2402.19456v1
- Date: Thu, 29 Feb 2024 18:50:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-01 13:29:54.106205
- Title: Statistical Estimation in the Spiked Tensor Model via the Quantum
Approximate Optimization Algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムによるスパイクテンソルモデルの統計的推定
- Authors: Leo Zhou, Joao Basso, Song Mei
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、最適化のための汎用アルゴリズムである。
我々は,1ドルステップのQAOAの弱い回復しきい値が1ドルステップのテンソルパワーの繰り返し値と一致することを証明した。
ある$p$と$q$に対して、QAOAはテンソルパワーオーバーラップよりも定数係数が大きいオーバーラップを達成する。
- 参考スコア（独自算出の注目度）: 17.955614278088238
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a general-purpose
algorithm for combinatorial optimization. In this paper, we analyze the
performance of the QAOA on a statistical estimation problem, namely, the spiked
tensor model, which exhibits a statistical-computational gap classically. We
prove that the weak recovery threshold of $1$-step QAOA matches that of
$1$-step tensor power iteration. Additional heuristic calculations suggest that
the weak recovery threshold of $p$-step QAOA matches that of $p$-step tensor
power iteration when $p$ is a fixed constant. This further implies that
multi-step QAOA with tensor unfolding could achieve, but not surpass, the
classical computation threshold $\Theta(n^{(q-2)/4})$ for spiked $q$-tensors.
Meanwhile, we characterize the asymptotic overlap distribution for $p$-step
QAOA, finding an intriguing sine-Gaussian law verified through simulations. For
some $p$ and $q$, the QAOA attains an overlap that is larger by a constant
factor than the tensor power iteration overlap. Of independent interest, our
proof techniques employ the Fourier transform to handle difficult combinatorial
sums, a novel approach differing from prior QAOA analyses on spin-glass models
without planted structure.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は組合せ最適化のための汎用アルゴリズムである。
本稿では,統計的推定問題,すなわち,古典的に統計計算のギャップを示すスパイクテンソルモデルにおいて,QAOAの性能を解析する。
我々は,1ドルステップのQAOAの弱い回復閾値が1ドルステップのテンソルパワーの繰り返しと一致することを証明した。
追加のヒューリスティックな計算は、$p$-step qaoaの弱い回復しきい値が$p$が固定定数であるときに$p$-stepテンソルパワーイテレーションのそれと一致することを示唆している。
これはさらに、テンソル展開を伴うマルチステップQAOAが、スパイクされた$q$-tensorsに対して古典的な計算しきい値$\Theta(n^{(q-2)/4})$を達成できることを示している。
一方, p$-step qaoa に対する漸近的重なり分布を特徴付け, シミュレーションにより検証された興味深い正弦-ガウス則を見いだした。
幾らかの$p$と$q$に対して、QAOAはテンソルパワーの繰り返しの重なりよりも定数係数が大きい重なりが得られる。
本手法は, 固定構造を持たないスピングラスモデルにおいて, 従来のQAOA解析と異なり, 難解な組合せ和を扱うためにフーリエ変換を用いる。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - On the Accuracy of Hotelling-Type Tensor Deflation: A Random Tensor
Analysis [16.28927188636617]
階数-$r$ の $sum_i=1r beta_i A_i + W$ の非対称スパイクモデルを考える。
本研究では, ホテルリング型デフレに関する研究を行った。
論文 参考訳（メタデータ） (2022-11-16T16:01:56Z) - Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models [15.857373057387669]
無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。
我々の分析は、サドル点近似の和対パス積分によって理解することができる。
一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
論文 参考訳（メタデータ） (2022-04-21T17:40:39Z) - Provably Efficient Convergence of Primal-Dual Actor-Critic with
Nonlinear Function Approximation [15.319335698574932]
The first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sample。
Open GymAI連続制御タスクの結果。
論文 参考訳（メタデータ） (2022-02-28T15:16:23Z) - Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation
from Incomplete Measurements [30.395874385570007]
基本的な課題は、高度に不完全な測定からテンソルを忠実に回収することである。
タッカー分解におけるテンソル因子を直接回復するアルゴリズムを開発した。
2つの正準問題に対する基底真理テンソルの線形独立率で確実に収束することを示す。
論文 参考訳（メタデータ） (2021-04-29T17:44:49Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - Tight Nonparametric Convergence Rates for Stochastic Gradient Descent
under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。
特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文 参考訳（メタデータ） (2020-06-15T08:25:50Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。