提出新框架统一优化非凸函数,突破传统限制。
$γ$-weakly $θ$-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions
- 引入γ-弱θ上凹性,统一刻画多种非凸函数。
- 可构造线性近似,逼近误差由曲率参数决定。
- 适用于离线、在线优化,尤其在拟阵约束下更优。
非凸优化是机器学习与组合优化中的核心挑战。本文提出并研究γ-弱θ上凹性,一种新型一阶条件,用于刻画广泛的一类非凸函数。该条件严格推广了DR-子模函数与单侧光滑(OSS)函数,能捕捉累积后递减收益及平起行为等更复杂的尺度依赖曲率。理论核心表明:γ-弱θ上凹函数具有上线性化性质——对任意可行点,可构造一个线性代理函数,其增益可保证逼近原非线性目标。关键技术贡献在于非均匀上线性化论证,所得近似系数显式依赖于曲率参数与可行域几何。此线性化性质带来一系列统一的近似保证:通过标准归约,可直接获得离线优化的统一近似界,以及静态与动态在线情形下的后悔界。此外,该框架恢复了DR-子模最大化问题的最优近似系数,并在拟阵约束下改进了现有OSS优化的近似系数。
原文摘要 · Abstract (English)
Optimizing non-convex functions is a fundamental challenge across machine learning and combinatorial optimization. We introduce and study $γ$-weakly $θ$-up-concavity, a novel first-order condition that characterizes a broad class of such functions. This condition provides a powerful unifying framework, strictly generalizing both DR-submodular and One-Sided Smooth (OSS) functions while capturing broader forms of scale-dependent curvature, including accumulating-then-diminishing returns and flat-start behavior. Our central theoretical contribution demonstrates that $γ$-weakly $θ$-up-concave functions are upper-linearizable: for any feasible point, we can construct a linear surrogate whose gains provably approximate the original non-linear objective. A key technical contribution is a nonuniform upper-linearization argument yielding approximation coefficients that depend explicitly on the curvature parameters and the geometry of the feasible region. This linearizability yields immediate and unified approximation guarantees for a wide range of problems. Specifically, we obtain unified approximation guarantees for offline optimization as well as static and dynamic regret bounds in online settings via standard reductions to linear optimization. Moreover, our framework recovers the optimal approximation coefficient for DR-submodular maximization and improves existing approximation coefficients for OSS optimization, particularly over matroid constraints.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。