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.


翻译:在标准设置和参数设置中,这种纸上连接离散的和连续的优化方法可以使分解的子模块功能最小化。 我们通过将这一问题降低到一个最大流点的多个调频点,为这一问题提供了更好的运行时间。 当对地面的$O(1)美元元元元元元的分解动作中的每一函数设定了$V$, 并且是多元的, 我们的运行时间将达到多元性因素, 等同于用美元( vert V\verd) $( verd) 的悬浮图解析最大流, 以及多元整体能力。 我们通过提供简单的迭接合方法来实现这一目标, 可以优化到高精度, 任何在子模块基数聚点上定义的同系函数, 只要我们能有效地在与我们构建的某个图形的切断函数相对的基数多功能上将其最小化为最小化。 我们通过取消对等分解问题的解决办法来解决这个最小化问题, 我们通过新的高效的调控波减少至最大流点来获得。 这种减少具有独立的利益, 并意味着在多个环境中对准最小值最小值的最小值问题有一些未知的界限。

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月28日
Arxiv
0+阅读 · 2021年4月27日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关VIP内容
专知会员服务
76+阅读 · 2021年3月16日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员