arXiv:2602.13506 · v3

$γ$-weakly $θ$-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions

首次提交 2026-02-14 06:34

版本更新 2026-11-11 15:03

雷达观测 2026-11-13 14:16

摘要

Many objectives in machine learning and combinatorial optimization are non-concave. We introduce $γ$-weak $θ$-up-concavity, a first-order condition for nonnegative monotone functions in which a scaling function $θ$ lets the curvature change with the size of the solution. The resulting class strictly contains monotone DR-submodular functions and One-Sided Smooth (OSS) functions. It also contains functions whose marginal gains first increase and then decrease, and functions that vanish faster than any power of the norm at the origin. We construct a surrogate gradient from gradients along the segment from the origin to the current point and prove an upper-linearization inequality with a point-dependent approximation coefficient. Restricting actions to the closed convex hull of the coordinate-wise maximal feasible points makes this coefficient uniformly positive, with a value determined by the curvature parameters and the geometry of the feasible set. Standard reductions to linear optimization then give offline approximation algorithms and online algorithms with regret guarantees. The coefficient matches the optimal one for DR-submodular maximization and improves the best known coefficients for OSS maximization over matroid constraints whenever the OSS parameter is positive.

作者备注：Accepted to Neurips 2026