Submodular + Concave
Authors: Siddharth Mitra
Moran Feldman
amin karbasi
Venue: NeurIPS 2021 Poster (2021)
Keywords: submodular optimization
non-convex optimization
Frank-Wolfe like algorithms
non-convex quadratic programming

Abstract: It has been well established that first order optimization methods can converge to the maximal objective value of concave functions and provide constant factor approximation guarantees for (non-convex/non-concave) continuous submodular functions. In this work, we initiate the study of the maximization of functions of the form $F(x) = G(x) +C(x)$ over a solvable convex body $P$, where $G$ is a smooth DR-submodular function and $C$ is a smooth concave function. This class of functions is a strict extension of both concave and continuous DR-submodular functions for which no theoretical guarantee is known. We provide a suite of Frank-Wolfe style algorithms, which, depending on the nature of the objective function (i.e., if $G$ and $C$ are monotone or not, and non-negative or not) and on the nature of the set $P$ (i.e., whether it is downward closed or not), provide $1-1/e$, $1/e$, or $1/2$ approximation guarantees. We then use our algorithms to get a framework to smoothly interpolate between choosing a diverse set of elements from a given ground set (corresponding to the mode of a determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines.


Submodular + Concave
Siddharth Mitra
Moran Feldman
School of Engineering & Applied Science
Department of Computer Science
Yale University
University of Haifa
New Haven, CT 06520-8299
Haifa 3498838 Israel
siddharth www.h.mmiirryy.. www.mmitaaall.l.mmmmmmmmm edu
moranf e&cs haifa. ac i1
Amin Karbasi
School of Engineering & Applied Science Yale University
New Haven, CT 06520-8292 amin. wwrbaaaaraaalle...oaa....aaaaaaa edu
Abstract
It has been well established that first order optimization methods can converge to the maximal objective value of concave functions and provide constant factor approximation guarantees for mnn-coonvexnnon-conee functions. In this work, we initiate the study of the maximization of functions of the form F(x)= = G(x) + C(x) over a solvable convex body P, where G is a smooth DR subouuuou function and C is a smooth concave function. This class functions a strict extension both concave and continuous DR -ussubmodular functions for which no theoretical guarantee is known. We provide a suite of Frank-Wole style algorithms, which, depending on the nature of the objective function (i.e., if G and C' are monotone not, and non-negative or not) and on the nature of the set P (i.e., whether it is downward closed or not), provide 1 1-11/a 1/e, L/e, 1/2 approximation guarantees. We then our algorithms to get framework to smoothly interpolate between choosing a diverse set of elements from given ground set (corresponding to the mode of determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines.
continuous submodular
Introduction
Despite their simplicity, first-order optimization methods (such as gradient descent and its variants, Frank- Wolfe, momentum based methods, and others) have shown great success in many machine learning applications. large body of research in the operations research and machine learning communities has fully demystified the convergence rate of such methods in minimizing well behaved convex objectives [Bubeck] 2015. Nesterov 2018 More recently, new surge of rigorous results has also shown that gradient descent methods can find the global minima of specific non-convex objective functions arisen from non-negative matrix factorization [Arora et al., 20122.. robust PCA [Netrapalli
et al. 2014], phase retrieval [Chen et al. 2019b), matrix completion [Sun and Luo 2016], and the training wide neural networks [Du et al. [0019 Jacot et al., 20188) Allen-Zhu al., 2019], name a few. It is also very well known that finding the global minimum of a general non-convex function is indeed computationally intractable [Murty and Kabadi [987]. To avoid such impossibility results, simpler goals have been pursued by the community: either developing algorithms that can escape
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

saddle points and reach local minima [Ge et al. 2015| or describing structural properties under which reaching a local minimizer ensures optimality Sun al. 2016 Bian al. 2017b Hazan al. 2016]. In the same spirit, this paper quantifies a large class of non-convex functions for which first-order optimization methods provably achieve near optimal solutions.
More specifically, we consider objective functions that are formed by the sum of a continuous DR- submodular function G(z)) and a concave function C(z)). Recent research in non-convex optimization
has shown that first-order optimization methods provide constant factor approximation guarantees
for maximizing continuous submodular functions Bian et al. [2017b], Hassani et al. [2017] Bian
et al. [2017a], Niazadeh et al. [2018), Hassani et al. [2020a] Mokhtari et al. [201 Similarly, such
methods find the global maximizer of concave functions. However, the class ((a) G(z)) + +C(z)
functions is strictly larger than both concave and continuous DR DRssubmodular functions. More
specifically, (xx) is not concave nor continuous DRssubmodular in general (Figure | iillustrates
an example). In this paper, we show that first-order methods provably provide strong theoretical guarantees for maximizing such functions.
The combinations of continuous submodular and concave functions naturally arise in many ML applications such as maximizing regularized submodular function (Kazemi et al. 2020a] or finding
the mode of distributions [Kazemi et al., 2020aa Robinson et al. 2019]. For instance, it is common
to add regularizer D-optimal design objective function to increase the stability of the final
solution against perturbations [H 2010 Derezinski et al. 2020 Lattimore and Szepesvari [020] Similarly, many instances of sub-uuuoo distributions, such as determinantal point processes (DPPs). have been studied in depth in order to sample diverse set of items from ground set Kulesza 2012 Rebeschini and Karbasi 2015 Anari al. 2016]. In order to control the level of diversity, one natural recipe is to consider the combination of a log-concave (e.g.. normal distribution, exponential distribution and Laplace distribution) (Dwivedi et al. 2019 Robinson et al.) 2019] and log-submodular distributions (Djolonga and Krause, 2014|Bresler Bresler et al., 2019), i.e., Pr(x) oc exp(AC(xx) + (1 (x) for some À É [0, IJ. In this way, we can obtain a class of distributions that contains log-concave and log-submodular distributions as special cases. However, this class of distributions is strictly more expressive than both log- log-concave and log-submouular models, e.g., in contrast to log-concave distributions, they are not uni-modal in general. Finding the mode of such distributions amounts to maximizing a combination of a continuous Du-submodular function and a concave function. The contributions of this paper are follows.
Assuming first-order oracle access for the function F, we develop the algorithms: GREEDY FRANK-WOLFE (Algorithm 1 and MEASURED GREEDY FRANK-WOR (Algorithm
2 which achieve constant factors approximation guarantees between 1 - 1/e and I/e depending on the setting, i.e. depending on the monotonicity and non-negativity of G and
C, and depending on the constraint set having the down-closeness property or not.
Furthermore, if we have access to the individual gradients of G and C, then we are able to make the guarantee with respect to C' exact using the algorithms: GRADIENT COMBINING FRANK-WOLL WOLFE (Algorithm 3) and NON-OBLIVIOUS FRANK- WOLFE (Algorithm These results summarized and made more precise in Table and Section
We then present experiments designed to use our algorithms to smoothly interpolate between contrasting objectives such as picking diverse set of elements and picking a clustered set of elements. This smooth interpolation provides a way to control the amount of diversity in the final solution. We also demonstrate the use of our algorithms to maximize large class of (non- wwwpeee/noonconccay quadratic programming problems,
Related Work. The study of discrete submodular maximization has flourished in the last decade through far reaching applications in machine learning and and artificial intelligence including viral marketing (Kempe et al. 2003). dictionary learning [Kausse and Cevher 2010]. sparse regression
[Elenberg et al. 2016), neural network interoperability Elenberg et al. 2017 crowd teaching (Singla
ct al. 2014], sequential decision making [Alieva et al., 2021], active learning (Wei et al., 2015). (.01s..am0 and
data summarization [Mirzasoleiman et al. 2013). We refer the interested reader to recent survey by
Tohidi et al. 2020) and the references therein.
Recently, Bian et al. [017bb proposed an extension of discrete submodular functions to the continuous domains that can of use machine learning applications. Notably, this class of (non-convex/non- concave) functions, called continuous DR-submodular, contains the continuous multilinear ex-
2

---

Figure 1: LEFT: (continuous) DR-submodular softmax extension. MIDDLE: concave quadratic function. RIGHT: sum of both.
tension of discrete submodular functions Calinescu al. [201T] special case. Continuous
DR-submodular functions can reliably model revenue maximization [Bian et al. 2017b]. robust bud-
get allocation (Staib and Jegelka 2017]. experimental design [Chen et al. [018 MAP inference for
DPPs Gillenwater et al. 2012 Hassani et al., 2020b]. energy allocation [Wilder (2018)) classes of
zero-sum games [Wilder 2018c| online welfare maximization and online task assignment (Sadeghi
et al. 2020 as well as many other settings of interest.
The research on maximizing continuous DR-submodular functions in the last few years has established strong theoretical results in different optimization settings including unconstrained [Nazadeh et al.
2018 Bian et al.] 2019), stochastic Mokhtari et al. 20l8a]. Hassani et al. [2017]. online [Chen
ct al. 2018 Zhang et al.
2019; Sadeghi and Fazel 2019 Raut et al. [022]] and parallel models of
computation [Chen et al.
2019a Mokhtari et al. 20188 Xie et al., 2019 Ene and Nguyen 2019].
different line of works study the maximization of discrete functions that can be represented as the sum of a non-negative monotone submodular function and a linear function. The ability to do so useful practice since the linear function can viewed as soft constraint, and it also has theoretical applications as is argued by the first work in this line [Sviridenko et al. 2017 (for example, the problem of maximization of monotone submodular function with bounded curvature can be reduced to the maximization of the sum of a monotone submodular function and linear function). In terms of the approximation guarantee, the algorithms suggested by Sviridenko et al. [2017] were optimal. However, more recent works improve over the time complexities of these algorithms [Feldman 2021 Harshaw et al. 2019, Ene et al., 2020], generalize them to weakly-subboouular functions Harshaw et al. [2199] and adapt them other computational models such as the data
stream and MapReduce models Kazemi et al. 2020b Ene et al. 2020
Setting and Notation
Let us now formally define the setting consider. Fix a subset X' of I?" of the form Il= X, where X; a closed range R. Intuitively, a function G: X + called (continuous) DR-submodular it exhibits diminishing returns in the sense that given vector x E X, the increase in G(x) obtained by increasing I; (for any E [n]) by = >> 0 is negatively correlated with the original values of the coordinates of x. This intuition is captured by the following definition. In this definition e, denotes the standard basis vector in the 2hh direction.
Definition 2.1. A function G: X + R is DR-submodular if every two vectors b E X, positive value k and coordinate i E [n] we have G(a ke;) - G(a)= 2 G(b + ke,) - G(b) whenever a S and a + ke; b ke; x
well known that when is continuously differentiable, then is DR-submodular if and only if (G(a) 2 VG(b) for every two vectors a. b X' that obey < b. Furthermore, for the sake of simplicity we assume in this work that X' = [0, 1)
We are interested in the problem of finding the point in some convex body P C [0, 1]" that maximizes given function F: [o, 1]" + IR that can be expressed the sum of DR-submodular function G: [0, 1J" + IR and a concave function C:: [0, 1]" + R. To get meaningful results for this problem, we need to make some assumptions. Here we describe three basic assumptions that we make throughout the paper. The quality of the results that we obtain improves if additional assumptions are made, as described in Section
Throoughout the paper, inequalities between vectors should be understood as holding coordinate-wise.
3

---

ALGORITHM
G
P
a
GREEDY
MONOTONE & NON-NEG.
MONOTONE & NON-NEG.
GENERAL
1 1/1/e
1 1/e
FRANK-W -WOFEE
MEASURED GREEDY
MONOTONE & NON-NEG.
NON-NEG.
DOWN-CLOSED
1-e
1/e
FRANK-WOLFE
MEASURED GREEDY
NON-NEG.
MONOTONE
DOWN-CLOSED
1/e
1 - 1/e
FRANK-WOLFE
& NON-NEG.
MEASURED GREEDY
MONOTONE
MONOTONE & NON-NEG.
DOWN-CLOSED
1 1/e
1 1/e
FRANK-WOL.R
& NON-NEG.
MEASURED GREEDY
NON-NEG.
NON-NEG.
DOWN-CLOSED
1/e
1/e
FRANK- FRANK-WOLFE
GRADIENT COMBINING
MONOTONE
GENERAL
GENERAL
1/2
FRANK-WOLAY
NON-NEG.
NON-OBLIVE CON-OBLIVIOUS
MONOTONE
NON-NEG.
GENERAL
1-1/
1-8
FRANK-WOLFF
& NON-NEG.
Table 1: Summary of algorithms, settings, and guarantees ("NON-NEG." " is shorthand for "non- negative"). All of the conditions are addition to the continuity and smoothness G and C, and the convexity of P. and 3 are the constants preceding G())) and C(o) respectively in the lower bound on the output of the algorithm.
Our first basic assumption that non-negative. This assumption necessary since we obtain multiplicative approximation guarantees with respect to G, and such guarantees do not make sense when is allowed to take negative values [ Our second basic assumption is that P is solvable, i.c. that one efficiently optimize linear functions subject to it. Intuitively, this assumption makes sense because one should not expect to be able to optimize a complex function such as F' subject to one cannot optimize linear functions subject to it (nevertheless, it is possible to adapt our algorithms to obtain some guarantee even when linear functions can only be approximately optimized subject to P). Our final basic assumption is that both functions G and C are L-smooth, which means that they are differentiable, and moreover, their graidents are L-Lipschitz, i.e., [ - fb())] S 2la-blle bll2
V a, b [0, 1|"
We conclude this section by introducing some additional notation that we need. We denote by arbitrary optimal solution for the problem described above, and define D maxxep |||||- Additionally, we denote by 0 and the all-zeros and all-ones vector, respectively; and given two vectors a, b R", denote by @ b their coordinate-wisc multiplication, and by (a, b) their standard Euclidean inner product.
3 Main Algorithms and Results
In this section we present our (first-order) algorithms for solving the problem described in Section 2 In general, these algorithms are all FrankWooft type algorithms, but they differ in the exact linear function which is maximized in each iteration (step of the while/for loop), and in the formula used to update the solution (step 2 of the while/for loop). As mentioned previously, we assume everywhere that G' is non-negative T-smooth DR-submodular function, C' is an L-smooth concave function, and P is a solvable convex body. Some of our algorithms require additional non-negativity and/or monotonicity assumptions the functions G and C, and occasionally they also require downward closed assumption on P. A summary of which settings each algorithm is applicable to can be found in Table T Each algorithm listed in the table outputs point E P which is guaranteed to obey F(x) a G(o) + 3 C(o)- - E for the constants a and 3 given in Table and some error term E.
Remark: An anonymous referee introduced us to a newly named class of functions called "up- concave" functions, which includes functions that are concave along non-negative directions (see Wilder 2018a It is known that both DR-submodular and concave functions are up-concave,
We note that almost all the literature on submodular maximization of both discrete and continuous functions assumes non-negativity for the same reason.

---

Algorithm 1:
Algorithm 2:
GREEDY FRANK- WOLFE (E)
MEASURED GREEDY FRANK- WOLFE (E)
Let + and y(0)
Let t 0 and y(t) 60
while < 1 do
while < 1 do
s(0) < arg maxxe COCessEeVVFii (VF(y()),
s(0) <- arg maxxer ((axxxe(([-y()) y(0) o
VF(y
y ((tte) y( -
y(t+s) y(( + (1- (1-y(0) Os(0)
t t+E
end while return (())
end while return y(1)
and therefore, the function F we optimize also belongs to this class. More interestingly, all our results can generalized (without any modification) to the case which the function G is an arbitrary non-negative up-concave function (rather than non-negative DR-submodular function).
3.1 Greedy Frank- Wolfe Algorithm
In this section we assume that both G and C monotone and non-negative functions (in addition to their other properties). Given this assumption, we analyze the guarantee of the greedy Frank-Wor -Wofee variant appearing as Algorithm | This algorithm is related the Continuous Greedy algorithm for discrete objective functions due to Cälinescu et al. [2011], and it gets quality control parameter E (0, We assume the algorithm that E is an integer. This assumption without loss of generality because, if violates the assumption, then it can be replaced with a value from the range (e/2, 8) that obeys it. Most of the proofs of this section are deferred to Appendix A.
One can observe that the output y-(1) of Algorithm | is within the convex body P because it is convex combination of the vectors s s(()) (((e), st..,,,s.,,, which are all vectors in P. Let us now analyze the value of the output of Algorithm [ The next lemma the first step towards this goal.
provides a lower bounds on the increase in the value of y(!) as a function of
Lemma 3.1. For every 0 S i <-_ F(yle(++1)) F(y(50) 2 [F(o) - [[y(st))]-ee+ - LDD
The corollary below follows by showing (via induction) that the inequality ((y(et)) 2 11- -1-1 e)'] F(o) - i- = LDD holds for every integer 0 S S E =-1, and then plugging in = -1 The inductive step proven using Lemma 3.1
Corollary 3.2.
(2) 2 (1- -(o)
We are now ready summarize the properties of Algorithm D in a theorem.
Theorem 3.3. Let S be the time takes to find point P maximizing given liner function, then Algorithm 7 rans in O( 10e-1pp (n + S)) time, makes ( /5) calls to the gradient oracle, and oulputs vector y such that Fly) 2 (1 1/e) F(o) OsT.DP)
Proof. The output guarantee of Theorem
3.3 follows directly from Corollary 3.2 The time and
oracle complexity follows by observing that the algorithm's is while loop makes iterations, and each iteration requires O(n + S) time, in addition to making single call to the gradient oracle. O
3.2 Measured Greedy Frank-Wolfe Algorithm
In this section we assume that P is down-closed body (in addition to being convex) and that G and C' are both non-negative. Given these assumptions, we analyze the guarantee of the variant of Frank- Wolfe appearing Algorithm 2 which is motivated by the Measured Continuous Greedy algorithm for discrete objective functions due to Feldmann et al. [201T]. We again have a quality control parameter (0, 1), and assume (without loss of generality) that -1 is integer.
The properties of Algorithm 2 are summarized Theorem 3.4 Since the proof of this theorem can be viewed generalization of the proof of Theorem 3.3
defer it to Appendix A.2.
5

---

Theorem 3.4. Let S be the time it takes to find point in P maximizing given function, then Algorithm 2 runs O(E vector y such that
(n+ (n S)) time, makes (11/E) calls the gradient oracle, and outputs
1- i is monotone Fly) 2 e
-G(0)+
e- i monotone
J. -C(())
otherwise
otherwise
3.3 Gradient Combining Frank-Wolfe Algorithm
Up to this point, the guarantees of the algorithms that we have seen had both a and 3 that are strictly smaller than 1. How- ever, since concave functions can be exactly maximized, it reasonable to expect also al- gorithms for which the coeffi- cient/ / associated with C(o) is equal to 1. In Sections B.3 and 3.4 we describe such algo- rithms.
Algorithm 3: GRADIENT COMBINING FRANK- WONFEE (s)
Let y (0) be a vector in maximizing C up to an error of 2 0.
for
1 to 8-3 do
8(() +- arg maxxep (VG(y(--1) + -VC(y((-11)
y() - (1- - g()
end for return the vector maximizing F among (y ..... ....,y(e y((
In this section, we assume that a monotone and non-negative function (in addition to its other properties). The algorithm we study in this section is Algorithm 3 and it again takes quality control parameter & E (0, 1) as input. This time, however, the algorithm assumes that =-3 is an integer. As usual, if that is not the case, then e can be replaced with value from the range [c/2, s| that has this property. Most of the proofs of this section are deferred to Appendix A.3.
Firstly, note that for every integer 0 S Si y(( E P: and therefore, the output of Algorithm
also belongs to P. For i = 0 this holds by the initialization of ("),, For larger values of i, this follows by induction because ( is a convex combination of yf and the point s(() (y(1-)) belongs to P by the induction hypothesis, and g belongs to P by definition).
Our next objective is to lower bound the value of the output point of Algorithm 3 For that purpose, it will be useful to define F(x) G(xx + (x) and H()) = Flo) - ((y To get bound on the value of the output of Algorithm 3 we first show that (1) is small for at least some i value. We do that using the next lemma, which shows that Hi) decreases as function of i as longs as it is not already small compared to G(y*). Then, Corollary 3.6 guarantees the existence of a good iteration i".
Lemma 3.5. For every integer Si H - 1) H(O H() e² -G(() 2G( 262. [C(o) - C(y((-())) LD2 LD2 =² [H(i - 1) G(y(i-)) LD?
Corollary 3.6. There is an integer 0 S 1* < 33 obeying H < (c0))
We are now ready summarize the properties of Algorithm in theorem.
Theorem 3.7. Let S1 be the time it takes to find a point in P maximizing a given liner function and S2 be the time it takes to find point in P maximizing C(-) up to error of n, then Algorithm 2 runs in Ols (n + S1) + S2) time, makes O(1/=²) gradient oracle calls, and outputs a vector such that
Fly) 2 (1 (1) -(() C(o) e -0n+
Proof. We begin the proof by analyzing the time and oracle complexities of Algorithm 3 Every iteration of the loop Algorithm 3 takes O(n + Si) time. As there are - such iterations, the entire algorithm runs in (n + S1]+ + 52) time. Also note that each iteration of the loop requires 2 calls to the gradient oracles (a single call to the oracle corresponding to G. and a single call to the oracle corresponding C), so the overall oracle complexity of the algorithm is (11/²3).

---

Consider now iteration i", whose existence is guaranteed by Corollary 3.6 Then,
H(i*) - G(y(*)) - + 2 - 6LD*)
(G(o) + +C(o)))(()) -G(y)) +20g)))))))+)0))))) G(y + [G(o) 2n 6LD*)
F(yl)) 2 [11 -) G(o) -())
- 1-
The theorem now follows since the output of Algorithm 2 is at least good as y
3.4 Non-oblivious Frank- Wolfe Algorithm
As mentioned in the beginning of Section 3.3 our objective present an-
in this section other algorithm that has 3 1 (i.e. it maximizes C' "ex- actly" in some sense). In Sec- tion 3.3 we presented Algo- rithm which achieves this goal with a = 1/2. The algo- rithm we present in the current section achieves the same goal with improved value of 1 1/e for However, the improvement is obtained at the cost of requiring the function C' to be non-negative (which was not required in Section 3.3). Additionally, like in the previous section, we assume here that G is monotone and non-negative function (in addition to its other properties).
Algorithm 4: NON-OBLIVIOUS FRANK- WOLFE (E)
Let y be an arbitrary vector in P, and let B(e) t e(1 Inz).
for i = 0 to [e 1 B(E)/E²1 do
s()) arg maxxer VG((()) VC(y()),
( t- (1 - 8) (() + s()
end for
return the vector maximizing F ammmg (y(0) ..... (Te Mich
The algorithm we study in this section is non-oblivious variant of the Frank Wolfe algorithm, appearing as Algorithm which takes quality control parameter & E (0, 1/4 as input. As usual, we assume without loss of generality that e-1 is an integer. Algorithm 4 also employs the non-ne nen-tvgae
auxiliary function: G(x) = E G..GG()jx) This function is inspired by the non-oblivious
objective function used by Filmus and Ward (2012).
Note that any call to the gradient oracle of G can be simulated using s calls to the gradient oracle of G. The properties of Algorithm 4 are stated Theorem 3.8 Since the proof of this theorem is quite technical and reuses some of ideas from the proof of Theorem 3.7 (as well as new ideas), we defer it to Appendix A.4.
Theorem 3.8. Let S be the time takes find a point in P maximizing given linear function, then Algorithm 4 runs in (n/= + 5) 21) time, makes ( lne= gradient oracle calls, and outputs vector y such that:
Fly) 2 (1 1/e- 4s Ins G(o) + (1 4- Ine C(o) 4
4 Experiments
In this section we describe some experiments pertaining to our algorithms for maximizing DR- submodular concave functions. All experiments are done on 2015 Apple MacBook Pro with quad-core 2.2 GHz i7 processor and 16 GB of RAM.
4.1 Interpolating Between Constrasting Objectives
We use algorithms for maximizing the of a DR-submodular function and concave function to provide a way to achieve a trade-off between different objectives. For example, given ground set X and DPP supported on the power set 2 the maximum posteriori (MAP) of the DPP corresponds to picking the most likely (diverse) set of elements according to the DPP. On the other hand, concave functions be used encourage points being closer together and clustered.
Finding the MAP of a DPP an NP-hard problem. However, continuous approaches employing the multilinear extension Calinescuu et al. 2011 or the softmax extension [Bian et al. 2017a Gillenwater et al., 2012) provide strong approximation guarantees for The softmax approach usually preferred it has closed form solution which is easier to work with. Now, suppose
7

---

Figure Outputs of the experiment described in Section 4.1 LEFT PLOT:
(jutt the
submodular objective). RIGIIT PLOT: À = 0 (just the concave objective). MIDDLE PLOT: 0 < X < 1 (combination of both objectives). A darker square corresponds a larger entry in the final output of Algorithm for the corresponding element.
that [X] = n, and let L be the n x n kernel of the DPP and I be the n x n identity matrix, then ((x) log det (dtidix(( I) + I] is the softmax extension for E [0, 1]" Here, diag(x)
corresponds to a diagonal matrix with the entries of x along its diagonal.
Observe now that, given vector E [0, 1]". Z; can be thought of as the likelihood of picking element Moreover, Liy captures the similarity between elements i and j. Hence, our choice for a concave function which promotes similarity among elements C(x) Ei, L1 - (xr - ))) The rationale behind this as follows. For particular pair of elements and j. Lig large, that means that i and j are similar, so we would want C to be larger when Lij is high, provided that we are indeed picking both i and j (i.e., provided that (r; - 23)² is small). One can verify that the function C(x) is indeed concave its Hessian is negative semidefinite.
In our first experiment we fix the ground set to be the set of 20 x 20 = 400 points evenly spaced in [0, 1] x [0.
R We also choose L to be the Gaussian kernel L,, exp(-d(i, j)² 220²). where d(i,j) is the Euclidean distance between points i and j. and σ = 0.04. Given the functions G' and C defined above, we optimize in this experiment a combined objective formally specified by F = XG + (1 A)C, where À E [0, 1] is a control parameter that can be used to balance the contrasting objectives represented by G and C. For example, setting X 1 produces the (spread out) pure DPP MAP solution, setting À = 0 produces the (clustered) pure concave solution and X = 0.5 produces solution that takes both constraints into consideration to some extent. important to note, however, that the effect of changing À on the importance that each type of constraint gets is not necessarily mmeer-allhouse
it becomes linear when the ranges of G and C happen be similar.
In Figure 2 we can see how changing À changes the solution. The plots in the figure show the final on just the submodular objective G (left plot), just the concave
output of Algorithm 3 when objective C' (right plot), and a combination of both (middle plot). The algorithm is run with the same cardinality constraint of 25 in all plots, which corresponds iteratation must be at most 25. It is important to note that we represent the exact (continuous) output of the algorithm here. To get discrete solution, rounding method should be applied. Also, all of the runs of the algorithm begin from the same fixed starting point inside the cardinality constrained polytope. The step sizes used by the different runs are all constant, and were chosen empirically.
imposing that the & norm of each
On Jeopardy Dataset. As we can see, the above setup lends itself nicely to interpolating between contrasting objectives, and this can be used in real world applications. For example, consider set of news articles or sentences. The DPP MAP solution would correspond to picking a very diverse set of articles, whereas using just the concave objective would pick a set of similar articles or sentences. The important step is to appropriately codify the similarity between elements of the ground set (i.c. the news articles or the sentences) in the kernel L. To illustrate this, we consider a set of 324 questions from the game show Jeopardy (taken from https://www.j-art http://wwwcccci..oooo com//. use a pretrained BERT model to map these questions (BERT) embeddings, and then use sesiie-similarity to construct the matrix L. This matrix can be seen to be positive semidefinite. Though we do not have a (small) set of topics or meta-features for these questions, when this experiment is run, we get that the concave solution picks questions focused on a few topics such as history and fantasy (like "Saar designer John Galliano was born Juan Carlos Galliano in this British possession at the tip of Spuin", "In 1801 this onetime VP compiled 'A Manual of Parliamentary Practice' still used in the U.S. Senate".
8

---

and "In Euripides' play about this famed beauty, it's her double who goes to Troy"), whereas the DPP solution is much more spread out (including questions such as "These parts of a peach tree are glossy green, pointed and lance shaped" and "5xx x0 15").
4.2 Other Submodular Concave Objectives
In this section we compare algorithms with two baselines: the Frank- algorithm [Frank and Wolfe [I956] and the projected gradient ascent algorithm. In all the experiments done in this section, the objective function is again F XG + (1 AJC, where G and C' are a Susuumudula function and a concave function, respectively. For simplicity, we set À = 1/2 throughout the section.
4.2.1 Quadratic Programming
The non-convex quadratic programming (NQP) problem is fundamental NP-hard problem studied within the realm of DR- DRsuumoouular quadratic programming in works such as Bian et al. [2017a] and on its own [Xia et al., 2018 Burer and Letchford 2009, [hhrrli and Tuncbilek 1995] Here, we use our submodular + concave framework to study the NQP problem for a class Hessian matrices which can be decomposed the sum of Hessian corresponding to submodular objective and a Hessian corresponding to a concave objective. We define G(x) = 2/2 x Hx + x + c. By choosing the matrix H and vector h appropriately, this objective can be made be monotone or non mon-monotone DR-submodular. We also define the down-closed constraint set to be P {x e b E RT)). Following Bian et al. 2017aa). we choose the matrix H E Raxn to be a randomly generated symmetric matrix with entries uniformly distributed in 0J. and the matrix A to be a random matrix with entries uniformly distributed in [0.01, 1.01] (the 0.01 addition here is used to ensure that the entries are all positive). The vector b is chosen as the all ones vector, and the vector u is tight upper bound on P whose 7th coordinate is defined as U, minje[m] b, AAt. We let h = -.2 H u which makes G non-monotone. Finally, although this does not affect the results of our experiments, we take to be large enough additive constant (in this case 10) to make G non-negative.
RT Ax S b, x < u, A E RT Rmxx"
It is known that when the Hessian of quadratic program is negative semidefinite, the resulting objective is concave. Accordingly, we let C(x) 20 Dx, where D is a negative semidefinite matrix defined by the negation of the product of random matrix with entries in [0, 1] with its transpose. As one can observe, the generality of DR-submodular + concave objectives allows us to consider quadratic programming with very different Hessians. We hope that our ability to do this will motivate future work about quadratic programming for broader class of Hessian matrices.
In the current experiment, we let E {8, 12, 16) and m E {0.5n, n, 1.5n]. and run each algorithm for 50 iterations. Note that having fixed the number of iterations, the maximum step size for Algorithms/ 1 and is upper bounded by (number of iterations)
1/50 to guarantee that these algorithms remain within the polytope. To ensure consistency, we set the step sizes for the other algorithms to be !/5a as well, except for Algorithm 4 for which we set to the value of g given by solving e (E))/E2 50. This ensures that the gradient computation in Algorithm i is not too time consuming. We start Algorithms [ an from the starting point their pseudocodes specify, and the other algorithms from the same arbitrary point. We show the results for n 8 and m = 4,8 8, 12 and 3c respectively (each plot shows the average of 50 runs of the experiment). Due to space constraints, the results for n = 12 and 16 are postponed to Appendix B. We also note that since Algorithms 3 and 4 output the best among the results of all their iterations, we just plot the final output of these algorithms instead of the entire trajectory.
in Figures 3a 3b
4.2.2 D-optimal Experimental Design
Following Chen et al. 2018), the sussuuuod objective function for the D-optimal experimental
design problem is G
( log det (Ei_ Y, Y:). Here, Y, is an n dimensional row-vector in
which each entry is drawn independently from the standard Gaussian distribution. The choice of concave function is C(x) = TO Σi= log(x;). this experiment there is no combinatorial constraint. Instead, we are interested in maximization over box constraint, i.e., over [1, (note that the box shifted compared to the standard [0, 1)me to ensure that G defined everywhere as it undefined
at 0). The final outputs of all the algorithms for 8, 12, 16 appear in Figure 3d Like in

---

154
19.3
Decelty Jkye
Grondh (lkge
Haauurd Gready rigerhhnn
Hessured Greaty iageritm
154
celiciuu PA LAgeri Oorpec
Pripetes Draind Jour
Progin Caudkedd
33
30 (a) 8,
50
10
20
30
50
(b)
R. 22
13.25
175
23.29
Dicclty PaY Jkye Biee frod ent coenting (Agg- Clold FSI (2/iaaaai))))
Couctly Degadtie
cowtent Canrii He prpprttinn Siiprtiive
Prpperee Dradie Soree Dosu
Peo Gradiee Ricert pooselred
Mumber rhhoriee
Demarionn
(c)
12
(d) Final outputs for the D-optimal design problem.
3b and Be correspond to the quadratic programming experiment from Section 1.2.1 Plot 3d pertains to the D-optimal experimental design problem from Section 4.2.2
Figure 3: Plots 3a
Section 4.2.1
each algorithm was run for 50 iterations, and each plot is the average of 50 runs. The step sizes and starting points used by the algorithms are set exactly like in Section 4.2.1
Takeaways. Based on our experiments, we can observe that Algorithms and consistently outperform the other algorithms. We can also see (especially in the D-optimal experimental design problem where they almost superimpose) that the difference between Algorithm and the standard Frank- Wolfe algorithm are minimal, but we believe that the difference between the two algorithms can be made more pronounced by considering settings in which the gradient of C' dominates the gradient of G. Finally, one can note that the output value in plots 3a 3b and 3c tends to decrease when the number of constraints increases, which matches our intuitive expectation.
5 Conclusion
In this paper, we have considered the maximization of a class of objective functions that strictly larger than both DR-submodular functions and concave functions. The ability optimize this class of functions using first-order information is interesting from both theoretical and practical points of view. Our results provide step towards the goal of efficiently analyzing structured non-convex functions a goal that is becoming increasingly relevant.
Our various results enable to obtain approximation guarantees for many use cases. One use case which is somewhat less well-covered by our results the case of maximizing the difference between non-negative monotone DR- Sussuuuad function G and non-negative monotone convex function C. Currently, only Algorithm|33 appplis applies to this case, yielding an approximation guarantee of a 1/2 and 8 1 (in the notation of Table However, as the functions in this case have many properties on top of what is required by Algorithm it is reasonable to believe that one can improve over this approximation guarantee.
Funding Transparency Statement
Funding in direct support of this work: The work of Moran Feldman was supported in part by Israel Science Foundation (ISF) grant no. 459/20. Amin Karbasi acknowledges funding in direct support of this work from NSF (IIS- 1845032) and ONR (N00014-19-112400))
Additional revenues related to this work:
None
10

---

References
Ayya Alieva, Aiden Aceves, Jialin Song, Stephen Mayo, Yisong Yue, and Yuxin Chen. Learning to make decisions via submodular regularization. In International Conference Learning Representations, 2021.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems, 2019.
Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes. In 29th Annual Conference Learning Theory, 2016.
Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra. Computing nonnegative matrix factorization provably. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012.
An Bian, Kfir Y. Levy, Andreas Krause, and Joachim M. Buhmann. Continuous dr-submodular maximization: Structure and algorithms. In Proceedings of the 31st International Conference on Neural Information Processing Systems, 7a.
An Bian, Joachim M. Buhmann, and Andreas Krause. Optimal dr-submodular maximization and applications to provable mean field inference. In Proceedings of the 36th International Conference on Machine Learning. 2019.
Andrew An Bian, Baharan Mirzasoleiman, Joachim M. Buhmann, and Andreas Krause, Guaranteed non-convex optimization: Submodular maximization over continuous domains. In AISTATS, 2017b.
Guy Bresler, Frederic Koehler, Ankur Moitra, and Elchanan Mossel. Learning restricted boltzmann machines via influence maximization. Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, 2019.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 2015.
Samuel Burer and Adam N. Letchford. On nonconvex quadratic programming with box constraints. SIAM Journal on Optimization, 2009.
Gruia Cälinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák, Maximizing a monotone submodular function subject to matroid constraint. SIAM J. Comput., 2011.
Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. In Proceedings of the Twenty- First International Conference on Artificial Intelligence and Statistics, 2018.
Lin Chen, Moran Feldman, and Amin Karbasi. Unconstrained submodular maximization with constant adaptive complexity. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 2019a.
Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval. Mathematical Programming, 2019b.
Michal Derezinski, Feynman Liang, and Michael Mahoney. Bayesian experimental design using regularized determinantal point processes. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statisties, 2020.
Josip Djolonga and Andreas Krause. From map to marginals: Variational inference in bayesian submodular models. In Advances in Neural Information Processing Systems, 2014.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes pwer-parameterized neural networks. In International Conference on Learning Representations, 2019.
11

---

Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu. Log-concave sampling: Metropolis- hastings algorithms are fast. Journal of Machine Learning Research, 2019.
Ethan R. Elenberg, Rajiv Khanna, Alexandros G. Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. In Proceedings of the 30th Conference on Neural Information Processing Systems, 2016.
Ethan R. Elenberg, Alexandros G. Dimakis, Moran Feldman, and Amin Karbasi. Streaming weak submodularity: Interpreting neural networks on the fly. In Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
Alina Ene and Huy L. Nguyen. Parallel algorithm for non-monotone dr-submodular maximization.
In Proceedings of the 37th International Conference on Machine Learning, 2019,
Alina Ene, Sofia Maria Nikolakaki, and Evimaria Terzi. Team formation: Striking a balance between coverage and cost. CoRR, 2020.
Moran Feldman. Guess free maximization submodular and linear sums, Algorithmica, 2021.
Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In 2011 IEEE 52nd Annual Symposium on Foundations Computer Science, 2011.
Yuval Filmus and Justin Ward. A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In 2012 IEEE 53rd Annual Symposiun on Foundations of Computer Science, 2012.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 1956.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points - online stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference Learning Theory, 2015.
J. Gillenwater, A. Kulesza, and B. Taskar, Near-Optimal MAP Inference for Determinantal Point Processes. Proc. Neural Information Processing Systems (NIPS), 2012.
Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In ICML, 2019.
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maxi- mization. In Proceedings of the 31 International Conference on Neural Information Processing Systems, 2017.
Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional gradi- ent++: (non)convex minimization and continuous submodular maximization. SIAM Journal on Optimization, 2020a.
Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional gradient++, 2020b.
Elad Hazan, Kfir Y. Levy, and Shai Shalev-Shwarte On graduated optimization for stochastic non-convex problems. In Proceedings of The 33rd International Conference on Machine Learning. 2016.
Xiaofei He. Laplacian regularized d-optimal design for active learning and its application to image retrieval. IEEE Transactions on Image Processing, 2010.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Regularized submodular maximization at scale. CoRR, 2020a.
12

---

Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Regularized submodular maximization scale. CoRR, 2020b.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, Association for Computing Machinery, 2003.
Andreas Krause and Volkan Cevher. Submodular dictionary selection for sparse representation. In Proceedings of the 27th International Conference on International Conference on Machine Learning, 2010.
Alex Kulesza.
Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 2012.
Tor Lattimore and Csaba Szepesvari. Bandit algorithms. Cambridge University Press, 2020.
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative elements in massive data. In Advances in Neural Information Processing Systems, 2013.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Conditional gradient method for stochastic submodular maximization: Closing the gap. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, 2018a.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Decentralized submodular maximization: Bridging discrete and continuous settings. In Proceedings of the 35th International Conference Machine Learning, 2018b.
K. G. Murty and S. N. Kabadi. Some np-complete problems in quadratic and nonlinear programming. Mathematical Programming, 1987.
Yurii Nesterov. Lectures on Convex Optimization. Springer Publishing Company, Incorporated, 2018.
Pranceth Netrapalli, U N Niranjan, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. Non-convex robust pca. In Advances in Neural Information Processing Systems, 2014.
Rad Niazadeh, Tim Roughgarden, and Joshua R. Wang. Optimal algorithms for continuous monotone submodular and dr-submodullar maximization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018
Prasanna Sanjay Raut, Omid Sadeghi, and Maryam Fazel. Online dr-submodular maximization with stochastic cumulative constraints, 2021.
Patrick Rebeschini and Amin Karbasi. Fast mixing for discrete point processes. In Proceedings of The 28th Conference Learning Theory, 2015.
Joshua Robinson, Suvrit Sra, and Stefanie Jegelka. Flexible modeling of diversity with strongly log-concave distributions. In Advances in Neural Information Processing Systems, 2019.
Omid Sadeghi and Maryam Fazel. Online continuous DR-submodular maximization with long-term budget constraints. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 2019.
Omid Sadeghi, Prasanna Raut, and Maryam Fazel. A single recipe for online submodular maximiza- tion with adversarial stochastic constraints. In Advances in Neural Information Processing Systems, 2020.
Hanif D. Sherali and Cihan H. Tuncbilek. A reformulatooncconveffeeet approach for solving nonconvex quadratic programming problems. Journal of Global Optimization, 1995.
Adish Singla, Ilija Bogunovic, Gábor Bartók, Amin Karbasi, and Andreas Krause. Near-optimally teaching the crowd to classify. Proceedings of the 31 International Conference on International Conference Machine Learning, 2014.
13

---

Matthew Staib and Stefanie Jegelka. Robust budget allocation via continuous submodular functions. In Proceedings of the 34th International Conference on Machine Learning. 2017.
Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary?, 2016.
Ruoyu Sun and Zui-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, 2016.
Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res., 2017.
Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, and Amin Karbasi.
Submodularity in action: From machine learning to signal processing applications. IEEE Signal Processing Magazine, 2020.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, 2015.
Bryan Wilder. Risk-sensitive submodular optimization. In AAAI, pages 6451 2018a. URL https: //www//wwwww.. aaai wwg/ ind///ndxxxxp// http:///ss/aaee..ppppaAAAAAAAAAA
Bryan Wilder. Risk-sensitive submodular optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 2018b.
Bryan Wilder. Equilibrium computation and robust optimization in zero sum games with submodular structure. Proceedings of the AAAI Conference on Artificial Intelligence, 2018c.
Wei Xia, Juan Vera, and Luis F. Zuluaga. Globally solving non-convex quadratic programs via linear integer programming techniques, 2018.
Jiahao Xie, Chao Zhang, Zebang Shen, Chao Mi, and Hui Qian. Decentralized gradient tracking for continuous dr-submodular maximization. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, 2019.
Mingrui Zhang, Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization: From full-information bandit feedback. In Advances in Neural Information Processing Systems, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Though we don't have an explicit
limitations section, do diseuss the limitations throughout the text, for example in
the "Takeaways' paragraph just preceding Section 5
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Ys]] We mention the settings and assumptions of all theoretical claims in Section 2 and also in each section pertaining to theorem/algorithmt
(b) Did you include complete proofs of all theoretical results? [Yes] All the results have complete proofs. Some are in the main text and some are part of the appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL.)? [Yes] It is in the supplemental material.
14

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We specify all parameter details regarding the experiments in Section
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We mention the resources used to run the experiments in Section 4
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Whenever we are following the data generation recipe from prior works, we cite the source. This can be seen in Section 4
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "orqzmcBi0W_", "reviewer": "Reviewer_aSDv", "summary": "Authors consider the problem maximizing a function that can be written as the addition of submodular and concave functions. They provide multiple Frank-Wolfe-based algorithms for this problem with different approximation factors. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1)Author motivates the subject from a theoretical and practical point of view. But all the experiments are on synthetic data. It would be great if they can add simulation for an application on a real dataset.\n\n2)In the introduction, the author reviewed the previous works carefully.\n\n3)the author successfully addressed the issue and recommended the algorithms. They proposed this new problem. Their idea to change the frank Wolfe algorithm to come up with a better approximation factor is interesting. Although, if they can characterize what type of functions can be written as sub+concave or, for example, come up with the condition on second-order derivative, which is equivalent to writing a function as sub+concave that would be very interesting.\n\n4)The authors successfully provide simulation results for their algorithm.\n\n5)The paper is well-organized and well-written.\n\n6)The proof is mathematically correct.\n\n7)the code is included. \n\nOverall, the idea is interesting, and the author's way of solving the problem is interesting too.\n\n\n----------- Post Rebuttal------------- \n\nI have read all the comments, and I don't change my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations and potential negative social impact of their work.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "YKbyNcTcGD8", "reviewer": "Reviewer_rEMg", "summary": "This paper studies maximization of submodular + concave functions over solvable polytopes. This problem forms a new class of non-convex optimization problems, for which no theoretical results have been obtained. Depending on the conditions of the problem, the authors develop several algorithms and prove that they return approximately optimal solutions. Experiments demonstrate the practical utility of the proposed algorithms. \n\n--- After rebuttal ---\n\nI appreciate the authors' kind response. My technical concerns have been resolved. However, I still think the experimental comparison in running time is important to clearly demonstrate the effectiveness of Algorithm 4 since $\\nabla \\bar{G}$ usually requires more computation costs than $\\nabla \\bar{G}$, as mentioned in the response. Despite the lack of experiments, the theoretical contributions are great and I think the paper is above the acceptance threshold. Therefore, I keep my score of 6. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses a new class of optimization problems, which are motivated by some machine learning applications (e.g., DPP + clustered). The theoretical guarantees are reasonable and strong. Overall, I think this is a good paper. There are, however, some concerns and comments as listed below: \n\n1. Since each algorithm and its analysis are explained only briefly, it is hard to see how novel and significant each of them is. Algorithms 1 and 2 seem to be similar to continuous greedy and measured continuous greedy. Regarding the analyses of them, are there some special techniques required to deal with the additional concave function? Regarding Algorithms 3 and 4, are there existing studies that provide their bases, or are they newly developed for submodular + concave maximization?\n\n2. I would like the authors to show how to guarantee outputs of Algorithm 2 are included in $P$. \n\n3. I think the class of quadratic functions considered in Section 4.2.1 is interesting. I would appreciate it if the authors could present relevant previous studies on non-convex quadratic programming, if any, and explain advantages of the submodular + concave framework in the quadratic-programming context. \n\n4. In Figure 3, algorithms are compared based on the number of iterations. What if those are compared based on running times?\n\nMinor comments: \n\n- It is better to define $\\bar 0$ and $\\bar 1$ in Section 2. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are described. The paper seems to have no negative societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HXcc1dPxrGB", "reviewer": "Reviewer_8aFc", "summary": "This paper studies the maximization of a nonconvex function in the form of $F = G + C$ on a convex set $P \\\\subseteq [0,1]^n$, where $G$ is DR-submodular and $C$ is concave. For various settings (monotonicity/nonnegativity of $G$ or $C$, $P$ is a down-closed/general convex set, the gradient oracle is for only $F$/both $G$ and $C$, etc.), the authors developed the first approximation algorithms.\n\nThe algorithms exploit some ideas from submodular function maximization such as Frank-Wolfe, measured continuous greedy, etc. The algorithms have provable fine approximation guarantees, i.e., they achieve $\\\\alpha$- and $\\\\beta$-approximation for $G$ and $C$, respectively. These are stronger guarantees than the standard approximation results in submodular function maximization. Furthermore, the authors proved even tighter approximation ratios (i.e., $\\\\beta \\\\approx 1$) if the individual gradients of $G$ and $C$ are available.\n\nThe authors conducted the numerical experiments in (nonconvex) quadratic programming and D-optimal design. The proposed algorithms achieved better objective values compared to the baseline methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I enjoyed reading this paper. The class of nonconvex functions is reasonable and interesting because we can obtain constant-factor approximation guarantees. The paper is well-structured and easy to follow (if one is familiar with submodular/convex analysis). The authors provided effective algorithms for various settings. Each proposed algorithm nicely extends the known algorithm for submodular or concave maximization. The experiment with real-world data shows the efficacy of the proposed algorithms. In summary, the paper made significant theoretical contributions to nonconvex optimization using submodular maximization techniques, and the results are supported by real-world experiments. I would recommend accepting it.\n\n## Minor comment\nThe class of submodular+concave is contained in the class of up-concave functions (i.e., concave along nonnegative directions). Can we understand the results from the up-concavity of objective functions? I guess Greedy Frank-Wolfe also works for up-concave functions with the same approximation ($\\\\alpha=\\\\beta=1-1/e$), but not sure for the rest. It would be helpful if the authors have comments on the relation to up-concavity.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "0j66jZpXGHF", "reviewer": "Reviewer_mN3h", "summary": "This paper studies a class of optimization problems where the goal is to maximize the sum of a DR-submodular function and a concave function. Depending on whether the DR-submodular function is monotone, the concave function is monotone or non-negative, and the constraint set is down-closed, the authors have proposed 4 algorithms with various approximation ratios for the DR-submodular and concave parts of the objective function. Finally, this work provides a set of experiments to compare the performance of the proposed algorithms with baseline algorithms for DR-submodular maximization and concave maximization.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has many strengths that are listed below:\n- Theoretical analysis of the previously unstudied framework of DR-submodular + concave maximization and providing new algorithms (inspired by the algorithms for DR-submodular maximization) that obtain separate approximation ratios for the DR-submodular and the concave part.\n- Comprehensive set of numerical experiments to highlight the performance of the proposed algorithms and compare/contrast them with the previously known algorithms for either DR-submodular maximization or concave maximization.\n- Great review of all the previous works that are either studying a similar framework or using similar techniques and ideas.\n- Easy to follow proofs (in the appendix) for all the claims and results of the paper.\n\nOn the other hand, this work has some limitations as follows:\n- In my view, the framework of DR-submodular + concave maximization is not well motivated in the paper. While the DR-submodular + linear setting is well-motivated in prior works, I'm not sure how important this extension to concave functions is (aside from the additional theoretical challenges to obtain results). It seems like the chosen concave functions in all the provided experiments are also arbitrarily chosen and not inspired by a practical application.\n- One of the most important subclasses of this framework is \"monotone non-negative DR-submodular - monotone non-negative convex\" maximization which is a penalized formulation of constrained DR-submodular maximization with convex constraints. Out of the 4 proposed algorithms, the Gradient Combining Frank-Wolfe algorithm (with approximation ratios 1/2 and 1 for the DR-submodular and concave parts respectively) is the only one that could be used for this problem. Given the specific structure of the concave function in this example (negative and monotone decreasing), I think it is possible to obtain a better approximation ratio for the DR-submodular part.\n- Most of the ideas for designing the proposed algorithms are heavily inspired by prior works on submodular maximization and although the theoretical analysis for the DR-submodular + concave is not exactly similar to prior results, it could be considered a straightforward extension of previous proofs (particularly for the first two proposed algorithms). \n**********************************\nPost-Rebuttal Update: Thanks to the authors for their careful responses to the raised questions. I totally agree that \"the addition of a concave function can be seen as the usage of a concave regularizer for the maximization of DR-submodular functions\" and this is basically the \"monotone non-negative DR-submodular - monotone non-negative convex\" case that I mentioned earlier. For instance, a knapsack or budget constraint $c^Tx\\leq 1$ could be enforced in the penalized form as $C(x)=-P(c^Tx)$ where $P$ is a monotone and convex function (e.g., $P(z)=exp(z)$). I think a separate discussion of this framework and obtaining an improved approximation ratio $\\alpha>\\frac{1}{2}$ for this special case would be interesting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, however, I don't think neither was really needed to be addressed. In terms of limitations, Table 1 clearly highlights the settings that each of the proposed algorithms could be applied to, and therefore, it is easy to infer the problems that are not addressed by this work. Also, this paper is mainly a theoretical work and does not raise any potential ethical concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5 hours to read the paper and also almost all of the proofs provided in the appendix."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this generally a good paper although not entirely without (minor) flaws. Please take the reviewers comments in consideration when preparing a revision. The answers provided by the authors were given due consideration. 
Decision: Accept (Poster)