# Optimal approximation for unconstrained
non-submodular minimization

Marwa El Halabi CSAIL, MIT<EMAIL_ADDRESS>Stefanie Jegelka CSAIL, MIT
<EMAIL_ADDRESS>
###### Abstract

Submodular function minimization is a well studied problem; existing
algorithms solve it exactly or up to arbitrary accuracy. However, in many
applications, the objective function is not exactly submodular. No theoretical
guarantees exist in this case. While submodular minimization algorithms rely
on intricate connections between submodularity and convexity, we show that
these relations can be extended sufficiently to obtain approximation
guarantees for non-submodular minimization. In particular, we prove how a
projected subgradient method can perform well even for certain non-submodular
functions. This includes important examples, such as objectives for structured
sparse learning and variance reduction in Bayesian optimization. We also
extend this result to noisy function evaluations. Our algorithm works in the
value oracle model. We prove that in this model, the approximation result we
obtain is the best possible with a subexponential number of queries.

##  1 Introduction

Many machine learning problems can be formulated as minimizing a _set
function_ $H$. In general, this problem is NP-hard, but it can be solved
efficiently with additional structure. An important example of such structure
is that $H$ is _submodular_ , i.e., it satisfies the diminishing returns (DR)
property $H(A\cup\\{i\\})-H(A)\geq H(B\cup\\{i\\})-H(B)$, for all $A\subseteq
B,i\in V\setminus B$. Submodularity is a natural model for a variety of
applications, such as computer vision [11, 10], subset selection [44, 45],
structured sparse learning [2], clustering [48], and many more. Several
algorithms minimize submodular functions in polynomial time, either exactly or
within arbitrary accuracy. These include combinatorial algorithms [55, 32,
33], and algorithms based on convex optimization [24, 3, 42, 13, 1].

However, in many applications, such as structured sparse learning, Bayesian
optimization, and column subset selection, the objective function is not
exactly submodular. Instead, it satisfies a weaker form of the diminishing
returns property. An important class of such functions are _$\alpha$ -weakly
DR-submodular_ functions, introduced in [43]. The parameter $\alpha$
characterizes how close the function is to being submodular (see Section 2 for
a precise definition). Furthermore, in many cases, only noisy evaluations of
the objective are available. A natural question then arises: _Can submodular
minimization algorithms extend to such non-submodular noisy functions?_

Non-submodular _maximization_ , under various notions of approximate
submodularity, has recently received a lot of attention [15, 54, 6, 40, 31,
56, 29, 30]. In contrast, only few studies consider _minimization_ of non-
submodular set functions. Blais et al. [7] show that the cutting plane method
of [42] can be used to approximately minimize noisy submodular functions.
Other recent works have studied the problem of minimizing the ratio of two set
functions, where one [4, 50] or both [61] of them are non-submodular. The
ratio problem is related to constrained minimization, which does not admit a
constant factor approximation even in the submodular case [58]. If the
objective is approximately _modular_ , i.e., it has bounded _curvature_ ,
algorithmic techniques related to those for submodular maximization achieve
optimal approximations for constrained minimization [57, 36].

In this paper, we initiate the study of the unconstrained non-submodular
minimization problem

$\min\nolimits_{S\subseteq V}\;H(S):=F(S)-G(S),$ (1)

where $F$ and $G$ are monotone (i.e., non-decreasing or non-increasing)
functions, $F$ is _$\alpha$ -weakly DR-submodular_, and $G$ is _$\beta$
-weakly DR-supermodular_, i.e., $-G$ is ${\beta^{-1}}$-weakly DR-submodular.
The definitions of weak DR-sub-/supermodularity only hold for monotone
functions, and thus do not directly apply to $H$. This setting covers several
important applications, including structured sparse learning and Bayesian
optimization. In fact, we show that any set function $H$ can be decomposed
into functions $F$ and $G$ that satisfy these assumptions, albeit with
properties leading to weaker approximations when the function is far from
being submodular.

A key strategy for minimizing submodular functions exploits a tractable tight
convex relaxation that enables convex optimization algorithms. But, this
relaxation relies on the equivalence between the convex closure of a
submodular function and the polynomial-time computable _Lovász extension_. In
general, the convex closure of a set function can be NP-hard to compute, and
the Lovász extension is convex if and only if the set function is submodular.
Thus, the optimization delicately relies on submodularity; generally, a
tractable tight convex relaxation is impossible. Yet, in this paper, we show
that for approximately submodular functions, we may just pretend that the
Lovász extension provides (approximate) subgradients that can be used in a
projected subgradient method (PGM). In fact, this strategy is guaranteed to
obtain an approximate solution to Problem (1), characterized by $\alpha$ and
$\beta$. This insight broadly expands the scope of submodular minimization
techniques. In short, our main contributions are:

  * •

the _first_ approximation guarantee for unconstrained non-submodular
minimization: PGM achieves a tight approximation of
$H(S)\leq{F(S^{*})}/\alpha-\beta G(S^{*})+\epsilon$;

  * •

an extension of this result to the case where only a noisy oracle of $H$ is
accessible;

  * •

a hardness result showing that improving on the approximation guarantee
achieved by PGM would require exponentially many queries in the value oracle
model;

  * •

application to structured sparse learning and structured batch Bayesian
optimization, implying the _first_ approximation guarantees for these
problems;

  * •

experiments demonstrating that classical submodular minimization algorithms
are indeed robust against noise and non-submodularity in the objective,
reflecting our theoretical results.

Figure 1: Classes of set functions

##  2 Preliminaries

We begin by introducing our notation, the definitions of weak DR-
submodularity/supermodularity, and by reviewing some facts about classical
submodular minimization.

#### Notation

Let $V=\\{1,\cdots,d\\}$ be the ground set. Given a set function
$F:2^{V}\to\mathbb{R}$, we denote the _marginal gain_ of adding an element $i$
to a set $A$ by $F(i|A)=F(A\cup\\{i\\})-F(A)$. Given a vector
$\boldsymbol{x}\in\mathbb{R}^{d}$, $x_{i}$ is its $i$-th entry and
$\mathrm{supp}(\boldsymbol{x})=\\{i\in V|x_{i}\not=0\\}$ is its support set;
$\boldsymbol{x}$ also defines a _modular_ set function as
$\boldsymbol{x}(A)=\sum_{i\in A}x_{i}$.

#### Set function classes

$F$ is _normalized_ if $F(\emptyset)=0$, and non-decreasing (non-increasing)
if $F(A)\leq F(B)$ ($F(A)\geq F(B)$) for all $A\subseteq B$. $F$ is
_submodular_ if it has diminishing marginal gains: $F(i|A)\geq F(i|B)$ for all
$A\subseteq B$, $i\in V\setminus B$, _modular_ if the inequality holds as an
equality, and _supermodular_ if $F(i|A)\leq F(i|B)$. Relaxing these
inequalities leads to the notions of weak DR-submodularity/supermodularity
introduced in [43] and [6], respectively.

######  Definition 1 (Weak DR-submodularity/supermodularity).

A set function $F$ is _$\alpha$ -weakly DR-submodular_, with $\alpha>0$, if
for all $A\subseteq B,i\in V\setminus B$

$F(i|A)\geq\alpha F(i|B).$

Similarly, $F$ is $\beta$-weakly DR-supermodular, with $\beta>0$, if for all
$A\subseteq B,i\in V\setminus B$

$F(i|B)\geq\beta F(i|A).$

We say that $F$ is _$(\alpha,\beta)$ -weakly DR-modular_ if it satisfies both
properties.

If $F$ is non-decreasing, then $\alpha,\beta\in(0,1]$, and if it is non-
increasing, then $\alpha,\beta\geq 1$. $F$ is submodular (supermodular) iff
$\alpha=1$ ($\beta=1$) and modular if both $\alpha=\beta=1$ ad the
inequalities hold as equalities.

These notions have been used, sometimes under different names, in various
works such as [28, 20, 9, 40, 54]. The parameters $1\\!-\\!\alpha$ and
$1\\!-\\!\beta$ are referred to as _generalized inverse curvature_ [9] and
_generalized curvature_ [6], respectively. They extend the notions of _inverse
curvature_ and _curvature_ [14] commonly defined for supermodular and
submodular functions. These notions are also related to _weakly
submodular/supermodular_ functions [15, 9]. Namely, the classes of weakly DR-
submodular/supermodular/modular functions are respective subsets of the
classes of weakly submodular/supermodular/modular functions (c.f., [20, Prop.
8], [9, Prop. 1]), as illustrated in Figure 1. For a survey of other notions
of approximate submodularity used in the literature, we refer the reader to
[6, Sect. 6].

#### Submodular minimization

Minimizing a submodular set function $F$ is equivalent to minimizing a non-
smooth convex function, obtained by considering a _continuous extension_ of
$F$, from vertices of the hypercube $\\{0,1\\}^{d}$ to the full hypercube
$[0,1]^{d}$. This extension, called the _Lovász extension_ [46], is convex if
and only if $F$ is submodular.

######  Definition 2 (Lovász extension).

Given any normalized set function $F$, its Lovász extension
$f_{L}:\mathbb{R}^{d}\to\mathbb{R}$ is defined for all
$\boldsymbol{s}\in\mathbb{R}^{d}$ as

$f_{L}(\boldsymbol{s})=\sum_{k=1}^{d}s_{j_{k}}F(j_{k}|S_{k-1}),$

where we defined an ordering $s_{j_{1}}\geq\cdots\geq s_{j_{d}}$ of the
coordinates of $\boldsymbol{s}$, and and $S_{k}=\\{j_{1},\cdots,j_{k}\\}$.

When $F$ is submodular, minimizing $f_{L}$ is equivalent to minimizing $F$ .
Moreover, a subgradient $\boldsymbol{\kappa}$ of $f_{L}$ at any
$\boldsymbol{s}\in\mathbb{R}^{d}$ can be computed efficiently by sorting the
entries of $\boldsymbol{s}$ in decreasing order and taking
$\kappa_{j_{k}}=F(j_{k}|S_{k-1})$ for all $k\in V$ [18].

This relation between submodularity and convexity allows for generic convex
optimization algorithms to be used for minimizing $F$. However, it has been
unclear how these relations are affected if the function is only approximately
submodular. In this paper, we establish a similar relation between approximate
submodularity and approximate convexity.

##  3 Weakly DR-submodular minimization

We consider set functions $H:2^{V}\to\mathbb{R}$ of the form $H(S)=F(S)-G(S)$,
where $F$ is $\alpha$-weakly DR-submodular, $G$ is $\beta$-weakly DR-
supermodular, and both $F$ and $G$ are normalized non-decreasing functions. We
later extend our results to non-increasing functions. We assume a _value
oracle_ access to $H$; i.e., there is an oracle that, given a set $S\subseteq
V$, returns the value $H(S)$. Note that $H$ itself is in general _not_ weakly
DR-submodular. Interestingly, any set function can be decomposed in this form,
as the following proposition shows.

######  Proposition 1.

Given a set function $H$, and $\alpha,\beta\in(0,1]$ such that
$\alpha\beta<1$, there exists a non-decreasing $\alpha$-weakly DR-submodular
function $F$, and a non-decreasing $(\alpha,\beta)$-weakly DR-modular function
$G$, such that $H(S)=F(S)-G(S)$ for all $S\subseteq V$.

###### Proof.

This decomposition builds on the decomposition of $H$ into the difference of
two non-decreasing submodular functions [34]. We start by choosing any
function $G^{\prime}$ which is non-decreasing $(\alpha,\beta)$-weakly DR-
modular, and is strictly $\alpha$-weakly DR-submodular, i.e.,
$\epsilon_{G^{\prime}}=\min_{i\in V,A\subset B\subseteq V\setminus
i}G^{\prime}(i|A)-\alpha G^{\prime}(i|B)>0$. It is always possible to find
such a function: We provide an example in Proposition 2 for $\alpha=1$. For
$\alpha<1$, we can simply use $G^{\prime}(S)=|S|$. It is not possible though
to choose $G^{\prime}$ such that $\alpha=\beta=1$ (this would imply
$G^{\prime}(i|B)\geq G^{\prime}(i|A)>G^{\prime}(i|B)$). We construct $F$ and
$G$ based on $G^{\prime}$.

Let $\epsilon_{H}=\min_{i\in V,A\subseteq B\subseteq V\setminus
i}H(i|A)-\alpha H(i|B)<0$ the violation of $\alpha$-weak DR-submodularity of
$H$; we may use a lower bound $\epsilon^{\prime}_{H}\leq\epsilon_{H}$. We
define
$F^{\prime}(S)=H(S)+\tfrac{|\epsilon^{\prime}_{H}|}{\epsilon_{G^{\prime}}}G^{\prime}(S)$,
then $F^{\prime}(i|A)\geq\alpha F^{\prime}(i|B),\forall i\in V,A\subset
B\subseteq V\setminus i$, but not necessarily for $A=B$ since $F^{\prime}$ is
not necessarily non-decreasing. To correct for that, let
$V^{-}=\\{i:F^{\prime}(i|V\setminus i)<0\\}$ and define
$F(S)=F^{\prime}(S)-\sum_{i\in S\cap V-}F^{\prime}(i|V\setminus i)$. For all
$i\in V,A\subseteq V\setminus i$, if $i\not\in V^{-}$ then
$F(i|A)=F^{\prime}(i|A)\geq\alpha F^{\prime}(i|V\setminus i)\geq 0$, otherwise
$F(i|A)=F^{\prime}(i|A)-F^{\prime}(i|V\setminus
i)\geq(\alpha-1)F^{\prime}(i|V\setminus i)\geq 0$ for $A\not=V\setminus i$ and
$F(i|V\setminus i)=0$. $F$ is thus non-decreasing $\alpha$-weakly DR-
submodular. We also define
$G(S)=\tfrac{|\epsilon^{\prime}_{H}|}{\epsilon_{G^{\prime}}}G^{\prime}(S)-\sum_{i\in
S\cap V-}F^{\prime}(i|V\setminus i)$, then $H(S)=F(S)-G(S)$ and $G$ is non-
decreasing $(\alpha,\beta)$-weakly DR-modular. ∎

Computing such a decomposition is _not_ required to run PGM for minimization;
it is only needed to evaluate the corresponding approximation guarantee. The
construction in the above proof requires computing the maximal $\alpha$-weak
DR-submodularity violation $\epsilon_{H}$ of $H$, which is NP-hard in general.
However, when $\epsilon_{H}$ or a lower bound of it is known, $F$ and $G$ can
be obtained in polynomial time, for a suitable choice of $G^{\prime}$.
Proposition 2 provides a valid choice of $G^{\prime}$ for $\alpha=1$. Any
modular function can be used for $\alpha<1$.

######  Proposition 2.

Given $\beta\in(0,1)$, let $G^{\prime}(S)=g(|S|)$ where
$g(x)=\tfrac{1}{2}ax^{2}+(1-\tfrac{1}{2}a)x$ with $a=\frac{\beta-1}{d-1}$.
Then $G^{\prime}$ is non-decreasing $(1,\beta)$-weakly DR-modular, and is
strictly submodular, with $\epsilon_{G^{\prime}}=\min_{i\in V,A\subset
B\subseteq V\setminus i}G^{\prime}(i|A)-G^{\prime}(i|B)=-a>0$.

