論文の概要: Local Urysohn Width: A Topological Complexity Measure for Classification

• arxiv url: http://arxiv.org/abs/2603.15412v1
• Date: Mon, 16 Mar 2026 15:22:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 18:28:58.536798
• Title: Local Urysohn Width: A Topological Complexity Measure for Classification
• Title（参考訳）: Urysohn の局所幅: 分類のためのトポロジカル複雑度測定
• Authors: Xin Li,
• Abstract要約: 計量空間上の分類問題に対する複雑性尺度であるエンファンローカライズン幅を導入する。 ユーリゾーン幅は、分類エンプロブレム自体の位相幾何学的・幾何学的複雑さを特徴づける
• 参考スコア（独自算出の注目度）: 6.0044467881527614
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We introduce \emph{local Urysohn width}, a complexity measure for classification problems on metric spaces. Unlike VC dimension, fat-shattering dimension, and Rademacher complexity, which characterize the richness of hypothesis \emph{classes}, Urysohn width characterizes the topological-geometric complexity of the classification \emph{problem itself}: the minimum number of connected, diameter-bounded local experts needed to correctly classify all points within a margin-safe region. We prove four main results. First, a \textbf{strict hierarchy theorem}: for every integer $w \geq 1$, there exists a classification problem on a \emph{connected} compact metric space (a bouquet of circles with first Betti number $β_1 = w$) whose Urysohn width is exactly~$w$, establishing that topological complexity of the input space forces classifier complexity. Second, a \textbf{topology $\times$ geometry scaling law}: width scales as $Ω(w \cdot L/D_0)$, where $w$ counts independent loops and $L/D_0$ is the ratio of loop circumference to locality scale. Third, a \textbf{two-way separation from VC dimension}: there exist problem families where width grows unboundedly while VC dimension is bounded by a constant, and conversely, families where VC dimension grows unboundedly while width remains~1. Fourth, a \textbf{sample complexity lower bound}: any learner that must correctly classify all points in the safe region of a width-$w$ problem needs $Ω(w \log w)$ samples, independent of VC dimension.
• Abstract（参考訳）: 距離空間上の分類問題に対する複雑性尺度である 'emph{local Urysohn width} を導入する。 仮説 \emph{classes} の豊かさを特徴づけるVC次元、脂肪散乱次元、ラデマッハ複雑性とは異なり、Urysohn width は分類 \emph{problem itself} の位相幾何学的複雑さを特徴付けている。 主な成果は4つある。 第一に、 \textbf{strict hierarchy theorem}: 任意の整数 $w \geq 1$ に対して、入力空間の位相的複雑さが分数化複雑性を課すような \emph{ connected} コンパクト計量空間(第一ベッチ数 $β_1 = w$ を持つ円の花束)上の分類問題が存在する。 第二に、 \textbf{topology $\times$ geometry scale law}: width scales as $Ω(w \cdot L/D_0)$, where $w$ counts independent loops and $L/D_0$ is the ratio of loop circumference to locality scale。 第三に、 \textbf{two-way separation from VC dimension}: 幅が非有界に成長する問題族が存在するが、VC次元は定数で有界であり、逆に、VC次元が非有界に成長する問題族は、幅が1である。 第4に、textbf{sample complexity lower bound}: 幅の安全な領域のすべての点を正しく分類しなければならない学習者は、VC次元とは独立に$Ω(w \log w)$ sampleが必要である。

関連論文リスト

• Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models [34.196233651364615]
  ガウス分布に基づく実数値マルチインデックスモデル(MIM)の学習の複雑さについて検討する。 K$-MIM は関数 $f:mathbbRdto mathbbR$ であり、入力の$K$-次元部分空間への射影のみに依存する。 逆ラベルノイズが存在する場合でも, 正方形損失に対して幅広いMIMを学習するための一般アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-27T17:47:26Z)
• Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces [0.815557531820863]
  我々は、$d$-dimensional $gamma$-margin half-spaces のリスト複製数が[ fracd2+1 le MathrmLR(Hd_gamma) le d, ] を満たすことを証明した。
  論文  参考訳（メタデータ） (2025-03-19T15:17:13Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• On the Sample Complexity of Two-Layer Networks: Lipschitz vs. Element-Wise Lipschitz Activation [20.70453775428433]
  本研究では,異なるアクティベーション関数を用いた有界二層ニューラルネットワークのサンプル複雑性について検討する。 我々は、$sigma$ が要素ワイドであれば、$mathcalH$ のサンプルの複雑さは、幅の対数依存しか持たないことを証明する。
  論文  参考訳（メタデータ） (2022-11-17T16:27:15Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Robust testing of low-dimensional functions [8.927163098772589]
  著者たちの最近の研究は、線型$k$-juntasがテスト可能であることを示した。 耐雑音性試験への関心が高まった後, 本論文では, 耐雑音性(あるいは頑健性)バージョンを実証する。 クエリ複雑性が$kO(mathsfpoly(log k/epsilon))$,$k$-halfspacesの交叉のクラスに対して完全耐雑音試験器を得る。
  論文  参考訳（メタデータ） (2020-04-24T10:23:12Z)

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

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