提出更优的非单调弱DR-子模优化算法，逼近效果随参数平滑变化。
Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
- 结合Frank-Wolfe与γ感知双贪心策略处理非单调性
- 当γ=1时达到0.401逼近比，γ<1时优雅退化
- 适用于带约束的非单调子模优化，适合机器学习场景
在机器学习与优化中，带约束的子模函数最大化是一个基础问题。本文研究在向下封闭凸体上对非负、非单调的γ-弱DR-子模函数进行最大化。主要成果是提出一种逼近算法，其保证值随γ平滑变化：当γ=1（即DR-子模情形）时，逼近比恢复为0.401；当γ<1时，保证值渐进下降，且优于此前同类问题的报告结果。方法结合了基于Frank-Wolfe的连续贪心框架与γ感知的双贪心步骤，形成简单而有效的非单调性处理机制。该方法在向下封闭凸体上的非单调γ-弱DR-子模最大化中实现了当前最优逼近保证。
原文摘要 · Abstract (English)
Maximizing submodular objectives under constraints is a fundamental problem in machine learning and optimization. We study the maximization of a nonnegative, non-monotone $γ$-weakly DR-submodular function over a down-closed convex body. Our main result is an approximation algorithm whose guarantee depends smoothly on $γ$; in particular, when $γ=1$ (the DR-submodular case) our bound recovers the $0.401$ approximation factor, while for $γ<1$ the guarantee degrades gracefully and, it improves upon previously reported bounds for $γ$-weakly DR-submodular maximization under the same constraints. Our approach combines a Frank-Wolfe-guided continuous-greedy framework with a $γ$-aware double-greedy step, yielding a simple yet effective procedure for handling non-monotonicity. This results in state-of-the-art guarantees for non-monotone $γ$-weakly DR-submodular maximization over down-closed convex bodies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。