論文の概要: A Regret-Variance Trade-Off in Online Learning
- arxiv url: http://arxiv.org/abs/2206.02656v1
- Date: Mon, 6 Jun 2022 14:50:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-07 20:19:52.933932
- Title: A Regret-Variance Trade-Off in Online Learning
- Title（参考訳）: オンライン学習におけるRegret-Variance Trade-Off
- Authors: Dirk van der Hoeven, Nikita Zhivotovskiy, Nicol\`o Cesa-Bianchi
- Abstract要約: 予測の分散が学習にどのように活用できるかを示す。
損失の減少を伴うオンライン予測では, 後悔に対する汚職の影響は大きなばらつきによって補うことができることを示す。
我々はその結果をオンライン線形回帰の設定にまで拡張する。
- 参考スコア（独自算出の注目度）: 14.41667013062914
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider prediction with expert advice for strongly convex and bounded
losses, and investigate trade-offs between regret and "variance" (i.e., squared
difference of learner's predictions and best expert predictions). With $K$
experts, the Exponentially Weighted Average (EWA) algorithm is known to achieve
$O(\log K)$ regret. We prove that a variant of EWA either achieves a negative
regret (i.e., the algorithm outperforms the best expert), or guarantees a
$O(\log K)$ bound on both variance and regret. Building on this result, we show
several examples of how variance of predictions can be exploited in learning.
In the online to batch analysis, we show that a large empirical variance allows
to stop the online to batch conversion early and outperform the risk of the
best predictor in the class. We also recover the optimal rate of model
selection aggregation when we do not consider early stopping. In online
prediction with corrupted losses, we show that the effect of corruption on the
regret can be compensated by a large variance. In online selective sampling, we
design an algorithm that samples less when the variance is large, while
guaranteeing the optimal regret bound in expectation. In online learning with
abstention, we use a similar term as the variance to derive the first
high-probability $O(\log K)$ regret bound in this setting. Finally, we extend
our results to the setting of online linear regression.
- Abstract（参考訳）: 我々は,強い凸と有界損失に対する専門家の助言による予測を考察し,後悔と「ばらつき」のトレードオフ(学習者の予測と最高の専門家の予測の2乗差)を考察する。
K$の専門家は、EWA(Exponentially Weighted Average)アルゴリズムが$O(\log K)$ regretを達成することが知られている。
我々は、EWAの変種が負の後悔(すなわちアルゴリズムが最高の専門家より優れている)を達成するか、あるいは分散と後悔の両方に縛られる$O(\log K)$を保証することを証明している。
この結果をもとに,学習において予測のばらつきをどのように活用できるか,いくつかの例を示す。
オンラインからバッチ分析では、大規模な経験的分散により、オンラインからバッチへの変換が早期に停止し、クラスで最高の予測器のリスクを上回ることが示される。
また、早期停止を考慮しない場合、モデル選択集約の最適率を回復する。
損失の減少を伴うオンライン予測では, 後悔に対する腐敗の影響は大きなばらつきによって補償できることを示す。
オンライン選択的サンプリングでは,分散が大きくなるとサンプルを少なくし,期待に縛られる最適後悔を保証できるアルゴリズムを設計した。
禁忌を伴うオンライン学習では、この設定で最初の高い確率を持つ$O(\log K)$後悔を導き出すために、差分のような用語を用いる。
最後に、結果をオンライン線形回帰の設定に拡張する。
関連論文リスト
- Rejection via Learning Density Ratios [50.91522897152437]
拒絶による分類は、モデルを予測しないことを許容する学習パラダイムとして現れます。
そこで我々は,事前学習したモデルの性能を最大化する理想的なデータ分布を求める。
私たちのフレームワークは、クリーンでノイズの多いデータセットで実証的にテストされます。
論文 参考訳（メタデータ） (2024-05-29T01:32:17Z) - Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
本稿では,閾値演算による予測値がS$変化の程度を測るマージン補数の概念を導入する。
適切な因果仮定の下では、予測スコア$S$に対する$X$の影響は、真の結果$Y$に対する$X$の影響に等しいことを示す。
論文 参考訳（メタデータ） (2024-05-24T11:22:19Z) - Model-Based Epistemic Variance of Values for Risk-Aware Policy
Optimization [63.32053223422317]
モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。
特に、MDP上の分布によって誘導される値の分散を特徴付けることに焦点をあてる。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。
論文 参考訳（メタデータ） (2023-12-07T15:55:58Z) - No-Regret Learning with Unbounded Losses: The Case of Logarithmic
Pooling [12.933990572597583]
対数プール法(対数プール)として知られる基本的および実用的アグリゲーション法に焦点をあてる。
オンラインの対戦環境において,最適なパラメータ集合を学習する問題を考察する。
本稿では,O(sqrtT log T)$experied regretに達する方法で,専門家の重みを学習するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-22T22:27:25Z) - Can Q-Learning be Improved with Advice? [27.24260290748049]
本稿では,マルコフ決定過程(MDP)のオンライン学習において,後悔に対する最悪の下限を回避できるかどうかを論じる。
最適$Q$-値関数の予測が蒸留と呼ばれる合理的に弱い条件を満たす場合、状態-作用対の集合を、その予測が極端に不正確な状態-作用対の集合に置き換えることで、後悔境界を改善することができることを示す。
私たちの研究は、キャッシュやスケジューリングといった単純なオンライン問題に重点を置いていた予測を伴うアルゴリズムに関する最近の研究を、強化学習のより複雑で一般的な問題へと拡張しています。
論文 参考訳（メタデータ） (2021-10-25T15:44:20Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T19:08:53Z) - Online Multivalid Learning: Means, Moments, and Prediction Intervals [16.75129633574157]
本稿では,様々な意味で「多値」な文脈予測手法を提案する。
得られた見積もりは、単に限界ではなく、$ Y$ラベルのさまざまな統計を正しく予測します。
我々のアルゴリズムは逆選択の例を扱うので、任意の点予測法の残差の統計量を予測するのに等しく使用できる。
論文 参考訳（メタデータ） (2021-01-05T19:08:11Z) - Leveraging Predictions in Smoothed Online Convex Optimization via
Gradient-based Algorithms [18.64335888217192]
オンライン凸最適化は、時間的変化のあるステージコストと追加のスイッチングコストで検討する。
スイッチングコストはすべてのステージにカップリングをもたらすため、長期的な予測は品質の低下に悩まされる傾向がある。
本稿では,勾配に基づくオンラインアルゴリズムReceding Horizon Inexact Gradient (RHIG)を導入し,その性能を動的後悔によって解析する。
論文 参考訳（メタデータ） (2020-11-25T06:25:51Z) - Almost Tight L0-norm Certified Robustness of Top-k Predictions against
Adversarial Perturbations [78.23408201652984]
トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。
我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。
例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
論文 参考訳（メタデータ） (2020-11-15T21:34:44Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
2人の専門家と1人の予測者による予測問題を考える。
専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。
もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
論文 参考訳（メタデータ） (2020-03-18T20:12:08Z) - Debiased Off-Policy Evaluation for Recommendation Systems [8.63711086812655]
A/Bテストは信頼できるが、時間と費用がかかり、失敗のリスクが伴う。
提案手法は,履歴データに対するアルゴリズムの性能を推定する手法である。
提案手法は,最先端手法よりも平均2乗誤差が小さい。
論文 参考訳（メタデータ） (2020-02-20T02:30:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。