論文の概要: Fast Rates for Online Prediction with Abstention
- arxiv url: http://arxiv.org/abs/2001.10623v2
- Date: Sat, 20 Jun 2020 19:07:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-06 02:23:11.643316
- Title: Fast Rates for Online Prediction with Abstention
- Title（参考訳）: 注意を伴うオンライン予測の高速化
- Authors: Gergely Neu and Nikita Zhivotovskiy
- Abstract要約: 学習者が$frac 12$よりも極端に小額の費用を支払うことによって予測を控えることによって、時間的地平から独立して期待される後悔の限界を達成できることが示される。
また,留置コストの順序が時間とともに任意に変化するような設定を含む,モデルのさまざまな拡張についても論じる。
- 参考スコア（独自算出の注目度）: 15.99072005190786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the setting of sequential prediction of individual $\{0, 1\}$-sequences
with expert advice, we show that by allowing the learner to abstain from the
prediction by paying a cost marginally smaller than $\frac 12$ (say, $0.49$),
it is possible to achieve expected regret bounds that are independent of the
time horizon $T$. We exactly characterize the dependence on the abstention cost
$c$ and the number of experts $N$ by providing matching upper and lower bounds
of order $\frac{\log N}{1-2c}$, which is to be contrasted with the best
possible rate of $\sqrt{T\log N}$ that is available without the option to
abstain. We also discuss various extensions of our model, including a setting
where the sequence of abstention costs can change arbitrarily over time, where
we show regret bounds interpolating between the slow and the fast rates
mentioned above, under some natural assumptions on the sequence of abstention
costs.
- Abstract（参考訳）: 個別の$\{0, 1\}$-sequencesを専門家の助言で逐次予測すると、学習者が$\frac 12$(例えば$0.49$)よりも極端に小額の費用を支払うことで、予測から退避することを許すことにより、時間的地平線から独立して期待される後悔の限界を達成できることが示される。
我々は、棄却コスト$c$ とエキスパート数 $n$ の依存性を正確に特徴付けし、オプションを使わずに使用可能な$\sqrt{t\log n}$ の最高のレートと対照的な$\frac{\log n}{1-2c}$ のオーダーの上下境界を提供する。
また, 本モデルの様々な拡張についても検討し, 回避コストの列が時間とともに任意に変化するような設定についても検討し, 回避コスト列の自然な仮定の下で, 上記のスローレートと高速レートの間を補間する後悔の限界を示す。
関連論文リスト
- Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with
Application to Fairness [1.6741394365746018]
我々は,各ラウンドにおいてスカラー報酬が得られ,ベクトル値のコストがかかる問題であるknapsacks[CBwK]のコンテキスト的帯域幅問題を考える。
予測段階更新に基づく二元的戦略を導入し,多元対数項まで$sqrtT$の総コスト制約を扱えるようにした。
論文 参考訳（メタデータ） (2023-05-25T07:41:35Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳（メタデータ） (2022-05-02T08:48:22Z) - On Dynamic Pricing with Covariates [6.6543199581017625]
UCBとThompsonのサンプリングに基づく価格設定アルゴリズムは、$O(dsqrtTlog T)$ regret upper boundを実現できることを示す。
私たちの後悔に対する上限は、対数的要因までの下位境界と一致します。
論文 参考訳（メタデータ） (2021-12-25T16:30:13Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳（メタデータ） (2021-04-22T17:20:48Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳（メタデータ） (2021-01-31T16:17:56Z) - Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed
Rewards [24.983866845065926]
我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。
本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。
提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
論文 参考訳（メタデータ） (2020-10-24T10:44:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。