論文の概要: Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust
- arxiv url: http://arxiv.org/abs/2303.01709v1
- Date: Fri, 3 Mar 2023 04:39:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 16:10:41.177452
- Title: Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust
- Title（参考訳）: エキスパートによる学習のためのストリーミングアルゴリズム:決定論的Versus Robust
- Authors: David P. Woodruff, Fred Zhang, Samson Zhou
- Abstract要約: エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
- 参考スコア（独自算出の注目度）: 62.98860182111096
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the online learning with experts problem, an algorithm must make a
prediction about an outcome on each of $T$ days (or times), given a set of $n$
experts who make predictions on each day (or time). The algorithm is given
feedback on the outcomes of each day, including the cost of its prediction and
the cost of the expert predictions, and the goal is to make a prediction with
the minimum cost, specifically compared to the best expert in the set. Recent
work by Srinivas, Woodruff, Xu, and Zhou (STOC 2022) introduced the study of
the online learning with experts problem under memory constraints.
However, often the predictions made by experts or algorithms at some time
influence future outcomes, so that the input is adaptively chosen. Whereas
deterministic algorithms would be robust to adaptive inputs, existing
algorithms all crucially use randomization to sample a small number of experts.
In this paper, we study deterministic and robust algorithms for the experts
problem. We first show a space lower bound of
$\widetilde{\Omega}\left(\frac{nM}{RT}\right)$ for any deterministic algorithm
that achieves regret $R$ when the best expert makes $M$ mistakes. Our result
shows that the natural deterministic algorithm, which iterates through pools of
experts until each expert in the pool has erred, is optimal up to
polylogarithmic factors. On the positive side, we give a randomized algorithm
that is robust to adaptive inputs that uses
$\widetilde{O}\left(\frac{n}{R\sqrt{T}}\right)$ space for $M=O\left(\frac{R^2
T}{\log^2 n}\right)$, thereby showing a smooth space-regret trade-off.
- Abstract（参考訳）: 専門家によるオンライン学習問題において、アルゴリズムは、毎日(または時間)に予測を行う1組のn$専門家に対して、t$日(または時間)ごとに結果を予測しなければならない。
アルゴリズムは、予測のコストと専門家予測のコストを含む、各日の成果に対するフィードバックを与え、その目標は、特にセットの最高の専門家と比較して、最小のコストで予測を行うことである。
Srinivas、Woodruff、Xu、Zhou(STOC 2022)による最近の研究は、専門家によるオンライン学習の研究をメモリ制約下で導入した。
しかし、しばしば専門家やアルゴリズムによる予測が将来の結果に影響を与え、入力が適応的に選択される。
決定論的アルゴリズムは適応入力に頑健であるが、既存のアルゴリズムはすべてランダム化を使って少数の専門家をサンプリングしている。
本稿では,専門家問題に対する決定論的およびロバストなアルゴリズムについて検討する。
まず、最善のエキスパートが$m$の間違いをしたときの後悔$r$を達成する決定論的アルゴリズムに対して、$\widetilde{\omega}\left(\frac{nm}{rt}\right)$の空間下限を示す。
その結果,プール内の各専門家が誤認するまで専門家のプールを通じて繰り返す自然決定論的アルゴリズムは,多対数因子に最適であることが判明した。
正の面では、$\widetilde{o}\left(\frac{n}{r\sqrt{t}}\right)$空間 for $m=o\left(\frac{r^2 t}{\log^2 n}\right)$を使用する適応入力にロバストなランダム化アルゴリズムを与える。
関連論文リスト
- Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。
この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。
我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
論文 参考訳（メタデータ） (2024-05-06T17:38:20Z) - No-Regret Online Prediction with Strategic Experts [16.54912614895861]
オンラインバイナリ予測の一般化をエキスパートアドバイスフレームワークを用いて研究し、各ラウンドで、学習者は、Kドルの専門家のプールからmgeq 1ドルの専門家を選ぶことができる。
我々は、専門家が戦略的に行動し、彼らの信念を誤報することでアルゴリズムの予測への影響を最大化することを目的とした設定に焦点を当てる。
目標は,次の2つの要件を満たすアルゴリズムを設計することです。 1) $textitIncentive-compatible$: 専門家に信念を真実に報告させるインセンティブ,2) $textitNo-regret$: Achieve。
論文 参考訳（メタデータ） (2023-05-24T16:43:21Z) - Memory Bounds for the Experts Problem [53.67419690563877]
専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。
目標は、予測を処理し、最小コストで予測を行うことです。
アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
論文 参考訳（メタデータ） (2022-04-21T01:22:18Z) - Efficient and Optimal Fixed-Time Regret with Two Experts [5.650647159993238]
専門家のアドバイスによる予測は、オンライン学習における基礎的な問題である。
T$のラウンドと$n$のエキスパートを持つ場合、古典的な乗法的重み更新法は、$T$が事前に知られているときに、少なくとも$sqrt(T/2)ln n$の後悔を被る。
専門家が$n$の数が小さい/固定された場合、より後悔する保証のあるアルゴリズムが存在する。
論文 参考訳（メタデータ） (2022-03-15T01:07:09Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Impossible Tuning Made Possible: A New Expert Algorithm and Its
Applications [37.6975819766632]
我々は、すべてのエキスパート$i$に対して、後悔の$Oleft(sqrt(ln d)sum_t ell_t,i2right)を同時に$T$ラウンド$d$-expert問題で達成できることを示します。
本アルゴリズムは,補正項と重み付きエントロピー正規化器を備えたミラー・ディキストリアル・フレームワークに基づいている。
論文 参考訳（メタデータ） (2021-02-01T18:34:21Z) - Malicious Experts versus the multiplicative weights algorithm in online
prediction [85.62472761361107]
2人の専門家と1人の予測者による予測問題を考える。
専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。
もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
論文 参考訳（メタデータ） (2020-03-18T20:12:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。