γ-弱 θ-上凹性：超越 DR-Submodular 与 OSS 函数的非凸优化统一框架

View PDF HTML (experimental)

Abstract:Many objectives in machine learning and combinatorial optimization are non-concave. We introduce $\gamma$-weak $\theta$-up-concavity, a first-order condition for nonnegative monotone functions in which a scaling function $\theta$ 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.

Comments:	Accepted to Neurips 2026
Subjects:	Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)
Cite as:	arXiv:2602.13506 [cs.LG]
	(or arXiv:2602.13506v3 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2602.13506 arXiv-issued DOI via DataCite

Submission history

From: Vaneet Aggarwal [view email]
[v1] Fri, 13 Feb 2026 22:34:44 UTC (21 KB)
[v2] Thu, 7 May 2026 20:41:04 UTC (67 KB)
[v3] Wed, 11 Nov 2026 07:03:50 UTC (68 KB)