論文の概要: On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport

• arxiv url: http://arxiv.org/abs/2109.15030v2
• Date: Fri, 1 Oct 2021 01:00:36 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-04 11:23:01.129813
• Title: On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport
• Title（参考訳）: 等値および最適輸送のための投影交互最大化の収束について
• Authors: Minhui Huang, Shiqian Ma and Lifeng Lai
• Abstract要約: 本稿では,多くの応用例を有する等価・最適輸送(EOT)問題について検討する。 離散分布の場合、EOT問題は線形プログラム(LP)として定式化できる。 このLPは一般解法では禁止的に大きいため、Scetbon etal citescetbonequitable はエントロピー正則化を加えることによって問題を摂動することを示唆している。 彼らは、エントロピー正規化EOTの双対を解くための予測交互化アルゴリズム(PAM)を提案した。
• 参考スコア（独自算出の注目度）: 36.97843660480747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon \etal \cite{scetbon2021equitable} suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating maximization algorithm (PAM) to solve the dual of the entropy regularized EOT. In this paper, we provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that can numerically improve the performance of PAM. Results in this paper may shed lights on block coordinate (gradient) descent methods for general optimization problems.
• Abstract（参考訳）: 本稿では、公平な分割問題や複数のエージェントによる最適輸送問題など多くの応用がある等式と最適輸送問題(eot)について述べる。 離散分布の場合、eot問題は線形プログラム(lp)として定式化することができる。 この LP は一般の LP ソルバに対して禁止的に大きいため、Scetbon \etal \cite{scetbon2021equitable} はエントロピー正規化を加えることで問題を摂動することを示唆する。 彼らは、エントロピー正規化 eot の双対を解くために、計画的交互最大化アルゴリズム (pam) を提案した。 本稿では,PAMの収束解析について述べる。 元の eot 問題の原始解を構築するための新しい丸め手順が提案されている。 また,PAMの性能を数値的に向上する外挿手法を取り入れたPAMの変種を提案する。 本論文の結果は,一般最適化問題に対するブロック座標(次)降下法に光を流すことができる。

関連論文リスト

• Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings [7.6275971668447005]
  消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。 本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。 さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
  論文  参考訳（メタデータ） (2024-02-22T05:48:54Z)
• Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
  任意のOTコスト関数に対して連続的エントロピーOT(EOT)バリセンタを近似する新しいアルゴリズムを提案する。 本手法は、弱いOTに基づくEOT問題の二重再構成に基づいている。
  論文  参考訳（メタデータ） (2023-10-02T11:24:36Z)
• Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems [3.038642416291856]
  クラス確率分布上に定義された複合目的関数を最小化する一般的な最適化問題を考える。 本稿では,正規分布最適化問題の解法として,モロー・吉田変分輸送(MYVT)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-07-31T01:14:42Z)
• Safe Screening for Unbalanced Optimal Transport [17.489075240435348]
  セーフスクリーニングの UOT 問題への適用可能性について,$ell$-penalty と KL-penalty を用いて実証した。 具体的には、新しい近似射影、楕円型安全な領域、および2つの超平面緩和法を提案する。 これらの拡張により、アルゴリズムの複雑さを変えることなく、UOTのスクリーニング効率が大幅に向上した。
  論文  参考訳（メタデータ） (2023-07-01T06:22:14Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。 提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。 大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
  論文  参考訳（メタデータ） (2022-11-02T14:35:13Z)
• A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization [7.483040617090451]
  本研究では,ソフトマックスパラメータ化の下で,エントロピー規則化制約付きマルコフ決定過程(CMDP)について検討する。 我々の理論的解析は、ラグランジアン双対函数は滑らかであり、ラグランジアン双対性ギャップは原始性ギャップと制約違反に分解できることを示している。
  論文  参考訳（メタデータ） (2021-10-17T21:26:40Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Variational Optimization for the Submodular Maximum Coverage Problem [11.734438054316147]
  この問題に対する最初の変分近似は、ネムハウザーの発散に基づくものである。 いくつかの公開データセットといくつかのアプリケーションタスクでそれを実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-10T00:50:25Z)
• Joint Wasserstein Distribution Matching [89.86721884036021]
  JDM問題(Joint Distribution matching)は、2つのドメインの関節分布を一致させるために双方向マッピングを学習することを目的としており、多くの機械学習およびコンピュータビジョンアプリケーションで発生している。 2つの領域における関節分布のワッサーシュタイン距離を最小化することにより、JDM問題に対処することを提案する。 そこで我々は,難解な問題を簡単な最適化問題に還元する重要な定理を提案し,その解法を開発した。
  論文  参考訳（メタデータ） (2020-03-01T03:39:00Z)

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

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