# Continuous Non-monotone DR-submodular Maximization with Down-closed Convex
Constraint

Shengminjie Chen<EMAIL_ADDRESS>
School of Mathematical Sciences
University of Chinese Academy of Science
Beijing, 100049, P.R. China Donglei Du<EMAIL_ADDRESS>
Faculty of Management
University of New Brunswick
Fredericton, E3B 5A3, New Brunswick, Canada Wenguo Yang<EMAIL_ADDRESS>
School of Mathematical Sciences
University of Chinese Academy of Science
Beijing, 100049, P.R. China Dachuan Xu<EMAIL_ADDRESS>
Beijing Institute for Scientific and Engineering Computing
Beijing University of Technology
Beijing, 100124, P.R. China Suixiang Gao<EMAIL_ADDRESS>
School of Mathematical Sciences
University of Chinese Academy of Science
Beijing, 100049, P.R. China

###### Abstract

We investigate the continuous non-monotone DR-submodular maximization problem
subject to a down-closed convex solvable constraint. Our first contribution is
to construct an example to demonstrate that (first-order) stationary points
can have arbitrarily bad approximation ratios, and they are usually on the
boundary of the feasible domain. These findings are in contrast with the
monotone case where any stationary point yields a $1/2$-approximation (Hassani
et al. (2017)). Moreover, this example offers insights on how to design
improved algorithms by avoiding bad stationary points, such as the restricted
continuous local search algorithm (Chekuri et al. (2014)) and the aided
measured continuous greedy (Buchbinder and Feldman (2019)). However, the
analyses in the last two algorithms only work for the discrete domain because
both need to invoke the inequality that the multilinear extension of any
submodular set function is bounded from below by its Lovasz extension. Our
second contribution, therefore, is to remove this restriction and show that
both algorithms can be extended to the continuous domain while retaining the
same approximation ratios, and hence offering improved approximation ratios
over those in Bian et al. (2017a) for the same problem. At last, we also
include numerical experiments to demonstrate our algorithms on problems
arising from machine learning and artificial intelligence.

Keywords: Non-monotone DR-Submodular Maximization, Down-Closed Convex
Constraints, Approximation Algorithms

###### Contents

  1. 1 Introduction
  2. 2 Preliminary
  3. 3 Performance of Stationary Points
    1. 3.1 Negative Result for Stationary Points
    2. 3.2 Stationary Points in Reduced Feasible Domain
  4. 4 Aided Frank-Wolfe Variant
    1. 4.1 Lyapunov Function
    2. 4.2 Extending the algorithm in Buchbinder and Feldman (2019) via Lyapunov framework
    3. 4.3 Discretization via the Lyapunouv Function
    4. 4.4 Discussions
  5. 5 Numerical Experiments
    1. 5.1 Non-monotone Quadratic Programming
    2. 5.2 Regular Coverage Maximization
    3. 5.3 Determinantal Point Processes
    4. 5.4 Revenue/Profit Maximization
  6. 6 Conclusion

##  1 Introduction

Submodular optimization is an important topic in discrete optimization. A set
function $f:2^{V}\rightarrow\mathbb{R}_{+}$ is submodular if for every
$X,Y\subseteq V$, $f(X)+f(Y)\geq f(X\cap Y)+f(X\cup Y)$. Equivalently,
submodularity can be expressed by the diminishing return property in set
functions, that is, for every $X\subseteq Y\subseteq V$ and for every $u\in
V\setminus Y$, $f(\\{u\\}\cup X)-f(X)\geq f(\\{u\\}\cup Y)-f(Y)$.

Submodular functions arise naturally in numerous theoretical studies and
practical applications. Submodularity captures one important commonality of
many functions investigated in the literature, such as entropy functions, cut
functions, coverage functions, etc. Although it can be minimized in polynomial
time (Iwata et al. (2001)), maximizing submodular set functions is an NP-hard
problem and can be approximately solved in polynomial time. Seminal works were
proposed by Nemhauser et al. (1978) ($1-e^{-1}$, monotone, cardinality
constraints) and Fisher et al. (1978) ($(1+p)^{-1}$, monotone, intersection of
$p$ matroids). Following these work, further results also appeared, such as
Sviridenko (2004) ($1-e^{-1}$, monotone, knapsack constraints) and Buchbinder
et al. (2015) ($1/2$, non-monotone, unconstrained). The above approximation
algorithms have been adopted in some application fields such as influence
maximization (Kempe et al. (2003)), active learning (Golovin and Krause
(2012)), sensor placement (Krause et al. (2008)), determinantal point
processes (Gillenwater et al. (2012)).

The multilinear extension has played an important role in maximizing
submodular set functions. For example, the continuous greedy ($1-e^{-1}$,
monotone, down-closed) (Calinescu et al. (2011)), the restricted local search
($0.309$, non-monotone, down-closed) (Chekuri et al. (2014)), the repeated
local search ($1/4$, non-monotone, down-closed) (Chekuri et al. (2014)), the
measured continuous greedy ($1/e$, non-monotone, down-closed) (Feldman et al.
(2011)), the measured continuous greedy + the continuous double greedy
($0.372$, non-monotone, down-closed) (Ene and Nguyen (2016)), and the local
search + the measured continuous greedy ($0.385$, non-monotone, down-closed)
(Buchbinder and Feldman (2019)). These algorithms return a fractional
solution, which then can be rounded to an integral solution via such
techniques as pipage rounding (Calinescu et al. (2011)), swap rounding
(Chekuri et al. (2010)), and contention resolution scheme (Chekuri et al.
(2014)).

However, the aforementioned results concentrate on combinatorial optimization
problems; that is, feasible solutions belong to a discrete domain (binary or
integer vectors). Recently, submodular optimization in the continuous domain
(namely real vectors) becomes an attractive research field due to its vast
applications, in particular, machine learning and artificial intelligence.
Bach (2019) extended the submodular set function minimization problem to the
continuous domain. Marinacci and Montrucchio (2005) and Bian et al. (2017b)
characterize the difference between submodular functions and DR-submodular
functions in the continuous domain. Bian et al. (2017b) proposed a
$(1-e^{-1})$ approximation algorithm to maximize monotone continuous DR-
submodular functions under down-closed convex constraints. Hassani et al.
(2017) adopted the projected gradient ascent method to maximize monotone
continuous DR-submodular functions over general convex constraints with a
$1/2$ approximation guarantee. For non-monotone cases, Bian et al. (2017a)
adopted a two-phase Frank-Wolfe algorithm with a $1/4$ approximation ratio and
extended the measured continuous greedy from the multilinear extension of
submodular set functions to continuous DR-submodular functions subject to
down-closed convex constraints with a $1/e$ approximation ratio. Niazadeh et
al. (2020) proposed a $1/2$ approximation algorithm subject to box
constraints, which improves prior works in Bian et al. (2017b). If the
feasible domain is a general convex set containing the origin, Du et al.
(2022) proposed a Frank-Wolfe algorithm with a $1/4$ approximation ratio,
which is proved to be tight by Mualem and Feldman (2023). In addition, Du
(2022b) proposed a systematic framework, namely the Lyapunov approach, for
approximation algorithms design and analyses in the continuous domain and then
a systematic approach to discretize the algorithm. These results have been
applied to many application problems, such as revenue maximization (Bian et
al. (2020)), mean-field inference (Bian et al. (2019)), robust budget
allocation (Staib and Jegelka (2017)), determinantal point processes
(Gillenwater et al. (2012)), etc.

Although many advances have been made for DR-submodular maximization in both
discrete and continuous domains, there are still many important open problems
to be addressed.

  * •

Is the approximation ratio 1/2 in Hassani et al. (2017) still valid for the
stationary points in the non-monotone case? If not, what is the approximation
ratio in the non-monotone case?

  * •

The restricted continuous local search in Chekuri et al. (2014) and the aided
measured continuous greedy in Buchbinder and Feldman (2019) only work for the
discrete domain because their proofs strongly depend on the multilinear
extension and the Lovasz extension. Can we extend these algorithms to the
continuous domain without worsening the approximation ratios? if yes, can the
continuous domain offers us more flexibility in tuning the parameters used in
the algorithms, and hence potentially improving the approximation ratios?

The main focus of this work is to answer these questions on the following
problem.

$\max_{\mathbf{x}\in\mathcal{P}}F(\mathbf{x})$ (1)

where $\mathcal{P}\subseteq[0,1]^{n}$ is down-closed, convex, and solvable,
and $F(\mathbf{x}):[0,1]^{n}\mapsto\mathbb{R}_{+}$ is continuous, non-
negative, non-monotone, and DR-submodular.

Contribution. To answer the first question, we construct an example from the
multilinear extension of regular coverage set functions, which is non-
negative, non-monotone and DR-submodular. With this concrete example, we
propose a minimization problem to show that the ratio between the values of
the worst stationary point and the optimal solution approaches $0$, implying
that the stationary point can have arbitrarily bad approximation ratio for
non-monotone DR-submodular objective functions. Moreover, the worst stationary
point tends to be close to the boundary of the feasible domain. These fundings
may explain why the restricted continuous local search (Chekuri et al. (2014))
and the aided measured continuous greedy (Buchbinder and Feldman (2019))
produce better approximation ratios.

For the second question, we offer an essentially different analysis to show
the same upper bounds on the optimal value used in the $0.309$ (Chekuri et al.
(2014)) and the $0.385$ (Buchbinder and Feldman (2019)) approximation
algorithm for the continuous domain. The key new ingredient in our analysis is
to eliminate the multilinear and the Lovasz extensions and utilize solely the
DR-submodularity. The aforementioned second upper bound, together with a
tailor-made Lyapunov function, allow us to adopt the Lyapunov framework
introduced in Du (2022a) to present an $0.385$ approximation algorithm for the
continuous domain problem in (1), and hence extending the _aided measured
continuous greedy algorithm_ from the discrete domain to the continuous
domain. Moreover, we show that this $0.385$ approximation algorithm is
‘optimal’ in the sense that the algorithm is the optimal solution of certain
variation problem. This perspective offers insights on which directions to
devote (or avoid) our efforts to potentially design improved approximation
algorithms for the problem.

At last, we also include numerical experiments to demonstrate our algorithms
on problems arising from machine learning and artificial intelligence.

Table 1: Summary of DR-submodular maximization with down-closed convex constraints Reference |  Setting |  Guarantee
---|---|---
Repeated Local Search (Chekuri et al. (2014)) |  discrete, non-monotone DR-submodular |  $1/4-O(\varepsilon)$
Two Stage Frank-Wolfe (Bian et al. (2017a)) |  continuous, non-monotone DR-submodular |  $1/4-O(\varepsilon)$
Continuous Greedy (Calinescu et al. (2011)) |  discrete, monotone DR-submodular |  $1-e^{-1}-O(\varepsilon)$
Frank-Wolfe Variant (Bian et al. (2017b)) |  continuous, monotone DR-submodular |  $1-e^{-1}-O(\varepsilon)$
Measured Continuous Greedy (Feldman et al. (2011)) |  discrete, non-monotone DR-submodular |  $e^{-1}-O(\varepsilon)$
Frank-Wolfe Variant (Bian et al. (2017a)) |  continuous, non-monotone DR-submodular |  $e^{-1}-O(\varepsilon)$
Restricted Local Search (Chekuri et al. (2014)) |  discrete, non-monotone DR-submodular |  $0.309-O(\varepsilon)$
Aided Measured Continuous Greedy (Buchbinder and Feldman (2019)) |  discrete, non-monotone DR-submodular |  $0.385-O(\varepsilon)$
Stationary Points Hassani et al. (2017) |  monotone DR-submodular |  $1/2$
Stationary Points This work |  non-monotone DR-submodular |  $0$
Stationary Points (reduced feasible domain) This work |  non-monotone DR-submodular |  $0.309-O(\varepsilon)$
Aided Frank-Wolfe Variant This work |  continuous, non-monotone DR-submodular |  $0.385-O(\varepsilon)$

Applications. Continuous DR-submodular functions are ubiquitous in many
applications. Below are some examples that are common in discrete
optimization, machine learning, and data mining.

  * •

Multilinear extensions of submodular set functions (ME): The multilinear
extension of each submodular set function is a special DR-submodular function
that are infinitely differentiable. The multilinear extension of the set
function $f:2^{[n]}\rightarrow\mathbb{R}$ is defined as the function
$F(\mathbf{x}):[0,1]^{n}\mapsto\mathbb{R}$ with

$F(\mathbf{x})=\sum_{S\subseteq[n]}f(S)\prod_{i\in
S}x_{i}\prod_{j\in[n]\setminus S}(1-x_{j}),$

where $[n]:=\\{1,\ldots,n\\}$.

  * •

Non-convex/concave quadratic programming (NQP): The goal is to maximize
$F(\mathbf{x})=\frac{1}{2}\mathbf{x}^{T}\mathbf{H}\mathbf{x}+\mathbf{h}^{T}\mathbf{x}+c$
subject to linear constraints, where all entries of Hessian $H$ are non-
positive. This type of problems arises in many applications such as scheduling
(Skutella (2001)), and demand forecasting (Ito and Fujimaki (2016)), among
many others.

  * •

Softmax extension of determinantal point processes (DPPs): DPPs is an
important probabilistic model in machine learning, which can be adopted as
generative models in applications such as document summarization (Gillenwater
et al. (2012); Bian et al. (2017a)), news threading tasks (Kulesza and Taskar
(2012)), etc. The formal description is as follows:

$F(\mathbf{x})=\log\det\left[\text{diag}(\mathbf{x})(\mathbf{L}-\mathbf{I})+\mathbf{I}\right]$
(2)

where $\text{diag}(\mathbf{x})$ is the diagonal matrix with the vector
$\mathbf{x}\in[0,1]^{n}$ and $\mathbf{I}$ is the identity matrix.

  * •

Revenue/Profit maximization in online social networks (RM/PM): This problem
comes from the “word-of-mouth” effects in online social networks. Sellers
provide a subset of users in online social networks with some free samples,
such as discounts, free products, etc, to maximize the total revenue/profit
when other users buy their product. In Bian et al. (2017b); Tang et al.
(2018), the objective function has two parts, the revenue gain and the revenue
loss/cost. In this work, we adopt the form in Bian et al. (2017b), where
$x_{t}$ represents the free sample of user $t$, $R_{s}(\mathbf{x})$ is the
non-negative, non-decreasing, DR-submodular revenue gain,
$\bar{R}_{t}(\mathbf{x})$ is the non-positive, non-increasing DR-submodular
revenue loss, and $\phi(x_{t})$ is the modular revenue gain from user $t$ who
received the free sample.

$F(\mathbf{x})=\alpha\sum_{s:x_{s}=0}R_{s}(\mathbf{x})+\beta\sum_{t:x_{t}\neq
0}\phi(x_{t})+\gamma\sum_{t:x_{t}\neq 0}\bar{R}_{t}(\mathbf{x})$ (3)

Organization. The rest of this work is organized as follows. First, we present
some basic definitions and lemmas in Section 2. In Section 3, we illustrate
the negative result of stationary points for non-monotone scenarios by an
example and prove the $0.309$ approximation guarantee of stationary points in
the reduced feasible domain. In Section 4, we propose unified and novel
analyses of the upper bound on the optimal value for the continuous domain.
Then we use a tailor-make Lyapunov function to our problem to present a
$0.385$ approximation algorithm, which is shown to be the optimal solution of
a variation problem. Numerical experiments are presented in Section 5. We
provide concluding remarks in Section 6.

##  2 Preliminary

We first introduce some relevant definitions and lemmas. The first concept is
the submodular function on the real lattice $\mathbb{R}^{n}$, which is a
special case of the submodular function on arbitrary lattice (see e.g., Topkis
(1998)).

###### Definition 1

A function $F(\mathbf{x}):\mathbb{R}^{n}\mapsto\mathbb{R}$ is submodular if

$F(\mathbf{x})+F(\mathbf{y})\geq
F(\mathbf{x}\vee\mathbf{y})+F(\mathbf{x}\wedge\mathbf{y}),\forall\mathbf{x},\mathbf{y}\in\mathbb{R}^{n},$
(4)

where $\vee$ and $\wedge$ are the coordinate-wise maximum and minimum:
${x}_{i}\vee{y}_{i}=\max\\{x_{i},y_{i}\\}$ and
${x}_{i}\wedge{y}_{i}=\min\\{x_{i},y_{i}\\}$, $\forall i\in[n]$.

Note that a twice-differentiable function $F(\mathbf{x})$ is submodular iff

$\cfrac{\partial F(\mathbf{x})}{\partial x_{i}\partial x_{j}}\leq 0,\text{ for
}\forall\mathbf{x}\in\mathcal{X},\forall i\neq j.$ (5)

