arXiv:1711.02515v3 [cs.LG] 16 Dec 2017

Continuous DR-submodular Maximization:
Structure and Algorithms

An Bian
ETH Zurich
ybian@inf.ethz.ch

Kfir Y. Levy
ETH Zurich
yehuda.levy@inf.ethz.ch

Andreas Krause
ETH Zurich
krausea@ethz.ch

Joachim M. Buhmann
ETH Zurich
jbuhmann@inf.ethz.ch

Abstract
DR-submodular continuous functions are important objectives with wide real-world
applications spanning MAP inference in determinantal point processes (DPPs),
and mean-field inference for probabilistic submodular models, amongst others.
DR-submodularity captures a subclass of non-convex functions that enables both
exact minimization and approximate maximization in polynomial time.
In this work we study the problem of maximizing non-monotone continuous DRsubmodular functions under general down-closed convex constraints. We start
by investigating geometric properties that underlie such objectives, e.g., a strong
relation between (approximately) stationary points and global optimum is proved.
These properties are then used to devise two optimization algorithms with provable
guarantees. Concretely, we first devise a “two-phase” algorithm with 1/4 approximation guarantee. This algorithm allows the use of existing methods for finding
(approximately) stationary points as a subroutine, thus, harnessing recent progress
in non-convex optimization. Then we present a non-monotone F RANK -W OLFE
variant with 1/e approximation guarantee and sublinear convergence rate. Finally,
we extend our approach to a broader class of generalized DR-submodular continuous functions, which captures a wider spectrum of applications. Our theoretical
findings are validated on synthetic and real-world problem instances.

1

Introduction

Submodularity is classically most well known for set function optimization, where it enables efficient
minimization [23] and approximate maximization [31; 25] in polynomial time. Submodularity has
recently been studied on the integer lattice [34; 33] and on continuous domains [3; 4; 36; 21], with
significant theoretical results and practical applications. For set functions, it is well known that
submodularity is equivalent to the diminishing returns (DR) property. However, this does not hold
for integer-lattice functions or continuous functions, where the DR property defines a subclass of
submodular functions, called DR-submodular functions.
In continuous domains, applying convex optimization techniques enables efficient minimization of
submodular continuous functions [3; 36] (despite the non-convex nature of such objectives). In [4]
it is further shown that continuous submodularity enables constant-factor approximation schemes
for constrained monotone DR-submodular maximization and “box” constrained non-monotone
submodular maximization problems.
31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.

Many real-world non-convex problems, such as maximizing the softmax extension of DPPs, require
maximizing a non-monotone DR-submodular function over a general down-closed convex constraint.
Yet, current theory [3; 4; 36] does not apply to this general problem setting, which motivates us to
develop guaranteed and efficient algorithms for such problems.
Exploring the structure that underlies DR-submodularity is crucial to deriving guaranteed algorithms.
Combined with a notion of non-stationarity for constrained optimization problems and a new notion
of “strong DR-submodularity”, we find a rich structure in the problem of continuous DR-submodular
maximization. This in turn gives rise to two approximation algorithms with provable guarantees.
Specifically, we make the following contributions:
- We bound the difference between objective values of stationary points and the global optimum.
Our analysis shows that the bound is even tighter if the objective is strongly DR-submodular
(see Definition 3).
- Based on the geometric properties, we present two algorithms: (i) A two-phase
√ F RANK W OLFE-style algorithm with 1/4 approximation guarantee converges with a 1/ k rate; (ii) a
non-monotone F RANK -W OLFE variant exhibits a 1/e approximation guarantee and converges
sublinearly. Even though the worst-case guarantee of the first one is worse than the second, it
yields several practical advantages, which we discuss in Section 4.2.
- We investigate a generalized class of submodular functions on “conic” lattices. This allows
us to model a larger class of non-trivial applications. These include logistic regression with
a non-convex separable regularizer, non-negative PCA, etc. To optimize them, we provide a
reduction that enables to invoke algorithms for continuous submodular optimization problems.
- We experimentally demonstrate the applicability of our methods on both synthetic and realworld problem instances.
1.1

Problem Statement

Notation. We use boldface letters, e.g., x to represent a vector, boldface capital letters, e.g., A
to denote a matrix. xi is the ith entry of x, Aij is the (ij)th entry of A. We use ei to denote the
standard ith basis vector. f (·) is used to denote a continuous function, and F (·) to represent a set
function. [n] := {1, ..., n} for an integer n ≥ 1. k · k means the Euclidean norm by default. Given
two vectors x, y, x ≤ y means xi ≤ yi , ∀i. x ∨ y and x ∧ y denote coordinate-wise maximum and
coordinate-wise minimum, respectively.
The general setup of constrained non-monotone DR-submodular (see Definition 1 below) maximization is,
max f (x),
(P)
x∈P
Qn
where f : X → R is continuous DR-submodular, X = i=1 Xi , each Xi is an interval [3; 4]. Wlog1 ,
we assume that the lower bound u of X is 0, i.e., X = [0, ū]. The set P ⊆ [0, ū] is assumed to be a
down-closed convex set, where down-closedness means: x ∈ P and 0 ≤ y ≤ x implies that y ∈ P.
The diameter of P is D := maxx,y∈P kx − yk, and it holds that D ≤ kūk. We use x∗ to denote the
global maximum of (P). One can assume f is non-negative over X , since otherwise one just needs to
find a lower bound for the minimum function value of f over [0, ū] (and box-constrained submodular
minimization can be solved to arbitrary precision in polynomial time [3]). Over continuous domains,
a DR-submodular function [4] is a submodular function with the diminishing returns (DR) property,
Definition 1 (DR-submodular & DR property). A function f : X 7→ R is DR-submodular (has the
DR property) if ∀a ≤ b ∈ X , ∀i ∈ [n], ∀k ∈ R+ s.t. (kei + a) and (kei + b) are still in X , it holds,
f (kei + a) − f (a) ≥ f (kei + b) − f (b).

(1)

If f is differentiable, one can show that Definition 1 is equivalent to ∇f being an antitone mapping
from Rn to Rn . Furthermore, if f is twice-differentiable, the DR property is equivalent to all of
the entries of its Hessian being non-positive, i.e., ∇2ij f (x) ≤ 0, ∀x ∈ X , i, j ∈ [n]. A function
f : X 7→ R is DR-supermodular iff −f is DR-submodular. We also assume that f has Lipschitz
gradients,
1

Since otherwise one can work on a new function g(x) := f (x + u) that has 0 as the lower bound of its
domain, and all properties of the function are still preserved.

2

Definition 2. A function f has L-Lipschitz gradients if for all x, y ∈ X it holds that,
k∇f (x) − ∇f (y)k ≤ Lkx − yk.

(2)

A brief summary of related work appears in Section 6.

2

Motivating Real-world Examples

Many continuous objectives in practice turn out to be DR-submodular. Here we list several of them.
More can be found in Appendix B.
Softmax extension. Determinantal point processes (DPPs) are probabilistic models of repulsion,
that have been used to model diversity in machine learning [26]. The constrained MAP (maximum a
posteriori) inference problem of a DPP is an NP-hard combinatorial problem in general. Currently,
the methods with the best approximation guarantees are based on either maximizing the multilinear
extension [6] or the softmax extension [20], both of which are DR-submodular functions (details in
Appendix F.1). The multilinear extension is given as an expectation over the original set function
values, thus evaluating the objective of this extension requires expensive sampling. In constast, the
softmax extension has a closed form expression, which is much more appealing from a computational
perspective. Let L be the positive semidefinite kernel matrix of a DPP, its softmax extension is:
f (x) = log det (diag(x)(L − I) + I) , x ∈ [0, 1]n ,

(3)

where I is the identity matrix, diag(x) is the diagonal matrix with diagonal elements set as x.
The problem of MAP inference in DPPs corresponds to the problem maxx∈P f (x), where P is a
down-closed convex constraint, e.g., a matroid polytope or a matching polytope.
Mean-field inference for log-submodular models. Log-submodular models [9] are a class of
probabilistic models over subsets of a ground set V = [n], where the log-densities
P are submodular
set functions F (S): p(S) = Z1 exp(F (S)). The partition function Z =
S⊆V exp(F (S)) is
typically hard to evaluate.
One
can
use
mean-field
inference
to
approximate
p(S)
by some factorized
Q
Q
n
distribution qx (S) := i∈S xi j ∈S
/ (1 − xj ), x ∈ [0, 1] , by minimizing the distance measured
P
x (S)
w.r.t. the Kullback-Leibler divergence between qx and p, i.e., S⊆V qx (S) log qp(S)
. It is,
XY Y
Xn
KL(x) = −
xi
(1 − xj )F (S) +
[xi log xi + (1 − xi ) log(1 − xi )] + log Z.
S⊆V i∈S

