提出一种统一框架，解决离散与连续域上子模函数差的最小化问题。
Discrete and Continuous Difference of Submodular Minimization
- 将子模函数差问题转化为凸函数差形式，适配离散与连续场景。
- 在整数压缩感知和整数最小二乘任务中优于现有基线方法。
- 适用于需要优化非凸子模结构的机器学习与信号处理场景。
子模函数在连续或离散域上广泛存在。本文研究在两种域上对两个子模函数之差（DS）进行最小化，扩展了以往仅限于集合函数的研究。我们证明：所有离散域上的函数以及所有连续域上的光滑函数均为DS函数。在离散域中，发现DS最小化等价于凸函数差（DC）最小化，与集合函数情形一致。为此提出一种新的DC算法（DCA）变体，并应用于对应的DC规划，获得与集合函数情况相当的理论保证。该算法可通过离散化推广至连续域。实验表明，在整数压缩感知和整数最小二乘任务中，本方法显著优于基线方法。
原文摘要 · Abstract (English)
Submodular functions, defined on continuous or discrete domains, arise in numerous applications. We study the minimization of the difference of two submodular (DS) functions, over both domains, extending prior work restricted to set functions. We show that all functions on discrete domains and all smooth functions on continuous domains are DS. For discrete domains, we observe that DS minimization is equivalent to minimizing the difference of two convex (DC) functions, as in the set function case. We propose a novel variant of the DC Algorithm (DCA) and apply it to the resulting DC Program, obtaining comparable theoretical guarantees as in the set function case. The algorithm can be applied to continuous domains via discretization. Experiments demonstrate that our method outperforms baselines in integer compressive sensing and integer least squares.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。