論文の概要: A Fine-Grained Understanding of Uniform Convergence for Halfspaces

• arxiv url: http://arxiv.org/abs/2605.06004v1
• Date: Thu, 07 May 2026 10:53:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-08 22:27:11.708017
• Title: A Fine-Grained Understanding of Uniform Convergence for Halfspaces
• Title（参考訳）: 半空間に対する一様収束の微積分的理解
• Authors: Aryeh Kontorovich, Kasper Green Larsen,
• Abstract要約: 最悪のVC境界を超えたハーフスペースの微細な均一収束挙動について検討する。 $dge 2$ の $mathbbRd$ の非同次半空間に対して、標準一階VC境界は本質的に強であることを示す。 対照的に$mathbbR2$の同質半空間は明らかに異なる振る舞いを示す。
• 参考スコア（独自算出の注目度）: 31.579168044707462
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the fine-grained uniform convergence behavior of halfspaces beyond worst-case VC bounds. For inhomogeneous halfspaces in $\mathbb{R}^d$ with $d\ge 2$, we show that standard first-order VC bounds are essentially tight: even consistent hypotheses can incur population error $Θ(d\ln(n/d)/n)$, and in the agnostic setting the deviation scales as $\sqrt{τ\ln(1/τ)}$ at true error $τ$. In contrast, homogeneous halfspaces in $\mathbb{R}^2$ exhibit a markedly different behavior. In the realizable case, every hypothesis consistent with the sample has error $O(1/n)$. In the agnostic case, we prove a bandwise, log-free deviation bound on each dyadic risk band via a critical-wedge localization argument. Unioning over bands incurs only a $\ln\ln n$ overhead, and we establish a matching lower bound showing this overhead is unavoidable. Together, these results give a fine-grained and nearly complete picture of uniform convergence for halfspaces, revealing sharp dimensional and structural thresholds.
• Abstract（参考訳）: 最悪のVC境界を超えたハーフスペースの微細な均一収束挙動について検討する。 例えば、$\mathbb{R}^d$ と $d\ge 2$ の非同次半空間に対して、標準的な一階VC境界は本質的にタイトであることが示される: 一貫性のある仮説でさえ、集団誤差を$\(d\ln(n/d)/n)$ とすることができるし、無知の設定では、偏差スケールを$\sqrt{τ\ln(1/τ)}$ として真誤差で$τ$ とすることができる。 対照的に、$\mathbb{R}^2$ の同質半空間は明らかに異なる振る舞いを示す。 実現可能な場合、サンプルと一致するすべての仮説は、エラー$O(1/n)$を持つ。 不可知の場合,各ダイアドリスクバンドに有界な帯域幅の対数自由な偏差を臨界ウェッジの局所化の議論を通じて証明する。 バンド上の結合は$\ln\ln n$オーバーヘッドしか発生せず、このオーバーヘッドを示す一致した下界を確立することは避けられない。 これらの結果は、ハーフ空間に対する一様収束の微細でほぼ完全な図形を与え、鋭い次元と構造的しきい値を示す。

関連論文リスト

• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
  我々は, citetKM25 モデルにおける一様分布の下で, 半空間を 1n$ で滑らかに学習する複雑性について検討した。
  論文  参考訳（メタデータ） (2026-05-04T08:53:40Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [21.64772960240025]
  問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。 私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
  論文  参考訳（メタデータ） (2024-08-20T01:24:54Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• 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)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• 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)

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

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