論文の概要: Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via
Leverage Scores Sampling
- arxiv url: http://arxiv.org/abs/2311.13548v1
- Date: Wed, 22 Nov 2023 17:44:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 14:14:57.971450
- Title: Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via
Leverage Scores Sampling
- Title（参考訳）: レバレッジスコアサンプリングによるカーネルヒルベルト空間の効率的な数値積分
- Authors: Antoine Chatalic, Nicolas Schreuder, Ernesto De Vito, Lorenzo Rosasco
- Abstract要約: 本稿では,積分を対象確率測度に対して,積分の点的評価のみを用いて近似する問題を考察する。
本稿では,初期観測から得られる近似レバレッジスコアを用いて,$mn$サンプルのランダムな小部分集合を均一に描画するか,あるいは近似的に評価する手法を提案する。
- 参考スコア（独自算出の注目度）: 16.992480926905067
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this work we consider the problem of numerical integration, i.e.,
approximating integrals with respect to a target probability measure using only
pointwise evaluations of the integrand. We focus on the setting in which the
target distribution is only accessible through a set of $n$ i.i.d.
observations, and the integrand belongs to a reproducing kernel Hilbert space.
We propose an efficient procedure which exploits a small i.i.d. random subset
of $m<n$ samples drawn either uniformly or using approximate leverage scores
from the initial observations. Our main result is an upper bound on the
approximation error of this procedure for both sampling strategies. It yields
sufficient conditions on the subsample size to recover the standard (optimal)
$n^{-1/2}$ rate while reducing drastically the number of functions evaluations,
and thus the overall computational cost. Moreover, we obtain rates with respect
to the number $m$ of evaluations of the integrand which adapt to its
smoothness, and match known optimal rates for instance for Sobolev spaces. We
illustrate our theoretical findings with numerical experiments on real
datasets, which highlight the attractive efficiency-accuracy tradeoff of our
method compared to existing randomized and greedy quadrature methods. We note
that, the problem of numerical integration in RKHS amounts to designing a
discrete approximation of the kernel mean embedding of the target distribution.
As a consequence, direct applications of our results also include the efficient
computation of maximum mean discrepancies between distributions and the design
of efficient kernel-based tests.
- Abstract（参考訳）: 本研究では,数値積分の問題,すなわち,積分の点的評価のみを用いて,対象確率測度に対して積分を近似する問題を考える。
我々は、ターゲット分布が$n$ i.d. の観測によってのみアクセス可能な設定に焦点を合わせ、積分子は再生されたカーネルヒルベルト空間に属する。
そこで我々は,初期観測から得られる近似レバレッジスコアを用いて,$m<n$サンプルのランダムな小部分集合を均一に描画するか,あるいは利用した。
我々の主な結果は、両方のサンプリング戦略に対するこの手順の近似誤差の上限である。
これは、標準(最適)の$n^{-1/2}$レートを回復するのに十分な条件を与え、機能評価の数を劇的に削減し、全体的な計算コストを削減している。
さらに、その滑らかさに適応する積分器の評価数に対して$m$のレートを得ることができ、例えばソボレフ空間の既知最適レートと一致する。
提案手法は,従来のランダム化法とグリード化法を比較検討し,実データを用いた数値実験により理論的知見を述べる。
rkhsにおける数値積分の問題は、核の離散近似を設計することで、対象分布の埋め込みを意味することに注意する。
その結果,結果の直接適用には,分布間の平均誤差の最大値の効率的な計算や,カーネルベースの効率的なテストの設計も含まれる。
関連論文リスト
- On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
我々は,強い対数対数データの下での拡散に基づく生成モデルの収束挙動を理論的に保証する。
スコア推定に使用される関数のクラスは、スコア関数上のリプシッツネスの仮定を避けるために、リプシッツ連続関数からなる。
この手法はサンプリングアルゴリズムにおいて最もよく知られた収束率をもたらす。
論文 参考訳（メタデータ） (2023-11-22T18:40:45Z) - Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。
通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。
本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
論文 参考訳（メタデータ） (2023-09-29T15:24:48Z) - Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。
本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
論文 参考訳（メタデータ） (2023-06-13T01:18:16Z) - Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。
分散勾配追跡法を,勾配推定のない帯域設定に拡張する。
近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
論文 参考訳（メタデータ） (2022-10-11T17:04:45Z) - Nystr\"om Kernel Mean Embeddings [92.10208929236826]
Nystr"om法に基づく効率的な近似手法を提案する。
サブサンプルサイズの条件は標準の$n-1/2$レートを得るのに十分である。
本稿では,この結果の最大誤差と二次規則の近似への応用について論じる。
論文 参考訳（メタデータ） (2022-01-31T08:26:06Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳（メタデータ） (2021-10-07T17:51:10Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Consensus-Based Optimization on the Sphere: Convergence to Global
Minimizers and Machine Learning [7.998311072988401]
球面上の非函数の大域的最適化のための新しい倉本ビエク型モデルの実装について検討する。
本稿では,本論文で提案したアルゴリズムが寸法によく適合し,極めて多目的であることを示す数値実験を行った。
論文 参考訳（メタデータ） (2020-01-31T18:23:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。