The lower bound on $\epsilon_{H}$ and the choice of $\alpha,\beta$, and
$G^{\prime}$ will affect the approximation guarantee on $H$, as we clarify
later. When $H$ is far from being submodular, it may not be possible to choose
$G^{\prime}$ to obtain a non-trivial guarantee. However, many important non-
submodular functions do admit a decomposition which leads to non-trivial
bounds. We call such functions approximately submodular.

In what follows, we establish a connection between approximate submodularity
and approximate convexity, which allows us to derive a _tight_ approximation
guarantee for PGM on Problem (1). All omitted proofs are given in Appendix
A.2.

###  3.1 Convex relaxation

When $H$ is not submodular, the connections between its Lovász extension and
tight convex relaxation for exact minimization, outlined in Section 2, break
down. However, Problem (1) can still be converted to a non-smooth convex
optimization problem, via a different convex extension. Given a set function
$H$, its _convex closure_ $h^{-}$ is the point-wise largest convex function
from $[0,1]^{d}$ to $\mathbb{R}$ that always lower bounds $H$. Intuitively,
$h^{-}$ is the _tightest_ convex extension of $H$ on $[0,1]^{d}$. The
following equivalence holds [17, Prop. 3.23]:

$\min_{S\subseteq
V}H(S)=\min_{\boldsymbol{s}\in[0,1]^{d}}h^{-}(\boldsymbol{s}).$ (2)

Unfortunately, evaluating and optimizing the convex closure of a general set
function is NP-hard [60]. The key property that makes Problem (2) efficient to
solve when $H$ is submodular is that its convex closure then coincides with
its Lovász extension, i.e., $h^{-}=h_{L}$. This property no longer holds if
$H$ is only approximately submodular. But, in this case, a weaker key property
holds: we show in Lemma 1 that the Lovász extension approximates $h^{-}$, and
that the same vectors that served as its subgradients in the submodular case
can still serve as approximate subgradients to $h^{-}$.

######  Lemma 1.

Given a vector $\boldsymbol{s}\in[0,1]^{d}$ such that $s_{j_{1}}\geq\cdots\geq
s_{j_{d}}$, we define $\boldsymbol{\kappa}$ such that
$\kappa_{j_{k}}=H(j_{k}|S_{k-1})$ where $S_{k}=\\{j_{1},\cdots,j_{k}\\}$.
Then, $h_{L}(\boldsymbol{s})=\boldsymbol{\kappa}^{\top}\boldsymbol{s}\geq
h^{-}(\boldsymbol{s})$, $\boldsymbol{\kappa}(A)\leq\tfrac{1}{\alpha}F(A)-\beta
G(A)$ for all $A\subseteq V$, and
$\boldsymbol{\kappa}^{\top}\boldsymbol{s}^{\prime}\leq\tfrac{1}{\alpha}f^{-}(\boldsymbol{s}^{\prime})+\beta(-g)^{-}(\boldsymbol{s}^{\prime})$
for all $\boldsymbol{s}^{\prime}\in[0,1]^{d}$.

To prove Lemma 1, we use a specific formulation of the convex closure $h^{-}$
[19, Def. 20]:

$h^{-}(\boldsymbol{s})=\max_{\boldsymbol{\kappa}\in\mathbb{R}^{d},\rho\in\mathbb{R}}\\{\boldsymbol{\kappa}^{\top}\boldsymbol{s}+\rho:\boldsymbol{\kappa}(A)+\rho\leq
H(A),\forall A\subseteq V\\},$ (3)

and build on the proof of Edmonds’ greedy algorithm [18].

We can view the vector $\boldsymbol{\kappa}$ in Lemma 1 as an approximate
subgradient of $h^{-}$ at $\boldsymbol{s}$ in the following sense:

$\tfrac{1}{\alpha}f^{-}(\boldsymbol{s}^{\prime})+\beta(-g)^{-}(\boldsymbol{s}^{\prime})\geq
h^{-}(\boldsymbol{s})+\langle\boldsymbol{\kappa},\boldsymbol{s}^{\prime}-\boldsymbol{s}\rangle,\forall\boldsymbol{s}^{\prime}\in[0,1]^{d}.$

Lemma 1 also implies that the Lovász extension $h_{L}$ approximates the convex
closure $h^{-}$ in the following sense:

$h^{-}(\boldsymbol{s})\leq
h_{L}(\boldsymbol{s})\leq\tfrac{1}{\alpha}f^{-}(\boldsymbol{s})+\beta(-g)^{-}(\boldsymbol{s}),\forall\boldsymbol{s}\in[0,1]^{d}.$

We can thus say that $h_{L}$ is approximately convex in this case. This key
insight allows us to approximately minimize $h^{-}$ using simple convex
optimization algorithms.

###  3.2 Algorithm and approximation guarantees

Equipped with the approximate subgradients of $h^{-}$, we can now apply an
approximate projected subgradient method (PGM). Starting from an arbitraty
$\boldsymbol{s}^{1}\in[0,1]^{d}$, PGM iteratively updates
$\boldsymbol{s}^{t+1}=\Pi_{[0,1]^{d}}(\boldsymbol{s}^{t}-\eta\boldsymbol{\kappa}^{t})$,
where $\boldsymbol{\kappa}^{t}$ is the approximate subgradient at
$\boldsymbol{s}^{t}$ from Lemma 1, and $\Pi_{[0,1]^{d}}$ is the projection
onto $[0,1]^{d}$. We set the step size to $\eta=\tfrac{R}{L\sqrt{T}}$, where
$L=F(V)+G(V)$ is the Lipschitz constant, i.e.,
$\|\boldsymbol{\kappa}^{t}\|_{2}\leq L$ for all $t$, and $R=2\sqrt{d}$ is the
domain radius $\|\boldsymbol{s}^{1}-\boldsymbol{s}^{*}\|_{2}\leq R$.

######  Theorem 1.

After $T$ iterations of PGM,
$\hat{\boldsymbol{s}}\in\operatorname*{arg\,min}_{t\in\\{1,\cdots,T\\}}h_{L}(\boldsymbol{s}^{t})$
satisfies:

$h^{-}(\hat{\boldsymbol{s}})\;\leq\;h_{L}(\hat{\boldsymbol{s}})\;\leq\;\frac{1}{\alpha}f^{-}(\boldsymbol{s}^{*})+\beta(-g)^{-}(\boldsymbol{s}^{*})+\frac{RL}{\sqrt{T}},$

where $\boldsymbol{s}^{*}$ is an optimal solution of
$\min_{\boldsymbol{s}\in[0,1]^{d}}h^{-}(\boldsymbol{s})$.

Importantly, the algorithm does not need to know the $\alpha$ and $\beta$
parameters, which can be hard to compute in practice. In fact, the iterates
taken are exactly the same as in the submodular case.

Theorem 1 provides an approximate fractional solution
$\hat{\boldsymbol{s}}\in[0,1]^{d}$. To round it to a discrete solution,
Corollary 1 shows that it is sufficient to pick the superlevel set of
$\hat{\boldsymbol{s}}$ with the smallest $H$ value.

######  Corollary 1.

Given the fractional solution $\hat{\boldsymbol{s}}$ in Theorem 1, let
$\hat{S}_{k}=\\{j_{1},\cdots,j_{k}\\}$ such that
$\hat{s}_{j_{1}}\geq\cdots\geq\hat{s}_{j_{d}}$, and $\hat{S}_{0}=\emptyset$.
Then $\hat{S}\in\operatorname*{arg\,min}_{k\in\\{0,\cdots,d\\}}H(\hat{S}_{k})$
satisfies

$H(\hat{S})\leq\frac{1}{\alpha}F(S^{*})-\beta G(S^{*})+\frac{RL}{\sqrt{T}},$

where $S^{*}$ is an optimal solution of Problem (1).

###### Proof.

By definition of the Lovász extension,
$h_{L}(\hat{\boldsymbol{s}})=\sum_{k=1}^{d-1}(\hat{s}_{j_{k}}-\hat{s}_{j_{k+1}})H(\hat{S}_{k})+\hat{s}_{j_{d}}H(V)\geq\min_{k\in\\{0,\cdots,d\\}}H(\hat{S}_{k}).$
The corollary then follows by Theorem 1 and the extension property
$f^{-}(\boldsymbol{s}^{*})=F(S^{*}),(-g)^{-}(\boldsymbol{s}^{*})=-G(S^{*})$. ∎

To obtain a set that satisfies $H(\hat{S})\leq F(S^{*})/\alpha-\beta
G(S^{*})+\epsilon$, we thus need at most $O({dL^{2}}/{\epsilon^{2}})$
iterations of PGM, where the time per iteration is $O(d\log d+d~{}\text{EO})$,
with EO being the time needed to evaluate $H$ on any set. Moreover, the
techniques from [13, 1] for accelerating the runtime of stochastic PGM to
$\tilde{O}(d~{}\text{EO}/\epsilon^{2})$ can be extended to our setting.

If $F$ is regarded as a cost and $G$ as a revenue, this guarantee states that
the returned solution achieves at least a fraction $\beta$ of the revenue of
the optimal solution, by paying at most a $1/\alpha$-multiple of the cost. The
quality of this guarantee depends on $F,G$ and their parameters
$\alpha,\beta$; it becomes vacuous when $F(S^{*})/\alpha\geq\beta G(S^{*})$.
If $F$ is submodular and $G$ is supermodular, Problem (1) reduces to
submodular minimization and Corollary 1 recovers the guarantee
$H(\hat{S})\leq{H(S^{*})}+{RL}/{\sqrt{T}}$.

######  Remark 1.

The upper bound in Corollary 1 still holds if the worst case parameters
$\alpha,\beta$ are instead replaced by
$\alpha_{T}=\tfrac{1}{T}\sum_{t=1}^{T}\tfrac{F(S^{*})}{\boldsymbol{\kappa}_{F}^{t}(S^{*})}$
and
$\beta_{T}=\tfrac{1}{T}\sum_{t=1}^{T}\tfrac{\boldsymbol{\kappa}_{G}^{t}(S^{*})}{G(S^{*})}$,
where $(\boldsymbol{\kappa}^{t}_{F})_{j_{k}}=F(j^{t}_{k}|S^{t}_{k-1})$ and
$(\boldsymbol{\kappa}^{t}_{G})_{j_{k}}=G(j^{t}_{k}|S^{t}_{k-1})$. This refined
upper bound yields improvements if only few of the relevant submodularity
inequalities are violated, e.g., due to infrequent perturbations.

The following proposition shows that the approximation guarantee in Corollary
1 is tight, even if $F$ and $G$ are weakly DR-modular. Hence, it is not
possible to obtain a better approximation guarantee for PGM.

######  Proposition 3.

For any $\alpha,\beta\in(0,1]$, there exists a set function $H(S)=F(S)-G(S)$,
where $F$ is a non-decreasing $(\alpha,1)$-weakly DR-modular function and $G$
is a non-decreasing $(1,\beta)$-weakly DR-modular function, such that the
solution $\hat{S}$ in Corollary 1 satisfies

$H(\hat{S})=\frac{1}{\alpha}F(S^{*})-\beta G(S^{*}).$

###### Proof sketch.

We define

$F(S)=\begin{cases}|S|+\tfrac{d}{\beta}-1&\text{if $1\in S$}\\\
\alpha|S|&\text{ otherwise}\end{cases},\text{ and
}G(S)=\begin{cases}|S|+\tfrac{d}{\beta}-1&\text{if $1\in S$}\\\
\tfrac{1}{\beta}|S|&\text{ otherwise}\end{cases}.$

We can assume w.l.o.g. that the starting point $\boldsymbol{s}^{1}$ is such
that the largest element is $j_{1}=1$. Then for all $t$ the approximate
subgradients $\boldsymbol{\kappa}^{t}=\boldsymbol{0},$ thus $H(\hat{S})=0$,
while the optimal solution $S^{*}=V\setminus\\{1\\}$ has value
$H(S^{*})=(\alpha-\frac{1}{\beta})(n-1)<0$. Hence,
$H(\hat{S})=\tfrac{1}{\alpha}F(S^{*})-\beta
G(S^{*})=\tfrac{\alpha(n-1)}{\alpha}-\beta\tfrac{(n-1)}{\beta}$. ∎

All results in this section extend to the case where $F$ and $G$ are non-
increasing functions.

######  Corollary 2.

Given $H(S)=F(S)-G(S)$, where $F$ and $G$ are non-increasing functions with
$F(V)=G(V)=0$, we run PGM with $\tilde{H}(S)=H(V\setminus S)$ for $T$
iterations. Let
$\tilde{\boldsymbol{s}}\in\operatorname*{arg\,min}_{t\in\\{1,\cdots,T\\}}\tilde{h}_{L}(\boldsymbol{s}^{t})$
and $\hat{S}=V\setminus\tilde{S}$, where $\tilde{S}$ is the superlevel set of
$\tilde{\boldsymbol{s}}$ with the smallest $H$ value, then

$H(\hat{S})\leq\alpha{F(S^{*})}-\frac{1}{\beta}G(S^{*})+\frac{RL}{\sqrt{T}},$

where $S^{*}$ is an optimal solution of Problem (1). This bound is tight, even
if $F$ and $G$ are weakly DR-modular.

###### Proof.

We may write $\tilde{H}(S)=\tilde{F}(S)-\tilde{G}(S)$, where
$\tilde{F}(S)=F(V\setminus S)$ is non-decreasing $1/\alpha$-weakly DR-
submodular, and $\tilde{G}(S)=G(V\setminus S)$ is non-decreasing
$1/\beta$-weakly DR-supermodular. Let
$\tilde{S}^{*}\in\operatorname*{arg\,min}_{S\subseteq V}\tilde{H}(S)$, then
$S^{*}=V\setminus\tilde{S}^{*}$. Corollary 1 implies that
$H(\hat{S})=\tilde{H}(\tilde{S})\leq{\alpha}\tilde{F}(\tilde{S}^{*})-\tfrac{1}{\beta}\tilde{G}(\tilde{S}^{*})={\alpha}F(S^{*})-\tfrac{1}{\beta}G(S^{*})$.
The tightness follows from Proposition 3, too. ∎

A general set function $H$, using $F$ and $G$ from the decomposition in
Proposition 1, yields in Corollary 1:

$H(\hat{S})\leq\tfrac{1}{\alpha}H(S^{*})+(\tfrac{1}{\alpha}-\beta)\bigl{(}\tfrac{|\epsilon^{\prime}_{H}|}{\epsilon_{G^{\prime}}}G^{\prime}(S^{*})-\\!\\!\\!\\!\sum_{i\in
S\cap V^{-}}\\!\\!\\!F^{\prime}(i|V\setminus i)\bigl{)}+\epsilon,$

