論文の概要: Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2501.14635v1
• Date: Fri, 24 Jan 2025 16:55:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-27 14:58:19.500640
• Title: Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization
• Title（参考訳）: 非凸凹極小最適化による最適輸送バリセンタ
• Authors: Kaheon Kim, Rentian Yao, Changbo Zhu, Xiaohui Chen,
• Abstract要約: Wasserstein-Descent $dotmathbbH1$-Ascent (WDHA)アルゴリズムは、正確なバリセンタを計算する。 ほぼ線形時間 $O(m logm)$ と線型空間複雑性 $O(m)$ をバリセンタ問題を近似するための原始双対アルゴリズムとして提示する。
• 参考スコア（独自算出の注目度）: 11.344401324787974
• License:
• Abstract: The optimal transport barycenter (a.k.a. Wasserstein barycenter) is a fundamental notion of averaging that extends from the Euclidean space to the Wasserstein space of probability distributions. Computation of the unregularized barycenter for discretized probability distributions on point clouds is a challenging task when the domain dimension $d > 1$. Most practical algorithms for approximating the barycenter problem are based on entropic regularization. In this paper, we introduce a nearly linear time $O(m \log{m})$ and linear space complexity $O(m)$ primal-dual algorithm, the Wasserstein-Descent $\dot{\mathbb{H}}^1$-Ascent (WDHA) algorithm, for computing the exact barycenter when the input probability density functions are discretized on an $m$-point grid. The key success of the WDHA algorithm hinges on alternating between two different yet closely related Wasserstein and Sobolev optimization geometries for the primal barycenter and dual Kantorovich potential subproblems. Under reasonable assumptions, we establish the convergence rate and iteration complexity of WDHA to its stationary point when the step size is appropriately chosen. Superior computational efficacy, scalability, and accuracy over the existing Sinkhorn-type algorithms are demonstrated on high-resolution (e.g., $1024 \times 1024$ images) 2D synthetic and real data.
• Abstract（参考訳）: 最適な輸送バリーセンター(Wasserstein barycenter)は、ユークリッド空間から確率分布のワッサーシュタイン空間へ広がる平均の概念である。 点雲上の離散化確率分布に対する非正規化バリセンタの計算は、ドメイン次元が$d > 1$である場合、難しい作業である。 バリセンタ問題を近似するための最も実用的なアルゴリズムはエントロピー正則化に基づいている。 本稿では、入力確率密度関数が$m$-pointグリッド上で離散化されるときの正確なバリセンタを計算するために、ほぼ線形時間$O(m \log{m})$および線形空間複雑性$O(m)$プリミナルデュアルアルゴリズム、Wasserstein-Descent$\dot{\mathbb{H}}^1$-Ascent (WDHA)アルゴリズムを導入する。 WDHAアルゴリズムの鍵となる成功は、2つの異なる関係を持つワッサーシュタインとソボレフ最適化測度を主バリセンターと二重カントロビッチポテンシャルサブプロブレムで交互に比較することにある。 合理的な仮定の下では、ステップサイズが適切に選択された場合、WDHAの収束率と反復複雑性を定常点に設定する。 既存のシンクホーン型アルゴリズムよりも優れた計算効率、スケーラビリティ、精度を2D合成および実データに高分解能(例:1024 \times 1024$ image)で示す。

関連論文リスト

• 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)
• Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers [10.259254824702555]
  我々は、外乱が存在する場合に、$k$-sparse Wasserstein Barycenter問題を研究する。 既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張することはできない。 本稿では,外乱問題のある$k$sparse WBに対して定数近似係数を求めるクラスタリングに基づくLP法を提案する。
  論文  参考訳（メタデータ） (2024-04-20T15:01:35Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters [0.0]
  N$離散確率測度に対する2乗ユークリッドコストで, マルチマルジナル最適輸送(MOT)の解を近似する2つのアルゴリズムを提案する。 高速で、メモリ効率が高く、実装も簡単で、どのスパースOTソルバでもブラックボックスとして使用することができる。
  論文  参考訳（メタデータ） (2022-02-02T10:59:54Z)
• Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
  本稿では,Wasserstein Barycenter問題に対する次元還元手法について検討する。 ランダム化次元減少は、その問題を$d$と$k$に独立に次元$O(log n)$の空間にマッピングするために利用できることを示す。 また、Wasserstein Barycenter問題に対するコアセットの構成も提供し、入力分布を著しく減少させる。
  論文  参考訳（メタデータ） (2021-10-18T02:57:25Z)
• Projection Robust Wasserstein Barycenter [36.97843660480747]
  ワッサースタイン・バリセンターの 近似は 次元の呪いのため 数値的に困難です 本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
  論文  参考訳（メタデータ） (2021-02-05T19:23:35Z)
• Continuous Regularized Wasserstein Barycenters [51.620781112674024]
  正規化ワッサーシュタイン・バリセンタ問題に対する新しい双対定式化を導入する。 我々は、強い双対性を確立し、対応する主対関係を用いて、正規化された輸送問題の双対ポテンシャルを用いて暗黙的にバリセンターをパラメトリゼーションする。
  論文  参考訳（メタデータ） (2020-08-28T08:28:06Z)
• 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)
• Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks [15.171726731041055]
  ワッサーシュタイン・バリーセンター(Wasserstein Barycenter)は、与えられた確率分布の集合の重み付き平均を表す原理的なアプローチである。 本稿では,Wasserstein Barycentersを機械学習の高次元的応用を目的とした,スケーラブルな新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-08T22:41:18Z)

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

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