論文の概要: A Generalized Online Algorithm for Translation and Scale Invariant
Prediction with Expert Advice
- arxiv url: http://arxiv.org/abs/2009.04372v1
- Date: Wed, 9 Sep 2020 15:45:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-20 08:45:37.030337
- Title: A Generalized Online Algorithm for Translation and Scale Invariant
Prediction with Expert Advice
- Title(参考訳): エキスパートによる翻訳・スケール不変予測のための一般化オンラインアルゴリズム
- Authors: Kaan Gokcesu, Hakan Gokcesu
- Abstract要約: 本稿では,専門家の助言問題による逐次予測において,一般競合クラスに対するアルゴリズムの期待された後悔について検討する。
我々の後悔の限界は任意のスケーリングと損失の翻訳の下で安定している。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we aim to create a completely online algorithmic framework for
prediction with expert advice that is translation-free and scale-free of the
expert losses. Our goal is to create a generalized algorithm that is suitable
for use in a wide variety of applications. For this purpose, we study the
expected regret of our algorithm against a generic competition class in the
sequential prediction by expert advice problem, where the expected regret
measures the difference between the losses of our prediction algorithm and the
losses of the 'best' expert selection strategy in the competition. We design
our algorithm using the universal prediction perspective to compete against a
specified class of expert selection strategies, which is not necessarily a
fixed expert selection. The class of expert selection strategies that we want
to compete against is purely determined by the specific application at hand and
is left generic, which makes our generalized algorithm suitable for use in many
different problems. We show that no preliminary knowledge about the loss
sequence is required by our algorithm and its performance bounds, which are
second order, expressed in terms of sums of squared losses. Our regret bounds
are stable under arbitrary scalings and translations of the losses.
- Abstract(参考訳): 本研究は, 専門家の損失に対して, 翻訳不要かつスケールフリーな, 専門家のアドバイスによる予測のための, 完全にオンラインなアルゴリズムフレームワークの構築を目的とする。
私たちの目標は、幅広いアプリケーションでの使用に適した一般化アルゴリズムを作ることです。
そこで本研究では,予測アルゴリズムの損失と競争における「最良の」専門家選択戦略の損失の差を推定する,専門家アドバイス問題による逐次予測における汎用的競争クラスに対するアルゴリズムの期待後悔について検討する。
本アルゴリズムは,必ずしも固定された専門家選択戦略ではない,特定の専門家選択戦略のクラスと競合するために,普遍的な予測視点を用いたアルゴリズムを設計する。
私たちが競争したいエキスパート選択戦略のクラスは、手元の特定のアプリケーションによって純粋に決定され、汎用的であり、このため、我々の一般的なアルゴリズムは、多くの異なる問題での使用に適している。
我々は,損失系列に関する予備的な知識をアルゴリズムに必要とせず,その性能境界は二階数であり,二乗損失の和で表されることを示した。
我々の後悔の限界は任意のスケーリングと損失の翻訳の下で安定している。
関連論文リスト
- Data Dependent Regret Guarantees Against General Comparators for Full or
Bandit Feedback [0.0]
対戦型オンライン学習問題について検討し、完全オンライン・アルゴリズム・フレームワークを構築した。
我々のアルゴリズムは普遍的な予測の観点から機能し、使用する性能指標は任意のコンパレータ列に対する期待された後悔である。
論文 参考訳(メタデータ) (2023-03-12T00:18:46Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳(メタデータ) (2023-03-03T04:39:53Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳(メタデータ) (2023-01-30T13:17:15Z) - Optimal Tracking in Prediction with Expert Advice [0.0]
専門家のアドバイス設定を用いて予測を検証し、専門家の集合が生み出す決定を組み合わせて意思決定を行うことを目的とする。
我々は、専門家のアドバイス設定による予測の下で、最小限の動的後悔を達成する。
我々のアルゴリズムは、このような普遍的に最適で適応的で真にオンラインの保証を、事前の知識なしで生成した最初のアルゴリズムです。
論文 参考訳(メタデータ) (2022-08-07T12:29:54Z) - Second Order Regret Bounds Against Generalized Expert Sequences under
Partial Bandit Feedback [0.0]
本稿では,部分帯域フィードバック設定下でのエキスパートアドバイスの問題について検討し,逐次ミニマックス最適アルゴリズムを作成する。
本アルゴリズムは,従来の帯域幅フィードバックとは対照的に,逆向きに損失を明らかにすることのできる,より一般的な部分的監視設定で動作する。
論文 参考訳(メタデータ) (2022-04-13T22:48:12Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-10T10:02:31Z) - Generalized Translation and Scale Invariant Online Algorithm for
Adversarial Multi-Armed Bandits [0.0]
敵の多腕バンディット問題について検討し、任意の翻訳と腕の損失のスケールで不変な完全にオンラインのアルゴリズムフレームワークを作成する。
我々のアルゴリズムは、普遍的な予測の観点から機能し、使用する性能指標は、任意のアーム選択シーケンスに対して期待された後悔である。
論文 参考訳(メタデータ) (2021-09-19T20:13:59Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳(メタデータ) (2021-07-03T23:17:26Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳(メタデータ) (2021-03-02T11:04:33Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳(メタデータ) (2020-10-22T04:51:01Z) - No-Regret and Incentive-Compatible Online Learning [29.267666165169324]
本研究では,学習アルゴリズムの予測に対する影響を最大化するために,専門家が戦略的に行動するオンライン学習環境について検討する。
私たちは、学習アルゴリズムを、後見の最高の固定専門家に対して、不適切なものにしたいと考えています。
完全な情報設定と部分的な情報設定の両方について、専門家にとって後悔とインセンティブの相性のないアルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-02-20T16:21:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。