where $\epsilon^{\prime}_{H}$ is a lower bound on the violation of
$\alpha$-weak DR-submodularity of $H$, $F^{\prime}$ and $G^{\prime}$ are the
auxilliary functions used to construct $F$ and $G$, and
$\epsilon_{G^{\prime}}$ is the strict $\alpha$-weak DR-submodularity of
$G^{\prime}$ (see proof of Proposition 1 for precise definitions). It is clear
that a larger lower bound $|\epsilon^{\prime}_{H}|$ leads to a worse upper
bound. Moreover, the choice of $G^{\prime}$ affects the bound: ideally, we
want to choose $G^{\prime}$ to minimize $G^{\prime}(S^{*})$, and maximize the
quantities $\alpha,\epsilon_{G^{\prime}}$ and $\beta$, which characterize how
submodular and supermodular $G^{\prime}$ is, respectively. However, a larger
$\alpha$ leads to a larger $|\epsilon^{\prime}_{H}|$ and smaller
$\epsilon_{G^{\prime}}$, and a larger $\epsilon_{G^{\prime}}$ would result in
a smaller $\beta$, and vice versa. The best choice of $G^{\prime}$ will depend
on $H$.

Apart from the above results for general unconstrained minimization, our
results also imply approximation guarantees for generalizing constrained
submodular minimization to weakly DR-submodular functions. We discuss this
extension in Appendix A.1.

###  3.3 Extension to noisy evaluations

In many real-world applications, we do not have access to the objective
function itself, but rather to a noisy version of it. For example, in machine
learning, the objective function is often estimated from data. In other cases,
evaluating the function may be too computationally expensive, and thus
individual evaluations are approximated.

Several works have considered maximizing noisy oracles of submodular [38, 31,
56, 29, 30] and weakly submodular [51] functions. In contrast, to the best of
our knowledge, _minimizing_ noisy oracles of submodular functions was only
studied in [7]. We address a more general setup where the underlying function
$H$ is not necessarily submodular. We assume again that $F$ and $G$ are
normalized and non-decreasing. The results easily extend to non-increasing
functions by minimizing $H(V\setminus S)$ as in Corollary 2.

We show in Proposition 4 that our approximation guarantee for Problem (1)
continues to hold even if we only have access to an approximate oracle
$\tilde{H}$. Essentially, $\tilde{H}$ still allows to obtain approximate
subgradients of $h^{-}$ in the sense of Lemma 1, but now with an additional
additive error.

######  Proposition 4.

Assume we have an approximate oracle $\tilde{H}$ with input parameters
$\epsilon,\delta\in(0,1)$, such that for every $S\subseteq V$,
$|\tilde{H}(S)-H(S)|\leq\epsilon$ with probability $1-\delta$. We run PGM with
$\tilde{H}$ for $T$ iterations. Let
$\hat{\boldsymbol{s}}=\operatorname*{arg\,min}_{t\in\\{1,\cdots,T\\}}\tilde{h}_{L}(\boldsymbol{s}^{t})$,
and $\hat{S}_{k}=\\{j_{1},\cdots,j_{k}\\}$ such that
$\hat{s}_{j_{1}}\geq\cdots\geq\hat{s}_{j_{d}}$. Then
$\hat{S}\in\operatorname*{arg\,min}_{k\in\\{0,\cdots,d\\}}\tilde{H}(\hat{S}_{k})$
satisfies

$H(\hat{S})\leq\frac{1}{\alpha}F(S^{*})-\beta G(S^{*})+\epsilon^{\prime},$

with probability $1-\delta^{\prime}$, by choosing
$\epsilon=\tfrac{\epsilon^{\prime}}{8d}$,
$\delta=\tfrac{\delta^{\prime}\epsilon^{\prime 2}}{32d^{2}}$ and using $2Td$
calls to $\tilde{H}$ with $T=({4\sqrt{d}L}/{\epsilon^{\prime}})^{2}$.

Blais et al [7] consider the same setup for the special case of submodular
$H$, and use the cutting plane method of [42]. Their runtime has better
dependence $O(\log(1/\epsilon^{\prime}))$ on the error $\epsilon^{\prime}$,
but worse dependence $O(d^{3})$ on the dimension $d=|V|$, and their result
needs oracle accuracy $\epsilon=O(\epsilon^{\prime 2}/d^{5})$. Hence, for
large ground set sizes $d$, Proposition 4 is preferable.

The above proposition allows us, in particular, to handle multiplicative and
additive noise in $H$.

######  Proposition 5.

Let $\tilde{H}=\xi H$ where the noise $\xi\geq 0$ is bounded by
$|\xi|\leq\omega$ and is independently drawn from a distribution $\mathcal{D}$
with mean $\mu>0$. We define the function $\tilde{H}_{m}$ as the mean of $m$
queries to $\tilde{H}(S)$. $\tilde{H}_{m}$ is then an approximate oracle to
$\mu H$. In particular, for every $\delta,\epsilon\in(0,1)$, taking
$m=({\omega H_{\max}}/{\epsilon})^{2}\ln({1}/{\delta})$ where
$H_{\max}=\max_{S\subseteq V}H(S)$, we have for every $S\subseteq V$,
$|\tilde{H}_{m}(S)-\mu H(S)|\leq\epsilon$ with probability at least
$1-\delta$.

###### Proof.

For every $S\subseteq V$ and $\epsilon^{\prime}>0$, a Chernoff bound implies
that $(1-\epsilon^{\prime})\mu
H(S)\leq\tilde{H}_{m}(S)=\tfrac{1}{m}\sum_{i=1}^{m}\xi_{i}H(S)\leq(1+\epsilon^{\prime})\mu
H(S),$ with probability at least $1-\exp(-\tfrac{\epsilon^{\prime
2}\mu^{2}m}{\omega^{2}})$. Choosing $\epsilon^{\prime}=\tfrac{\epsilon}{\mu
H_{\max}}$ yields the proposition. ∎

Proposition 5, together with Proposition 4, implies that using PGM with
$\tilde{H}_{m}$, and picking the superlevel set with the smallest
$\tilde{H}_{m}$ value, we can find a set $\hat{S}$ such that $H(\hat{S})\leq
F(S^{*})/\alpha-\beta G(S^{*})+\epsilon^{\prime}$ with probability
$1-\delta^{\prime}$, using $m=O\bigl{(}(\tfrac{\omega
H_{\max}d}{\mu\epsilon^{\prime}})^{2}\ln(\tfrac{d^{2}}{\delta^{\prime}\mu^{2}\epsilon^{\prime
2}})\bigl{)}$ samples, after $T=O\bigl{(}(\sqrt{d}\mu
H_{\max}/\epsilon^{\prime})^{2}\bigl{)}$ iterations, with
$O\bigl{(}\tfrac{\omega}{\mu}(\tfrac{H_{\max}d}{\epsilon^{\prime}})^{4}\ln(\tfrac{d^{2}}{\delta^{\prime}\mu^{2}\epsilon^{\prime
2}})\bigl{)}$ total calls to $\tilde{H}$. Note that $H_{\max}$ is upper
bounded by $F(V)$. This result provides a theoretical upper bound on the
number of samples needed to be robust to bounded multiplicative noise. Much
fewer samples are actually needed in practice, as illustrated in our
experiments (c.f., Sect. 5.1). Using similar arguments, we can show that our
results also extend to additive noise oracles $\tilde{H}=H+\xi$.

###  3.4 Inapproximability Result

Problem (1) is equivalent to general set function minimization by Proposition
1. Thus solving Problem (1) optimally or with any multiplicative factor
approximation (i.e., $H(\hat{S})\leq\gamma(d)H(S^{*})$ for some positive
polynomial time computable function $\gamma(d)$ of $d$) is NP-Hard [59, 34].
Moreover, in the value oracle model, it is not possible to obtain any
multiplicative constant factor approximation, using a subexponential number of
queries [34]. It is thus necessary to consider bicriteria-like approximation
guarantees as we do.
We showed earlier in Proposition 3 that the approximation guarantees in
Corollary 1 and 2 cannot be improved for PGM. We derive now an information
theoretic inapproximability result, showing that these approximation
guarantees cannot be improved in general. In particular, we show that, in the
value oracle model, no (deterministic or randomized) algorithm can improve on
the approximation guarantees achieved by PGM, using subexponential number of
queries, even when $G$ is weakly DR-modular.

######  Theorem 2.

For any $\alpha,\beta\in(0,1]$ such that $\alpha\beta<1,d>2$ and $\delta>0$,
there are instances of Problem (1) such that no (deterministic or randomized)
algorithm, using less than exponentially many queries, can always find a
solution $S\subseteq V$ of expected value at most
$\tfrac{1}{\alpha}F(S^{*})-\beta G(S^{*})-\delta$.

###### Proof.

We use a similar proof technique to [23]. Let $C,D$ be two sets that partition
the ground set $V=C\cup D$ such that $|C|=|D|=d/2$. We construct a normalized
set function $H$ whose values depend only on $k(S)=|S\cap C|$ and
$\ell(S)=|S\cap D|$. In particular, we define

$\displaystyle H(S)=\begin{cases}0&\text{if $|k(S)-\ell(S)|\leq\epsilon d$}\\\
\frac{2\alpha\delta}{2-d}&\text{otherwise}\end{cases},$

for some $\epsilon\in[1/d,1/2)$. By Proposition 1, given a non-decreasing
$(\alpha,\beta)$-weakly DR-modular function $G^{\prime}$, we can write
$H(S)=F(S)-G(S)$, where
$F(S)=H(S)+\frac{|\epsilon_{H}|}{\epsilon_{G^{\prime}}}G^{\prime}(S)$ is
normalized non-decreasing $\alpha$-weakly DR-submodular, and
$G(S)=\frac{|\epsilon_{H}|}{\epsilon_{G^{\prime}}}G^{\prime}(S)$ is normalized
non-decreasing $(\alpha,\beta)$-weakly DR-modular. Note that $V^{-}=\emptyset$
in this case, since $H(i|V\setminus i)=0$. We choose $G^{\prime}(S)=|S|$ if
$\alpha<1$, then $\epsilon_{G^{\prime}}=\min_{i\in V,S\subset T\subseteq
T\setminus i}G(i|S)-\alpha G(i|T)=1-\alpha>0$. If $\alpha=1$, we use the
$(1,\beta)$-weakly DR-modular function defined in Proposition 2, then
$\epsilon_{G^{\prime}}=\frac{1-\beta}{d-1}>0$.

Let the partition $(C,D)$ be random and unknown to the algorithm. We argue
that, with high probability, any given query $S$ will be “balanced”, i.e.,
$|k(S)-\ell(S)|\leq\epsilon d$. Hence no deterministic algorithm can
distinguish between $H$ and the constant zero function. Given a fixed
$S\subseteq V$, let $X_{i}=1$ if $i\in C$ and $0$ otherwise, for all $i\in S$,
then $\mu=\mathbb{E}[\sum_{i\in S}X_{i}]=\sum_{i\in
S}\frac{|C|}{d}=\frac{|S|}{2}$. Then by a Chernoff’s bound we have
$Pr(|k(S)-\ell(S)|>\epsilon d)\leq 2\exp(-\frac{\epsilon^{2}d}{4})$. Hence,
given a sequence of $e^{\frac{\epsilon^{2}d}{8}}$ queries, the probability
that each query $S$ is balanced, and thus has value $H(S)=0$, is still at
least $1-2e^{-\frac{\epsilon^{2}d}{8}}$. On the other hand, we have
$H(S^{*})=\frac{2\alpha\delta}{2-d}<0$, achieved at $S^{*}=C$ or $D$.
Moreover, note that $\epsilon_{H}=\min_{i\in V,S\subseteq T\subseteq
T\setminus i}H(i|S)-\alpha H(i|T)=(1+\alpha)H(S^{*})$. Hence

$\tfrac{1}{\alpha}F(S^{*})-\beta
G(S^{*})-\delta=\tfrac{1}{\alpha}H(S^{*})\biggl{(}1-(1-\alpha\beta)(1+\alpha)\frac{G^{\prime}(S^{*})}{\epsilon_{G^{\prime}}}\biggl{)}-\delta<0,$

since
$\tfrac{G^{\prime}(S^{*})}{\epsilon_{G^{\prime}}}=\tfrac{d}{2(1-\alpha)}$ if
$\alpha<1$, and
$\frac{G^{\prime}(S^{*})}{\epsilon_{G^{\prime}}}\geq\frac{3d(d-1)}{8(1-\beta)}$,
if $\alpha=1$.

Therefore, with high probability, the algorithm cannot find a set with value
$H(S)\leq\tfrac{1}{\alpha}F(S^{*})-\beta G(S^{*})-\delta$. This also holds for
a randomized algorithm, by averaging over its random choices. ∎

The approximation guarantees in Corollary 1 and 2 are thus optimal. Note that
$G$ is weakly DR-modular in the above proof, so the hardness result still
holds in this case. In contrast, $F$ is not necessarily weakly DR-modular.
Whether the approximation guarantee can be improved when $F$ is also weakly
DR-modular is left as an open question. Such improvement cannot be achieved by
PGM though, as shown by the tightness result in Proposition 3.

##  4 Applications

Several applications can benefit from the theory in this work. We discuss two
examples here.

###  4.1 Structured sparse learning

Structured sparse learning aims to estimate a _sparse_ parameter vector whose
support is known to have a particular _structure_ , such as group-sparsity,
clustering, tree-structure, or diversity [49, 41]. Such problems can be
formulated as

$\min_{\boldsymbol{x}\in\mathbb{R}^{d}}\ell(\boldsymbol{x})+\lambda
F(\mathrm{supp}(\boldsymbol{x})),$ (4)

where $\ell$ is a convex loss function and $F$ is a set function favoring the
desirable supports.

Existing convex methods propose to replace the discrete regularizer
$F(\mathrm{supp}(\boldsymbol{x}))$ by its “closest” convex relaxation [2, 21,
49, 20]. For example, the cardinality regularizer
$|\mathrm{supp}(\boldsymbol{x})|$ is replaced by the $\ell_{1}$-norm. This
allows the use of standard convex optimization methods, but does not provide
any approximation guarantee for the original objective function without
statistical modeling assumptions. This approach is also only computationally
feasible when $F$ is submodular [2] or can be expressed as an integral linear
program [21].

Alternatively, one may write Problem (4) as $\min_{S\subseteq V}\lambda
F(S)-G^{\ell}(S)$, where $G^{\ell}$ is a normalized non-decreasing set
function:

$G^{\ell}(S)=\ell(0)-\min_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\ell(\boldsymbol{x}).$ (5)

Recently, it was shown that if $\ell$ has restricted smoothness and strong
convexity, $G^{\ell}$ is weakly modular [22, 9, 53]. This allowed for
approximation guarantees of greedy algorithms to be applied to the constrained
variant of Problem (4), but only for the special case of a sparsity constraint
[15, 22], and for some near-modular constraints [54]. In applications,
however, the structure of interest is often better modeled by a non-modular
regularizer $F$, which may be submodular [2] or non-submodular [21, 20]. Weak
modularity of $G^{\ell}$ is not enough for our results to apply, but, if the
loss function $\ell$ is smooth, strongly convex, and is generated from random
data, then we show that $G^{\ell}$ is also weakly DR-modular.

######  Proposition 6.

