論文の概要: Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
- arxiv url: http://arxiv.org/abs/2604.26446v1
- Date: Wed, 29 Apr 2026 09:00:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-30 15:59:36.322175
- Title: Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
- Title（参考訳）: ガウスマルジナルスにおける均質半空間を用いた学習のほぼ最適暗号ハードネス
- Authors: Jizhou Huang, Brendan Juba,
- Abstract要約: ガウス分布の下での等質半空間の同定に関わる3つの問題について検討する。
それぞれの問題の目標は、その対応する損失測度の観点から最も適した等質半空間にアプローチする等質半空間を出力することである。
本研究では,これらの問題に対して,Learning With Errors (LWE) 問題の広く信じられている硬さ仮定の下で,ほぼ最適計算硬度を求める。
- 参考スコア（独自算出の注目度）: 21.00905771355709
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each of these problems, we are given labeled examples $(\mathbf{x}, \mathrm{y})$ drawn from an unknown distribution on $\mathbb{R}^d\times\{-1, +1\}$, whose marginal distribution on $\mathbf{x}$ is standard Gaussian and on $\mathrm{y}$ is arbitrary. The goal of each problem is to output a homogeneous halfspace that approaches the best-fitting homogeneous halfspace in terms of its corresponding loss measure. We prove near-optimal computational hardness results for these problems under the widely believed hardness assumption of the Learning With Errors (LWE) problem. Prior hardness results for these problems were mostly established for general halfspaces; our findings extend some of these hardness results to homogeneous halfspaces. Remarkably, our lower bound strictly generalizes over prior works and narrows the gap between the upper and lower bounds for agnostically learning homogeneous halfspaces under Gaussian marginals.
- Abstract（参考訳）: 本研究では,ガウス分布下での同種半空間の同定に関わる3つの問題について検討する。
これらの問題のそれぞれにおいて、ラベル付き例 $(\mathbf{x}, \mathrm{y})$ は、$\mathbb{R}^d\times\{-1, +1\}$ 上の未知の分布から引き出されるが、$\mathbf{x}$ 上の辺分布は標準ガウスであり、$\mathrm{y}$ は任意である。
それぞれの問題の目標は、その対応する損失測度の観点から最も適した等質半空間にアプローチする等質半空間を出力することである。
本研究では,これらの問題に対して,Learning With Errors (LWE) 問題の広く信じられている硬さ仮定の下で,ほぼ最適計算硬度を求める。
これらの問題に対する先行硬度結果は主に一般半空間に対して確立され、我々の発見はこれらの硬度結果の一部を均質半空間に拡張した。
顕著なことに、我々の下界は事前の作業に対して厳密に一般化し、ガウス境界の下で同質半空間を不可知的に学習するために上界と下界の間のギャップを狭める。
関連論文リスト
- Testable Learning of General Halfspaces under Massart Noise [40.15176310729312]
ガウス分布の下で一般マスアート半空間を実証的に学習するアルゴリズム的タスクについて検討する。
テスト可能な学習環境では、以下の特性を満たすテスター-ラーナーペアの設計が目的である。
我々の主な成果は、Massartノイズと限界を持つ一般半空間に対する最初のテスト可能な学習アルゴリズムである。
論文 参考訳（メタデータ） (2026-02-25T18:30:10Z) - Improved Hardness Results for Learning Intersections of Halfspaces [2.1393480341554736]
不適切な設定でハーフ空間の弱学習交差点に対して、強い(そして驚くほど単純な)下界を示す。
我々は、$omega(log log N)$ halfspaces を$N$で学習しても超多項式時間を要することを示すことで、このギャップを著しく狭めている。
具体的には、次元$N$の任意の$k$ハーフスペースに対して、精度$N-Omega(k)$、指数関数的に多くのクエリが必要であることを示す。
論文 参考訳（メタデータ） (2024-02-25T05:26:35Z) - 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) - Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals [43.0867217287089]
ガウス分布の下で半空間を不可知的に学習する作業について検討する。
この課題に対して,ほぼ最適計算硬度を証明した。
論文 参考訳（メタデータ） (2023-02-13T16:46:23Z) - Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
ガウスの下の半空間を不可知的に学習する問題を考察する。
我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
論文 参考訳（メタデータ） (2021-02-10T18:40:44Z) - Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins [92.7662890047311]
勾配降下は、分類誤差$tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
論文 参考訳（メタデータ） (2020-10-01T16:48:33Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
分布固有モデルにおいて,同種半空間の学習を代理する問題に対する解を示す。
任意の凸分布において、誤分類誤差は本質的にハーフスペースの誤分類誤差につながることを示す。
論文 参考訳（メタデータ） (2020-06-11T18:55:59Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Learning Halfspaces with Massart Noise Under Structured Distributions [46.37328271312332]
分布特異的PACモデルにおいて,マスアートノイズを伴う学習空間の問題を解く。
対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対
論文 参考訳（メタデータ） (2020-02-13T17:02:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。