論文の概要: A Complexity Measure for Active Learning in Multi-group Mean Estimation

• arxiv url: http://arxiv.org/abs/2606.14690v1
• Date: Fri, 12 Jun 2026 17:54:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-15 16:00:43.024671
• Title: A Complexity Measure for Active Learning in Multi-group Mean Estimation
• Title（参考訳）: 多群平均推定におけるアクティブラーニングのための複雑度測定
• Authors: Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub,
• Abstract要約: マルチグループ平均バンドレート$d$-armed banditsにおけるemphmax-riskによるアクティブラーニングの目的について検討した。 学習者は、最悪の不確実性指数を最小限に抑えるために、$d$グループ全体で$T$サンプルの予算を適応的に割り当てる。 滑らかなクラスに対しては、$mathrmVLC$ は分散-フィッシャー情報の再パラメータ化であり、共通族に対する閉形式値を持つ。
• 参考スコア（独自算出の注目度）: 8.550300650352732
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study a \emph{max-risk} objective for active learning in a multi-group mean estimation $d$-armed bandits: a learner adaptively allocates a budget of $T$ samples across $d$ groups to minimize the worst-case uncertainty index $\max_{k\in[d]}σ_k^2/n_k$, where $σ_k$ is the standard deviation of the distribution of arm $d$, and $n_k$ is the number of times arm $d$ is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the $\mathrm{VLC}$ is a reparametrization of a variance--Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced $\ell_1$ geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.
• Abstract（参考訳）: 学習者は、最悪のケースの不確実性指標である$\max_{k\in[d]}σ_k^2/n_k$を最小にするために、$d$グループ全体で$T$サンプルを適応的に割り当て、$σ_k$はアーム$d$の分布の標準偏差であり、$n_k$はアーム$d$の回数である。 局所的なミニマックスフレームワークを開発し、この目的に対する最初の一般下界を証明し、任意の有限分散仮説クラスに有効である。 境界は難易度を次の3つの直交因子に分類する: \emph{budget} 項、不確実性が腕に不均一に広がるかを測定する \emph{heteroscedasticity} 指数、モデル依存の複雑さ尺度である \emph{Variance Local Curvature} (\mathrm{VLC}$)。 滑らかなクラスに対しては、$\mathrm{VLC}$ は分散-フィッシャー情報の再パラメータ化であり、共通族に対する閉形式値を持つ。 最強の上限に対するベンチマークは、幅広い状況における対数的要因まで、ほぼ最適であることを示し、高度に異種なインスタンスにおいて、体系的なギャップを指摘している。 本証明では, 決定空間上の損失誘起$\ell_1$幾何と, 明示的ランダム行列計算にハードインスタンス構造を還元する表現型インスタンス生成器の2つの重要な要素を紹介する。

関連論文リスト

• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  不変学習は、構造が統計的に識別可能であっても失敗することがある。 ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。 合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
  論文  参考訳（メタデータ） (2026-06-11T05:49:43Z)
• Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model [28.636700996382558]
  敵のノイズに満ちた性質により、Efronのガウス的二群分数モデルにおいて、ヌル位置パラメータ$$に対する信頼区間を研究する。 信頼区間の最小最適長を、未知の割合の汚染と全てのノイズに満ちた敵に対して、所定のカバレッジレベルで特徴付ける。
  論文  参考訳（メタデータ） (2026-04-28T22:40:54Z)
• Robust Learning of a Group DRO Neuron [21.632698901872843]
  任意のラベルノイズと群レベルの分布シフトの存在下で,標準2乗損失下で原始ニューロンを学習する問題について検討した。 我々のフレームワークは、任意のラベルの破損やグループ固有の分布シフトに直面して、堅牢な学習保証を提供する。
  論文  参考訳（メタデータ） (2026-01-26T04:00:53Z)
• Locally minimax optimal confidence sets for the best model [40.60301522036206]
  この論文は基本的な推論問題に取り組む:$P$ over $mathbbRd$ が未知の平均$boldsymbolmu$ である場合、$boldsymbolmu$ の最小成分に対応する指数に対する信頼セットを形成する必要がある。 我々は$d$が$n$でスケールするか、および$boldsymbolmu$の任意の関係によらず、妥当性を維持する「次元に依存しない」テストを提案する。
  論文  参考訳（メタデータ） (2025-03-27T16:06:07Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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