i=1

j ∈S
/

KL(x) is DR-supermodular w.r.t. x (details in Appendix F.1). Minimizing the Kullback-Leibler
divergence KL(x) amounts to maximizing a DR-submodular function.
2.1

Motivating Example Captured by Generalized Submodularity on Conic Lattices

Submodular continuous functions can already model many scenarios. Yet, there are several interesting cases which are in general not (DR-)Submodular, but can still be captured by a generalized
notion. This generalization enables to develop polynomial algorithms with guarantees by using ideas
from continuous submodular optimization. We present one representative objective here (more in
Appendix B). In Appendix A we show the technical details on how they are covered by a class of
submodular continuous functions over conic lattices.
Consider the logistic regression model with a non-convex separable regularizer. This flexibility may
result in better statistical performance (e.g., in recovering discontinuities, [2]) compared to classical
models with convex regularizers. Let z 1 , ..., z m in Rn be m training points with corresponding
binary labels y ∈ {±1}m . Assume that the following mild assumption is satisfied: For any fixed
dimension i, all the data points have the same sign, i.e., sign(zij ) is the same for all j ∈ [m] (which
can be achieved by easily scaling if not). The task is to solve the following non-convex optimization
problem,
Xm
minn f (x) := m−1
fj (x) + λr(x),
(4)
j=1

x∈R

where fj (x) = log(1 + exp(−yj x> z j )) is the logistic loss; λ > 0 is the regularization parameter,
and r(x) is some non-convex separable regularizer. Such separable regularizers are popular in
3

statistics, and two notable choices are r(x) =

γx2i
i=1 1+γx2i ,
sign(zij ), i ∈

Pn

and r(x) =

Pn

2
i=1 min{γxi , 1}
Pm
1
:= m
j=1 fj (x).

(see

[2]). Let us define a vector α ∈ {±1}n as αi =
[n] and l(x)
One
can show that l(x) is not DR-submodular or DR-supermodular. Yet, in Appendix A we will show
that l(x) is Kα -DR-supermodular, where the latter generalizes DR-supermodularity. Usually, one
can assume the optimal solution x∗ lies in some box [u, ū]. Then the problem is an instance of
constrained non-monotone Kα -DR-submodular maximization.

3

Underlying Properties of Constrained DR-submodular Maximization

In this section we present several properties arising in DR-submodular function maximization. First
we show properties related to concavity of the objective along certain directions, then we establish the
relation between locally stationary points and the global optimum (thus called “local-global relation”).
These properties will be used to derive guarantees for the algorithms in Section 4. All omitted proofs
are in Appendix D.
3.1

Properties Along Non-negative/Non-positive Directions

A DR-submodular function f is concave along any non-negative/non-positive direction [4]. Notice
that DR-submodularity is a stronger condition than concavity along directions v ∈ ±Rn+ : for instance,
a concave function is concave along any direction, but it may not be a DR-submodular function.
For a DR-submodular function with L-Lipschitz gradients, one can get the following quadratic lower
bound using standard techniques by combing the concavity and Lipschitz gradients in (2).
Quadratic lower bound. If f is DR-submodular with a L-Lipschitz gradient, then for all x ∈ X
and v ∈ ±Rn+ , it holds,
L
kvk2 .
(5)
2
It will be used in Section 4.2 for analyzing the non-monotone F RANK -W OLFE variant (Algorithm 2).
f (x + v) ≥ f (x) + h∇f (x), vi −

Strong DR-submodularity. DR-submodular objectives may be strongly concave along directions
v ∈ ±Rn+ , e.g., for DR-submodular quadratic functions. We will show that such additional structure
may be exploited to obtain stronger guarantees for the local-global relation.
Definition 3 (Strongly DR-submodular). A function f is µ-strongly DR-submodular (µ ≥ 0) if for
all x ∈ X and v ∈ ±Rn+ , it holds that,
f (x + v) ≤ f (x) + h∇f (x), vi −
3.2

µ
kvk2 .
2

(6)

Relation Between Approximately Stationary Points and Global Optimum

First of all, we present the following Lemma, which will motivate us to consider a non-stationarity
measure for general constrained optimization problems.
Lemma 1. If f is µ-strongly DR-submodular, then for any two points x, y in X , it holds:
µ
(y − x)> ∇f (x) ≥ f (x ∨ y) + f (x ∧ y) − 2f (x) + kx − yk2 .
(7)
2
Lemma 1 implies that if x is stationary (i.e., ∇f (x) = 0), then 2f (x) ≥ f (x ∨ y) + f (x ∧ y) +
µ
2
2 kx − yk , which gives an implicit relation between x and y. While in practice finding an exact
stationary point is not easy, usually non-convex solvers will arrive at an approximately stationary
point, thus requiring a proper measure of non-stationarity for the constrained optimization problem.
Non-stationarity measure. Looking at the LHS of (7), it naturally suggests to use maxy∈P (y −
x)> ∇f (x) as the non-stationarity measure, which happens to coincide with the measure proposed
by recent work of [27], and it can be calculated for free for Frank-Wolfe-style algorithms (e.g.,
Algorithm 3). In order to adapt it to the local-global relation, we give a slightly more general
definition here: For any constraint set Q ⊆ X , the non-stationarity of a point x ∈ Q is,
gQ (x) := maxhv − x, ∇f (x)i
v∈Q

4

(non-stationarity).

(8)

It always holds that gQ (x) ≥ 0, and x is a stationary point in Q iff gQ (x) = 0, so (8) is a natural
generalization of the non-stationarity measure k∇f (x)k for unconstrained optimization. As the next
statement shows, gQ (x) plays an important role in characterizing the local-global relation.
Proposition 1 (Local-Global Relation). Let x be a point in P with non-stationarity gP (x), and
Q := {y ∈ P | y ≤ ū − x}. Let z be a point in Q with non-stationarity gQ (z). It holds that,

1
µ
max{f (x), f (z)} ≥ [f (x∗ ) − gP (x) − gQ (z)] +
kx − x∗ k2 + kz − z ∗ k2 ,
(9)
4
8
where z ∗ := x ∨ x∗ − x.
Proof sketch of Proposition 1: The proof uses Lemma 1, the non-stationarity in (8) and a key
observation in the following Claim. The detailed proof is in Appendix D.2.
Claim 1. It holds that f (x ∨ x∗ ) + f (x ∧ x∗ ) + f (z ∨ z ∗ ) + f (z ∧ z ∗ ) ≥ f (x∗ ).
Note that [7; 20] propose a similar relation for the special cases of multilinear/softmax extensions by
mainly proving the same conclusion as in Claim 1. Their relation does not incorporate the properties
of non-stationarity or strong DR-submodularity. They both use the proof idea of constructing a
complicated auxiliary set function tailored to specific DR-submodular functions. We present a
different proof method by directly utilizing the DR property on carefully constructed auxiliary points
(e.g., (x + z) ∨ x∗ in the proof of Claim 1), this is arguably more succint and straightforward than
that of [7; 20].

4

Algorithms for Constrained DR-submodular Maximization

Based on the properties, we present two algorithms for solving (P). The first is based on the localglobal relation, and the second is a F RANK -W OLFE variant adapted for the non-monotone setting.
All the omitted proofs are deferred to Appendix E.
4.1

An Algorithm Based on the Local-Global Relation

Algorithm 1: TWO - PHASE F RANK -W OLFE for non-monotone DR-submodular maximization
Input: maxx∈P f (x), stopping tolerance 1 , 2 , #iterations K1 , K2
(0)
1 x ← N ON - CONVEX F RANK -W OLFE (f, P, K1 , 1 , x
);
// x(0) ∈ P
n
2 Q ← P ∩ {y ∈ R+ | y ≤ ū − x};
(0)
3 z ← N ON - CONVEX F RANK -W OLFE (f, Q, K2 , 2 , z
);
// z (0) ∈ Q
Output: arg max{f (x), f (z)} ;
We summarize the TWO - PHASE algorithm in Algorithm 1. It is generalized from the “two-phase”
method in [7; 20]. It invokes some non-convex solver (we use the NON - CONVEX F RANK -W OLFE
by [27]; pseudocode is included in Algorithm 3 of Appendix C) to find approximately stationary
points in P and Q, respectively, then returns the solution with the larger function value. Though
we use N ON - CONVEX F RANK -W OLFE as the subroutine here, it is worth noting that any algorithm
that is guaranteed to find an approximately stationary point can be plugged into Algorithm 1 as
the subroutine. We give an improved approximation bound by considering more properties of
DR-submodular functions. Borrowing the results from [27] for the NON - CONVEX F RANK -W OLFE
subroutine, we get the following,
Theorem 1. The output of Algorithm 1 satisfies,

