論文の概要: Gaussian Partitioning for Reliable Learning of Multi-Index Models

• arxiv url: http://arxiv.org/abs/2611.05264v1
• Date: Tue, 03 Nov 2026 17:52:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-07 13:25:19.075224
• Title: Gaussian Partitioning for Reliable Learning of Multi-Index Models
• Title（参考訳）: マルチインデックスモデルの信頼性学習のためのガウス分割
• Abstract要約: ガウス的分割はガウス的分割に関してスムーズな分布のアルゴリズム的プリミティブである。 k$ハーフスペースの関数の場合、非依存的かつテスト可能な学習者は、この誤差依存を次元依存$dmathrmpoly(k/c)$で達成する。 固定滑らか性と正質量パラメータに対して、次元依存の$dO(log(k/)$と一致するSQ下界を持つ$k$半空間の交叉を学習する。
• 参考スコア（独自算出の注目度）: 40.887819183133224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce Gaussian partitioning, an algorithmic primitive for distributions smooth with respect to a Gaussian. It partitions space into polyhedral regions so that almost all mass lies in thin strips restricting a few orthogonal directions. Within each strip, the conditional distribution approximately matches low-degree Gaussian moments in the unrestricted directions. Our construction builds on logconcave partitioning of Diakonikolas, Kane, and Ma (FOCS 2026). Under input marginals smooth with respect to the standard Gaussian, we obtain agnostic learners with error $(1+c)\mathrm{opt}+ε$ for broad classes of Boolean multi-index models, including functions of halfspaces, low-dimensional convex concepts, and low-dimensional polynomial threshold functions. For functions of $k$ halfspaces, both agnostic and testable agnostic learners achieve this error with dimension dependence $d^{\mathrm{poly}(k/c)}$, improving the previous exponential dependence on $k/c$ in the agnostic exponent. For learning from positive examples with imperfect unlabeled data (PUI), we give algorithms and Statistical Query (SQ) lower bounds that qualitatively characterize complexity through Gaussian moment matching. For fixed smoothness and positive-mass parameters, we learn intersections of $k$ halfspaces with dimension dependence $d^{O(\log(k/ε))}$ and matching SQ lower bounds, improving the previous $d^{\mathrm{poly}(1/ε)}$ upper bound even for one halfspace. A general reduction from agnostic reliable learning to PUI yields negative reliable learners for these intersections with the same dimension dependence, for fixed smoothness. Finally, for PQ learning and testable learning with distribution shift, we prove qualitatively optimal SQ lower bounds of $d^{Ω(1/ε^2)}$, even for intersections of two halfspaces with Gaussian training data and arbitrary test distributions.
• Abstract（参考訳）: ガウス的分割はガウス的分割に関してスムーズな分布のアルゴリズム的プリミティブである。 空間を多面体領域に分割し、ほとんどすべての質量がいくつかの直交方向を制限する細い帯に置かれるようにしている。 各ストリップ内の条件分布は、制限されていない方向の低次ガウスモーメントとほぼ一致する。 本研究は,Diakonikolas, Kane, Ma (FOCS 2026) の対流圏分割を基盤として構築した。 標準ガウスに関してスムーズな入力境界の下では、半空間の関数、低次元凸概念、低次元多項式しきい値関数を含むブール多インデックスモデルの幅広いクラスに対して、誤差$(1+c)\mathrm{opt}+ε$ の無知学習者を得る。 k$ハーフスペースの関数に対して、非依存的およびテスト可能な非依存的学習者は、この誤差を次元依存性$d^{\mathrm{poly}(k/c)}$で達成し、非依存的指数における以前の$k/c$への指数的依存を改善した。 不完全なラベル付きデータ(PUI)を持つポジティブな例から学ぶために、ガウスモーメントマッチングを通じて複雑性を定性的に特徴づけるアルゴリズムと統計的クエリ(SQ)の下限を与える。 固定滑らか性と正質量パラメータに対して、次元依存を持つ$k$半空間の交叉を$d^{O(\log(k/ε))}$とマッチング SQ の下界を学習し、以前の$d^{\mathrm{poly}(1/ε)}$上界を1つの半空間でも改善する。 不可知的信頼学習からPUIへの一般的な還元は、これらの交点に対して同じ次元依存を持つ負の信頼学習者、固定的な滑らかさをもたらす。 最後に、分布シフトを伴うPQ学習およびテスト可能な学習において、ガウス的トレーニングデータと任意のテスト分布を持つ2つの半空間の交叉に対しても、$d^{Ω(1/ε^2)}$の質的に最適なSQ下界を証明した。

関連論文リスト

• Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs [43.317911105862756]
  ガウス分布の下では、$k$次数2のしきい値関数を$Rd$で学習するアルゴリズムを提案する。 我々の結果は、$k$であっても、正確性に依存しないパラメータ指数を得る最初のものである。
  論文  参考訳（メタデータ） (2026-11-03T16:05:15Z)
• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  半空間の平滑化学習の複雑性について,KM25のモデルにおける一様限界の下で検討した。
  論文  参考訳（メタデータ） (2026-05-04T08:53:40Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Statistical Query Lower Bounds for Smoothed Agnostic Learning [42.71001191804269]
  我々は,最近導入されたCKKMS24によるスムーズな学習の複雑さについて検討した。 具体的には、滑らかなモデルにおいて、ガウス分布の下で半空間を不可知的に学習することに焦点を当てる。
  論文  参考訳（メタデータ） (2026-02-24T18:46:46Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04: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)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
  本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。 下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
  論文  参考訳（メタデータ） (2022-02-10T15:34:10Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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