Paperlane

no. 14 · Friday 13 November 2026

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

Mohammad Pedramfar and Vaneet Aggarwal

math.OC · v3

Abstract

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.

comments
Accepted to Neurips 2026
fields
Optimization and Control
pdf ↗ page arXiv:2602.13506 ↗