論文の概要: Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications

• arxiv url: http://arxiv.org/abs/2509.08911v1
• Date: Wed, 10 Sep 2025 18:15:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-12 16:52:24.099637
• Title: Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications
• Title（参考訳）: インスタンス最適行列乗算重み更新とその応用
• Authors: Weiyuan Gong, Tongyang Li, Xinzhao Wang, Zhiyu Zhang,
• Abstract要約: O(sqrtTcdot S(X||d-1I_d))$。 偏極ノイズ,ランダムな量子状態,ギブス状態によって崩壊した量子状態の学習技術よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 18.700744251450313
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Matrix Multiplicative Weight Update (MMWU) is a seminal online learning algorithm with numerous applications. Applied to the matrix version of the Learning from Expert Advice (LEA) problem on the $d$-dimensional spectraplex, it is well known that MMWU achieves the minimax-optimal regret bound of $O(\sqrt{T\log d})$, where $T$ is the time horizon. In this paper, we present an improved algorithm achieving the instance-optimal regret bound of $O(\sqrt{T\cdot S(X||d^{-1}I_d)})$, where $X$ is the comparator in the regret, $I_d$ is the identity matrix, and $S(\cdot||\cdot)$ denotes the quantum relative entropy. Furthermore, our algorithm has the same computational complexity as MMWU, indicating that the improvement in the regret bound is ``free''. Technically, we first develop a general potential-based framework for matrix LEA, with MMWU being its special case induced by the standard exponential potential. Then, the crux of our analysis is a new ``one-sided'' Jensen's trace inequality built on a Laplace transform technique, which allows the application of general potential functions beyond exponential to matrix LEA. Our algorithm is finally induced by an optimal potential function from the vector LEA problem, based on the imaginary error function. Complementing the above, we provide a memory lower bound for matrix LEA, and explore the applications of our algorithm in quantum learning theory. We show that it outperforms the state of the art for learning quantum states corrupted by depolarization noise, random quantum states, and Gibbs states. In addition, applying our algorithm to linearized convex losses enables predicting nonlinear quantum properties, such as purity, quantum virtual cooling, and R\'{e}nyi-$2$ correlation.
• Abstract（参考訳）: Matrix Multiplicative Weight Update (MMWU) は、多数のアプリケーションを対象としたオンライン学習アルゴリズムである。 $d$-dimensional spectraplex 上の Learning from Expert Advice (LEA) 問題の行列版に適用すると、MMWU が $O(\sqrt{T\log d})$ のミニマックス最適後悔境界を達成することはよく知られている。 本稿では,O(\sqrt{T\cdot S(X||d^{-1}I_d)})$,$X$が後悔のコンパレータ,$I_d$がアイデンティティ行列,$S(\cdot||\cdot)$が量子相対エントロピーを表す改良アルゴリズムを提案する。 さらに, このアルゴリズムは, MMWU と同じ計算量で, 後悔境界の改善は ``free'' であることを示す。 まず,MMWUが標準指数ポテンシャルによって誘導される特殊な場合として,行列LEAのための汎用ポテンシャルベースフレームワークを開発した。 そして、我々の分析の要点は、ラプラス変換法に基づいて構築された新しい '`one-sided'' のジェンセンのトレース不等式である。 提案アルゴリズムは,ベクトルLEA問題から最適ポテンシャル関数を導出し,虚数誤差関数を導出する。 以上を補完し、行列LEAのメモリローバウンドを提供し、量子学習理論におけるアルゴリズムの適用について検討する。 偏極ノイズ、ランダムな量子状態、ギブス状態によって崩壊した量子状態の学習において、最先端の量子状態よりも優れていることを示す。 さらに,線形凸損失に対するアルゴリズムの適用により,純度,量子仮想冷却,R\'{e}nyi-$2$相関などの非線形量子特性の予測が可能となった。

関連論文リスト

• Matrix Inversion by Quantum Walk [0.0]
  行列反転のためのHHLアルゴリズムは、量子計算における画期的なアルゴリズムである。 位相推定を連続時間量子ウォークに置き換えることでアルゴリズムを大幅に単純化する。
  論文  参考訳（メタデータ） (2025-08-08T18:00:05Z)
• Quantum Non-Linear Bandit Optimization [2.7718037613443127]
  学習者がゼロ次関数オラクルを持つブラックボックス関数を最大化する非線形帯域最適化について検討する。 本稿では,新しいパラメトリック関数近似手法を用いたQ-NLB-UCBアルゴリズムを提案する。 Q-NLB-UCB の後悔境界は、$O(mathrmpolylog T)$だけでなく、入力次元も含まないことを証明している。
  論文  参考訳（メタデータ） (2025-03-04T21:53:33Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。 Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。 評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
  論文  参考訳（メタデータ） (2024-04-30T23:55:03Z)
• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret [23.418957451727255]
  量子強化学習(RL)のための新しいUCRL型アルゴリズムを提案する。 我々は$mathcalO(mathrmpoly(S, A, H, log T))$ the worst-case regret for it, where $T$ is the number of episodes。 具体的には、$d$次元線形表現を持つ線形混合MDPに対する値目標回帰(VTR)に基づく量子アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2023-02-21T16:23:11Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• 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)

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

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