µ
max{f (x), f (z)} ≥
kx − x∗ k2 + kz − z ∗ k2
(10)
8





1
max{2h1 , Cf (P)}
max{2h2 , Cf (Q)}
√
√
+
f (x∗ ) − min
, 1 − min
, 2 ,
4
K1 + 1
K2 + 1
where h1 := maxx∈P f (x) − f (x(0) ), h2 := maxz∈Q f (z) − f (z (0) ) are the initial suboptimalities,
Cf (P) := supx,v∈P,γ∈[0,1],y=x+γ(v−x) γ22 (f (y) − f (x) − (y − x)> ∇f (x)) is the curvature of f
w.r.t. P, and z ∗ = x ∨ x∗ − x.
5

√
Theorem 1 indicates that Algorithm 1 has a 1/4 approximation guarantee and 1/ k rate. However,
it has good empirical performance as demonstrated by the experiments
 in Section 5. Informally, this
can be partially explained by the term µ8 kx − x∗ k2 + kz − z ∗ k2 in (10): if x is away from x∗ ,
this term will augment the bound; if x is close to x∗ , by the smoothness of f , it should be close to
optimal.
4.2

The Non-monotone F RANK -W OLFE Variant

Algorithm 2: Non-monotone F RANK -W OLFE variant for DR-submodular maximization
Input: maxx∈P f (x), prespecified step size γ ∈ (0, 1]
(0)
1 x
← 0, t(0) ← 0, k ← 0;
// k : iteration index, t(k) : cumulative step size
(k)
2 while t
< 1 do
3
v (k) ← arg maxv∈P,v≤ū−x(k) hv, ∇f (x(k) )i;
// shrunken LMO
(k)
4
use uniform step size γk = γ; set γk ← min{γk , 1 − t };
5
x(k+1) ← x(k) + γk v (k) , t(k+1) ← t(k) + γk , k ← k + 1;
Output: x(K) ;

// assuming there are K iterations in total

Algorithm 2 summarizes the non-monotone F RANK -W OLFE variant, which is inspired by the unified
continuous greedy algorithm in [13] for maximizing the multilinear extension of a submodular set
function. It initializes the solution x(0) to be 0, and maintains t(k) as the cumulative step size. At
iteration k, it maximizes the linearization of f over a “shrunken” constraint set: {v|v ∈ P, v ≤
ū − x(k) }, which is different from the classical LMO of Frank-Wolfe-style algorithms (hence we
refer to it as the “shrunken LMO”). Then it employs an update step in the direction v (k) chosen by
the LMO with a uniform step size γk = γ. The cumulative step size t(k) is used to ensure that the
overall step sizes sum to one, thus the output solution x(K) is a convex combination of the LMO
outputs, hence also lies in P.
The shrunken LMO (Step 3) is the key difference compared to the monotone F RANK -W OLFE variant
in [4]. The extra constraint v ≤ ū − x(k) is added to prevent too aggressive growth of the solution,
since in the non-monotone setting such aggressive growth may hurt the overall performance. The
next theorem states the guarantees of Algorithm 2.
Theorem 2. Consider Algorithm 2 with uniform step size γ. For k = 1, ..., K it holds that,
(k)

f (x(k) ) ≥ t(k) e−t

f (x∗ ) −

LD2 2
kγ − O(γ 2 )f (x∗ ).
2

(11)

By observing that t(K) = 1 and applying Theorem 2, we get the following Corollary:
Corollary 1. The output of Algorithm 2 satisfies f (x(K) ) ≥ e−1 f (x∗ ) −

LD 2
2K

1
K2

−O



f (x∗ ).

Corollary 1 shows that Algorithm 2 enjoys a sublinear convergence rate towards some point x(K)
inside P, with a 1/e approximation guarantee.
Proof sketch of Theorem 2: The proof is by induction. To prepare the building blocks, we first of
all show that the growth of x(k) is indeed bounded,
(k)

Lemma 2. Assume x(0) = 0. For k = 0, ..., K − 1, it holds xi

(k)

≤ ūi [1 − (1 − γ)t

/γ

], ∀i ∈ [n].

Then the following Lemma provides a lower bound, which gets the global optimum involved,
Lemma 3 (Generalized from Lemma 7 in [8]). Given θ ∈ (0, ū], let λ0 = mini∈[n]
x ∈ [0, θ], it holds f (x ∨ x∗ ) ≥ (1 − λ10 )f (x∗ ).

ūi
θi .

Then for all

Then the key ingredient for induction is the relation between f (x(k+1) ) and f (x(k) ) indicated by:
Claim 2. For k = 0, ..., K −1 it holds f (x(k+1) ) ≥ (1−γ)f (x(k) )+γ(1−γ)t

(k)

/γ

2

2
f (x∗ )− LD
2 γ ,

which is derived by a combination of the quadratic lower bound in (5), Lemma 2 and Lemma 3.
6

Remarks on the two algorithms. Notice that though the TWO - PHASE algorithm has a worse
guarantee than the non-monotone F RANK -W OLFE variant, it is still of interest: i) It allows flexibility
in using a wide range of existing solvers for finding an (approximately) stationary point. ii) The
guarantees that we present rely on a worst-case analysis. The empirical performance of the TWO PHASE algorithm is often comparable or better than that of the F RANK -W OLFE variant. This suggests
to explore more properties in concrete problems that may favor the TWO - PHASE algorithm, which we
leave for future work.

5

Experimental Results

We test the performance of the analyzed algorithms, while considering the following baselines: 1)
QUADPROG IP [39], which is a global solver for non-convex quadratic programming; 2) Projected
1
gradient ascent (P ROJ G RAD) with diminishing step sizes ( k+1
, k starts from 0). We run all the
algorithms for 100 iterations. For the subroutine (Algorithm 3) of TWO - PHASE F RANK -W OLFE,
we set 1 = 2 = 10−6 , K1 = K2 = 100. All the synthetic results are the average of 20 repeated
experiments. All experiments were implemented using MATLAB. Source code can be found at:
https://github.com/bianan/non-monotone-dr-submodular.
5.1

DR-submodular Quadratic Programming

As a state-of-the-art global solver, QUADPROG IP2 [39] can find the global optimum (possibly in
exponential time), which were used to calculate the approximation ratios. Our problem instances are
synthetic DR-submodular quadratic objectives with down-closed polytope constraints, i.e., f (x) =
m×n
1 >
>
n
m
2 x Hx + h x + c and P = {x ∈ R+ | Ax ≤ b, x ≤ ū, A ∈ R++ , b ∈ R+ }. Both objective
and constraints were randomly generated, in the following two manners:
1) Uniform distribution. H ∈ Rn×n is a symmetric matrix with uniformly distributed entries in
[−1, 0]; A ∈ Rm×n has uniformly distributed entries in [ν, ν + 1], where ν = 0.01 is a small positive
constant in order to make entries of A strictly positive.

0.95

0.9

1

1

0.95

0.95

Approx. ratio

Approx. ratio

Approx. ratio

1

0.9

0.9

0.85
0.85
8

10

12

14

Dimensionality

(a) m = b0.5nc

16

8

10

12

Dimensionality

(b) m = n

14

16

8

10

12

14

16

Dimensionality

(c) m = b1.5nc

Figure 1: Results on DR-submodular quadratic instances with uniform distribution.
2) Exponential distribution. The entries of −H and A were sampled from exponential distributions
Exp(λ) (For a random variable y ≥ 0, its probability density function is λe−λy , and for y < 0, its
density is 0). Specifically, each entry of −H was sampled from Exp(1), then the matrix −H was
made to be symmetric. Each entry of A was sampled from Exp(0.25) + ν, where ν = 0.01 is a small
positive constant.
In both the above two cases, we set b = 1m , and ū to be the tightest upper bound of P by
i
ūj = mini∈[m] Abij
, ∀j ∈ [n]. In order to make f non-monotone, we set h = −0.2 ∗ H> ū. To
make sure that f is non-negative, we first of all solve the problem minx∈P 21 x> Hx + h> x using
QUADPROG IP, let the solution to be x̂, then set c = −f (x̂) + 0.1 ∗ |f (x̂)|.
The approximation ratios w.r.t. dimensionalities (n) are plotted in Figures 1 and 2, for the two
manners of data generation. We set the number of constraints to be m = b0.5nc, m = n and
m = b1.5nc in Figures 1a to 1c (and Figures 2a to 2c), respectively.
2

