論文の概要: Memory Bounds for the Experts Problem

• arxiv url: http://arxiv.org/abs/2204.09837v1
• Date: Thu, 21 Apr 2022 01:22:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-23 02:53:44.098117
• Title: Memory Bounds for the Experts Problem
• Title（参考訳）: エキスパート問題のためのメモリ境界
• Authors: Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou
• Abstract要約: 専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。 目標は、予測を処理し、最小コストで予測を行うことです。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
• 参考スコア（独自算出の注目度）: 53.67419690563877
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online learning with expert advice is a fundamental problem of sequential prediction. In this problem, the algorithm has access to a set of $n$ "experts" who make predictions on each day. The goal on each day is to process these predictions, and make a prediction with the minimum cost. After making a prediction, the algorithm sees the actual outcome on that day, updates its state, and then moves on to the next day. An algorithm is judged by how well it does compared to the best expert in the set. The classical algorithm for this problem is the multiplicative weights algorithm. However, every application, to our knowledge, relies on storing weights for every expert, and uses $\Omega(n)$ memory. There is little work on understanding the memory required to solve the online learning with expert advice problem, or run standard sequential prediction algorithms, in natural streaming models, which is especially important when the number of experts, as well as the number of days on which the experts make predictions, is large. We initiate the study of the learning with expert advice problem in the streaming setting, and show lower and upper bounds. Our lower bound for i.i.d., random order, and adversarial order streams uses a reduction to a custom-built problem using a novel masking technique, to show a smooth trade-off for regret versus memory. Our upper bounds show novel ways to run standard sequential prediction algorithms in rounds on small "pools" of experts, thus reducing the necessary memory. For random-order streams, we show that our upper bound is tight up to low order terms. We hope that these results and techniques will have broad applications in online learning, and can inspire algorithms based on standard sequential prediction techniques, like multiplicative weights, for a wide range of other problems in the memory-constrained setting.
• Abstract（参考訳）: 専門家のアドバイスによるオンライン学習は、逐次予測の基本的な問題である。 この問題では、アルゴリズムは、毎日予測を行う「専門家」のセットにアクセスすることができる。 毎日の目標は、これらの予測を処理し、最小限のコストで予測することだ。 予測を行った後、アルゴリズムはその日の実際の結果を確認し、その状態を更新し、翌日に進む。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。 この問題の古典的なアルゴリズムは乗法重みアルゴリズムである。 しかし、私たちの知る限り、すべてのアプリケーションは、すべての専門家のために重みを格納し、$\omega(n)$メモリを使用する。 専門家が予測を行う日数だけでなく、専門家が予測を行う日数が大きい場合には、特に重要な自然ストリーミングモデルにおいて、専門家のアドバイスによるオンライン学習の解決や標準的な逐次予測アルゴリズムの実行に必要なメモリの理解に関する作業はほとんどない。 本研究は,ストリーミング環境におけるエキスパートアドバイス問題による学習を開始し,下限と上限を示す。 ランダム順序や逆順列に対する我々の低い境界は、新しいマスキング手法を用いてカスタム構築問題への還元を利用して、後悔と記憶のトレードオフを円滑に表す。 我々の上界は、専門家の小さな「プール」上で、標準的な逐次予測アルゴリズムを実行する新しい方法を示し、必要なメモリを減らす。 ランダムな順序列の場合、上界は低次項まで厳密であることが示される。 これらの結果と技術が、オンライン学習に広く応用され、メモリ制約のある設定における他の幅広い問題に対して、乗法重みのような標準的な逐次予測技術に基づくアルゴリズムを刺激できることを願っている。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Improved Frequency Estimation Algorithms with and without Predictions [22.382900492405938]
  データストリームに現れる要素の頻度を推定することは、大規模データ分析において重要なタスクである。 理論的には,Hsu等の学習に基づくアルゴリズムを,予測を使わずに上回る新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-12T18:59:06Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Online Paging with a Vanishing Regret [6.520803851931362]
  本稿では,オンラインアルゴリズムが複数の予測器にアクセスでき,ページ到着時刻の予測列を生成するオンラインページング問題の変種について考察する。 予測器は時折予測誤差を発生させ、そのうちの少なくとも1つが予測誤差のサブ線形数を生成すると仮定する。 この仮定は、最適オフラインアルゴリズムに対する時間平均後悔が無限大になる傾向にあるランダム化オンラインアルゴリズムの設計に十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-18T18:17:49Z)
• Malicious Experts versus the multiplicative weights algorithm in online prediction [85.62472761361107]
  2人の専門家と1人の予測者による予測問題を考える。 専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。 もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
  論文  参考訳（メタデータ） (2020-03-18T20:12:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。