Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
复制标题
近最优近似离散和连续子模函数最小化
DOI：
10.1137/1.9781611975994.51
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sidford, Aaron
中科院分区：
文献类型：
--
作者：
Axelrod, Brian;Liu, Yang P.;Sidford, Aaron
在本文中，我们提供了改进的运行时间和甲骨文的复杂性近似最小化的子模函数。我们的主要结果是给出了一个随机算法，该算法对任意定义在n元上的值域为[-1，1]的子模函数，以高概率计算ε-可加近似极小元不含（n/ε2）个预言值.这改进了Chakrabartyet al.（STOC 2017）的n3（n5/3/ε2）oracle求值算法和Hamoudiet al.的n3（n3/2/ε2）oracle求值算法...此外，我们利用这一结果的推广来获得最小化广泛的一类非凸函数的有效算法。对于定义域为[0，1] n的函数f，若f对所有i ∈ j都满足且关于L ∞-范数为L-Lipschitz，我们给出了一个算法，该算法以高概率计算ε-可加近似极小值，且函数求值为n（n）·poly（L/ε）.
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined onn-elements with range [–1, 1], computes an ε-additive approximate minimizer inÕ(n/ε2) oracle evaluations with high probability. This improves over theÕ(n5/3/ε2) oracle evaluation algorithm of Chakrabartyet al. (STOC 2017) and theÕ(n3/2/ε2) oracle evaluation algorithm of Hamoudiet al…Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any functionfwith domain [0, 1]nthat satisfies for alli≠jand isL-Lipschitz with respect to theL∞-norm we give an algorithm that computes anε-additive approximate minimizer withÕ(n ·poly(L/ε) function evaluation with high probability.
登录
查看更多内容
DOI：
--
发表时间：
2019-06
期刊：
ArXiv
影响因子：
--
作者：
Oliver Hinder;Aaron Sidford;N. Sohoni
通讯作者：
Oliver Hinder;Aaron Sidford;N. Sohoni
DOI：
--
发表时间：
2011
期刊：
International Conference on Machine Learning
影响因子：
--
作者：
S. Jegelka;J. Bilmes
通讯作者：
J. Bilmes
关于子模函数最小化
DOI：
--
发表时间：
1985
期刊：
Comb.
影响因子：
--
作者：
W. Cunningham
通讯作者：
W. Cunningham
$alpha$-弱拟凸问题的加速方法
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Sergey Guminov;A. Gasnikov
通讯作者：
A. Gasnikov
动态图割及其在计算机视觉中的应用
DOI：
--
发表时间：
2010
期刊：
Computer Vision: Detection, Recognition and Reconstruction
影响因子：
--
作者：
Pushmeet Kohli;Philip H. S. Torr
通讯作者：
Philip H. S. Torr