論文の概要: Optimal Coreset for Gaussian Kernel Density Estimation

• arxiv url: http://arxiv.org/abs/2007.08031v5
• Date: Mon, 21 Feb 2022 03:45:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-10 06:47:56.236654
• Title: Optimal Coreset for Gaussian Kernel Density Estimation
• Title（参考訳）: ガウスカーネル密度推定のための最適コアセット
• Authors: Wai Ming Tai
• Abstract要約: 点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。 我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
• 参考スコア（独自算出の注目度）: 0.8376091455761259
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a point set $P\subset \mathbb{R}^d$, the kernel density estimate of $P$ is defined as \[ \overline{\mathcal{G}}_P(x) = \frac{1}{\left|P\right|}\sum_{p\in P}e^{-\left\lVert x-p \right\rVert^2} \] for any $x\in\mathbb{R}^d$. We study how to construct a small subset $Q$ of $P$ such that the kernel density estimate of $P$ is approximated by the kernel density estimate of $Q$. This subset $Q$ is called a coreset. The main technique in this work is constructing a $\pm 1$ coloring on the point set $P$ by discrepancy theory and we leverage Banaszczyk's Theorem. When $d>1$ is a constant, our construction gives a coreset of size $O\left(\frac{1}{\varepsilon}\right)$ as opposed to the best-known result of $O\left(\frac{1}{\varepsilon}\sqrt{\log\frac{1}{\varepsilon}}\right)$. It is the first result to give a breakthrough on the barrier of $\sqrt{\log}$ factor even when $d=2$.
• Abstract（参考訳）: 点集合 $p\subset \mathbb{r}^d$ が与えられると、カーネル密度推定値 $p$ は任意の $x\in\mathbb{r}^d$ に対して \[ \overline{\mathcal{g}}_p(x) = \frac{1}{\left|p\right|}\sum_{p\in p}e^{-\left\lvert x-p \right\rvert^2} \] と定義される。 我々は、$P$の小さな部分集合を、$P$のカーネル密度推定が$Q$のカーネル密度推定によって近似されるように構成する方法を研究する。 このサブセット $q$ は coreset と呼ばれる。 本研究の主な手法は、不一致理論による点集合 p$ 上の$\pm 1$ の色付けを構築し、バナシュツィクの定理を活用することである。 d>1$ が定数であるとき、我々の構成は $o\left(\frac{1}{\varepsilon}\right)$ の最もよく知られている結果とは対照的に、サイズ $o\left(\frac{1}{\varepsilon}\sqrt{\log\frac{1}{\varepsilon}}\right)$ のコアセットを与える。 $d=2$であっても、$\sqrt{\log}$ factorの障壁を突破する最初の結果である。

関連論文リスト

• A Tight VC-Dimension Analysis of Clustering Coresets with Applications [19.213536807823836]
  ここでは,距離の最小化を行う中心に点を割り当てることが目的とする,$k$-clustering問題に対するコアセットを検討する。 点集合 $P$ が与えられたとき、コアセット $Omega$ はすべての候補解に対して$P$ のコストを近似する小さな重み付き部分集合である。 以下の指標に対して、改良された$k$-medianコアセット境界を得る。
  論文  参考訳（メタデータ） (2025-01-11T17:00:57Z)
• Sparsifying Suprema of Gaussian Processes [6.638504164134713]
  我々は、$O_varepsilon(1)$-size subset $S subseteq T$ と、S$ における実値 $c_s_s の集合が存在することを示す。 また、中心となるガウス過程の過度にスペーシフィケーション結果を用いて、有界な幾何学的幅の凸集合に対するスペーシフィケーション補題を与える。
  論文  参考訳（メタデータ） (2024-11-22T01:43:58Z)
• Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
  $ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。 我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。 我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• A note on estimating the dimension from a random geometric graph [2.3020018305241337]
  グラフの隣接行列にアクセスする際に、基礎空間の次元$d$を推定する問題について検討する。 また、密度の条件がなければ、$d$の一貫した推定子は$n r_nd to infty$と$r_n = o(1)$が存在することを示す。
  論文  参考訳（メタデータ） (2023-11-21T23:46:44Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• 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)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• 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)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• Sets Clustering [25.358415142404752]
  我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。 このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。 オープンソースコードと文書分類および施設位置の実験結果も提供される。
  論文  参考訳（メタデータ） (2020-03-09T13:30:30Z)

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

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