論文の概要: An Accelerated Stochastic Algorithm for Solving the Optimal Transport
Problem
- arxiv url: http://arxiv.org/abs/2203.00813v1
- Date: Wed, 2 Mar 2022 01:16:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-03 16:07:05.075335
- Title: An Accelerated Stochastic Algorithm for Solving the Optimal Transport
Problem
- Title（参考訳）: 最適輸送問題の解法のための高速化確率アルゴリズム
- Authors: Yiling Xie, Yiling Luo, Xiaoming Huo
- Abstract要約: PDASGDは性質上実装が容易である: イテレーション毎の計算は他の非確率的な計算よりもはるかに高速である。
合成データと実データの両方で数値実験を行い,PDASGDの効率向上を実証した。
- 参考スコア（独自算出の注目度）: 2.1485350418225244
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel accelerated stochastic algorithm -- primal-dual
accelerated stochastic gradient descent with variance reduction (PDASGD) -- for
solving the optimal transport (OT) problem between two discrete distributions.
PDASGD can also be utilized to compute for the Wasserstein barycenter (WB) of
multiple discrete distributions. In both the OT and WB cases, the proposed
algorithm enjoys the best-known convergence rate (in the form of order of
computational complexity) in the literature. PDASGD is easy to implement in
nature, due to its stochastic property: computation per iteration can be much
faster than other non-stochastic counterparts. We carry out numerical
experiments on both synthetic and real data; they demonstrate the improved
efficiency of PDASGD.
- Abstract（参考訳）: 本研究では,2つの離散分布間の最適移動量(ot)問題を解くために,分散還元法(pdasgd)を用いた主元-双進加速度確率勾配降下法を提案する。
PDASGDは複数の離散分布のWasserstein Barycenter(WB)の計算にも利用できる。
OTとWBのいずれの場合も、提案アルゴリズムは文学において最もよく知られた収束率(計算複雑性の順序という形で)を享受する。
PDASGDは確率的な性質のため、本質的に実装が容易である:イテレーション毎の計算は他の非確率的な計算よりもはるかに高速である。
合成データと実データの両方について数値実験を行い,pdasgdの効率改善を実証した。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳（メタデータ） (2023-01-23T19:13:25Z) - A stochastic linearized proximal method of multipliers for convex
stochastic optimization with expectation constraints [8.133190610747974]
計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。
予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
論文 参考訳（メタデータ） (2021-06-22T07:24:17Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Distributed Stochastic Consensus Optimization with Momentum for
Nonconvex Nonsmooth Problems [45.88640334610308]
本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。
提案アルゴリズムは,過度な通信を実現することができることを示す。
提案アルゴリズムの有効性を示す実験を行った。
論文 参考訳（メタデータ） (2020-11-10T13:12:21Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。