論文の概要: For Kernel Range Spaces a Constant Number of Queries Are Sufficient
- arxiv url: http://arxiv.org/abs/2306.16516v1
- Date: Wed, 28 Jun 2023 19:19:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-30 15:57:24.142093
- Title: For Kernel Range Spaces a Constant Number of Queries Are Sufficient
- Title(参考訳): カーネルレンジスペースの場合、定数のクエリは十分である
- Authors: Jeff M. Phillips and Hasan Pourmahmood-Aghababa
- Abstract要約: カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。
Anvarepsilon$-cover は点 $Q の部分集合 mathbbRd$ for any $p in mathbbRd$ that $frac1n |R_p - R_q|leq varepsilon$ for some $q in Q$ の部分集合である。
- 参考スコア(独自算出の注目度): 13.200502573462712
- 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)$). 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 $(1/\varepsilon)^{\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)$)に関する。
点集合 $X$ of size $n$ に対して、クエリは値のベクトル $R_p \in \mathbb{R}^n$ を返し、$i$th 座標 $(R_p)_i = K(p,x_i)$ for $x_i \in X$ が返される。
Q \subset \mathbb{R}^d$ は任意の$p \in \mathbb{R}^d$ に対して、$\frac{1}{n} \|R_pR_q\|_1\leq \varepsilon$ の集合である。
これは、組合せ範囲空間に対するハウスラーの$\varepsilon$-covers(例えば、ボールクエリ内の点の部分集合で定義される)の概念の滑らかな類似であり、結果として得られるベクトル$R_p$は$[0,1]^n$の代わりに$\{0,1\}^n$である。
これらの範囲空間のカーネルバージョンは、座標が不確かで不正確であるかもしれないデータ解析タスクに現れ、従ってクエリ範囲内外の概念に柔軟性を加えることを望んでいる。
私たちの主な結果は、組合せ範囲空間とは異なり、カーネル $\varepsilon$-covers のサイズは入力サイズ $n$ と次元 $d$ に依存しないということです。
ここでは、$(1/\varepsilon)^{\tilde O(1/\varepsilon^2)}$, $\tilde{O}(f(1/\varepsilon))$は、カーネルに依存することができる$(1/\varepsilon)$でログ係数を隠す。
これは、範囲クエリにおける境界の概念を緩和することで、最終的には次元の呪いが消え、非常に高次元の機械学習の成功を説明するのに役立つことを意味する。
また、この結果を約$(1/\varepsilon)^{\Omega(1/\varepsilon)$で補い、$/\varepsilon$への指数的な依存が必要とされることを示す。
関連論文リスト
- Online Learning of Smooth Functions [0.35534933448684125]
隠れ関数が一定の滑らか性を持つことが知られている実数値関数のオンライン学習について検討する。
定数係数までシャープな$textopt_p(mathcal F_q)$の新たなバウンダリを見つける。
マルチ変数のセットアップでは、$textopt_p(mathcal F_q,d)$ to $textopt_p(mathcal F_q,d)$に関連する不等式を確立し、$textopt_p(mathcal F)$を示す。
論文 参考訳(メタデータ) (2023-01-04T04:05:58Z) - 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) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - 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) - Mathematical comparison of classical and quantum mechanisms in
optimization under local differential privacy [0.0]
我々は、$mathrmEC_n(varepsilon)not=mathrmCQ_n(varepsilon)$ for every $nge3$を示し、$mathrmEC_n(varepsilon)$と$mathrmCQ_n(varepsilon)$の差をある方法で見積もる。
論文 参考訳(メタデータ) (2020-11-19T17:05:11Z) - 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) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。