We used the open source code provided by [39], and the IBM CPLEX optimization studio https://www.
ibm.com/jm-en/marketplace/ibm-ilog-cplex as the subroutine.

7

1
0.95

0.9
0.85
0.8

Approx. ratio

1
0.95

Approx. ratio

Approx. ratio

1
0.95

0.9
0.85

0.9
0.85
0.8

0.8
0.75

0.75
8

10

12

14

16

0.75

8

Dimensionality

8

10

12

14

(a) m = b0.5nc

10

12

14

16

Dimensionality

16

Dimensionality

(c) m = b1.5nc

(b) m = n

Figure 2: Results on quadratic instances with exponential distribution.
One can see that TWO - PHASE F RANK -W OLFE usually performs the best, P ROJ G RAD follows, and
non-monotone F RANK -W OLFE variant is the last. The good performance of TWO - PHASE F RANK W OLFE can be partially explained by the strong DR-submodularity of quadratic functions according
to Theorem 1. Performance of the two analyzed algorithms is consistent with the theoretical bounds:
the approximation ratios of F RANK -W OLFE variant are always much higher than 1/e.
5.2

Maximizing Softmax Extensions

0.2

0.2

0.15

0.15

0.1
0.05
0

Function value

0.2
0.15

Function value

Function value

With some derivation, one can see the derivative of the softmax extension in (3) is: ∇i f (x) =
tr((diag(x)(L − I) + I)−1 (L − I)i ), ∀i ∈ [n], where (L − I)i denotes the matrix obtained by
zeroing all entries except the ith row of (L − I). Let C := (diag(x)(L − I) + I)−1 , D := (L − I),
one can see that ∇i f (x) = D>
i· C·i , which gives an efficient way to calculate the gradient ∇f (x).

0.1
0.05
0

-0.05
10

12

14

Dimensionality

(a) m = b0.5nc

16

0
-0.05

-0.05
8

0.1
0.05

8

10

12

Dimensionality

(b) m = n

14

16

8

10

12

14

16

Dimensionality

(c) m = b1.5nc

Figure 3: Results on softmax instances with polytope constraints generated from uniform distribution.
Results on synthetic data. We generate the softmax objectives (see (3)) in the following way: first
generate the n eigenvalues d ∈ Rn+ , each randomly distributed in [0, 1.5], and set D = diag(d).
After generating a random unitary matrix U, we set L = UDU> . One can verify that L is positive
semidefinite and has eigenvalues as the entries of d.
We generate the down-closed polytope constraints in the same form and same way as that for DRsubmodular quadratic functions, except for setting b = 2 ∗ 1m . Function values returned by different
solvers w.r.t. n are shown in Figure 3, for which the random polytope constraints were generated
with uniform distribution (results for which the random polytope constraints were generated with
exponential distribution are deferred to Appendix G). The number of constraints was set to be
m = b0.5nc, m = n and m = b1.5nc in Figures 3a to 3c, respectively. One can observe that
TWO - PHASE F RANK -W OLFE still has the best performance, the non-monotone F RANK -W OLFE
variant follows, and P ROJ G RAD has the worst performance.
Real-world results on matched summarization. The task of “matched summarization” is to select
a set of document pairs out of a corpus of documents, such that the two documents within a pair
are similar, and the overall set of pairs is as diverse as possible. The motivation for this task is very
practical: it could be, for example, to compare the opinions of various politicians on a range of
representative topics.
In our experiments, we used a similar setting to the one in [20]. We experimented on the 2012
US Republican debates data, which consists of 8 candidates: Bachman, Gingrich, Huntsman, Paul,
Perry, Romney and Santorum. Each task involves one pair of candidates, so in total there are
8

Function value

Function value

28 = 7 ∗ 8/2 tasks. Figure 4a plots the averaged function values returned by the three solvers over 28
tasks, w.r.t. different values of a hyperparameter reflecting the matching quality (details see [20]).
Figure 4b traces the objectives
w.r.t.
iterations for a spe2.5
cific
candidate
pair (Bachman,
10
2
Romney). For TWO - PHASE
8
F RANK -W OLFE, the objectives
1.5
6
of
the selected phase were plot1
4
ted.
One can see that TWO 0.5
2
PHASE F RANK -W OLFE also
0
0.2
0.4
0.6
0.8
1
0
20
40
60
80
100
achieves the best performance,
Match quality controller
Iteration
while
the performance of non(a) Average on 28 tasks
(b) Objectives w.r.t. iterations
monotone F RANK -W OLFE variant and P ROJ G RAD is comparaFigure 4: Results on 2012 US Republican debates data.
ble.

6

Related Work

Submodular optimization and, more broadly, non-convex optimization are extensively studied in the
literature, which renders it very difficult comprehensively surveying all previous work. Here we only
briefly summarize some of the most related papers.
Submodular optimization over integer-lattice and continuous domains. Many results from submodular set function optimization have been generalized to the integer-lattice case [34; 33; 12; 24].
Of particular interest is the reduction [12] from an integer-lattice DR-submodular maximization problem to a submodular set function maximization problem. Submodular optimization over continuous
domains has attracted considerable attention recently [3; 4; 36]. Two classes of functions that are
covered by continuous submodularity are the Lovasz extensions [28] and multilinear extensions
[6] of submodular set functions. Particularly, multilinear extensions of submodular set functions
are also continuous DR-submodular [3], but with the special property that they are coordinate-wise
linear. Combined with the rounding technique of contention resolution [7], maximizing multilinear
extensions [38; 19; 13; 8; 11] has become the state-of-the-art method for submodular set function
maximization. Some of the techniques in maximizing multilinear extensions [13; 7; 8] have inspired
this work. However, we are the first to explore the rich properties and devise algorithms for the
general constrained DR-submodular maximization problem over continuous domains.
Non-convex optimization. Non-convex optimization receives a surge of attention in the past years.
One active research topic is to reach a stationary point for unconstrained optimization [35; 32; 1] or
constrained optimization [18; 27]. However, without proper assumptions, a stationary point may not
lead to any global approximation guarantee. The local-global relation (in Proposition 1) provides a
strong relation between (approximately) stationary points and global optimum, thus making it flexible
to incorporate progress in this area.

7

Conclusion

We have studied the problem of constrained non-monotone DR-submodular continuous maximization.
We explored the structural properties of such problems, and established a local-global relation. Based
on these properties, we presented a TWO - PHASE algorithm with a 1/4 approximation guarantee, and a
non-monotone F RANK -W OLFE variant with a 1/e approximation guarantee. We further generalized
submodular continuous function over conic lattices, which enabled us to model a larger class of
applications. Lastly, our theoretical findings were verified by synthetic and real-world experiments.
Acknowledgement. This research was partially supported by ERC StG 307036, by the Max Planck
ETH Center for Learning Systems, and by the ETH Zürich Postdoctoral Fellowship program.

9