The above definition implies that submodular functions are generally non-
convex and non-concave. In addition, the above definition has no restriction
on the diagonal elements of the Hessian matrix, i.e.,
$\frac{\partial^{2}F(\mathbf{x})}{\partial x^{2}_{i}}\in\mathbb{R}$.
Naturally, if $\frac{\partial^{2}F(\mathbf{x})}{\partial x^{2}_{i}}$ is
further required to be non-positive, then it implies a stronger submodularity,
namely DR-submodularity, which is coined in Bian et al. (2017b). However, the
same concept (under a different name) was already investigated systematically
in Marinacci and Montrucchio (2005) in more general settings.

######  Definition 2 (Marinacci and Montrucchio (2005); Bian et al. (2017b))

A function $F(\mathbf{x})$ is defined on subsets of
$\mathbb{R}^{n}:\mathcal{X}=\prod_{i=1}^{n}\mathcal{X}_{i}$, where each
$\mathcal{X}_{i}$ is a compact subset of $\mathbb{R}$. If
$F(\mathbf{x}):\mathcal{X}\rightarrow\mathbb{R}$ is DR-submodular, for
$\forall\mathbf{x}\leq\mathbf{y}\in\mathcal{X}$, $\forall i\in[n]$, $\forall
k\in\mathbb{R}_{+}$ such that $k\mathbf{e}_{i}+\mathbf{x}$ and
$k\mathbf{e}_{i}+\mathbf{y}$ are still in $\mathcal{X}$, the following
inequality holds

$F(\mathbf{x}+k\mathbf{e}_{i})-F(\mathbf{x})\geq
F(\mathbf{y}+k\mathbf{e}_{i})-F(\mathbf{y})$ (6)

where $\mathbf{e}_{i}$ represents the unit vector and
$\mathbf{x}\leq\mathbf{y}$ means $x_{i}\leq y_{i},\forall i\in[n]$. A twice-
differentiable function $F(\mathbf{x})$ is DR-submodular iff

$\cfrac{\partial F(\mathbf{x})}{\partial x_{i}\partial x_{j}}\leq 0,\text{ for
}\forall\mathbf{x}\in\mathcal{X}$ (7)

It is easy to show that the multilinear extension of a submodular set function
is infinitely differentiable and DR-submodular. In addition, a differentiable
function is DR-submodular iff $\forall\mathbf{x}\leq\mathbf{y}\in\mathcal{X}$,
$\nabla F(\mathbf{x})\geq\nabla F(\mathbf{y})$. Based on this observation,
naturally, there is the following lemma.

######  Lemma 3 (Marinacci and Montrucchio (2005); Calinescu et al. (2011);
Bian et al. (2017b))

If $F(\mathbf{x})$ is DR-submodular, then $F(\mathbf{x})$ is concave along any
non-negative directions.

Lemma 3 shows that DR-submodular functions possess certain ‘concavity’ to some
extent, implying the following result.

######  Lemma 4 (A rephrased version of Lemma 3 in Bian et al. (2017a))

If $F(\mathbf{x})$ is DR-submodular and non-negative, then for any
$\mathbf{x},\mathbf{y}\in\mathcal{X}$, we have:

$\displaystyle F(\mathbf{x}\vee\mathbf{y})$
$\displaystyle\geq(1-\alpha)F(\mathbf{y})$ (8) $\displaystyle
F(\mathbf{x}\wedge\mathbf{y})$ $\displaystyle\geq\beta F(\mathbf{y})$

where $\alpha\geq\max_{i\in[n]}\frac{x_{i}-l_{i}}{u_{i}-l_{i}}$,
$\beta\leq\min_{i\in[n]}\frac{x_{i}-l_{i}}{u_{i}-l_{i}}$, and $l_{i},u_{i}$
are the lower bound and the upper bound of $\mathcal{X}_{i}$, respectively.

###### Lemma 5

For a DR-submodular function $F(\mathbf{x})$ defined on
$\mathcal{X}=[\mathbf{l},\mathbf{u}]$, where
$\mathbf{l}=(l_{1},l_{2},...,l_{n})$, $\mathbf{u}=(u_{1},u_{2},...,u_{n})$ are
the lower bound and the upper bound of $\mathcal{X}$, we denote
$\alpha_{i}=\frac{x_{i}-l_{i}}{u_{i}-l_{i}}$ for all $i\in[n]$ and
$\mathbf{l}_{S}=(l_{s_{1}},l_{s_{2}},...,l_{s_{n}})$ by $l_{s_{i}}=l_{i}$ if
$i\in S$ otherwise $l_{s_{i}}=0$, similarly, $\mathbf{u}_{[n]\setminus S}$.
Then, we have:

$F(\mathbf{x})\geq\sum_{S\subseteq[n]}F(\mathbf{l}_{[n]\setminus
S}\vee\mathbf{u}_{S})\prod_{i\in S}\alpha_{i}\prod_{j\in[n]\setminus
S}(1-\alpha_{j})$ (9)

Proof  If $n=1$,
$F(\mathbf{x})=F(\alpha_{1}u_{1}+(1-\alpha_{1})l_{1})\geq\alpha_{1}F(u_{1})+(1-\alpha_{1})F(l_{1})$.
By induction, we assume that Eq.(9) holds on $n=k-1$. Therefore, when $n=k$,
we have:

$\displaystyle F(\mathbf{x})$
$\displaystyle=F(\alpha_{k}(u_{k}\mathbf{e}_{k}\vee\mathbf{x}_{[k-1]})+(1-\alpha_{k})(l_{k}\mathbf{e}_{k}\vee\mathbf{x}_{[k-1]}))$
$\displaystyle\geq\alpha_{k}F(u_{k}\mathbf{e}_{k}\vee\mathbf{x}_{[k-1]})+(1-\alpha_{k})F(l_{k}\mathbf{e}_{k}\vee\mathbf{x}_{[k-1]})$
$\displaystyle\geq\alpha_{k}\sum_{S\subseteq[k-1]}F(\mathbf{l}_{[k-1]\setminus
S}\vee\mathbf{u}_{S\cup\\{k\\}})\prod_{i\in
S}\alpha_{i}\prod_{j\in[k-1]\setminus S}(1-\alpha_{j})$
$\displaystyle\quad+(1-\alpha_{k})\sum_{S\subseteq[k-1]}F(\mathbf{l}_{[k]\setminus
S}\vee\mathbf{u}_{S})\prod_{i\in S}\alpha_{i}\prod_{j\in[k-1]\setminus
S}(1-\alpha_{j})$
$\displaystyle=\sum_{S\subseteq[k]}F(\mathbf{l}_{S}\vee\mathbf{u}_{[k]\setminus
S})\prod_{i\in S}\alpha_{i}\prod_{j\in[k]\setminus S}(1-\alpha_{j})$

We need the concept of stationary point for problem (1), where we only need to
assume that $F$ is differentiable.

###### Definition 6

A feasible solution $\mathbf{x}\in\mathcal{P}$ for problem (1) is a stationary
point, when $F$ is differentiable, if it satisfies the first-order necessary
condition,

$\max_{\mathbf{y}\in\mathcal{P}}\langle\nabla
F(\mathbf{x}),\mathbf{y}-\mathbf{x}\rangle\leq 0$ (10)

When $F$ is further assumed to be DR-submodular, as assumed in problem (1), we
have the following inequality.

######  Lemma 7 (A rephrased version of Corollary 3.3 in Chekuri et al.
(2014))

If $\mathbf{x}$ is a stationary point for problem (1), then

$2F(\mathbf{x})\geq
F(\mathbf{x}\vee\mathbf{y})+F(\mathbf{x}\wedge\mathbf{y}),\forall\mathbf{y}\in\mathcal{X}$
(11)

Lemma 7 immediately implies the following result by a simple convex
combination of (11) with another inequality resulting from choosing
$y:=x\wedge y\in\mathcal{P}$ due to down-closeness in (11).

###### Lemma 8

If $\mathbf{x}$ is a stationary point for (1), then we have

$F(\mathbf{x})\geq\gamma
F(\mathbf{x}\vee\mathbf{y})+(1-\gamma)F(\mathbf{x}\wedge\mathbf{y}),\forall\mathbf{y}\in\mathcal{X},\gamma\in[0,0.5]$
(12)

##  3 Performance of Stationary Points

Although Hassani et al. (2017) show that the ratio between the values of the
worst stationary point and the optimal solution for monotone DR-submodular
objective functions is $1/2$, it is still an open problem whether the same
approximation ratio still holds for the non-monotone case. We answer this
question negatively by showing that stationary points can have arbitrarily bad
approximation ratios. For this purpose, we construct an example to show that
the value ratio between the worst stationary point and the optimal solution
approaches $0$ for the non-monotone case. In addition, we observe an
interesting phenomenon that the worst stationary point tend to be close to the
boundary of the feasible domain, implying that removing stationary points near
the boundary of the feasible domain can potentially improves the approximation
ratio of stationary points, as have been done previously in the literature,
such as Chekuri et al. (2014); Buchbinder and Feldman (2019). Our example may
explain their success in obtaining improved approximation algorithms.

The rest of this section provides a new analysis, which removes the reliance
on the multilinear and the Lovasz extensions used in Chekuri et al. (2014), to
prove that their _restricted local search_ algorithm is also a $0.309$
approximation solution in the continuous domain.

###  3.1 Negative Result for Stationary Points

The conventional coverage function is one of the famous submodular set
functions, which is monotone non-decreasing, and non-negative. Inspired by the
coverage function, we construct a regular coverage function which is the
difference between the coverage function and the size of the selected
solution. The formal description is as follows.

###### Definition 9

For a ground set $V=\\{1,2,...,n\\}$ and a subset collection
$\\{S_{1},...,S_{n}\\}$ where $S_{i}\subseteq V$, the regular coverage
function is defined as $f(X)=|\bigcup_{i\in X}S_{i}|-|X|$.

According to the above definition, although the regular coverage function is
not always non-negative, we can construct a concrete example of the regular
coverage function such that it is non-monotone and non-negative.

###### Example 1

Let $V=\\{1,2,...,2k+1\\}$, $S_{i}=\\{i,2k+1\\}$ for $i\in\\{1,2,...,k\\}$,
$S_{i}=\\{i\\}$ for $i\in\\{k+1,k+2,...,2k\\}$, and
$S_{2k+1}=\\{1,2,...,k,2k+1\\}$. It is not hard to show that the regular
coverage function for this instance is non-monotone, non-negative, and
submodular.

###### Example 2

As an illustration of the above example, choosing $k=1$ gives us
$V=\\{1,2,3\\}$, $S_{1}=\\{1,3\\}$, $S_{2}=\\{2\\}$, $S_{3}=\\{1,3\\}$. Then,
$f(\\{1\\})=1$, $f(\\{2\\})=0$, $f(\\{3\\})=1$, $f(S\\{1,2\\})=1$,
$f(\\{1,3\\})=0$, $f(\\{2,3\\})=1$, $f(\\{1,2,3\\})=0$.

Based on the setup of Example 1, let $F:[0,1]^{2k+1}\rightarrow\mathbb{R}_{+}$
be the multilinear extension of the regular coverage function
$f:2^{V}\rightarrow\mathbb{R}_{+}$. $F(\mathbf{x})$ and $\nabla F(\mathbf{x})$
have the following closed-form:

$\begin{array}[]{c}\begin{aligned} F(\mathbf{x})&=\sum_{S\subseteq
V}f(S)\cdot\prod_{i\in S}x_{i}\cdot\prod_{i\notin S}(1-x_{i})=\sum_{S\subseteq
V}(|\cup_{i\in S}S_{i}|-|S|)\cdot\prod_{i\in S}x_{i}\cdot\prod_{i\notin
S}(1-x_{i})\\\ &=\sum_{S\subseteq V}|\cup_{i\in S}S_{i}|\cdot\prod_{i\in
S}x_{i}\cdot\prod_{i\notin S}(1-x_{i})-\sum_{S\subseteq V}|S|\cdot\prod_{i\in
S}x_{i}\cdot\prod_{i\notin S}(1-x_{i})\\\
&=k+1-\left(1-x_{2k+1}\right)\prod_{i=1}^{k}\left(1-x_{i}\right)-\left(1-x_{2k+1}\right)\left(k-\sum_{i=1}^{k}x_{i}\right)+\sum_{i=k+1}^{2k}x_{i}-\sum_{i=1}^{2k+1}x_{i}\\\
&=k+1-\left(1-x_{2k+1}\right)\prod_{i=1}^{k}\left(1-x_{i}\right)-\left(1-x_{2k+1}\right)\left(k-\sum_{i=1}^{k}x_{i}\right)-\sum_{i=1}^{k}x_{i}-x_{2k+1}\end{aligned}\\\
\cfrac{\partial F(\mathbf{x})}{\partial
x_{i}}=\begin{cases}(1-x_{2k+1})\cdot\prod_{j=1,j\neq
i}^{k}(1-x_{j})-x_{2k+1}&\text{ if }i\leq k\\\ 0&\text{ if }k+1\leq i\leq
2k\\\ \prod_{j=1}^{k}(1-x_{j})+k-\sum_{i=1}^{k}x_{i}-1&\text{ if
}i=2k+1\end{cases}\end{array}$ (13)

Our goal is to calculate the ratio between the worst stationary point and the
optimal solution. In other words, we want to minimize the ratio between
stationary points in the feasible domain and the optimal solution, i.e.,
minimize the ratio $\frac{F(\mathbf{x})}{F(\mathbf{x}^{*})}$ where
$\mathbf{x}$ is an arbitrary stationary point in the feasible domain and
$\mathbf{x}^{*}$ is the optimal solution. To achieve our objective, we
construct the following minimization problem.

$\displaystyle\min$ $\displaystyle\quad\cfrac{F(\mathbf{x})}{F(\mathbf{y})}$
(14) s.t. $\displaystyle\mathbf{x}\text{ is a stationary point}$
$\displaystyle\mathbf{x},\mathbf{y}\text{ are feasible}$

Note that the objective function in Eq.(14) is to minimize the ratio
$\frac{F(\mathbf{x})}{F(\mathbf{y})}$ and $\mathbf{y}$ is in the denominator.
It means that the ratio $\frac{F(\mathbf{x})}{F(\mathbf{y})}$ reaches the
global minimum if and only if $\mathbf{y}$ is the optimal solution of the
function $F$ in the feasible domain. It implies that constraints on the above
minimization problem are that $\mathbf{x}$ is a stationary point and
$\mathbf{x},\mathbf{y}$ are in the feasible domain. Because the multilinear
extension $F(\mathbf{x})$ is defined in $[0,1]^{2k+1}$ which is a special
down-closed convex constraint, an immediate observation is that
$\mathbf{z}^{*}=\arg\max_{\mathbf{z}\in[0,1]^{2k+1}}\left\langle\nabla
F(\mathbf{x}),\mathbf{z}-\mathbf{x}\right\rangle=\mathbf{1}_{\nabla
F(\mathbf{x})_{\geq 0}}$, where the last term is the $n$-dimensional binary
vector whose $i$-th coordinate ($i\in[n]$) is 1 when $\frac{\partial
F(\mathbf{x})}{\partial x_{i}}\geq 0$ and 0 otherwise. We can therefore
simplify the constraint as follows:

$\max_{\mathbf{z}\in[0,1]^{2k+1}}\langle\nabla
F(\mathbf{x}),\mathbf{z}-\mathbf{x}\rangle\leq 0\iff\langle\nabla
F(\mathbf{x}),\mathbf{1}_{\nabla F(\mathbf{x})_{\geq 0}}-\mathbf{x}\rangle\leq
0$

Now, we have the following optimization problem to reveal the ratio between
the worst stationary point and the optimal solution.

$\displaystyle\min$ $\displaystyle\qquad\cfrac{F(\mathbf{x})}{F(\mathbf{y})}$
(15) s.t. $\displaystyle\left\langle\nabla F(\mathbf{x}),\mathbf{1}_{\nabla
F(\mathbf{x})_{\geq 0}}-\mathbf{x}\right\rangle\leq 0$
$\displaystyle\mathbf{x},\mathbf{y}\in[0,1]^{2k+1}$

Specially, we choose two special points $\mathbf{x}$ and $\mathbf{y}$, where
$x_{i}=1$, $y_{i}=0$ for $i=1,...,2k$, and $x_{2k+1}=0$, $y_{2k+1}=1$. In
addition, we have $\frac{\partial F(\mathbf{x})}{\partial x_{i}}=0$ for
$i=1,...,2k$, $\frac{\partial F(\mathbf{x})}{\partial x_{2k+1}}=-1$,
$\frac{\partial F(\mathbf{y})}{\partial y_{i}}=-1$ for $i=1,...,k$,
$\frac{\partial F(\mathbf{y})}{\partial y_{i}}=0$ for $i=k+1,...,2k$, and
$\frac{\partial F(\mathbf{y})}{\partial y_{2k+1}}=k$. Therefore,

