# $\\gamma$-weakly $\\theta$-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions

DevFeed: [$\\gamma$-weakly $\\theta$-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions](<https://devfeed.tech/articles/gamma-weakly-theta-up-concavity-a-unified-framework-for-non-convex-optimization-beyond-dr-submodular-and-oss-functions-131882.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2602.13506>)

Author: Mohammad Pedramfar, Vaneet Aggarwal

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [actions](<https://devfeed.tech/tags/actions.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [also](<https://devfeed.tech/tags/also.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [best](<https://devfeed.tech/tags/best.md>), [change](<https://devfeed.tech/tags/change.md>), [class](<https://devfeed.tech/tags/class.md>), [combinatorial-optimization](<https://devfeed.tech/tags/combinatorial-optimization.md>), [condition](<https://devfeed.tech/tags/condition.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [dr](<https://devfeed.tech/tags/dr.md>), [framework](<https://devfeed.tech/tags/framework.md>), [functions](<https://devfeed.tech/tags/functions.md>), [gamma](<https://devfeed.tech/tags/gamma.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [oss](<https://devfeed.tech/tags/oss.md>), [up](<https://devfeed.tech/tags/up.md>)

## AI overview

The proposed γ-weak θ-up-concavity framework covers monotone DR-submodular and One-Sided Smooth (OSS) functions, plus objectives whose marginal gains can rise before falling or that vanish faster than any power of the norm near the origin. It builds a surrogate gradient from gradients along the segment between the origin and the current point, yielding an upper-linearization inequality with a point-dependent approximation coefficient. Restricting actions to the closed convex hull of coordinate-wise maximal feasible points makes that coefficient uniformly positive, according to curvature and feasible-set geometry. Reductions to linear optimization provide offline approximation algorithms and online regret guarantees. The coefficient matches the optimal DR-submodular maximization value and improves known OSS coefficients under matroid constraints when the OSS parameter is positive.

## Source excerpt

arXiv:2602.13506v3 Announce Type: replace-cross 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.