論文の概要: Stochastic Saddle-Point Optimization for Wasserstein Barycenters
- arxiv url: http://arxiv.org/abs/2006.06763v3
- Date: Thu, 2 Dec 2021 21:57:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 13:13:15.733218
- Title: Stochastic Saddle-Point Optimization for Wasserstein Barycenters
- Title(参考訳): Wasserstein Barycenter の確率的サドル点最適化
- Authors: Daniil Tiapkin, Alexander Gasnikov and Pavel Dvurechensky
- Abstract要約: オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
- 参考スコア(独自算出の注目度): 69.68068088508505
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the population Wasserstein barycenter problem for random
probability measures supported on a finite set of points and generated by an
online stream of data. This leads to a complicated stochastic optimization
problem where the objective is given as an expectation of a function given as a
solution to a random optimization problem. We employ the structure of the
problem and obtain a convex-concave stochastic saddle-point reformulation of
this problem. In the setting when the distribution of random probability
measures is discrete, we propose a stochastic optimization algorithm and
estimate its complexity. The second result, based on kernel methods, extends
the previous one to the arbitrary distribution of random probability measures.
Moreover, this new algorithm has a total complexity better than the Stochastic
Approximation approach combined with the Sinkhorn algorithm in many cases. We
also illustrate our developments by a series of numerical experiments.
- Abstract(参考訳): オンラインデータストリームによって生成される有限個の点からなるランダム確率測度に対する集団Wasserstein Barycenter問題について考察する。
これは、目的がランダムな最適化問題の解として与えられる関数の期待として与えられる複雑な確率的最適化問題につながる。
我々は,この問題の構造を用いて,凸凹型確率的サドル点再構成を求める。
確率測度の分布が離散的であれば,確率的最適化アルゴリズムを提案し,その複雑性を推定する。
第2の結果は、カーネル法に基づいて、前の結果を確率測度の任意の分布に拡張する。
さらに, このアルゴリズムは, 確率近似法よりも複雑度が高く, 多くの場合, シンクホーン法が組み合わさっている。
また,一連の数値実験によって,我々の発展を解説する。
関連論文リスト
- Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。
我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
論文 参考訳(メタデータ) (2024-03-29T21:12:25Z) - Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳(メタデータ) (2023-12-24T07:46:37Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳(メタデータ) (2023-06-21T17:03:22Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳(メタデータ) (2022-10-23T23:23:23Z) - Distributed stochastic proximal algorithm with random reshuffling for
non-smooth finite-sum optimization [28.862321453597918]
非滑らかな有限サム最小化は機械学習の基本的な問題である。
本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
論文 参考訳(メタデータ) (2021-11-06T07:29:55Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳(メタデータ) (2021-10-07T17:51:10Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。
提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
論文 参考訳(メタデータ) (2020-12-07T14:58:16Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。