$\displaystyle\max_{\mathbf{z}\in[0,1]^{2k+1}}\langle\nabla
F(\mathbf{x}),\mathbf{z}-\mathbf{x}\rangle$ $\displaystyle=$
$\displaystyle\langle\nabla
F(\mathbf{x}),\mathbf{1}_{[2k]}-\mathbf{x}\rangle=0$
$\displaystyle\max_{\mathbf{z}\in[0,1]^{2k+1}}\langle\nabla
F(\mathbf{y}),\mathbf{z}-\mathbf{y}\rangle$ $\displaystyle=$
$\displaystyle\langle\nabla
F(\mathbf{x}),\mathbf{1}_{[k+1,2k+1]}-\mathbf{y}\rangle=0$

It implies that $\mathbf{x}$ and $\mathbf{y}$ are stationary points, i.e.,
$\frac{F(\mathbf{x})}{F(\mathbf{y})}=\frac{1}{k}$. In other words, the ratio
between the worst stationary point and the optimal solution is not greater
than $\frac{1}{k}$, which approaches $0$ with increasing $k$.

In terms of the numerical solution, solving Eq.(15) under $k=2$, $3$, $5$,
$10$, $20$, $30$, $50$, the ratio between the worst stationary point and the
optimal solution decreases with $k$ and tends to $0$. Details are in Tab.2.
Although Eq.(15) is non-convex and non-concave, the solution returned by the
optimization algorithm is a stationary point of Eq.(15). It represents that
the global minimum of Eq.(15) is no more than that of the solution returned by
the optimization algorithm. In addition, there is an interesting phenomenon
that the maximal component of the bad stationary point tends to be close to
$1$. Therefore, we have the following claim.

###### Claim 1

For non-monotone continuous DR-submodular functions, the ratio
$\frac{F(\mathbf{x})}{F(\mathbf{x}^{*})}$ is $0$, where $\mathbf{x}$ is the
worst stationary point and $\mathbf{x}^{*}$ is the optimal solution. It
implies that the stationary point will be arbitrarily bad in non-monotone
cases. Furthermore, the worst stationary point tends to be close to the
boundary of the feasible domain.

Table 2: Ratios between the worst stationary point and the optimal solution |  $k=2$ |  $k=3$ |  $k=5$ |  $k=10$ |  $k=20$ |  $k=30$ |  $k=50$
---|---|---|---|---|---|---|---
Ratio $\frac{F(\mathbf{x})}{F(\mathbf{y})}$ |  $0.4142$ |  $0.3222$ |  $0.1999$ |  $0.1000$ |  $0.0500$ |  $0.0333$ |  $0.0200$
$\max_{i\in[2k+1]}x_{i}$ |  $0.5858$ |  $0.6778$ |  $0.9999$ |  $0.9999$ |  $0.9804$ |  $1.0000$ |  $0.9942$

###  3.2 Stationary Points in Reduced Feasible Domain

According to Tab.2 and Claim 1, if we want stationary points to yield better
approximation ratio, removing some of the bad stationary points that are near
the boundary of the feasible domain is a natural approach. To some extent, it
explains why the restricted continuous local search by Chekuri et al. (2014)
has a better approximation ratio than the continuous local search for
maximizing the multilinear extension of submodular set functions. Moreover,
the proofs in Chekuri et al. (2014) heavily depend on the fact that the
multilinear extension is no less than the Lovasz extension of any submodular
set function. Therefore leaving open the question whether the approximation
ratio $0.309$ can also be achieved in the continuous domain for DR-submodular
functions that are not arising from the multilinear extension.

In problem (1), $\forall m\in[0,1]$, define the reduced feasible domain
$\mathcal{P}\cap[0,m]^{n}$. We introduce a projection vector $\mathbf{w}$ that
depends on the stationary point $\mathbf{x}\in\mathcal{P}\cap[0,m]^{n}$, such
that, for each point $\mathbf{z}\in\mathcal{P}$ but
$\mathbf{z}\notin\mathcal{P}\cap[0,m]^{n}$, there is a vector
$\mathbf{z}^{\prime}=\mathbf{z}\wedge\mathbf{w}\in\mathcal{P}$ but
$\mathbf{z}^{\prime}\notin\mathcal{P}\cap[0,m]^{n}$ satisfying the following
lemma.

######  Lemma 10 (A rephrased version of Lemma 3.16 in Chekuri et al. (2014))

Let $\mathbf{x}$ be a stationary point in $\mathcal{P}\cap[0,m]^{n}$ and
$\mathbf{z}$ be any point in $\mathcal{P}$. Define
$\mathbf{w}=(w_{1},w_{2},...,w_{n})\in[0,1]^{n}$ by $w_{i}=m$ if $x_{i}\geq
m-\varepsilon$ and $w_{i}=1$ if $x_{i}<m-\varepsilon$. Then, for
$\mathbf{z}^{\prime}=\mathbf{z}\wedge\mathbf{w}$, we have:

$2F(\mathbf{x})\geq
F(\mathbf{x}\wedge\mathbf{z}^{\prime})+F(\mathbf{x}\vee\mathbf{z}^{\prime})$
(16)

To prove the approximation ratio of $\mathbf{x}$, we next prove the following
lower bounds on $F(\mathbf{x}\vee\mathbf{z}^{\prime})$ and
$F(\mathbf{x}\wedge\mathbf{z}^{\prime})$, respectively, without using the
multilinear and Lovasz extensions as have been done in Chekuri et al. (2014).
Therefore the following lemmas hold not only for DR-submodular functions
arising as the multilinear extensions of submodular set functions but also for
general DR-submodular functions defined directly on the continuous domain. We
propose a simplified and unified analysis by only using the DR-submodularity
of $F$.

###### Lemma 11

Let $\mathbf{x}\in\mathcal{P}\cap[0,m]^{n}$ be a stationary point in the
reduced domain and $\mathbf{x}^{*}\in\mathcal{P}$ be the optimal solution.
Denote $A=\\{i\in[n]:x_{i}\geq m-\varepsilon\\}$ and $\hat{A}=[n]\setminus A$.
For $\mathbf{z}^{\prime}=\mathbf{x}^{*}\wedge\mathbf{w}$, we have:

$F(\mathbf{x}\vee\mathbf{z}^{\prime})\geq(1-m)mF(\mathbf{x}^{*})+(1-m)^{2}F(\mathbf{x}^{*}_{\hat{A}})$
(17)

where $\mathbf{x}^{*}_{\hat{A}}$ is a vector that agrees with $\mathbf{x}^{*}$
on coordinates belonging to $\hat{A}$, and equals to 0 on other coordinates,
i.e., $\mathbf{x}^{*}_{A}\wedge\mathbf{x}^{*}_{\hat{A}}=\mathbf{0}$,
$\mathbf{x}^{*}_{A}\vee\mathbf{x}^{*}_{\hat{A}}=\mathbf{x}^{*}$.

Proof  Firstly, define a function $G$ on $[\mathbf{0},\mathbf{x}^{*}_{A}]$;
that is, $\forall\mathbf{y}\in[\mathbf{0},\mathbf{x}^{*}_{A}]$,
$G(\mathbf{y}):=F(\mathbf{x}^{*}_{\hat{A}}+\mathbf{y})-F(\mathbf{x}^{*}_{\hat{A}})$.
Note that $G(\mathbf{0})=0$. We now show that $G$ is DR-submodular. $\forall
i\in A$ and $k_{i}\in\mathbb{R}_{+}$, for all
$\mathbf{a}\leq\mathbf{b}\in[\mathbf{0},\mathbf{x}^{*}_{A}]$ and
$\mathbf{b}+k_{i}\mathbf{e}_{i}\in[\mathbf{0},\mathbf{x}^{*}_{A}]$.

$\displaystyle G(k_{i}\mathbf{e}_{i}+\mathbf{a})-G(\mathbf{a})$
$\displaystyle=F((k_{i}\mathbf{e}_{i}+\mathbf{a})+\mathbf{x}^{*}_{\hat{A}})-F(\mathbf{a}+\mathbf{x}^{*}_{\hat{A}})=F(k_{i}\mathbf{e}_{i}|\mathbf{a}+\mathbf{x}^{*}_{\hat{A}})$
$\displaystyle\geq
F(k_{i}\mathbf{e}_{i}|\mathbf{b}+\mathbf{x}^{*}_{\hat{A}})=F((k_{i}\mathbf{e}_{i}+\mathbf{b})+\mathbf{x}^{*}_{\hat{A}})-F(\mathbf{b}+\mathbf{x}^{*}_{\hat{A}})$
$\displaystyle=G(k_{i}\mathbf{e}_{i}+\mathbf{b})-G(\mathbf{b}),$

where the inequality comes from the DR-submodularity of $F$.

Next, we show that $G$ is non-decreasing on $[0,\mathbf{x}^{*}_{A}]$. If there
exist $\mathbf{y}\in[0,\mathbf{x}^{*}_{A}]$ and
$\mathbf{y}+\varepsilon\mathbf{e}_{i}\in[0,\mathbf{x}^{*}_{A}]$ such that
$G(\mathbf{y}+\varepsilon\mathbf{e}_{i})-G(\mathbf{y})<0$, i.e.,
$F(\mathbf{y}+\varepsilon\mathbf{e}_{i}+\mathbf{x}^{*}_{\hat{A}})-F(\mathbf{y}+\mathbf{x}^{*}_{\hat{A}})<0$,
then $F(\varepsilon\mathbf{e}_{i}|\mathbf{y}+\mathbf{x}^{*}_{\hat{A}})\leq 0$.
According to the DR-submodularity of $F$, we have
$F(\varepsilon\mathbf{e}_{i}|\mathbf{x}^{*}-\varepsilon\mathbf{e}_{i})\leq
F(\varepsilon\mathbf{e}_{i}|\mathbf{y}+\mathbf{x}^{*}_{\hat{A}})<0$, implying
that $F(\mathbf{x}^{*}-\varepsilon\mathbf{e}_{i})>F(\mathbf{x}^{*})$, which
contradicts the optimality of $\mathbf{x}^{*}$.

From
$\mathbf{w}_{A}\wedge\mathbf{x}^{*}_{A}\in[\mathbf{0},\mathbf{x}^{*}_{A}]$ and
$w_{i}=m,\forall i\in A$, we have
$\mathbf{w}_{A}\wedge\mathbf{x}^{*}_{A}=m\mathbf{x}^{*}_{A}+(1-m)(\mathbf{x}^{*}_{A}-\frac{1}{1-m}(\mathbf{x}^{*}_{A}-\mathbf{x}^{*}_{A}\wedge\mathbf{w}_{A}))$.
Also,
$\mathbf{x}^{*}_{A}-\frac{1}{1-m}(\mathbf{x}^{*}_{A}-\mathbf{x}^{*}_{A}\wedge\mathbf{w}_{A})=\frac{1}{1-m}\mathbf{x}^{*}_{A}\wedge\mathbf{w}_{A}-\frac{m}{1-m}\mathbf{x}^{*}_{A}\geq
0$. For $i\in A$, if $m\leq x^{*}_{i}$, we have $\frac{m-mx^{*}_{i}}{1-m}\leq
x^{*}_{i}\iff m-mx^{*}_{i}\leq x^{*}_{i}-mx^{*}_{i}$. For $i\in A$, if $m\geq
x^{*}_{i}$, we have $\frac{x^{*}_{i}-mx^{*}_{i}}{1-m}\leq x^{*}_{i}\iff
x^{*}_{i}-mx^{*}_{i}\leq x^{*}_{i}-mx^{*}_{i}$. It implies that
$\mathbf{x}^{*}_{A}-\frac{1}{1-m}(\mathbf{x}^{*}_{A}-\mathbf{x}^{*}_{A}\wedge\mathbf{w}_{A})\leq\mathbf{x}^{*}_{A}$,
i.e.,
$\mathbf{x}^{*}_{A}-\frac{1}{1-m}(\mathbf{x}^{*}_{A}-\mathbf{x}^{*}_{A}\wedge\mathbf{w}_{A})\in[\mathbf{0},\mathbf{x}^{*}_{A}]$.
Then, we have

$\displaystyle G(\mathbf{w}_{A}\wedge\mathbf{x}^{*}_{A})$ $\displaystyle\geq
mG(\mathbf{x}^{*}_{A})+(1-m)G\left(\mathbf{x}^{*}_{A}-\frac{1}{1-m}(\mathbf{x}^{*}_{A}-\mathbf{x}^{*}_{A}\wedge\mathbf{w}_{A})\right)$
$\displaystyle\geq
mG(\mathbf{x}^{*}_{A})=mF(\mathbf{x}^{*})-mF(\mathbf{x}^{*}_{\hat{A}}),$

where the first inequality comes from Lemma 3; and the second inequality comes
from Lemma 4.

Finally we complete our proof.

$\displaystyle F(\mathbf{x}\vee\mathbf{z}^{\prime})$
$\displaystyle=F(\mathbf{x}\vee(\mathbf{x}^{*}\wedge\mathbf{w}))\geq(1-m)F(\mathbf{w}\wedge\mathbf{x}^{*})=(1-m)F((\mathbf{w}_{A}\wedge\mathbf{x}^{*}_{A})\vee\mathbf{x}^{*}_{\hat{A}})$
$\displaystyle=(1-m)\left[F(\mathbf{x}^{*}_{\hat{A}})+F(\mathbf{w}_{A}\wedge\mathbf{x}^{*}_{A}|\mathbf{x}^{*}_{\hat{A}})\right]=(1-m)\left[F(\mathbf{x}^{*}_{\hat{A}})+G(\mathbf{w}_{A}\wedge\mathbf{x}^{*}_{A})\right]$
$\displaystyle\geq(1-m)\left[F(\mathbf{x}^{*}_{\hat{A}})+mG(\mathbf{x}^{*}_{A})\right]=(1-m)\left[F(\mathbf{x}^{*}_{\hat{A}})+mF(\mathbf{x}^{*})-mF(\mathbf{x}^{*}_{\hat{A}})\right]$
$\displaystyle=(1-m)mF(\mathbf{x}^{*})+(1-m)^{2}F(\mathbf{x}^{*}_{\hat{A}}),$

where the inequality comes from the DR-submodularity of $F$ and $G$, and Lemma
4.

###### Lemma 12

Let $\mathbf{x}\in\mathcal{P}\cap[0,m]^{n}$ be a stationary point in the
reduced domain and $\mathbf{x}^{*}\in\mathcal{P}$ be the optimal solution.
Denote $A=\\{i\in[n]:x_{i}\geq m-\varepsilon\\}$ and $\hat{A}=[n]\setminus A$.
For $\mathbf{z}^{\prime}=\mathbf{x}^{*}\wedge\mathbf{w}$, we have:

$F(\mathbf{x}\wedge\mathbf{z}^{\prime})\geq(m-\varepsilon)\left[F(\mathbf{x}^{*})-F(\mathbf{x}^{*}_{\hat{A}})\right]$
(18)

Proof

$\displaystyle F(\mathbf{x}\wedge\mathbf{z}^{\prime})$
$\displaystyle=F(\mathbf{x}\wedge\mathbf{x}^{*}\wedge\mathbf{w})=F(\mathbf{x}\wedge\mathbf{x}^{*})=F((\mathbf{x}_{A}\vee\mathbf{1}_{\hat{A}})\wedge(\mathbf{x}_{\hat{A}}\vee\mathbf{1}_{A})\wedge\mathbf{x}^{*})$
$\displaystyle\geq(m-\varepsilon)F((\mathbf{x}_{\hat{A}}\vee\mathbf{1}_{A})\wedge\mathbf{x}^{*})=(m-\varepsilon)F((\mathbf{x}_{\hat{A}}\wedge\mathbf{x}^{*}_{\hat{A}})\vee\mathbf{x}^{*}_{A})$
$\displaystyle\geq(m-\varepsilon)\left[F(\mathbf{x}^{*})-F(\mathbf{x}^{*}_{\hat{A}})\right].$

In the above, the first inequality is because of Lemma 4. The second
inequality comes from the submodularity
$F((\mathbf{x}_{\hat{A}}\wedge\mathbf{x}^{*}_{\hat{A}})\vee\mathbf{x}^{*}_{A})+F(\mathbf{x}^{*}_{\hat{A}})\geq
F(\mathbf{x}^{*})+F((\mathbf{x}_{\hat{A}}\vee\mathbf{x}^{*}_{A})\wedge\mathbf{x}^{*}_{\hat{A}})$,
where
$(\mathbf{x}_{\hat{A}}\wedge\mathbf{x}^{*}_{\hat{A}})\vee\mathbf{x}^{*}_{A}\vee\mathbf{x}^{*}_{\hat{A}}=\mathbf{x}^{*}$
and
$((\mathbf{x}_{\hat{A}}\wedge\mathbf{x}^{*}_{\hat{A}})\vee\mathbf{x}^{*}_{A})\wedge\mathbf{x}^{*}_{\hat{A}}=(\mathbf{x}_{\hat{A}}\vee\mathbf{x}^{*}_{A})\wedge(\mathbf{x}^{*}_{\hat{A}}\vee\mathbf{x}^{*}_{A})\wedge\mathbf{x}^{*}_{\hat{A}}$.

