論文の概要: 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の信頼区間も構築する。
予備結果は、ワッサーシュタイン・バリセンタ問題以外の応用を得るために期待値によって与えられる一般的な凸最適化問題に対して導かれる。
関連論文リスト
- The Curse of Memory in Stochastic Approximation: Extended Version [1.534667887016089]
適応制御の初期から、制御システムコミュニティ内で近似の理論と応用が成長してきた。
近年の結果, (十分小さい) ステップサイズ$alpha>0$のSAの顕著な性能が確認されている。
論文 参考訳(メタデータ) (2023-09-06T12:22:32Z) - 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) - Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators
with Massive Data [20.79270369203348]
既存の手法は主に高い計算効率のために置換されたサブサンプリングに焦点を当てている。
まず,準類似度推定の文脈で最適なサブサンプリング確率を導出する。
我々は,分散サブサンプリングフレームワークを開発し,全データの小さなパーティションで統計を同時に計算する。
論文 参考訳(メタデータ) (2020-05-21T02:46:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。