Let
$\ell(\boldsymbol{x})\\!\\!=L(\boldsymbol{x})-\boldsymbol{z}^{\top}\boldsymbol{x}$,
where $L$ is smooth and strongly convex, and $\boldsymbol{z}\in\mathbb{R}^{d}$
has a continuous density w.r.t the Lebesgue measure. Then there exist
$\alpha_{G},\beta_{G}\\!\\!>\\!\\!0$ such that $G^{\ell}$ is
$(\alpha_{G},\beta_{G})$-weakly DR-modular.

We actually prove a more general result: if $\ell$ is smooth and strongly
convex on the _restricted_ domain of $k$-sparse vectors, $G^{\ell}$ is weakly
DR-modular for all sets of cardinality $k$. Our current algorithm analysis
requires weak DR-submodularity to hold for all sets. Whether the algorithm can
be modified to only query sets of cardinality $k$, and as a result apply to an
even more general class of loss functions, is an interesting question for
future work.

We prove Proposition 6 by first utilizing a result from [22], which relates
the marginal gain of $G^{\ell}$ to the marginal decrease of $\ell$. We then
argue that the minimizer of $\ell$, restricted to any given support, has full
support with probability one, and thus $\ell$ has non-zero marginal decrease
with probability one. The proof is given in Appendix A.3. The actual
$\alpha_{G},\beta_{G}$ parameters depend on the conditioning of $\ell$. Their
positivity also relies on $\boldsymbol{z}$ being random (typically, data drawn
from a distribution), otherwise we may have $\alpha_{G}=\beta_{G}=0$ [53,
Sect. A.1]. In Section 5.2, we evaluate Proposition 6 empirically.

The approximation guarantee in Corollary 1 thus applies to Problem (4),
whenever $\ell$ has the form in Proposition 6, and $F$ is $\alpha$-weakly DR-
submodular. In particular, this holds for example when $\ell$ is the least
squares loss with a nonsingular measurement matrix. Examples of structure-
inducing regularizers $F$ include submodular regularizers [2], but also non-
submodular ones such as the following.

Range cost: The range cost is $F(S)=\max(S)-\min(S)+1$ if $S\not=\emptyset$,
and $F(\emptyset)=0$, where $\max(S)\;(\min(S))$ denotes the maximal (minimal)
element in $S$ [2]. This regularizer favors the selection of contiguous
interval supports on a chain. Such structure is desirable, e.g., for time
series and cancer diagnosis [52]. This idea also extends to the selection of
rectangular supports in 2D and 3D. Here, $F$ is a normalized non-decreasing
$\tfrac{1}{d-1}$-weakly DR-submodular function [20].

Expensive feature cost: Given two, possibly overlapping, groups
$B_{1},B_{2}\subseteq V$ of expensive features, $F(S)=\lambda(|S|+C(S))$,
where

$C(S)=\begin{cases}a&\text{if either $S\cap B_{1}\not=\emptyset$ or $S\cap
B_{2}\not=\emptyset$ }\\\ b&\text{if $S\cap B_{1}\not=\emptyset$ and $S\cap
B_{2}\not=\emptyset$ }\\\ 0&\text{otherwise}\\\ \end{cases},$

where $0\leq 2a<b$ [54]. This regularizer favors the selection of sparse and
cheap features, and penalizes the use of both groups. Such structure is
desirable for example when predicting the status of patients from data
obtained via some medical tests; expensive features in this case are ones that
require burdensome tests. $F$ is a non-decreasing $\alpha$-weakly DR-
submodular function with $\alpha=\tfrac{1+a}{1+(b-a)}$. This regularizer also
extends to more groups of expensive features.

###  4.2 Structured batch Bayesian optimization

The goal in batch Bayesian optimization is to optimize an unknown expensive-
to-evaluate noisy function $f$ with as few batches of function evaluations as
possible [16, 26]. For example, evaluations can correspond to performing
expensive experiments. The evaluation points are chosen to maximize an
acquisition function subject to a cardinality constraint. Several acquisition
functions have been proposed for this purpose, amongst others the _variance
reduction_ function [39, 8]. This function is used to maximally reduce the
variance of the posterior distribution over potential maximizers of the
unknown function.

Often, the unknown $f$ is modeled by a Gaussian process with zero mean and
kernel function $k(\boldsymbol{x},\boldsymbol{x}^{\prime})$, and we observe
noisy evaluations $y=f(\boldsymbol{x})+{\epsilon}$ of the function, where
${\epsilon}\sim\mathcal{N}(0,\sigma^{2})$. Given a set
$\mathcal{X}=\\{\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{d}\\}$ of potential
maximizers of $f$, each $\boldsymbol{x}_{i}\in\mathbb{R}^{n}$, and a set
$S\subseteq V$, let $\boldsymbol{y}_{S}=[y_{i}]_{i\in S}$ be the corresponding
observations at points $x_{i},i\in S$. The posterior distribution of $f$ given
$\boldsymbol{y}_{S}$ is again a Gaussian process, with posterior covariance
$k_{S}(\boldsymbol{x},\boldsymbol{x}^{\prime})$, and variance
$\sigma_{S}^{2}(\boldsymbol{x})$:

$\displaystyle k_{S}(\boldsymbol{x},\boldsymbol{x}^{\prime})$
$\displaystyle=k(\boldsymbol{x},\boldsymbol{x}^{\prime})-\boldsymbol{k}_{S}(\boldsymbol{x})^{\top}(\boldsymbol{K}_{S}+\sigma^{2}\boldsymbol{I})^{-1}\boldsymbol{k}_{S}(\boldsymbol{x}^{\prime}),$
$\displaystyle\sigma^{2}_{S}(\boldsymbol{x})$
$\displaystyle=k_{S}(\boldsymbol{x},\boldsymbol{x}),$

where $\boldsymbol{k}_{S}=[k(\boldsymbol{x}_{i},\boldsymbol{x})]_{i\in S}$,
and $\boldsymbol{K}_{S}=[k(\boldsymbol{x}_{i},\boldsymbol{x}_{j})]_{i,j\in S}$
is the corresponding submatrix of the positive definite kernel matrix
$\boldsymbol{K}$. The variance reduction function is defined as:

$G(S)=\sum_{i\in
V}\sigma^{2}(\boldsymbol{x}_{i})-\sigma^{2}_{S}(\boldsymbol{x}_{i}),$

where
$\sigma^{2}(\boldsymbol{x}_{i})=k(\boldsymbol{x}_{i},\boldsymbol{x}_{i})$. We
show that the variance reduction function is weakly DR-modular.

######  Proposition 7.

The variance reduction function $G$ is non-decreasing $(\beta,\beta)$-weakly
DR-modular, with
$\beta=\frac{\lambda^{2}_{\min}(\boldsymbol{K})}{\lambda_{\max}(\boldsymbol{K})(\lambda_{\min}(\boldsymbol{K})+\sigma^{2})}$,
where $\lambda_{\max}(\boldsymbol{K})$ and $\lambda_{\min}(\boldsymbol{K})$
are the largest and smallest eigenvalues of $\boldsymbol{K}$.

To prove Proposition 7, we show that $G$ can be written as a noisy column
subset selection objective, and prove that such an objective function is
weakly DR-modular, generalizing the result of [57]. The proof is given in
Appendix A.4. The variance reduction function can thus be maximized with a
greedy algorithm to a $\beta$-approximation [57], which follows from a
stronger notion of approximate modularity.

Maximizing the variance reduction may also be phrased as an instance of
Problem (1), with $G$ being the variance reduction function, and
$F(S)=\lambda|S|$ an item-wise cost. This formulation easily allows to include
nonlinear costs with (weak) decrease in marginal costs (economies of scale).
For example, in the sensor placement application, the cost of placing a sensor
in a hazardous environment may diminish if other sensors are also placed in
similar environments. Unlike previous works, the approximation guarantee in
Corollary 1 still applies to such cost functions, while maintaining the
$\beta$-approximation with respect to $G$.

##  5 Experiments

We empirically validate our results on noisy submodular minimization and
structured sparse learning. In particular, we address the following questions:
(1) How robust are different submodular minimization algorithms, including
PGM, to multiplicative noise? (2) How well can PGM minimize a non-submodular
objective? Do the parameters $(\alpha,\beta)$ accurately characterize its
performance? All experiments were implemented in Matlab.

###  5.1 Noisy submodular minimization

First, we consider minimizing a submodular function $H$ given a noisy oracle
$\tilde{H}=\xi H$, where $\xi$ is independently drawn from a Gaussian
distribution with mean one and standard deviation $0.1$. In this setting, we
evaluate the performance of different submodular minimization algorithms, on
two example problems, minimum cut and clustering. We use the Matlab code from
http://www.di.ens.fr/~fbach/submodular/.

We compare seven submodular minimization algorithms: The minimum-norm-point
algorithm (MNP) [24], the conditional gradient method [37] with fixed step-
size (CG-$2/(t+2)$) and with line search (CG-LS), PGM with fixed step-size
(PGM-$1/\sqrt{t}$) and with the approximation of Polyak’s rule (PGM-polyak)
[5], the analytic center cutting plane method [25] (ACCPM) and a variant of it
that emulates the simplicial method (ACCPM-Kelley).

We replace the true oracle for $H$ by the approximate oracle
$\tilde{H}_{m}(S)=\tfrac{1}{m}\sum_{i=1}^{m}\xi_{i}H(S)$, for all these
algorithms. We test their performance on two datasets: “Genrmf-long”, which is
a min-cut/max-flow problem with $d=575$ and $2390$ edges, and “Two-moons”, a
synthetic semi-supervised clustering instance with $d=400$ data points and
$16$ labeled points. We refer the reader to [3, Sect. 12.1] for more details
about the algorithms and datasets. We stopped each algorithm after 1000
iterations for the first dataset and after 400 iterations for the second one,
or until the duality gap reached $10^{-8}$. To compute the optimal value
$H(S^{*})$, we use MNP with the noise-free oracle $H$ .

|  |
---|---|---
|  |
Figure 2:  Noisy submodular minimization results for “Genrmf-long” (top) and
“Two-moons” (bottom) data: Best achieved objective (log-scale) vs. number of
samples (left). Objective (log-scale) vs. iterations, for $m=50$ (middle),
$m=1000$ (right-top) and $m=150$ (right-bottom).

Figure 2 shows the gap in discrete objective value for all algorithms on the
two datasets, for increasing the number of samples $m$ (top), and for two
fixed values of $m$, as a function of iterations (middle and bottom). We plot
the best value achieved so far. As expected, the accuracy improves with more
samples. In fact, this improvement is faster than the bounds in Proposition 5
and in [7]. The objective function in the “Two-moons” dataset takes smaller
values, which makes it easier to solve in the multiplicative noise setting, as
we indeed observe. Among the compared algorithms, ACCPM and MNP converge
fastest, as also observed in [3] without noise, but they also seem to be the
most sensitive to noise. In summary, these empirical results suggest that
submodular minimization algorithms are indeed robust to noise, as predicted by
our theory.

###  5.2 Structured sparse learning

Our second set of experiments is structured sparse learning, where we aim to
estimate a sparse parameter vector
$\boldsymbol{x}^{\natural}\in\mathbb{R}^{d}$ whose support is an interval. The
range function $F^{r}(S)=\max(S)-\min(S)+1$ if $S\not=\emptyset$, and
$F^{r}(\emptyset)=0$, is a natural regularizer to choose. Recall that $F^{r}$
is $\tfrac{1}{d-1}$-weakly DR-submodular. Another reasonable regularizer is
the modified range function $F^{\mathrm{mr}}(S)=d-1+F^{r}(S),\forall
S\not=\emptyset$ and $F^{\mathrm{mr}}(\emptyset)=0$, which is non-decreasing
and submodular [2]. As discussed in Section 4.1, no existing method provides a
guaranteed approximate solution to Problem (4) with such regularizers, with
the exception of some statistical assumptions, under which
$\boldsymbol{x}^{\natural}$ can be recovered using the tightest convex
relaxation $\Theta^{r}$ of $F^{r}$ [20]. Evaluating $\Theta^{r}$ involves a
linear program with constraints corresponding to all possible interval sets,
such exhaustive search is not feasible in more complex settings.

We consider a simple regression setting in which
$\boldsymbol{x}^{\natural}\in\mathbb{R}^{d}$ has $k$ consecutive ones and is
zero otherwise. We observe noisy linear measurements
$\boldsymbol{y}=\boldsymbol{A}\boldsymbol{x}+\boldsymbol{\epsilon}$, where
$\boldsymbol{A}\in\mathbb{R}^{d\times n}$ is an i.i.d Gaussian matrix with
normalized columns and $\boldsymbol{\epsilon}\in\mathbb{R}^{n}$ is an i.i.d
Gaussian noise vector with standard deviation $0.01$. We set $d=250,k=20$ and
vary the number of measurements $n$ between $d/4$ and $2d$.

We compare the solutions obtained by minimizing the least squares loss
$\ell(\boldsymbol{x})=\frac{1}{2}\|\boldsymbol{y}-\boldsymbol{A}\boldsymbol{x}\|_{2}^{2}$
with the three regularizers: The range function $F^{r}$, where $H$ is
optimized via exhaustive search (OPT-Range), or via PGM (PGM-Range); the
modified range function $F^{\mathrm{mr}}$, solved via exhaustive search (OPT-
ModRange), or via PGM (PGM-ModRange); and the convex relaxation $\Theta^{r}$
(CR-Range), solved using CVX [27]. The marginal gains of $G^{\ell}$ (5) can be
efficiently computed using rank-1 updates of the pseudo-inverse [47].

|  |
---|---|---
|  |
Figure 3:  Structured sparsity results: Support and estimation errors (log-
scale) vs measurement ratio (left); objective and corresponding
$\alpha_{T},\beta_{T}$ parameters vs. regularization parameter for $n=112$
(middle) and $n=306$ (right).

Figure 3 (top) displays the best achieved support error in hamming distance,
and estimation error
$\|\hat{\boldsymbol{x}}-\boldsymbol{x}^{\natural}\|_{2}/\|\boldsymbol{x}^{\natural}\|_{2}$
on the regularization path, where $\lambda$ was varied between $10^{-4}$ and
$10$. Figure 3 (middle and bottom) illustrates the objective value $H=\lambda
F^{r}-G^{\ell}$ for PGM-Range, CR-Range, and OPT-Range, and $H=\lambda
F^{mr}-G^{\ell}$ for PGM-ModRange, and OPT-ModRange, and the corresponding
parameters $\alpha_{T},\beta_{T}$ defined in Remark 1, for two fixed values of
$n$. Results are averaged over $5$ runs.

We observe that PGM minimizes the objective with $F^{mr}$ almost exactly as
$n$ grows. It performs a bit worse with $F^{r}$, which is expected since
$F^{r}$ is not submodular. This is also reflected in the support and
estimation errors. Moreover, $\alpha_{T},\beta_{T}$ here reasonably predict
the performance of PGM; larger values correlate with closer to optimal
objective values. They are also more accurate than the worst case
$\alpha,\beta$ in Definition 1. Indeed, the $\alpha_{T}$ for the range
function is much larger than the worst case $\tfrac{1}{d-1}$. Similarly,
$\beta_{T}$ for $G^{\ell}$ is quite large and approaches 1 as $n$ grows, while
the worst case $\beta$ is only guaranteed to be non-zero when $\ell$ is
strongly convex, in Proposition 6. Finally, it is interesting that the convex
approach with $\Theta^{r}$ essentially matches the performance of OPT-Range
when $n\geq d$. In this regime, $G^{\ell}$ becomes nearly modular, hence the
convex objective $\ell+\lambda\Theta^{r}$ starts approximating the convex
closure of $\lambda F^{r}-G^{\ell}$.

