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

Sep 30, 2026

Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization

We study online and offline maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets K⊆[0,1]dK\subseteq[0,1]^d that contain a supplied diagonal point ζ1ζ\mathbf{1}. Our online algorithm earns at least α‾(ζ)=12−(1−2ζ)+22(3−2ζ)2\underlineα(ζ)=\frac{1}{2}-\frac{(1-2ζ)_+^2}{2(3-2ζ)^2} times the reward of the best fixed feasible point, minus O(T)O(\sqrt{T}), using one possibly stochastic gradient query and one projection per round; α‾(0)=4/9\underlineα(0)=4/9. One post-decision noisy value query per round gives O(T3/4)O(T^{3/4}) regret, and two exact value queries give O(T)O(\sqrt{T}). Conversely, no offline algorithm with polynomially many exact value-and-gradient queries attains a coefficient above an explicit β∗≈0.4704β_*\approx 0.4704 at ζ=0ζ=0, improving the bound 2(e−1/2−e−1)≈0.4782(e^{-1/2}-e^{-1})\approx 0.478 of Oveis Gharan and Vondrák (2011); for ζ>0ζ>0, two families of hard instances give an upper bound that we reduce exactly to finitely many convex problems below ζ=1/8ζ=1/8 and give in closed form above it. The bound β∗β_* also holds for nonnegative submodular set functions under a cardinality constraint, improving the previous 0.4780.478. Online-to-offline conversion gives α‾(ζ)−ε\underlineα(ζ)-\varepsilon offline, and the upper bound also limits online learners with polynomial query budgets and uniform O(Tκ)O(T^κ) regret, κ<1κ<1. Both coefficients equal 1/21/2 for ζ≥1/2ζ\ge 1/2 and fall short of 1/21/2 by order (1/2−ζ)2(1/2-ζ)^2 below. For quadratic objectives we attain 1/21/2, and for cubic objectives max⁡{8/17, 23−4r/(1+3−4r)2}\max\{8/17,\,2\sqrt{3-4r}/(1+\sqrt{3-4r})^2\} with r=min⁡{ζ,1/2}r=\min\{ζ,1/2\}. For submodular set functions, rounding the multilinear extension gives α‾(ζ)−ε\underlineα(ζ)-\varepsilon under a matroid whose polytope contains ζ1ζ\mathbf{1} and 4/9−ε4/9-\varepsilon under a fixed number of knapsack constraints.
Feb 24, 2026

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

We study online maximization of non-monotone Diminishing-Return(DR)-submodular functions over down-closed convex sets, a regime where existing projection-free online methods suffer from suboptimal regret and limited feedback guarantees. Our main contribution is a new structural result showing that this class is 1/e1/e-linearizable under carefully designed exponential reparametrization, scaling parameter, and surrogate potential, enabling a reduction to online linear optimization. As a result, we obtain O(T1/2)O(T^{1/2}) static regret with a single gradient query per round and unlock adaptive and dynamic regret guarantees, together with improved rates under semi-bandit, bandit, and zeroth-order feedback. Across all feedback models, our bounds strictly improve the state of the art.
Jan 30, 2025

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

We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of O(T1−θ/2)O(T^{1-θ/2}) with communication complexity of O(Tθ)O(T^θ) and number of linear optimization oracle calls of O(T2θ)O(T^{2θ}) for decentralized upper-linearizable function optimization, for any 0≤θ≤10\le θ\le 1. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.