References
[1] Allen-Zhu, Zeyuan and Hazan, Elad. Variance reduction for faster non-convex optimization. In
International Conference on Machine Learning (ICML), pp. 699–707, 2016.
[2] Antoniadis, Anestis, Gijbels, Irène, and Nikolova, Mila. Penalized likelihood regression for
generalized linear models with non-quadratic penalties. Annals of the Institute of Statistical
Mathematics, 63(3):585–615, 2011.
[3] Bach, Francis. Submodular functions: from discrete to continous domains. arXiv preprint
arXiv:1511.00394, 2015.
[4] Bian, Andrew An, Mirzasoleiman, Baharan, Buhmann, Joachim M., and Krause, Andreas.
Guaranteed non-convex optimization: Submodular maximization over continuous domains. In
International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 111–120, 2017.
[5] Boyd, Stephen and Vandenberghe, Lieven. Convex optimization. Cambridge university press,
2004.
[6] Calinescu, Gruia, Chekuri, Chandra, Pál, Martin, and Vondrák, Jan. Maximizing a submodular set function subject to a matroid constraint. In Integer programming and combinatorial
optimization, pp. 182–196. Springer, 2007.
[7] Chekuri, Chandra, Vondrák, Jan, and Zenklusen, Rico. Submodular function maximization via
the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43
(6):1831–1879, 2014.
[8] Chekuri, Chandra, Jayram, TS, and Vondrák, Jan. On multiplicative weight updates for concave
and submodular function maximization. In Proceedings of the 2015 Conference on Innovations
in Theoretical Computer Science, pp. 201–210. ACM, 2015.
[9] Djolonga, Josip and Krause, Andreas. From map to marginals: Variational inference in bayesian
submodular models. In Neural Information Processing Systems (NIPS), pp. 244–252, 2014.
[10] Eghbali, Reza and Fazel, Maryam. Designing smoothing functions for improved worst-case
competitive ratio in online optimization. In Advances in Neural Information Processing Systems
(NIPS), pp. 3279–3287. 2016.
[11] Ene, Alina and Nguyen, Huy L. Constrained submodular maximization: Beyond 1/e. In
Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 248–257,
2016.
[12] Ene, Alina and Nguyen, Huy L. A reduction for optimizing lattice submodular functions with
diminishing returns. arXiv preprint arXiv:1606.08362, 2016.
[13] Feldman, Moran, Naor, Joseph, and Schwartz, Roy. A unified continuous greedy algorithm
for submodular maximization. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd
Annual Symposium on, pp. 570–579. IEEE, 2011.
[14] Friedland, S and Gaubert, S. Submodular spectral functions of principal submatrices of a
hermitian matrix, extensions and applications. Linear Algebra and its Applications, 438(10):
3872–3884, 2013.
[15] Fuchssteiner, Benno and Lusky, Wolfgang. Convex cones, volume 56. Elsevier, 2011.
[16] Fujishige, Satoru. Submodular functions and optimization, volume 58. Elsevier, 2005.
[17] Garg, Vijay K. Introduction to lattice theory with computer science applications. John Wiley &
Sons, 2015.
[18] Ghadimi, Saeed, Lan, Guanghui, and Zhang, Hongchao. Mini-batch stochastic approximation
methods for nonconvex stochastic composite optimization. Mathematical Programming, 155
(1-2):267–305, 2016.
[19] Gharan, Shayan Oveis and Vondrák, Jan. Submodular maximization by simulated annealing. In
Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp.
1098–1116. Society for Industrial and Applied Mathematics, 2011.
[20] Gillenwater, Jennifer, Kulesza, Alex, and Taskar, Ben. Near-optimal map inference for determinantal point processes. In Advances in Neural Information Processing Systems (NIPS), pp.
2735–2743, 2012.
10

[21] Hassani, Hamed, Soltanolkotabi, Mahdi, and Karbasi, Amin. Gradient methods for submodular
maximization. In Advances in Neural Information Processing Systems (NIPS), pp. 5837–5847,
2017.
[22] Ito, Shinji and Fujimaki, Ryohei. Large-scale price optimization via network flow. In Advances
in Neural Information Processing Systems (NIPS), pp. 3855–3863, 2016.
[23] Iwata, Satoru, Fleischer, Lisa, and Fujishige, Satoru. A combinatorial strongly polynomial
algorithm for minimizing submodular functions. Journal of the ACM, 48(4):761–777, 2001.
[24] Khodabakhsh, Ali and Nikolova, Evdokia. Maximizing non-monotone dr-submodular functions
with cardinality constraints. arXiv preprint arXiv:1611.09474, 2016.
[25] Krause, Andreas and Golovin, Daniel. Submodular function maximization. Tractability:
Practical Approaches to Hard Problems, 3:19, 2012.
[26] Kulesza, Alex, Taskar, Ben, et al. Determinantal point processes for machine learning. Foundations and Trends R in Machine Learning, 5(2–3):123–286, 2012.
[27] Lacoste-Julien, Simon. Convergence rate of frank-wolfe for non-convex objectives. arXiv
preprint arXiv:1607.00345, 2016.
[28] Lovász, László. Submodular functions and convexity. In Mathematical Programming The State
of the Art, pp. 235–257. Springer, 1983.
[29] Montanari, Andrea and Richard, Emile. Non-negative principal component analysis: Message
passing algorithms and sharp asymptotics. IEEE Transactions on Information Theory, 62(3):
1458–1484, 2016.
[30] Motzkin, Theodore S and Straus, Ernst G. Maxima for graphs and a new proof of a theorem of
turán. Canad. J. Math, 17(4):533–540, 1965.
[31] Nemhauser, George L, Wolsey, Laurence A, and Fisher, Marshall L. An analysis of approximations for maximizing submodular set functions – i. Mathematical Programming, 14(1):265–294,
1978.
[32] Reddi, Sashank J., Sra, Suvrit, Poczos, Barnabas, and Smola, Alexander J. Proximal stochastic
methods for nonsmooth nonconvex finite-sum optimization. In Advances in Neural Information
Processing Systems (NIPS), pp. 1145–1153. 2016.
[33] Soma, Tasuku and Yoshida, Yuichi. A generalization of submodular cover via the diminishing
return property on the integer lattice. In Advances in Neural Information Processing Systems
(NIPS), pp. 847–855, 2015.
[34] Soma, Tasuku, Kakimura, Naonori, Inaba, Kazuhiro, and Kawarabayashi, Ken-ichi. Optimal
budget allocation: Theoretical guarantee and efficient algorithm. In International Conference
on Machine Learning (ICML), pp. 351–359, 2014.
[35] Sra, Suvrit. Scalable nonconvex inexact proximal splitting. In Advances in Neural Information
Processing Systems (NIPS), pp. 530–538, 2012.
[36] Staib, Matthew and Jegelka, Stefanie. Robust budget allocation via continuous submodular
functions. In International Conference on Machine Learning (ICML), pp. 3230–3240, 2017.
[37] Topkis, Donald M. Minimizing a submodular function on a lattice. Operations research, 26(2):
305–321, 1978.
[38] Vondrák, Jan. Optimal approximation for the submodular welfare problem in the value oracle
model. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 67–74,
2008.
[39] Xia, Wei, Vera, Juan, and Zuluaga, Luis F. Globally solving non-convex quadratic programs via
linear integer programming techniques. arXiv preprint arXiv:1511.02423, 2015.
[40] Zass, Ron and Shashua, Amnon. Nonnegative sparse pca. Advances in Neural Information
Processing Systems (NIPS), pp. 1561–1568, 2007.

11

Appendix
A

Continuous Submodular Functions on Conic Lattices and the Reduction

Motivated by the objectives that can not be modeled by continuous submodular functions, we
consider the more general submodular continuous functions over lattices induced by conic inequalities.
Furthermore we provide a reduction to the original (DR-)submodular optimization problem.
A.1

Definitions and Properties

Let us look at the proper cone that will be used to define a conic inequality firstly. A cone K ⊆ Rn
is a proper cone if it is convex, closed, solid (having nonempty interior) and pointed (contains no
line, i.e., x ∈ K, −x ∈ K implies x = 0). A proper cone K can be used to define a conic inequality
(a.k.a. generalized inequality [5, Chapter 2.4]): a K b iff b − a ∈ K, which also defines a partial
ordering since the binary relation K is reflexive, antisymmetric and transitive. Then it is easy to see
that (X , K ) is a partial ordered set (poset).
If two elements a, b ∈ X have a least upper bound (greatest lower bound), it is denoted as the “join”:
a ∨ b (the “meet”: a ∧ b). A lattice is a poset that contains the join and meet of each pair of its
elements [17]. A “lattice cone” [15] is the proper cone that can be used to define a lattice. Note that
not all conic inequalities can be used to define a lattice. For example, the positive semidefine cone
KPSD = {A ∈ Rn×n |A is symmetric, A  0} is a proper cone, but its induced ordering can not be
used to define a lattice. There is a simple counter example to show this in Appendix F.2.
Specifically, we name the lattice that can be defined through a conic inequality as “conic lattice”,
since it is of particular interest for modeling the real-world applications in this paper.
Definition 4 (Conic Lattice). Given a poset (X , K ) induced by the conic inequality K , if there
exist joint and meet operations for every pair of elements (a, b) in X × X , s.t. a ∨ b and a ∧ b are
still in X , then we call (X , K ) a conic lattice.
In one word, a conic lattice (X , K ) is a lattice induced by a conic inequality K . In the following
we introduce a class of conic lattices to model the applications in this work. We further provide a
general characterization about submodularity on this conic lattice.
Orthant conic lattice. Given a sign vector α ∈ {±1}n , the orthant cone is defined as Kα :=
{x ∈ Rn | xi αi ≥ 0, ∀i ∈ [n]}, one can see that Kα is a proper cone. For any two points
a, b ∈ X , one can further define the join and meet operations: (a ∨ b)i := αi max{αi ai , αi bi },
(a ∧ b)i := αi min{αi ai , αi bi }, ∀i ∈ [n]. Then one can show that the poset (X , Kα ) is a conic
lattice.
A function f : X 7→ R is submodular on a lattice [37; 16] if for all (x, y) ∈ X × X , it holds that,
f (x) + f (y) ≥ f (x ∨ y) + f (x ∧ y).