##  6 Conclusion

We established new links between approximate submodularity and convexity,
which we used to analyze the performance of PGM. We thus provided the first
approximation guarantee for unconstrained, possibly noisy, non-submodular
minimization. This result significantly widens the range of applications where
submodular minimization techniques are applicable. We also provided a matching
lower bound showing the optimality of our approximation guarantee. We
experimentally validated our theory, and illustrated the robustness of
submodular minimization algorithms to noise and non-submodularity.

## Acknowledgments

This research was supported by a DARPA D3M award, NSF CAREER award 1553284,
and NSF award 1717610. The views, opinions, and/or findings contained in this
article are those of the author and should not be interpreted as representing
the official views or policies, either expressed or implied, of the Defense
Advanced Research Projects Agency or the Department of Defense. The authors
acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center
for providing HPC resources that have contributed to the research results
reported within this paper.

## References

  * [1] B. Axelrod, Y. P. Liu, and A. Sidford.  Near-optimal approximate discrete and continuous submodular function minimization.  arXiv preprint arXiv:1909.00171, 2019.
  * [2] F. Bach.  Structured sparsity-inducing norms through submodular functions.  In Proceedings of the International Conference on Neural Information Processing Systems, pages 118–126, 2010.
  * [3] F. Bach.  Learning with submodular functions: A convex optimization perspective.  Foundations and Trends® in Machine Learning, 6(2-3):145–373, 2013.
  * [4] W. Bai, R. Iyer, K. Wei, and J. Bilmes.  Algorithms for optimizing the ratio of submodular functions.  In Proceedings of the International Conference on Machine Learning, pages 2751–2759, 2016.
  * [5] D. P. Bertsekas.  Nonlinear programming.  Athena scientific, 1995.
  * [6] A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek.  Guarantees for greedy maximization of non-submodular functions with applications.  In Proceedings of the International Conference on Machine Learning, volume 70, pages 498–507. JMLR. org, 2017.
  * [7] E. Blais, C. L. Canonne, T. Eden, A. Levi, and D. Ron.  Tolerant junta testing and the connection to submodular optimization and function isomorphism.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 2113–2132. Society for Industrial and Applied Mathematics, 2018.
  * [8] I. Bogunovic, J. Scarlett, A. Krause, and V. Cevher.  Truncated variance reduction: A unified approach to bayesian optimization and level-set estimation.  In Proceedings of the International Conference on Neural Information Processing Systems, pages 1507–1515, 2016.
  * [9] I. Bogunovic, J. Zhao, and V. Cevher.  Robust maximization of non-submodular objectives.  In A. Storkey and F. Perez-Cruz, editors, Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 890–899. PMLR, 09–11 Apr 2018.
  * [10] Y. Boykov and V. Kolmogorov.  An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision.  IEEE Transactions on Pattern Analysis & Machine Intelligence, 26(9):1124–1137, 2004.
  * [11] Y. Boykov, O. Veksler, and R. Zabih.  Fast approximate energy minimization via graph cuts.  In Proceedings of the IEEE International Conference on Computer Vision, volume 1, pages 377–384. IEEE, 1999.
  * [12] S. Bubeck.  Theory of convex optimization for machine learning.  arXiv preprint arXiv:1405.4980, 15, 2014.
  * [13] D. Chakrabarty, Y. T. Lee, A. Sidford, and S. C.-w. Wong.  Subquadratic submodular function minimization.  In Proceedings of the ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1220–1231, New York, NY, USA, 2017. ACM.
  * [14] M. Conforti and G. Cornuéjols.  Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem.  Discrete applied mathematics, 7(3):251–274, 1984.
  * [15] A. Das and D. Kempe.  Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection.  arXiv preprint arXiv:1102.3975, 2011.
  * [16] T. Desautels, A. Krause, and J. W. Burdick.  Parallelizing exploration-exploitation tradeoffs in gaussian process bandit optimization.  Journal of Machine Learning Research, 15:4053–4103, 2014.
  * [17] S. Dughmi.  Submodular functions: Extensions, distributions, and algorithms. a survey.  arXiv preprint arXiv:0912.0322, 2009.
  * [18] J. Edmonds.  Submodular functions, matroids, and certain polyhedra.  In Combinatorial Optimization–Eureka, You Shrink!, pages 11–26. Springer, 2003.
  * [19] M. El Halabi.  Learning with Structured Sparsity: From Discrete to Convex and Back.  PhD thesis, Ecole Polytechnique Fédérale de Lausanne, 2018.
  * [20] M. El Halabi, F. Bach, and V. Cevher.  Combinatorial penalties: Structure preserved by convex relaxations.  Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018.
  * [21] M. El Halabi and V. Cevher.  A totally unimodular view of structured sparsity.  Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 223–231, 2015.
  * [22] E. R. Elenberg, R. Khanna, A. G. Dimakis, S. Negahban, et al.  Restricted strong convexity implies weak submodularity.  The Annals of Statistics, 46(6B):3539–3568, 2018.
  * [23] U. Feige, V. S. Mirrokni, and J. Vondrák.  Maximizing non-monotone submodular functions.  SIAM Journal on Computing, 40(4):1133–1153, 2011.
  * [24] S. Fujishige and S. Isotani.  A submodular function minimization algorithm based on the minimum-norm base.  Pacific Journal of Optimization, 7(1):3–17, 2011.
  * [25] J. L. Goffin and J. P. Vial.  On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm.  Mathematical Programming, 60(1):81–92, Jun 1993.
  * [26] J. González, Z. Dai, P. Hennig, and N. Lawrence.  Batch bayesian optimization via local penalization.  In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 648–657, 2016.
  * [27] M. Grant and S. Boyd.  CVX: Matlab software for disciplined convex programming, version 2.1.  http://cvxr.com/cvx, Mar. 2014.
  * [28] H. Hassani, M. Soltanolkotabi, and A. Karbasi.  Gradient methods for submodular maximization.  In Proceedings of the International Conference on Neural Information Processing Systems, pages 5843–5853, 2017.
  * [29] A. Hassidim and Y. Singer.  Submodular optimization under noise.  In S. Kale and O. Shamir, editors, Proceedings of the Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1069–1122, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR.
  * [30] A. Hassidim and Y. Singer.  Optimization for approximate submodularity.  In Proceedings of the International Conference on Neural Information Processing Systems, pages 394–405. Curran Associates Inc., 2018\.
  * [31] T. Horel and Y. Singer.  Maximization of approximately submodular functions.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Proceedings of the International Conference on Neural Information Processing Systems, pages 3045–3053. Curran Associates, Inc., 2016\.
  * [32] S. Iwata, L. Fleischer, and S. Fujishige.  A combinatorial strongly polynomial algorithm for minimizing submodular functions.  Journal of the ACM, 48(4):761–777, July 2001.
  * [33] S. Iwata and J. B. Orlin.  A simple combinatorial algorithm for submodular function minimization.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 1230–1237. Society for Industrial and Applied Mathematics, 2009.
  * [34] R. Iyer and J. Bilmes.  Algorithms for approximate minimization of the difference between submodular functions, with applications.  In Proceedings of the Conference on Uncertainty in Artificial Intelligence, UAI’12, pages 407–417, Arlington, Virginia, United States, 2012\. AUAI Press.
  * [35] R. Iyer, S. Jegelka, and J. Bilmes.  Monotone closure of relaxed constraints in submodular optimization: Connections between minimization and maximization.  In Proceedings of the Conference on Uncertainty in Artificial Intelligence, UAI’14, pages 360–369, Arlington, Virginia, United States, 2014\. AUAI Press.
  * [36] R. K. Iyer, S. Jegelka, and J. A. Bilmes.  Curvature and optimal algorithms for learning and minimizing submodular functions.  In Proceedings of the International Conference on Neural Information Processing Systems, pages 2742–2750, 2013.
  * [37] M. Jaggi.  Revisiting frank-wolfe: Projection-free sparse convex optimization.  In Proceedings of the International Conference on Machine Learning, pages 427–435, 2013.
  * [38] D. Kempe, J. Kleinberg, and É. Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of ACM SIGKDD international conference on Knowledge discovery and data mining (KDD), pages 137–146. ACM, 2003.
  * [39] 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(Feb):235–284, 2008.
  * [40] A. Kuhnle, J. D. Smith, V. G. Crawford, and M. T. Thai.  Fast maximization of non-submodular, monotonic functions on the integer lattice.  arXiv preprint arXiv:1805.06990, 2018.
  * [41] A. Kyrillidis, L. Baldassarre, M. El Halabi, Q. Tran-Dinh, and V. Cevher.  Structured Sparsity: Discrete and Convex Approaches, pages 341–387.  Springer International Publishing, Cham, 2015.
  * [42] Y. T. Lee, A. Sidford, and S. C.-w. Wong.  A faster cutting plane method and its implications for combinatorial and convex optimization.  In IEEE Annual Symposium on Foundations of Computer Science, pages 1049–1065. IEEE, 2015.
  * [43] B. Lehmann, D. Lehmann, and N. Nisan.  Combinatorial auctions with decreasing marginal utilities.  Games and Economic Behavior, 55(2):270–296, 2006.
  * [44] H. Lin and J. Bilmes.  An application of the submodular principal partition to training data subset selection.  In NIPS workshop on Discrete Optimization in Machine Learning, 2010\.
  * [45] H. Lin and J. Bilmes.  Optimal selection of limited vocabulary speech corpora.  In Conference of the International Speech Communication Association, 2011.
  * [46] L. Lovász.  Submodular functions and convexity, pages 235–257.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1983.
  * [47] C. D. Meyer, Jr.  Generalized inversion of modified matrices.  SIAM Journal on Applied Mathematics, 24(3):315–323, 1973.
  * [48] M. Narasimhan, N. Jojic, and J. A. Bilmes.  Q-clustering.  In Y. Weiss, B. Schölkopf, and J. C. Platt, editors, Proceedings of the International Conference on Neural Information Processing Systems, pages 979–986. MIT Press, 2006.
  * [49] G. Obozinski and F. Bach.  A unified perspective on convex structured sparsity: Hierarchical, symmetric, submodular norms and beyond.  working paper or preprint, Dec. 2016.
  * [50] C. Qian, J.-C. Shi, Y. Yu, K. Tang, and Z.-H. Zhou.  Optimizing ratio of monotone set functions.  In Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI’17, pages 2606–2612. AAAI Press, 2017.
  * [51] C. Qian, J.-C. Shi, Y. Yu, K. Tang, and Z.-H. Zhou.  Subset selection under noise.  In Proceedings of the International Conference on Neural Information Processing Systems, pages 3560–3570, 2017.
  * [52] F. Rapaport, E. Barillot, and J. Vert.  Classification of arraycgh data using fused svm.  Bioinformatics, 24(13):i375–i382, 2008.
  * [53] S. Sakaue.  Weakly modular maximization: Applications, hardness, tractability, and efficient algorithms.  arXiv preprint arXiv:1805.11251, 2018.
  * [54] S. Sakaue.  Greedy and iht algorithms for non-convex optimization with monotone costs of non-zeros.  In K. Chaudhuri and M. Sugiyama, editors, Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 206–215. PMLR, 16–18 Apr 2019.
  * [55] A. Schrijver.  A combinatorial algorithm minimizing submodular functions in strongly polynomial time.  Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000\.
  * [56] A. Singla, S. Tschiatschek, and A. Krause.  Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization.  In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI’16, pages 2037–2043. AAAI Press, 2016.
  * [57] M. Sviridenko, J. Vondrák, and J. Ward.  Optimal approximation for submodular and supermodular optimization with bounded curvature.  Mathematics of Operations Research, 42(4):1197–1218, 2017.
  * [58] Z. Svitkina and L. Fleischer.  Submodular approximation: Sampling-based algorithms and lower bounds.  SIAM Journal on Computing, 40(6):1715–1737, 2011.
  * [59] L. Trevisan.  Inapproximability of combinatorial optimization problems.  arXiv preprint cs/0409043, 2004.
  * [60] J. Vondrák.  Submodularity in combinatorial optimization.  PhD thesis, Charles University, 2007.
  * [61] Y.-J. Wang, D.-C. Xu, Y.-J. Jiang, and D.-M. Zhang.  Minimizing ratio of monotone non-submodular functions.  Journal of the Operations Research Society of China, Mar 2019.

##  Appendix A Appendix

###  A.1 Extension to constrained minimization

Our result directly implies a generalization of some approximation guarantees
of constrained submodular minimization to constrained weakly DR-submodular
minimization. In particular, we consider the problem

$\min_{S\in\mathcal{C}}F(S),$ (6)

where $F$ is a monotone $\alpha$-weakly DR-submodular function and
$\mathcal{C}$ denotes a family of feasible sets. We note that Theorem 1 still
holds in this setting, if we project the iterates onto the convex hull
$\mathrm{conv}(\mathcal{C})$ of $\mathcal{C}$. We can thus obtain a solution
$\hat{\boldsymbol{s}}\in\mathrm{conv}(\mathcal{C})$ such that
$f_{L}(\hat{\boldsymbol{s}})\leq\frac{F(S^{*})}{\alpha}+\epsilon$ where
$S^{*}$ is the optimal solution of (6). However, the rounding in Corollary 1
does not hold anymore, since not all sup-level sets of $\hat{\boldsymbol{s}}$
will be feasible.

One rounding approach proposed in [35] is to simply pick the smallest feasible
sup-level set. Given $\boldsymbol{s}\in[0,1]^{d}$, we pick the largest
$\theta\in[0,1]$ such that
$S_{\theta}=\\{s_{i}:s_{i}\geq\theta\\}\in\mathcal{C}$. The obtained set would
then satisfy $F(S_{\theta})\leq\frac{1}{\theta}f_{L}(\boldsymbol{s})$.
Applying this rounding to $\hat{\boldsymbol{s}}$, we obtain
$F(\hat{S}_{\theta})\leq\frac{1}{\alpha\theta}F(S^{*})+\epsilon$. In general
there is no guarantee that $\theta\not=0$. But for certain constraints, such
as matroid, cut and set cover constraints, Iyer et al. [35] show that $\theta$
admits non-zero bounds (see Table 2 in [35]).

###  A.2 Proofs for Section 3

See 2

###### Proof.

$g$ is a concave function, since $a<0$, hence $G^{\prime}(S)$ is submodular.
It also follows that

$\displaystyle\max_{i\in V,S\subseteq T\subseteq V\setminus
i}\frac{G^{\prime}(i|S)}{G^{\prime}(i|T)}$ $\displaystyle=\max_{i\in
V,S\subseteq T\subseteq V\setminus
i}\frac{G^{\prime}(i)}{G^{\prime}(i|V\setminus i)}$
$\displaystyle=\frac{\tfrac{1}{2}a+(1-\tfrac{1}{2}a)}{\tfrac{1}{2}a(d^{2}-(d-1)^{2})+(1-\tfrac{1}{2}a)(d-(d-1))}$
$\displaystyle=\frac{1}{\tfrac{1}{2}a(2d-2)+1}$
$\displaystyle=\frac{1}{\beta}.$

