論文の概要: Oracle Efficient Algorithms for Groupwise Regret

• arxiv url: http://arxiv.org/abs/2310.04652v1
• Date: Sat, 7 Oct 2023 02:17:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-12 16:57:19.947898
• Title: Oracle Efficient Algorithms for Groupwise Regret
• Title（参考訳）: グループワイドレグレットのためのOracleの効率的なアルゴリズム
• Authors: Krishna Acharya, Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, Juba Ziani
• Abstract要約: 睡眠専門家によるBlum & Lykouris(Blum & Lykouris)の簡易な修正は、外的後悔不在集団の考慮を減らし、よく理解された問題に効果的に還元できることを示す。 グループ間で一様に比較すると,従来のオンライン線形回帰アルゴリズムに比べ誤差が大幅に改善され,グループ的に反省する保証がないことがわかった。
• 参考スコア（独自算出の注目度）: 7.840453701379554
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of online prediction, in which at each time step $t$, an individual $x_t$ arrives, whose label we must predict. Each individual is associated with various groups, defined based on their features such as age, sex, race etc., which may intersect. Our goal is to make predictions that have regret guarantees not just overall but also simultaneously on each sub-sequence comprised of the members of any single group. Previous work such as [Blum & Lykouris] and [Lee et al] provide attractive regret guarantees for these problems; however, these are computationally intractable on large model classes. We show that a simple modification of the sleeping experts technique of [Blum & Lykouris] yields an efficient reduction to the well-understood problem of obtaining diminishing external regret absent group considerations. Our approach gives similar regret guarantees compared to [Blum & Lykouris]; however, we run in time linear in the number of groups, and are oracle-efficient in the hypothesis class. This in particular implies that our algorithm is efficient whenever the number of groups is polynomially bounded and the external-regret problem can be solved efficiently, an improvement on [Blum & Lykouris]'s stronger condition that the model class must be small. Our approach can handle online linear regression and online combinatorial optimization problems like online shortest paths. Beyond providing theoretical regret bounds, we evaluate this algorithm with an extensive set of experiments on synthetic data and on two real data sets -- Medical costs and the Adult income dataset, both instantiated with intersecting groups defined in terms of race, sex, and other demographic characteristics. We find that uniformly across groups, our algorithm gives substantial error improvements compared to running a standard online linear regression algorithm with no groupwise regret guarantees.
• Abstract（参考訳）: 我々はオンライン予測の問題を調査し、各ステップ$t$で個々の$x_t$が到着し、そのラベルを予測しなければならない。 各個人は、年齢、性別、人種などの特徴に基づいて定義された様々なグループに関連付けられ、交差する可能性がある。 私たちの目標は、全体だけでなく、すべてのグループのメンバーで構成される各サブシーケンス上でも、後悔の保証を持つ予測を行うことです。 以前の [blum & lykouris] や [lee et al] のような研究は、これらの問題に対して魅力的な後悔の保証を提供しているが、大きなモデルクラスでは計算上は役に立たない。 睡眠専門家によるBlum & Lykouris(Blum & Lykouris)の簡易な修正は,外的後悔欠席集団の考慮を減らし,よく理解された問題に効果的に還元できることを示す。 提案手法は, [Blum & Lykouris] と比較して, 同様の後悔の保証を与えるが, 群数では時間線型であり, 仮説クラスではオラクル効率がよい。 特に、このアルゴリズムは、群数が多項式的に有界であり、外部回帰問題を効率的に解くことができ、モデルクラスが小さくなければならないという[Blum & Lykouris]の強い条件を改善することを示唆している。 この手法はオンライン線形回帰問題やオンライン最短経路などのオンライン組合せ最適化問題を扱うことができる。 このアルゴリズムは, 理論上の後悔点の他に, 合成データと2つの実データ -- 医療費と成人所得データセット -- に関して, 人種, 性別, その他の人口統計学的特徴の観点から定義された交差するグループでインスタンス化されている。 グループ間で一様になるアルゴリズムは、グループ毎の後悔のない標準的なオンライン線形回帰アルゴリズムよりもエラーをかなり改善できることがわかった。

関連論文リスト

• Group-wise oracle-efficient algorithms for online multi-group learning [12.664869982542895]
  本研究では,オンライン学習者が,集団の系列に対応するサブシーケンスの集合に対して,小さな予測後悔を同時に達成しなければならない学習モデルである,オンライン多群学習の課題について検討する。 本稿では, 逆数および逆数変換の設定を含む, 種々の条件下で, サブ線形後悔を伴うオラクル効率のアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-06-07T23:00:02Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• Multicalibrated Regression for Downstream Fairness [17.084765209458762]
  我々は、回帰関数 $hatf$ を適切にマルチキャリブレーションした'' を取り、効率的に後処理する方法を示します。 後処理はラベル付きデータを必要としない。
  論文  参考訳（メタデータ） (2022-09-15T14:16:01Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。 一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
  論文  参考訳（メタデータ） (2022-05-25T21:31:36Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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