論文の概要: Decomposable Submodular Function Minimization via Maximum Flow
- arxiv url: http://arxiv.org/abs/2103.03868v1
- Date: Fri, 5 Mar 2021 18:46:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-08 14:37:15.408037
- Title: Decomposable Submodular Function Minimization via Maximum Flow
- Title（参考訳）: 最大流れによる分解可能部分モジュラー関数最小化
- Authors: Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski,
Adrian Vladu
- Abstract要約: 本稿では,分解可能な部分モジュラー関数の最小化に対する離散最適化と連続最適化のアプローチを橋渡しする。
我々は、最大フローオラクルに対する多数の呼び出しに還元することで、この問題に対する実行時間を改善する。
- 参考スコア（独自算出の注目度）: 6.993741009069205
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper bridges discrete and continuous optimization approaches for
decomposable submodular function minimization, in both the standard and
parametric settings.
We provide improved running times for this problem by reducing it to a number
of calls to a maximum flow oracle. When each function in the decomposition acts
on $O(1)$ elements of the ground set $V$ and is polynomially bounded, our
running time is up to polylogarithmic factors equal to that of solving maximum
flow in a sparse graph with $O(\vert V \vert)$ vertices and polynomial integral
capacities.
We achieve this by providing a simple iterative method which can optimize to
high precision any convex function defined on the submodular base polytope,
provided we can efficiently minimize it on the base polytope corresponding to
the cut function of a certain graph that we construct. We solve this
minimization problem by lifting the solutions of a parametric cut problem,
which we obtain via a new efficient combinatorial reduction to maximum flow.
This reduction is of independent interest and implies some previously unknown
bounds for the parametric minimum $s,t$-cut problem in multiple settings.
- Abstract（参考訳）: 本稿では,分解可能部分モジュラ関数最小化のための離散的かつ連続的な最適化手法を,標準およびパラメトリック設定の両方で橋渡しする。
我々は、最大フローオラクルへの多数の呼び出しに還元することで、この問題に対する実行時間を改善する。
分解の各関数が、$V$ の $O(1)$ 要素上で作用し、多項式有界であるとき、私達の実行時間は、$O(\vert V \vert)$ 頂点と多項式積分容量を持つスパースグラフにおける最大フローを解くことと同等の多項数係数である。
本手法は,部分モジュラーベースポリトープ上で定義される凸関数を高精度に最適化する,簡単な反復法を提供することにより実現し,構築するグラフのカット関数に対応する基本ポリトープ上で効率よく最小化することができる。
我々はこの最小化問題をパラメトリックカット問題の解を持ち上げて解くことで解決する。
この減少は独立した利益であり、複数の設定におけるパラメトリック最小$s,t$-cut問題に対する未知の境界を示唆している。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - 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) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization [7.197233473373693]
2つの凸関数の和を最小化する問題を考える。
1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。
我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
論文 参考訳（メタデータ） (2022-05-25T13:01:09Z) - Parallel Quasi-concave set optimization: A new frontier that scales
without needing submodularity [14.93584434176082]
擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。
我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
論文 参考訳（メタデータ） (2021-08-19T15:50:41Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Sparse Approximate Solutions to Max-Plus Equations with Application to
Multivariate Convex Regression [34.99564569478268]
我々は,任意の$ell_p$近似誤差に対して,そのような解を効率よく最小時間で得る方法を示す。
本稿では, 凸関数を一括フィッティングする手法を提案し, 最適性を保証するとともに, 略スパースアフィン領域を提案する。
論文 参考訳（メタデータ） (2020-11-06T15:17:00Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Submodular Maximization Through Barrier Functions [32.41824379833395]
連続最適化における障壁関数に着想を得た制約付き部分モジュラーの新しい手法を提案する。
提案するアルゴリズムを実世界の複数のアプリケーションに対して広範囲に評価する。
論文 参考訳（メタデータ） (2020-02-10T03:32:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。