論文の概要: Performance analysis of greedy algorithms for minimising a Maximum Mean
Discrepancy
- arxiv url: http://arxiv.org/abs/2101.07564v1
- Date: Tue, 19 Jan 2021 11:18:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-23 04:21:18.550481
- Title: Performance analysis of greedy algorithms for minimising a Maximum Mean
Discrepancy
- Title(参考訳): 最大平均差最小化のためのグリードアルゴリズムの性能解析
- Authors: Luc Pronzato
- Abstract要約: MMDによって測定された有限サンプルサイズ近似誤差はSBQに対して1/n$まで減少することを示す。
近似誤差の上限はSBQより若干優れているが、他の手法の方がはるかに高速である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We analyse the performance of several iterative algorithms for the
quantisation of a probability measure $\mu$, based on the minimisation of a
Maximum Mean Discrepancy (MMD). Our analysis includes kernel herding, greedy
MMD minimisation and Sequential Bayesian Quadrature (SBQ). We show that the
finite-sample-size approximation error, measured by the MMD, decreases as $1/n$
for SBQ and also for kernel herding and greedy MMD minimisation when using a
suitable step-size sequence. The upper bound on the approximation error is
slightly better for SBQ, but the other methods are significantly faster, with a
computational cost that increases only linearly with the number of points
selected. This is illustrated by two numerical examples, with the target
measure $\mu$ being uniform (a space-filling design application) and with $\mu$
a Gaussian mixture.
- Abstract(参考訳): 我々は,最大平均離散性(MMD)の最小化に基づいて,確率測度$\mu$の量子化のための複数の反復アルゴリズムの性能を解析する。
我々の分析では、カーネルハーディング、greedy MMD最小化、Sequential Bayesian Quadrature (SBQ)がある。
MMDが測定した有限サンプルサイズ近似誤差はSBQに対して1/n$と減少し,また,ステップサイズシーケンスを使用する場合のカーネルハーディングやグリーディーMDDの最小化にも有効であることを示す。
近似誤差の上界はsbqより若干優れているが、他の手法の方がかなり高速であり、計算コストは選択した点数で線形に増加するだけである。
これは2つの数値的な例で示され、目標測度 $\mu$ は一様(空間充填設計のアプリケーション)であり、$\mu$ はガウス混合である。
関連論文リスト
- Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-03-03T14:39:33Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Fast Projected Newton-like Method for Precision Matrix Estimation with
Nonnegative Partial Correlations [19.767301759060263]
本稿では,よく設計されたニュートン方向を組み込んだ新しいニュートン型アルゴリズムを提案する。
提案したニュートン型アルゴリズムが問題の最小化に収束することを証明する。
合成および実世界のデータを含む実験により,提案アルゴリズムの効率は著しく向上した。
論文 参考訳(メタデータ) (2021-12-03T14:39:10Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳(メタデータ) (2021-09-08T18:00:05Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳(メタデータ) (2021-06-22T07:24:17Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳(メタデータ) (2021-03-04T19:01:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。