論文の概要: Dual-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clustering

• arxiv url: http://arxiv.org/abs/2501.18143v1
• Date: Thu, 30 Jan 2025 05:21:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-31 15:14:36.447643
• Title: Dual-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clustering
• Title（参考訳）: 2次元非線形最適輸送による小型切削クラスタリング
• Authors: Fangyuan Xie, Jinghui Yuan, Feiping Nie, Xuelong Li,
• Abstract要約: ミンカット問題を双有界非線形最適輸送問題として扱う。 また、Frank-Wolfe法に基づく双有界非線形最適輸送の解法を開発した。
• 参考スコア（独自算出の注目度）: 83.13494760649874
• License:
• Abstract: Min cut is an important graph partitioning method. However, current solutions to the min cut problem suffer from slow speeds, difficulty in solving, and often converge to simple solutions. To address these issues, we relax the min cut problem into a dual-bounded constraint and, for the first time, treat the min cut problem as a dual-bounded nonlinear optimal transport problem. Additionally, we develop a method for solving dual-bounded nonlinear optimal transport based on the Frank-Wolfe method (abbreviated as DNF). Notably, DNF not only solves the size constrained min cut problem but is also applicable to all dual-bounded nonlinear optimal transport problems. We prove that for convex problems satisfying Lipschitz smoothness, the DNF method can achieve a convergence rate of \(\mathcal{O}(\frac{1}{t})\). We apply the DNF method to the min cut problem and find that it achieves state-of-the-art performance in terms of both the loss function and clustering accuracy at the fastest speed, with a convergence rate of \(\mathcal{O}(\frac{1}{\sqrt{t}})\). Moreover, the DNF method for the size constrained min cut problem requires no parameters and exhibits better stability.
• Abstract（参考訳）: ミンカットは重要なグラフ分割法である。 しかし、ミンカット問題に対する現在の解法は、遅い速度、解決の難しさに悩まされ、しばしば単純な解に収束する。 これらの問題に対処するため、ミンカット問題を双有界制約に緩和し、初めて、ミンカット問題を双有界非線形最適輸送問題として扱う。 さらに,Frank-Wolfe法(略してDNF)に基づく双有界非線形最適輸送の解法を開発した。 特に、DNFはサイズ制限されたミンカット問題を解くだけでなく、全ての双有界非線形最適輸送問題にも適用できる。 リプシッツの滑らかさを満たす凸問題に対して、DNF法は(\mathcal{O}(\frac{1}{t})\)の収束率を達成することができる。 本稿では,DNF法をミンカット問題に適用し,損失関数とクラスタリング精度の両方を最速で達成し,収束速度は \(\mathcal{O}(\frac{1}{\sqrt{t}})\ とする。 さらに,DNF法ではパラメータを必要とせず,安定性が向上した。

関連論文リスト

• Fast Algorithm for Constrained Linear Inverse Problems [5.0490573482829335]
  我々は、ある原子ノルムが2次制約の下で最小化される制約付き線形逆問題(LIP)を考える。 凸正則性を改善した制約付きLIPの2つの等価な再構成を提案する。 FLIPSの2成分選択,圧縮センシング,画像デノーミングの古典的問題に対する性能を実証する。
  論文  参考訳（メタデータ） (2022-12-02T10:12:14Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Convex mixed-integer optimization with Frank-Wolfe methods [20.37026309402396]
  混合整数非線形最適化は理論的および計算的課題を示す。 本稿では,凸ノード緩和を用いた分岐結合アルゴリズムに基づいて,これらの問題の解法を提案する。
  論文  参考訳（メタデータ） (2022-08-23T14:46:54Z)
• 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)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• 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)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• PFNN: A Penalty-Free Neural Network Method for Solving a Class of Second-Order Boundary-Value Problems on Complex Geometries [4.620110353542715]
  本稿では,2次境界値問題のクラスを解くために,ペナルティのないニューラルネットワーク手法であるPFNNを提案する。 PFNNは、精度、柔軟性、堅牢性の点で、既存のいくつかのアプローチよりも優れている。
  論文  参考訳（メタデータ） (2020-04-14T13:36:14Z)

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

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