In light of the above lemmas, next, we prove the approximation ratio of
stationary points in $\mathcal{P}\cap[0,m]^{n}$.

###### Theorem 13

Any stationary point in
$\mathcal{P}\cap\left[0,\frac{3-\sqrt{5}}{2}\right]^{n}$ produces a value that
is at least $(0.309-O(\varepsilon))$ of the optimal solution for problem (1).

Proof  According to Lemmas 10, 11, and 12, we have:

$\displaystyle F(\mathbf{x})$
$\displaystyle\geq\cfrac{1}{2}\left[F(\mathbf{x}\vee\mathbf{z}^{\prime})+F(\mathbf{x}\wedge\mathbf{z}^{\prime})\right]$
$\displaystyle\geq\cfrac{1}{2}\left[(1-m)mF(\mathbf{x}^{*})+(1-m)^{2}F(\mathbf{x}^{*}_{\hat{A}})+(m-\varepsilon)F(\mathbf{x}^{*})-(m-\varepsilon)F(\mathbf{x}^{*}_{\hat{A}})\right]$
$\displaystyle=\cfrac{(2-m)m-\varepsilon}{2}F(\mathbf{x}^{*})+\cfrac{(1-m)^{2}-m+\varepsilon}{2}F(\mathbf{x}^{*}_{\hat{A}})$

Note that $m\in\left[0,\frac{3-\sqrt{5}}{2}\right]$ implies that
$\frac{(1-m)^{2}-m}{2}F(\mathbf{x}^{*}_{\hat{A}})\geq 0$. So choosing

$m^{*}=\arg\max_{m\in\left[0,\frac{3-\sqrt{5}}{2}\right]}\frac{(2-m)m}{2}=\frac{3-\sqrt{5}}{2}$

leads to $\frac{(2-m^{*})m^{*}}{2}\geq 0.309$.

Efficient algorithms exist to return a stationary point in
$\mathcal{P}\cap[0,m]^{n}$. For example, the Frank-Wolfe algorithm with the
adaptive step (Lacoste-Julien (2016)) returns a stationary point with a gap
smaller than $\varepsilon$ in at most
$O\left(\frac{1}{\varepsilon^{2}}\right)$ iterations. Hence Theorem 13 with
this Frank-Wolfe algorithm offers us a $(0.309-\varepsilon)$ approximation
algorithm for problem (1).

To understand why this restricted local search offers better approximation
ratio than the vanilla version of the local search, note that points
stationary in the interior of $\mathcal{P}\cap[0,m]^{n}$ are also stationary
in $\mathcal{P}$; but not the other way around. Therefore, the reduced
feasible domain removes some boundary stationary points in $\mathcal{P}$, and
changes some non-stationary points in $\mathcal{P}$ to stationary points in
the reduced domain, leading to better performances.

Recall our previous Example 1. In Tab.3, we report the value ratios for the
worst stationary points in $\mathcal{P}$ and
$\mathcal{P}\cap\left[0,\frac{3-\sqrt{5}}{2}\right]^{n}$, respectively. The
results show that the approximation ratio of stationary points in
$\mathcal{P}\cap\left[0,\frac{3-\sqrt{5}}{2}\right]^{n}$ performs better than
those in $\mathcal{P}$. Also, for this particular example, the numerical
ratios are much better than the proven approximation ratio of $0.309$ when
$m=\frac{3-\sqrt{5}}{2}$, and leaving open the question on what the exact
approximation ratio of the restricted local search is.

Table 3: Ratios between the worst stationary point and the optimal solution |  $k=2$ |  $k=3$ |  $k=5$ |  $k=10$ |  $k=20$ |  $k=30$ |  $k=50$
---|---|---|---|---|---|---|---
Restricted Continuous Local Search with $m=1$ |  $0.4142$ |  $0.3222$ |  $0.1999$ |  $0.1000$ |  $0.0500$ |  $0.0333$ |  $0.0200$
Restricted Continuous Local Search with $m=\frac{3-\sqrt{5}}{2}$ |  $0.4271$ |  $0.4062$ |  $0.3945$ |  $0.3877$ |  $0.3847$ |  $0.3838$ |  $0.3830$

##  4 Aided Frank-Wolfe Variant

Because the proof of the approximation _ratio of the aided measured continuous
greedy_ algorithm in Buchbinder and Feldman (2019) strongly depends on the
discrete optimal solution and the inequality that the multilinear extension of
any submodular set function is bounded from below by its Lovasz extension,
whether the same algorithm yields a $0.385$ approximation ratio for problem
(1) on the continuous domain admits is still an open problem. In this section,
we answer this question affirmatively. Because our proof only utilizes DR-
submodularity instead of the multilinear extension, the Lovasz extension, and
the discrete optimal solution, it brings out more flexibility in tuning the
parameters used in the algorithm. To design and discretize our algorithm, we
adopt the systematic framework proposed in Du (2022a), namely Lyapunov
framework.

Firstly, we prove the following essential lemma which will be used to derive
an upper bound on the optimal solution to clear the way to adopt the
aforementioned Lyapunov framework. Note that the lemma below extends Lemma 4.4
in Buchbinder and Feldman (2019) from binary optimal solution to any solution
in $\mathcal{P}$ and its proof only uses DR-submodularity and non-negativity
of $F$. Denote

$\displaystyle\theta_{A}(t)$ $\displaystyle:=$
$\displaystyle\left\|\mathbf{x}_{A}(t)\right\|_{\infty}=\max_{i\in
A}\mathbf{x}_{i}(t);\quad\theta_{\hat{A}}(t):=\left\|\mathbf{x}_{\hat{A}}(t)\right\|_{\infty}=\max_{i\in\hat{A}}\mathbf{x}_{i}(t)$

###### Lemma 14

For any $\mathbf{z}\in\mathcal{P}$ and a partition $A\cap\hat{A}=\emptyset$,
$A\cup\hat{A}=[n]$, assume $\theta_{A}(t)\leq\theta_{\hat{A}}(t)$, we have:

$F(\mathbf{x}(t)\vee\mathbf{z})\geq\left(1-\theta_{A}(t)\right)F(\mathbf{z})-\left(\theta_{\hat{A}}(t)-\theta_{A}(t)\right)F(\mathbf{z}\vee\mathbf{1}_{A})$
(19)

Proof  For convenience and without ambiguity, denote
$\mathbf{x}=\mathbf{x}(t)$, $\theta_{A}=\theta_{A}(t)$, and
$\theta_{\hat{A}}=\theta_{\hat{A}}(t)$. First, we have:

$\mathbf{x}\vee\mathbf{z}=\left(1-\theta_{\hat{A}}\right)\mathbf{z}+\theta_{\hat{A}}\left[\mathbf{z}+\frac{1}{\theta_{\hat{A}}}(\mathbf{x}\vee\mathbf{z}-\mathbf{z})\right].$

Then,

$\mathbf{q}=\mathbf{z}+\cfrac{1}{\theta_{\hat{A}}}(\mathbf{x}\vee\mathbf{z}-\mathbf{z})=\cfrac{\mathbf{x}\vee\mathbf{z}-\left(1-\theta_{\hat{A}}\right)\mathbf{z}}{\theta_{\hat{A}}}\begin{cases}=z_{i}&z_{i}\geq
x_{i}\\\ \leq\cfrac{\theta_{A}}{\theta_{\hat{A}}}&x_{i}>z_{i},i\in A\\\
\leq\cfrac{\theta_{A}}{\theta_{\hat{A}}}&x_{i}>z_{i},\text{ some
}i\in\hat{A}\\\ >\cfrac{\theta_{A}}{\theta_{\hat{A}}}&x_{i}>z_{i},\text{
others }i\in\hat{A}\end{cases}$

According to the above inequalities, define three sets

$\displaystyle B_{1}$ $\displaystyle=$ $\displaystyle\left\\{i\in[n]:z_{i}\geq
x_{i}\right\\}$ $\displaystyle B_{2}$ $\displaystyle=$
$\displaystyle\left\\{i\in[n]:x_{i}>z_{i},q_{i}\leq\frac{\theta_{A}}{\theta_{\hat{A}}}\right\\}$
$\displaystyle B_{3}$ $\displaystyle=$
$\displaystyle\left\\{i\in[n]:x_{i}>z_{i},1\geq
q_{i}>\frac{\theta_{A}}{\theta_{\hat{A}}}\right\\}$

Obviously, $B_{3}\subseteq\hat{A}$ and
$\mathbf{q}_{B_{2}}\geq\mathbf{z}_{B_{2}}$, implying that
$\mathbf{q}=\mathbf{q}_{B_{1}}\vee\mathbf{q}_{B_{2}}\vee\mathbf{q}_{B_{3}}\vee\mathbf{z}_{B_{2}}$.
Then, we have:

$\displaystyle F(\mathbf{x}(t)\vee\mathbf{z})$
$\displaystyle\geq\left(1-\theta_{\hat{A}}\right)F(\mathbf{z})+\theta_{\hat{A}}F\left(\mathbf{z}+\frac{1}{\theta_{\hat{A}}}(\mathbf{x}\vee\mathbf{z}-\mathbf{z})\right)$
$\displaystyle=\left(1-\theta_{\hat{A}}\right)F(\mathbf{z})+\theta_{\hat{A}}F(\mathbf{q}_{B_{1}}\vee\mathbf{q}_{B_{2}}\vee\mathbf{q}_{B_{3}}\vee\mathbf{z}_{B_{2}})$
$\displaystyle\geq\left(1-\theta_{\hat{A}}\right)F(\mathbf{z})+\theta_{\hat{A}}\cfrac{\theta_{\hat{A}}-\theta_{A}}{\theta_{\hat{A}}}F(\mathbf{q}_{B_{1}}\vee\mathbf{q}_{B_{3}}\vee\mathbf{z}_{B_{2}})$
$\displaystyle\geq\left(1-\theta_{\hat{A}}\right)F(\mathbf{z})+\left(\theta_{\hat{A}}-\theta_{A}\right)(F(\mathbf{z})-F(\mathbf{z}\vee\mathbf{1}_{A}))$
$\displaystyle=\left(1-\theta_{A}\right)F(\mathbf{z})-\left(\theta_{\hat{A}}-\theta_{A}\right)F(\mathbf{z}\vee\mathbf{1}_{A}),$

where the first inequality comes from Lemma 3; the second inequality comes
from Lemma 4; and the third inequality comes from the DR-submodularity and
non-negativity of $F$, i.e.,
$F(\mathbf{q}_{B_{1}}\vee\mathbf{z}_{B_{2}}\vee\mathbf{q}_{B_{3}})+F(\mathbf{z}\vee\mathbf{1}_{A})\geq
F(\mathbf{z})+F(\mathbf{z}\vee\mathbf{1}_{A}\vee\mathbf{q}_{B_{1}}\vee\mathbf{z}_{B_{2}}\vee\mathbf{q}_{B_{3}})$
.

###  4.1 Lyapunov Function

In this subsection, we utilize the following parametric Lyapunov function
$E(\mathbf{x}(t))$ to design our algorithm for problem (1). For convenience,
we denote $\dot{E}(\mathbf{x}(t))=\frac{dE(\mathbf{x}(t))}{dt}$.

###### Definition 15

_( Du (2022a))_ The Lyapunov function associated with a continuous-time
algorithm $\mathbf{x}(t)$ and a feasible solution $\mathbf{y}\in\mathcal{P}$
for problem (1) is as follows:

$E(\mathbf{x}(t))=a(t)F(\mathbf{x}(t))+h(t)F(\mathbf{y})-d(t)F(\mathbf{x}^{*})$
(20)

And the upper bound of the optimal solution $F(\mathbf{x}^{*})$ is as follows:

$F(\mathbf{x}^{*})\leq
p(\mathbf{x}(t))F(\mathbf{x}(t))+q(\mathbf{x}(t))\langle\nabla
F(\mathbf{x}(t)),v(\mathbf{x}(t))\rangle+r(\mathbf{x}(t))F(\mathbf{y})$ (21)

where $a(t)$, $h(t)$, $d(t)$ are non-negative and non-decreasing,
$p(\mathbf{x}(t))$, $q(\mathbf{x}(t))$, $r(\mathbf{x}(t))$ are non-negative.

We recall the main ingredients of the Lyapunov framework introduced by Du
(2022b). The key idea is to enforce monotonicity of the Lyapunov function
$E(\mathbf{x}(t))$, implying that $E(\mathbf{x}(t))\geq E(\mathbf{x}(0))$,
from which the approximation ratio of the algorithm $\mathbf{x}(t)$ follows:

$\cfrac{a(t)F(\mathbf{x}(t))}{a(t)+h(t)-h(0)}+\cfrac{\left[h(t)-h(0)\right]F(\mathbf{y})}{a(t)+h(t)-h(0)}\geq\cfrac{d(t)-d(0)}{a(t)+h(t)-h(0)}F(\mathbf{x}^{*})+\cfrac{a(0)}{a(t)+h(t)-h(0)}F(\mathbf{x}(0))$
(22)

It implies that the continuous algorithm returns the solution $\mathbf{x}(t)$
with probability $p=\frac{a(t)}{a(t)+h(t)-h(0)}$ and returns the solution
$\mathbf{y}$ with probability $1-p$.

To achieve non-decreasing $E(\mathbf{x}(t))$ without using any information on
the optimal value, we backtrack sufficient conditions for the following to
hold:

$\displaystyle\dot{E}(\mathbf{x}(t))$ $\displaystyle=$
$\displaystyle\dot{a}(t)F(\mathbf{x}(t))+a(t)\langle\nabla
F(\mathbf{x}(t)),\dot{\mathbf{x}}(t))\rangle+\dot{h}(t)F(\mathbf{y})-\dot{d}(t)F(\mathbf{x}^{*})\geq
0$

Replacing $F(\mathbf{x}^{*})$ with an upper bound in (21) to obtain a lower
bound of $\dot{E}(\mathbf{x}(t))$. A sufficient condition for the above is
that this resultant lower bound is non-negative.

$\displaystyle\dot{E}(\mathbf{x}(t))$ $\displaystyle\overset{(\ref{eq:up-
bound})}{\geq}$
$\displaystyle(\dot{a}(t)-\dot{d}(t)p(\mathbf{x}(t)))F(\mathbf{x}(t))+(\dot{h}(t)-\dot{d}(t)r(\mathbf{x}(t)))F(\mathbf{y})$
$\displaystyle\langle\nabla
F(\mathbf{x}(t)),a(t)\dot{\mathbf{x}}(t)-\dot{d}(t)q(\mathbf{x}(t))v(\mathbf{x}(t))\rangle\geq
0$

Because $F(\mathbf{x}(t))$ and $F(\mathbf{y})$ are non-negative, and
$F(\mathbf{x}(t))$ is non-monotone, a sufficient condition for the above is
that the coefficients of the first two terms to be non-negative and the
coefficient of the third term is equal to zero:

$\displaystyle\dot{a}(t)$ $\displaystyle\geq$
$\displaystyle\dot{d}(t)p(\mathbf{x}(t)),\dot{h}(t)\geq\dot{d}(t)r(\mathbf{x}(t)),$
$\displaystyle\dot{\mathbf{x}}(t)$ $\displaystyle=$
$\displaystyle\cfrac{\dot{d}(t)q(\mathbf{x}(t))v(\mathbf{x}(t))}{a(t)}$

Hence, we can construct the following variation problem to design our
continuous algorithm $\mathbf{x}(t)$ such that the approximation ratio is
maximized.

$\displaystyle\max$ $\displaystyle\cfrac{d(t)-d(0)}{a(t)+h(t)-h(0)}$ (23) s.t.
$\displaystyle\dot{a}(t)\geq\dot{d}(t)p(\mathbf{x}(t))$
$\displaystyle\dot{h}(t)\geq\dot{d}(t)r(\mathbf{x}(t))$
$\displaystyle\dot{\mathbf{x}}(t))=\cfrac{\dot{d}(t)q(\mathbf{x}(t))v(\mathbf{x}(t))}{a(t)}$
$\displaystyle a(t),h(t),d(t)\text{ are non-negative and non-decreasing}$

One of the biggest advantages of this Lyapunov framework is that the algorithm
design and analysis process can be put on autopilot mode once we specify the
parametric forms of the Lyapunov function and the upper bound on optimal
value.

###  4.2 Extending the algorithm in Buchbinder and Feldman (2019) via Lyapunov
framework

Lemma 14 holds for all feasible solutions. In other words, given any map
$\mathcal{P}\ni\mathbf{x}^{*}\mapsto g(\mathbf{x}^{*})\in\mathcal{P}$, we
obtain an upper bound variant on the optimal solution as follows:

$F(g(\mathbf{x}^{*}))\leq\cfrac{F(\mathbf{x}(t))+\langle\nabla
F(\mathbf{x}(t)),\mathbf{x}(t)\vee
g(\mathbf{x^{*}})-\mathbf{x}(t)\rangle+\left(\theta_{\hat{A}}(t)-\theta_{A}(t)\right)F(g(\mathbf{x}^{*})\vee\mathbf{1}_{A})}{1-\theta_{A}(t)}$
(24)

