論文の概要: A Sinkhorn-type Algorithm for Constrained Optimal Transport

• arxiv url: http://arxiv.org/abs/2403.05054v1
• Date: Fri, 8 Mar 2024 05:01:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-11 20:55:48.606260
• Title: A Sinkhorn-type Algorithm for Constrained Optimal Transport
• Title（参考訳）: 制約付き最適輸送のためのシンクホーン型アルゴリズム
• Authors: Xun Tang, Holakou Rahmanian, Michael Shavlovsky, Kiran Koshy Thekumparampil, Tesi Xiao, Lexing Ying
• Abstract要約: この研究は、等式制約と不等式制約を組み合わせた一般的なOT問題に焦点をあてる。 対応するエントロピー正規化の定式化を導出し、理論的保証によって支持される制約付きOT問題に対してシンクホーン型アルゴリズムを導入する。 全体として、この研究は、エントロピー最適輸送の最近の理論的および数値的な進歩と制約されたケースを体系的に組み合わせ、実践者は複雑なシナリオにおいて近似的な輸送計画を引き出すことができる。
• 参考スコア（独自算出の注目度）: 14.935188572016635
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Entropic optimal transport (OT) and the Sinkhorn algorithm have made it practical for machine learning practitioners to perform the fundamental task of calculating transport distance between statistical distributions. In this work, we focus on a general class of OT problems under a combination of equality and inequality constraints. We derive the corresponding entropy regularization formulation and introduce a Sinkhorn-type algorithm for such constrained OT problems supported by theoretical guarantees. We first bound the approximation error when solving the problem through entropic regularization, which reduces exponentially with the increase of the regularization parameter. Furthermore, we prove a sublinear first-order convergence rate of the proposed Sinkhorn-type algorithm in the dual space by characterizing the optimization procedure with a Lyapunov function. To achieve fast and higher-order convergence under weak entropy regularization, we augment the Sinkhorn-type algorithm with dynamic regularization scheduling and second-order acceleration. Overall, this work systematically combines recent theoretical and numerical advances in entropic optimal transport with the constrained case, allowing practitioners to derive approximate transport plans in complex scenarios.
• Abstract（参考訳）: エントロピック最適輸送(OT)とシンクホーンアルゴリズムは、機械学習の実践者が統計分布間の輸送距離を計算するための基本的なタスクを実践した。 本研究では, 等式制約と不等式制約を組み合わせることで, ot問題の一般クラスに注目する。 対応するエントロピー正規化の定式化を導出し、理論的保証によって支持される制約付きOT問題に対してシンクホーン型アルゴリズムを導入する。 最初に近似誤差をエントロピー正則化によって解くと、正則化パラメータの増加とともに指数関数的に減少する。 さらに,最適化手順をリアプノフ関数で特徴付けることにより,双対空間におけるシンクホーン型アルゴリズムの線形一階収束率を証明した。 弱エントロピー正則化の下で高速かつ高次収束を実現するために,動的正則化スケジューリングと2次加速度を伴うシンクホーン型アルゴリズムを補強する。 全体として、この研究は、エントロピー最適輸送の最近の理論と数値的な進歩と制約されたケースを体系的に組み合わせ、複雑なシナリオにおける近似輸送計画の導出を可能にする。

関連論文リスト

• Distributed Optimization via Energy Conservation Laws in Dilated Coordinates [5.35599092568615]
  本稿では,拡張座標における連続時間力学系の解析のためのエネルギー保存手法を提案する。 収束率を逆時間差係数で明示的に表すことができる。 その高速化された収束挙動は、実用的、大規模問題に対する様々な最先端分散最適化アルゴリズムに対してベンチマークされる。
  論文  参考訳（メタデータ） (2024-09-28T08:02:43Z)
• Optimal Transport with Tempered Exponential Measures [33.07787452859956]
  間接測度正規化を伴う指数族を一般化することは、非常に便利な中核となる。 我々の定式化は、不均衡な最適輸送問題設定に自然に適合する。
  論文  参考訳（メタデータ） (2023-09-07T20:53:23Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm [0.0]
  エントロピー正則化は、元の最適輸送問題を一般化する。 Kullback-Leibler の発散を一般の$f$-divergence に置き換えると、自然な一般化につながる。 本稿では,正規化された最適輸送コストとその勾配を計算するための実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T16:37:31Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。 このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
  論文  参考訳（メタデータ） (2020-06-06T19:28:14Z)

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

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