cs.LGFeb 13, 2026

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

Authors: Mohammad Pedramfar, Vaneet Aggarwal

Organizations: Mila - Quebec AI Institute/McGill University · Purdue University

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.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

    Feb 24, 2026Yiyang Lu, Haresh Jadav, Mohammad Pedramfar +2Submodular OptimizationDynamic Regret Minimization

  2. Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

    Jan 30, 2025Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalSubmodular OptimizationOnline Convex Optimization