(12)

One can establish the characterizations of submodularity on the orthant conic lattice (X , Kα )
similarly as that in [4]:
Proposition 2 (Characterizations of Submodularity on Orthant Conic Lattice (X , Kα )). If a function
f is is submodular on the lattice (X , Kα ) (called Kα -submodular), then we have the following two
equivalent characterizations:
a) ∀a, b ∈ X s.t. a Kα b, ∀i s.t. ai = bi , ∀k ∈ R+ s.t. (kei + a) and (kei + b) are still in X , it
holds that,
αi [f (kei + a) − f (a)] ≥ αi [f (kei + b) − f (b)].

(weak DR)

(13)

b) If f is twice differentiable, then ∀x ∈ X it holds,
αi αj ∇2ij f (x) ≤ 0, ∀i, j ∈ [n], i 6= j.

(14)

Proposition 2 can be proved by directly generalizing the proof of Proposition 1 in [4], proof is omitted
here due to the high similarity. Next, we generalize the definition of DR-submodularity to the conic
lattice (X , Kα ):
12

Definition 5 (Kα -DR-submodular). A function f : X 7→ R is Kα -DR-submodular if ∀a, b ∈ X s.t.
a Kα b, ∀i ∈ [n], ∀k ∈ R+ s.t. (kei + a) and (kei + b) are still in X , it holds that,
αi [f (kei + a) − f (a)] ≥ αi [f (kei + b) − f (b)].

(15)

In correspondence to the relation between DR-submodularity and submodularity over continuous
domains (Proposition 2 in [4]), one can easily get the similar relation (with highly similar proof) in
bellow:
Proposition 3 (Kα -submodular + coordinate-wise concave ⇔ Kα -DR-submodular). A function f is
Kα -DR-submodular iff it is Kα -submodular and coordinate-wise concave.
Combining (14) and Proposition 3, one can show that if f is twice differentiable and Kα -DRsubmodular, then ∀x ∈ X it holds that,
αi αj ∇2ij f (x) ≤ 0, ∀i, j ∈ [n].

(16)

Similarly, a function f is Kα -DR-supermodular iff −f is Kα -DR-submodular.
Remark: We only consider the orthant conic lattice (X , Kα ) here, since it can already model
the applications in this paper. However, it is noteworthy that the framework can be generalized to
arbitrary conic lattices, which may be of interest to model more complicated applications. We left
this as future exploration.
A.2

A Reduction to Optimizing Submodular Functions over Continuous Domains

To be succint, in this section we only discuss the reduction for the Kα -DR-submodular maximization
problems. However, it is easy to see that the reduction works for all kinds of Kα -submodular
optimization problems, e.g., Kα -submodular minimization problem.
Suppose g is a Kα -DR-submodular function, and the Kα -DR-submodular maximization problem
is maxy∈P 0 g(y), where P 0 = {y ∈ Rn |hi (y) ≤ bi , ∀i ∈ [m], y Kα 0} is down-closed w.r.t. the
conic inequality Kα . The down-closedness here means if a ∈ P 0 and 0 Kα b Kα a, then
b ∈ P 0 as well.
Let A := diag(α), and a function f (x) := g(Ax). One can see that if g is Kα -DR-submodular,
then f is DR-submodular: assume wlog.3 that g is twice differentiable, then ∇2 f (x) = A> ∇2 gA,
and ∇2ij f (x) = αi αj ∇2ij g ≤ 0, so f is DR-submodular.
By the affine transformation y := Ax, one can transform the Kα -DR-submodular maximization problem to be a DR-submodular maximization problem maxx∈P g(Ax), where P = {x ∈
Rn |hi (Ax) ≤ bi , ∀i ∈ [m], Ax Kα 0} is down-closed w.r.t. the ordinary component-wise inequality ≤. To verify the down-closedness of P w.r.t. to the ordinary inequality ≤ here, let y1 = Ax1 ∈ P 0
(so x1 ∈ P). Suppose there is a point y2 = Ax2 s.t. 0 Kα y2 Kα y1 . From the down-closedness
of P 0 , we know that y2 ∈ P 0 , thus x2 ∈ P. Looking at 0 Kα y2 Kα y1 , it is equivalent to that
0 ≤ x2 ≤ x1 . Thus we establish the down-closedness of P.
Given the reduction, we can reuse the algorithms for the original DR-submodular maximization
problem (P).
A.3

Proof for the Logistic Loss in Section 2.1

Remember that the logistic loss is:
1 Xm
1 Xm
fj (x) =
log(1 + exp(−yj x> z j ))
l(x) =
j=1
j=1
m
m

(17)

Claim 3. l(x) in (17) is Kα -DR-supermodular.
Proof of Claim 3. To show that l(x) is Kα -DR-supermodular, we can check the second-order condition in (16), that is, whether it holds that αp αq ∇2pq l(x) ≥ 0, ∀p, q ∈ [n]. One can easily see
3

If not one can still use other equivalent characterizations, for instance, the characterization in (12) or in (13)
to formulate this.

13

that,
−yj zpj
∂l(x)
1 Xm
=
j=1 exp (yj x> z j ) + 1
∂xp
m
2
∂ l(x)
1 Xm
exp (yj x> z j )
zpj zqj .
=
j=1 [exp (yj x> z j ) + 1]2
∂xp ∂xq
m
Since αp = sign(zpj ), so αp αq ∇2pq l(x) ≥ 0, ∀p, q ∈ [n]. Thus l(x) in (17) is Kα -DR-supermodular
according to (16).

B

More Applications

We present more applications that fall into submodular or Kα -submodular optimization problems.
One class of notable examples are the objectives studied in [10] in the online setting. These objectives
are captured by the DR-submodular property over continuous domains. One can also refer to Section
2.2 in [3] to see more examples.
DR-submodular quadratic functions. Price optimization with continuous prices is a DRsubmodular quadratic optimization problem [22]. Another representative class of DR-submodular
quadratic objectives arises when computing the stability number s(G) of a graph G = (V, E) [30],
−1
s(G) = minx∈∆ x> (A + I)x, where A is the adjacency matrix of the graph G, ∆ is the standard
simplex. This is an instance of a convex-constrained DR-submodular maximization problem.
Non-negative PCA (NN-PCA). NN-PCA [40; 29] is widely used as alternative models of PCA for
dimension reduction, since its projection involves only non-negative weights—a required property
in fields like economics, bioinformatics and computer vision. For a given set of m data points
z j ∈ Rn , j ∈ [m], NN-PCA aims to solve the following non-convex optimization problem:
Xm

1
>
min
f (x) := − x>
zj zj
x.
(18)
j=1
2
kxk2 ≤1,x≥0
Let A =

Pm

j=1

>

z j z j , one can see that,
App =

Xm
j=1

(zpj )2 ≥ 0, Apq =

Xm
j=1

zpj zqj = Aqp .

Let us make the following weak assumption: For one dimension/feature i, all the data points have
the same sign, i.e., sign(zij ) is the same for all j ∈ [m] (which can be achieved by easily scaling
if not). Now, by choosing the sign vector α ∈ {±1}n to be αp = sign(zpj ), ∀p ∈ [n], one can
easily verify that Apq αp αq ≥ 0, ∀p, q ∈ [n]. Notice that ∇2 f in (18) is −A, so it holds that
αp αq ∇2pq f ≤ 0, ∀p, q ∈ [n], thus f (x) is Kα -DR-submodular according to (16). Thus we can treat
(18) as a constrained Kα -DR-submodular minimization problem.
Submodular spectral functions. As discussed by [3], submodular spectral functions [14] in the
following form are DR-submodular,

Xn
f (x) = log det
xi Ai , x ∈ Rn+ ,
(19)
i=1

where Ai are positive definite matrices. One can check the DR-submodularity of f (x) by checking
its second-order-derivatives.

C

The Subroutine Algorithm
0