We also have

$\displaystyle\epsilon_{G^{\prime}}$ $\displaystyle=\min_{i\in V,S\subset
T\subseteq V\setminus i}G^{\prime}(i|S)-G^{\prime}(i|T)$
$\displaystyle=\min_{T\subset V}2g(|T|)-g(|T|-1)-g(|T|+1)$
$\displaystyle=\min_{T\subset
V}\tfrac{1}{2}a(2|T|^{2}-(|T|-1)^{2}-(|T|+1)^{2})+(1-\tfrac{1}{2}a)(2|T|-(|T|-1)-(|T|+1))$
$\displaystyle=-a.$

∎

See 1

###### Proof.

Given any feasible point $(\boldsymbol{\kappa}^{\prime},\rho^{\prime})$ in the
definition of $h^{-}$, i.e., $\boldsymbol{\kappa}(A)+\rho^{\prime}\leq
H(A),\forall A\subseteq V$, we have:

$\displaystyle\boldsymbol{\kappa}^{\top}\boldsymbol{s}-(\boldsymbol{\kappa}^{\prime\top}\boldsymbol{s}+\rho^{\prime})$
$\displaystyle=\sum_{k=1}^{d}s_{j_{k}}(H(j_{k}|S_{k-1})-\kappa^{\prime}_{j_{k}})-\rho^{\prime}$
$\displaystyle=\sum_{k=1}^{d-1}(s_{j_{k}}-s_{j_{k+1}})\left(H(S_{k})-\boldsymbol{\kappa}^{\prime}(S_{k})\right)+s_{j_{d}}\left(H(V)-\boldsymbol{\kappa}^{\prime}(V)\right)-\rho^{\prime}$
$\displaystyle\geq\left(\sum_{k=1}^{d-1}(s_{j_{k}}-s_{j_{k+1}})+s_{j_{d}}\right)\rho^{\prime}-\rho^{\prime}$
$\displaystyle=(s_{j_{1}}-1)\rho^{\prime}\geq 0$

Hence $\boldsymbol{\kappa}^{\top}\boldsymbol{s}\geq h^{-}(\boldsymbol{s})$.
The last inequality holds by noting that $\rho^{\prime}\leq 0$ since
$\boldsymbol{\kappa}(\emptyset)+\rho^{\prime}\leq H(\emptyset)=0$.

The upper bound on $\boldsymbol{\kappa}(A)$ for any $A\subseteq V$ follows
from the definition of weak DR-submodularity.

$\displaystyle\boldsymbol{\kappa}(A)$ $\displaystyle=\sum_{j_{k}\in
A}H(j_{k}|S_{k-1})$ $\displaystyle\leq\sum_{j_{k}\in
A}\frac{1}{\alpha}F(j_{k}|A\cap S_{k-1})-\beta G(j_{k}|A\cap S_{k-1})$
$\displaystyle=\sum_{k=1}^{d}\frac{1}{\alpha}(F(A\cap S_{k})-F(A\cap
S_{k-1}))-\beta(G(A\cap S_{k})-G(A\cap S_{k-1}))$
$\displaystyle=\frac{F(A)}{\alpha}-\beta G(A)$

Note that $\boldsymbol{\kappa}$ can be written as
$\boldsymbol{\kappa}=\boldsymbol{\kappa}^{F}-\boldsymbol{\kappa}^{G}$ where
$\boldsymbol{\kappa}^{F}_{j_{k}}=F(j_{k}|S_{k-1})$ and
$\boldsymbol{\kappa}^{G}_{j_{k}}=G(j_{k}|S_{k-1})$. We have
$\boldsymbol{\kappa}^{F}(A)\leq\frac{F(A)}{\alpha}$ and
$\boldsymbol{\kappa}^{G}(A)\leq\beta G(A),\forall A\subseteq V$. Hence
$(\alpha\boldsymbol{\kappa}^{F},\boldsymbol{0})$ and
$(\frac{1}{\beta}\boldsymbol{\kappa}^{G},\boldsymbol{0})$ are feasible points
in the definitions of $f^{-}$ and $(-g)^{-}$. The bound on
$\boldsymbol{\kappa}^{\top}\boldsymbol{s}^{\prime}$ for any
$\boldsymbol{s}^{\prime}\in[0,1]^{d}$ then follows directly from the
definitions of $f^{-}$ and $(-g)^{-}$ (3). ∎

See 1

###### Proof.

Let $\boldsymbol{z}^{t+1}=\boldsymbol{s}^{t}-\eta\boldsymbol{\kappa}^{t}$,
then note that
$\|\boldsymbol{s}^{t+1}-\boldsymbol{s}^{*}\|_{2}\leq\|\boldsymbol{z}^{t+1}-\boldsymbol{s}^{*}\|_{2}$
due to the properties of projection (see for e.g., [12, Lemma 3.1]), it
follows then

$\displaystyle\langle\boldsymbol{\kappa}^{t},\boldsymbol{s}^{t}-\boldsymbol{s}^{*}\rangle$
$\displaystyle=\frac{1}{\eta}\langle\boldsymbol{s}^{t}-\boldsymbol{z}^{t+1},\boldsymbol{s}^{t}-\boldsymbol{s}^{*}\rangle$
$\displaystyle=\frac{1}{2\eta}(\|\boldsymbol{s}^{t}-\boldsymbol{z}^{t+1}\|_{2}^{2}+\|\boldsymbol{s}^{t}-\boldsymbol{s}^{*}\|_{2}^{2}-\|\boldsymbol{z}^{t+1}-\boldsymbol{s}^{*}\|_{2}^{2})$
$\displaystyle=\frac{1}{2\eta}(\|\boldsymbol{s}^{t}-\boldsymbol{s}^{*}\|_{2}^{2}-\|\boldsymbol{z}^{t+1}-\boldsymbol{s}^{*}\|_{2}^{2})+\frac{\eta}{2}\|\boldsymbol{\kappa}^{t}\|_{2}^{2}$
$\displaystyle\leq\frac{1}{2\eta}(\|\boldsymbol{s}^{t}-\boldsymbol{s}^{*}\|_{2}^{2}-\|\boldsymbol{s}^{t+1}-\boldsymbol{s}^{*}\|_{2}^{2})+\frac{\eta}{2}\|\boldsymbol{\kappa}^{t}\|_{2}^{2}$

Summing over $t$ we get

$\displaystyle\sum_{t=1}^{T}\langle\boldsymbol{\kappa}^{t},\boldsymbol{s}^{t}-\boldsymbol{s}^{*}\rangle$
$\displaystyle\leq T\frac{R^{2}}{2\eta}+\frac{\eta TL^{2}}{2}$

Since $F$ is $\alpha$-weakly DR submodular and $-G$ is
$\frac{1}{\beta}$-weakly DR submodular, we have by lemma 1 for all $t$,
$(\boldsymbol{\kappa}^{t})^{\top}\boldsymbol{s}^{*}\leq\frac{f^{-}(\boldsymbol{s}^{*})}{\alpha}+\beta(-g)^{-}(\boldsymbol{s}^{*})$
and
$(\boldsymbol{\kappa}^{t})^{\top}\boldsymbol{s}^{t}=h_{L}(\boldsymbol{s}^{t})\geq
h^{-}(\boldsymbol{s}^{t})$. Plugging in the value of $\eta$, we thus obtain

$\min_{t}h^{-}(\boldsymbol{s}^{t})\leq\min_{t}h_{L}(\boldsymbol{s}^{t})\leq\frac{f^{-}(\boldsymbol{s}^{*})}{\alpha}+\beta(-g)^{-}(\boldsymbol{s}^{*})+\frac{RL}{\sqrt{T}}.$

∎

See 3

###### Proof.

We define

$F(S)=\begin{cases}|S|+\tfrac{d}{\beta}-1&\text{if $1\in S$}\\\
\alpha|S|&\text{ otherwise}\end{cases},\text{ and
}G(S)=\begin{cases}|S|+\tfrac{d}{\beta}-1&\text{if $1\in S$}\\\
\tfrac{1}{\beta}|S|&\text{ otherwise}\end{cases}.$

It’s easy to see that both $F$ and $G$ are monotone functions. For all
$A\subseteq B,i\in V\setminus B$, we have

$\displaystyle\frac{F(i|A)}{F(i|B)}=\begin{cases}1&\text{if $1\in A$ or
$1\not\in B$}\\\ \alpha&\text{if $1\not\in A,1\in B$}\\\
\frac{\frac{d}{\beta}+(1-\alpha)|A|}{\frac{d}{\beta}+(1-\alpha)|B|}&\text{if
$i=1$}\\\ \end{cases}$

Note that
$\frac{d}{\beta}+(1-\alpha)|A|\geq\frac{d}{\beta}\geq\alpha(\frac{d}{\beta}+(1-\alpha)|B|)$,
hence $\alpha\leq\frac{F(i|A)}{F(i|B)}\leq 1$, which proves that $F$ is
supermodular and $\alpha$-weakly DR-submodular.

Similarly we have

$\displaystyle\frac{F(i|A)}{F(i|B)}=\begin{cases}1&\text{if $1\in A$ or
$1\not\in B$}\\\ \frac{1}{\beta}&\text{if $1\not\in A,1\in B$}\\\
\frac{\frac{d}{\beta}+(1-\frac{1}{\beta})|A|}{\frac{d}{\beta}+(1-\frac{1}{\beta})|B|}&\text{if
$i=1$}\\\ \end{cases}$

Note that
$\frac{d}{\beta}+(1-\frac{1}{\beta})|A|\leq\frac{d}{\beta}\leq\frac{1}{\beta}(\frac{d}{\beta}+(1-\frac{1}{\beta})|B|)$,
hence $1\leq\frac{F(i|A)}{F(i|B)}\leq\frac{1}{\beta}$, which proves that $G$
is monotone submodular and $\beta$-weakly DR-supermodular.

It remains to show that the solution obtained by projected subgradient method
and thresholding have value $H(\hat{S})=0$. We can assume w.l.o.g that the
starting point $\boldsymbol{s}^{1}$ is such that the largest element is
$j_{1}=1$ (otherwise we can modify the example to have whatever is the largest
element as the “bad element”). Note that $H(1)=H(j_{k}|S_{k})=0$ for all
$k\in[d]$, hence $\boldsymbol{\kappa}^{1}=\mathbf{0}$ and
$\boldsymbol{s}^{t}=\boldsymbol{s}^{1}$ and
$\boldsymbol{\kappa}^{t}=\mathbf{0}$ for all $t\in\\{1,\cdots,T\\}$.
Thresholding $\boldsymbol{s}^{1}$ would thus yield $H(\hat{S})=0$, with
$\hat{S}=\emptyset$ or any other set such that $1\in\hat{S}$. ∎

See 4

###### Proof.

We define $\boldsymbol{\kappa}$ as $\kappa_{j_{k}}=H(j_{k}|S_{k-1})$ and
$\tilde{\boldsymbol{\kappa}}$ as
$\tilde{\kappa}_{j_{k}}=\tilde{H}(j_{k}|S_{k-1})$ for any ordering on $V$. For
all $k\in V$, we have $|\tilde{\kappa}_{j_{k}}-\kappa_{j_{k}}|\leq 2\epsilon$
with probability $1-2d\delta$ (by a union bound), hence
$|\boldsymbol{\tilde{\kappa}}(S^{*})-\boldsymbol{\kappa}(S^{*})|\leq
2\epsilon|S^{*}|$. Plugging this into the proofs of Theorem 1 and Corollary 1
yields $H(\hat{S})\leq\tfrac{1}{\alpha}F(S^{*})-\beta
G(S^{*})+2\epsilon(|S^{*}|+1)+\tfrac{RL}{\sqrt{T}},$ with probability
$1-2dT\delta$ (by a union bound). The proposition follows by setting
$\epsilon,\delta$ and $T$ to the chosen values. ∎

###  A.3 Proofs for Section 4.1

We prove Proposition 6 under a more general setting where $\ell$ has
$\nu$-restricted smoothness (RSM) and $\mu$-restricted strong convexity (RSC).
Let’s recall the definition of RSC/RSM.

######  Definition 3 (RSM/RSC).

Given a differentiable function $\ell:\mathbb{R}^{d}\to\mathbb{R}$ and
$\Omega\subset\mathbb{R}^{d}\times\mathbb{R}^{d}$, $\ell$ is
$\mu_{\Omega}$-RSC and $\nu_{\Omega}$-RSM if
$\frac{\mu_{\Omega}}{2}\|\boldsymbol{x}-\boldsymbol{y}\|_{2}^{2}\leq\ell(\boldsymbol{y})-\ell(\boldsymbol{x})-\langle\nabla\ell(\boldsymbol{x}),\boldsymbol{y}-\boldsymbol{x}\rangle\leq\frac{\nu_{\Omega}}{2}\|\boldsymbol{x}-\boldsymbol{y}\|_{2}^{2},\;\;\forall(\boldsymbol{x},\boldsymbol{y})\in\Omega.$

If $\ell$ is RSC/RSM on
$\Omega=\\{(\boldsymbol{x},\boldsymbol{y}):\|\boldsymbol{x}\|_{0}\leq
k_{1},\|\boldsymbol{y}\|_{0}\leq
k_{1},\|\boldsymbol{x}-\boldsymbol{y}\|_{0}\leq k_{2}\\}$, we denote by
$\mu_{k_{1},k_{2}},\nu_{k_{1},k_{2}}$ the corresponding RSC and RSM
parameters. For simplicity, we also define
$\mu_{k}:=\mu_{k,k},\nu_{k}:=\mu_{k,k}$.

Before we can prove Proposition 6, we need two key lemmas. Lemma 2 restates a
result from [22], which relates the marginal gain of $G^{\ell}$ to the
marginal decrease in $\ell$. In Lemma 3, we argue that for a class of loss
functions, namely RSC/RSM functions of the form
$\ell(\boldsymbol{x})=L(\boldsymbol{x})-\boldsymbol{z}^{\top}\boldsymbol{x}$,
where $\boldsymbol{z}$ is a random vector, the corresponding minimizer has
full support with probability one. Proposition 8 then follows from these two
lemmas by noting that $\ell$ thus have non-zero marginal decrease, with
respect to any $i\in V$, with probability one.

######  Lemma 2.

Given $G^{\ell}(S)=\ell(0)-\min_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\ell(\boldsymbol{x})$, then for any disjoint sets $A,B\subseteq V$ and a
corresponding minimizer
$\boldsymbol{x}^{A}:=\operatorname*{arg\,min}_{\mathrm{supp}(\boldsymbol{x})\subseteq
A}\ell(\boldsymbol{x})$, if $\ell$ is $\mu_{|A\cup B|}$-RSC and
$\nu_{|A|,|B|}$-RSM, we have:

