論文の概要: Stronger Coreset Bounds for Kernel Density Estimators via Chaining
- arxiv url: http://arxiv.org/abs/2310.08548v1
- Date: Thu, 12 Oct 2023 17:44:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 10:30:20.923879
- Title: Stronger Coreset Bounds for Kernel Density Estimators via Chaining
- Title（参考訳）: 連鎖によるカーネル密度推定器のより強いコアセット境界
- Authors: Rainie Bozzai and Thomas Rothvoss
- Abstract要約: 本稿では,カーネル関数のコアセットの複雑性を改善するために,差分法と連鎖法を適用した。
我々の結果は、ガウスカーネルとラプラシアカーネルのコアセットとして$Obig(fracsqrtdvarepsilonsqrtloglog frac1varepsilonbig)をランダムに生成する時間アルゴリズムを与える。
また、最もよく知られた$Obig(fracsqrtdvarepsilonsqrtlog (2max1,
- 参考スコア（独自算出の注目度）: 0.5454560484178483
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We apply the discrepancy method and a chaining approach to give improved
bounds on the coreset complexity of a wide class of kernel functions. Our
results give randomized polynomial time algorithms to produce coresets of size
$O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$
for the Gaussian and Laplacian kernels in the case that the data set is
uniformly bounded, an improvement that was not possible with previous
techniques. We also obtain coresets of size
$O\big(\frac{1}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$ for the
Laplacian kernel for $d$ constant. Finally, we give the best known bounds of
$O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\{1,\alpha\})}\big)$ on the
coreset complexity of the exponential, Hellinger, and JS Kernels, where
$1/\alpha$ is the bandwidth parameter of the kernel.
- Abstract（参考訳）: 我々は,幅広いカーネル関数のコアセットの複雑性を改良するために,分離法と連鎖法を適用した。
この結果から,ランダム化多項式時間アルゴリズムは,データセットが一様有界である場合にはガウスおよびラプラキアのカーネルに対して,サイズ$o\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$のコア集合を生成する。
また、サイズ $O\big(\frac{1}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$d$ constant のラプラシア核に対してコアセットを得る。
最後に、最もよく知られた境界である$o\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\{1,\alpha\})}\big)$ を指数関数、ヘリンガー、jsカーネルのコアセットの複雑さに基づいて与える。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - On the speed of uniform convergence in Mercer's theorem [6.028247638616059]
コンパクト集合上の連続正定核 $K(mathbf x, mathbf y)$ は $sum_i=1infty lambda_iphi_i(mathbf x)phi_i(mathbf y)$ と表すことができ、$(lambda_i,phi_i)$ は対応する積分作用素の固有値-固有ベクトル対である。
固有値の減衰速度からこの収束速度を推定し、300万ドルで証明する。
論文 参考訳（メタデータ） (2022-05-01T15:07:57Z) - Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。
我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
論文 参考訳（メタデータ） (2022-04-09T16:45:22Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Kernel Thinning [26.25415159542831]
カーネルの薄型化は、サンプリングや標準的な薄型化よりも効率的に$mathbbP$を圧縮するための新しい手順である。
我々は、ガウス、マタン、およびB-スプライン核に対する明示的な非漸近的な最大誤差境界を導出する。
論文 参考訳（メタデータ） (2021-05-12T17:56:42Z) - Convergence of Graph Laplacian with kNN Self-tuned Kernels [14.645468999921961]
自己チューニングされたカーネルは、各点に$sigma_i$ を $k$-nearest neighbor (kNN) 距離で適応的に設定する。
本稿では、グラフラプラシアン作用素$L_N$を、kNN自己チューニングカーネルの新しい族に対する多様体(重み付き)ラプラシアンに収束することを証明する。
論文 参考訳（メタデータ） (2020-11-03T04:55:33Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。