Therefore, the main challenge to obtain a good upper bound is to construct a
proper map $g(\mathbf{x}^{*})$. The down-closeness of the convex $\mathcal{P}$
suggests a natural map: $g(\mathbf{x}^{*})=\pi(t)\wedge\mathbf{x}^{*}$, for
any given vector $\pi(t)\in[0,1]^{n}$. Note that
$g(\mathbf{x}^{*})\leq\mathbf{x}^{*}\in\mathcal{P}$. Different choices of
$\pi(t)$ will produce different algorithms. The one in Buchbinder and Feldman
(2019) is as follows:

$\pi(t)=\pi_{A}(t)\mathbf{1}_{A}+\pi_{\hat{A}}(t)\mathbf{1}_{\hat{A}}$ (25)

where $\pi_{A}(t)=0$ if $t\leq\theta$ and $\pi_{A}(t)=1$ if $t>\theta$; and
$\pi_{\hat{A}}(t)=1,\forall t\in[0,1]$, where $A\subseteq[n]$ is a random set
that depends on the stationary point $\mathbf{y}$: namely, each $i\in[n]$ is
included independently in $A$ with probability $y_{i}$. If we fix both the
parametric form of $\pi(t)$ as in (25) and the choice of $A$, but allow
$\pi_{A}(t)$ and $\pi_{\hat{A}}(t)$ to choose other continuous functions, can
we get better approximation ratio? It turns out the answer is negative as will
be explained now via the Lyapunov framework. From this discussion, we propose
the following Algorithm 1

Algorithm 1

Input: $F$: objective function, $\mathcal{P}$: feasible domain,
$\pi(t)\in[0,1]$: parameter function.
Output: the solution $\mathbf{x}(1)$ with probability $1-p$ and the solution
$\mathbf{y}$ with probability $p$

1: $\mathbf{y}\leftarrow$ Frank-Wolfe Algorithm $(F,\mathcal{P})$

2: $A$ is a random subset of $[n]$. For all $i\in[n]$, $i\in A$ with
probability of $y_{i}$ independently./* Frank-Wolfe Variant Stage */

3: Initialize $\mathbf{x}(0)=\mathbf{0}$

4: for $t\in[0,1]$ do

5:
$\mathbf{v}(t)=\arg\max\limits_{\mathbf{v}\in\mathcal{P},\mathbf{v}\leq(\mathbf{1}-\mathbf{x}(t))\wedge\pi(t)}\langle\nabla
F(\mathbf{x}(t)),\mathbf{v}\rangle$

6: $\frac{d\mathbf{x}(t)}{dt}=\mathbf{v}(t)$

7: end for

The critical thing to employ the Lyapunov framework is to find a good upper
bound with a parametric form as in (21). Next, we will take on this job.

###### Lemma 16

For each $t\in[0,1]$, we have:

$\displaystyle F(\mathbf{x}(t)\vee(\pi(t)\wedge\mathbf{x}^{*}))$
$\displaystyle\geq\pi_{\hat{A}}(t)\cdot(1-\theta_{A}(t))F(\mathbf{x}^{*})-(1-\pi_{A}(t))\cdot(1-\theta_{A}(t))F(\mathbf{x}^{*}\wedge\mathbf{1}_{A})$
(26)
$\displaystyle\quad-(\theta_{\hat{A}}(t)-\theta_{A}(t))F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{1}_{A})$

Proof

$\displaystyle F(\mathbf{x}(t)\vee(\pi(t)\wedge\mathbf{x}^{*}))$
$\displaystyle\geq(1-\theta_{A}(t))F(\pi(t)\wedge\mathbf{x}^{*})-(\theta_{\hat{A}}(t)-\theta_{A}(t))F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{1}_{A})$
$\displaystyle\geq(1-\theta_{A}(t))[F(\mathbf{x}^{*}\wedge\pi(t)\wedge\mathbf{1}_{A})+F(\mathbf{x}^{*}\wedge(\mathbf{1}_{A}\vee\pi_{\hat{A}}(t)\mathbf{1}_{\hat{A}}))-F(\mathbf{x}^{*}\wedge\mathbf{1}_{A})]$
$\displaystyle\quad-(\theta_{\hat{A}}(t)-\theta_{A}(t))F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{1}_{A})$
$\displaystyle\geq\pi_{\hat{A}}(t)\cdot(1-\theta_{A}(t))F(\mathbf{x}^{*})-(1-\pi_{A}(t))\cdot(1-\theta_{A}(t))F(\mathbf{x}^{*}\wedge\mathbf{1}_{A})$
$\displaystyle\quad-(\theta_{\hat{A}}(t)-\theta_{A}(t))F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{1}_{A})$

The first inequality is because of Lemma 14. The second inequality comes from
submodularity, i.e.,
$F(\pi(t)\wedge\mathbf{x}^{*})+F(\mathbf{x}^{*}\wedge\mathbf{1}_{A})\geq
F(\mathbf{x}^{*}\wedge\mathbf{1}_{A}\wedge\pi(t))+F(\mathbf{x}^{*}\wedge(\mathbf{1}_{A}\vee\pi(t)))$.
The last inequality is due to Lemma 4.

Lemma 16 implies the following upper bound on the optimal value
$F(\mathbf{x}^{*})$.

$\begin{array}[]{c}\begin{aligned}
F(\mathbf{x}^{*})&\leq\cfrac{F(\mathbf{x}(t))}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}+\cfrac{\langle\nabla
F(\mathbf{x}(t)),\mathbf{x}(t)\vee(\pi(t)\wedge\mathbf{x}^{*})-\mathbf{x}(t)\rangle}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}\\\
&\quad+\cfrac{\left(\theta_{\hat{A}}(t)-\theta_{A}(t)\right)}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}F((\mathbf{x}^{*}\wedge\pi(t))\vee\mathbf{y})+\cfrac{1-\pi_{A}(t)}{\pi_{\hat{A}}(t)}F(\mathbf{x}^{*}\wedge\mathbf{y})\\\
&\leq\max_{\mathbf{v}\in\mathcal{P}\wedge\pi(t)}\cfrac{\langle\nabla
F(\mathbf{x}(t)),\mathbf{x}(t)\vee\mathbf{v}-\mathbf{x}(t)\rangle}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}+\cfrac{F(\mathbf{x}(t))}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}+r(\mathbf{x}(t))F(\mathbf{y})\\\
&\leq\max_{\mathbf{v}\in\mathcal{P}\wedge\pi(t),\mathbf{v}\leq\mathbf{1}-\mathbf{x}(t)}\cfrac{\langle\nabla
F(\mathbf{x}(t)),\mathbf{v}\rangle}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}+\cfrac{F(\mathbf{x}(t))}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}+r(\mathbf{x}(t))F(\mathbf{y})\end{aligned}\\\
\\\ \bigg{\Downarrow}\\\
p(\mathbf{x}(t))=q(\mathbf{x}(t))=\cfrac{1}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}\\\
v(\mathbf{x}(t))=\arg\max\limits_{\mathbf{v}\in\mathcal{P}\wedge\pi(t),\mathbf{v}\leq\mathbf{1}-\mathbf{x}(t)}\langle\nabla
F(\mathbf{x}(t)),\mathbf{v}\rangle\\\
r(\mathbf{x}(t))=\cfrac{\left(\theta_{\hat{A}}(t)-\theta_{A}(t)\right)}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}+\cfrac{1-\pi_{A}(t)}{\pi_{\hat{A}}(t)\left\|\pi(t)\right\|_{-\infty}}\end{array}$
(27)

The first inequality comes from Eq.(26), Lemmas 3, and 5, i.e.,
$F((\mathbf{x}^{*}\wedge\pi(t))\vee\mathbf{x}(t))\leq
F(\mathbf{x}(t))+\langle\nabla
F(\mathbf{x}(t)),(\mathbf{x}^{*}\wedge\pi(t))\vee\mathbf{x}(t)-\mathbf{x}(t)\rangle$.
The second inequality is from Lemma 8, i.e.,
$F(\mathbf{y})=\int_{0}^{1}F(\mathbf{y})d\lambda(t)\geq\gamma\int_{0}^{1}F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{y})d\lambda(t)+(1-\gamma)\int_{0}^{1}F(\pi(t)\wedge\mathbf{x}^{*}\wedge\mathbf{y})d\lambda(t)\geq\gamma\int_{0}^{1}F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{y})d\lambda(t)+(1-\gamma)F(\mathbf{x}^{*}\wedge\mathbf{y})\int_{0}^{1}\left\|\pi(t)\right\|_{-\infty}d\lambda(t)$
for every $\int_{0}^{1}d\lambda(t)=1$. Therefore, for the given constraints,
we can decide $a(t)$, $d(t)$, $h(t)$, $\theta_{A}(t)$, $\theta_{\hat{A}}(t)$
by the following equations.

$\begin{cases}&\dot{a}(t)=\dot{d}(t)p(\mathbf{x}(t))\\\
&\dot{h}(t)=\dot{d}(t)r(\mathbf{x}(t))\\\
&\dot{\mathbf{x}}(t))=\cfrac{\dot{d}(t)q(\mathbf{x}(t))v(\mathbf{x}(t))}{a(t)}\\\
\end{cases}\Rightarrow\begin{cases}&a(t)=e^{t}\\\
&\dot{\mathbf{x}}(t))=v(\mathbf{x}(t))\\\
&\theta_{A}(t)=1-e^{-\int_{0}^{t}\pi_{A}(s)ds}\\\
&\theta_{\hat{A}}(t)=1-e^{-\int_{0}^{t}\pi_{\hat{A}}(s)ds}\\\
&d(t)=\int_{0}^{t}g_{A}(t)\pi_{\hat{A}}(t)dt\\\
&h(t)=\int_{0}^{t}g_{A}(t)-g_{\hat{A}}(t)+\frac{1-\pi_{A}(t)}{\left\|\pi(t)\right\|}g_{A}(t)dt\end{cases}$
(28)

Because of $p(\mathbf{x}(t))=q(\mathbf{x}(t))$, we have
$\dot{\mathbf{x}}(t)=\frac{\dot{a}(t)}{a(t)}v(\mathbf{x}(t))$. To ensure that
the final output $\mathbf{x}(1)=\int_{0}^{1}v(\mathbf{x}(s))d(\ln a(s))$ is a
feasible solution in $\mathcal{P}$, we fix the stopping time at $t=1$ and
hence $\mathbf{x}(t)$ is a convex combination of feasible solutions
$v(\mathbf{x}(s))$. It induces that we have $\ln(a(0))=0$ and $\ln(a(1))=1$,
i.e., $a(t)=e^{t}$. Also, we have
$\dot{\mathbf{x}}(t)\leq\frac{\dot{a}(t)}{a(t)}\circ(\mathbf{1}-\mathbf{x}(t))\circ\pi(t)$.
It implies $x_{i}(t)\leq 1-{e^{-\int_{0}^{t}\pi_{A}(s)ds}}$ for $i\in A$ and
$x_{i}(t)\leq 1-{e^{-\int_{0}^{t}\pi_{\hat{A}}(s)ds}}$ for $i\in\hat{A}$.
Therefore, we have the explicit form of
$\theta_{A}(t),\theta_{\hat{A}}(t),d(t),h(t)$. For convenience, we denote
$g_{A}(t)=e^{t-\int_{0}^{t}\pi_{A}(s)ds}$ and
$g_{\hat{A}}(t)=e^{t-\int_{0}^{t}\pi_{\hat{A}}(s)ds}$.

Plugging Eq.(27) and Eq.(28) into Eq.(23), we construct the following
optimization problem to maximize the approximation ratio of Algorithm 1. The
first constraint comes from the condition of Lemma 14, i.e.,
$\theta_{A}(t)\leq\theta_{\hat{A}}(t)$. The second constraint comes from Lemma
8, i.e., $\gamma\in[0,1/2]$.

$\displaystyle\max$
$\displaystyle\cfrac{\int_{0}^{1}\pi_{\hat{A}}(q)g_{A}(q)dq}{e+\int_{0}^{1}g_{A}(q)-g_{\hat{A}}(q)+\frac{(1-\pi_{A}(q))g_{A}(q)}{\left\|\pi(q)\right\|_{-\infty}}dq}$
(29) s.t. $\displaystyle e^{-\int_{0}^{t}\pi_{A}(s)ds}\geq
e^{-\int_{0}^{t}\pi_{\hat{A}}(s)ds}$
$\displaystyle\int_{0}^{1}\cfrac{\left(\theta_{\hat{A}}(t)-\theta_{A}(t)\right)}{(1-\theta_{A}(t))\pi_{\hat{A}}(t)}dt\leq\int_{0}^{1}\cfrac{1-\pi_{A}(t)}{\pi_{\hat{A}}(t)\left\|\pi(t)\right\|_{-\infty}}dt$
$\displaystyle\pi_{A}(t),\pi_{\hat{A}}(t)\in[0,1]$

Note that $1\leq g_{\hat{A}}(t)\leq g_{A}(t)\leq e^{t}$, $g_{\hat{A}}(t)$ and
$g_{A}(t)$ are non-decreasing. It means that the increasing rate of
$\int_{0}^{1}g_{A}(q)-g_{\hat{A}}(q)dq$ with increasing $\pi_{\hat{A}}(q)$ is
less than the that of $\int_{0}^{1}\pi_{\hat{A}}(q)g_{A}(q)dq$ with increasing
$\pi_{\hat{A}}(q)$. In addition, a larger $\pi_{\hat{A}}(q)$ implies a larger
$\int_{0}^{1}\pi_{\hat{A}}(q)g_{A}(q)dq$ and a smaller
$\int_{0}^{1}\frac{(1-\pi_{A}(q))g_{A}(q)}{\left\|\pi(q)\right\|_{-\infty}}dq$.
Hence, a larger $\pi_{\hat{A}}(t)$ induces a larger approximation ratio.
Therefore, for all $t\in[0,1]$, we have:

$\pi_{\hat{A}}(t)=1\Rightarrow g_{\hat{A}}(t)=1$ (30)

From $\pi_{\hat{A}}(t)=1$, it means
$F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{1}_{A})=F(\mathbf{x}^{*}\vee\mathbf{1}_{A})$.
In other words, we can replace $F((\pi(t)\wedge\mathbf{x}^{*})\vee\mathbf{y})$
by $F(\mathbf{x}^{*}\vee\mathbf{y})$. Therefore, Eq.(26) can be rewritten as:

$\displaystyle F(\mathbf{x}(t)\vee(\pi(t)\wedge\mathbf{x}^{*}))$
$\displaystyle\geq\pi_{\hat{A}}(t)\cdot(1-\theta_{A}(t))F(\mathbf{x}^{*})-(1-\pi_{A}(t))\cdot(1-\theta_{A}(t))F(\mathbf{x}^{*}\wedge\mathbf{1}_{A})$
(31)
$\displaystyle\quad-(\theta_{\hat{A}}(t)-\theta_{A}(t))F(\mathbf{x}^{*}\vee\mathbf{1}_{A})$

Similar as Eq.(27) and Eq.(28), we can simplify
$r(\mathbf{x}(t))=\frac{\theta_{\hat{A}}(t)-\theta_{A}(t)}{1-\theta_{A}(t)}+1-\pi_{A}(t)$
and $h(t)=\int_{0}^{t}g_{A}(t)-g_{\hat{A}}(t)dt+g_{A}(t)-g_{A}(0)$. Therefore,
we have a simplified variation problem as follows:

$\displaystyle\max$
$\displaystyle\quad\cfrac{\int_{0}^{1}g_{A}(q)dq}{e+g_{A}(1)-1+\int_{0}^{1}g_{A}(q)-1dq}=1-\cfrac{1}{1+\frac{\int_{0}^{1}g_{A}(q)dq}{e+g_{A}(1)-2}}$
(32) s.t. $\displaystyle e^{-\int_{0}^{t}\pi_{A}(s)ds}\geq
e^{-t},g_{A}(t)=e^{t-\int_{0}^{t}\pi_{A}(s)ds}$
$\displaystyle\int_{0}^{1}\cfrac{\left(1-e^{-t}-\theta_{A}(t)\right)}{(1-\theta_{A}(t))}\leq\int_{0}^{1}(1-\pi_{A}(t))dt$
$\displaystyle\pi_{A}(t)\in[0,1]$

It implies that we should make $\int_{0}^{1}g_{A}(q)dq$ as large as possible
and $g_{A}(1)$ as small as possible. In other words, we hope that $g_{A}(t)$
is as large as possible for all $t\in[0,1)$ but $g_{A}(1)$ is as small as
possible. Therefore, it represents that there is a $\theta\in[0,1]$ such that
$g_{A}(t)$ has the following form, which uniquely decides the form of
$\pi_{A}(t)$ as follows:

