論文の概要: When Can Unlabeled Data Pools Replace Membership Queries?

• arxiv url: http://arxiv.org/abs/2610.41001v1
• Date: Thu, 29 Oct 2026 21:34:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.499235
• Title: When Can Unlabeled Data Pools Replace Membership Queries?
• Title（参考訳）: ラベルなしデータプールはいつメンバーシップクエリを置き換えることができるのか?
• Abstract要約: メンバシップクエリにより、学習者は任意のポイントをラベル付けし、ハーフスペースをすべてのマージンでほぼ最適に複雑にすることができる。 ラベルのないデータがメンバーシップクエリを置き換えることができるのかを問う。
• 参考スコア（独自算出の注目度）: 14.391648046717073
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Membership queries let a learner label arbitrary points and give near-optimal $\tilde O(n\log(1/\eps))$ label complexity for halfspaces under every marginal. A pool learner may label only sampled points. We ask when unlabeled data can replace membership queries. For homogeneous halfspaces the answer depends only on the angular law of $X/\|X\|$. If this law assigns zero mass to every hyperplane through the origin and positive mass to every nonempty open set of directions together with its reflection, a pool learner uses $O(n\log^3n\log(n/(\epsδ)))$ labels, uniformly over all such marginals and targets, without density, moment, concavity or isotropy assumptions. The same label bound holds for non-homogeneous halfspaces under every marginal with full support and no mass on affine hyperplanes, including Gaussians. Dropping either angular assumption admits $Ω(1/\eps)$ pool versus $O(\log(1/\eps))$ membership-query separations, even with unlimited unlabeled data. The price is paid in unlabeled data: in dimension $n\ge3$, for every unlabeled budget fixed in advance, some marginal satisfying both assumptions forces $Ω(1/\eps)$ labels. For isotropic $s$-concave marginals in dimension $n\ge3$, unlimited pools keep logarithmic label rates for every finite $s$. With an unlabeled budget fixed in advance, class-uniform polylogarithmic rates hold exactly for $s>-1/(n+1)$, or $s>-1/n$ under central symmetry, and in the general class the optimal rate between these thresholds is $\tildeΘ(\eps^{-(n-2)/n})$. This extends the range $s\ge-1/(2n+3)$ of previous sample-based guarantees, in the realizable setting.
• Abstract（参考訳）: メンバシップクエリは、学習者が任意のポイントをラベル付けし、ほぼ最適の$\tilde O(n\log(1/\eps))$ラベルの複雑さをすべてのマージンのハーフスペースで与えます。 プール学習者はサンプルポイントのみをラベル付けすることができる。 ラベルのないデータがメンバーシップクエリを置き換えることができるのかを問う。 等質半空間に対しては、解は$X/\|X\|$の角法則にのみ依存する。 この法則が原点と正の質量を通じてすべての超平面にゼロ質量を、その反射とともに空でないすべての方向のすべての進路に割り当てるなら、プール学習者は$O(n\log^3n\log(n/(\epsδ)))$ラベルを使い、密度、モーメント、共空性、等方性仮定を伴わずに、すべての限界と目標を均一に超える。 同じラベル境界は、すべての辺辺の非同次半空間に対して完全サポートを持ち、ガウスを含むアフィン超平面上の質量を持たない。 任意の角の仮定をドロップすると$Ω(1/\eps)$ pool対$O(\log(1/\eps))$ membership-query separationsが許容される。 原価は未定のデータで支払われる:次元$n\ge3$、事前に固定された全ての未定の予算に対して、両方の仮定を満たす限界額は$Ω(1/\eps)$ラベルを強制する。 isotropic $s$-concave marginals in dimension $n\ge3$,limited pools keep logarithmic label rate for every finite $s$。 前もってラベルなしの予算が固定された場合、クラスユニフォームの多元数レートは、ちょうど中心対称性の下で$s>-1/(n+1)$、または$s>-1/n$であり、一般的なクラスでは、これらのしきい値間の最適レートは$\tilde'(\eps^{-(n-2)/n})$である。 これにより、以前のサンプルベースの保証の$$s\ge-1/(2n+3)の範囲を、実現可能な設定で拡張できる。

関連論文リスト

• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck、Li、Nagarajは、一般的なデータでは、ノイズラベルに適合する$m$のニューロンを持つ任意の2層ニューラルネットワークは、リプシッツ定数を持つ必要があると推測した。 予想法則を1つの対数係数まで証明し、特にReLUネットワークにおいて連続的な片方向線形活性化を行う。
  論文  参考訳（メタデータ） (2026-07-08T17:44:15Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Active Learning of General Halfspaces: Label Queries vs Membership Queries [35.41111301965335]
  アクティブな学習者は、$tildeOmega(d/(log(m)epsilon)$というラベルの複雑さを必要とする。 クエリ複雑性が$tildeO(min1/p, 1/epsilon + dcdot polylog (1/epsilon))$$O(opt)+epsilon$のエラー保証を実現する。
  論文  参考訳（メタデータ） (2024-12-31T15:40:48Z)
• On a Near-Optimal \& Efficient Algorithm for the Sparse Pooled Data Problem [3.1591462359227136]
  プールされたデータ問題は、凝縮された測定値から、アイテムのセットの未知のラベルを特定するように要求する。 SIGMA$ の 0 でないエントリの数が $k sim ntheta$ for $theta in (0,1)$ である場合、プールされたデータ問題はスパース(sparse)と呼ぶ。 最も基本的な問題は、SIGMA$を高い確率で再構築しながら、できるだけ少数のプールを使用するプーリングスキームを設計することである。
  論文  参考訳（メタデータ） (2023-12-22T10:24:51Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。 当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise [4.8728183994912415]
  対比雑音を伴う$mathbbRd$の同質半空間のオンラインアクティブ学習について研究する。 私たちの主な貢献は、時間内で動作するパーセプトロンライクなアクティブラーニングアルゴリズムです。 アルゴリズムは、ほぼ最適ラベルの複雑さで基礎となるハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-12-19T22:04:10Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)

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

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