-weakly -up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions
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
| Matroid independence polytope | Matroid basis polytope |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
| Choice of | Transition equation | Transition point |
|---|---|---|
| , | ||
| unique positive root | ||
| , | ||
| , | unique positive root | |
| unique positive root |
Nonconvex Optimization
Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.
See all 162 papers