Algorithm 3 is taken from [27], the only difference lies in the output: we output the solution x(k )
with the minimum non-stationarity, which is needed to apply the local-global relation. While [27]
outputs the solution in the last step. Since Cf (P) is generally hard to evaluate, we used the classical
2
F RANK -W OLFE step size k+2
in the experiments.
14

Algorithm 3: N ON - CONVEX F RANK -W OLFE (f, P, K, , x(0) )[27]
Input: maxx∈P f (x), P: convex set, K: number of iterations, : stopping tolerance
1 for k = 0, ..., K do
2
find v (k) s.t. hv (k) , ∇f (x(k) )i ≥ maxv∈P hv, ∇f (x(k) )i;
// LMO
3
dk ← v (k) − x(k) , gk := hdk , ∇f (x(k) )i ;
// gk : non-stationarity measure
4
if gk ≤  then return x(k) ;
5
Option I: γk ∈ arg minγ∈[0,1] f (x(k) + γd(k) ), Option II: γk ← min{ gCk , 1} for
C ≥ Cf (P) ;
6
x(k+1) ← x(k) + γk d(k) ;
0

Output: x(k ) and gk0 = min0≤k≤K gk ;

D
D.1

// modified output solution compared to [27]

Proofs for Properties
Proof of Lemma 1

Proof of Lemma 1. Since f is DR-submodular, so it is concave along any direction v ∈ ±Rn+ . We
know that x ∨ y − x ≥ 0 and x ∧ y − x ≤ 0, so from the strong DR-submodularity in (6),
µ
f (x ∨ y) − f (x) ≤ h∇f (x), x ∨ y − xi − kx ∨ y − xk2 ,
2
µ
f (x ∧ y) − f (x) ≤ h∇f (x), x ∧ y − xi − kx ∧ y − xk2 .
2
Summing the above two inequalities and notice that x ∨ y + x ∧ y = x + y, we arrive,
µ
(y − x)> ∇f (x) ≥ f (x ∨ y) + f (x ∧ y) − 2f (x) + (kx ∨ y − xk2 + kx ∧ y − xk2 )
2
µ
= f (x ∨ y) + f (x ∧ y) − 2f (x) + ky − xk2 ,
2
the last equality holds since kx ∨ y − xk2 + kx ∧ y − xk2 = ky − xk2 .
D.2

Proof of Proposition 1

Proof of Proposition 1. Consider the point z ∗ := x ∨ x∗ − x = (x∗ − x) ∨ 0. One can see that: 1)
0 ≤ z ∗ ≤ x∗ ; 2) z ∗ ∈ P (down-closedness); 3) z ∗ ∈ Q (because of z ∗ ≤ ū − x). From Lemma 1,
µ
hx∗ − x, ∇f (x)i + 2f (x) ≥ f (x ∨ x∗ ) + f (x ∧ x∗ ) + kx − x∗ k2 ,
(20)
2
µ
(21)
hz ∗ − z, ∇f (z)i + 2f (z) ≥ f (z ∨ z ∗ ) + f (z ∧ z ∗ ) + kz − z ∗ k2 .
2
Let us first of all prove the following key Claim.
Claim 1. It holds that f (x ∨ x∗ ) + f (x ∧ x∗ ) + f (z ∨ z ∗ ) + f (z ∧ z ∗ ) ≥ f (x∗ ).
Proof of Claim 1. Firstly, we are going to prove that
f (x ∨ x∗ ) + f (z ∨ z ∗ ) ≥ f (z ∗ ) + f ((x + z) ∨ x∗ ),

(22)

which is equivalent to f (x ∨ x∗ ) − f (z ∗ ) ≥ f ((x + z) ∨ x∗ ) − f (z ∨ z ∗ ). It can be shown that
x ∨ x∗ − z ∗ = (x + z) ∨ x∗ − z ∨ z ∗ . Combining this with the fact that z ∗ ≤ z ∨ z ∗ , and using
the DR property (see (1)) implies (22). Then we establish,
x ∨ x∗ − z ∗ = (x + z) ∨ x∗ − z ∨ z ∗ .

(23)

We will show that both the RHS and LHS of the above equation are equal to x: for the LHS of (23)
we can write x ∨ x∗ − z ∗ = x ∨ x∗ − (x ∨ x∗ − x) = x. For the RHS of (23) let us consider any
coordinate i ∈ [n],
(xi + zi ) ∨ x∗i − zi ∨ zi∗ = (xi + zi ) ∨ x∗i − ((xi + zi ) − xi ) ∨ ((xi ∨ x∗i ) − xi ) = xi ,
15

where the last equality holds easily for the two situations: (xi + zi ) ≥ x∗i and (xi + zi ) < x∗i .
Next, we are going to prove that,
f (z ∗ ) + f (x ∧ x∗ ) ≥ f (x∗ ) + f (0)
(24)
∗
it is equivalent to f (z ) − f (0) ≥ f (x∗ ) − f (x ∧ x∗ ), which can be done similarly by the DR
property: Notice that
x∗ − x ∧ x∗ = x ∨ x∗ − x = z ∗ − 0 and 0 ≤ x ∧ x∗
thus (24) holds from the DR property. Combining (22) and (24) one can get,
f (x ∨ x∗ ) + f (z ∨ z ∗ ) + f (x ∧ x∗ ) + f (z ∧ z ∗ ) ≥ f (x∗ ) + f (0) + f ((x + z) ∨ x∗ ) + f (z ∧ z ∗ )
≥ f (x∗ ) (non-negativity of f ) .

Combining (20) and (21) and Claim 1 it reads,
hx∗−x, ∇f (x)i+ hz ∗−z, ∇f (z)i+ 2(f (x) + f (z)) ≥ f (x∗ ) +

µ
(kx−x∗ k2 + kz−z ∗ k2 ) (25)
2

From the definition of non-stationarity in (8) one can get,
x∗ ∈P

gP (x) := maxhv − x, ∇f (x)i ≥ hx∗ − x, ∇f (x)i

(26)

v∈P

∗

z ∈Q

gQ (z) := maxhv − z, ∇f (z)i ≥ hz ∗ − z, ∇f (z)i

(27)

v∈Q

Putting together (25) to (27) we can get,
µ
(kx − x∗ k2 + kz − z ∗ k2 ).
2
so it arrives max{f (x), f (z)} ≥ 14 [f (x∗ ) − gP (x) − gQ (z)] + µ8 (kx − x∗ k2 + kz − z ∗ k2 ).
2(f (x) + f (z)) ≥ f (x∗ ) − gP (x) − gQ (z) +

E
E.1

Proofs for Algorithms
Proof of Theorem 1

Proof of Theorem 1. Let gP (x), gQ (z) to be the non-stationarity of x and z, respectively. Since we
are using the NON - CONVEX F RANK -W OLFE (Algorithm 3) as subroutine, according to [27, Theorem
1], one can get,


max{2h1 , Cf (P)}
√
gP (x) ≤ min
, 1
K1 + 1


max{2h2 , Cf (Q)}
√
, 2 ,
gQ (z) ≤ min
K2 + 1
Plugging the above into Proposition 1 we reach the conclusion in (10).
E.2

Proof of Lemma 2
(k)

Lemma 2. Assume x(0) = 0. For k = 0, ..., K − 1, it holds xi

(k)

≤ ūi [1 − (1 − γ)t

/γ

], ∀i ∈ [n].

(0)

Proof of Lemma 2. We prove by induction. First of all, it holds when k = 0, since xi
t(0) = 0 as well. Assume it holds for k. Then for k + 1, we have
(k+1)

xi

(k)

+ γvi

≤ xi

(k)

+ γ(ūi − xi ) (constraint of shrunken LMO)

= (1 −

(k)
γ)xi

= xi

= 0, and

(k)
(k)

(28)

+ γ ūi

≤ (1 − γ)ūi [1 − (1 − γ)t
= ūi [1 − (1 − γ)t

(k+1)

/γ

(k)

].

16

/γ

] + γ ūi

(induction)

(29)

E.3

Proof of Lemma 3

Lemma 3 (Generalized from Lemma 7 in [8]). Given θ ∈ (0, ū], let λ0 = mini∈[n]
x ∈ [0, θ], it holds f (x ∨ x∗ ) ≥ (1 − λ10 )f (x∗ ).

ūi
θi .

Then for all

