論文の概要: Dimension-Independent Kernel ε-Covers

• arxiv url: http://arxiv.org/abs/2306.16516v2
• Date: Thu, 12 Jun 2025 05:36:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 15:37:21.946426
• Title: Dimension-Independent Kernel ε-Covers
• Title（参考訳）: 次元独立カーネルε-コーバー
• Authors: Jeff M. Phillips, Hasan Pourmahmood-Aghababa,
• Abstract要約: カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。 カーネルレンジ空間に対して$varepsilon$-coverという概念を導入する。
• 参考スコア（独自算出の注目度）: 8.234735564035567
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We introduce the notion of an $\varepsilon$-cover for a kernel range space. A kernel range space concerns a set of points $X \subset \mathbb{R}^d$ and the space of all queries by a fixed kernel (e.g., a Gaussian kernel $K(p,\cdot) = \exp(-\|p-\cdot\|^2)$, where $p \in \mathbb{R}^d$). For a point set $X$ of size $n$, a query returns a vector of values $R_p \in \mathbb{R}^n$, where the $i$th coordinate $(R_p)_i = K(p,x_i)$ for $x_i \in X$. An $\varepsilon$-cover is a subset of points $Q \subset \mathbb{R}^d$ so for any $p \in \mathbb{R}^d$ that $\frac{1}{n} \|R_p - R_q\|_1\leq \varepsilon$ for some $q \in Q$. This is a smooth analog of Haussler's notion of $\varepsilon$-covers for combinatorial range spaces (e.g., defined by subsets of points within a ball query) where the resulting vectors $R_p$ are in $\{0,1\}^n$ instead of $[0,1]^n$. The kernel versions of these range spaces show up in data analysis tasks where the coordinates may be uncertain or imprecise, and hence one wishes to add some flexibility in the notion of inside and outside of a query range. Our main result is that, unlike combinatorial range spaces, the size of kernel $\varepsilon$-covers is independent of the input size $n$ and dimension $d$. We obtain a bound of $2^{\tilde O(1/\varepsilon^2)}$, where $\tilde{O}(f(1/\varepsilon))$ hides log factors in $(1/\varepsilon)$ that can depend on the kernel. This implies that by relaxing the notion of boundaries in range queries, eventually the curse of dimensionality disappears, and may help explain the success of machine learning in very high-dimensions. We also complement this result with a lower bound of almost $(1/\varepsilon)^{\Omega(1/\varepsilon)}$, showing the exponential dependence on $1/\varepsilon$ is necessary.
• Abstract（参考訳）: カーネルレンジ空間に対して$\varepsilon$-coverという概念を導入する。 カーネル範囲空間は、点の集合 $X \subset \mathbb{R}^d$ と、固定されたカーネルによる全てのクエリの空間(例えば、ガウス核 $K(p,\cdot) = \exp(-\|p-\cdot\|^2)$, ここで $p \in \mathbb{R}^d$)に関する。 点集合 $X$ of size $n$ に対して、クエリは値のベクトル $R_p \in \mathbb{R}^n$ を返し、$i$th 座標 $(R_p)_i = K(p,x_i)$ for $x_i \in X$ が返される。 $\varepsilon$-cover は点 $Q \subset \mathbb{R}^d$ であるので、任意の$p \in \mathbb{R}^d$ に対して $\frac{1}{n} \|R_p - R_q\|_1\leq \varepsilon$ は、ある$q \in Q$ に対して$Q \subset \mathbb{R}^d$ である。 これはハウスラーのコンビナトリアルレンジ空間に対する$\varepsilon$-covers(例えば、ボールクエリ内の点の部分集合で定義される)の概念の滑らかな類似であり、結果として得られるベクトル$R_p$は$[0,1]^n$ではなく$$\{0,1\}^n$である。 これらの範囲空間のカーネルバージョンは、座標が不確かで不正確であるかもしれないデータ解析タスクに現れ、従ってクエリ範囲内外の概念に柔軟性を加えることを望んでいる。 我々の主な結果は、組合せ範囲空間とは異なり、カーネル$\varepsilon$-coversのサイズは入力サイズ$n$と次元$d$とは独立である。 ここで、$\tilde{O}(f(1/\varepsilon))$は、カーネルに依存することができる$(1/\varepsilon)$でログ係数を隠す。 これは、範囲クエリのバウンダリの概念を緩和することで、最終的に次元性の呪いが消え、非常に高次元での機械学習の成功を説明するのに役立つことを示唆している。 また、この結果を約$(1/\varepsilon)^{\Omega(1/\varepsilon)$で補い、$/\varepsilon$への指数的な依存が必要とされることを示す。

関連論文リスト

• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• Sparsifying Suprema of Gaussian Processes [6.638504164134713]
  我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。 また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
  論文  参考訳（メタデータ） (2024-11-22T01:43:58Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。 1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
  論文  参考訳（メタデータ） (2024-06-04T15:50:42Z)
• Metricizing the Euclidean Space towards Desired Distance Relations in Point Clouds [1.2366208723499545]
  我々は教師なし学習アルゴリズム、具体的には$k$-Means and density-based clustering algorithm(DBSCAN)を攻撃している。 クラスタリングアルゴリズムの結果は、特定の距離関数を使用するための標準化された固定された処方令がなければ、一般的には信頼できない可能性がある。
  論文  参考訳（メタデータ） (2022-11-07T16:37:29Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。 我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
  論文  参考訳（メタデータ） (2022-04-09T16:45:22Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Approximate Maximum Halfspace Discrepancy [6.35821487778241]
  範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。 数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
  論文  参考訳（メタデータ） (2021-06-25T19:14:45Z)
• Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
  点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。 我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
  論文  参考訳（メタデータ） (2020-07-15T22:58:50Z)

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

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