論文の概要: Fast rates for prediction with limited expert advice
- arxiv url: http://arxiv.org/abs/2110.14485v1
- Date: Wed, 27 Oct 2021 14:57:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 15:11:19.255797
- Title: Fast rates for prediction with limited expert advice
- Title(参考訳): 専門的アドバイスを限定した予測の速さ
- Authors: El Mehdi Saad (CELESTE, LMO), Gilles Blanchard (LMO, DATASHAPE)
- Abstract要約: 本稿では,情報へのアクセスが制限された有限族における最高の専門家予測に関して,過大な一般化誤差を最小化する問題について検討する。
トレーニングフェーズにおけるTラウンド1ラウンドあたりのエキスパートのアドバイスを1人だけ見ることができれば、最悪の場合の過剰リスクはOmega$(1/$sqrt$T)であり、確率は一定値以下であることが示される。
この設定でこの速度を達成するための新しいアルゴリズムを設計し、与えられた一般化誤差の精度を達成するのに必要な訓練ラウンド数とクエリ数に正確にインスタンス依存のバウンダリを与える。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of minimizing the excess generalization error with
respect to the best expert prediction in a finite family in the stochastic
setting, under limited access to information. We assume that the learner only
has access to a limited number of expert advices per training round, as well as
for prediction. Assuming that the loss function is Lipschitz and strongly
convex, we show that if we are allowed to see the advice of only one expert per
round for T rounds in the training phase, or to use the advice of only one
expert for prediction in the test phase, the worst-case excess risk is
$\Omega$(1/ $\sqrt$ T) with probability lower bounded by a constant. However,
if we are allowed to see at least two actively chosen expert advices per
training round and use at least two experts for prediction, the fast rate
O(1/T) can be achieved. We design novel algorithms achieving this rate in this
setting, and in the setting where the learner has a budget constraint on the
total number of observed expert advices, and give precise instance-dependent
bounds on the number of training rounds and queries needed to achieve a given
generalization error precision.
- Abstract(参考訳): 本稿では,情報へのアクセス制限の下で,確率的条件下での有限族における最高の専門家予測に対する過剰な一般化誤差を最小化する問題について検討する。
学習者は、トレーニングラウンド毎に限られた数の専門家のアドバイスと、予測にしかアクセスできないと仮定する。
損失関数がリプシッツで強い凸であると仮定すると、訓練段階ではTラウンドあたりの1人の専門家のアドバイスを見ることができ、またテストフェーズでの予測に1人の専門家のアドバイスを使うことができれば、最悪の場合の余剰リスクは、確率を定数で下限に抑えた$\Omega$(1/$\sqrt$T)となる。
しかし、トレーニングラウンド毎に少なくとも2つのアクティブな専門家アドバイスを確認でき、少なくとも2つの専門家を使って予測できる場合、O(1/T)の速さが達成できる。
この設定でこの速度を達成する新しいアルゴリズムを設計し、学習者が観察した専門家のアドバイスの総数に予算制約を課す設定において、与えられた一般化誤差の精度を達成するのに必要なトレーニングラウンド数とクエリの正確なインスタンス依存境界を与える。
関連論文リスト
- An Adversarial Analysis of Thompson Sampling for Full-information Online Learning: from Finite to Infinite Action Spaces [54.37047702755926]
我々は完全なフィードバックの下でオンライン学習のためのトンプソンサンプリングの分析法を開発した。
我々は、後悔の分解を、学習者が先入観を期待したことを後悔させ、また、過度な後悔と呼ぶ先延ばし的な用語を示します。
論文 参考訳(メタデータ) (2025-02-20T18:10:12Z) - Learning to Partially Defer for Sequences [17.98959620987217]
モデル全体の予測の特定の出力を専門家に推論できるシーケンス出力のL2D設定を提案する。
また、旅行セールスマンソルバやニュース要約モデルにおいて、こうした粒度のデリラルが全デリラルよりもコスト精度のトレードオフを達成できることを実証的に示す。
論文 参考訳(メタデータ) (2025-02-03T15:50:11Z) - Rethinking Early Stopping: Refine, Then Calibrate [49.966899634962374]
校正誤差と校正誤差は,訓練中に同時に最小化されないことを示す。
我々は,早期停止とハイパーパラメータチューニングのための新しい指標を導入し,トレーニング中の改善誤差を最小限に抑える。
本手法は,任意のアーキテクチャとシームレスに統合し,多様な分類タスクにおける性能を継続的に向上する。
論文 参考訳(メタデータ) (2025-01-31T15:03:54Z) - Inverse Reinforcement Learning with Sub-optimal Experts [56.553106680769474]
与えられた専門家の集合と互換性のある報酬関数のクラスの理論的性質について検討する。
以上の結果から,複数の準最適専門家の存在が,相反する報酬の集合を著しく減少させる可能性が示唆された。
我々は,最適なエージェントの1つに十分近い準最適専門家のパフォーマンスレベルが最適である場合に,最小限の最適化を行う一様サンプリングアルゴリズムを解析する。
論文 参考訳(メタデータ) (2024-01-08T12:39:25Z) - 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) - On Second-Order Scoring Rules for Epistemic Uncertainty Quantification [8.298716599039501]
本研究では,2次学習者が不確実性を忠実に表現する動機となる損失関数が存在しないことを示す。
この結果を証明するための主要な数学的ツールとして,2次スコアリングルールの一般化概念を導入する。
論文 参考訳(メタデータ) (2023-01-30T08:59:45Z) - Constant regret for sequence prediction with limited advice [0.0]
予測とm$ge$2の専門家の損失を観測するために,p = 2の専門家のみを1ラウンド毎に組み合わせた戦略を提供する。
学習者が1ラウンドにつき1人の専門家のフィードバックのみを観察することを制約されている場合、最悪の場合の後悔は"スローレート"$Omega$($sqrt$KT)である。
論文 参考訳(メタデータ) (2022-10-05T13:32:49Z) - Optimal Tracking in Prediction with Expert Advice [0.0]
専門家のアドバイス設定を用いて予測を検証し、専門家の集合が生み出す決定を組み合わせて意思決定を行うことを目的とする。
我々は、専門家のアドバイス設定による予測の下で、最小限の動的後悔を達成する。
我々のアルゴリズムは、このような普遍的に最適で適応的で真にオンラインの保証を、事前の知識なしで生成した最初のアルゴリズムです。
論文 参考訳(メタデータ) (2022-08-07T12:29:54Z) - No-Regret Learning with Unbounded Losses: The Case of Logarithmic
Pooling [12.933990572597583]
対数プール法(対数プール)として知られる基本的および実用的アグリゲーション法に焦点をあてる。
オンラインの対戦環境において,最適なパラメータ集合を学習する問題を考察する。
本稿では,O(sqrtT log T)$experied regretに達する方法で,専門家の重みを学習するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-22T22:27:25Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
2人の専門家と1人の予測者による予測問題を考える。
専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。
もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
論文 参考訳(メタデータ) (2020-03-18T20:12:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。