Proof of Lemma 3. Consider r(λ) = x∗ + λ(x ∨ x∗ − x∗ ), it is easy to see that r(λ) ≥ 0, ∀λ ≥ 0.
Notice that λ0 ≥ 1. Let y = r(λ0 ) = x∗ + λ0 (x ∨ x∗ − x∗ ), it is easy to see that y ≥ 0, it also hold
that y ≤ ū: Consider one coordinate i, 1) if xi ≥ x∗i , then yi = x∗i +λ0 (xi −x∗i ) ≤ λ0 xi ≤ λ0 θi ≤ ūi ;
2) if xi < x∗i , then yi = x∗i ≤ ūi . So f (y) ≥ 0.
Note that

1 ∗
1
1
1
)x + 0 y = (1 − 0 )r(0) + 0 r(λ0 ),
0
λ
λ
λ
λ
since f is concave along r(λ), so it holds that,
x ∨ x∗ = (1 −

f (x ∨ x∗ ) ≥ (1 −

E.4

1
1
1
)f (x∗ ) + 0 f (y) ≥ (1 − 0 )f (x∗ ).
λ0
λ
λ

Proof of Theorem 2

Proof of Theorem 2. First of all, let us prove the Claim:
Claim 2. For k = 0, ..., K −1 it holds f (x(k+1) ) ≥ (1−γ)f (x(k) )+γ(1−γ)t

(k)

/γ

2

2
f (x∗ )− LD
2 γ ,

Proof of Claim 2. Consider a point z (k) := x(k) ∨ x∗ − x(k) , one can observe that: 1) z (k) ≤
ū − x(k) ; 2) since x(k) ≥ 0, x∗ ≥ 0, so z (k) ≤ x∗ , which implies that z (k) ∈ P (from downclosedness of P). So z (k) is a candidate solution for the new LMO (Step 3). We have,
L 2 (k) 2
γ kv k (Quadratic lower bound from (5))
2
L
≥ γh∇f (x(k) ), v (k) i − γ 2 D2 (diameter of P)
2
L 2 2
(k)
(k)
≥ γh∇f (x ), z i − γ D (shrunken LMO)
2
L
(k)
(k)
≥ γ(f (x + z ) − f (x(k) )) − γ 2 D2 (concave along z (k) )
2
L
= γ[f (x(k) ∨ x∗ ) − f (x(k) )] − γ 2 D2
2
1
L
≥ γ[(1 − 0 )f (x∗ ) − f (x(k) )] − γ 2 D2 (Lemma 3)
λ
2
(k)
L
= γ[(1 − γ)t /γ f (x∗ ) − f (x(k) )] − γ 2 D2
2

f (x(k+1) ) − f (x(k) ) ≥ γh∇f (x(k) ), v (k) i −

(k)

where the last equality comes from setting θ := ū(1 − (1 − γ)t
(k)
λ0 = mini ūθii = (1 − (1 − γ)t /γ )−1 .

/γ

) according to Lemma 2, thus

After rearrangement, we reach the claim.
Then, let us prove Theorem 2 by induction.
First of all, it holds when k = 0 (notice that t(0) = 0). Assume that it holds for k. Then for k + 1,
considering the fact e−t − O(γ) ≤ (1 − γ)t/γ when 0 < γ ≤ t ≤ 1 and Claim 2 we get,
f (x(k+1) )
≥ (1 − γ)f (x(k) ) + γ(1 − γ)t

(k)

/γ

f (x∗ ) −

LD2 2
γ
2
17

≥ (1 − γ)f (x(k) ) + γ[e−t
≥ (1 − γ)[t(k) e−t

(k)

= [(1 − γ)t(k) e−t

(k)

≥ [(1 − γ)t(k) e−t

(k)

(k)

− O(γ)]f (x∗ ) −

LD2 2
γ
2

(30)

(k)
LD2 2
LD2 2
kγ − O(γ 2 )f (x∗ )] + γ[e−t − O(γ)]f (x∗ ) −
γ
2
2
2
(k)
LD 2
γ [(1 − γ)k + 1] − [(1 − γ)O(γ 2 ) + γO(γ)]f (x∗ )
+ γe−t ]f (x∗ ) −
2
(k)
LD2 2
γ (k + 1) − O(γ 2 )f (x∗ ).
+ γe−t ]f (x∗ ) −
(31)
2

f (x∗ ) −

(k)

(k)

Let us consider the term [(1 − γ)t(k) e−t + γe−t ]f (x∗ ). We know that the function g(t) = te−t
is concave in [0, 2], so g(t(k) + γ) − g(t(k) ) ≤ γg 0 (t(k) ), which amounts to
(k)

[(1 − γ)t(k) e−t

(k)

+ γe−t

(k)

]f (x∗ ) ≥ (t(k) + γ)e−(t

+γ)

(k+1)

f (x∗ ) = t(k+1) e−t

f (x∗ )

(32)

Plugging (32) into (31) we get,
f (x(k+1) ) ≥ t(k+1) e−t

(k+1)

f (x∗ ) −

LD2 2
γ (k + 1) − O(γ 2 )f (x∗ ).
2

Thus proving the induction, and proving the theorem as well.

F

Miscellaneous Results

F.1

Verifying DR-submodularity of the Objectives

Softmax extension. For softmax extension, the objective is,
f (x) = log det (diag(x)(L − I) + I) , x ∈ [0, 1]n .
Its DR-submodularity can be established by directly applying Lemma 3 in [20]: [20, Lemma 3]
immediately implies that all entries of ∇2 f are non-positive, so f (x) is DR-submodular.
Multilinear extension. The DR-submodularity of multilinear extension can be directly recognized
by considering the conclusion in Appendix A.2 of [3] and the fact that multilinear extension is
coordinate-wise linear.
P
x (S)
KL(x). The Kullback-Leibler divergence between qx and p, i.e., S⊆V qx (S) log qp(S)
is,
KL(x) = −

XY
S⊆V i∈S

xi

Y
j ∈S
/

(1 − xj )F (S) +

Xn
i=1

[xi log xi + (1 − xi ) log(1 − xi )] + log Z.

The first term is the negative of a multilinear extension, so it is DR-supermodular. The second term
is separable, and coordinate-wise convex, so it will not affect the off-diagonal entries of ∇2 KL(x),
it will only contribute to the diagonal entries. Now, one can see that all entries of ∇2 KL(x) are
non-negative, so KL(x) is DR-supermodular w.r.t. x.
F.2

A Counter Example to Show PSD Cone is not Lattice

The positive semidefine cone KPSD = {A ∈ Rn×n |A is symmetric, A  0} is a proper cone, but
not a lattice cone. That is, it can not be used to define a lattice over the space of symmetric matrices.
Let us consider the two dimensional symmetric matrix space S 2 . Specifically, the following two
symmetric matrices,




1 0
0 0
X=
,Y =
.
0 0
0 1
For the conic inequality KPSD , assume that there exists a least upper bound, i.e., the join of X, Y:
Z := X ∨ Y. From the definition of least upper bound, ∀ W ∈ S 2 it should hold that,
W KPSD X and W KPSD Y iff W KPSD Z.
18

(33)



b a
Suppose Z =
. Firstly, consider W to be diagonal matrices, one can verify that Z must be in
a c


1 a
the form of
, then considering W = I forcing Z to be I.
a 1




2 2 1
1 1 2
Now let W = 3
, which is KPSD X and KPSD Y. However, W − I = 3
∈
/ KPSD ,
1 2
2 1
thus contradicting (33).

G

Additional Experimental Results

We generate the down-closed polytope constraints in the same form and same way as that for
DR-submodular quadratic functions.
Figure 5 shows the function values returned by different solvers w.r.t. n, for which the random
polytope constraints were generated with exponential distribution. Specifically, the random polytope
m
is in the form of P = {x ∈ Rn+ | Ax ≤ b, x ≤ ū, A ∈ Rm×n
++ , b ∈ R+ }. Each entry of A was
sampled from Exp(1) + ν, where ν = 0.01 is a small positive constant. We set b = 2 ∗ 1m , and
i
, ∀j ∈ [n]. One can see that the
set ū to be the tightest upper bound of P by ūj = mini∈[m] Abij
TWO - PHASE F RANK -W OLFE has the best performance, while non-monotone F RANK -W OLFE and
P ROJ G RAD have comparable performance.

0.1

0.1

0.08

0.08

0.06
0.04

Function value

Function value

Function value

0.06

0.06
0.04
0.02

0.02

0.05
0.04
0.03
0.02

0
8

10

12

14

Dimensionality

(a) m = b0.5nc

16

8

10

12

Dimensionality

(b) m = n

14

16

8

10

12

14

16

Dimensionality

(c) m = b1.5nc

Figure 5: Results on softmax instances with random polytope constraints generated from exponential
distribution.

19

