論文の概要: Constant regret for sequence prediction with limited advice
- arxiv url: http://arxiv.org/abs/2210.02256v1
- Date: Wed, 5 Oct 2022 13:32:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 14:53:48.796644
- Title: Constant regret for sequence prediction with limited advice
- Title（参考訳）: 限られたアドバイスによるシーケンス予測に対する絶え間ない後悔
- Authors: El Mehdi Saad (LMO), G. Blanchard (LMO, DATASHAPE)
- Abstract要約: 予測とm$ge$2の専門家の損失を観測するために,p = 2の専門家のみを1ラウンド毎に組み合わせた戦略を提供する。
学習者が1ラウンドにつき1人の専門家のフィードバックのみを観察することを制約されている場合、最悪の場合の後悔は"スローレート"$Omega$($sqrt$KT)である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of cumulative regret minimization for individual
sequence prediction with respect to the best expert in a finite family of size
K under limited access to information. We assume that in each round, the
learner can predict using a convex combination of at most p experts for
prediction, then they can observe a posteriori the losses of at most m experts.
We assume that the loss function is range-bounded and exp-concave. In the
standard multi-armed bandits setting, when the learner is allowed to play only
one expert per round and observe only its feedback, known optimal regret bounds
are of the order O($\sqrt$ KT). We show that allowing the learner to play one
additional expert per round and observe one additional feedback improves
substantially the guarantees on regret. We provide a strategy combining only p
= 2 experts per round for prediction and observing m $\ge$ 2 experts' losses.
Its randomized regret (wrt. internal randomization of the learners' strategy)
is of order O (K/m) log(K$\delta$ --1) with probability 1 -- $\delta$, i.e., is
independent of the horizon T ("constant" or "fast rate" regret) if (p $\ge$ 2
and m $\ge$ 3). We prove that this rate is optimal up to a logarithmic factor
in K. In the case p = m = 2, we provide an upper bound of order O(K 2
log(K$\delta$ --1)), with probability 1 -- $\delta$. Our strategies do not
require any prior knowledge of the horizon T nor of the confidence parameter
$\delta$. Finally, we show that if the learner is constrained to observe only
one expert feedback per round, the worst-case regret is the "slow rate"
$\Omega$($\sqrt$ KT), suggesting that synchronous observation of at least two
experts per round is necessary to have a constant regret.
- Abstract（参考訳）: 我々は,情報へのアクセスが制限された有限サイズのK族において,個々のシーケンス予測に対する累積的後悔最小化の問題について検討する。
各ラウンドにおいて、学習者は、最大p専門家の凸の組み合わせを使って予測し、その後、最大m専門家の損失を後方から観察することができると仮定する。
損失関数は範囲限定かつ exp-concave であると仮定する。
標準的なマルチアームバンディット設定では、学習者が1ラウンドごとに1人の専門家のみをプレイし、そのフィードバックのみを観察できる場合、既知の最適後悔境界はO($\sqrt$KT)である。
学習者がラウンド毎に1人のエキスパートをプレイし、1つの追加フィードバックを観察できるようにすることで、後悔に対する保証が大幅に向上することを示す。
予測とm$\ge$2専門家の損失を観測するために、1ラウンドあたりp = 2専門家のみを組み合わせる戦略を提供する。
そのランダム化された後悔 (wrt. internal randomization of the learners' strategy) は順序 o (k/m) log(k$\delta$ --1) であり、確率 1 -- $\delta$、すなわち、(p $\ge$ 2 と m $\ge$ 3) のとき、水平線 t から独立している。
p = m = 2 の場合、確率 1 -- $\delta$ の位数 O(K2 log(K$\delta$ --1) の上界を与える。
我々の戦略は地平線 T の事前知識や信頼パラメータ $\delta$ の知識を必要としない。
最後に、もし学習者が1ラウンドあたり1人の専門家のフィードバックのみを観察することを制約されている場合、最悪の後悔は「スローレート」$\Omega$($\sqrt$KT)であり、1ラウンドあたりの少なくとも2人の専門家の同期観察が常に後悔することが必要であることを示唆する。
関連論文リスト
- Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。
我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
論文 参考訳（メタデータ） (2023-06-05T06:55:39Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - A Regret-Variance Trade-Off in Online Learning [14.41667013062914]
予測の分散が学習にどのように活用できるかを示す。
損失の減少を伴うオンライン予測では, 後悔に対する汚職の影響は大きなばらつきによって補うことができることを示す。
我々はその結果をオンライン線形回帰の設定にまで拡張する。
論文 参考訳（メタデータ） (2022-06-06T14:50:19Z) - No-Regret Learning with Unbounded Losses: The Case of Logarithmic
Pooling [12.933990572597583]
対数プール法(対数プール)として知られる基本的および実用的アグリゲーション法に焦点をあてる。
オンラインの対戦環境において,最適なパラメータ集合を学習する問題を考察する。
本稿では,O(sqrtT log T)$experied regretに達する方法で,専門家の重みを学習するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-22T22:27:25Z) - Fast rates for prediction with limited expert advice [0.0]
本稿では,情報へのアクセスが制限された有限族における最高の専門家予測に関して,過大な一般化誤差を最小化する問題について検討する。
トレーニングフェーズにおけるTラウンド1ラウンドあたりのエキスパートのアドバイスを1人だけ見ることができれば、最悪の場合の過剰リスクはOmega$(1/$sqrt$T)であり、確率は一定値以下であることが示される。
この設定でこの速度を達成するための新しいアルゴリズムを設計し、与えられた一般化誤差の精度を達成するのに必要な訓練ラウンド数とクエリ数に正確にインスタンス依存のバウンダリを与える。
論文 参考訳（メタデータ） (2021-10-27T14:57:36Z) - Nonstochastic Bandits with Infinitely Many Experts [1.7188280334580197]
無限に多くの専門家と非確率的盗賊の問題を考察する。
有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。
そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
論文 参考訳（メタデータ） (2021-02-09T22:42:36Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳（メタデータ） (2021-01-31T16:17:56Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
2人の専門家と1人の予測者による予測問題を考える。
専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。
もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
論文 参考訳（メタデータ） (2020-03-18T20:12:08Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。