$\frac{\|[\nabla\ell(\boldsymbol{x}^{A})]_{B}\|_{2}^{2}}{2\nu_{|A\cup
B|,|B|}}\leq
G^{\ell}(B|A)\leq\frac{\|[\nabla\ell(\boldsymbol{x}^{A})]_{B}\|_{2}^{2}}{2\mu_{|A\cup
B|}}$

######  Lemma 3.

If $\boldsymbol{x}^{\star}$ is the minimizer of
$\min_{x\in\mathbb{R}^{d}}L(\boldsymbol{x})-\boldsymbol{z}^{\top}\boldsymbol{x}$,
where $L$ is a strongly-convex and smooth loss function, and
$\boldsymbol{z}\in\mathbb{R}^{d}$ has a continuous density w.r.t to the
Lebesgue measure, then $\boldsymbol{x}^{\star}$ has full support with
probability one.

###### Proof.

This follows directly from [20, Theorem 1] by taking $\Phi(x)=0$. We include
the proof here for completeness.

Since $L$ is strongly-convex, given $\boldsymbol{z}$ the corresponding
minimizer $\boldsymbol{x}^{\star}$ is unique, then the function
$E(\boldsymbol{z}):=\operatorname*{arg\,min}_{\boldsymbol{x}\in\mathbb{R}^{d}}L(\boldsymbol{x})-\boldsymbol{z}^{T}\boldsymbol{x}$
is well defined. Given fixed $i\in V$, we show that the set
$S_{i}:=\\{\boldsymbol{z}:[E(\boldsymbol{z})]_{i}=0\\}$ has measure zero.
Then, taking the union of the finitely many sets $S_{i},\forall i\in V$, all
of zero measure, we have $P(\exists\boldsymbol{z}\in\mathbb{R}^{d},\exists
i\in V,\text{ s.t., }[E(\boldsymbol{z})]_{i}=0)=0$.

To show that the set $S_{i}$ has measure zero, let
$\boldsymbol{z}_{1},\boldsymbol{z}_{2}\in S_{i}$ and denote by $\mu>0$ the
strong convexity constant of $L$. We have by optimality conditions:

$\Big{(}\big{(}\boldsymbol{z}_{1}-\nabla
L(E(\boldsymbol{z}_{1}))\big{)}-\big{(}\boldsymbol{z}_{2}-\nabla
L(E(\boldsymbol{z}_{2}))\big{)}\Big{)}^{\top}\Big{(}E(\boldsymbol{z}_{1})-E(\boldsymbol{z}_{2})\Big{)}=0$

Hence,

$\displaystyle(\boldsymbol{z}_{1}-\boldsymbol{z}_{2})^{\top}(E(\boldsymbol{z}_{1})-E(\boldsymbol{z}_{2}))$
$\displaystyle\geq\big{(}\nabla L(E(\boldsymbol{z}_{1}))-\nabla
L(E(\boldsymbol{z}_{2}))\big{)}^{\top}\big{(}E(\boldsymbol{z}_{1})-E(\boldsymbol{z}_{2})\big{)}$
$\displaystyle(\boldsymbol{z}_{1}-\boldsymbol{z}_{2})^{\top}(E(\boldsymbol{z}_{1})-E(\boldsymbol{z}_{2}))$
$\displaystyle\geq\mu\|E(\boldsymbol{z}_{1})-E(\boldsymbol{z}_{2})\|_{2}^{2}$
$\displaystyle\frac{1}{\mu}\|\boldsymbol{z}_{1}-\boldsymbol{z}_{2}\|_{2}$
$\displaystyle\geq\|E(\boldsymbol{z}_{1})-E(\boldsymbol{z}_{2})\|_{2}$

Thus $E$ is a deterministic Lipschitz-continuous function of $\boldsymbol{z}$.
By optimality conditions $\boldsymbol{z}=\nabla L(E(\boldsymbol{z}))$, then
$z_{i}=\nabla L(E(\boldsymbol{z}_{V\setminus i}))_{i}$. Thus $z_{i}$ is a
Lipschitz-continuous function of $\boldsymbol{z}_{V\setminus i}$, which can
only happen with zero measure. ∎

######  Proposition 8.

Let
$\ell(\boldsymbol{x})=L(\boldsymbol{x})-\boldsymbol{z}^{\top}\boldsymbol{x}$,
where $L$ is $\mu_{|U|}$-RSC and $\nu_{|U|}$-RSM for some $U\subseteq V$ and
$\boldsymbol{z}\in\mathbb{R}^{d}$ has a continuous density w.r.t the Lebesgue
measure. Then there exist $\alpha_{G},\beta_{G}>0$ such that $G^{\ell}$ is
$(\alpha_{G},\beta_{G})$-weakly DR modular on $U$ (i.e., Def. 1 restricted to
sets $A\subseteq B\subseteq U$).

###### Proof.

Given $i\in U,A\subseteq U\setminus i$, let
$\boldsymbol{x}^{A}:=\operatorname*{arg\,min}_{\mathrm{supp}(\boldsymbol{x})\subseteq
A}\ell(\boldsymbol{x})$, then by Lemma 2 and $\nu_{|A|+1,1}\leq\nu_{|A|+1}$ we
have:

$\displaystyle\frac{[\nabla\ell(\boldsymbol{x}^{A})]_{i}^{2}}{2\nu_{|A|+1}}$
$\displaystyle\leq
G^{\ell}(i|A)\leq\frac{[\nabla\ell(\boldsymbol{x}^{A})]_{i}^{2}}{2\mu_{|A|+1}}$

We argue that $[\nabla\ell(x^{A})]_{i}^{2}\not=0$ with probability one. For
that, we define $\ell_{A}(\boldsymbol{u}):=\ell(\boldsymbol{x})$, where
$[\boldsymbol{x}]_{A}=\boldsymbol{u},[\boldsymbol{x}]_{V\setminus
A}=0,\forall\boldsymbol{u}\in\mathbb{R}^{|A|}$, then $\ell_{A}$ is
$\mu_{|A|}$-strongly convex and $\nu_{|A|}$-smooth on $\mathbb{R}^{|A|}$.
Hence, by lemma 3, the minimizer $\boldsymbol{u}^{\star}$ of $\ell_{A}$ has
full support with probability one, and thus
$\mathrm{supp}(\boldsymbol{x}^{A})=A$ also with probability one. By the same
argument, we have $\mathrm{supp}(\boldsymbol{x}^{A\cup\\{i\\}})=A\cup\\{i\\}$.
We can thus deduce that $[\nabla\ell(x^{A})]_{i}^{2}\not=0$, since otherwise
$G^{\ell}(i|A)=0$, which implies that $\boldsymbol{x}^{A\cup\\{i\\}}=x^{A}$
(minimizer is unique) and $\mathrm{supp}(\boldsymbol{x}^{A\cup\\{i\\}})=A$,
which happens with probability zero.

For all $i\in U,A,B\subseteq U\setminus i$, the following bounds hold:

$\frac{\mu_{|B|+1}[\nabla\ell(\boldsymbol{x}^{A})]_{i}^{2}}{\nu_{|A|+1}[\nabla\ell(\boldsymbol{x}^{B})]_{i}^{2}}\leq\frac{G^{\ell}(i|A)}{G^{\ell}(i|B)}\leq\frac{\nu_{|B|+1}[\nabla\ell(\boldsymbol{x}^{A})]_{i}^{2}}{\mu_{|A|+1}[\nabla\ell(\boldsymbol{x}^{B})]_{i}^{2}}$

$G^{\ell}$ is then $(\alpha_{G},\beta_{G})$-weakly DR-modular with
$\alpha_{G}:=\min_{A\subseteq B\subseteq U,i\in U\setminus
B}\frac{\mu_{|B|+1}[\nabla\ell(\boldsymbol{x}^{A})]_{i}^{2}}{\nu_{|A|+1}[\nabla\ell(\boldsymbol{x}^{B})]_{i}^{2}}>0$
and $\beta_{G}:=\min_{A\subseteq B\subseteq U,i\in U\setminus
B}\frac{\mu_{|A|+1}[\nabla\ell(\boldsymbol{x}^{B})]_{i}^{2}}{\nu_{|B|+1}[\nabla\ell(\boldsymbol{x}^{A})]_{i}^{2}}>0$.
∎

###  A.4 Proofs for Section 4.2

To prove Proposition 7, we first show that the objective in noisy column
subset selection problems is weakly DR-modular, generalizing the result of
[57]. We then show that the variance reduction function can be written as a
noisy column subset selection objective.

We start by giving explicit expressions for the marginals of the objective in
noisy column subset selection problems.

######  Proposition 9.

Let
$\ell(\boldsymbol{x}):=\frac{1}{2}\|\boldsymbol{y}-\boldsymbol{A}\boldsymbol{x}\|_{2}^{2}+\frac{\sigma^{2}}{2}\|\boldsymbol{x}\|^{2}$
for some $\sigma\geq 0$ and
$G(S)=\ell(0)-\min_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\ell(\boldsymbol{x})$, then

$\displaystyle G(i|S)$ $\displaystyle=[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]^{2}_{i}~{}\phi(S,i)=\Bigl{(}\frac{\boldsymbol{y}^{\top}R^{S}(\boldsymbol{a}_{i})}{2\sqrt{\phi(S,i)}}\Bigl{)}^{2},$

where $\boldsymbol{a}_{i}$ is the ith column of $\boldsymbol{A}$,
$\boldsymbol{x}^{S}(\boldsymbol{a}_{i}):=\operatorname*{arg\,min}_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\frac{1}{2}\|\boldsymbol{a}_{i}-\boldsymbol{A}\boldsymbol{x}\|_{2}^{2}+\frac{\sigma^{2}}{2}\|\boldsymbol{x}\|^{2}$
is the vector of optimal regression coefficients,
$R^{S}(\boldsymbol{a}_{i})=\boldsymbol{a}_{i}-\boldsymbol{A}\boldsymbol{x}^{S}(\boldsymbol{a}_{i})$
the corresponding residual, and
$\phi(S,i)=\frac{1}{2}\|R^{S}(\boldsymbol{a}_{i})\|^{2}+\frac{\sigma^{2}}{2}\|\boldsymbol{x}^{S}(\boldsymbol{a}_{i})\|^{2}+\frac{\sigma^{2}}{2}$.

###### Proof.

