論文の概要: Stochastic Approximation versus Sample Average Approximation for
population Wasserstein barycenters
- arxiv url: http://arxiv.org/abs/2001.07697v9
- Date: Mon, 25 Oct 2021 14:16:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-07 23:54:48.364834
- Title: Stochastic Approximation versus Sample Average Approximation for
population Wasserstein barycenters
- Title（参考訳）: 集団ワッサーシュタインバリセンターにおける確率近似とサンプル平均近似
- Authors: Darina Dvinskikh
- Abstract要約: 機械学習と最適化のコミュニティには、凸リスク問題、すなわち最小化近似(SA)とサンプル平均近似(SAA)の2つの主要なアプローチがある。
ワッサーシュタイン・バリセンタ問題に対して、この優越性は逆転可能であることを示す。
最適輸送距離とエントロピー規則化された最適輸送距離に関して定義されたバリセンタを計算するSAおよびSAA実装の複雑さ境界を述べることで、詳細な比較を行う。
- 参考スコア（独自算出の注目度）: 2.3025186469300434
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the machine learning and optimization community, there are two main
approaches for the convex risk minimization problem, namely, the Stochastic
Approximation (SA) and the Sample Average Approximation (SAA). In terms of
oracle complexity (required number of stochastic gradient evaluations), both
approaches are considered equivalent on average (up to a logarithmic factor).
The total complexity depends on the specific problem, however, starting from
work \cite{nemirovski2009robust} it was generally accepted that the SA is
better than the SAA. % Nevertheless, in case of large-scale problems SA may run
out of memory as storing all data on one machine and organizing online access
to it can be impossible without communications with other machines. SAA in
contradistinction to SA allows parallel/distributed calculations. We show that
for the Wasserstein barycenter problem this superiority can be inverted. We
provide a detailed comparison by stating the complexity bounds for the SA and
the SAA implementations calculating barycenters defined with respect to optimal
transport distances and entropy-regularized optimal transport distances. As a
byproduct, we also construct confidence intervals for the barycenter defined
with respect to entropy-regularized optimal transport distances in the
$\ell_2$-norm. The preliminary results are derived for a general convex
optimization problem given by the expectation in order to have other
applications besides the Wasserstein barycenter problem.
- Abstract（参考訳）: 機械学習と最適化のコミュニティでは、凸リスク最小化問題(Stochastic Approximation (SA)とSample Average Approximation (SAA)の2つの主要なアプローチがある。
オラクル複雑性(要求された確率勾配評価数)の観点では、両方のアプローチは平均(対数係数まで)で等価であると考えられている。
全体の複雑性は特定の問題に依存するが、仕事から始めると、sa は saa よりも優れていると一般に受け入れられた。
しかし、大規模な問題が発生した場合、saは1台のマシンにすべてのデータを保存し、他のマシンとの通信がなければ、オンラインアクセスを組織することは不可能である。
SA に反比例する SAA は並列/分散計算を可能にする。
我々は、wasserstein barycenter問題に対して、この優越性が逆転可能であることを示す。
最適輸送距離とエントロピー規則化された最適輸送距離に関して定義されたバリセンタを計算するSAおよびSAA実装の複雑さ境界を述べることで、詳細な比較を行う。
副産物として、entropy-regularized optimal transport distances in the $\ell_2$-norm に関して定義されるbarycenterの信頼区間も構築する。
予備結果は、ワッサーシュタイン・バリセンタ問題以外の応用を得るために期待値によって与えられる一般的な凸最適化問題に対して導かれる。
関連論文リスト
- Mean field initialization of the Annealed Importance Sampling algorithm for an efficient evaluation of the Partition Function of Restricted Boltzmann Machines [0.0]
Annealed Importance Smpling (AIS)は、システムのパーティション関数を推定するツールである。
本研究では,適切な選択した平均場開始確率分布を用いることで,推定の品質と計算コストを両立させることができることを示す。
計算コストが比較的低いAISを用いて分割関数を推定するには,これらがよい出発点である。
論文 参考訳（メタデータ） (2024-04-17T10:22:03Z) - Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming [0.6906005491572401]
本稿では,凸あるいは強凸プログラミング問題の解法におけるサンプル平均近似(SAA)について検討する。
SAAのサンプルの複雑さは、計量エントロピーの定量化から完全に解放されることを示している。
本稿では, SAA が証明可能な有効性を維持している非リプシッツ的シナリオについて検討する。
論文 参考訳（メタデータ） (2024-01-01T04:35:53Z) - Improved dimension dependence of a proximal algorithm for sampling [16.147290924171692]
そこで本研究では,すべての古典的設定において,より優れた複雑性境界を実現するサンプリングアルゴリズムを提案する。
提案アルゴリズムは,2021年に導入した近位サンプルを用いた。
強い対数対数分布の場合、この手法は温度開始を伴わずに$tildemathcalO(kappa d1/2)$の複雑さを持つ。
LSI を満たす分布に対して、我々は $tilde MathcalO(hat kappa d1/2)$ ここで $hat kappa$ は滑らかさと滑らかさの比である。
論文 参考訳（メタデータ） (2023-02-20T16:44:48Z) - Statistical, Robustness, and Computational Guarantees for Sliced
Wasserstein Distances [18.9717974398864]
スライスされたワッサーシュタイン距離は古典的なワッサーシュタイン距離の性質を保ちながら、高次元での計算と推定によりスケーラブルである。
このスケーラビリティを, (i) 経験的収束率, (ii) データの汚染に対する堅牢性, (iii) 効率的な計算方法という3つの重要な側面から定量化する。
論文 参考訳（メタデータ） (2022-10-17T15:04:51Z) - Fixed-point iterations for several dissimilarity measure barycenters in
the Gaussian case [69.9674326582747]
目標追跡とセンサ融合の文脈では、多数のガウス密度を扱うことは珍しくない。
FPI(Fixed-Point Iterations)は、いくつかの異なる尺度に従って、バリセンタの計算を行う。
論文 参考訳（メタデータ） (2022-05-10T11:12:12Z) - Near-optimal estimation of smooth transport maps with kernel
sums-of-squares [81.02564078640275]
滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。
生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。
そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-03T13:45:36Z) - Continuous Regularized Wasserstein Barycenters [51.620781112674024]
正規化ワッサーシュタイン・バリセンタ問題に対する新しい双対定式化を導入する。
我々は、強い双対性を確立し、対応する主対関係を用いて、正規化された輸送問題の双対ポテンシャルを用いて暗黙的にバリセンターをパラメトリゼーションする。
論文 参考訳（メタデータ） (2020-08-28T08:28:06Z) - On Projection Robust Optimal Transport: Sample Complexity and Model
Misspecification [101.0377583883137]
射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。
私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。
次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
論文 参考訳（メタデータ） (2020-06-22T14:35:33Z) - $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a
Robust Divergence Estimator [95.71091446753414]
最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。
本手法は既存の不一致対策よりも高いロバスト性を実現する。
論文 参考訳（メタデータ） (2020-06-13T06:09:27Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。