論文の概要: Generalized Kernel Thinning
- arxiv url: http://arxiv.org/abs/2110.01593v1
- Date: Mon, 4 Oct 2021 17:41:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-05 17:55:27.276024
- Title: Generalized Kernel Thinning
- Title(参考訳): 一般化カーネル薄片化
- Authors: Raaz Dwivedi, Lester Mackey
- Abstract要約: kernel Thinningアルゴリズムは、$n$ポイントの分布の要約を$sqrt n$ポイントの要約に圧縮する。
対象のカーネルに直接適用されるKTは、カーネルヒルベルト空間における各関数$f$に対して、より厳密な$mathcalO(sqrtlog n/n)$積分誤差をもたらすことを示す。
- 参考スコア(独自算出の注目度): 25.21711170090549
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The kernel thinning (KT) algorithm of Dwivedi and Mackey (2021) compresses an
$n$ point distributional summary into a $\sqrt n$ point summary with
better-than-Monte-Carlo maximum mean discrepancy for a target kernel
$\mathbf{k}$ by leveraging a less smooth square-root kernel. Here we provide
four improvements. First, we show that KT applied directly to the target kernel
yields a tighter $\mathcal{O}(\sqrt{\log n/n})$ integration error bound for
each function $f$ in the reproducing kernel Hilbert space. This modification
extends the reach of KT to any kernel -- even non-smooth kernels that do not
admit a square-root, demonstrates that KT is suitable even for heavy-tailed
target distributions, and eliminates the exponential dimension-dependence and
$(\log n)^{d/2}$ factors of standard square-root KT. Second, we show that, for
analytic kernels, like Gaussian and inverse multiquadric, target kernel KT
admits maximum mean discrepancy (MMD) guarantees comparable to square-root KT
without the need for an explicit square-root kernel. Third, we prove KT with a
fractional $\alpha$-power kernel $\mathbf{k}_{\alpha}$ for $\alpha > 1/2$
yields better-than-Monte-Carlo MMD guarantees for non-smooth kernels, like
Laplace and \Matern, that do not have square-roots. Fourth, we establish that
KT applied to a sum of $\mathbf{k}$ and $\mathbf{k}_{\alpha}$ (a procedure we
call KT+) simultaneously inherits the improved MMD guarantees of power KT and
the tighter individual function guarantees of KT on the target kernel. Finally,
we illustrate the practical benefits of target KT and KT+ for compression after
high-dimensional independent sampling and challenging Markov chain Monte Carlo
posterior inference.
- Abstract(参考訳): Dwivedi と Mackey (2021) のカーネルシンニング (KT) アルゴリズムは、より滑らかでない平方根のカーネルを利用することで、ターゲットカーネル $\mathbf{k}$ に対するより優れたモンテカルト・カルロの最大平均誤差を、$\sqrt n$ポイントサマリに圧縮する。
ここでは4つの改善がある。
まず、KT をターゲットカーネルに直接適用すると、再生カーネルヒルベルト空間における各関数 $f$ に対して、より厳密な $\mathcal{O}(\sqrt{\log n/n})$積分誤差が生じることを示す。
この修正は、KT の到達範囲を任意のカーネルにまで拡大する -- 平方根を含まない非滑らかなカーネルでさえも、KT は重尾のターゲット分布にも適しており、指数次元依存性と標準平方根 KT の$(\log n)^{d/2}$因子を排除している。
第2に,gaussianやinverse multiquadricのような解析的カーネルでは,ターゲットカーネルktは,明示的な平方根カーネルを必要とせずに,正方根ktに匹敵する最大平均差(mmd)を保証する。
第3に、最小の$\alpha$-power カーネル $\mathbf{k}_{\alpha}$ for $\alpha > 1/2$ で kt を証明すれば、ラプラスや \matern のような正方根を持たない非スムースカーネルに対して、モンテカルロmmdよりも優れた保証が得られる。
第4に、KT が $\mathbf{k}$ と $\mathbf{k}_{\alpha}$ (KT+ と呼ぶ手順) の和に適用されたことが、改良された KT の MMD 保証と、ターゲットカーネル上の KT のより厳密な個々の関数保証を同時に継承することを確立する。
最後に,高次元独立サンプリング後の圧縮に対する標的ktとkt+の実用的効果を示し,マルコフ連鎖モンテカルロ後方推定に挑戦する。
関連論文リスト
- On The Relative Error of Random Fourier Features for Preserving Kernel
Distance [7.383448514243228]
有名なラプラシアカーネルを含むかなりの範囲のカーネルに対して、RFFは低次元を用いて小さな相対誤差でカーネル距離を近似することはできないことを示す。
一般シフト不変カーネルに対するデータ公開次元還元に向けての第一歩を踏み出し、ラプラシアンカーネルに対して同様の$mathrmpoly(epsilon-1 log n)$ dimension を得る。
論文 参考訳(メタデータ) (2022-10-01T10:35:12Z) - 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) - A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
カーネル平均埋め込みは、その無限次元平均埋め込みによる確率測度を表す。
カーネルが特徴的である場合、カーネルの総和密度を持つ分布は密度が高いことを示す。
有限サンプル設定でそのような分布を最適化するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-06-18T08:33:45Z) - Taming Nonconvexity in Kernel Feature Selection---Favorable Properties
of the Laplace Kernel [77.73399781313893]
カーネルベースの特徴選択の客観的機能を確立することが課題である。
非言語最適化に利用可能な勾配に基づくアルゴリズムは、局所ミニマへの収束を保証できるだけである。
論文 参考訳(メタデータ) (2021-06-17T11:05:48Z) - 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) - Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。
私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
論文 参考訳(メタデータ) (2020-06-12T17:25:39Z) - 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) - Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
モデルに基づく楽観的アルゴリズムであるKernel-UCBVIを導入する。
スパース報酬を伴う連続MDPにおける我々のアプローチを実証的に検証する。
論文 参考訳(メタデータ) (2020-04-12T12:23:46Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳(メタデータ) (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。