論文の概要: Damped Online Newton Step for Portfolio Selection

• arxiv url: http://arxiv.org/abs/2202.07574v1
• Date: Tue, 15 Feb 2022 17:01:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-16 16:07:25.673797
• Title: Damped Online Newton Step for Portfolio Selection
• Title（参考訳）: ポートフォリオ選択のためのオンラインニュートンステップの減衰
• Authors: Zakaria Mhammedi and Alexander Rakhlin
• Abstract要約: 古典的なオンラインポートフォリオ選択の問題を再考し、各ラウンドで学習者がポートフォリオの集合上の分布を選択し、その富を割り当てる。 この問題に対する対数的後悔を達成する既存のアルゴリズムは、ラウンドの総数とスケールする時間と空間の複雑さがある。 対数的後悔を伴う最初の実用的オンラインポートフォリオ選択アルゴリズムを提示し、その時間と空間の複雑さは水平線上で対数的にのみ依存する。
• 参考スコア（独自算出の注目度）: 96.0297968061824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the classic online portfolio selection problem, where at each round a learner selects a distribution over a set of portfolios to allocate its wealth. It is known that for this problem a logarithmic regret with respect to Cover's loss is achievable using the Universal Portfolio Selection algorithm, for example. However, all existing algorithms that achieve a logarithmic regret for this problem have per-round time and space complexities that scale polynomially with the total number of rounds, making them impractical. In this paper, we build on the recent work by Haipeng et al. 2018 and present the first practical online portfolio selection algorithm with a logarithmic regret and whose per-round time and space complexities depend only logarithmically on the horizon. Behind our approach are two key technical novelties of independent interest. We first show that the Damped Online Newton steps can approximate mirror descent iterates well, even when dealing with time-varying regularizers. Second, we present a new meta-algorithm that achieves an adaptive logarithmic regret (i.e. a logarithmic regret on any sub-interval) for mixable losses.
• Abstract（参考訳）: 古典的なオンラインポートフォリオ選択の問題を再考し、各ラウンドで学習者がポートフォリオの集合上の分布を選択し、その富を割り当てる。 この問題に対して、カバーの損失に関する対数的後悔は、例えばユニバーサルポートフォリオ選択アルゴリズムを用いて達成可能であることが知られている。 しかし、この問題に対する対数的後悔を達成する既存のアルゴリズムは、丸ごとの総数と多項式的にスケールする時間と空間の複雑さを持ち、現実的ではない。 本稿では,Haipengらによる最近の研究に基づいて,対数的後悔を伴う最初の実用的なオンラインポートフォリオ選択アルゴリズムを提案する。 私たちのアプローチの背後には、2つの重要な技術革新があります。 まず, 減衰したオンラインニュートンステップは, 時変正規化器を扱う場合においても鏡面降下を緩和できることを示した。 第2に,混合損失に対する適応対数的後悔(すなわち,任意のサブインターバルにおける対数的後悔)を実現するメタアルゴリズムを提案する。

関連論文リスト

• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum States [33.073320699506326]
  従来のオンラインポートフォリオ選択問題を再考する。 本稿では,まず,多言語的後悔を求めるアルゴリズムBISONSを提案する。 我々は、より一般的な問題、ログロスを伴う量子状態のオンライン学習にアルゴリズムと分析を拡張した。
  論文  参考訳（メタデータ） (2022-02-06T12:15:55Z)
• Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses [0.0]
  動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。 文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
  論文  参考訳（メタデータ） (2021-09-28T15:06:31Z)
• Gap-Dependent Bounds for Two-Player Markov Games [122.20541282562363]
  2-TBSGによる2プレイヤーターン型マルコフゲームにおけるナッシュラーニングアルゴリズムの実行時の累積的後悔の分析 この境界は対数項のみの理論的な下界と一致する。 我々は、無限の地平線でディスカウントされたゲーム設定に結論を拡張し、同様のギャップ依存対数後悔境界を提案する。
  論文  参考訳（メタデータ） (2021-07-01T18:25:07Z)
• On Limited-Memory Subsampling Strategies for Bandits [0.0]
  本稿では,Budry et al. (2020) の最近の研究で提案されている単純な決定論的部分サンプリング則が,一次元指数関数族において最適であることを示す。 また、これらの保証は、アルゴリズムメモリを時間軸の多対数関数に制限する場合にも有効であることを示す。 本稿では,近年の観測結果のみをサブサンプリングに用い,既知の急激な変化を前提とした最適後悔保証を実現するアルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2021-06-21T09:11:22Z)
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL [34.15978290083909]
  バンディットおよび強化学習問題におけるアルゴリズムの簡易モデル選択手法を提案する。 我々は、このアプローチの総後悔は、最も有効な候補者の後悔の回数が乗算的要因であることを証明します。 線形バンディットのモデル選択における最近の取り組みとは違って,我々のアプローチは,敵の環境によってコンテキスト情報が生成されるケースをカバーできるほど多用途である。
  論文  参考訳（メタデータ） (2020-12-24T00:53:42Z)
• 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)
• Efficient improper learning for online logistic regression [68.8204255655161]
  サンプル数 n の対数的後悔を持つ任意の正則アルゴリズムは、必然的に B の指数乗法定数を損なうことが知られている。 本研究では、対数的後悔を保ちながら、この指数定数を回避する効率的な不適切なアルゴリズムを設計する。 シュロゲート損失を伴う正規化経験的リスク最小化に基づく新しいアルゴリズムは、O(B log(Bn))として、オーダーO(d2)の1回あたりの時間複雑度で、後悔のスケーリングを満足させる。
  論文  参考訳（メタデータ） (2020-03-18T09:16:14Z)

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

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