Given $i\in V,S\subseteq V\setminus i$, let
$\boldsymbol{x}^{S}(\boldsymbol{y}):=\operatorname*{arg\,min}_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\ell(\boldsymbol{x})$, and
$R^{S}(\boldsymbol{y})=\boldsymbol{y}-\boldsymbol{A}\boldsymbol{x}^{S}(\boldsymbol{y})$
the corresponding residual. Let $\gamma=[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{i}$, then we can write

$\displaystyle\boldsymbol{y}$
$\displaystyle=\boldsymbol{A}\boldsymbol{x}^{S\cup i}(\boldsymbol{y})+R^{S\cup
i}(\boldsymbol{y})$ $\displaystyle=\boldsymbol{A}_{S}[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+\boldsymbol{a}_{i}\gamma+R^{S\cup i}(\boldsymbol{y})$
$\displaystyle=\boldsymbol{A}_{S}([\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+\gamma\boldsymbol{x}^{S}(\boldsymbol{a}_{i}))+\gamma
R^{S}(\boldsymbol{a}_{i})+R^{S\cup i}(\boldsymbol{y})$

By optimality conditions we have $-\boldsymbol{A}_{S\cup i}^{\top}R^{S\cup
i}(\boldsymbol{y})+\sigma^{2}\boldsymbol{x}^{S\cup i}(\boldsymbol{y})=0$ and
$-\boldsymbol{A}_{S}^{\top}R^{S}(\boldsymbol{a}_{i})+\sigma^{2}\boldsymbol{x}^{S}(\boldsymbol{a}_{i})=0$.
Let $\hat{\boldsymbol{x}}^{S}(\boldsymbol{y})=[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+\gamma\boldsymbol{x}^{S}(\boldsymbol{a}_{i})$, then
$\hat{\boldsymbol{x}}^{S}(\boldsymbol{y})$ satisfies the constraint
$\mathrm{supp}(\hat{\boldsymbol{x}}^{S}(\boldsymbol{y}))=S$ and the optimality
condition
$\boldsymbol{A}_{S}^{\top}(\boldsymbol{A}_{S}\hat{\boldsymbol{x}}^{S}(\boldsymbol{y})-\boldsymbol{y})+\sigma^{2}\hat{\boldsymbol{x}}^{S}(\boldsymbol{y})=0$.
We can see this by plugging in the expression for $\boldsymbol{y}$ and using
the optimality conditions on $\boldsymbol{x}^{S\cup i}(\boldsymbol{y})$ and
$\boldsymbol{x}^{S}(\boldsymbol{a}_{i})$.

$\displaystyle\boldsymbol{A}_{S}^{\top}(\boldsymbol{A}_{S}\hat{\boldsymbol{x}}^{S}(\boldsymbol{y})-\boldsymbol{y})+\sigma^{2}\hat{\boldsymbol{x}}^{S}(\boldsymbol{y})$
$\displaystyle=-\boldsymbol{A}_{S}^{\top}(\gamma
R^{S}(\boldsymbol{a}_{i})+R^{S\cup
i}(\boldsymbol{y}))+\sigma^{2}([\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+\gamma\boldsymbol{x}^{S}(\boldsymbol{a}_{i}))=0$

Hence
$\hat{\boldsymbol{x}}^{S}(\boldsymbol{y})={\boldsymbol{x}}^{S}(\boldsymbol{y})$.
By the optimality condition on $\boldsymbol{x}^{S\cup i}(\boldsymbol{y})$, we
also have

$\displaystyle R^{S}(\boldsymbol{a}_{i})^{\top}R^{S\cup i}(\boldsymbol{y})$
$\displaystyle=\boldsymbol{a}_{i}^{\top}R^{S\cup
i}(\boldsymbol{y})-\boldsymbol{x}^{S}(\boldsymbol{a}_{i})^{\top}\boldsymbol{A}_{S}^{\top}R^{S\cup
i}(\boldsymbol{y})$
$\displaystyle=\sigma^{2}\gamma-\sigma^{2}\boldsymbol{x}^{S}(\boldsymbol{a}_{i})^{\top}[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}$

The marginals are thus given by

$\displaystyle G(i|S)$
$\displaystyle=\ell({\boldsymbol{x}}^{S}(\boldsymbol{y}))-\ell(\boldsymbol{x}^{S\cup
i}(\boldsymbol{y}))$ $\displaystyle=\frac{1}{2}\|\gamma
R^{S}(\boldsymbol{a}_{i})+R^{S\cup
i}(\boldsymbol{y})\|_{2}^{2}+\frac{\sigma^{2}}{2}\|[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+\gamma\boldsymbol{x}^{S}(\boldsymbol{a}_{i})\|^{2}-\frac{1}{2}\|R^{S\cup
i}(\boldsymbol{y})\|_{2}^{2}-\frac{\sigma^{2}}{2}\|\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})\|^{2}$
$\displaystyle=\frac{\gamma^{2}}{2}\|R^{S}(\boldsymbol{a}_{i})\|^{2}+\sigma^{2}\gamma^{2}-\sigma^{2}\gamma\boldsymbol{x}^{S}(\boldsymbol{a}_{i})^{\top}[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+\frac{\sigma^{2}}{2}\gamma^{2}\|\boldsymbol{x}^{S}(\boldsymbol{a}_{i})\|^{2}+\sigma^{2}\gamma\boldsymbol{x}^{S}(\boldsymbol{a}_{i})^{\top}[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}-\frac{\sigma^{2}}{2}\gamma^{2}$
$\displaystyle=\gamma^{2}(\frac{1}{2}\|R^{S}(\boldsymbol{a}_{i})\|^{2}+\frac{\sigma^{2}}{2}\|\boldsymbol{x}^{S}(\boldsymbol{a}_{i})\|^{2}+\frac{\sigma^{2}}{2})$

Hence $G(i|S)=[\boldsymbol{x}^{S\cup i}(\boldsymbol{y})]^{2}_{i}\phi(S,i)$.

By the optimality condition on $\boldsymbol{x}^{S}(\boldsymbol{a}_{i})$ we
also have:

$\displaystyle~{}~{}~{}~{}~{}\frac{1}{2}\boldsymbol{y}^{\top}R^{S}(\boldsymbol{a}_{i})$
$\displaystyle=\frac{1}{2}(R^{S\cup i}(\boldsymbol{y})+\boldsymbol{A}_{S\cup
i}\boldsymbol{x}^{S\cup i}(\boldsymbol{y}))^{\top}R^{S}(\boldsymbol{a}_{i})$
$\displaystyle=\frac{1}{2}\Bigl{(}\sigma^{2}\gamma-\sigma^{2}\boldsymbol{x}^{S}(\boldsymbol{a}_{i})^{\top}[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}^{\top}\boldsymbol{A}_{S}^{\top}R^{S}(\boldsymbol{a}_{i})+[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{i}^{\top}\boldsymbol{a}_{i}^{\top}R^{S}(\boldsymbol{a}_{i})\Bigl{)}$
$\displaystyle=\frac{1}{2}\Bigl{(}\sigma^{2}\gamma-\sigma^{2}\boldsymbol{x}^{S}(\boldsymbol{a}_{i})^{\top}[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}+\sigma^{2}[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{S}^{\top}\boldsymbol{x}^{S}(\boldsymbol{a}_{i})+[\boldsymbol{x}^{S\cup
i}(\boldsymbol{y})]_{i}(R^{S}(\boldsymbol{a}_{i})+\boldsymbol{A}_{S}\boldsymbol{x}^{S}(\boldsymbol{a}_{i}))^{\top}R^{S}(\boldsymbol{a}_{i})\Bigl{)}$
$\displaystyle=\frac{1}{2}\Bigl{(}\sigma^{2}\gamma+\gamma\|R^{S}(\boldsymbol{a}_{i})\|_{2}^{2}+\gamma\sigma^{2}\|\boldsymbol{x}^{S}(\boldsymbol{a}_{i})\|_{2}^{2}\Bigl{)}$

Hence
$\Bigl{(}\frac{\boldsymbol{y}^{\top}R^{S}(\boldsymbol{a}_{i})}{2\sqrt{\phi(S,i)}}\Bigl{)}^{2}=\gamma^{2}{\phi(S,i)}=G(i|S)$.
∎

######  Proposition 10.

Given a positive-definite matrix $\boldsymbol{A}$, let $\boldsymbol{a}_{i}$ be
the ith column of $\boldsymbol{A}$, and
$\ell_{i}(\boldsymbol{x}):=\frac{1}{2}\|\boldsymbol{a}_{i}-\boldsymbol{A}\boldsymbol{x}\|_{2}^{2}+\frac{\sigma^{2}}{2}\|\boldsymbol{x}\|^{2}$
for all $i\in V$, for some $\sigma\geq 0$. Then the function $G(S)=\sum_{i\in
V}\ell(0)-\min_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\ell_{i}(\boldsymbol{x})$ is a non-decreasing $(\beta,\beta)$-weakly DR-
modular function, with
$\beta=(\frac{\lambda_{\min}(\boldsymbol{A})}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})})^{2}\frac{1}{\kappa^{2}(\boldsymbol{A})}$,
where
$\kappa(\boldsymbol{A})=\lambda_{\max}(\boldsymbol{A})/\lambda_{\min}(\boldsymbol{A})$
is the condition number of $\boldsymbol{A}$.

###### Proof.

For all $j\in V$, let
$G_{j}(S):=\ell(0)-\min_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\ell_{j}(\boldsymbol{x})$, then we can write $G(S)=\sum_{j\in V}G_{j}(S)$.
Given $i\in V,S\subseteq V\setminus i$, let
$\boldsymbol{x}^{S}(\boldsymbol{a}_{i}):=\operatorname*{arg\,min}_{\mathrm{supp}(\boldsymbol{x})\subseteq
S}\ell_{i}(\boldsymbol{x})$ be the optimal regression coefficients,
$R^{S}(\boldsymbol{a}_{i})=\boldsymbol{a}_{i}-\boldsymbol{A}\boldsymbol{x}^{S}(\boldsymbol{a}_{i})$
the corresponding residual. By Proposition 9, we have for all $j\in V$:

$\displaystyle G_{j}(i|S)$ $\displaystyle=[\boldsymbol{x}^{S\cup
i}(\boldsymbol{a}_{j})]^{2}_{i}~{}\phi(S,i)=\Bigl{(}\frac{\boldsymbol{a}_{j}^{\top}R^{S}(\boldsymbol{a}_{i})}{2\sqrt{\phi(S,i)}}\Bigl{)}^{2},$

where
$\phi(S,i)=\frac{1}{2}\|R^{S}(\boldsymbol{a}_{i})\|^{2}+\frac{\sigma^{2}}{2}\|\boldsymbol{x}^{S}(\boldsymbol{a}_{i})\|^{2}+\frac{\sigma^{2}}{2}$.
Note that $\phi(S,i)>0$ since $\boldsymbol{A}$ is positive definite (columns
are linearly independent).

In the noiseless case $\sigma=0$, we have $\boldsymbol{x}^{S\cup
i}(\boldsymbol{a}_{i})=\mathds{1}_{i}$. In the noisy case $\sigma>0$, we have
by optimality conditions

$\displaystyle(\boldsymbol{A}_{S\cup i}^{\top}\boldsymbol{A}_{S\cup
i}+\sigma^{2}I)\boldsymbol{x}^{S\cup i}(\boldsymbol{a}_{i})$
$\displaystyle=\boldsymbol{A}_{S\cup i}^{\top}\boldsymbol{a}_{i}$
$\displaystyle(\boldsymbol{A}_{S\cup i}^{\top}\boldsymbol{A}_{S\cup
i}+\sigma^{2}I)\boldsymbol{x}^{S\cup i}(\boldsymbol{a}_{i})$
$\displaystyle=(\boldsymbol{A}_{S\cup i}^{\top}\boldsymbol{A}_{S\cup
i}+\sigma^{2}I)\mathds{1}_{i}-\sigma^{2}\mathds{1}_{i}$
$\displaystyle\boldsymbol{x}^{S\cup i}(\boldsymbol{a}_{i})$
$\displaystyle=\mathds{1}_{i}-\sigma^{2}(\boldsymbol{A}_{S\cup
i}^{\top}\boldsymbol{A}_{S\cup i}+\sigma^{2}I)^{-1}\mathds{1}_{i}$

Since
$(\sigma^{2}+\lambda_{\min}(\boldsymbol{A}))^{-1}I\succcurlyeq(\boldsymbol{A}_{S\cup
i}^{\top}\boldsymbol{A}_{S\cup
i}+\sigma^{2}I)^{-1}\succcurlyeq(\sigma^{2}+\lambda_{\max}(\boldsymbol{A}))^{-1}I$,
we have

$1-\frac{\sigma^{2}}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})}\leq[\boldsymbol{x}^{S\cup
i}(\boldsymbol{a}_{i})]_{i}\leq
1-\frac{\sigma^{2}}{\sigma^{2}+\lambda_{\max}(\boldsymbol{A})}.$

We will construct two unit vectors $\boldsymbol{y},\boldsymbol{z}$ such that
$\tfrac{1}{2}(\frac{\lambda_{\min}(\boldsymbol{A})}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})})^{2}\|\boldsymbol{A}\boldsymbol{y}\|^{2}_{2}\leq
G(i|S)\leq\frac{1}{2}\|\boldsymbol{A}\boldsymbol{z}\|^{2}_{2}$.

Let
$w_{j}=\frac{\boldsymbol{a}_{j}^{\top}R^{S}(\boldsymbol{a}_{i})}{2\sqrt{\phi(S,i)}},\forall
j\in V$ and $\boldsymbol{z}=\boldsymbol{w}/\|\boldsymbol{w}\|_{2}$. Hence
$\|\boldsymbol{z}\|_{2}=1$ and

$\displaystyle\tfrac{1}{2}R^{S}(\boldsymbol{a}_{i})^{\top}\boldsymbol{A}\boldsymbol{z}$
$\displaystyle=\tfrac{1}{2}\sum_{j\in
V}R^{S}(\boldsymbol{a}_{i})^{\top}\boldsymbol{a}_{j}\frac{w_{j}}{\|\boldsymbol{w}\|_{2}}$
$\displaystyle=\sqrt{\phi(S,i)}\sum_{j\in
V}\frac{w_{j}^{2}}{\|\boldsymbol{w}\|_{2}}$
$\displaystyle=\sqrt{\phi(S,i)}{\|\boldsymbol{w}\|_{2}}.$

Note that $\|\boldsymbol{w}\|_{2}^{2}=G(i|S)$ and
$\phi(S,i)\geq\frac{1}{2}\|R^{S}(\boldsymbol{a}_{i})\|^{2}$. Then by Cauchy-
Schwartz inequality, we have:

$\displaystyle G(i|S)$
$\displaystyle\leq\frac{\|R^{S}(\boldsymbol{a}_{i})\|^{2}\|\boldsymbol{A}\boldsymbol{z}\|^{2}}{4\phi(S,i)}$
$\displaystyle\leq\tfrac{1}{2}\|\boldsymbol{A}\boldsymbol{z}\|^{2}.$

Let $v_{S}=\boldsymbol{x}^{S}(\boldsymbol{a}_{i}),v_{i}=-1$ and zero
elsewhere, and $y=v/\|v\|_{2}$. Hence $\|\boldsymbol{y}\|_{2}=1,\|v\|_{2}\geq
1$ and

$\displaystyle\|\boldsymbol{A}\boldsymbol{y}\|_{2}$
$\displaystyle=\frac{\|R^{S}(\boldsymbol{a}_{i})\|_{2}}{\|v\|_{2}}$
$\displaystyle\leq\|R^{S}(\boldsymbol{a}_{i})\|_{2}.$

Note that $G(i|S)\geq
G_{i}(i|S)=(1-\frac{\sigma^{2}}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})})^{2}~{}\phi(S,i)\geq\tfrac{1}{2}(\frac{\lambda_{\min}(\boldsymbol{A})}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})})^{2}\|R^{S}(\boldsymbol{a}_{i})\|^{2}_{2}\geq\tfrac{1}{2}(\frac{\lambda_{\min}(\boldsymbol{A})}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})})^{2}\|\boldsymbol{A}\boldsymbol{y}\|^{2}_{2}$.

The proposition follows then from

$\displaystyle\tfrac{1}{2}(\frac{\lambda_{\min}(\boldsymbol{A})}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})})^{2}\lambda^{2}_{\min}(\boldsymbol{A})=\tfrac{1}{2}(\frac{\lambda_{\min}(\boldsymbol{A})}{\sigma^{2}+\lambda_{\min}(\boldsymbol{A})})^{2}\max_{\|\boldsymbol{y}\|_{2}=1}\|\boldsymbol{A}\boldsymbol{y}\|^{2}_{2}\leq
G(i|S)\leq\max_{\|\boldsymbol{z}\|_{2}=1}\tfrac{1}{2}\|\boldsymbol{A}\boldsymbol{z}\|^{2}_{2}=\tfrac{1}{2}\lambda^{2}_{\max}(\boldsymbol{A}).$

∎

For the special case of $\sigma=0$, we recover the result of [57].

######  Corollary 3.

Given a positive-definite kernel matrix $\boldsymbol{K}$, we define for any
$i\in V$,
$\ell_{i}(\boldsymbol{z})=\|\boldsymbol{y}-\boldsymbol{K}^{1/2}\boldsymbol{z}\|_{2}^{2}+\sigma^{2}\|\boldsymbol{z}\|_{2}^{2}$
with $\boldsymbol{y}=\boldsymbol{K}^{1/2}\mathds{1}_{i}$, then we can write
the variance reduction function $G(S)=\sum_{i\in
V}\sigma^{2}(\boldsymbol{x}_{i})-\sigma^{2}_{S}(\boldsymbol{x}_{i})=\sum_{i\in
V}\ell(\boldsymbol{0})-\min_{\mathrm{supp}(\boldsymbol{z})\subseteq
S}\ell(\boldsymbol{z})$. Then $G$ is a non-decreasing $(\beta,\beta)$-weakly
DR-modular function, with
$\beta=\frac{\lambda^{2}_{\min}(\boldsymbol{K})}{\lambda_{\max}(\boldsymbol{K})(\sigma^{2}+\lambda_{\min}(\boldsymbol{K}))}$,
where $\lambda_{\max}(\boldsymbol{K})$ and $\lambda_{\min}(\boldsymbol{K})$
are the largest and smallest eigenvalues of $\boldsymbol{K}$.

###### Proof.

For a fixed $i\in V,S\subseteq V\setminus i$, let
$\boldsymbol{z}^{S}:=\operatorname*{arg\,min}_{\mathrm{supp}(x)\subseteq
S}\ell_{i}(\boldsymbol{z})$. Then by optimality conditions
$\boldsymbol{z}^{S}=(\boldsymbol{K}_{S}+\sigma^{2}\boldsymbol{I}_{S})^{-1}\boldsymbol{k}_{S}(\boldsymbol{x}_{i})$.
Hence
$\ell(\boldsymbol{z}^{S})=\|\boldsymbol{y}\|_{2}^{2}-2\boldsymbol{y}^{T}\boldsymbol{K}_{S}^{1/2}\boldsymbol{z}^{S}+(\boldsymbol{z}^{S})^{\top}(\boldsymbol{K}_{S}+\sigma^{2}\boldsymbol{I}_{S})\boldsymbol{z}^{S}=\|\boldsymbol{y}\|_{2}^{2}-\boldsymbol{k}_{S}(\boldsymbol{x}_{i})(\boldsymbol{K}_{S}+\sigma^{2}\boldsymbol{I}_{S})^{-1}\boldsymbol{k}_{S}(\boldsymbol{x}_{i})$.
It follows then that
$\sigma^{2}(\boldsymbol{x}_{i})-\sigma^{2}_{S}(\boldsymbol{x}_{i})=\ell(\boldsymbol{0})-\min_{\mathrm{supp}(\boldsymbol{z})\subseteq
S}\ell(\boldsymbol{z})$. The corollary then follows from Proposition 10. ∎