論文の概要: Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components

• arxiv url: http://arxiv.org/abs/2110.14859v1
• Date: Thu, 28 Oct 2021 02:36:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-29 16:27:16.027884
• Title: Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components
• Title（参考訳）: 心電図に基づくコンポーネントの近似分解可能部分モジュラー関数最小化
• Authors: Nate Veldt, Austin R. Benson, Jon Kleinberg
• Abstract要約: 限られたサポートの単純な部分モジュラ関数の和を最小化することは、機械学習に多くの応用がある。 我々は、和の成分が濃度ベースである場合の高速な手法を開発し、入力集合のサイズにのみ依存する。 この問題に対する最初の近似アルゴリズムを開発し、この近似はスパースグラフカット問題への還元により迅速に計算できる。
• 参考スコア（独自算出の注目度）: 30.33731479053404
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minimizing a sum of simple submodular functions of limited support is a special case of general submodular function minimization that has seen numerous applications in machine learning. We develop fast techniques for instances where components in the sum are cardinality-based, meaning they depend only on the size of the input set. This variant is one of the most widely applied in practice, encompassing, e.g., common energy functions arising in image segmentation and recent generalized hypergraph cut functions. We develop the first approximation algorithms for this problem, where the approximations can be quickly computed via reduction to a sparse graph cut problem, with graph sparsity controlled by the desired approximation factor. Our method relies on a new connection between sparse graph reduction techniques and piecewise linear approximations to concave functions. Our sparse reduction technique leads to significant improvements in theoretical runtimes, as well as substantial practical gains in problems ranging from benchmark image segmentation tasks to hypergraph clustering problems.
• Abstract（参考訳）: 限られたサポートの単純部分モジュラー関数の和を最小化することは、機械学習で多くの応用が見られた一般部分モジュラー関数最小化の特別な場合である。 我々は、和の成分が濃度ベースである場合の高速な手法を開発し、入力集合のサイズにのみ依存する。 この変種は、画像分割や最近の一般化されたハイパーグラフ切断関数に生じる共通のエネルギー関数など、実際に最も広く適用されているものの一つである。 本研究では,この問題に対する最初の近似アルゴリズムを開発し,その近似アルゴリズムをスパースグラフカット問題に還元することで近似を高速に計算し,所望の近似係数でグラフスパーシティを制御する。 提案手法は,スパースグラフの削減手法と,凹凸関数に対する分割線形近似との新たな接続に依存する。 我々のスパース低減技術は, 画像分割タスクからハイパーグラフクラスタリング問題に至るまで, 理論的ランタイムの大幅な改善と, 実質的な向上をもたらす。

関連論文リスト

• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals [8.140698535149042]
  本稿では,その隣接行列を推定することにより,スパース重み付きグラフを学習するアルゴリズムを提案する。 提案アルゴリズムは,本論文におけるいくつかの既存手法よりも,平均反復回数の観点から,より高速に収束することを示す。
  論文  参考訳（メタデータ） (2022-02-06T17:06:13Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Decomposable Submodular Function Minimization via Maximum Flow [6.993741009069205]
  本稿では,分解可能な部分モジュラー関数の最小化に対する離散最適化と連続最適化のアプローチを橋渡しする。 我々は、最大フローオラクルに対する多数の呼び出しに還元することで、この問題に対する実行時間を改善する。
  論文  参考訳（メタデータ） (2021-03-05T18:46:38Z)
• Efficient Consensus Model based on Proximal Gradient Method applied to Convolutional Sparse Problems [2.335152769484957]
  我々は、勾配近似(PG)アプローチに基づく効率的なコンセンサスアルゴリズムの理論解析を導出し、詳述する。 提案アルゴリズムは、異常検出タスクに対する別の特別な畳み込み問題にも適用できる。
  論文  参考訳（メタデータ） (2020-11-19T20:52:48Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Fast Convex Relaxations using Graph Discretizations [13.977100716044102]
  マッチングと視覚問題はコンピュータ・コンピューティング・アプリケーションの基本である。 応用技術は、実用的な応用においてその実現可能性を減らすための重要な計算努力が伴う。 このセットアップにより、SLICやCut-Pursuitによって構築された問題に忠実に取り組むことができます。
  論文  参考訳（メタデータ） (2020-04-23T11:14:38Z)
• Robust Submodular Minimization with Applications to Cooperative Modeling [0.0]
  本稿では,制約を考慮したロバストな部分モジュラー最小化問題について検討する。 制約付き部分モジュラー最小化は、画像セグメンテーションにおける協調的カット、画像対応における協調的マッチングなど、いくつかの応用で発生する。
  論文  参考訳（メタデータ） (2020-01-25T20:40:37Z)

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

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