論文の概要: Classical and Quantum Iterative Optimization Algorithms Based on Matrix
Legendre-Bregman Projections
- arxiv url: http://arxiv.org/abs/2209.14185v1
- Date: Wed, 28 Sep 2022 15:59:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 19:37:10.588201
- Title: Classical and Quantum Iterative Optimization Algorithms Based on Matrix
Legendre-Bregman Projections
- Title(参考訳): 行列レジェンドレ・ブレグマン射影に基づく古典的および量子的反復最適化アルゴリズム
- Authors: Zhengfeng Ji
- Abstract要約: エルミート行列空間上で定義されたルジャンドル・ブレーグマン射影について考察し,それに基づいて反復最適化アルゴリズムを設計する。
本稿では,ブレグマン射影アルゴリズムと近似的ブラグマン射影アルゴリズムについて検討する。
特に、近似反復アルゴリズムは、最大エントロピー推論のための一般化反復スケーリング(GIS)アルゴリズムの非可換バージョンをもたらす。
- 参考スコア(独自算出の注目度): 1.5736899098702972
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider Legendre-Bregman projections defined on the Hermitian matrix
space and design iterative optimization algorithms based on them. A general
duality theorem is established for Bregman divergences on Hermitian matrices,
and it plays a crucial role in proving the convergence of the iterative
algorithms. We study both exact and approximate Bregman projection algorithms.
In the particular case of Kullback-Leibler divergence, our approximate
iterative algorithm gives rise to the non-commutative versions of both the
generalized iterative scaling (GIS) algorithm for maximum entropy inference and
the AdaBoost algorithm in machine learning as special cases. As the
Legendre-Bregman projections are simple matrix functions on Hermitian matrices,
quantum algorithmic techniques are applicable to achieve potential speedups in
each iteration of the algorithm. We discuss several quantum algorithmic design
techniques applicable in our setting, including the smooth function evaluation
technique, two-phase quantum minimum finding, and NISQ Gibbs state preparation.
- Abstract(参考訳): エルミート行列空間上で定義されたルジャンドル・ブレグマン射影とそれに基づく反復最適化アルゴリズムを考える。
一般双対定理は、エルミート行列上のブレグマン発散に対して成立し、反復アルゴリズムの収束を証明する上で重要な役割を果たす。
ブレグマン射影アルゴリズムと近似ブレグマン射影アルゴリズムの両方について検討した。
Kullback-Leibler分散の場合、我々の近似反復アルゴリズムは、最大エントロピー推論のための一般化反復スケーリング(GIS)アルゴリズムと機械学習におけるAdaBoostアルゴリズムの両方の非可換バージョンを特殊ケースとして生み出す。
ルジャンドル・ブレグマン射影はエルミート行列上の単純な行列関数であるため、アルゴリズムの各イテレーションで潜在的な高速化を達成するために量子アルゴリズム手法が適用できる。
本稿では,スムーズな関数評価手法,2相量子最小探索法,NISQギブス状態生成法など,この設定に適用可能な量子アルゴリズム設計手法について論じる。
関連論文リスト
- A fixed-point algorithm for matrix projections with applications in
quantum information [7.988085110283119]
このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。
量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
論文 参考訳(メタデータ) (2023-12-22T11:16:11Z) - Learning the Positions in CountSketch [56.22648269865784]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-11T07:28:35Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Fast Projected Newton-like Method for Precision Matrix Estimation under
Total Positivity [15.023842222803058]
現在のアルゴリズムはブロック座標降下法や近点アルゴリズムを用いて設計されている。
本稿では,2次元投影法に基づく新しいアルゴリズムを提案し,慎重に設計された探索方向と変数分割方式を取り入れた。
合成および実世界のデータセットに対する実験結果から,提案アルゴリズムは最先端の手法と比較して計算効率を著しく向上させることを示した。
論文 参考訳(メタデータ) (2021-12-03T14:39:10Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Optimizing the Phase Estimation Algorithm Applied to the Quantum
Simulation of Heisenberg-Type Hamiltonians [0.0]
位相推定アルゴリズムは、暗号、数論、量子システムのシミュレーションに応用された強力な量子アルゴリズムである。
このアルゴリズムを用いて、ハイゼンベルク・ハミルトニアンの下での2つのスピン-1/2粒子系の時間発展をシミュレートする。
アルゴリズムには円、反復、ベイジアンの3つの最適化を導入する。
論文 参考訳(メタデータ) (2021-05-07T21:41:08Z) - Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
本稿では,リッジ回帰モデルに基づく量子アルゴリズムを提案する。
提案アルゴリズムは幅広い応用範囲を持ち,提案アルゴリズムは他の量子アルゴリズムのサブルーチンとして利用することができる。
論文 参考訳(メタデータ) (2021-04-27T11:03:52Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳(メタデータ) (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。