論文の概要: An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem

• arxiv url: http://arxiv.org/abs/2203.00813v3
• Date: Tue, 30 May 2023 00:15:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 03:18:06.724895
• Title: An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem
• Title（参考訳）: 最適輸送問題の解法のための高速化確率アルゴリズム
• Authors: Yiling Xie, Yiling Luo, Xiaoming Huo
• Abstract要約: 線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。 PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
• 参考スコア（独自算出の注目度）: 2.1485350418225244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A primal-dual accelerated stochastic gradient descent with variance reduction algorithm (PDASGD) is proposed to solve linear-constrained optimization problems. PDASGD could be applied to solve the discrete optimal transport (OT) problem and enjoys the best-known computational complexity -- $\widetilde{\mathcal{O}}(n^2/\epsilon)$, where $n$ is the number of atoms, and $\epsilon>0$ is the accuracy. In the literature, some primal-dual accelerated first-order algorithms, e.g., APDAGD, have been proposed and have the order of $\widetilde{\mathcal{O}}(n^{2.5}/\epsilon)$ for solving the OT problem. To understand why our proposed algorithm could improve the rate by a factor of $\widetilde{\mathcal{O}}(\sqrt{n})$, the conditions under which our stochastic algorithm has a lower order of computational complexity for solving linear-constrained optimization problems are discussed. It is demonstrated that the OT problem could satisfy the aforementioned conditions. Numerical experiments demonstrate superior practical performances of the proposed PDASGD algorithm for solving the OT problem.
• Abstract（参考訳）: 線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた原始-双対促進確率勾配降下法を提案する。 PDASGDは離散的最適輸送(OT)問題を解くために適用でき、最もよく知られた計算複雑性 -$\widetilde{\mathcal{O}}(n^2/\epsilon)$、$n$は原子の数、$\epsilon>0$は正確である。 文献では、APDAGDのような原始双対加速一階法が提案され、OT問題を解くために$\widetilde{\mathcal{O}}(n^{2.5}/\epsilon)$が与えられた。 提案アルゴリズムが$\widetilde{\mathcal{O}}(\sqrt{n})$の係数で改善できる理由を理解するために,線形制約最適化問題の解法として,確率的アルゴリズムがより低い計算複雑性を有する条件について議論する。 その結果,OT問題は上記の条件を満たすことができた。 数値実験により,OT問題の解法として提案した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)

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

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