$g_{A}(t)=e^{t-\int_{0}^{t}\pi_{A}(s)ds}=\begin{cases}e^{t}&t\in[0,\theta]\\\
e^{\theta}&t\in(\theta,1]\end{cases}\Rightarrow\pi_{A}(t)=\begin{cases}0&t\in[0,\theta]\\\
1&t\in(\theta,1]\end{cases}$ (33)

Table 4: Parameter functions in the Lyapunov function |  $a(t)$ |  $h(t)$ |  $d(t)$ |  $p(\mathbf{x}(t))$ |  $q(\mathbf{x}(t))$ |  $r(\mathbf{x}(t))$
---|---|---|---|---|---|---
$t\in[0,\theta]$ |  $e^{t}$ |  $2e^{t}-t$ |  $e^{t}$ |  $1$ |  $1$ |  $2-e^{-t}$
$t\in(\theta,1]$ |  $e^{t}$ |  $e^{\theta}\cdot(t+2-\theta)-t$ |  $e^{\theta}\cdot(t+1-\theta)$ |  $e^{t-\theta}$ |  $e^{t-\theta}$ |  $1-e^{-\theta}$

It is easy to verify
$\int_{0}^{1}\frac{\left(1-e^{-t}-\theta_{A}(t)\right)}{(1-\theta_{A}(t))}\leq\int_{0}^{1}(1-\pi_{A}(t))dt$.
Then, we obtain the following parametric coefficient functions used in the
Lyapunov framework (Eq.(20)) in Tab.4. Therefore, we can reduce the variation
problem to a univariate optimization problem:

$\max_{\theta\in[0,1]}\cfrac{(2-\theta)\cdot
e^{\theta}-1}{e+3e^{\theta}-3-\theta e^{\theta}}$ (34)

Solving the above maximization problem, we have $\theta\approx 0.372$,
$p\approx 0.77$, and the approximation ratio is at least $0.385$. Therefore,
the Lyapunov framework recovers the _aided measured continuous greedy
algorithm_ in Buchbinder and Feldman (2019) and extended it from the
multilinear extension of submodular set functions to general DR-submodular
functions. Note that the optimal $\pi_{A}(t)$ and $\pi_{\hat{A}}(t)$ from the
variation problem agree with the ones used in Buchbinder and Feldman (2019),
showing that their choice is optimal under the form of the lower bound in
Lemma 14 and the assumption that components in $A$ are the same, and
components in $\hat{A}$ are the same.

Algorithm 2 Discretized Algorithm 1

Input: $F$: objective function, $\mathcal{P}$: feasible domain,
$\theta\in[0,1]$: parameter, $\varepsilon$: convergence rate, $D$: diameter of
the feasible domain, $L$: constant of $L$-smooth for the objective function.
Output: the solution $\mathbf{x}(1)$ with probability $1-p$ and the solution
$\mathbf{y}$ with probability $p$

1: $\mathbf{y}\leftarrow$ Frank-Wolfe with adaptive step sizes
$(F,\mathcal{P})$

2: $A$ is a random subset of $[n]$. For all $i\in[n]$, $i\in A$ with
probability of $y_{i}$ independently. /* Frank-Wolfe Variant Stage */

3: Initialize $\mathbf{x}(0)=\mathbf{0}$, $t_{0}=0$,
$N_{1}=O\left(\frac{\theta DL}{\varepsilon}\right)$,
$N_{2}=O\left(\frac{(1-\theta)DL}{\varepsilon}\right)$.

4: for $j=0$ to $N_{1}+N_{2}-1$ do

5: if $j\leq N_{1}-1$ then

6: $\mathbf{v}(t_{j})=\arg\max_{\mathbf{v}\in\mathcal{P}_{[n]\setminus
A},\mathbf{v}\leq\mathbf{1}-\mathbf{x}(t_{j})}\langle\nabla
F(\mathbf{x}(t_{j})),\mathbf{v}\rangle$

7:
$\mathbf{x}(t_{j+1})=\mathbf{x}(t_{j})+(1-e^{\frac{-1}{N_{1}+N_{2}}})\mathbf{v}(t_{j})$

8: else

9:
$\mathbf{v}(t_{j})=\arg\max_{\mathbf{v}\in\mathcal{P},\mathbf{v}\leq\mathbf{1}-\mathbf{x}(t_{j})}\langle\nabla
F(\mathbf{x}(t_{j})),\mathbf{v}\rangle$

10:
$\mathbf{x}(t_{j+1})=\mathbf{x}(t_{j})+\frac{1}{(N_{1}+N_{2})e^{\frac{1}{N_{1}+N_{2}}}}\mathbf{v}(t_{j})$

11: end if

12: end for

###  4.3 Discretization via the Lyapunouv Function

In this subsection, we construct a discrete-time implementation of the above
continuous-time algorithm that keeps the same approximation ratio with
polynomial-time oracle complexity by following the framework proposed in Du
(2022b). Based on the Lyapunov function in Subsection 4.1, we first introduce
the discrete version of the Lyapunov function, namely the potential function.
From the potential function, the discretized implementation of Algorithm 1 is
naturally obtained.

###### Definition 17

(Du (2022a)) The potential function associated with a continuous-time
algorithm $\mathbf{x}(t)$ is as follows:

$E(\mathbf{x}(t_{j}))=a(t_{j})F(\mathbf{x}(t_{j}))+h(t_{j})F(\mathbf{y})-d(t_{j})F(\mathbf{x}^{*})$
(35)

And the upper bound of the optimal solution $F(\mathbf{x}^{*})$ is as follows:

$F(\mathbf{x}^{*})\leq
p(\mathbf{x}(t_{j}))F(\mathbf{x}(t))+q(\mathbf{x}(t_{j}))\langle\nabla
F(\mathbf{x}(t_{j})),v(\mathbf{x}(t_{j}))\rangle+r(\mathbf{x}(t_{j}))F(\mathbf{y})$
(36)

where $a(t_{j})$, $h(t_{j})$, $d(t_{j})$ are non-negative, non-decreasing
sequences and $p(\mathbf{x}(t_{j}))$, $q(\mathbf{x}(t_{j})$,
$r(\mathbf{x}(t_{j}))$ are non-negative sequences.

Similar as Subsection 4.1, if $E(\mathbf{x}(t_{j}))$ is a non-decreasing
sequence, i.e., $E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))\geq 0$, it
implies
$E(\mathbf{x}(t_{N}))-E(\mathbf{x}(t_{0}))=\sum_{j=0}^{N-1}E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))\geq
0$, where $N$ is the number of iterations. However, there are some errors in
the process of discretization. The first error arises from the continuous
algorithm to the discrete algorithm, which is bounded by $L$-smooth, i.e.,
$F(\mathbf{x}(t_{j+1}))-F(\mathbf{x}(t_{j}))\geq\langle\nabla
F(\mathbf{x}(t_{j})),\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})\rangle-\frac{L}{2}\left\|\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})\right\|^{2}$.
The second error comes from the differential equation by using the finite
difference to replace the derivative. Therefore, we introduce some error
measures that implies $E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))\geq-
Err_{1}(t_{j})F(\mathbf{x}(t_{j}))-Err_{2}(t_{j})F(\mathbf{y})-Err_{3}(t_{j})$.
If $Err_{1}(t_{j})$ and $Err_{2}(t_{j})$ are non-positive, it means that we
just consider the error comes from the $L$-smooth, i.e., $Err_{3}(t_{j})$. If
the solution $\mathbf{x}(t_{j})$ in each iteration is feasible and
$Err_{1}(t_{j})\geq 0$, we can substitute $F(\mathbf{x}(t_{j}))$ by
$F(\mathbf{x}^{*})$. Hence, the approximation ratio has the following closed-
form, $Err_{1}^{+}(t_{j})=\max\\{Err_{1}(t_{j}),0\\}$, similarly
$Err_{2}^{+}(t_{j})$.

$\displaystyle\cfrac{a(t_{N})}{a(t_{N})+h(t_{N})-h(t_{0})+\sum_{j=0}^{N-1}Err_{2}^{+}(t_{j})}F(\mathbf{x}(t_{N}))+\cfrac{h(t_{N})-h(t_{0})+\sum_{j=0}^{N-1}Err_{2}^{+}(t_{j})}{a(t_{N})+h(t_{N})-h(t_{0})+\sum_{j=0}^{N-1}Err_{2}^{+}(t_{j})}F(\mathbf{y})$
(37)
$\displaystyle\quad\geq\cfrac{d(t_{N})-d(t_{0})-\sum_{j=0}^{N-1}Err_{1}^{+}(t_{j})}{a(t_{N})+h(t_{N})-h(t_{0})+\sum_{j=0}^{N-1}Err_{2}^{+}(t_{j})}F(\mathbf{x}^{*})-\cfrac{\sum_{j=0}^{N-1}Err_{3}(t_{j})}{a(t_{N})+h(t_{N})-h(t_{0})+\sum_{j=0}^{N-1}Err_{2}^{+}(t_{j})}$

To achieve our target, plugging the discrete upper bound of
$F(\mathbf{x}^{*})$ into $E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))$, we
have the lower bound of $E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))$. In
light of the lower bound, it induces a sufficient condition to guarantee the
non-decreasing $E(\mathbf{x}(t_{j}))$ with some errors.

$\begin{array}[]{c}\begin{aligned}
E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))&=a(t_{j+1})[F(\mathbf{x}(t_{j+1}))-F(\mathbf{x}(t_{j}))]+[a(t_{j+1})-a(t_{j})]F(\mathbf{x}(t_{j}))\\\
&\quad+[h(t_{j+1})-h(t_{j})]F(\mathbf{y})-[d(t_{j+1})-d(t_{j})]F(\mathbf{x}^{*})\\\
&\geq\langle\nabla
F(\mathbf{x}(t_{j})),a(t_{j+1})[\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})]-\frac{a(t_{j+1})L}{2}\left\|\mathbf{x}(t_{j+1})-\mathbf{x}(t)_{j}\right\|^{2}\\\
&\quad-[d(t_{j+1})-d(t_{j})]q(\mathbf{x}(t_{j}))v(\mathbf{x}(t_{j}))\rangle\\\
&\quad+[a(t_{j+1})-a(t_{j})-[d(t_{j+1})-d(t_{j})]p(\mathbf{x}(t_{j}))]F(\mathbf{x}(t_{j}))\\\
&\quad+[h(t_{j+1})-h(t_{j})-[d(t_{j+1})-d(t_{j})]r(\mathbf{x}(t_{j}))]F(\mathbf{y})\\\
&\geq-
Err_{1}(t_{j})F(\mathbf{x}(t_{j}))-Err_{2}(t_{j})F(\mathbf{y})-Err_{3}(t_{j})\end{aligned}\\\
\bigg{\Downarrow}\\\
\begin{cases}a(t_{j+1})-a(t_{j})-[d(t_{j+1})-d(t_{j})]p(\mathbf{x}(t_{j}))&=-Err_{1}(t_{j})\\\
h(t_{j+1})-h(t_{j})-[d(t_{j+1})-d(t_{j})]r(\mathbf{x}(t_{j}))&=-Err_{2}(t_{j})\\\
\cfrac{a(t_{j+1})L}{2}\left\|\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})\right\|^{2}&=Err_{3}(t_{j})\\\
\cfrac{[d(t_{j+1})-d(t_{j})]q(\mathbf{x}(t_{j}))v(\mathbf{x}(t_{j}))}{a(t_{j+1})}&=\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})\end{cases}\end{array}$
(38)

Note that $Err_{3}(t_{j})$ is non-negative, which implies that the error
caused by the discrete algorithm is unavoidable. If there are some special
sequences, which ensure that $Err_{1}(t_{j})$ or $Err_{2}(t_{j})$ is non-
positive, we can ignore $F(\mathbf{x}(t_{j}))$ or $F(\mathbf{y})$,
accordingly. Therefore, we construct a large-scale numerical optimization
problem to maximize the approximation ratio, whose decision variables are the
sequence $a(t_{j})$, $h(t_{j})$, $d(t_{j})$, and $v(\mathbf{x}(t_{j}))$.

$\displaystyle\max$
$\displaystyle\left\\{\cfrac{d(t_{N})-d(t_{0})-\sum_{j=0}^{N-1}Err_{1}^{+}(t_{j})}{a(t_{N})+h(t_{N})-h(t_{0})+\sum_{j=0}^{N-1}Err_{2}^{+}(t_{j})},\cfrac{-\sum_{j=0}^{N-1}Err_{3}(t_{j})}{a(t_{N})+h(t_{N})-h(t_{0})+\sum_{j=0}^{N-1}Err_{2}^{+}(t_{j})}\right\\}$
(39) s.t. $\displaystyle a(t_{j}),b(t_{j}),c(t_{j}),d(t_{j})\text{ satisfies
Eq.(\ref{discrete lower bound of E})}$

In addition to solve the above optimization problem, we can also identify
sequence $a(t_{j})$, $h(t_{j})$, $d(t_{j})$ by using parameter functions in
the Lyapunov function. It implies that the objective is to determine the
sequence of $t_{j}$. If we choose a proper sequence $t_{j}$ such that
$\sum_{j=0}^{N-1}Err_{1}(t_{j})$, $\sum_{j=0}^{N-1}Err_{2}(t_{j})$, and
$\sum_{j=0}^{N-1}\frac{a(t_{j+1})L}{2a_{t_{N}}}\left\|\mathbf{x}(t_{j+1})-\mathbf{x}(t)_{j}\right\|^{2}$
are small enough, the approximation ratio of the discrete implementation has a
small loss on the approximation ratio of the Lyapunov function. Based on
Tab.4, we calculate errors that comes from the differential equation.

$\displaystyle Err_{1}(t_{j})$
$\displaystyle=\begin{cases}0&t_{j}\leq\theta\\\
e^{t_{j}}(1+t_{j+1}-t_{j})-e^{t_{j+1}}\leq 0&t_{j}>\theta\end{cases}$ (40)
$\displaystyle Err_{2}(t_{j})$
$\displaystyle=\begin{cases}1+t_{j+1}-t_{j}-e^{t_{j+1}-t_{j}}\leq
0&t_{j}\leq\theta\\\ 0&t_{j}>\theta\end{cases}$

where inequalities are due to $e^{t_{j+1}-t_{j}}\geq 1+t_{j+1}-t_{j}$. It
implies that errors of differential equations are negligible, that is, we can
release $F(\mathbf{x}(t_{j}))$ and $F(\mathbf{y})$ in
$E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))$. In other words,
$E(\mathbf{x}(t_{j+1}))-E(\mathbf{x}(t_{j}))\geq-\frac{a(t_{j+1})L}{2}\left\|\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})\right\|^{2}$.
Furthermore, we have $t_{N}=1$ and $t_{0}=0$. Therefore, the approximation
ratio of the discrete implementation of the continuous algorithm
$\mathbf{x}(t)$ is as follows:

$\displaystyle\cfrac{e}{e+e^{\theta}\cdot(3-\theta)-3}F(\mathbf{x}(t_{N}))+\cfrac{e^{\theta}\cdot(3-\theta)-3}{e+e^{\theta}\cdot(3-\theta)-3}F(\mathbf{y})$
(41)
$\displaystyle\quad\geq\cfrac{e^{\theta}\cdot(2-\theta)-1}{e+e^{\theta}\cdot(3-\theta)-3}F(\mathbf{x}^{*})-\sum_{j=0}^{N-1}\cfrac{a(t_{j+1})L}{2(e+e^{\theta}\cdot(3-\theta)-3)}\left\|\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})\right\|^{2}$

Note that if we can restrict the last term small enough in the above
inequality, it implies that the discrete implementation is a $0.385$
approximation algorithm to maximize general continuous DR-submodular functions
subject to down-closed convex constraints. Additionally, the last term is
often called convergence rate. Next, we analyze the complexity of the discrete
implementation of the Algorithm 1. For convenience, let $N_{1}$ be the number
of iterations in $t\in[0,\theta]$, $N_{2}$ be the number of iterations in
$t\in(\theta,1]$, $D$ be the diameter of the feasible domain, i.e.,
$D=\max_{\mathbf{x},\mathbf{y}\in\mathcal{P}}\left\|\mathbf{x}-\mathbf{y}\right\|^{2}$,
and $t_{j+1}-t_{j}=\frac{1}{N_{1}+N_{2}}=\frac{1}{N}$.

