論文の概要: Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem

• arxiv url: http://arxiv.org/abs/2205.13766v1
• Date: Fri, 27 May 2022 05:54:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-30 13:27:14.051959
• Title: Block-coordinate Frank-Wolfe algorithm and convergence analysis for semi-relaxed optimal transport problem
• Title（参考訳）: 半緩和最適輸送問題に対するブロック座標Frank-Wolfeアルゴリズムと収束解析
• Authors: Takumi Fukunaga and Hiroyuki Kasai
• Abstract要約: 凸半緩和最適輸送(OT)問題に対する高速ブロックコーディネートFrank-Wolfe (BCFW) アルゴリズムを提案する。 数値実験により,提案アルゴリズムはカラー転送に有効であり,最先端のアルゴリズムを超越することを示した。
• 参考スコア（独自算出の注目度）: 20.661025590877774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The optimal transport (OT) problem has been used widely for machine learning. It is necessary for computation of an OT problem to solve linear programming with tight mass-conservation constraints. These constraints prevent its application to large-scale problems. To address this issue, loosening such constraints enables us to propose the relaxed-OT method using a faster algorithm. This approach has demonstrated its effectiveness for applications. However, it remains slow. As a superior alternative, we propose a fast block-coordinate Frank-Wolfe (BCFW) algorithm for a convex semi-relaxed OT. Specifically, we prove their upper bounds of the worst convergence iterations, and equivalence between the linearization duality gap and the Lagrangian duality gap. Additionally, we develop two fast variants of the proposed BCFW. Numerical experiments have demonstrated that our proposed algorithms are effective for color transfer and surpass state-of-the-art algorithms. This report presents a short version of arXiv:2103.05857.
• Abstract（参考訳）: 最適輸送(OT)問題は機械学習に広く用いられている。 厳密な大量保存制約で線形プログラミングを解くためには,OT問題の計算が必要である。 これらの制約は大規模な問題への適用を妨げる。 このような制約を緩めることで、より高速なアルゴリズムを用いて緩和OT法を提案することができる。 このアプローチは、アプリケーションの有効性を示している。 しかし、それはまだ遅い。 優れた代替手段として、凸半緩和OTに対する高速ブロック座標Frank-Wolfe (BCFW)アルゴリズムを提案する。 具体的には、最悪の収束反復の上限と、線型化双対性ギャップとラグランジアン双対性ギャップの等価性を証明する。 さらに,提案するbcfwの高速変種を2種類開発した。 数値実験により,提案アルゴリズムはカラー転送に有効であり,最先端アルゴリズムを超越することを示した。 本報告では、arXiv:2103.05857の短いバージョンを示す。

関連論文リスト

• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。 まず、この方法はスティーフェル多様体に拡張される。 また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
  論文  参考訳（メタデータ） (2023-03-29T07:36:54Z)
• 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)
• An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem [2.1485350418225244]
  線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。 PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
  論文  参考訳（メタデータ） (2022-03-02T01:16:10Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport [26.245086561385282]
  最適輸送(OT)問題は、厳密な大量保存制約を持つ線形プログラミングの解を必要とする。 スパース解を与える高速ブロック座標Frank-Wolfe (BCFW) アルゴリズムを提案する。 色伝達問題における数値的な評価は,提案アルゴリズムが異なる設定で最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2021-03-10T03:46:29Z)
• 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)

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

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