論文の概要: Actively Learning Halfspaces without Synthetic Data

• arxiv url: http://arxiv.org/abs/2509.20848v1
• Date: Thu, 25 Sep 2025 07:39:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-26 20:58:12.759311
• Title: Actively Learning Halfspaces without Synthetic Data
• Title（参考訳）: 合成データのない半空間をアクティブに学習する
• Authors: Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So,
• Abstract要約: 我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
• 参考スコア（独自算出の注目度）: 34.777547976926456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the classic point location problem, one is given an arbitrary dataset $X \subset \mathbb{R}^d$ of $n$ points with query access to an unknown halfspace $f : \mathbb{R}^d \to \{0,1\}$, and the goal is to learn the label of every point in $X$. This problem is extremely well-studied and a nearly-optimal $\widetilde{O}(d \log n)$ query algorithm is known due to Hopkins-Kane-Lovett-Mahajan (FOCS 2020). However, their algorithm is granted the power to query arbitrary points outside of $X$ (point synthesis), and in fact without this power there is an $\Omega(n)$ query lower bound due to Dasgupta (NeurIPS 2004). In this work our goal is to design efficient algorithms for learning halfspaces without point synthesis. To circumvent the $\Omega(n)$ lower bound, we consider learning halfspaces whose normal vectors come from a set of size $D$, and show tight bounds of $\Theta(D + \log n)$. As a corollary, we obtain an optimal $O(d + \log n)$ query deterministic learner for axis-aligned halfspaces, closing a previous gap of $O(d \log n)$ vs. $\Omega(d + \log n)$. In fact, our algorithm solves the more general problem of learning a Boolean function $f$ over $n$ elements which is monotone under at least one of $D$ provided orderings. Our technical insight is to exploit the structure in these orderings to perform a binary search in parallel rather than considering each ordering sequentially, and we believe our approach may be of broader interest. Furthermore, we use our exact learning algorithm to obtain nearly optimal algorithms for PAC-learning. We show that $O(\min(D + \log(1/\varepsilon), 1/\varepsilon) \cdot \log D)$ queries suffice to learn $f$ within error $\varepsilon$, even in a setting when $f$ can be adversarially corrupted on a $c\varepsilon$-fraction of points, for a sufficiently small constant $c$. This bound is optimal up to a $\log D$ factor, including in the realizable setting.
• Abstract（参考訳）: 古典的な点位置問題では、未知の半空間 $f : \mathbb{R}^d \to \{0,1\}$ へのクエリアクセスを持つ任意のデータセット $X \subset \mathbb{R}^d$ が与えられる。 この問題は極めてよく研究されており、Hopkins-Kane-Lovett-Mahajan (FOCS 2020)により、ほぼ最適の$\widetilde{O}(d \log n)$クエリアルゴリズムが知られている。 しかし、それらのアルゴリズムは、$X$(ポイント合成)以外の任意の点を問合せする権限が与えられており、実際には、Dasgupta (NeurIPS 2004) による$\Omega(n)$の問合せ下界が存在する。 この研究の目的は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計することである。 下界の$\Omega(n)$を回避するために、通常のベクトルが$D$の集合から来る学習半空間について検討し、$\Theta(D + \log n)$の厳密な境界を示す。 コーナリーとして、軸方向の半空間に対して最適な$O(d + \log n)$クエリ決定論的学習者を取得し、$O(d \log n)$ vs. $\Omega(d + \log n)$のギャップを閉じる。 実際、我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。 我々の技術的洞察は、それぞれの順序を逐次的に考慮するのではなく、これらの順序の構造を利用してバイナリ検索を並列に行うことであり、我々のアプローチはより広い関心を持つ可能性があると信じている。 さらに,我々は,PAC学習のためのほぼ最適なアルゴリズムを得るために,正確な学習アルゴリズムを用いた。 O(\min(D + \log(1/\varepsilon), 1/\varepsilon) \cdot \log D)$ query suffice to learn $f$ within error $\varepsilon$, in a setting if $f$ can be adversarially derupted on a $c\varepsilon$-fraction of point, for a enough small constant $c$。 この境界は、実現可能な設定を含む$\log D$ factorまで最適である。

関連論文リスト

• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Almost Tight Approximation Algorithms for Explainable Clustering [16.22135057266913]
  本稿では,Dasguptaらによって提案された最近の説明可能なクラスタリングの枠組みについて考察する。 具体的には、$k$-meansと$k$-mediansの問題に焦点をあて、ほぼ上と下の境界を提供する。
  論文  参考訳（メタデータ） (2021-07-01T23:49:23Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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