論文の概要: Kernel Thinning

• arxiv url: http://arxiv.org/abs/2105.05842v9
• Date: Wed, 7 Jun 2023 00:41:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-08 20:52:42.609929
• Title: Kernel Thinning
• Title（参考訳）: カーネルの薄型化
• Authors: Raaz Dwivedi, Lester Mackey
• Abstract要約: カーネルの薄型化は、サンプリングや標準的な薄型化よりも効率的に$mathbbP$を圧縮するための新しい手順である。 我々は、ガウス、マタン、およびB-スプライン核に対する明示的な非漸近的な最大誤差境界を導出する。
• 参考スコア（独自算出の注目度）: 26.25415159542831
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce kernel thinning, a new procedure for compressing a distribution $\mathbb{P}$ more effectively than i.i.d. sampling or standard thinning. Given a suitable reproducing kernel $\mathbf{k}_{\star}$ and $\mathcal{O}(n^2)$ time, kernel thinning compresses an $n$-point approximation to $\mathbb{P}$ into a $\sqrt{n}$-point approximation with comparable worst-case integration error across the associated reproducing kernel Hilbert space. The maximum discrepancy in integration error is $\mathcal{O}_d(n^{-1/2}\sqrt{\log n})$ in probability for compactly supported $\mathbb{P}$ and $\mathcal{O}_d(n^{-\frac{1}{2}} (\log n)^{(d+1)/2}\sqrt{\log\log n})$ for sub-exponential $\mathbb{P}$ on $\mathbb{R}^d$. In contrast, an equal-sized i.i.d. sample from $\mathbb{P}$ suffers $\Omega(n^{-1/4})$ integration error. Our sub-exponential guarantees resemble the classical quasi-Monte Carlo error rates for uniform $\mathbb{P}$ on $[0,1]^d$ but apply to general distributions on $\mathbb{R}^d$ and a wide range of common kernels. Moreover, the same construction delivers near-optimal $L^\infty$ coresets in $\mathcal O(n^2)$ time. We use our results to derive explicit non-asymptotic maximum mean discrepancy bounds for Gaussian, Mat\'ern, and B-spline kernels and present two vignettes illustrating the practical benefits of kernel thinning over i.i.d. sampling and standard Markov chain Monte Carlo thinning, in dimensions $d=2$ through $100$.
• Abstract（参考訳）: 我々は,分散$\mathbb{p}$をi.i.d.サンプリングや標準薄型化よりも効果的に圧縮する新しい手法であるkernel thinningを導入する。 適切な再生成カーネル $\mathbf{k}_{\star}$ と $\mathcal{o}(n^2)$ time が与えられると、カーネル・シンニングは$n$-point 近似を$\mathbb{p}$ に圧縮し、関連する再生成カーネル hilbert 空間をまたいだ最悪のケース統合エラーと一致する$\sqrt{n}$-point 近似を与える。 積分誤差の最大誤差は$\mathcal{o}_d(n^{-1/2}\sqrt{\log n})$で、コンパクトにサポートされている$\mathbb{p}$と$\mathcal{o}_d(n^{-\frac{1}{2}} (\log n)^{(d+1)/2}\sqrt{\log\log n})$ for sub-exponential $\mathbb{p}$ on $\mathbb{r}^d$である。 対照的に、$\mathbb{P}$の等サイズのi.d.サンプルは$\Omega(n^{-1/4})$積分誤差を被る。 このサブ指数保証は、$[0,1]^d$ で一様$\mathbb{p}$ の古典的な準モンテカルロ誤差率に似ているが、$\mathbb{r}^d$ の一般分布と幅広い共通カーネルに適用できる。 さらに、同じ構成は、ほぼ最適の$L^\infty$ coresetsを$\mathcal O(n^2)$ timeで提供する。 我々は,gaussian,mat\'ern,b-splineカーネルの非漸近的最大平均偏差を明示的に導出し,i.i.d.サンプリングおよび標準マルコフ連鎖モンテカルロ薄型化におけるカーネル薄型化の実用的利点を示す2つのvignetteを,$d=2$から$100$の次元で提示する。

関連論文リスト

• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Classical shadows of fermions with particle number symmetry [0.0]
  我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。 ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
  論文  参考訳（メタデータ） (2022-08-18T17:11: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)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• 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)

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

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