論文の概要: The VC dimension of partial concept classes via Radon's theorem
- arxiv url: http://arxiv.org/abs/2607.10751v1
- Date: Sun, 12 Jul 2026 13:00:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 15:40:48.523829
- Title: The VC dimension of partial concept classes via Radon's theorem
- Title（参考訳）: ラドンの定理による部分概念クラスのVC次元
- Authors: Grigory Ivanov, Attila Jung, Márton Naszódi,
- Abstract要約: 部分的概念クラス (PCC) を部分関数の族 (f: Vto0,1,ast) として定義する。
主な結果は,拡張球(L_pparenth),(1le pinfty)におけるPCCのVC次元上の次元自由な上界であり,非ユークリッドおよびアルゴリズム的に特に関係のある場合(elld_1)を含む。
私たちはまた、VCの低い境界を証明します。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Following Alon, Hanneke, Holzman, and Moran (FOCS 2021), we define a partial concept class (PCC) as a family of partial functions \(f: V\to\{0,1,\ast\}\); equivalently, its concepts partition the ground set into black ($f^{-1}(1)$), grey ($f^{-1}(\ast)$), and white parts ($f^{-1}(0)$). Its VC dimension is defined by shattering sets on which the value $\ast$ is not taken. We study two geometric PCCs in real Banach spaces, both with a margin \(δ>0\): expanded half-spaces, where the grey part is a strip of width at least \(δ\) adjacent to a half-space, and expanded balls, where the grey part is an annulus of width \(δ\) around a unit radius ball. Our main results are dimension-free upper bounds on the VC dimension of the PCC of expanded balls in \(L_p\parenthμ\), \(1\le p<\infty\), including the non-Euclidean and algorithmically particularly relevant case \(\ell^d_1\). These bounds depend on the margin and on the radii, but not on the ambient dimension or the underlying measure space. These are extensions of the work of Bourneuf, Charbit, and Thomassé (FOCS 2025) who studied the PCC of expanded balls in Euclidean space, that is, $\ell_2^d$. We also prove lower bounds on the VC dimension that match the upper bounds in terms of the margin parameter $δ$. Finally, we derive a Dense Neighborhood Lemma in \(L_p\)-spaces, again extending the known Euclidean results. Our method relies on the linearization of the distance through a map into a space of non-trivial Rademacher type, and then the use of a balanced signed-sum estimate, or a no-dimensional Radon theorem. The arguments rely on ideas from functional analysis that are clearly explained for the non-expert in that field.
- Abstract（参考訳）: Alon, Hanneke, Holzman, and Moran (FOCS 2021) に続いて、部分概念クラス (PCC) を部分関数の族 \(f: V\to\{0,1,\ast\}\) として定義する。
そのVC次元は、$\ast$を取らない集合を破砕することによって定義される。
実バナッハ空間における2つの幾何的PCCについて検討し、両端辺 \(δ>0\): 拡張半空間において、グレイ部はハーフ空間に隣接する少なくとも幅 \(δ\) のストリップであり、拡張球では、グレイ部は単位半径球の周りの幅 \(δ\) の環状である。
我々の主な結果は、非ユークリッドおよびアルゴリズム上、特に関連する場合 \(\ell^d_1\)を含む拡張球のPCCのVC次元上の次元自由な上界である。
これらの境界は辺と半径に依存するが、周囲次元や下層の測度空間には依存しない。
これらは Bourneuf, Charbit, Thomassé (FOCS 2025) の業績の拡張であり、ユークリッド空間における拡張球のPCC、すなわち$\ell_2^d$ の研究である。
また、マージンパラメータ$δ$の観点で上界に一致するVC次元上の下界も証明する。
最後に、dense Neighborhood Lemma を \(L_p\)-空間で導き、既知のユークリッドの結果を再び拡張する。
我々の手法は、写像から非自明なラデマッハ型の空間への距離の線型化と、バランスの取れた符号和推定、あるいは非次元ラドン定理(英語版)の使用に依存する。
この議論は、その分野の非専門家に対して明確に説明される機能解析の考えに依存している。
関連論文リスト
- Terminal Dimension Reduction for Time Series with Applications [53.49083917849734]
ターミナル埋め込みは次元減少のための強力なツールとして登場した。
この問題を克服するアフィン線分への終端埋め込みの一般化を開発する。
フレシェ距離の下で時系列をクラスタリングするための最初の次元自由コアセットを得る。
論文 参考訳（メタデータ） (2026-07-10T15:05:30Z) - Annihilating and breaking Lorentz cone entanglement [49.1574468325115]
円錐によって誘導される順序を持つ有限次元順序ベクトル空間の間の線型写像は絡み目破れと呼ばれる。
我々は、K$が任意の次元のローレンツに制限されたローレンツ絡みのより大きなクラスについて研究する。
論文 参考訳（メタデータ） (2025-06-17T12:58:14Z) - Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。
分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文 参考訳（メタデータ） (2025-04-29T15:56:48Z) - A Variant of the Bravyi-Terhal Bound for Arbitrary Boundary Conditions [10.560637835517094]
商 $mathbbZD/Lambda$ of $mathbbZD$ of cardinality $n$ on a $D$-dimensional lattice quotient を考える。
すべての安定化器ジェネレータが半径$rho$の範囲内にある量子ビットに作用すると、コードの最小距離$d$は$d leq msqrtgamma_D(sqrtD + 4rho)nfracD-1D$である。
論文 参考訳（メタデータ） (2025-02-07T15:18:40Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。
本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。
我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
論文 参考訳（メタデータ） (2022-04-09T16:45:22Z) - A Variational Quantum Algorithm For Approximating Convex Roofs [0.0]
絡み合い測度は、まずバイパルタイトヒルベルト空間の純粋な状態に対して定義され、その後凸屋根拡大を通じて混合状態に拡張される。
mathbbN$で$dに対して$f$-$d$拡張と呼ぶ一連の拡張を生成します。
純状態上で定義された絡み合い尺度の$f$-$d$拡張を近似することを目的とした量子変分アルゴリズムを導入する。
論文 参考訳（メタデータ） (2022-03-04T02:30:35Z) - Asymptotic Tensor Powers of Banach Spaces [77.34726150561087]
ユークリッド空間は、そのテンソル半径がその次元と等しい性質によって特徴づけられることを示す。
また、領域または範囲がユークリッドである作用素のテンソル半径がその核ノルムと等しいことを示す。
論文 参考訳（メタデータ） (2021-10-25T11:51:12Z) - Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。
特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。
提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
論文 参考訳（メタデータ） (2020-11-02T14:59:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。