論文の概要: Learning Intersections of Two Margin Halfspaces under Factorizable Distributions

• arxiv url: http://arxiv.org/abs/2511.09832v2
• Date: Sun, 16 Nov 2025 19:17:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:22.402974
• Title: Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
• Title（参考訳）: 因子分布下での2つの有理半空間の学習断面積
• Authors: Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, Christos Tzamos,
• Abstract要約: ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 56.51474048985742
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning intersections of halfspaces is a central problem in Computational Learning Theory. Even for just two halfspaces, it remains a major open question whether learning is possible in polynomial time with respect to the margin $γ$ of the data points and their dimensionality $d$. The best-known algorithms run in quasi-polynomial time $d^{O(\log(1/γ))}$, and it has been shown that this complexity is unavoidable for any algorithm relying solely on correlational statistical queries (CSQ). In this work, we introduce a novel algorithm that provably circumvents the CSQ hardness barrier. Our approach applies to a broad class of distributions satisfying a natural, previously studied, factorizability assumption. Factorizable distributions lie between distribution-specific and distribution-free settings, and significantly extend previously known tractable cases. Under these distributions, we show that CSQ-based methods still require quasipolynomial time even for weakly learning, whereas our algorithm achieves $poly(d,1/γ)$ time by leveraging more general statistical queries (SQ), establishing a strong separation between CSQ and SQ for this simple realizable PAC learning problem. Our result is grounded in a rigorous analysis utilizing a novel duality framework that characterizes the moment tensor structure induced by the marginal distributions. Building on these structural insights, we propose new, efficient learning algorithms. These algorithms combine a refined variant of Jennrich's Algorithm with PCA over random projections of the moment tensor, along with a gradient-descent-based non-convex optimization framework.
• Abstract（参考訳）: ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフ空間であっても、データポイントのマージン$γ$とそれらの次元$d$に関して、多項式時間で学習が可能であるかどうかという大きな未解決の問題である。 最もよく知られたアルゴリズムは準多項式時間$d^{O(\log(1/γ))}$で動作し、相関統計クエリ(CSQ)のみに依存するアルゴリズムでは、この複雑さは避けられないことが示されている。 本研究ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。 我々のアプローチは、自然で以前に研究された分解可能性の仮定を満たす広範な分布のクラスに適用できる。 分解可能な分布は、分布固有の設定と分布のない設定の間にあり、これまで知られていた抽出可能なケースを著しく拡張する。 これらの分布下では、CSQに基づく手法は弱い学習でも準多項式時間を必要とするが、我々のアルゴリズムはより一般的な統計的クエリ(SQ)を活用して$poly(d,1/γ)$ timeを達成し、この単純な実現可能なPAC学習問題に対してCSQとSQの強い分離を確立する。 この結果は,境界分布によって引き起こされるモーメントテンソル構造を特徴付ける,新しい双対性フレームワークを用いた厳密な解析に基礎を置いている。 これらの構造的洞察に基づいて、我々は新しい効率的な学習アルゴリズムを提案する。 これらのアルゴリズムは、勾配差に基づく非凸最適化フレームワークとともに、モーメントテンソルのランダムなプロジェクションの上に、イェンリッヒのアルゴリズムの洗練された変種とPCAを組み合わせたものである。

関連論文リスト

• New Statistical and Computational Results for Learning Junta Distributions [0.38073142980733]
  我々は、$k$-junta分布の学習は、ノイズを伴う$k$-parity関数の学習と等価であることを示す。 統計的複雑性が最適であるユンタ分布を学習するためのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2025-05-09T06:44:35Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
  所望のテレビ距離内において,$d$次元空間にマージンを持つ高次元半空間を学習するためのガウス時間アルゴリズムを提案する。 我々のアルゴリズムはラベルを必要とせず、隠れたハーフスペースのユニークな(そして効率的な)識別性を確立する。 超ポリノミカルな既存のモーメントバウンド保証の代わりに、トータル変分(TV)距離に基づくポリタイム保証を提供することにより、この問題を改善する。
  論文  参考訳（メタデータ） (2023-11-02T17:51:10Z)
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
  本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。 一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
  論文  参考訳（メタデータ） (2023-05-28T19:40:46Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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