論文の概要: On the Intrinsic Dimensions of Data in Kernel Learning
- arxiv url: http://arxiv.org/abs/2601.16139v1
- Date: Thu, 22 Jan 2026 17:32:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-23 21:37:20.674857
- Title: On the Intrinsic Dimensions of Data in Kernel Learning
- Title（参考訳）: カーネル学習におけるデータ固有の次元について
- Authors: Rustem Takhanov,
- Abstract要約: ラプラスカーネルのようなカーネルの場合、実効次元$d_K$はミンコフスキー次元$d_$よりもかなり小さく、正則領域で証明可能であることを示す。
以上の結果から,Laplaceカーネルのようなカーネルの場合,実効次元$d_K$は,通常のドメインに有するMinkowski次元$d_$よりも著しく小さいことが分かる。
- 参考スコア（独自算出の注目度）: 1.675218291152252
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The manifold hypothesis suggests that the generalization performance of machine learning methods improves significantly when the intrinsic dimension of the input distribution's support is low. In the context of KRR, we investigate two alternative notions of intrinsic dimension. The first, denoted $d_ρ$, is the upper Minkowski dimension defined with respect to the canonical metric induced by a kernel function $K$ on a domain $Ω$. The second, denoted $d_K$, is the effective dimension, derived from the decay rate of Kolmogorov $n$-widths associated with $K$ on $Ω$. Given a probability measure $μ$ on $Ω$, we analyze the relationship between these $n$-widths and eigenvalues of the integral operator $φ\to \int_ΩK(\cdot,x)φ(x)dμ(x)$. We show that, for a fixed domain $Ω$, the Kolmogorov $n$-widths characterize the worst-case eigenvalue decay across all probability measures $μ$ supported on $Ω$. These eigenvalues are central to understanding the generalization behavior of constrained KRR, enabling us to derive an excess error bound of order $O(n^{-\frac{2+d_K}{2+2d_K} + ε})$ for any $ε> 0$, when the training set size $n$ is large. We also propose an algorithm that estimates upper bounds on the $n$-widths using only a finite sample from $μ$. For distributions close to uniform, we prove that $ε$-accurate upper bounds on all $n$-widths can be computed with high probability using at most $O\left(ε^{-d_ρ}\log\frac{1}ε\right)$ samples, with fewer required for small $n$. Finally, we compute the effective dimension $d_K$ for various fractal sets and present additional numerical experiments. Our results show that, for kernels such as the Laplace kernel, the effective dimension $d_K$ can be significantly smaller than the Minkowski dimension $d_ρ$, even though $d_K = d_ρ$ provably holds on regular domains.
- Abstract（参考訳）: 本仮説は,入力分布の固有次元が低い場合に,機械学習手法の一般化性能が著しく向上することが示唆された。
KRRの文脈で、本質的な次元の2つの代替概念を考察する。
第一に$d_ρ$ と表記されるものは、領域 $Ω$ 上の核関数 $K$ によって誘導される正準計量に関して定義されるミンコフスキー上の次元である。
第二の次元は、$d_K$と表されるが、これは、$$$$K$に付随するコルモゴロフ$n$-幅の崩壊速度から導かれる。
確率測度$μ$が$Ω$に与えられたとき、これらの$n$-幅と積分作用素$φ\to \int_ΩK(\cdot,x)φ(x)dμ(x)$の固有値の関係を分析する。
固定領域 $Ω$ に対して、コルモゴロフ$n$-幅は、すべての確率測度における最悪のケース固有値減衰を $Ω$ で支えられる$μ$ であることを示す。
これらの固有値は制約付きKRRの一般化挙動を理解する中心であり、任意の$ε> 0$に対して位数$O(n^{-\frac{2+d_K}{2+d_K} + ε})$の過剰な誤差境界を導出することができる。
また、$μ$の有限サンプルのみを用いて、$n$-widths上の上限を推定するアルゴリズムを提案する。
均一に近い分布に対して、すべての$n$-幅上のε$-正確な上限は、少なくとも$O\left(ε^{-d_ρ}\log\frac{1}ε\right)$サンプルを用いて高い確率で計算できることを示す。
最後に, 種々のフラクタル集合に対する有効次元$d_K$を計算し, 追加の数値実験を行う。
以上の結果から,Laplaceカーネルのようなカーネルの場合,実効次元$d_K$は,通常のドメインで証明可能な$d_K = d_ρ$であっても,ミンコフスキー次元$d_ρ$よりもかなり小さいことが分かる。
関連論文リスト
- Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。
We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。
また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
論文 参考訳（メタデータ） (2025-03-26T03:36:36Z) - Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Learning linear dynamical systems under convex constraints [4.13951084724473]
単一軌道の標本から線形力学系の有限時間同定の問題を考える。
A*$は制約のない設定に必要な値よりもはるかに小さい値に対して確実に推定できることを示す。
論文 参考訳（メタデータ） (2023-03-27T11:49:40Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。