論文の概要: Pushing the Efficiency-Regret Pareto Frontier for Online Learning of
Portfolios and Quantum States
- arxiv url: http://arxiv.org/abs/2202.02765v1
- Date: Sun, 6 Feb 2022 12:15:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-09 09:52:28.311244
- Title: Pushing the Efficiency-Regret Pareto Frontier for Online Learning of
Portfolios and Quantum States
- Title（参考訳）: ポートフォリオと量子状態のオンライン学習のための効率-回帰パレートフロンティアの推進
- Authors: Julian Zimmert, Naman Agarwal, Satyen Kale
- Abstract要約: 従来のオンラインポートフォリオ選択問題を再考する。
本稿では,まず,多言語的後悔を求めるアルゴリズムBISONSを提案する。
我々は、より一般的な問題、ログロスを伴う量子状態のオンライン学習にアルゴリズムと分析を拡張した。
- 参考スコア（独自算出の注目度）: 33.073320699506326
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We revisit the classical online portfolio selection problem. It is widely
assumed that a trade-off between computational complexity and regret is
unavoidable, with Cover's Universal Portfolios algorithm, SOFT-BAYES and
ADA-BARRONS currently constituting its state-of-the-art Pareto frontier. In
this paper, we present the first efficient algorithm, BISONS, that obtains
polylogarithmic regret with memory and per-step running time requirements that
are polynomial in the dimension, displacing ADA-BARRONS from the Pareto
frontier. Additionally, we resolve a COLT 2020 open problem by showing that a
certain Follow-The-Regularized-Leader algorithm with log-barrier regularization
suffers an exponentially larger dependence on the dimension than previously
conjectured. Thus, we rule out this algorithm as a candidate for the Pareto
frontier. We also extend our algorithm and analysis to a more general problem
than online portfolio selection, viz. online learning of quantum states with
log loss. This algorithm, called SCHRODINGER'S BISONS, is the first efficient
algorithm with polylogarithmic regret for this more general problem.
- Abstract（参考訳）: 従来のオンラインポートフォリオ選択問題を再考する。
CoverのUniversal Portfoliosアルゴリズム、SOFT-BAYES、ADA-BARRONSが現在最先端のParetoフロンティアを構成しているため、計算複雑性と後悔のトレードオフは避けられないと広く考えられている。
本稿では,PartoフロンティアからADA-BARRONSを取り除き,その次元の多項式であるメモリとステップごとのランニング時間要件を記憶する,最初の効率的なアルゴリズムであるBISONSを提案する。
さらに、log-barrier正規化を持つある種の後続正規化リーダーアルゴリズムが、以前予想したよりも指数関数的に大きな次元依存性を被ることを示すことにより、colt 2020 open problemを解決した。
したがって、我々はこのアルゴリズムをパレートフロンティアの候補として除外する。
また、オンラインポートフォリオ選択よりも一般的な問題である、ログロスを伴う量子状態のオンライン学習にもアルゴリズムと解析を拡張しました。
このアルゴリズムはSCHROINGER'S BISONSと呼ばれ、このより一般的な問題に対する多元論的後悔を伴う最初の効率的なアルゴリズムである。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Second Order Methods for Bandit Optimization and Control [34.51425758864638]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳（メタデータ） (2024-02-14T04:03:38Z) - Online Learning Quantum States with the Logarithmic Loss via VB-FTRL [1.8856444568755568]
対数損失を伴う量子状態のオンライン学習(LL-OLQS)は、30年以上にわたってオンライン学習において古典的なオープンな問題である。
本稿では,LL-OLQS に対する VB-FTRL を適度な計算量で一般化する。
それぞれのアルゴリズムは半定値プログラムで構成されており、例えば、切断平面法によって時間内に実装することができる。
論文 参考訳（メタデータ） (2023-11-06T15:45:33Z) - Damped Online Newton Step for Portfolio Selection [96.0297968061824]
古典的なオンラインポートフォリオ選択の問題を再考し、各ラウンドで学習者がポートフォリオの集合上の分布を選択し、その富を割り当てる。
この問題に対する対数的後悔を達成する既存のアルゴリズムは、ラウンドの総数とスケールする時間と空間の複雑さがある。
対数的後悔を伴う最初の実用的オンラインポートフォリオ選択アルゴリズムを提示し、その時間と空間の複雑さは水平線上で対数的にのみ依存する。
論文 参考訳（メタデータ） (2022-02-15T17:01:55Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Entropic barriers as a reason for hardness in both classical and quantum
algorithms [2.062593640149623]
古典的および量子的アルゴリズムを用いて3つの規則ランダムグラフ上の3-XORSATという難解な最適化問題を解く。
大規模なエネルギー障壁を乗り越えることができない新しい準グレーディアルゴリズムを導入することにより、問題硬度は主にエントロピー障壁によるものであることを示す。
論文 参考訳（メタデータ） (2021-01-30T07:58:24Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。