Beyond submodular maximization via one-sided smoothness

Abstract The multilinear framework for submodular maximization was developed to achieve a tight $$1-1/e$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>e</mml:mi> </mml:mrow> </mml:math> approximation for maximizing a monotone submodular function subject to a matroid constraint, including as special case the submodular welfare problem. The framework has a continuous optimization step (solving the multilinear extension of a submodular function) and a rounding part (rounding a fractional solution to an integral one). We extend both parts to provide a framework for a wider array of applications. The continuous part works for a more general class of continuous functions parameterized by a new smoothness parameter $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> . A twice differential function F is called $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> -one-sided-smooth ( $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> -OSS) if its second derivatives are bounded as follows: $$\frac{1}{2}u^T\nabla ^2 F(x) u \le \sigma \cdot \frac{\Vert u\Vert _1}{\Vert x\Vert _1} u^T \nabla F(x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> <mml:msup> <mml:mi>u</mml:mi> <mml:mi>T</mml:mi> </mml:msup> <mml:msup> <mml:mi>∇</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>F</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>u</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>σ</mml:mi> <mml:mo>·</mml:mo> <mml:mfrac> <mml:msub> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mi>u</mml:mi> <mml:mo>‖</mml:mo> </mml:mrow> <mml:mn>1</mml:mn> </mml:msub> <mml:msub> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mi>x</mml:mi> <mml:mo>‖</mml:mo> </mml:mrow> <mml:mn>1</mml:mn> </mml:msub> </mml:mfrac> <mml:msup> <mml:mi>u</mml:mi> <mml:mi>T</mml:mi> </mml:msup> <mml:mi>∇</mml:mi> <mml:mi>F</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> for all $$u,x\ge 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>,</mml:mo> <mml:mi>x</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , $$x\ne 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>≠</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> . For $$\sigma =0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>σ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> this includes previously studied continuous DR-Submodular functions as well as quadratics defined by copositive matrices. We give a modification of the continuous greedy algorithm which finds a solution for maximizing a monotone $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> -OSS F over a polytope in the non-negative orthant; the solution approximates the optimum to within factors which are functions of $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> which depend on additional properties. Interestingly, $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> -OSS functions arise as the multilinear extensions of set functions associated with several well-studied diversity maximization problems: $$\max f(S) = \sum _{i,j \in S} A_{ij} : |S| \le k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>max</mml:mo> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mm