論文の概要: 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$ はガウス混合である。

関連論文リスト

• Efficiently Solving Discounted MDPs with Predictions on Transition Matrices [6.199300239433395]
  生成モデルに基づくDMDP(Discounted Markov Decision Processs)について検討した。 DMDPの解法において,遷移行列上での予測がサンプル効率をいかに向上させるかを検討するための新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2025-02-21T09:59:46Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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 quantisation of probability measures using maximum mean discrepancy [10.29438865750845]
  何人かの研究者は、確率測度を定量化する方法として、最大平均誤差 (MMD) の最小化を提案している。 離散的候補集合よりもMDDを優しく最小化する逐次アルゴリズムを考える。 本手法を各反復時の候補集合のミニバッチに適用する変種について検討する。
  論文  参考訳（メタデータ） (2020-10-14T13:09:48Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)

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

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