論文の概要: Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport

• arxiv url: http://arxiv.org/abs/2103.05857v1
• Date: Wed, 10 Mar 2021 03:46:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-12 08:20:00.423181
• Title: Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport
• Title（参考訳）: 半緩和最適輸送のための高速ブロック座標Frank-Wolfeアルゴリズム
• Authors: Takumi Fukunaga, Hiroyuki Kasai
• Abstract要約: 最適輸送(OT)問題は、厳密な大量保存制約を持つ線形プログラミングの解を必要とする。 スパース解を与える高速ブロック座標Frank-Wolfe (BCFW) アルゴリズムを提案する。 色伝達問題における数値的な評価は,提案アルゴリズムが異なる設定で最先端のアルゴリズムより優れていることを示す。
• 参考スコア（独自算出の注目度）: 26.245086561385282
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport (OT), which provides a distance between two probability distributions by considering their spatial locations, has been applied to widely diverse applications. Computing an OT problem requires solution of linear programming with tight mass-conservation constraints. This requirement hinders its application to large-scale problems. To alleviate this issue, the recently proposed relaxed-OT approach uses a faster algorithm by relaxing such constraints. Its effectiveness for practical applications has been demonstrated. Nevertheless, it still exhibits slow convergence. To this end, addressing a convex semi-relaxed OT, we propose a fast block-coordinate Frank-Wolfe (BCFW) algorithm, which gives sparse solutions. Specifically, we provide their upper bounds of the worst convergence iterations, and equivalence between the linearization duality gap and the Lagrangian duality gap. Three fast variants of the proposed BCFW are also proposed. Numerical evaluations in color transfer problem demonstrate that the proposed algorithms outperform state-of-the-art algorithms across different settings.
• Abstract（参考訳）: 空間的位置を考慮した2つの確率分布間の距離を提供する最適輸送(OT)が,幅広い応用に応用されている。 OT問題の計算には、厳密な質量保存制約を持つ線形プログラミングの解決が必要である。 この要求は大規模問題への適用を妨げる。 この問題を軽減するため、最近提案された relaxed-ot アプローチでは、そのような制約を緩和することでより高速なアルゴリズムを使用する。 実用上の有効性が実証されている。 それでも、収束は遅い。 この目的のために, 凸半相対型otに対処し, 分散解を与える高速ブロック座標frank-wolfe (bcfw) アルゴリズムを提案する。 具体的には、最悪の収束反復の上限と、線型化双対性ギャップとラグランジアン双対性ギャップの等価性を提供する。 bcfwの3つの高速変種も提案されている。 色伝達問題における数値的な評価は,提案アルゴリズムが異なる設定で最先端のアルゴリズムより優れていることを示す。

関連論文リスト

• 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)
• Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem [20.661025590877774]
  凸半緩和最適輸送(OT)問題に対する高速ブロックコーディネートFrank-Wolfe (BCFW) アルゴリズムを提案する。 数値実験により,提案アルゴリズムはカラー転送に有効であり,最先端のアルゴリズムを超越することを示した。
  論文  参考訳（メタデータ） (2022-05-27T05:54:45Z)
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization [13.170519806372075]
  2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。 最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。 提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
  論文  参考訳（メタデータ） (2021-07-14T08:01:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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