$\displaystyle\sum_{j=0}^{N-1}\cfrac{a(t_{j+1})L}{2(e+e^{\theta}\cdot(3-\theta)-3)}\left\|\mathbf{x}(t_{j+1})-\mathbf{x}(t_{j})\right\|^{2}=\sum_{j=0}^{N-1}\cfrac{[d(t_{j+1})-d(t_{j})]^{2}q(t_{j})^{2}L}{2a(t_{t+1})(e+e^{\theta}\cdot(3-\theta)-3)}\left\|v(\mathbf{x}(t_{j})\right\|^{2}$
(42)
$\displaystyle\leq\sum_{j=0}^{N_{1}-1}\cfrac{[e^{t_{j+1}}-e^{t_{j}}]^{2}LD}{2e^{t_{j+1}}(e+e^{\theta}\cdot(3-\theta)-3)}+\sum_{j=N_{1}-1}^{N-1}\cfrac{e^{2t_{j}}(t_{j+1}-t_{j})^{2}LD}{2e^{t_{j+1}}(e+e^{\theta}\cdot(3-\theta)-3)}$
$\displaystyle=\cfrac{DL}{2(e+e^{\theta}\cdot(3-\theta)-3)}\cdot\left[(1-e^{\frac{-1}{N_{1}+N_{2}}})^{2}\cdot\cfrac{e^{\frac{1}{N_{1}+N_{2}}}(1-e^{\theta})}{1-e^{\frac{1}{N_{1}+N_{2}}}}+\cfrac{e^{\theta}-e}{(N_{1}+N_{2})^{2}e^{\frac{1}{N_{1}+N_{2}}}(1-e^{\frac{1}{N_{1}+N_{2}}})}\right]$
$\displaystyle\leq\cfrac{DL}{2(e+e^{\theta}\cdot(3-\theta)-3)}\cdot\left[\cfrac{(e^{\theta}-1)(N_{1}+N_{2}+1)}{(N_{1}+N_{2})^{2}}+\cfrac{e-e^{\theta}}{(N_{1}+N_{2})^{2}\frac{1+N_{1}+N_{2}}{N_{1}+N_{2}}\frac{1}{N_{1}+N_{2}}}\right]$
$\displaystyle=O\left(\cfrac{DL}{N_{1}+N_{2}}\right)=\varepsilon$

The first inequality comes from the definition of $D$, i.e.,
$\left\|v(\mathbf{x}(t_{j})\right\|^{2}\leq D$. The second equality is due to
$e^{t_{0}}=1$, $e^{t_{N_{1}}}=e^{\theta}$, $e^{t_{N}}=e$, and
$t_{j+1}-t_{j}=\frac{1}{N_{1}+N_{2}}$. The second inequality comes from
$1+x\leq e^{x}$. Therefore, we have
$N_{1}+N_{2}=O\left(\frac{DL}{\varepsilon}\right)$. In addition, we have
$\frac{N_{1}}{N_{1}+N_{2}}=\theta$. It implies $N_{1}=O\left(\frac{\theta
DL}{\varepsilon}\right)$ and
$N_{2}=O\left(\frac{(1-\theta)DL}{\varepsilon}\right)$. Therefore, we have the
following conclusion.

###### Theorem 18

Algorithm 2 outputs a solution that is at least $0.385$ times of the optimal
value for problem (1) with a gap smaller than $\varepsilon$ with at most
$O\left(\frac{DL}{\varepsilon}\right)$ iterations, where $D$ is the diameter
of the feasible domain and $L$ is the L-smooth constant of the DR-submodular
function $F$.

Note that a rephrased version of Lemma 2.3.7 in Feldman (2013) implies that
$O(DL)=O\left(n^{3}\right)F(\mathbf{x}^{*})$ for submodular set functions.
Therefore, Algorithm 2 is a $0.385-O(n^{-1})$ approximation algorithm for
problem (1) with $O\left(\frac{DL}{\varepsilon}\right)=O\left(n^{4}\right)$
iterations, i.e., $N_{1}=O\left(\theta n^{4}\right)$ and
$N_{2}=O\left((1-\theta)n^{4}\right)$. In addition, it is easy to verify that
approximating $e^{t_{j}}$ with $\left(1-\frac{1}{N_{1}+N_{2}}\right)^{-j}$
leads to step size $\frac{1}{N_{1}+N_{2}}$ and
$\left(1-\frac{1}{N_{1}+N_{2}}\right)\frac{1}{N_{1}+N_{2}}$, which mathces the
results in Buchbinder and Feldman (2019).

###  4.4 Discussions

In general, the partition $(A,\hat{A})$ in Lemma 14 is an adaptive partition,
which can change over time $t$ subject to
$\theta_{A}(t)\leq\theta_{\hat{A}}(t)$. Especially, the partition
$(A,\hat{A})$ can also be pre-determined before starting the continuous
algorithm $\mathbf{x}(t)$. Therefore, we should guarantee the following
inequality over each time $t$ for the pre-determined partition.

$\int_{0}^{t}\dot{\mathbf{x}}_{A}(t)dt\leq\int_{0}^{t}\dot{\mathbf{x}}_{\hat{A}}(t)dt$

Although the above analysis proves the optimality of the algorithm to some
extent under a partition that is independent of time, whether there are
suitable time-dependent partitions to lead to a better approximation is still
an open question.

Claim 1 illustrates that the worst stationary point without any approximation
ratio is probably close to the boundary of the feasible domain in some
dimensions. This phenomenon inspires a natural idea to obtain a potentially
improved solution $\mathbf{x}(t)$, i.e.,
$\theta_{A}(t)\leq\theta_{\hat{A}}(t)$, where $A$ is a dimension set which are
the dimensions near the boundary of the feasible domain in $\mathbf{y}$.
Therefore, we choose the pre-determined partition $A,\hat{A}$ depending on the
stationary point $\mathbf{y}$. However, there is another important remaining
question, whether there are better choices for $\mathbf{y}$ except stationary
points. If yes, it potentially improves the $0.385$ approximation algorithm
for the problem (1).

##  5 Numerical Experiments

In this section, we test five different algorithms on some applications
mentioned in Section 1. Two of them serve as baseline algorithms to contrast
algorithms in our work.

  * •

Baseline algorithms: Two-Phase Frank-Wolfe and Frank-Wolfe Variant have been
proposed by Bian et al. (2017a) to maximize continuous DR-submodular functions
subject to down-closed convex constraints. The first one is a $1/4$
approximation algorithm, which finds a stationary point $\mathbf{x}$ in the
feasible domain $\mathcal{P}$ and a stationary point $\mathbf{y}$ in the
feasible domain $\mathcal{P}\wedge(\mathbf{u}-\mathbf{x})$ and returns the
best of them. The second one is an $1/e$ approximation algorithm, which
returns a solution $\mathbf{x}(1)$ in feasible domain $\mathcal{P}$ where
$x_{i}(1)-x_{i}(0)\leq(1-e^{-1})(u_{i}-l_{i})$ for all $i\in N$.

  * •

Algorithms in this work: we adopt Frank-Wolfe to return a stationary point,
which is proved in Subsection 3.1 by a concrete example that the stationary
point may be arbitrarily bad. In addition, we adopt Frank-Wolfe to return a
stationary point in the reduce feasible domain, namely Reduced Frank-Wolfe,
which has the $0.309$ approximation guarantee. Aided Frank-Wolfe Variant is a
$0.385$ approximation algorithm analyzed in Section 4. Although it returns the
stationary point $\mathbf{y}$ with probability $0.23$ and the solution
$\mathbf{x}(1)$ returned by Frank-Wolfe Variant stage with probability $0.77$,
we make a slight change, which returns the best one in $\mathbf{x}(1)$ and
$\mathbf{y}$. It does not cause any loss to the approximation ratio.

Because both Two-Phase Frank-Wolfe and Aided Frank-Wolfe Variant need to find
a stationary point in the feasible domain $\mathcal{P}$, in the following
numerical experiments, we adopt the stationary point returned by Frank-Wolfe
as their stationary points. Additionally, in the following tables and figures,
without causing ambiguity, Two-Phase Frank-Wolfe-2 represents the second
stationary point returned by Two-Phase Frank-Wolfe, and Aided Frank-Wolfe
Variant-2 represents the solution returned by Frank-Wolfe variant stage in
Aided Frank-Wolfe Variant. In other words, the solution returned by Two-Phase
Frank-Wolfe is the best one of Frank-Wolfe and Two-Phase Frank-Wolfe-2; the
solution returned by Aided Frank-Wolfe Variant is the best one of the Frank-
Wolfe and Aided Frank-Wolfe Variant-2. In our experiments, the number of
iterations is $N=100$. Because there is randomness in all examples, the number
of repeated trails is $T=10$.

Table 5: Average function value with standard deviation in NQP |  Algorithm |  $m=\lfloor 0.1n\rfloor$ |  $m=\lfloor 0.3n\rfloor$ |  $m=\lfloor 0.5n\rfloor$
---|---|---|---|---
$n=100$ |  Frank-Wolfe |  $843.2299\pm 5.4480$ |  $836.0062\pm 3.3833$ |  $759.4658\pm 9.2937$
Two-Phase Frank-Wolfe-2 |  $837.0060\pm 4.6215$ |  $833.4710\pm 3.5045$ |  $759.2584\pm 8.7699$
Reduced Frank-Wolfe |  $836.5517\pm 5.2064$ |  $833.1673\pm 3.4484$ |  $759.3279\pm 8.9670$
Frank-Wolfe Variant |  $840.1015\pm 5.1331$ |  $834.7916\pm 3.6254$ |  $759.4359\pm 9.2176$
Aided Frank-Wolfe Variant-2 |  $838.0243\pm 4.9410$ |  $833.6677\pm 3.6423$ |  $759.1773\pm 9.0697$
$n=500$ |  Frank-Wolfe |  $20806.15\pm 20.6679$ |  $20699.98\pm 23.9101$ |  $18818.92\pm 35.9268$
Two-Phase Frank-Wolfe-2 |  $20759.12\pm 20.2773$ |  $20675.61\pm 21.4277$ |  $18815.96\pm 33.5124$
Reduced Frank-Wolfe |  $20750.54\pm 19.6014$ |  $20674.48\pm 21.4754$ |  $18816.51\pm 34.1660$
Frank-Wolfe Variant |  $20783.49\pm 18.9631$ |  $20689.62\pm 21.6035$ |  $18817.98\pm 34.9901$
Aided Frank-Wolfe Variant-2 |  $20760.85\pm 19.2939$ |  $20672.05\pm 21.0048$ |  $18815.81\pm 33.9950$
$n=1000$ |  Frank-Wolfe |  $82979.21\pm 60.7779$ |  $82762.57\pm 69.0859$ |  $75125.82\pm 65.5320$
Two-Phase Frank-Wolfe-2 |  $82857.82\pm 72.6572$ |  $82694.05\pm 63.6619$ |  $75125.25\pm 64.8827$
Reduced Frank-Wolfe |  $82833.04\pm 67.5125$ |  $82690.23\pm 64.5268$ |  $75125.12\pm 64.8164$
Frank-Wolfe Variant |  $82921.56\pm 69.3485$ |  $82736.38\pm 66.0542$ |  $75125.74\pm 65.4271$
Aided Frank-Wolfe Variant-2 |  $82850.28\pm 69.7793$ |  $82678.13\pm 62.3230$ |  $75123.11\pm 64.1905$

###  5.1 Non-monotone Quadratic Programming

Our first instance is the synthetic function of non-monotone quadratic
programming. The objective function is a non-monotone DR-submodular function
$F(\mathbf{x})=\frac{1}{2}\mathbf{x}^{T}\mathbf{H}\mathbf{x}+\mathbf{h}^{T}\mathbf{x}+c$
and the constraints are linear inequalities
$\mathcal{P}=\\{\mathbf{x}\in[\mathbf{0},\mathbf{1}]|\mathbf{A}\mathbf{x}\leq\mathbf{b},\mathbf{A}\in\mathbb{R}^{m\times
n}_{+},\mathbf{b}\in\mathbb{R}^{m}_{+}\\}$. We randomly generate the matrix
$\mathbf{H}$, whose entries are uniformly distributed in $[-1,0]$, and the
vector $\mathbf{h}$, whose components are uniformly distributed in $[0,1]$. To
ensure that $F(\mathbf{x})$ is non-negative, we choose $c$ to be a large
enough number. As for constraints, we randomly generate the matrix
$\mathbf{A}$, whose entries are uniformly distributed in $[0,1]$, and the
vector $\mathbf{b}$, whose components are uniformly distributed in
$[0,0.05n]$, where we set $m=\lfloor 0.1n\rfloor,\lfloor 0.3n\rfloor,\lfloor
0.5n\rfloor$, respectively; and $n=100,500,1000$, respectively.

Tab.5 shows the averages and standard deviations of the objective value over
$10$ repeated trails. Although the stationary point is probably arbitrarily
bad in the worst cases, it is the best solution in our numerical experiments.
In other words, Two-Phase Frank-Wolfe and Aided Frank-Wolfe Variant have the
best performance in Two-Phase Frank-Wolfe, Aided Frank-Wolfe Variant, Reduced
Frank-Wolfe, and Frank-Wolfe Variant. This is consistent with the results in
Bian et al. (2017a), who illustrate that the Two-Phase Frank-Wolfe performs
better than Frank-Wolfe Variant. However, our results more clearly show that
Two-Phase Frank-Wolfe has good performances because the stationary point is
good enough. In other words, Two-Phase Frank-Wolfe-2 and Aided Frank-Wolfe
Variant-2 do not improve the quality of our solution in our experiments. In
addition, Reduced Frank-Wolfe may only have theoretical value. Despite the
approximation ratio of Reduced Frank-Wolfe being larger than that of Two-Phase
Frank-Wolfe, the actual performance of the latter is better than that of the
former.

Table 6: Average function value with standard deviation in regular coverage |  Algorithm |  $m=\lfloor 0.1(2k+1)\rfloor$ |  $m=\lfloor 0.3(2k+1)\rfloor$ |  $m=\lfloor 0.5(2k+1)\rfloor$
---|---|---|---|---
$k=10$ |  Frank-Wolfe |  $9.9997\pm 0.0001$ |  $9.9998\pm 6.15e-05$ |  $9.9999\pm 4.13e-05$
Two-Phase Frank-Wolfe-2 |  $1.0000\pm 4.68e-09$ |  $0.9999\pm 1.41e-05$ |  $0.9895\pm 0.0285$
Reduce Frank-Wolfe |  $3.8851\pm 0.0037$ |  $3.8945\pm 0.0095$ |  $3.9011\pm 0.0087$
Frank-Wolfe Variant |  $6.0734\pm 0.0518$ |  $6.1365\pm 0.0291$ |  $6.1546\pm 0.0214$
Aided Frank-Wolfe Variant-2 |  $4.3887\pm 0.0559$ |  $4.4674\pm 0.0259$ |  $4.4884\pm 0.0178$
$k=100$ |  Frank-Wolfe |  $99.9957\pm 7.64e-05$ |  $99.9961\pm 4.09e-05$ |  $99.9963\pm 5.22e-05$
Two-Phase Frank-Wolfe-2 |  $1.0000\pm 2.15e-14$ |  $1.0000\pm 2.43e-14$ |  $1.0000\pm 1.21e-14$
Reduce Frank-Wolfe |  $38.2350\pm 0.0043$ |  $38.2389\pm 0.0006$ |  $38.2431\pm 0.0021$
Frank-Wolfe Variant |  $62.2366\pm 0.0257$ |  $62.3166\pm 0.0134$ |  $62.2949\pm 0.0151$
Aided Frank-Wolfe Variant-2 |  $42.5358\pm 0.0565$ |  $42.8831\pm 0.0324$ |  $43.0078\pm 0.0380$
$k=500$ |  Frank-Wolfe |  $499.9791\pm 8.35e-05$ |  $499.9794\pm 6.37e-05$ |  $499.9803\pm 7.86e-05$
Two-Phase Frank-Wolfe-2 |  $1.0000\pm 6.14e-14$ |  $1.0000\pm 7.1e-14$ |  $1.0000\pm 4.63e-14$
Reduced Frank-Wolfe |  $190.5986\pm 0.0068$ |  $190.6434\pm 0.0049$ |  $190.6910\pm 0.0087$
Frank-Wolfe Variant |  $314.6732\pm 0.0105$ |  $314.7026\pm 0.0093$ |  $314.7211\pm 0.0106$
Aided Frank-Wolfe Variant-2 |  $218.0404\pm 0.0510$ |  $218.1358\pm 0.0237$ |  $218.1503\pm 0.0346$

###  5.2 Regular Coverage Maximization

Our second instance is the multilinear extension of the regular coverage
function in Example 1, where the constraints are linear inequalities
$\mathcal{P}=\\{\mathbf{x}\in[\mathbf{0},\mathbf{1}]|\mathbf{A}\mathbf{x}\leq\mathbf{b},\mathbf{A}\in\mathbb{R}^{m\times(2k+1)}_{+},\mathbf{b}\in\mathbb{R}^{2k+1}_{+}\\}$,
$k=10,100,500$, and $m=\lfloor 0.1(2k+1)\rfloor,\lfloor
0.3(2k+1)\rfloor,\lfloor 0.5(2k+1)\rfloor$, respectively. Each entry in the
matrix $\mathbf{A}$ is uniformly distributed in $[0,1]$. Each component in the
vector $\mathbf{b}$ is uniformly distributed in $[0,0.05(2k+1)]$.

Tab.6 shows that the stationary point returned by Frank-Wolfe is the best
among all algorithms for this problem; that is, Two-Phase Frank-Wolfe and
Aided Frank-Wolfe Variant have the best performance. In addition, Tab.6 is
consist with our theoretical analyses in Subsection 3.1. The Two-Phase Frank-
Wolfe-2 row in Tab.6 illustrates that Frank-Wolfe can indeed return a poor
solution in numerical experiments, which implies that Aided Frank-Wolfe
Variant potentially returns a better solution than Two-Phase Frank-Wolfe for
this problems. Similar to NQP, Reduced Frank-Wolfe seems to have only
theoretical values.

Table 7: Average function value with standard deviation in DPPs |  Algorithm |  $m=\lfloor 0.1n\rfloor$ |  $m=\lfloor 0.3n\rfloor$ |  $m=\lfloor 0.5n\rfloor$
---|---|---|---|---
$n=10$ |  Frank-Wolfe |  $0.8767\pm 0.5306$ |  $0.6857\pm 0.3032$ |  $0.4604\pm 0.1822$
Two-Phase Frank-Wolfe-2 |  $0.4678\pm 0.2265$ |  $0.5341\pm 0.1589$ |  $0.4499\pm 0.1799$
Reduced Frank-Wolfe |  $0.6342\pm 0.3337$ |  $0.6033\pm 0.2212$ |  $0.4468\pm 0.1809$
Frank-Wolfe Variant |  $0.7709\pm 0.4389$ |  $0.6473\pm 0.2624$ |  $0.4581\pm 0.1830$
Aided Frank-Wolfe Variant-2 |  $0.6795\pm 0.3778$ |  $0.6005\pm 0.2302$ |  $0.4327\pm 0.1754$
$n=100$ |  Frank-Wolfe |  $1.2722\pm 0.4443$ |  $4.2817\pm 0.6281$ |  $4.4901\pm 0.5403$
Two-Phase Frank-Wolfe-2 |  $1.0346\pm 0.3638$ |  $4.1647\pm 0.6557$ |  $4.4551\pm 0.5859$
Reduced Frank-Wolfe |  $1.1455\pm 0.3779$ |  $4.2070\pm 0.6327$ |  $4.4636\pm 0.5658$
Frank-Wolfe Variant |  $1.2216\pm 0.4090$ |  $4.2695\pm 0.6336$ |  $4.4838\pm 0.5475$
Aided Frank-Wolfe Variant-2 |  $1.1309\pm 0.3730$ |  $4.0572\pm 0.6179$ |  $4.3070\pm 0.5600$
$n=500$ |  Frank-Wolfe |  $2.3437\pm 0.8585$ |  $20.5876\pm 1.1112$ |  $19.4039\pm 1.0967$
Two-Phase Frank-Wolfe-2 |  $2.1179\pm 0.8734$ |  $20.5734\pm 1.1179$ |  $19.3901\pm 1.1071$
Reduced Frank-Wolfe |  $2.2202\pm 0.8642$ |  $20.5634\pm 1.1218$ |  $19.3834\pm 1.1049$
Frank-Wolfe Variant |  $2.2986\pm 0.8698$ |  $20.5818\pm 1.1126$ |  $19.3961\pm 1.0962$
Aided Frank-Wolfe Variant-2 |  $2.1657\pm 0.8352$ |  $19.8884\pm 1.1097$ |  $18.7706\pm 1.0875$

###  5.3 Determinantal Point Processes

The third instance is the softmax extension of determinantal point processes.
We randomly generate a diagonal matrix $\mathbf{D}$ whose $n$ eigenvalues are
uniformly distributed in $[-0.5,1.0]$ and take the power of $e$. Then, we
construct a positive semidefinite matrix by
$\mathbf{L}=\mathbf{V}\mathbf{D}\mathbf{V}^{T}$ where $\mathbf{V}$ is a random
unitary matrix. Similarly, the constraints are linear inequalities
$\mathcal{P}=\\{\mathbf{x}\in[\mathbf{0},\mathbf{1}]|\mathbf{A}\mathbf{x}\leq\mathbf{b},\mathbf{A}\in\mathbb{R}^{m\times
n}_{+},\mathbf{b}\in\mathbb{R}^{n}_{+}\\}$ where entries of the matrix
$\mathbf{A}$ are uniformly distributed in $[0,1]$, components of the vector
$\mathbf{b}$ are uniformly distributed in $[0,0.05n]$, $m=\lfloor
0.1n\rfloor,\lfloor 0.3n\rfloor,\lfloor 0.5n\rfloor$, and $n=10,n=100,n=500$,
respectively.

In Tab.7, the results also imply that the stationary point is a good enough
solution, that is, Two-Phase Frank-Wolfe and Aided Frank-Wolfe Variant perform
better than Reduced Frank-Wolfe and Frank-Wolfe Variant. The solution returned
by Aided Frank-Wolfe Variant-2 is better than the solution returned by Two-
Phase Frank-Wolfe-2 in small-scale problems. Similarly, there is the same
relationship between Aided Frank-Wolfe Variant-2 and Reduced Frank-Wolfe. This
phenomenon may be because the number of stationary points increases with the
scale of the problem but the number of poor stationary points increases slowly
with the scale of the problem. In other words, there is less chance of
obtaining a bad stationary point in large-scale problems.

###  5.4 Revenue/Profit Maximization

The last instance is the revenue/profit maximization problem in online social
networks. We perform our algorithms in three networks. One is the synthetic
network, which has $2708$ nodes and $5208$ edges. The remaining two networks
come from the Stanford Large Network Dataset Collection (Leskovec and Krevl
(2014)). The dataset of Facebook has $4039$ nodes and $88234$ edges and the
dataset of Twitter has $81306$ nodes and $1768149$ edges. We set the weight of
each edge $(u,v)$ uniformly distributed from $\\{0.1,0.01,0.001\\}$.
Specially, in Eq.(3), we adopt the same parameter functions as Bian et al.
(2017b), i.e., $R_{s}(\mathbf{x})=\sqrt{\sum_{t:x_{t}\neq 0}x_{t}w_{st}}$,
$\pi(x_{t})=w_{tt}x_{t}$, $\bar{R}_{t}(\mathbf{x})=-x_{t}$, where $w_{st}$ is
the weight of the edge $(s,t)$, $\alpha=\beta=10$, and $\gamma=0.5$. Because
the edge from node $u$ to itself is not included in the three networks, we set
$w_{tt}=0.1$ for each node $t$. In addition, we test our algorithms under two
constraints. One is the cardinality constraint, which is commonly known as the
profit maximization problem, i.e., $\sum_{i}x_{i}\leq b$. The other one is a
system of linear inequalities
$\mathcal{P}=\\{\mathbf{x}\in[\mathbf{0},\mathbf{1}]|\mathbf{A}\mathbf{x}\leq\mathbf{b},\mathbf{A}\in\mathbb{R}^{m\times
n}_{+},\mathbf{b}\in\mathbb{R}^{n}_{+}\\}$ where entries of the matrix
$\mathbf{A}$ are uniformly distributed in $[0,1]$ and $\mathbf{b}$ is $0.1n$,
$0.3n$, and $0.5n$ respectively.

Fig.1 is the average profit value under cardinality constraints. Fig.2 is the
average revenue value under a system of linear inequalities. They show that
the stationary point $\mathbf{x}$ in $\mathcal{P}$ and the stationary point
$\mathbf{y}$ in $\mathcal{P}\wedge(\mathbf{1}-\mathbf{x})$ perform better than
other solutions. This means Two-Phase Frank-Wolfe and Aided Frank-Wolfe
Variant have better practical performances than other algorithms. Because the
revenue/profit maximization problem in online social networks is usually a
large-scale problem, which has thousands or even millions of nodes, it
supports our conjecture that there is less chance for algorithms to return a
bad stationary point. In addition, Fig.1 and Fig.2 also illustrate that
Reduced Frank-Wolfe is not suitable for practical problems and hence only
interesting from a theoretical perspective.

Figure 1: Average function value with standard deviation in revenue
maximization under cardinality constraints. From left to right are Synthesis,
Facebook, and Twitter.

Figure 2: Average function value with standard deviation in revenue
maximization under a system of linear inequalities. From left to right are
Synthesis and Facebook.

##  6 Conclusion

We study the continuous non-monotone DR-submodular maximization problem
subject to down-closed convex constraints. Firstly, we illustrate that
stationary points can have an arbitrarily bad approximation ratio, a sharp
contrast to the monotone DR-submodular case, which always admits a constant
approximation Hassani et al. (2017). In particular, we extend the
0.309-approximation algorithm (Chekuri et al. (2014)) and the
$0.385$-approximation algorithm (Buchbinder and Feldman (2019)) to the
continuous domain via new analyses without using any properties of the
multilinear extension. The most important open question is to close the
approximation gap for this problem, where the best lower bound is $0.385$ in
continuous domains as shown in this paper and the best upper bound is $0.478$
as shown in Qi (2022). Our numerical experiments show that both the $0.385$
approximation algorithm and two-phase Frank-Wolfe have excellent practical
performances. However, the latter is only shown to be at least $1/4$ (Bian et
al. (2017b)). An interesting open question is whether the latter has a better
theoretical performance.

Acknowledgments and Disclosure of Funding

Donglei Du’s research is partially supported by NSERC grant (No.283106) and
NSFC grants (Nos. 11771386 and 11728104). Wenguo Yang’s research is partially
supported by NSFC grants (Nos. 12071459 and 11991022). Dachuan Xu’s research
is partially supported by NSFC grant (No. 12131003).

## References

  * Bach (2019) F. Bach.  Submodular functions: from discrete to continuous domains.  _Mathematical Programming_ , 175(3):419–459, 2019\.  doi: 10.1007/s10107-018-1248-6.
  * Bian et al. (2017a) A. Bian, K. Levy, A. Krause, and J. M. Buhmann.  Continuous dr-submodular maximization: Structure and algorithms.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017a.
  * Bian et al. (2017b) A. A. Bian, B. Mirzasoleiman, J. Buhmann, and A. Krause.  Guaranteed non-convex optimization: Submodular maximization over continuous domains.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54, pages 111–120, 2017b.
  * Bian et al. (2019) Y. Bian, J. Buhmann, and A. Krause.  Optimal continuous DR-submodular maximization and applications to provable mean field inference.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 644–653, 2019.
  * Bian et al. (2020) Y. Bian, J. M. Buhmann, and A. Krause.  Continuous submodular function maximization.  _CoRR_ , abs/2006.13474, 2020.  URL https://arxiv.org/abs/2006.13474.
  * Buchbinder and Feldman (2019) N. Buchbinder and M. Feldman.  Constrained submodular maximization via a nonsymmetric technique.  _Mathematics of Operations Research_ , 44(3):988–1005, 2019.
  * Buchbinder et al. (2015) N. Buchbinder, M. Feldman, J. SeffiNaor, and R. Schwartz.  A tight linear time (1/2)-approximation for unconstrained submodular maximization.  _SIAM Journal on Computing_ , 44(5):1384–1402, 2015.  doi: 10.1137/130929205.
  * Calinescu et al. (2011) G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák.  Maximizing a monotone submodular function subject to a matroid constraint.  _SIAM Journal on Computing_ , 40(6):1740–1766, 2011.  doi: 10.1137/080733991.
  * Chekuri et al. (2010) C. Chekuri, J. Vondrak, and R. Zenklusen.  Dependent randomized rounding via exchange properties of combinatorial structures.  In _2010 IEEE 51st Annual Symposium on Foundations of Computer Science_ , pages 575–584, 2010.  doi: 10.1109/FOCS.2010.60.
  * Chekuri et al. (2014) C. Chekuri, J. Vondrák, and R. Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  _SIAM Journal on Computing_ , 43(6):1831–1879, 2014.  doi: 10.1137/110839655.
  * Du (2022a) D. Du.  Submodularity and lattice: theory, algorithms and applications.  _Unpublished book (in preparation)_ , 2022a.
  * Du (2022b) D. Du.  Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization.  _arXiv preprint arXiv:2205.12442_ , 2022b.
  * Du et al. (2022) D. Du, Z. Liu, C. Wu, D. Xu, and Y. Zhou.  An improved approximation algorithm for maximizing a dr-submodular function over a convex set.  _arXiv preprint arXiv:2203.14740_ , 2022.
  * Ene and Nguyen (2016) A. Ene and H. L. Nguyen.  Constrained submodular maximization: Beyond 1/e.  In _2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 248–257, 2016.  doi: 10.1109/FOCS.2016.34.
  * Feldman (2013) M. Feldman.  _Maximization problems with submodular objective functions_.  PhD thesis, Technion - Israel Institute of Technology, Israel, 2013.
  * Feldman et al. (2011) M. Feldman, J. Naor, and R. Schwartz.  A unified continuous greedy algorithm for submodular maximization.  In _2011 IEEE 52nd Annual Symposium on Foundations of Computer Science_ , pages 570–579, 2011.  doi: 10.1109/FOCS.2011.46.
  * Fisher et al. (1978) M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey.  An analysis of approximations for maximizing submodular set functions-ii.  _Mathematical Programming_ , 8(1):73–87, 1978\.
  * Gillenwater et al. (2012) J. Gillenwater, A. Kulesza, and B. Taskar.  Near-optimal map inference for determinantal point processes.  In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * Golovin and Krause (2012) D. Golovin and A. Krause.  Adaptive submodularity: Theory and applications in active learning and stochastic optimization.  _Journal of Artificial Intelligence Research_ , 42(1):427–486, 2012.
  * Hassani et al. (2017) H. Hassani, M. Soltanolkotabi, and A. Karbasi.  Gradient methods for submodular maximization.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 5843–5853, 2017.
  * Ito and Fujimaki (2016) S. Ito and R. Fujimaki.  Large-scale price optimization via network flow.  In _Advances in Neural Information Processing Systems_ , volume 29, 2016.
  * Iwata et al. (2001) S. Iwata, L. Fleischer, and S. Fujishige.  A combinatorial strongly polynomial algorithm for minimizing submodular functions.  _Journal of the ACM_ , 48(4):761–777, 2001.  doi: 10.1145/502090.502096.
  * Kempe et al. (2003) D. Kempe, J. Kleinberg, and E. Tardos.  Maximizing the spread of influence through a social network.  In _Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’03, page 137–146, 2003.  doi: 10.1145/956750.956769.
  * Krause et al. (2008) A. Krause, A. Singh, and C. Guestrin.  Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies.  _Journal of Machine Learning Research_ , 9(3):235–284, 2008.
  * Kulesza and Taskar (2012) A. Kulesza and B. Taskar.  Determinantal point processes for machine learning.  _Foundations and Trends® in Machine Learning_ , 5(2–3):123–286, 2012.  ISSN 1935-8237.  doi: 10.1561/2200000044.
  * Lacoste-Julien (2016) S. Lacoste-Julien.  Convergence rate of frank-wolfe for non-convex objectives.  _arXiv preprint arXiv:1607.00345_ , 2016.
  * Leskovec and Krevl (2014) J. Leskovec and A. Krevl.  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data, June 2014.
  * Marinacci and Montrucchio (2005) M. Marinacci and L. Montrucchio.  Ultramodular functions.  _Mathematics of Operations Research_ , 30(2):311–332, 2005.
  * Mualem and Feldman (2023) L. Mualem and M. Feldman.  Resolving the approximability of offline and online non-monotone dr-submodular maximization over general convex sets.  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , volume 206, pages 2542–2564, 2023.
  * Nemhauser et al. (1978) G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher.  An analysis of approximations for maximizing submodular set functions-i.  _Mathematical Programming_ , 14(1):265–294, 1978\.
  * Niazadeh et al. (2020) R. Niazadeh, T. Roughgarden, and J. R. Wang.  Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization.  _The Journal of Machine Learning Research_ , 21(1):4937–4967, 2020.
  * Qi (2022) B. Qi.  On maximizing sums of non-monotone submodular and linear functions.  _arXiv preprint arXiv:2205.15874_ , 2022.
  * Skutella (2001) M. Skutella.  Convex quadratic and semidefinite programming relaxations in scheduling.  _J. ACM_ , 48(2):206–242, mar 2001.  doi: 10.1145/375827.375840.
  * Staib and Jegelka (2017) M. Staib and S. Jegelka.  Robust budget allocation via continuous submodular functions.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 3230–3240, 2017.
  * Sviridenko (2004) M. Sviridenko.  A note on maximizing a submodular set function subject to a knapsack constraint.  _Operations Research Letters_ , 32(1):41–43, 2004\.  doi: https://doi.org/10.1016/S0167-6377(03)00062-2.
  * Tang et al. (2018) J. Tang, X. Tang, and J. Yuan.  Profit maximization for viral marketing in online social networks: Algorithms and analysis.  _IEEE Transactions on Knowledge and Data Engineering_ , 30(6):1095–1108, 2018.  doi: 10.1109/TKDE.2017.2787757.
  * Topkis (1998) D. M. Topkis.  _Supermodularity and complementarity_.  Princeton University Press, 1998.