論文の概要: Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

• arxiv url: http://arxiv.org/abs/2605.27594v1
• Date: Tue, 26 May 2026 19:07:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-28 17:38:55.472179
• Title: Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals
• Title（参考訳）: ガウス行列による半空間関数の固有学習
• Authors: Sergei Tikhonov, Arsen Vasilyan,
• Abstract要約: i.d.ラベル付きサンプルが$mathbbRd times pm 1$上の未知の分布からサンプリングされ、$mathbbRd$がガウシアンであることを考えると、目標はターゲットクラス$mathcalF$から仮説を出力することである。 我々のアルゴリズムは、$dO(K2 log (1/)/2) + (K/)O(K) で実行されます。
• 参考スコア（独自算出の注目度）: 5.7652356955571085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over $\mathbb{R}^d \times \{\pm 1\}$ whose marginal on $\mathbb{R}^d$ is Gaussian, the goal is to output a hypothesis from a target class $\mathcal{F}$ whose 0-1 loss is within $ε$ of that of the best classifier in $\mathcal{F}$. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of $K$ halfspaces under Gaussian marginals. Our algorithm runs in time $d^{O(K^2 \log(1/ε)/ε^2)} + (K/ε)^{O(K^3/ε^{2.5})}$. Prior to our work, the only known algorithm for $K \geq 2$ was brute-force search, with run-time exponential in $d$. Moreover, the dependence of our run-time on the dimension $d$ matches that of the best known improper learning algorithm, namely $d^{\widetilde{O}(K^2/ε^2)}$. For the special case of a single halfspace ($K=1$), the best previous run-time was $d^{O(1/ε^4)} + (1/ε)^{O(1/ε^6)}$. Our algorithm improves this to $d^{O(1/ε^2)} + (1/ε)^{O(1/ε^{2.5})}$. Once again, the dependence on $d$ matches that of the best known improper algorithm, namely $d^{O(1/ε^2)}$. Furthermore, the dependence of our run-time on the dimension $d$ is essentially optimal in the statistical query model.
• Abstract（参考訳）: ガウス分布に基づく多次元概念クラスの計算効率の良い固有非依存学習問題について検討する。 この設定では、例えば、$\mathbb{R}^d \times \{\pm 1\}$ 上の未知の分布からサンプルをラベル付けし、$\mathbb{R}^d$ がガウスであるなら、目的クラス $\mathcal{F}$ から仮説を出力することである。 ガウス境界の下では、任意のブール関数に対して、K$半空間の任意のブール関数に対して、最初の効率的な固有非依存学習アルゴリズムを与える。 我々のアルゴリズムは時間$d^{O(K^2 \log(1/ε)/ε^2)} + (K/ε)^{O(K^3/ε^{2.5})}$で実行される。 我々の研究に先立ち、$K \geq 2$の唯一の既知のアルゴリズムはブルートフォース検索であり、実行時の指数は$d$であった。 さらに、我々の実行時間の次元$d$依存性は、最もよく知られた不適切な学習アルゴリズムである$d^{\widetilde{O}(K^2/ε^2)}$と一致する。 1つのハーフスペース(K=1$)の特別な場合、最前の実行時間は$d^{O(1/ε^4)} + (1/ε)^{O(1/ε^6)}$である。 我々のアルゴリズムはこれを$d^{O(1/ε^2)} + (1/ε)^{O(1/ε^{2.5})}$に改善する。 繰り返しになるが、$d$への依存は最もよく知られた不適切なアルゴリズム、すなわち$d^{O(1/ε^2)}$と一致する。 さらに,次元$d$に対する実行時間の依存性は,統計的クエリモデルにおいて本質的に最適である。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
  シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。 適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
  論文  参考訳（メタデータ） (2024-11-08T17:10:38Z)
• Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
  本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。 我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
  論文  参考訳（メタデータ） (2024-10-02T15:21:07Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals [43.0867217287089]
  ガウス分布の下で半空間を不可知的に学習する作業について検討する。 この課題に対して,ほぼ最適計算硬度を証明した。
  論文  参考訳（メタデータ） (2023-02-13T16:46:23Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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