text:
\section{Introduction}

Submodular set functions are defined by the following condition for all pairs of sets $S,T$:
$$ f(S \cup T) + f(S \cap T) \leq f(S) + f(T),$$
or equivalently by the property that the {\em marginal value} of any element,
$f_S(j) = f(S+j)-f(S)$, satisfies $f_T(j) \leq f_S(j)$, whenever
$j \notin T \supset S$. In addition, a set function is called monotone
if $f(S) \leq f(T)$ whenever $S \subseteq T$.
Throughout this paper, we assume that $f(S)$ is nonnegative.

Submodular functions have been studied in the context of combinatorial
optimization since the 1970's, especially in connection with matroids
\cite{E70,E71,NWF78,NWF78II,NW78,W82a,W82b,L83,F97}.
Submodular functions appear mostly for the following two reasons:
(i) submodularity arises naturally in various combinatorial settings,
and many algorithmic applications use it either explicitly or implicitly;
(ii) submodularity has a natural interpretation as the property
of {\em diminishing returns}, which defines an important class of
utility/valuation functions.
Submodularity as an abstract concept is both general enough to be useful for applications
and it carries enough structure to allow strong positive results.
A fundamental algorithmic result is that any submodular function
can be {\em minimized} in strongly polynomial time \cite{FFI01,Lex00}.

In contrast to submodular minimization, submodular maximization problems are
typically hard to solve exactly. Consider the classical problem
of maximizing a monotone submodular function subject to a cardinality constraint,
$\max \{f(S): |S|\leq k\}$. It is known that this problem admits a $(1-1/e)$-approximation
\cite{NWF78} and this is optimal for two different reasons:
(i) Given only black-box access to $f(S)$, we cannot achieve a better approximation,
unless we ask exponentially many value queries \cite{NW78}.
This holds even if we allow unlimited computational power.
(ii) In certain special cases where $f(S)$ has a compact representation on the input,
it is NP-hard to achieve an approximation better than $1-1/e$ \cite{Feige98}.
The reason why the hardness threshold is the same in both cases
is apparently not well understood.

An optimal $(1-1/e)$-approximation for the problem $\max \{f(S): |S| \leq k\}$ where $f$ is
monotone sumodular is achieved
by a simple greedy algorithm \cite{NWF78}. This seems to be rather coincidental; for
other variants of submodular maximization, such as unconstrained (nonmonotone)
submodular maximization \cite{FMV07}, monotone submodular maximization subject
to a matroid constraint \cite{NWF78II,CCPV07,Vondrak08}, or submodular
maximization subject to linear constraints \cite{KTS09,LMNS09},
greedy algorithms achieve suboptimal results. A tool which has proven useful
in approaching these problems is the {\em multilinear relaxation}.

\

\noindent{\bf Multilinear relaxation.}
Let us consider a discrete optimization problem $\max \{f(S): S \in {\cal F}\}$, where
$f:2^X \rightarrow {\boldmath R}$ is the objective function and ${\cal F} \subset 2^X$
is the collection of feasible solutions. In case $f$ is a linear function,
$f(S) = \sum_{j \in S} w_j$, it is natural to replace this problem by a linear
programming problem. For a general set function $f(S)$, however, a linear
relaxation is not readily available. Instead, the following relaxation
has been proposed \cite{CCPV07,Vondrak08,CCPV09}:
For ${\bf x} \in [0,1]^X$, let $\hat{{\bf x}}$ denote a random vector in $\{0,1\}^X$
where each coordinate of $x_i$ is rounded independently to $1$ with probability $x_i$
and $0$ otherwise.\footnote{We denote vectors consistently in boldface $({\bf x})$ and their coordinates in italics $(x_i)$.
We also identify vectors in $\{0,1\}^n$ with subsets of $[n]$ in a natural way.
}
We define
$$ F({\bf x}) = {\bf E}[f(\hat{{\bf x}})] = \sum_{S \subseteq X} f(S) \prod_{i \in S} x_i
 \prod_{j \notin S} (1-x_j).$$
This is the unique {\em multilinear polynomial} which coincides with $f$ on $\{0,1\}$-vectors.
We remark that although we cannot compute the exact value of $F({\bf x})$ for a given
${\bf x} \in [0,1]^X$ (which would require querying $2^n$ possible values of $f(S)$),
we can compute $F({\bf x})$ approximately, by random sampling. Sometimes this causes
technical issues, which we also deal with in this paper.

Instead of the discrete problem $\max \{f(S): S \in {\cal F}\}$,
we consider a continuous optimization problem $\max \{F({\bf x}): {\bf x} \in P({\cal F})\}$,
where $P({\cal F})$ is the convex hull of characteristic vectors corresponding to ${\cal F}$,
$$ P({\cal F})
 = \left\{ \sum_{S \in {\cal F}} \alpha_S {\bf 1}_S:
   \sum_{S \in {\cal F}} \alpha_S = 1, \alpha_S \geq 0 \right\}.$$
The reason why the extension $F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$ is useful
for submodular maximization problems is that $F({\bf x})$ has convexity properties
that allow one to solve the continuous problem $\max \{F({\bf x}): {\bf x} \in P\}$
(within a constant factor) in a number of interesting cases.
Moreover, fractional solutions can be often
rounded to discrete ones without losing {\em anything} in terms of the objective
value. Then, our ability to solve the multilinear relaxation
translates directly into an algorithm for the original problem.
In particular, this is true when the collection of feasible solutions
forms a matroid.

{\em Pipage rounding} was originally developed by Ageev and Sviridenko
for rounding solutions in the bipartite matching polytope \cite{AS04}.
The technique was adapted to matroid polytopes by Calinescu et al.
 \cite{CCPV07}, who proved that for any submodular function $f(S)$
and any ${\bf x}$ in the matroid base polytope $B({\cal M})$,
the fractional solution ${\bf x}$ can be rounded to a base
$B \in {\cal B}$ such that $f(B) \geq F({\bf x})$.
This approach leads to an optimal $(1-1/e)$-approximation for
the Submodular Welfare Problem,
and more generally for monotone submodular maximization subject
to a matroid constraint \cite{CCPV07,Vondrak08}.
It is also known that
the factor of $1-1/e$ is optimal for the Submodular Welfare Problem
both in the NP framework \cite{KLMM05} and in the value oracle model
\cite{MSV08}. Under the assumption that the submodular function $f(S)$
has {\em curvature} $c$, there is a $\frac{1}{c}(1-e^{-c})$-approximation
and this is also optimal in the value oracle model \cite{VKyoto08}.
The framework of pipage rounding can be also extended to nonmonotone submodular functions;
this presents some additional issues which we discuss in this paper.

For the problem of
unconstrained (nonmonotone) submodular maximization, a $2/5$-approximation
was developed in \cite{FMV07}. This algorithm implicitly uses
the multilinear relaxation $\max \{F({\bf x}): {\bf x} \in [0,1]^X\}$.
For {\em symmetric} submodular functions, it is shown in \cite{FMV07}
that a uniformly random solution ${\bf x} = (1/2,\ldots,1/2)$ gives
$F({\bf x}) \geq \frac12 OPT$, and there is no better approximation algorithm
in the value oracle model. Recently, a $1/2$-approximation was found
for unconstrained maximization of a general nonnegative submodular function \cite{BFNS12}.
This algorithm can be formulated in the multilinear relaxation framework, but also
as a randomized combinatorial algorithm.

Using additional techniques, the multilinear relaxation can be also applied
to submodular maximization with knapsack constraints
($\sum_{j \in S} c_{ij} \leq 1$). For the problem of maximizing a monotone
submodular function subject to a constant number of knapsack constraints,
there is a $(1-1/e-\epsilon)$-approximation algorithm for any $\epsilon > 0$ \cite{KTS09}.
For maximizing a nonmonotone submodular function
subject to a constant number of knapsack constraints,
a $(1/5-\epsilon)$-approximation was designed in \cite{LMNS09}.

One should mention that not all the best known results for submodular maximization
have been achieved using the multilinear relaxation. The greedy algorithm
yields a $1/(k+1)$-approximation for monotone submodular maximization
subject to $k$ matroid constraints \cite{NWF78II}. Local search methods
have been used to improve this to a $1/(k+\epsilon)$-approximation,
and to obtain a $1/(k+1+1/(k-1)+\epsilon)$-approximation
for the same problem with a nonmonotone submodular function,
for any $\epsilon>0$ \cite{LMNS09,LSV09}.
For the problem of maximizing a nonmonotone submodular function
over the {\em bases} of a given matroid, local search yields
a $(1/6-\epsilon)$-approximation, assuming that the matroid contains two disjoint bases
\cite{LMNS09}.

\subsection{Our results}

Our main contribution (Theorem~\ref{thm:general-hardness})
is a general hardness construction that yields
inapproximability results in the value oracle model in an automated
way, based on what we call the {\em symmetry gap} for some fixed instance.
In this generic fashion, we are able to replicate a number of previously
known hardness results (such as the optimality of the factors
$1-1/e$ and $1/2$ mentioned above),
and we also produce new hardness results using this construction
(Theorem~\ref{thm:matroid-bases}).
Our construction helps explain the particular hardness thresholds obtained under
various constraints, by exhibiting a small instance where the threshold can be
seen as the gap between the optimal solution and the best symmetric solution.
The query complexity results in \cite{FMV07,MSV08,VKyoto08}
can be seen in hindsight as special cases of Theorem~\ref{thm:general-hardness},
but the construction in this paper is somewhat different and
technically more involved than the previous proofs for particular cases.

\paragraph{Concrete results}
Before we proceed to describe our general hardness result, we present its implications
for two more concrete problems.
We also provide closely matching approximation algorithms for these two problems,
based on the multilinear relaxation. In the following, we assume that the objective function is given by a value oracle
and the feasibility constraint is given by a membership oracle: a value oracle for $f$ returns the value $f(S)$ for a given set $S$,
and a membership oracle for ${\cal F}$ answers whether $S \in {\cal F}$ for a given set $S$.

First, we consider the problem of maximizing a nonnegative (possibly nonmonotone) submodular function
subject to a \emph{matroid base} constraint. (This generalizes for example the maximum bisection
problem in graphs.) We show that the approximability of this problem is related to base
packings in the matroid. We use the following definition.

\begin{definition}
\label{def:fractional-base}
For a matroid ${\cal M}$ with a collection of bases ${\cal B}$, the fractional base
packing number is the maximum possible value of $\sum_{B \in {\cal B}} \alpha_B$
for $\alpha_B \geq 0$ such that $\sum_{B \in {\cal B}: j \in B} \alpha_B \leq 1$ for
every element $j$.
\end{definition}

\noindent{\bf Example.}
Consider a uniform matroid with bases ${\cal B} = \{ B \subset [n]: |B| = k \}$. ($[n]$ denotes the set of integers
$\{1,2,\cdots,n\}$.)
Here, we can take each base with a coefficient $\alpha_B = 1 / {n-1 \choose k-1}$, which satisfies
the condition $\sum_{B \in {\cal B}: j \in B} \alpha_B \leq 1$ for every element $j$ since every element
is contained in ${n-1 \choose k-1}$ bases. We obtain that the fractional packing number is at least
${n \choose k} / {n-1 \choose k-1} = \frac{n}{k}$. It is also easy to check that the fractional packing number
cannot be larger than $\frac{n}{k}$.

\begin{theorem}
\label{thm:matroid-bases}
For any $\nu$ in the form $\nu = \frac{k}{k-1}, k \geq 2$,
and any fixed $\epsilon>0$, a $(1-\frac{1}{\nu}+\epsilon) = \frac{1}{k}$-approximation for the problem
$\max \{f(S): S \in {\cal B}\}$, where $f(S)$ is a nonnegative submodular function,
and ${\cal B}$ is a collection of bases in a matroid with fractional packing number at least $\nu$,
would require exponentially many value queries.

On the other hand, for any $\nu \in (1,2]$,
there is a randomized $\frac{1}{2}(1-\frac{1}{\nu}-o(1))$-approximation
for the same problem.
\end{theorem}

In case the matroid contains two disjoint bases ($\nu=2$), we obtain a
$(\frac14-o(1))$-approximation, improving the previously known factor of $\frac16-o(1)$ \cite{LMNS09}.
In the range of $\nu \in (1,2]$, our positive and negative results are within a factor of $2$.
For maximizing a submodular function over the bases of a general matroid,
we obtain the following.

\begin{corollary}
\label{coro:matroid-bases}
For the problem $\max \{f(S): S \in {\cal B}\}$,  where $f(S)$ is a nonnegative submodular function,
and ${\cal B}$ is a collection of bases in a matroid, any constant-factor approximation requires
an exponential number of value queries.
\end{corollary}

We also consider the problem of maximizing a nonnegative submodular function subject to a matroid independence
constraint.

\begin{theorem}
\label{thm:matroid-indep}
For any $\epsilon>0$, a $(\frac12 + \epsilon)$-approximation for the problem $\max \{f(S): S \in {\cal I} \}$,
where $f(S)$ is a nonnegative submodular function, and ${\cal I}$ is a collection of independent sets in a matroid,
would require exponentially many value queries.

On the other hand, there is a randomized $\frac14 (-1+\sqrt{5}-o(1)) \simeq 0.309$-approximation for the same problem.
\end{theorem}

Our algorithmic result improves a previously known $(\frac14 - o(1))$-approximation \cite{LMNS09}.
The hardness threshold follows from our general result, but also quite easily from \cite{FMV07}.

\medskip
\noindent{\bf Hardness from the symmetry gap.}
Now we describe our general hardness result.
Consider an instance $\max \{f(S): S \in {\cal F}\}$ which exhibits a certain
degree of symmetry. This is formalized by the notion of a {\em symmetry group}
${\cal G}$. We consider permutations $\sigma \in {\bf S}(X)$ where ${\bf S}(X)$
is the symmetric group (of all permutations) on the ground set $X$.
We also use $\sigma$ for the naturally induced mapping of subsets of $X$:
$\sigma(S) = \{ \sigma(i): i \in S \}$.
We say that the instance is invariant
under ${\cal G} \subset {\bf S}(X) $, if for any $\sigma \in {\cal G}$
and any $S \subseteq X$,
$f(S) = f(\sigma(S))$ and $S \in {\cal F} \Leftrightarrow \sigma(S) \in {\cal F}$.
We emphasize that even though we apply $\sigma$ to sets, it must be derived
from a permutation on $X$.
For ${\bf x} \in [0,1]^X$, we define the ``symmetrization of ${\bf x}$'' as
$$\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})],$$
where $\sigma \in {\cal G}$ is uniformly random and $\sigma({\bf x})$ denotes ${\bf x}$ with coordinates permuted by $\sigma$.

\medskip
{\bf Erratum:}
The main hardness result in the conference version of this paper \cite{Vondrak09} was formulated
for an arbitrary feasibility constraint ${\cal F}$, invariant under ${\cal G}$.
Unfortunately, this was an error and the theorem does not hold in that form
 --- an algorithm could gather some information from querying ${\cal F}$, and combining this
with information obtained by querying the objective function $f$ it could possibly determine the hidden optimal solution.
The possibility of gathering information from the membership oracle for ${\cal F}$ was neglected in the proof. (The reason for this
was probably that the feasibility constraints used in concrete applications of the theorem were very simple and indeed
did not provide any information about the optimum.)
Nevertheless, to correct this issue, one needs to impose a stronger symmetry constraint on ${\cal F}$, namely
the condition that $S \in {\cal F}$ depends only on the symmetrized version of $S$, $\overline{{\bf 1}_S} = {\bf E}_{\sigma \in {\cal G}}[{\bf 1}_{\sigma(S)}]$.
This is the case in all the applications of the hardness theorem in \cite{Vondrak09} and \cite{OV11} and hence
these applications are not affected.

\begin{definition}
\label{def:total-sym}
We call an instance $\max \{f(S): S \in {\cal F}\}$ on a ground set $X$ strongly symmetric with respect to a group of permutations ${\cal G}$ on $X$, if $f(S) = f(\sigma(S))$ for all $S \subseteq X$ and $\sigma \in {\cal G}$, and $S \in {\cal F} \Leftrightarrow S' \in {\cal F}$ whenever ${\bf E}_{\sigma \in {\cal G}}[{\bf 1}_{\sigma(S)}] = {\bf E}_{\sigma \in {\cal G}}[{\bf 1}_{\sigma(S')}] $.
\end{definition}

\noindent{\bf Example.} A cardinality constraint, ${\cal F} = \{S \subseteq [n]: |S| \leq k \}$, is strongly symmetric with respect to all permutations, because the condition $S \in {\cal F}$ depends only on the symmetrized vector $\overline{{\bf 1}_S} = \frac{|S|}{n} {\bf 1}$.
Similarly, a partition matroid constraint, ${\cal F} = \{S \subseteq [n]: |S \cap X_i| \leq k \}$ for disjoint sets $X_i$, is also strongly symmetric.
On the other hand, consider a family of feasible solution ${\cal F} = \{ \{1,2\}, \{2,3\}, \{3,4\}, \{4,1\} \}$. This family is invariant under a group generated by the cyclic rotation $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1$. It is not strongly symmetric, because the condition $S \in {\cal F}$ does not depend only the symmetrized vector $\overline{{\bf 1}_S} = (\frac14 |S|,\frac14 |S|,\frac14 |S|,\frac14 |S|)$;
some pairs are feasible and others are not.

\

Next, we define the symmetry gap as the ratio between the optimal solution
of $\max \{F({\bf x}): {\bf x} \in P({\cal F})\}$ and the best {\em symmetric} solution
of this problem.

\begin{definition}[Symmetry gap]
Let $\max \{ f(S): S \in {\cal F} \}$ be an instance on a ground set $X$,
which is strongly symmetric with respect to ${\cal G} \subset {\bf S}(X)$.
Let $F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$ be the multilinear extension of $f(S)$
and $P({\cal F}) = \mbox{conv}(\{{\bf 1}_I: I \in {\cal F} \})$ the polytope
associated with $\cal F$. Let $\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$.
The symmetry gap of $\max \{ f(S): S \in {\cal F} \}$ is defined as
$\gamma = \overline{OPT} / OPT$ where
$$OPT = \max \{F({\bf x}): {\bf x} \in P({\cal F})\},$$
$$\overline{OPT} = \max \{F(\bar{{\bf x}}): {\bf x} \in P({\cal F}) \}.$$
\end{definition}

\noindent
We give examples of computing the symmetry gap in Section~\ref{section:hardness-applications}.
Next, we need to define the notion of a {\em refinement} of an instance.
This is a natural way to extend a family of feasible sets to a larger ground set.
In particular, this operation preserves the types of constraints that we care about,
such as cardinality constraints, matroid independence, and matroid base constraints.

\begin{definition}[Refinement]
Let ${\cal F} \subseteq 2^X$, $|X|=k$ and $|N| = n$. We say that
$\tilde{{\cal F}}\subseteq 2^{N \times X}$ is a refinement of $\cal F$, if
$$ \tilde{{\cal F}} = \left\{ \tilde{S} \subseteq N \times X \ \big| \ (x_1,\ldots,x_k) \in P({{\cal F}})
 \mbox{ where } x_j = \frac{1}{n} |\tilde{S} \cap (N \times \{j\})| \right\}. $$
\end{definition}

In other words, in the refined instance, each element $j \in X$ is replaced by a set $N \times \{j\}$.
We call this set the {\em cluster} of elements corresponding to $j$.
A set $\tilde{S}$ is in $\tilde{{\cal F}}$ if and only if the fractions $x_j$ of the respective clusters that are intersected by $\tilde{S}$ form a vector ${\bf x} \in P({\cal F})$, i.e. a convex combination of sets in ${\cal F}$.

Our main result is that the symmetry gap for any strongly symmetric instance
translates automatically into hardness of approximation for refined instances.
(See Definition~\ref{def:total-sym} for the notion of being ``strongly symmetric".)
We emphasize that this is a query-complexity lower bound,
and hence independent of assumptions such as $P \neq NP$.

\begin{theorem}
\label{thm:general-hardness}
Let $\max \{ f(S): S \in {\cal F} \}$ be an instance of nonnegative
(optionally monotone) submodular maximization, strongly symmetric with respect to ${\cal G}$,
with symmetry gap $\gamma = \overline{OPT} / OPT$.
Let $\cal C$ be the class of instances $\max \{\tilde{f}(S): S \in \tilde{{\cal F}}\}$
where $\tilde{f}$ is nonnegative (optionally monotone) submodular
and $\tilde{{\cal F}}$ is a refinement of ${\cal F}$.
Then for every $\epsilon > 0$,
any (even randomized) $(1+\epsilon) \gamma$-approximation algorithm for the class $\cal C$ would require
exponentially many value queries to $\tilde{f}(S)$.
\end{theorem}

We remark that the result holds even if the class $\cal C$ is restricted
to instances which are themselves symmetric under a group related to ${\cal G}$
(see the discussion in Section~\ref{section:hardness-proof}, after the proofs of Theorem~\ref{thm:general-hardness}
and \ref{thm:multilinear-hardness}).
On the algorithmic side, submodular maximization seems easier for symmetric instances
and in this case we obtain optimal approximation factors, up to lower-order terms
(see Section~\ref{section:symmetric}).

Our hardness construction yields impossibility results also for solving
the continuous problem $\max \{F({\bf x}): {\bf x} \in P({\cal F}) \}$. In the case of matroid constraints,
this is easy to see, because an approximation to the continuous problem gives the same
approximation factor for the discrete problem (by pipage rounding, see Appendix~\ref{app:pipage}).
However, this phenomenon
is more general and we can show that the value of a symmetry gap translates into
an inapproximability result for the multilinear optimization problem under any constraint
satisfying a symmetry condition.

\begin{theorem}
\label{thm:multilinear-hardness}
Let $\max \{ f(S): S \in {\cal F} \}$ be an instance of nonnegative
(optionally monotone) submodular maximization, strongly symmetric with respect to ${\cal G}$,
with symmetry gap $\gamma = \overline{OPT} / OPT$.
Let $\cal C$ be the class of instances $\max \{\tilde{f}(S): S \in \tilde{{\cal F}}\}$
where $\tilde{f}$ is nonnegative (optionally monotone) submodular
and $\tilde{{\cal F}}$ is a refinement of ${\cal F}$.
Then for every $\epsilon > 0$,
any (even randomized) $(1+\epsilon) \gamma$-approximation algorithm for the multilinear relaxation
$\max \{\tilde{F}({\bf x}): {\bf x} \in P(\tilde{{\cal F}})\}$ of problems in $\cal C$ would require
exponentially many value queries to $\tilde{f}(S)$.
\end{theorem}

\

\noindent{\bf Additions to the conference version and follow-up work.}
An extended abstract of this work appeared in IEEE FOCS 2009 \cite{Vondrak09}.
As mentioned above, the main theorem in \cite{Vondrak09} suffers from a technical flaw.
This does not affect the applications, but the general theorem in \cite{Vondrak09} is not correct.
We provide a corrected version of the main theorem with a complete proof
(Theorem~\ref{thm:general-hardness}) and we extend this hardness result to the problem of solving
 the multilinear relaxation (Theorem~\ref{thm:multilinear-hardness}).

Subsequently, further work has been done which exploits the symmetry gap concept.
In \cite{OV11}, it has been proved using Theorem~\ref{thm:general-hardness} that
maximizing a nonnegative submodular function subject to a matroid independence constraint
with a factor better than $0.478$ would require exponentially many queries. Even in the case of a cardinality constraint,
$\max \{f(S): |S| \leq k\}$ cannot be approximated within a factor better than $0.491$ using subexponentially many
queries \cite{OV11}.
In the case of a matroid base constraint, assuming that the fractional base packing number
is $\nu = \frac{k}{k-1}$ for some $k \geq 2$, there is no $(1-e^{-1/k}+\epsilon)$-approximation in the value oracle model \cite{OV11}, improving the hardness of $(1-\frac{1}{\nu}+\epsilon) = (\frac{1}{k}+\epsilon)$-approximation from this paper.
These applications are not affected by the flaw in \cite{Vondrak09},
and they are implied by the corrected version of Theorem~\ref{thm:general-hardness} here.

Recently \cite{DV11}, it has been proved using the symmetry gap technique that combinatorial auctions with submodular bidders do not admit any truthful-in-expectation $1/m^\gamma$-approximation, where $m$ is the number of items and $\gamma>0$ some absolute constant.
This is the first nontrivial hardness result for truthful-in-expectation mechanisms for combinatorial auctions;
it separates the classes of monotone submodular functions and coverage functions,
where a truthful-in-expectation $(1-1/e)$-approximation is possible \cite{DRY11}.
The proof is self-contained and does not formally refer to \cite{Vondrak09}.

Moreover, this hardness result for truthful-in-expectation mechanisms as well as the main hardness result in this paper
have been converted from the oracle setting to a computational complexity setting \cite{DV12a,DV12b}.  This recent work
shows that the hardness of approximation arising from symmetry gap is not limited to instances given by an oracle, but holds
also for instances encoded explicitly on the input, under a suitable complexity-theoretic assumption.

\

\noindent{\bf Organization.}
The rest of the paper is organized as follows.
In Section~\ref{section:hardness-applications}, we present applications
of our main hardness result (Theorem~\ref{thm:general-hardness}) to concrete cases,
in particular we show how it implies the hardness statements in Theorem~\ref{thm:matroid-indep}
and \ref{thm:matroid-bases}.
In Section~\ref{section:hardness-proof}, we present the proofs of Theorem~\ref{thm:general-hardness}
 and Theorem~\ref{thm:multilinear-hardness}.
In Section~\ref{section:algorithms}, we prove the algorithmic results
in Theorem~\ref{thm:matroid-indep} and \ref{thm:matroid-bases}.
In Section~\ref{section:symmetric}, we discuss the special case of symmetric instances.
In the Appendix,
we present a few basic facts concerning submodular functions,
an extension of pipage rounding to matroid independence polytopes (rather than matroid base polytopes),
and other technicalities that would hinder the main exposition.

\section{From symmetry to inapproximability: applications}
\label{section:hardness-applications}

Before we get into the proof of Theorem~\ref{thm:general-hardness},
let us show how it can be applied to a number of specific problems.
Some of these are hardness results that were proved previously by
an ad-hoc method. The last application is a new one
(Theorem~\ref{thm:matroid-bases}).

\

\noindent{\bf Nonmonotone submodular maximization.}
Let $X = \{1,2\}$ and for any $S \subseteq X$,
$f(S) = 1$ if $|S|=1$, and $0$ otherwise.
Consider the instance $\max \{ f(S): S \subseteq X \}$.
In other words, this is the Max Cut problem on the graph $K_2$.
This instance exhibits a simple symmetry, the group of all (two) permutations
on $\{1,2\}$. We get $OPT = F(1,0) = F(0,1) = 1$, while $\overline{OPT} = F(1/2,1/2)
 = 1/2$. Hence, the symmetry gap is $1/2$.

\begin{figure}[here]
\begin{tikzpicture}[scale=.50]

\draw (-10,0) node {};

\filldraw [fill=gray,line width=1mm] (0,0) rectangle (4,2);

\filldraw [fill=white] (0.5,1) .. controls +(0,1) and +(0,1) .. (1.5,1)
 .. controls +(0,-1) and +(0,-1) .. (0.5,1);

\fill (1,1) circle (5pt);
\fill (3,1) circle (5pt);
\draw (1,1) -- (3,1);

\draw (-1,1) node {$X$};

\draw (7,1) node {$\bar{x}_1 = \bar{x}_2 = \frac{1}{2}$};

\end{tikzpicture}

\caption{Symmetric instance for nonmonotone submodular maximization: Max Cut on the graph $K_2$.
The white set denotes the optimal solution, while $\bar{{\bf x}}$ is the (unique) symmetric solution.}

\end{figure}

Since $f(S)$ is nonnegative submodular and there is no constraint on $S \subseteq X$,
this will be the case for any refinement of the instance as well.
Theorem~\ref{thm:general-hardness} implies immediately the following: any algorithm achieving
a $(\frac12 + \epsilon)$-approximation for nonnegative (nonmonotone) submodular
maximization requires exponentially many value queries
(which was previously known \cite{FMV07}). Note that a ``trivial instance" implies
a nontrivial hardness result. This is typically the case in applications of Theorem~\ref{thm:general-hardness}.

The same symmetry gap holds if we impose some simple constraints:
the problems $\max \{ f(S): |S| \leq 1 \}$ and $\max \{ f(S): |S| = 1 \}$
have the same symmetry gap as above. Hence, the hardness threshold of $1/2$
also holds for nonmonotone submodular maximization under cardinality constraints
of the type $|S| \leq n/2$, or $|S| = n/2$. This proves the hardness part of
Theorem~\ref{thm:matroid-indep}. This can be derived quite easily
from the construction of \cite{FMV07} as well.

\

\noindent{\bf Monotone submodular maximization.}
Let $X = [k]$ and $f(S) = \min \{|S|, 1\}$.
Consider the instance $\max \{f(S): |S| \leq 1 \}$.
This instance is invariant under all permutations on $[k]$, the symmetric group ${\bf S}_k$.
Note that the instance is {\em strongly symmetric} (Def.~\ref{def:total-sym}) with respect to ${\bf S}_k$,
since the feasibility constraint $|S| \leq 1$ depends only on the symmetrized vector
$\overline{{\bf 1}_S} = (\frac{1}{k}|S|,
\ldots, \frac{1}{k}|S|)$. We get $OPT = F(1,0,\ldots,0) = 1$, while
$\overline{OPT} = F(1/k,1/k,\ldots,1/k) = 1 - (1-1/k)^k$.

\iffalse
\begin{figure}[here]
\begin{tikzpicture}[scale=.50]

\draw (-8,0) node {};

\filldraw [fill=gray,line width=1mm] (0,0) rectangle (9,2);

\filldraw [fill=white] (0.5,1) .. controls +(0,1) and +(0,1) .. (1.5,1)
 .. controls +(0,-1) and +(0,-1) .. (0.5,1);

\fill (1,1) circle (5pt);
\fill (2,1) circle (5pt);
\fill (3,1) circle (5pt);
\fill (4,1) circle (5pt);
\fill (5,1) circle (5pt);
\fill (6,1) circle (5pt);
\fill (7,1) circle (5pt);
\fill (8,1) circle (5pt);

\draw [dotted] (1,1) -- (8,1);

\draw (-1,1) node {$X$};

\draw (11,1) node {$\bar{x}_{i} = \frac{1}{k}$};

\end{tikzpicture}

\caption{Symmetric instance for monotone submodular maximization.}

\end{figure}
\fi

Here, $f(S)$ is monotone submodular and any refinement of $\cal F$ is
a set system of the type $\tilde{{\cal F}} = \{S: |S| \leq \ell \}$.
Based on our theorem, this implies that any approximation better than $1 - (1-1/k)^k$
for monotone submodular maximization subject
to a cardinality constraint would require exponentially many value queries.
Since this holds for any fixed $k$, we get the same hardness
result for any $\beta > \lim_{k \rightarrow \infty} (1 - (1-1/k)^k) = 1-1/e$
(which was previously known \cite{NW78}).

\iffalse

\noindent{\bf Submodular welfare maximization.}
Let $X = [k] \times [k]$,
$ {\cal F} = \{ S: S$ contains at most $1$ pair $(i,j)$ for each $j \}$,
and $f(S) = |\{ i: \exists (i,j) \in S \}|$.
Consider the instance $\max \{f(S): S \in {\cal F}\}$.
This instance can be interpreted as an allocation problem of $k$ items to
$k$ players. A set $S$ represents an assignment in the sense that
$(i,j) \in S$ if item $j$ is allocated to player $i$.
A player is satisfied is she receives at least 1 item;
the objective function is the number of satisfied players.
This instance exhibits the symmetry of all permutations of the players
(and also all permutations of the items, although we do not use it here).
Note that the feasibility constraint $S \in {\cal F}$ depends only on the symmetrized
vector $\overline{{\bf 1}_S}$ which averages out the allocation of each item
across all players. Therefore the instance is strongly symmetric with respect
to permutations of players.
An optimum solution allocates each item to a different player, and $OPT = k$.
The symmetrized optimum allocates a $1/k$-fraction of each item to each player,
which gives $\overline{OPT} = F(\frac{1}{k},\frac{1}{k},\ldots,\frac{1}{k}) =
 k(1-(1-\frac{1}{k})^k)$.

\begin{figure}[here]
\begin{tikzpicture}[scale=.50]

\draw (-8,0) node {};

\filldraw [fill=gray,line width=1mm] (0,0) rectangle (8,2);
\filldraw [fill=white] (0.5,1) .. controls +(0,1) and +(0,1) .. (1.5,1)
 .. controls +(0,-1) and +(0,-1) .. (0.5,1);
\filldraw [fill=gray,line width=1mm] (0,2) rectangle (8,4);
\filldraw [fill=white] (2.5,3) .. controls +(0,1) and +(0,1) .. (3.5,3)
 .. controls +(0,-1) and +(0,-1) .. (2.5,3);
\filldraw [fill=gray,line width=1mm] (0,4) rectangle (8,6);
\filldraw [fill=white] (4.5,5) .. controls +(0,1) and +(0,1) .. (5.5,5)
 .. controls +(0,-1) and +(0,-1) .. (4.5,5);
\filldraw [fill=gray,line width=1mm] (0,6) rectangle (8,8);
\filldraw [fill=white] (6.5,7) .. controls +(0,1) and +(0,1) .. (7.5,7)
 .. controls +(0,-1) and +(0,-1) .. (6.5,7);

\fill (1,1) circle (5pt);
\fill (3,1) circle (5pt);
\fill (5,1) circle (5pt);
\fill (7,1) circle (5pt);
\fill (1,3) circle (5pt);
\fill (3,3) circle (5pt);
\fill (5,3) circle (5pt);
\fill (7,3) circle (5pt);
\fill (1,5) circle (5pt);
\fill (3,5) circle (5pt);
\fill (5,5) circle (5pt);
\fill (7,5) circle (5pt);
\fill (1,7) circle (5pt);
\fill (3,7) circle (5pt);
\fill (5,7) circle (5pt);
\fill (7,7) circle (5pt);

\draw [dotted] (1,1) -- (7,1);
\draw [dotted] (1,3) -- (7,3);
\draw [dotted] (1,5) -- (7,5);
\draw [dotted] (1,7) -- (7,7);

\draw (-1.5,4) node {players};
\draw (4,9) node {items};

\draw (10,4) node {$\bar{x}_{ij} = \frac{1}{k}$};

\end{tikzpicture}

\caption{Symmetric instance for submodular welfare maximization.}

\end{figure}

A refinement of this instance can be interpreted as an allocation problem
where we have $n$ copies of each item, we still have $k$ players,
and the utility functions are monotone submodular. Our theorem implies
that for submodular welfare maximization with $k$ players, a better approximation factor
than $1 - (1-\frac{1}{k})^k$ is impossible.\footnote{We note that
our theorem here assumes an oracle model where only the total value can be
queried for a given allocation. This is actually enough for the $(1-1/e)$-approximation
of \cite{Vondrak08} to work. However, the hardness result holds even if each player's valuation
function can be queried separately; this result was proved in \cite{MSV08}.}

\fi

\

\noindent{\bf Submodular maximization over matroid bases.}
Let $X = A \cup B$, $A = \{a_1, \ldots, a_k\}$, $B = \{b_1, \ldots, b_k\}$
and ${\cal F} = \{ S: |S \cap A| = 1 \ \& \ |S \cap B| = k-1 \}$.
We define $f(S) = \sum_{i=1}^{k} f_i(S)$ where
$f_i(S) = 1$ if $a_i \in S \ \& \ b_i \notin S$, and $0$ otherwise.
This instance can be viewed as a Maximum Directed Cut problem on a graph
of $k$ disjoint arcs, under the constraint that exactly one arc tail
and $k-1$ arc heads should be on the left-hand side ($S$).
An optimal solution is for example $S = \{a_1, b_2, b_3, \ldots, b_k \}$,
which gives $OPT = 1$.
The symmetry here is that we can apply the same permutation to $A$ and $B$
simultaneously. Again, the feasibility of a set $S$ depends only on the symmetrized vector $\overline{{\bf 1}_S}$:
in fact $S \in {\cal F}$ if and only if $\overline{{\bf 1}_S} = (\frac1k,\ldots,\frac1k,1-\frac1k,\ldots,1-\frac1k)$.
There is a unique symmetric solution
$\bar{{\bf x}} = (\frac1k,\ldots,\frac1k,1-\frac1k,\ldots,1-\frac1k)$, and
$\overline{OPT} = F(\bar{{\bf x}}) = {\bf E}[f(\hat{\bar{{\bf x}}})] = \sum_{i=1}^{k}
 {\bf E}[f_i(\hat{\bar{{\bf x}}})] = \frac1k$
(since each arc appears in the directed cut induced by $\hat{\bar{{\bf x}}}$ with probability $\frac{1}{k^2}$).

\begin{figure}[here]
\begin{tikzpicture}[scale=.60]

\draw (-6,0) node {};

\filldraw [fill=gray,line width=1mm] (0,0) rectangle (9,2);
\filldraw [fill=gray,line width=1mm] (0,2) rectangle (9,4);

\filldraw [fill=white] (0.5,3) .. controls +(0,1) and +(0,1) .. (1.5,3)
 .. controls +(0,-1) and +(0,-1) .. (0.5,3);
\filldraw [fill=white] (1.5,1) .. controls +(0,1) and +(0,1) .. (8.5,1)
 .. controls +(0,-1) and +(0,-1) .. (1.5,1);

\fill (1,1) circle (5pt);
\fill (2,1) circle (5pt);
\fill (3,1) circle (5pt);
\fill (4,1) circle (5pt);
\fill (5,1) circle (5pt);
\fill (6,1) circle (5pt);
\fill (7,1) circle (5pt);
\fill (8,1) circle (5pt);
\fill (1,3) circle (5pt);
\fill (2,3) circle (5pt);
\fill (3,3) circle (5pt);
\fill (4,3) circle (5pt);
\fill (5,3) circle (5pt);
\fill (6,3) circle (5pt);
\fill (7,3) circle (5pt);
\fill (8,3) circle (5pt);
\draw[-latex] [line width=0.5mm] (1,3) -- (1,1);
\draw[-latex] [line width=0.5mm] (2,3) -- (2,1);
\draw[-latex] [line width=0.5mm] (3,3) -- (3,1);
\draw[-latex] [line width=0.5mm] (4,3) -- (4,1);
\draw[-latex] [line width=0.5mm] (5,3) -- (5,1);
\draw[-latex] [line width=0.5mm] (6,3) -- (6,1);
\draw[-latex] [line width=0.5mm] (7,3) -- (7,1);
\draw[-latex] [line width=0.5mm] (8,3) -- (8,1);

\draw (-1,1) node {$B$};
\draw (-1,3) node {$A$};

\draw (11,3) node {$\bar{x}_{a_i} = \frac{1}{k}$};
\draw (11,1) node {$\bar{x}_{b_i} = 1 - \frac{1}{k}$};

\end{tikzpicture}

\caption{Symmetric instance for submodular maximization over matroid bases.}

\end{figure}
The refined instances are instances of (nonmonotone) submodular maximization
over the bases of a matroid, where the ground set is partitioned into $A \cup B$
and we should take a $\frac1k$-fraction of $A$ and a $(1-\frac1k)$-fraction of $B$.
(This means that the fractional packing number of bases is $\nu = \frac{k}{k-1}$.)
Our theorem implies that for this class of instances, an approximation better
than $1/k$ is impossible - this proves the hardness part of Theorem~\ref{thm:matroid-bases}.

\

Observe that in all the cases mentioned above, the multilinear relaxation is equivalent
to the original problem, in the sense that any fractional solution can be rounded
without any loss in the objective value. This implies that the same hardness factors apply to
solving the multilinear relaxation of the respective problems. In particular, using the last result
(for matroid bases), we obtain that the multilinear optimization problem $\max \{ F({\bf x}): {\bf x} \in P \}$
does not admit a constant factor for nonnegative submodular functions and matroid base polytopes.
(We remark that a $(1-1/e)$-approximation can be achieved for any {\em monotone} submodular function
and any solvable polytope, i.e.~polytope over which we can optimize linear functions \cite{Vondrak08}.)

As Theorem~\ref{thm:multilinear-hardness} shows, this holds more generally - any symmetry gap
construction gives an inapproximability result for solving the multilinear optimization problem
$\max \{F({\bf x}): {\bf x} \in P\}$. This in fact implies limits on what hardness results we can
possibly hope for using this technique. For instance, we cannot prove using the symmetry gap
that the monotone submodular maximization problem subject to the intersection of $k$ matroid constraints
does not admit a constant factor  - because we would also prove that the respective multilinear relaxation
does not admit such an approximation. But we know from \cite{Vondrak08} that a $(1-1/e)$-approximation
is possible for the multilinear problem in this case.

Hence, the hardness arising from the symmetry gap is related to the difficulty of solving
the multilinear optimization problem rather than the difficulty of rounding a fractional solution.
Thus this technique is primarily suited to optimization problems where the multilinear optimization problem
captures closely the original discrete problem.

\section{From symmetry to inapproximability: proof}
\label{section:hardness-proof}

\paragraph{The roadmap}
At a high level,
our proof resembles the constructions of \cite{FMV07,MSV08}.
We construct instances based on continuous functions $F({\bf x})$, $G({\bf x})$,
whose optima differ by a gap
for which we want to prove hardness. Then we show that after a certain perturbation,
the two instances are very hard to distinguish.
This paper generalizes the ideas of \cite{FMV07,MSV08} and brings
two new ingredients. First, we show that the functions
$F({\bf x}), G({\bf x})$, which are ``pulled out of the hat'' in \cite{FMV07,MSV08},
can be produced in a natural way from the multilinear relaxation
of the respective problem, using the notion of a {\em symmetry gap}.
Secondly, the functions $F({\bf x}), G({\bf x})$ are perturbed in a way that makes
them indistinguishable and this forms the main technical part
of the proof. In \cite{FMV07}, this step is quite simple.
In \cite{MSV08}, the perturbation is more complicated, but still relies
on properties of the functions $F({\bf x}), G({\bf x})$ specific to that application.
The construction that we present here (Lemma~\ref{lemma:final-fix})
uses the symmetry properties of a fixed instance in a generic fashion.

\

First, let us present an outline of our construction. Given an instance
$\max \{f(S): S \in {\cal F}\}$ exhibiting a symmetry gap $\gamma$,
we consider two smooth submodular\footnote{"Smooth submodularity"
means the condition $\mixdiff{F}{x_i}{x_j} \leq 0$ for all $i,j$.}
functions, $F({\bf x})$ and $G({\bf x})$.
The first one is the multilinear extension $F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$,
while the second one is its symmetrized version $G({\bf x}) = F(\bar{{\bf x}})$.
We modify these functions slightly so that we obtain
functions $\hat{F}({\bf x})$ and $\hat{G}({\bf x})$ with the following property:
For any vector ${\bf x}$ which is close to its symmetrized version
$\bar{{\bf x}}$, $\hat{F}({\bf x}) = \hat{G}({\bf x})$.
The functions $\hat{F}({\bf x}), \hat{G}({\bf x})$ induce instances of
submodular maximization on the refined ground sets. The way we define
discrete instances based on $\hat{F}({\bf x}), \hat{G}({\bf x})$ is natural,
using the following lemma.
Essentially, we interpret the fractional variables as fractions of clusters
in the refined instance.

\begin{lemma}
\label{lemma:smooth-submodular}
Let $F:[0,1]^X \rightarrow {\boldmath R}$,
 $N = [n]$, $n \geq 1$, and define $f:2^{N \times X} \rightarrow {\boldmath R}$
so that $f(S) = F({\bf x})$ where $x_i = \frac{1}{n} |S \cap (N \times \{i\})|$. Then
\begin{enumerate}
\item If $\partdiff{F}{x_i} \geq 0$ everywhere for each $i$, then
$f$ is monotone.
\item If  the first partial derivatives of $F$ are absolutely continuous\footnote{
A function $F:[0,1]^X \rightarrow {\boldmath R}$ is absolutely continuous,
if $\forall \epsilon>0; \exists \delta>0; \sum_{i=1}^{t} ||{\bf x}_i-{\bf y}_i|| < \delta \Rightarrow
\sum_{i=1}^{t} |F({\bf x}_i) - F({\bf y}_i)| < \epsilon$.} and $\mixdiff{F}{x_i}{x_j} \leq 0$ almost everywhere for all $i,j$,
then $f$ is submodular.
\end{enumerate}
\end{lemma}

\begin{proof}
First, assume $\partdiff{F}{x_i} \geq 0$ everywhere for all $i$. This implies that $F$ is nondecreasing in every coordinate,
i.e. $F({\bf x}) \leq F({\bf y})$ whenever ${\bf x} \leq {\bf y}$. This means that $f(S) \leq f(T)$ whenever $S \subseteq T$.

Next, assume $\partdiff{F}{x_i}$ is absolutely continuous for each $i$ and $\mixdiff{F}{x_j}{x_i} \leq 0$ almost everywhere for all $i,j$.
We want to prove that $\partdiff{F}{x_i} |_{\bf x} \geq \partdiff{F}{x_i} |_{\bf y}$ whenever ${\bf x} \leq {\bf y}$, which implies that the marginal
values of $f$ are nonincreasing.

Let ${\bf x} \leq {\bf y}$,
fix $\delta>0$ arbitrarily small, and pick ${\bf x}',{\bf y}'$ such that $||{\bf x}'-{\bf x}||<\delta, ||{\bf y}'-{\bf y}||<\delta, {\bf x}' \leq {\bf y}'$ and
on the line segment $[{\bf x}', {\bf y}']$, we have $\mixdiff{F}{x_j}{x_i} \leq 0$ except for a set of (1-dimensional) measure zero. If such a pair of points
${\bf x}', {\bf y}'$ does not exist, it means that there are sets $A,B$ of positive measure such that
${\bf x} \in A, {\bf y} \in B$ and for any
${\bf x}' \in A, {\bf y}' \in B$, the line segment $[{\bf x}',{\bf y}']$ contains a subset of positive (1-dimensional) measure where $\mixdiff{F}{x_j}{x_i}$
for some $j$ is positive or undefined. This would imply that $[0,1]^X$ contains a subset of positive measure where
$\mixdiff{F}{x_j}{x_i}$ for some $j$ is positive or undefined, which we assume is not the case.

Therefore, there is a pair of points ${\bf x}', {\bf y}'$ as described above.
We compare $\partdiff{F}{x_i} |_{{\bf x}'}$ and $\partdiff{F}{x_i} |_{{\bf y}'}$
by integrating along the line segment $[{\bf x}', {\bf y}']$. Since $\partdiff{F}{x_i}$ is absolutely continuous and $\partdiff{}{x_j} \partdiff{F}{x_i} = \mixdiff{F}{x_j}{x_i} \leq 0$ along this line segment for all $j$ except for a set of measure zero, we obtain $\partdiff{F}{x_i} |_{{\bf x}'} \geq \partdiff{F}{x_i} |_{{\bf y}'}$. This is true for ${\bf x}', {\bf y}'$ arbitrarily
close to ${\bf x}, {\bf y}$, and hence by continuity of $\partdiff{F}{x_i}$, we get $\partdiff{F}{x_i} |_{{\bf x}} \geq \partdiff{F}{x_i} |_{{\bf y}}$.
This implies that the marginal values of $f$ are nonincreasing.
\end{proof}

The way we construct $\hat{F}({\bf x}), \hat{G}({\bf x})$ is such that,
given a large enough refinement of the ground set,
it is impossible to distinguish the instances corresponding to
$\hat{F}({\bf x})$ and $\hat{G}({\bf x})$. As we argue more precisely later,
this holds because if the ground set is large and labeled in a random way
(considering the symmetry group of the instance), a query about a vector ${\bf x}$
effectively becomes a query about the symmetrized vector $\bar{{\bf x}}$.
We would like this property to imply that all queries with high probability fall
in the region where $\hat{F}({\bf x}) = \hat{G}({\bf x})$ and the inability to distinguish between $\hat{F}$
and $\hat{G}$ gives the hardness result that we want.
The following lemma gives the precise properties of $\hat{F}({\bf x})$
and $\hat{G}({\bf x})$ that we need.

\begin{lemma}
\label{lemma:final-fix}
Consider a function $f:2^X \rightarrow {\boldmath R}_+$ invariant under a group
of permutations $\cal G$ on the ground set $X$.
Let $F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$, $\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$,
and fix any $\epsilon > 0$.
Then there is $\delta > 0$ and functions $\hat{F}, \hat{G}:[0,1]^X \rightarrow {\boldmath R}_+$
(which are also symmetric with respect to ${\cal G}$), satisfying:
\begin{enumerate}
\item For all ${\bf x} \in [0,1]^X$, $\hat{G}({\bf x}) = \hat{F}(\bar{{\bf x}})$.
\item For all ${\bf x} \in [0,1]^X$, $|\hat{F}({\bf x}) - F({\bf x})| \leq \epsilon$.
\item Whenever $||{\bf x} - \bar{{\bf x}}||^2 \leq \delta$, $\hat{F}({\bf x}) = \hat{G}({\bf x})$
and the value depends only on $\bar{{\bf x}}$.
\item The first partial derivatives of $\hat{F}, \hat{G}$ are absolutely continuous.
\item If $f$ is monotone, then $\partdiff{\hat{F}}{x_i} \geq 0$ and
   $\partdiff{\hat{G}}{x_i} \geq 0$ everywhere.
\item If $f$ is submodular, then $\mixdiff{\hat{F}}{x_i}{x_j} \leq 0$ and
   $\mixdiff{\hat{G}}{x_i}{x_j} \leq 0$ almost everywhere.
\end{enumerate}
\end{lemma}

The proof of this lemma is the main technical part of this paper
and we defer it to the end of this section. Assuming this lemma,
we first finish the proof of the main theorem. We prove the following.

\begin{lemma}
\label{lemma:indistinguish}
Let $\hat{F}, \hat{G}$ be the two functions provided by Lemma~\ref{lemma:final-fix}.
For a parameter $n \in {\boldmath Z}_+$ and $N = [n]$, define two discrete functions
$\hat{f}, \hat{g}: 2^{N \times X} \rightarrow {\boldmath R}_+$ as follows:
Let $\sigma^{(i)}$ be an arbitrary permutation in ${\cal G}$ for each $i \in N$.
For every set $S \subseteq N \times X$, we define a vector $\xi(S) \in [0,1]^X$ by
$$ \xi_j(S) = \frac{1}{n} \left|\{i \in N: (i,\sigma^{(i)}(j)) \in S \}\right|.$$
Let us define:
$$ \hat{f}(S) = \hat{F}(\xi(S)), \ \ \ \ \ \hat{g}(S) = \hat{G}(\xi(S)).$$
In addition, let $\tilde{{\cal F}} = \{\tilde{S}: \xi(\tilde{S}) \in P({\cal F})\}$
be a feasibility constraint such that the condition $S \in {\cal F}$ depends
only on the symmetrized vector $\overline{{\bf 1}_S}$.
Then deciding whether an instance given by value/membership oracles is
$\max \{\hat{f}(S): S \in \tilde{{\cal F}}\}$ or $\max \{\hat{g}(S): S \in \tilde{{\cal F}} \}$
(even by a randomized algorithm, with any constant probability of success)
requires an exponential number of queries.
\end{lemma}

\begin{proof}
Let $\sigma^{(i)} \in {\cal G}$ be chosen independently at random for each $i \in N$ and consider the instances
$\max\{\hat{f}(S): S \in \tilde{{\cal F}} \}$, $\max \{\hat{g}(S): S \in \tilde{{\cal F}} \}$ as described in the lemma. We show that
every deterministic algorithm will follow the same computation path and return the same answer on both instances,
with high probability. By Yao's principle, this means that every randomized algorithm returns
the same answer for the two instances with high probability, for some particular $\sigma^{(i)} \in {\cal G}$.

The feasible sets in the refined instance, $S \in \tilde{{\cal F}}$, are such that
the respective vector $\xi(S)$ is in the polytope $P({{\cal F}})$.
Since the instance is strongly symmetric, the condition $S \in {\cal F}$ depends
only on the symmetrized vector $\overline{{\bf 1}_S}$. Hence, the condition $\xi(S) \in P({\cal F})$
depends only on the symmetrized vector $\overline{\xi(S)}$. Therefore, $S \in \tilde{{\cal F}} \Leftrightarrow
\xi(S) \in P({\cal F}) \Leftrightarrow \overline{\xi(S)} \in P({\cal F})$.
We have $\overline{\xi(S)}_j = {\bf E}_{\sigma \in {\cal G}}[\frac{1}{n} \left|\{i \in N: (i,\sigma^{(i)}(\sigma(j))) \in S \}\right|].$ The distribution of $\sigma^{(i)} \circ \sigma$ is the same as that of $\sigma$, i.e.~uniform over ${\cal G}$. Hence, $\overline{\xi(S)}_j$ and consequently the condition $S \in \tilde{{\cal F}}$ does not depend on $\sigma^{(i)}$ in any way.
Intuitively, an algorithm cannot learn any information about the permutations $\sigma^{(i)}$ by querying the feasibility oracle,
since the feasibility condition $S \in \tilde{{\cal F}}$ does not depend on $\sigma^{(i)}$ for any $i \in N$.

The main part of the proof is to show that even queries to the objective function are unlikely to reveal
any information about the permutations $\sigma^{(i)}$.
The key observation is that for any fixed query $Q$ to the objective function,
the associated vector ${\bf q} = \xi(Q)$ is very likely to be close
to its symmetrized version $\bar{{\bf q}}$.
To see this, consider a query $Q$. The associated vector ${\bf q} = \xi(Q)$
is determined by
$$ q_j = \frac{1}{n} |\{i \in N: (i,\sigma^{(i)}(j)) \in Q\}|
 = \frac{1}{n} \sum_{i=1}^{n} Q_{ij} $$
where $Q_{ij}$ is an indicator variable of the event $(i,\sigma^{(i)}(j)) \in Q$.
This is a random event due to the randomness in $\sigma^{(i)}$.
We have
$$ {\bf E}[Q_{ij}] = \Pr[Q_{ij}=1] = \Pr_{\sigma^{(i)} \in {\cal G}}[(i,\sigma^{(i)}(j)) \in Q].$$
Adding up these expectations over $i \in N$, we get
$$ \sum_{i \in N} {\bf E}[Q_{ij}]
 = \sum_{i \in N} \Pr_{\sigma^{(i)} \in {\cal G}}[(i,\sigma^{(i)}(j)) \in Q]
 = {\bf E}_{\sigma \in {\cal G}} [|\{i \in N: (i,\sigma(j)) \in Q \}|].$$
For the purposes of expectation, the independence of $\sigma^{(1)},
 \ldots, \sigma^{(n)}$ is irrelevant and that is why we replace them by one random permutation $\sigma$.
On the other hand, consider the symmetrized vector $\bar{{\bf q}}$, with coordinates
$$ \bar{q}_j = {\bf E}_{\sigma \in {\cal G}}[q_{\sigma(j)}]
 = \frac{1}{n} {\bf E}_{\sigma \in {\cal G}}[|\{i \in N: (i,\sigma^{(i)}(\sigma(j))) \in Q\}|]
 = \frac{1}{n} {\bf E}_{\sigma \in {\cal G}}[|\{i \in N: (i,\sigma(j)) \in Q \}|] $$
using the fact that the distribution of $\sigma^{(i)} \circ \sigma$
is the same as the distribution of $\sigma$ - uniformly random over ${\cal G}$.
Note that the vector ${\bf q}$ depends on the random permutations $\sigma^{(i)}$
but the symmetrized vector $\bar{{\bf q}}$ does not; this will be also useful
in the following. For now, we summarize that
$$ \bar{q}_j = \frac{1}{n} \sum_{i=1}^{n} {\bf E}[Q_{ij}] = {\bf E}[q_j].$$
Since each permutation $\sigma^{(i)}$ is chosen independently, the random variables
$\{Q_{ij}: 1 \leq i \leq n\}$ are independent (for a fixed $j$).
We can apply Chernoff's bound (see e.g. \cite{AlonSpencer}, Corollary A.1.7):
$$ \Pr\left[\left|\sum_{i=1}^{n} Q_{ij}- \sum_{i=1}^{n} {\bf E}[Q_{ij}] \right| > a \right]
 < 2e^{-2a^2 / n}.$$
Using $q_j = \frac{1}{n} \sum_{i=1}^{n} Q_{ij}$,
 $\bar{q}_j = \frac{1}{n} \sum_{i=1}^{n} {\bf E}[Q_{ij}]$
and setting $a = n \sqrt{\delta/|X|}$, we obtain
$$ \Pr\left[|q_j - \bar{q}_j| > \sqrt{{\delta}/{|X|}}\right]
 < 2e^{-2 n \delta / |X|}.$$
By the union bound,
\begin{equation}
\label{eq:D(q)}
  \Pr[||{\bf q}-\bar{{\bf q}}||^2 > \delta] \leq \sum_{j \in X} \Pr[|q_j-\bar{q}_j|^2 > {\delta}/{|X|}] < 2|X| e^{-2n \delta/|X|}.
\end{equation}
Note that while $\delta$ and $|X|$ are constants, $n$ grows as the size
of the refinement and hence the probability is exponentially small in the
size of the ground set $N \times X$.

Define $D({\bf q}) = ||{\bf q}-\bar{{\bf q}}||^2$. As long as $D({\bf q}) \leq \delta$ for every query issued by the algorithm,
the answers do not depend on the randomness of the input. This is because
then the values of $\hat{F}({\bf q})$ and $\hat{G}({\bf q})$ depend only on $\bar{{\bf q}}$,
which is independent of the random permutations $\sigma^{(i)}$,
as we argued above.
Therefore, assuming that $D({\bf q}) \leq \delta$ for each query,
the algorithm will always follow the same path
of computation and issue the same sequence of queries $\cal S$.
(Note that this is just a fixed sequence which can be written down
before we started running the algorithm.)
Assume that $|{\cal S}| = e^{o(n)}$, i.e.,~the number of queries is subexponential in $n$.
By (\ref{eq:D(q)}), using a union bound over all $Q \in {\cal S}$,
it happens with probability $1 - e^{-\Omega(n)}$ that ${D}({\bf q}) = ||{\bf q}-\bar{{\bf q}}||^2 \leq \delta$ for all $Q \in {\cal S}$.
(Note that $\delta$ and $|X|$ are constants here.)
Then, the algorithm indeed follows this path of computation and gives the same answer.
In particular, the answer does not depend on whether the instance is $\max \{\hat{f}(S): S \in \tilde{{\cal F}}\}$
or $\max \{\hat{g}(S): S \in \tilde{{\cal F}}\}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:general-hardness}]
Fix an $\epsilon > 0$.
Given an instance $\max \{f(S): S \in {\cal F}\}$
strongly symmetric under ${\cal G}$, let $\hat{F}, \hat{G}: [0,1]^X \rightarrow {\boldmath R}$
be the two functions provided by Lemma~\ref{lemma:final-fix}.
We choose a large number $n$ and consider a refinement $\tilde{{\cal F}}$
on the ground set $N \times X$, where $N = [n]$.
We define discrete instances of submodular maximization
$\max \{ \hat{f}(S): S \in \tilde{{\cal F}} \}$ and $\max \{ \hat{g}(S): S \in \tilde{{\cal F}} \}$.
As in Lemma~\ref{lemma:indistinguish}, for each $i \in N$
we choose a random permutation $\sigma^{(i)} \in {\cal G}$.
This can be viewed as a random shuffle of the labeling of the ground set
before we present it to an algorithm.
For every set $S \subseteq N \times X$, we define a vector $\xi(S) \in [0,1]^X$ by
$$ \xi_j(S) = \frac{1}{n} \left|\{i \in N: (i,\sigma^{(i)}(j)) \in S \}\right|.$$
In other words, $\xi_j(S)$ measures the fraction of copies of element $j$
contained in $S$; however, for each $i$ the $i$-copies of all elements
are shuffled by $\sigma^{(i)}$. Next, we define
$$ \hat{f}(S) = \hat{F}(\xi(S)), \ \ \ \ \ \hat{g}(S) = \hat{G}(\xi(S)).$$
We claim that $\hat{f}$ and $\hat{g}$ are submodular (for any fixed $\xi$).
Note that the effect
of $\sigma^{(i)}$ is just a renaming (or shuffling) of the elements
of $N \times X$, and hence for the purpose of proving submodularity we can assume
that $\sigma^{(i)}$ is the identity for all $i$. Then, $\xi_j(S) = \frac{1}{n}
 |S \cap (N \times \{j\})|$. Due to Lemma~\ref{lemma:smooth-submodular},
the property $\mixdiff{\hat{F}}{x_i}{x_j} \leq 0$ (almost everywhere) implies that $\hat{f}$ is submodular.
In addition, if the original instance was monotone, then $\partdiff{\hat{F}}{x_j} \geq 0$
and $\hat{f}$ is monotone. The same holds for $\hat{g}$.

The value of $\hat{g}(S)$ for any feasible solution $S \in \tilde{{\cal F}}$
is bounded by $\hat{g}(S) = \hat{G}(\xi(S)) = \hat{F}(\overline{\xi(S)})
\leq \overline{OPT} + \epsilon$.
On the other hand, let ${\bf x}^*$ denote a point where the optimum of the continuous problem
$\max \{\hat{F}({\bf x}): {\bf x} \in P({{\cal F}}) \}$ is attained, i.e. $\hat{F}({\bf x}^*) \geq OPT - \epsilon$.
For a large enough $n$, we can approximate the point ${\bf x}^*$ arbitrarily closely
by a rational vector with $n$ in the denominator,
which corresponds to a discrete solution $S^* \in \tilde{{\cal F}}$ whose
value $\hat{f}(S^*)$ is at least, say, $OPT - 2 \epsilon$.
Hence, the ratio between the optima of the {\em discrete} optimization
problems $\max \{\hat{f}(S): S \in \tilde{{\cal F}}\}$ and $\max \{\hat{g}(S): S \in \tilde{{\cal F}} \}$
can be made at most $\frac{\overline{OPT} + \epsilon}{OPT - 2 \epsilon}$, i.e. arbitrarily close
to the symmetry gap $\gamma = \frac{\overline{OPT}}{OPT}$.

By Lemma~\ref{lemma:indistinguish}, distinguishing the two instances
$\max \{\hat{f}(S): S \in \tilde{{\cal F}} \}$  and $\max \{\hat{g}(S): S \in \tilde{{\cal F}} \}$,
even by a randomized algorithm, requires an exponential number of value queries.
Therefore, we cannot estimate the optimum within a factor better than $\gamma$.
\end{proof}

Next, we prove Theorem~\ref{thm:multilinear-hardness} (again assuming Lemma~\ref{lemma:final-fix}),
i.e.~an analogous hardness result for solving the multilinear optimization problem.

\begin{proof}[Proof of Theorem~\ref{thm:multilinear-hardness}]
Given a symmetric instance $\max \{f(S): S \in {\cal F}\}$ and $\epsilon>0$, we construct
refined and modified instances $\max \{\hat{f}(S): S \in \tilde{{\cal F}} \}$,
 $\max \{\hat{g}(S): S \in \tilde{{\cal F}} \}$,
derived from the continuous functions $\hat{F}, \hat{G}$ provided by Lemma~\ref{lemma:final-fix},
exactly as we did in the proof of Theorem~\ref{thm:general-hardness}.
Lemma~\ref{lemma:indistinguish} states that these two instances cannot be distinguished using a subexponential number of value queries. Furthermore, the gap between the two modified instances corresponds to the symmetry gap $\gamma$ of the original instance: $\max \{\hat{f}(S): S \in \tilde{{\cal F}} \} \geq OPT - 2 \epsilon$ and $\max \{\hat{g}(S): S \in \tilde{{\cal F}} \} \leq \overline{OPT} + \epsilon = \gamma OPT + \epsilon$.

Now we consider the multilinear relaxations of the two refined instances, $\max \{\check{F}({\bf x}): {\bf x} \in P(\tilde{{\cal F}})\}$
and $\max \{\check{G}({\bf x}): {\bf x} \in P(\tilde{{\cal F}})\}$. Note that $\check{F}, \check{G}$, (although related to $\hat{F},
\hat{G}$) are not exactly the same as the functions $\hat{F}, \hat{G}$; in particular, they are defined
on a larger (refined) domain. However, we show that the gap between the optima of the two instances remains
the same.

First, the value of $\max \{\check{F}({\bf x}): {\bf x} \in P({\cal F})\}$ is at least the optimum of the discrete problem,
$\max \{\hat{f}(S): S \in \tilde{{\cal F}} \}$, which is at least $OPT - 2\epsilon$ as in the proof of
Theorem~\ref{thm:general-hardness}. The value of $\max \{\check{G}({\bf x}): {\bf x} \in P({\cal F})\}$ can be analyzed as follows. For any fractional solution ${\bf x} \in P({\cal F})$, the value of $\check{G}({\bf x})$
is the expectation ${\bf E}[\hat{g}(\hat{{\bf x}})]$, where $\hat{{\bf x}}$ is obtained by independently rounding the
coordinates of ${\bf x}$ to $\{0,1\}$. Recall that $\hat{g}$ is obtained by discretizing the continuous function
$\hat{G}$ (using Lemma~\ref{lemma:smooth-submodular}). In particular, $\hat{g}(S) = \hat{G}(\tilde{{\bf x}})$ where
$\tilde{x}_i = \frac{1}{n} |S \cap (N \times \{i\})|$ is the fraction of the respective cluster contained in $S$, and $|N| = n$ is the size of each cluster (the refinement parameter). If ${\bf 1}_S = \hat{{\bf x}}$, i.e. $S$ is chosen by independent sampling with probabilities according to ${\bf x}$, then for large $n$ the fractions $\frac{1}{n}|S \cap (N \times \{i\})|$ will be strongly concentrated around their expectation. As $\hat{G}$ is continuous, we get
$\lim_{n \rightarrow \infty} {\bf E}[\hat{g}(\hat{{\bf x}})] = \lim_{n \rightarrow \infty} {\bf E}[\hat{G}(\tilde{{\bf x}})]
 = \hat{G}({\bf E}[\tilde{{\bf x}}]) = \hat{G}(\bar{{\bf x}})$.
Here, $\bar{{\bf x}}$ is the vector ${\bf x}$ projected back to the original ground set $X$, where the coordinates
of each cluster have been averaged. By construction of the refinement, if ${\bf x} \in P(\tilde{{\cal F}})$ then
$\bar{{\bf x}}$ is in the polytope corresponding to the original instance, $P({\cal F})$.
Therefore, $\hat{G}(\bar{{\bf x}}) \leq
\max \{\hat{G}({\bf x}): {\bf x} \in P({\cal F}) \} \leq \gamma OPT + \epsilon$. For large enough $n$, this means that
$\max \{\check{G}({\bf x}): {\bf x} \in P(\tilde{{\cal F}}) \} \leq \gamma OPT + 2 \epsilon$. This holds for
an arbitrarily small fixed $\epsilon>0$, and hence the gap between the instances
$\max \{\check{F}({\bf x}): {\bf x} \in P(\tilde{{\cal F}})\}$ and $\max \{\check{G}({\bf x}): {\bf x} \in P(\tilde{{\cal F}})\}$
(which cannot be distinguished) can be made arbitrarily close to $\gamma$.
\end{proof}

\paragraph{Hardness for symmetric instances}
We remark that since Lemma~\ref{lemma:final-fix} provides functions $\hat{F}$ and $\hat{G}$ symmetric
under ${\cal G}$, the refined instances that we define are invariant with respect to
the following symmetries: permute the copies of each element in an arbitrary
way, and permute the classes of copies according to any permutation
$\sigma \in {\cal G}$. This means that our hardness results also hold
for instances satisfying such symmetry properties.

\

It remains to prove Lemma~\ref{lemma:final-fix}.
Before we move to the final construction of $\hat{F}({\bf x})$ and $\hat{G}({\bf x})$,
we construct as an intermediate step a function $\tilde{F}({\bf x})$ which is helpful
in the analysis.

\

\paragraph{Construction}
Let us construct a function $\tilde{F}({\bf x})$ which satisfies the following:
\begin{itemize}
\item For ${\bf x}$ ``sufficiently close'' to $\bar{{\bf x}}$, $\tilde{F}({\bf x}) = G({\bf x})$.
\item For ${\bf x}$ ``sufficiently far away'' from $\bar{{\bf x}}$, $\tilde{F}({\bf x}) \simeq F({\bf x})$.
\item The function $\tilde{F}({\bf x})$ is ``approximately" smooth submodular.
\end{itemize}
Once we have $\tilde{F}({\bf x})$, we can fix it to obtain a smooth submodular
function $\hat{F}({\bf x})$, which is still close to the original function $F({\bf x})$.
We also fix $G({\bf x})$ in the same way, to obtain a function $\hat{G}({\bf x})$
which is equal to $\hat{F}({\bf x})$ whenever ${\bf x}$ is close to $\bar{{\bf x}}$. We defer
this step until the end.

We define $\tilde{F}({\bf x})$ as a convex linear combination
of $F({\bf x})$ and $G({\bf x})$, guided by a ``smooth transition'' function, depending
on the distance of ${\bf x}$ from $\bar{{\bf x}}$. The form that we use is the following:\footnote{We remark
that a construction analogous to \cite{MSV08}
would be $\tilde{F}({\bf x}) = F({\bf x}) - \phi(H({\bf x}))$ where $H({\bf x}) = F({\bf x}) - G({\bf x})$.
While this makes the analysis easier in \cite{MSV08}, it cannot be used in general.
Roughly speaking, the problem is that in general the partial derivatives of $H({\bf x})$
are not bounded in any way by the value of $H({\bf x})$.}
$$ \tilde{F}({\bf x}) = (1-\phi(D({\bf x}))) F({\bf x}) + \phi(D({\bf x})) G({\bf x}) $$
where $\phi:{\boldmath R}_+ \rightarrow [0,1]$ is a suitable smooth function,
and
$$ D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2 = \sum_i (x_i - \bar{x}_i)^2.$$
The idea is that when ${\bf x}$ is close to $\bar{{\bf x}}$, $\phi(D({\bf x}))$ should be close to $1$,
i.e. the convex linear combination should give most of the weight to $G({\bf x})$.
The weight should shift gradually to $F({\bf x})$ as ${\bf x}$ gets further away from $\bar{{\bf x}}$.
Therefore, we define $\phi(t) = 1$ in a small interval $t \in [0,\delta]$,
and $\phi(t)$ tends to $0$ as $t$ increases.
This guarantees that $\tilde{F}({\bf x}) = G({\bf x})$ whenever
$D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2 \leq \delta$.
We defer the precise construction of $\phi(t)$ to Lemma~\ref{lemma:phi-construction},
after we determine what properties we need from $\phi(t)$.
Note that regardless of the definition of $\phi(t)$, $\tilde{F}({\bf x})$
is symmetric with respect to ${\cal G}$, since $F({\bf x}), G({\bf x})$ and $D({\bf x})$ are.

\

\paragraph{Analysis of the construction}
Due to the construction of $\tilde{F}({\bf x})$, it is clear that when
$D({\bf x}) = ||{\bf x}-\bar{{\bf x}}||^2$ is small, $\tilde{F}({\bf x}) = G({\bf x})$.
When $D({\bf x})$ is large, $\tilde{F}({\bf x}) \simeq F({\bf x})$.
The main issue, however, is whether we can say something about the first
and second partial derivatives of $\tilde{F}$. This is crucial for
the properties of monotonicity and submodularity, which we would like to preserve.
Let us write $\tilde{F}({\bf x})$ as
$$ \tilde{F}({\bf x}) = F({\bf x}) - \phi(D({\bf x})) H({\bf x}) $$
where $H({\bf x}) = F({\bf x}) - G({\bf x})$. By differentiating once, we get
\begin{equation}
\label{eq:partdiff}
\partdiff{\tilde{F}}{x_i} = \partdiff{F}{x_i} - \phi(D({\bf x})) \partdiff{H}{x_i}
 - \phi'(D({\bf x})) \partdiff{D}{x_i} H({\bf x})
\end{equation}
and by differentiating twice,
\begin{eqnarray}
\label{eq:mixdiff}
 \mixdiff{\tilde{F}}{x_i}{x_j} & = & \mixdiff{F}{x_i}{x_j}
- \phi({D}({\bf x})) \mixdiff{H}{x_i}{x_j}
 - \phi''({D}({\bf x})) \partdiff{{D}}{x_i} \partdiff{{D}}{x_j} H({\bf x}) \\
 & & - \phi'({D}({\bf x})) \left( \partdiff{{D}}{x_j} \partdiff{H}{x_i}
  + \mixdiff{{D}}{x_i}{x_j} H({\bf x}) + \partdiff{{D}}{x_i} \partdiff{H}{x_j} \right) \nonumber.
\end{eqnarray}

The first two terms on the right-hand sides of (\ref{eq:partdiff}) and
(\ref{eq:mixdiff}) are not bothering us, because they form
convex linear combinations of the derivatives of $F({\bf x})$ and $G({\bf x})$,
which have the properties that we need. The remaining terms might cause
problems, however, and we need to estimate them.

Our strategy is to define $\phi(t)$ in such a way that it eliminates
the influence of partial derivatives of $D$ and $H$ where they become too large.
Roughly speaking, $D$ and $H$ have negligible partial derivatives when ${\bf x}$
is very close to $\bar{{\bf x}}$. As ${\bf x}$ moves away from $\bar{{\bf x}}$, the partial
derivatives grow but then the behavior of $\phi(t)$ must be such that
their influence is supressed.

We start with the following important claim.\footnote{
We remind the reader that $\nabla F$, the gradient of $F$, is a vector
whose coordinates are the first partial derivatives $\partdiff{F}{x_i}$.
We denote by $\nabla F |_{{\bf x}}$ the gradient evaluated at ${\bf x}$.}

\begin{lemma}
\label{lemma:grad-symmetry}
Assume that $F:[0,1]^X \rightarrow {\boldmath R}$ is differentiable and invariant under a group of
permutations of coordinates ${\cal G}$. Let $G({\bf x}) = F(\bar{{\bf x}})$,
where $\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$.
Then for any ${\bf x} \in [0,1]^X$,
 $$ \nabla{G}|_{\bf x} = \nabla{F}|_{\bar{{\bf x}}}.$$
\end{lemma}

\begin{proof}
To avoid confusion, we use ${\bf x}$ for the arguments of the functions $F$ and $G$,
and ${\bf u}$, $\bar{{\bf u}}$, etc. for points where their partial derivatives are evaluated.
To rephrase, we want to prove that for any point ${\bf u}$ and any coordinate $i$,
the partial derivatives of $F$ and $G$ evaluated at $\bar{u}$ are equal:
$\partdiff{G}{x_i} \Big|_{{\bf x}={\bf u}} = \partdiff{F}{x_i} \Big|_{{\bf x}=\bar{{\bf u}}}$.

First, consider $F({\bf x})$. We assume that $F({\bf x})$ is invariant under
a group of permutations of coordinates $\cal G$,
i.e. $F({\bf x}) = F(\sigma({\bf x}))$ for any $\sigma \in {\cal G}$.
Differentiating both sides at ${\bf x}={\bf u}$, we get by the chain rule:
$$ \partdiff{F}{x_i} \Big|_{{\bf x}={\bf u}} =
 \sum_j \partdiff{F}{x_j} \Big|_{{\bf x}=\sigma({\bf u})} \partdiff{}{x_i} (\sigma({\bf x}))_j
 = \sum_j \partdiff{F}{x_j} \Big|_{{\bf x}=\sigma({\bf u})} \partdiff{x_{\sigma(j)}}{x_i}. $$
Here, $\partdiff{x_{\sigma(j)}}{x_i} = 1$ if $\sigma(j) = i$, and $0$ otherwise.
Therefore,
$$ \partdiff{F}{x_i} \Big|_{{\bf x}={\bf u}} =
 \partdiff{F}{x_{\sigma^{-1}(i)}} \Big|_{{\bf x}=\sigma({\bf u})}. $$
Now, if we evaluate the left-hand side at $\bar{{\bf u}}$, the right-hand side is evaluated
at $\sigma(\bar{{\bf u}}) = \bar{{\bf u}}$, and hence for any $i$ and any $\sigma \in {\cal G}$,
\begin{equation}
\label{eq:F-inv}
\partdiff{F}{x_i} \Big|_{{\bf x}=\bar{{\bf u}}} = \partdiff{F}{x_{\sigma^{-1}(i)}} \Big|_{{\bf x}=\bar{{\bf u}}}.
\end{equation}
Turning to $G({\bf x}) = F(\bar{{\bf x}})$, let us write $\partdiff{G}{x_i}$
using the chain rule:
$$ \partdiff{G}{x_i} \Big|_{{\bf x}={\bf u}} = \partdiff{}{x_i} F(\bar{{\bf x}}) \Big|_{{\bf x}={\bf u}}
 = \sum_j \partdiff{F}{x_j} \Big|_{{\bf x}=\bar{{\bf u}}} \cdot \partdiff{\bar{x}_j}{x_i}. $$
We have $\bar{x}_j = {\bf E}_{\sigma \in {\cal G}}[{\bf x}_{\sigma(j)}]$, and
so
$$ \partdiff{G}{x_i} \Big|_{{\bf x}={\bf u}} = \sum_j \partdiff{F}{x_j} \Big|_{{\bf x}=\bar{{\bf u}}}
 \cdot \partdiff{}{x_i} {\bf E}_{\sigma \in {\cal G}}[x_{\sigma(j)}]
 = {\bf E}_{\sigma \in {\cal G}} \left[\sum_j \partdiff{F}{x_j} \Big|_{x=\bar{u}}
 \cdot \partdiff{x_{\sigma(j)}}{x_i} \right]. $$
Again, $\partdiff{x_{\sigma(j)}}{x_i} = 1$ if $\sigma(j) = i$ and $0$ otherwise.
Consequently, we obtain
$$ \partdiff{G}{x_i} \Big|_{{\bf x}={\bf u}} = {\bf E}_{\sigma \in {\cal G}}
 \left[ \partdiff{F}{x_{\sigma^{-1}(i)}} \Big|_{{\bf x}=\bar{{\bf u}}} \right]
 = \partdiff{F}{x_i} \Big|_{{\bf x}=\bar{{\bf u}}} $$
where we used Eq. (\ref{eq:F-inv}) to remove the dependence on $\sigma \in {\cal G}$.
\end{proof}

Observe that the symmetrization operation $\bar{{\bf x}}$ is idempotent, i.e.
$\bar{\bar{{\bf x}}} = \bar{{\bf x}}$.
Because of this, we also get $\nabla{G}|_{\bar{{\bf x}}} = \nabla{F}|_{\bar{{\bf x}}}$.
Note that $G(\bar{{\bf x}}) = F(\bar{{\bf x}})$ follows from the definition,
but it is not obvious that the same holds for gradients, since their
definition involves points where $G({\bf x}) \neq F({\bf x})$. For second partial
derivatives, the equality no longer holds, as can be seen from
a simple example such as $F(x_1,x_2) = 1 - (1-x_1)(1-x_2)$,
$G(x_1,x_2) = 1 - (1-\frac{x_1+x_2}{2})^2$.

Next, we show that the functions $F({\bf x})$ and $G({\bf x})$ are very similar
in the close vicinity of the region where $\bar{{\bf x}} = {\bf x}$. Recall our definitions:
$H({\bf x}) = F({\bf x}) - G({\bf x})$, $D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2$.
Based on Lemma~\ref{lemma:grad-symmetry}, we know that $H(\bar{{\bf x}}) = 0$
and $\nabla H|_{\bar{{\bf x}}} = 0$. In the following lemmas,
we present bounds on $H({\bf x})$, $D({\bf x})$ and their partial derivatives.

\begin{lemma}
\label{lemma:H-bounds}
Let $f:2^X \rightarrow [0,M]$ be invariant under a permutation group $\cal G$.
Let $\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$,
$D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2$ and $H({\bf x}) = F({\bf x}) - G({\bf x})$ where $F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$
and $G({\bf x}) = F(\bar{{\bf x}})$. Then
\begin{enumerate}
\item  $ |\mixdiff{H}{x_i}{x_j}| \leq 8M $ everywhere, for all $i,j$;
\item  $ ||\nabla H({\bf x})|| \leq 8M|X| \sqrt{D({\bf x})}$;
\item  $ |H({\bf x})| \leq  8M|X| \cdot D({\bf x}). $
\end{enumerate}
\end{lemma}

\begin{proof}
First, let us get a bound on the second partial derivatives.
Assuming without loss of generality $x_i=x_j=0$, we have\footnote{${\bf x} \vee {\bf y}$
denotes the coordinate-wise maximum, $({\bf x} \vee {\bf y})_i = \max \{x_i,y_i\}$ and
${\bf x} \wedge {\bf y}$ denotes the coordinate-wise minimum, $({\bf x} \wedge {\bf y})_i = \min \{x_i,y_i\}$.}
$$ \mixdiff{F}{x_i}{x_j} =  {\bf E}[f(\hat{{\bf x}} \vee ({\bf e}_i+{\bf e}_j)) -
 f(\hat{{\bf x}} \vee {\bf e}_i) - f(\hat{{\bf x}} \vee {\bf e}_j) + f(\hat{{\bf x}})] $$
(see \cite{Vondrak08}). Consequently,
$$ \Big| \mixdiff{F}{x_i}{x_j} \Big| \leq 4 \max |f(S)| = 4 M.$$
It is a little bit more involved to analyze $\mixdiff{G}{x_i}{x_j}$.
Since $G({\bf x}) = F(\bar{{\bf x}})$ and $\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$,
we get by the chain rule:
$$ \mixdiff{G}{x_i}{x_j} = \sum_{k,\ell} \mixdiff{F}{x_k}{x_\ell}
 \partdiff{\bar{x}_k}{x_i} \partdiff{\bar{x}_\ell}{x_j}
 = {\bf E}_{\sigma,\tau \in {\cal G}} \left[ \sum_{k,\ell} \mixdiff{F}{x_k}{x_\ell}
   \partdiff{x_{\sigma(k)}}{x_i} \partdiff{x_{\tau(\ell)}}{x_j} \right].$$
It is useful here to use the Kronecker symbol, $\delta_{i,j}$,
which is $1$ if $i=j$ and $0$ otherwise. Note that
$\partdiff{x_{\sigma(k)}}{x_i} = \delta_{i,\sigma(k)} = \delta_{\sigma^{-1}(i),k}$,
etc. Using this notation, we get
$$ \mixdiff{G}{x_i}{x_j} = {\bf E}_{\sigma,\tau \in {\cal G}} \left[  \sum_{k,\ell}
\mixdiff{F}{x_k}{x_\ell} \delta_{\sigma^{-1}(i),k} \delta_{\sigma^{-1}(j),\ell} \right]
 = {\bf E}_{\sigma,\tau \in {\cal G}}
 \left[ \mixdiff{F}{x_{\sigma^{-1}(i)}}{x_{\tau^{-1}(j)}} \right], $$
$$ \Big| \mixdiff{G}{x_i}{x_j} \Big| \leq {\bf E}_{\sigma,\tau \in {\cal G}}
\left[ \Big| \mixdiff{F}{x_{\sigma^{-1}(i)}}{x_{\tau^{-1}(j)}} \Big| \right]
 \leq 4 M $$
and therefore
$$ \Big| \mixdiff{H}{x_i}{x_j} \Big|
 = \Big| \mixdiff{F}{x_i}{x_j} - \mixdiff{G}{x_i}{x_j} \Big|
 \leq 8 M.$$

Next, we estimate $\partdiff{H}{x_i}$ at a given point ${\bf u}$, depending
on its distance from $\bar{{\bf u}}$. Consider
the line segment between $\bar{{\bf u}}$ and ${\bf u}$. The function $H({\bf x}) = F({\bf x}) - G({\bf x})$
is $C_\infty$-differentiable, and hence we can apply the mean value theorem
to $\partdiff{H}{x_i}$: There exists a point $\tilde{{\bf u}}$ on the line segment
$[\bar{{\bf u}}, {\bf u}]$ such that
$$ \partdiff{H}{x_i} \Big|_{{\bf x}={\bf u}} - \partdiff{H}{x_i} \Big|_{{\bf x}=\bar{{\bf u}}}
 = \sum_j \mixdiff{H}{x_j}{x_i} \Big|_{{\bf x}=\tilde{{\bf u}}} (u_j-\bar{u}_j).$$
Recall that $\partdiff{H}{x_i} \Big|_{{\bf x}=\bar{{\bf u}}} = 0$.
Applying the Cauchy-Schwartz inequality to the right-hand side, we get
$$ \left( \partdiff{H}{x_i} \Big|_{{\bf x}={\bf u}} \right)^2
 \leq \sum_j \left( \mixdiff{H}{x_j}{x_i} \Big|_{{\bf x}=\tilde{{\bf u}}} \right)^2
  || {\bf u} - \bar{{\bf u}} ||^2  \leq (8M)^2 |X| ||{\bf u} - \bar{{\bf u}}||^2.$$
Adding up over all $i \in X$, we obtain
$$ || \nabla H({\bf u}) ||^2 = \sum_{i}\left( \partdiff{H}{x_i} \Big|_{{\bf x}={\bf u}} \right)^2
 \leq (8M|X|)^2 ||{\bf u} - \bar{{\bf u}}||^2.$$
Finally, we estimate the growth of $H({\bf u})$. Again, by the mean value theorem,
there is a point $\tilde{{\bf u}}$ on the line segment $[\bar{{\bf u}},{\bf u}]$, such that
$$ H({\bf u}) - H(\bar{{\bf u}}) = ({\bf u} - \bar{{\bf u}}) \cdot \nabla H(\tilde{{\bf u}}).$$
Using $H(\bar{{\bf u}}) = 0$, the Cauchy-Schwartz inequality and the above bound
on $\nabla H$,
$$ (H({\bf u}))^2 \leq ||\nabla H({\tilde{{\bf u}}})||^2  ||{\bf u} - \bar{{\bf u}}||^2
 \leq (8M|X|)^2 ||\tilde{{\bf u}}-\bar{{\bf u}}||^2 ||{\bf u}-\bar{{\bf u}}||^2. $$
Clearly, $||\tilde{{\bf u}} - \bar{{\bf u}}|| \leq ||{\bf u} - \bar{{\bf u}}||$, and therefore
$$ |H({\bf u})| \leq 8M|X| \cdot ||{\bf u}-\bar{{\bf u}}||^2.$$
\end{proof}

\begin{lemma}
\label{lemma:D-bounds}
For the function $D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2$, we have
\begin{enumerate}
\item $\nabla D = 2({\bf x} - \bar{{\bf x}})$, and therefore
 $||\nabla D|| = 2 \sqrt{D({\bf x})}$.
\item For all $i,j$, $|\mixdiff{D}{x_i}{x_j}| \leq 2$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let us write $D({\bf x})$ as
$$ D({\bf x}) = \sum_i (x_i - \bar{x}_i)^2 = \sum_i {\bf E}_{\sigma \in {\cal G}}[x_i - x_{\sigma(i)}]
 {\bf E}_{\tau \in {\cal G}}[x_i - x_{\tau(i)}]. $$
Taking the first partial derivative,
$$ \partdiff{D}{x_j} = 2 \sum_i {\bf E}_{\sigma \in {\cal G}}[x_i - x_{\sigma(i)}]
 \partdiff{}{x_j} {\bf E}_{\tau \in {\cal G}}[x_i - x_{\tau(i)}].$$
As before, we have $\partdiff{x_i}{x_j} = \delta_{ij}$.
Using this notation, we get
\begin{eqnarray*}
\partdiff{D}{x_j} & = & 2 \sum_i {\bf E}_{\sigma \in {\cal G}}[x_i - x_{\sigma(i)}]
 {\bf E}_{\tau \in {\cal G}}[\delta_{ij} - \delta_{\tau(i),j}] \\
 & = & 2 \sum_i {\bf E}_{\sigma,\tau \in {\cal G}}[(x_i - x_{\sigma(i)})
    (\delta_{ij} - \delta_{i,\tau^{-1}(j)})] \\
 & = & 2 \ {\bf E}_{\sigma,\tau \in {\cal G}}[x_j - x_{\sigma(j)} - x_{\tau^{-1}(j)}
    + x_{\sigma(\tau^{-1}(j))}].
\end{eqnarray*}
Since the distributions of $\sigma(j)$, $\tau^{-1}(j)$ and $\sigma(\tau^{-1}(j))$
are the same, we obtain
$$ \partdiff{D}{x_j} = 2 \ {\bf E}_{\sigma \in {\cal G}}[x_j - x_{\sigma(j)}]
 = 2(x_j - \bar{x}_j) $$
and
$$ ||\nabla D||^2 = \sum_j \Big| \partdiff{D}{x_j} \Big|^2
 = 4 \sum_j (x_j - \bar{x}_j)^2 = 4 D({\bf x}).$$

Finally, the second partial derivatives are
$$ \mixdiff{D}{x_i}{x_j} = 2 \partdiff{}{x_i} (x_j - \bar{x}_j)
 = 2 \partdiff{}{x_i} {\bf E}_{\sigma \in {\cal G}}[x_j - x_{\sigma(j)}]
 = 2 {\bf E}_{\sigma \in {\cal G}}[\delta_{ij} - \delta_{i,\sigma(j)}] $$
which is clearly bounded by $2$ in the absolute value.
\end{proof}

Now we come back to $\tilde{F}({\bf x})$ and its partial derivatives.
Recall equations (\ref{eq:partdiff}) and (\ref{eq:mixdiff}).
The problematic terms are those involving $\phi'(D({\bf x}))$ and $\phi''(D({\bf x}))$.
Using our bounds on $H({\bf x})$, $D({\bf x})$ and their derivatives, however,
we notice that $\phi'(D({\bf x}))$ always appears with factors on the order
of $D({\bf x})$ and $\phi''(D({\bf x}))$ appears with factors on the order of $(D({\bf x}))^2$.
Thus, it is sufficient if $\phi(t)$ is defined so that we have control
over $t \phi'(t)$ and $t^2 \phi''(t)$. The following lemma describes
the function that we need.

\begin{lemma}
\label{lemma:phi-construction}
For any $\alpha, \beta > 0$, there is $\delta \in (0, \beta)$
and a function $\phi:{\boldmath R}_+ \rightarrow [0,1]$ with an absolutely continuous first derivative
such that
\begin{enumerate}
\item For $t \leq \delta$, $\phi(t) = 1$.
\item For $t \geq \beta$, $\phi(t) < e^{-1/\alpha}$.
\item For all $t \geq 0$, $|t \phi'(t)| \leq 4 \alpha$.
\item For almost all $t \geq 0$, $|t^2 \phi''(t)| \leq 10 \alpha$.
\end{enumerate}
\end{lemma}

\begin{proof}
First, observe that if we prove the lemma for some particular value $\beta>0$, we can also prove prove it
for any other value $\tilde{\beta}>0$, by modifying the function as follows: $\tilde{\phi}(t) = \phi(\beta t / \beta')$.
This corresponds to a scaling of the parameter $t$ by $\beta' / \beta$. Observe that then $|t \tilde{\phi}'(t)| = |\frac{\beta}{\beta'} t \phi'(\beta t / \beta')| \leq 4 \alpha$ and $|t^2 \tilde{\phi}''(t)| = |(\frac{\beta}{\beta'})^2 t^2 \phi''(\beta t / \beta')| \leq 10 \alpha$, so the conditions are still satisfied.

Therefore, we can assume without
loss of generality that $\beta>0$ is a value of our choice,
for example $\beta = e^{1/(2\alpha^2)}+1$.
If we want to prove the result for a different value of $\beta$,
we can just scale the argument $t$ and the constant $\delta$
by $\beta / (e^{1/(2\alpha^2)}+1)$; the bounds on
$t \phi'(t)$ and $t^2 \phi''(t)$ still hold.

We can assume that $\alpha \in (0,\frac18)$ because for larger $\alpha$,
the statement only gets weaker. As we argued, we can assume WLOG that
$\beta = e^{1/(2\alpha^2)}+1$. We set $\delta = 1$ and
$\delta_2 = 1 + (1+\alpha)^{-1/2} \leq 2$.
(We remind the reader that in general these values will be scaled depending
on the actual value of $\beta$.) We define the function as follows:
\begin{enumerate}
\item $\phi(t) = 1$ for $t \in [0,\delta]$.
\item $\phi(t) = 1 - \alpha (t-1)^2$ for $t \in [\delta, \delta_2]$.
\item $\phi(t) = (1+\alpha)^{-1-\alpha} (t - 1)^{-2 \alpha}$
 for $t \in [\delta_2, \infty)$.
\end{enumerate}

\noindent
Let's verify the properties of $\phi(t)$.
For $t \in [0,\delta]$, we have
$\phi'(t) = \phi''(t) = 0$. For $t \in [\delta,\delta_2]$, we have
$$ \phi'(t) = -2\alpha \left(t-1 \right), \ \ \ \ \ \
 \phi''(t) = -2\alpha, $$
and for $t \in [\delta_2, \infty)$,
$$ \phi'(t) = -{2\alpha}{(1+\alpha)^{-1-\alpha}} \left( t-1 \right)^{-2\alpha-1}, $$
$$ \phi''(t) = {2\alpha(1+2\alpha)}{(1+\alpha)^{-1-\alpha}} \left( t-1 \right)^{-2\alpha-2}. $$
First, we check that the values and first derivatives agree at the breakpoints.
For $t = \delta = 1$, we get $\phi(1) = 1$ and $\phi'(1) = 0$.
For $t = \delta_2 = 1 + (1+\alpha)^{-1/2}$, we get
$\phi(\delta_2) = (1+\alpha)^{-1}$ and
$\phi'(\delta_2) = -2 \alpha (1+\alpha)^{-1/2}$.
Next, we need to check is that $\phi(t)$ is very small
for $t \geq \beta$. The function is decreasing for $t > \beta$,
therefore it is enough to check $t = \beta = e^{1/(2\alpha^2)}+1$:
$$ \phi\left(\beta \right) = (1+\alpha)^{-1-\alpha} (\beta - 1)^{-2\alpha}
  \leq (\beta-1)^{-2\alpha} = e^{-1/\alpha}. $$
The derivative bounds are satisfied trivially for $t \in [0,\delta]$.
For $t \in [\delta, \delta_2]$, using $t \leq \delta_2 = 1 + (1+\alpha)^{-1/2}$,
$$ |t \phi'(t)| = t \cdot 2 \alpha (t-1)
 \leq 2 \alpha (1 + (1+\alpha)^{-1/2}) (1+\alpha)^{-1/2} \leq 4 \alpha $$
and using $\alpha \in (0,\frac18)$,
$$ |t^2 \phi''(t)| = t^2 \cdot 2 \alpha \leq 2 \alpha (1 + (1+\alpha)^{-1/2})^2
 \leq 8 \alpha.$$
For $t \in [\delta_2,\infty)$, using $t-1 \geq (1+\alpha)^{-1/2}$,
\begin{eqnarray*}
|t \phi'(t)| & = & t \cdot \frac{2 \alpha}{(1+\alpha)^{1+\alpha}} \left(t-1 \right)^{-2\alpha-1}
 = \frac{2 \alpha}{1+\alpha} \left( (1 + \alpha)
\left( t-1 \right)^2 \right)^{-\alpha} \frac{t}{t-1} \\
& \leq & \frac{2 \alpha}{1 + \alpha} \cdot \frac{t}{t-1}
 \leq \frac{2 \alpha}{1+\alpha} \cdot \frac{1 + (1+\alpha)^{-1/2}}{(1+\alpha)^{-1/2}}
 = 2 \alpha \cdot \frac{1 + (1+\alpha)^{-1/2}}{(1+\alpha)^{1/2}} \leq 4 \alpha
\end{eqnarray*}
and finally, using $\alpha \in (0,\frac18)$,
\begin{eqnarray*}
 |t^2 \phi''(t)| & = & t^2 \cdot \frac{2\alpha(1+2\alpha)}{(1+\alpha)^{1+\alpha}}
 \left( t-1 \right)^{-2\alpha-2}
 = \frac{2\alpha(1+2\alpha)}{1+\alpha}
 \left( (1 + \alpha) \left( t-1 \right)^2 \right)^{-\alpha}
 \left( \frac{t}{t-1} \right)^2 \\
& \leq & \frac{2\alpha(1+2\alpha)}{1+\alpha} \cdot
 \left( \frac{1 + (1+\alpha)^{-1/2}}{(1+\alpha)^{-1/2}} \right)^2
 \leq 8 \alpha (1 + 2 \alpha) \leq 10 \alpha.
\end{eqnarray*}
\end{proof}

Using Lemmas~\ref{lemma:H-bounds}, \ref{lemma:D-bounds} and \ref{lemma:phi-construction},
we now prove bounds on the derivatives of $\tilde{F}({\bf x})$.

\begin{lemma}
\label{lemma:F-bounds}
Let $ \tilde{F}({\bf x}) = (1-\phi(D({\bf x}))) F({\bf x}) + \phi(D({\bf x})) G({\bf x}) $
where $F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$, $f:2^X \rightarrow [0,M]$,
$G({\bf x}) = F(\bar{{\bf x}})$, $D({\bf x})=||{\bf x}-\bar{{\bf x}}||^2$
are as above and $\phi(t)$ is provided by Lemma~\ref{lemma:phi-construction}
for a given $\alpha>0$.
Then, whenever $\mixdiff{F}{x_i}{x_j} \leq 0$,
$$
 \mixdiff{\tilde{F}}{x_i}{x_j}
  \leq  512 M |X| \alpha. $$
If, in addition, $\partdiff{F}{x_i} \geq 0$, then
$$
\partdiff{\tilde{F}}{x_i}
  \geq  -64 M |X| \alpha. $$
\end{lemma}

\begin{proof}
We have
$ \tilde{F}({\bf x}) = F({\bf x}) - \phi(D({\bf x})) H({\bf x}) $
where $H({\bf x}) = F({\bf x}) - G({\bf x})$. By differentiating once, we get
$$ \partdiff{\tilde{F}}{x_i} = \partdiff{F}{x_i}
 - \phi(D({\bf x})) \partdiff{H}{x_i} - \phi'(D({\bf x})) \partdiff{D}{x_i} H({\bf x}), $$
i.e.
$$ \Big| \partdiff{\tilde{F}}{x_i} -
 \left(\partdiff{F}{x_i} - \phi(D({\bf x})) \partdiff{H}{x_i} \right) \Big|
 = \Big| \phi'(D({\bf x})) \partdiff{D}{x_i} H({\bf x}) \Big|.$$
By Lemma~\ref{lemma:H-bounds} and \ref{lemma:D-bounds},
we have $|\partdiff{D}{x_i}| = 2 |x_i - \bar{x}_i| \leq 2$
and $|H({\bf x})| \leq 8M|X| \cdot D({\bf x})$. Therefore,
$$ \Big| \partdiff{\tilde{F}}{x_i} -
 \left(\partdiff{F}{x_i} - \phi(D({\bf x})) \partdiff{H}{x_i} \right) \Big|
 \leq 16 M |X| D({\bf x}) \cdot \Big| \phi'(D({\bf x})) \Big|.$$
By Lemma~\ref{lemma:phi-construction}, $|D({\bf x}) \phi'(D({\bf x}))| \leq 4 \alpha$, and hence
$$ \Big| \partdiff{\tilde{F}}{x_i} -
 \left(\partdiff{F}{x_i} - \phi(D({\bf x})) \partdiff{H}{x_i} \right) \Big|
 \leq 64 M |X| \alpha.$$
Assuming that $\partdiff{F}{x_i} \geq 0$, we also have $\partdiff{G}{x_i} \geq 0$
(see Lemma~\ref{lemma:grad-symmetry}) and therefore,
$ \partdiff{F}{x_i} - \phi(D({\bf x})) \partdiff{H}{x_i}
 = (1-\phi(D({\bf x}))) \partdiff{F}{x_i} + \phi(D({\bf x})) \partdiff{G}{x_i} \geq 0$.
Consequently,
$$ \partdiff{\tilde{F}}{x_i} \geq - 64 M |X| \alpha.$$
By differentiating $\tilde{F}$ twice, we obtain
\begin{eqnarray*}
\mixdiff{\tilde{F}}{x_i}{x_j} & = &
 \mixdiff{F}{x_i}{x_j} - \phi({D}({\bf x})) \mixdiff{H}{x_i}{x_j}
 - \phi''({D}({\bf x})) \partdiff{{D}}{x_i} \partdiff{{D}}{x_j} H({\bf x}) \\
& &  - \phi'({D}({\bf x})) \left( \partdiff{{D}}{x_j} \partdiff{H}{x_i}
 + \mixdiff{{D}}{x_i}{x_j} H({\bf x})
 + \partdiff{{D}}{x_i} \partdiff{H}{x_j} \right).
\end{eqnarray*}
Again, we use Lemma~\ref{lemma:H-bounds} and \ref{lemma:D-bounds}
to bound $|H({\bf x})| \leq 8M|X| D({\bf x})$, $|\partdiff{H}{x_i}| \leq 8M|X| \sqrt{D({\bf x})}$,
 $|\mixdiff{H}{x_i}{x_j}| \leq 8M$, $|\partdiff{D}{x_i}| \leq 2 \sqrt{D({\bf x})}$
and $|\mixdiff{D}{x_i}{x_j}| \leq 2$. We get
\begin{eqnarray*}
\Big| \mixdiff{\tilde{F}}{x_i}{x_j} - \mixdiff{F}{x_i}{x_j} +
 \phi({D}({\bf x})) \mixdiff{H}{x_i}{x_j} \Big|
 \leq 32 M|X| \Big| D^2({\bf x}) \phi''({D}({\bf x})) \Big|
  + 48 M|X| \Big| D({\bf x}) \phi'({D}({\bf x})) \Big|
\end{eqnarray*}
Observe that $\phi'(D({\bf x}))$ appears with $D({\bf x})$ and
$\phi''(D({\bf x}))$ appears with $(D({\bf x}))^2$.
By Lemma~\ref{lemma:phi-construction}, $|D({\bf x}) \phi'(D({\bf x}))| \leq 4 \alpha$
and $|D^2({\bf x}) \phi''(D({\bf x}))| \leq 10 \alpha$. Therefore,
\begin{eqnarray*}
\Big| \mixdiff{\tilde{F}}{x_i}{x_j} - \left( \mixdiff{F}{x_i}{x_j}
 - \phi({D}({\bf x})) \mixdiff{H}{x_i}{x_j} \right) \Big|
 \leq  320 M|X|\alpha + 192 M|X| \alpha  = 512 M |X| \alpha.
\end{eqnarray*}
If $\mixdiff{F}{x_i}{x_j} \leq 0$ for all $i,j$, then also $\mixdiff{G}{x_i}{x_j} =
 {\bf E}_{\sigma,\tau \in {\cal G}}[\mixdiff{F}{x_{\sigma^{-1}(i)}}{x_{\tau^{-1}(j)}}] \leq 0$
 (see the proof of Lemma~\ref{lemma:H-bounds}). Also,
$\mixdiff{F}{x_i}{x_j} - \phi({D}({\bf x})) \mixdiff{H}{x_i}{x_j}
 = \phi(D({\bf x})) \mixdiff{F}{x_i}{x_j} + (1-\phi(D({\bf x}))) \mixdiff{G}{x_i}{x_j} \leq 0$.
We obtain
\begin{eqnarray*}
\mixdiff{\tilde{F}}{x_i}{x_j} \leq 512 M |X| \alpha.
\end{eqnarray*}
\end{proof}

Finally, we can finish the proof of Lemma~\ref{lemma:final-fix}.

\begin{proof}[Proof of Lemma~\ref{lemma:final-fix}]
Let $\epsilon>0$ and $f:2^X \rightarrow [0,M]$.
We choose $\beta = \frac{\epsilon}{16 M|X|}$, so that $|H({\bf x})| = |F({\bf x}) - G({\bf x})| \leq \epsilon/2$
whenever $D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2 \leq \beta$
(due to by Lemma~\ref{lemma:H-bounds}, which states that $|H({\bf x})| \leq 8 M |X| D({\bf x})$).
Also, let $\alpha = \frac{\epsilon}{2000 M |X|^3}$.
For these values of $\alpha,\beta>0$,
let $\delta > 0$ and $\phi:{\boldmath R}_+ \rightarrow [0,1]$
be provided by Lemma~\ref{lemma:phi-construction}.
We define
$$ \tilde{F}({\bf x}) = (1-\phi(D({\bf x}))) F({\bf x}) + \phi(D({\bf x})) G({\bf x}). $$
Lemma~\ref{lemma:F-bounds} provides bounds on the first and second
partial derivatives of $\tilde{F}({\bf x})$.
Finally, we modify $\tilde{F}({\bf x})$ so that it satisfies the required
conditions (submodularity and optionally monotonicity).
For that purpose, we add a suitable multiple of the following function:
$$ J({\bf x}) = |X|^2 + 3|X| \sum_{i \in X} x_i - \left(\sum_{i \in X} x_i \right)^2.$$
We have $0 \leq J({\bf x}) \leq 3|X|^2$,
$\partdiff{J}{x_i} = 3|X| - 2 \sum_{i \in X} x_i \geq |X|$.
Further, $\mixdiff{J}{x_i}{x_j} = -2$. Note also that $J(\bar{{\bf x}}) = J({\bf x})$,
since $J({\bf x})$ depends only on the sum of all coordinates $\sum_{i \in X} x_i$.
To make $\tilde{F}({\bf x})$ submodular and optionally monotone, we define:
$$ \hat{F}({\bf x}) = \tilde{F}({\bf x}) + 256 M |X| \alpha J({\bf x}),$$
$$ \hat{G}({\bf x}) = G({\bf x}) + 256 M |X| \alpha J({\bf x}). $$
We verify the properties of $\hat{F}({\bf x})$ and $\hat{G}({\bf x})$:
\begin{enumerate}
\item
For any ${\bf x} \in P({\cal F})$, we have
\begin{eqnarray*}
\hat{G}({\bf x}) & = & G({\bf x}) + 256 M |X| \alpha J({\bf x}) \\
 & = & F(\bar{{\bf x}}) + 256 M |X| \alpha J(\bar{{\bf x}}) \\
 & = & \hat{F}(\bar{{\bf x}}).
\end{eqnarray*}

\item When $D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2 \geq \beta$,
Lemma~\ref{lemma:phi-construction} guarantees
that $0 \leq \phi(D({\bf x})) < e^{-1/\alpha} \leq \alpha$ and
\begin{eqnarray*}
|\hat{F}({\bf x}) - F({\bf x})| & \leq & \phi(D({\bf x})) |G({\bf x}) - F({\bf x})| + 256 M |X| \alpha J({\bf x}) \\
 & \leq & \alpha M + 768 M |X|^3 \alpha \\
 & \leq & \epsilon
\end{eqnarray*}
using $0 \leq F({\bf x}), G({\bf x}) \leq M$, $|X| \leq J({\bf x}) \leq 3|X|^2$ and $\alpha = \frac{\epsilon}{2000 M |X|^3}$.

When $D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2 < \beta$, we chose the value of $\beta$ so that
$|G({\bf x}) - F({\bf x})| < \epsilon/2$ and so by the above,
\begin{eqnarray*}
|\hat{F}({\bf x}) - F({\bf x})| & \leq & \phi(D({\bf x})) |G({\bf x}) - F({\bf x})| + 256 M |X| \alpha J({\bf x}) \\
 & \leq & \epsilon/2 + 768 M |X|^3 \alpha \\
 & \leq & \epsilon.
\end{eqnarray*}

\item Due to Lemma~\ref{lemma:phi-construction}, $\phi(t) = 1$ for $t \in [0,\delta]$.
Hence, whenever $D({\bf x}) = ||{\bf x} - \bar{{\bf x}}||^2 \leq \delta$, we have
$ \tilde{F}({\bf x}) = G({\bf x}) = F(\bar{{\bf x}})$, which depends only on $\bar{{\bf x}}$.
Also, we have $\hat{F}({\bf x}) = \hat{G}({\bf x}) = F(\bar{{\bf x}}) + 256 M |X| \alpha J({\bf x})$
and again, $J({\bf x})$ depends only on $\bar{{\bf x}}$ (in fact, only on the average
of all coordinates of ${\bf x}$). Therefore, $\hat{F}({\bf x})$ and $\hat{G}({\bf x})$
in this case depend only on $\bar{{\bf x}}$.

\item The first partial derivatives of $\hat{F}$ are given by the formula
$$ \partdiff{\hat{F}}{x_i} = \partdiff{F}{x_i}
 - \phi(D({\bf x})) \partdiff{H}{x_i} - \phi'(D({\bf x})) \partdiff{D}{x_i} H({\bf x}) + 256 M|X|\alpha \partdiff{J}{x_i}. $$
The functions $F, H, D, J$ are infinitely differentiable, so the only possible issue is with $\phi$.
By inspecting our construction of $\phi$ (Lemma~\ref{lemma:phi-construction}), we can see that it is piecewise
infinitely differentiable, and $\phi'$ is continuous at the breakpoints. Therefore, it is also
absolutely continuous. This implies that $\partdiff{\hat{F}}{x_i}$ is absolutely continuous.

The function $\hat{G}({\bf x}) = F(\bar{{\bf x}}) + 256 M|X|\alpha J({\bf x})$ is infinitely differentiable,
so its first partial derivatives are also absolutely continuous.

\item Assuming $\partdiff{F}{x_i} \geq 0$, we get $\partdiff{\tilde{F}}{x_i}
 \geq - 64 M |X| \alpha$ by Lemma~\ref{lemma:F-bounds}. Using $\partdiff{J}{x_i}
 \geq |X|$, we get $\partdiff{\hat{F}}{x_i} = \partdiff{\tilde{F}}{x_i}
 + 256 M|X| \alpha J({\bf x}) \geq 0$. The same holds for $\partdiff{\hat{G}}{x_i}$
since $\partdiff{G}{x_i} \geq 0$.

\item Assuming $\mixdiff{F}{x_i}{x_j} \leq 0$, we get $\mixdiff{\tilde{F}}{x_i}{x_j}
 \leq 512 M |X| \alpha$ by  Lemma~\ref{lemma:F-bounds}. Using $\mixdiff{J}{x_i}{x_j}
 = -2$, we get $\mixdiff{\hat{F}}{x_i}{x_j} = \mixdiff{\tilde{F}}{x_i}{x_j}
 + 256 M |X| \alpha \mixdiff{J}{x_i}{x_j} \leq 0$. The same holds for
$\mixdiff{\hat{G}}{x_i}{x_j}$ since $\mixdiff{G}{x_i}{x_j} \leq 0$.
\end{enumerate}
\end{proof}

This concludes the proofs of our main hardness results.

\section{Algorithms using the multilinear relaxation}
\label{section:algorithms}

Here we turn to our algorithmic results. First, we discuss
the problem of maximizing a submodular (but not necessarily
monotone) function subject to a matroid independence constraint.

\subsection{Matroid independence constraint}
\label{section:submod-independent}

Consider the problem $\max \{ f(S): S \in {\cal I} \}$, where ${\cal I}$ is the collection
of independent sets in a matroid ${\cal M}$.
We design an algorithm based on the multilinear relaxation of the problem,
$\max \{ F({\bf x}): {\bf x} \in P({\cal M}) \}$.
Our algorithm can be seen as "continuous local search" in the matroid polytope $P({\cal M})$,
constrained in addition by the box $[0,t]^X$
for some fixed $t \in [0,1]$. The intuition is that this forces
our local search to use fractional solutions that are more fuzzy
than integral solutions and therefore less likely to get stuck in a local
optimum. On the other hand, restraining the search space too much would not
give us much freedom in searching for a good fractional point.
This leads to a tradeoff and an optimal choice of $t \in [0,1]$
which we leave for later.

The matroid polytope is defined as
$ P({\cal M}) = \mbox{conv} \{ {\bf 1}_I: I \in {\cal I} \} $.
or equivalently \cite{E70} as
$ P({\cal M}) = \{ {\bf x} \geq 0: \forall S; \sum_{i \in S} x_i \leq r_{\cal M}(S) \}$,
where $r_{\cal M}(S)$ is the rank function of ${\cal M}$.
We define
$$ P_t({\cal M}) = P({\cal M}) \cap [0,t]^X = \{ {\bf x} \in P({\cal M}): \forall i; x_i \leq t \}.$$
We consider the problem $\max \{F({\bf x}): {\bf x} \in P_t({\cal M})\}$.
We remind the reader that
$F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$ denotes the multilinear extension.
Our algorithm works as follows.

\

\noindent{\bf Fractional local search in $P_t({\cal M})$} \\
 (given $t = \frac{r}{q}$, $r \leq q$ integer)
\begin{enumerate}
\item Start with ${\bf x} := (0,0,\ldots,0)$. Fix $\delta = 1/q$.
\item If there is  $i,j \in X$ and a direction ${\bf v} \in
 \{{\bf e}_j, -{\bf e}_i, {\bf e}_j - {\bf e}_i \}$ such that
${\bf x} + \delta {\bf v} \in P_t({\cal M})$ and $F({\bf x} + \delta {\bf v}) > F({\bf x})$,
set ${\bf x} := {\bf x} + \delta {\bf v}$ and repeat.
\item If there is no such direction ${\bf v}$, apply pipage rounding to ${\bf x}$
and return the resulting solution.
\end{enumerate}

\noindent{\em Notes.}
The procedure as presented here would not run in polynomial
time. A modification which runs in polynomial time is that
we move to a new solution only if $F({\bf x}+\delta {\bf v}) >
 F({\bf x}) + \frac{\delta}{poly(n)} OPT$ (where we first get
a rough estimate of $OPT$ using previous methods).
For simplicity, we analyze the variant above
and finally discuss why we can modify it without
losing too much in the approximation factor. We also defer
the question of how to estimate the value of $F({\bf x})$
to the end of this section.

For $t=1$, we have $\delta=1$ and the procedure
reduces to discrete local search. However, it is known that discrete
local search alone does not give any approximation guarantee. With
additional modifications, an algorithm based on discrete local search
achieves a $(\frac14-o(1))$-approximation \cite{LMNS09}.

Our version of fractional local search avoids this issue and leads
directly to a good fractional solution.  Throughout the algorithm,
we maintain ${\bf x}$ as a linear combination of $q$ independent sets
such that no element appears in more than $r$ of them. A local step
corresponds to an add/remove/switch operation preserving this condition.

Finally, we use pipage rounding to convert a fractional solution into
an integral one. As we show in Lemma~\ref{lemma:pipage} (in the Appendix),
a modification of the technique from \cite{CCPV07}
can be used to find an integral solution without any loss in the objective
function.

\begin{theorem}
\label{thm:submod-matroid-approx}
The fractional local search algorithm for any fixed $t \in [0,\frac12 (3-\sqrt{5})]$
returns a solution of value at least $(t - \frac12 t^2) OPT$,
where $OPT = \max \{f(S): S \in {\cal I}\}$.
\end{theorem}

We remark that for $t=\frac12(3-\sqrt{5})$, we would obtain a $\frac14(-1+\sqrt{5})
 \simeq 0.309$-approximation, improving the factor of $\frac14$ \cite{LMNS09}.
This is not a rational value, but we can pick a rational $t$
arbitrarily close to $\frac12 (3-\sqrt{5})$.
For values $t > \frac12 (3-\sqrt{5})$, our analysis does not yield
a better approximation factor.

First, we discuss properties of the point found by the fractional local search algorithm.

\begin{lemma}
\label{lemma:local-opt}
The outcome of the fractional local search algorithm $x$ is
a ``fractional local optimum'' in the following sense.
(All the partial derivatives are evaluated at $x$.)
\begin{itemize}
\item For any $i$ such that ${\bf x} - \delta {\bf e}_i \in P_t({\cal M})$,
$\partdiff{F}{x_i} \geq 0.$
\item For any $j$ such that ${\bf x} + \delta {\bf e}_j \in P_t({\cal M})$,
$\partdiff{F}{x_j} \leq 0.$
\item For any $i,j$ such that ${\bf x} + \delta ({\bf e}_j - {\bf e}_i) \in P_t({\cal M})$,
$\partdiff{F}{x_j} - \partdiff{F}{x_i} \leq 0.$
\end{itemize}
\end{lemma}

\begin{proof}
We use the property (see \cite{CCPV07}) that along any direction ${\bf v} = \pm {\bf e}_i$
or ${\bf v} = {\bf e}_i - {\bf e}_j$, the function $F({\bf x} + \lambda {\bf v})$ is a convex
function of $\lambda$. Also, observe that if it is possible to move from ${\bf x}$
in the direction of ${\bf v}$ by any nonzero amount, then it is possible to move
by $\delta {\bf v}$, because all coordinates of ${\bf x}$ are integer multiples of $\delta$
and all the constraints also have coefficients which are integer multiples of $\delta$.
Therefore, if $\frac{dF}{d\lambda} > 0$ and it is possible
to move in the direction of ${\bf v}$, we would get
$F({\bf x} + \delta {\bf v}) > F({\bf x})$ and the fractional local search would continue.

If ${\bf v} = -{\bf e}_i$ and it is possible to move along $-{\bf e}_i$,
we get $\frac{dF}{d\lambda} = -\partdiff{F}{x_i} \leq 0$. Similarly,
if ${\bf v} = {\bf e}_j$ and it is possible to move along ${\bf e}_j$,
we get $\frac{dF}{d\lambda} = \partdiff{F}{x_j} \leq 0$. Finally,
if ${\bf v} = {\bf e}_j - {\bf e}_i$ and it is possible to move along ${\bf e}_j - {\bf e}_i$,
we get $\frac{dF}{d\lambda} = \partdiff{F}{x_j} - \partdiff{F}{x_i} \leq 0$.
\end{proof}

We refer to the following exchange property for matroids
(which follows easily from \cite{Schrijver}, Corollary 39.12a; see also \cite{LMNS09}).

\begin{lemma}
\label{lemma:exchange}
If $I, C \in {\cal I}$, then for any $j \in C \setminus I$,
there is $\pi(j) \subseteq I \setminus C$, $|\pi(j)| \leq 1$,
such that $I \setminus \pi(j) + j \in {\cal I}$.
Moreover, the sets $\pi(j)$ are disjoint
(each $i \in I \setminus C$ appears at most once as $\pi(j) = \{i\}$).
\end{lemma}

Using this, we prove a lemma about fractional local optima
which generalizes Lemma 2.2 in \cite{LMNS09}.

\begin{lemma}
\label{lemma:fractional-search}
Let ${\bf x}$ be the outcome of fractional local search over $P_t({\cal M})$.
Let $C \in {\cal I}$ be any independent set.
Let $C' = \{i \in C: x_i < t\}$. Then
$$ 2 F({\bf x}) \geq F({\bf x} \vee {\bf 1}_{C'}) + F({\bf x} \wedge {\bf 1}_C).$$
\end{lemma}

Note that for $t = 1$, the lemma reduces to
$2 F({\bf x}) \geq F({\bf x} \vee {\bf 1}_C) + F({\bf x} \wedge {\bf 1}_C)$
(similar to Lemma 2.2 in \cite{LMNS09}).
For $t < 1$, however, it is necessary to replace $C$ by $C'$
in the first expression, which becomes apparent in the proof.
The reason is that we do not have any information on $\partdiff{F}{x_i}$
for coordinates where $x_i = t$.

\begin{proof}
Let $C \in {\cal I}$ and assume ${\bf x} \in P_t({\cal M})$ is a local optimum.
Since ${\bf x} \in P({\cal M})$, we can decompose it into a convex linear
combination of vertices of $P({\cal M})$, ${\bf x} = \sum_{I \in {\cal I}} x_I {\bf 1}_I$
where $\sum x_I = 1$..
By the smooth submodularity of $F({\bf x})$ (see \cite{Vondrak08}),
\begin{eqnarray*}
F({\bf x} \vee {\bf 1}_{C'}) - F({\bf x}) \leq \sum_{j \in C'} (1 - x_j) \partdiff{F}{x_j}
  =  \sum_{j \in C'} \sum_{I: j \notin I} x_I \partdiff{F}{x_j}
  = \sum_I x_I \sum_{j \in C' \setminus I} \partdiff{F}{x_j}.
\end{eqnarray*}
All partial derivatives here are evaluated at ${\bf x}$.
On the other hand, also by submodularity,
\begin{eqnarray*}
 F({\bf x}) - F({\bf x} \wedge {\bf 1}_C) \geq \sum_{i \notin C} x_i \partdiff{F}{x_i}
 = \sum_{i \notin C} \sum_{I: i \in I} x_I \partdiff{F}{x_i}
 = \sum_I x_I \sum_{i \in I \setminus C} \partdiff{F}{x_i}.
\end{eqnarray*}
To prove the lemma, it remains to prove the following.

\

\noindent {\bf Claim.} Whenever $x_I > 0$,
$\sum_{j \in C' \setminus I} \partdiff{F}{x_j}
 \leq \sum_{i \in I \setminus C} \partdiff{F}{x_i}$.

\

\noindent {\em Proof:}
For any $I \in {\cal I}$, we can apply
Lemma~\ref{lemma:exchange} to get a mapping $\pi$ such that
$I \setminus \pi(j) + j \in {\cal I}$ for any $j \in C \setminus I$.
Now, consider $j \in C' \setminus I$, i.e. $j \in C \setminus I$ and $x_j < t$.

If $\pi(j) = \emptyset$, is possible to move from ${\bf x}$ in the direction
of ${\bf e}_j$, because $I + j \in {\cal I}$ and hence we can replace $I$ by $I+j$
(or at least we can do this for some nonzero fraction of its coefficient)
in the linear combination.
Because $x_j < t$, we can move by a nonzero amount inside $P_t({\cal M})$.
By Lemma~\ref{lemma:local-opt}, $\partdiff{F}{x_j} \leq 0$.

Similarly, if $\pi(j) = \{i\}$, it is possible to move in the direction
of ${\bf e}_j - {\bf e}_i$, because $I$ can be replaced by $I \setminus \pi(j) + i$
for some nonzero fraction of its coefficient. By Lemma~\ref{lemma:local-opt},
in this case $\partdiff{F}{x_j} - \partdiff{F}{x_i} \leq 0$.

Finally, for any $i \in I$ we have $x_i > 0$ and therefore we can decrease
$x_i$ while staying inside $P_t({\cal M})$. By Lemma~\ref{lemma:local-opt},
we have $\partdiff{F}{x_i} \geq 0$ for all $i \in I$.
This means
$$ \sum_{j \in C' \setminus I} \partdiff{F}{x_j}
 \leq  \sum_{j \in C' \setminus I: \pi(j) = \emptyset} \partdiff{F}{x_j} +
  \sum_{j \in C' \setminus I: \pi(j) = \{i\}} \partdiff{F}{x_i}
 \leq \sum_{i \in I \setminus C} \partdiff{F}{x_i} $$
using the inequalities we derived above, and the fact that
each $i \in I \setminus C$ appears at most once in $\pi(j)$.
This proves the Claim, and hence the Lemma.
\end{proof}

Now we are ready to prove Theorem~\ref{thm:submod-matroid-approx}.

\begin{proof}
Let ${\bf x}$ be the outcome of the fractional local search over $P_t({\cal M})$.
Define $A = \{ i: x_i = t \}$.
Let $C$ be the optimum solution and $C' = C \setminus A = \{ i \in C: x_i < t\}$.
By Lemma~\ref{lemma:fractional-search},
$$ 2 F({\bf x}) \geq F({\bf x} \vee {\bf 1}_{C'}) + F({\bf x} \wedge {\bf 1}_C).$$
First, let's analyze $F({\bf x} \wedge {\bf 1}_C)$. We apply Lemma~\ref{lemma:rnd-threshold} (in the Appendix),
which states that $F({\bf x} \wedge {\bf 1}_C) \geq {\bf E}[f(T({\bf x} \wedge {\bf 1}_C))]$. Here,
$T({\bf x} \wedge {\bf 1}_C)$ is a random threshold set corresponding to the
vector ${\bf x} \wedge {\bf 1}_C$, i.e.
$$ T({\bf x} \wedge {\bf 1}_C) = \{ i: ({\bf x} \wedge {\bf 1}_C)_i > \lambda \}
 = \{ i \in C: x_i > \lambda \} = T({\bf x}) \cap C $$
where $\lambda \in [0,1]$ is uniformly random.
Equivalently,
$$ F({\bf x} \wedge {\bf 1}_C) \geq {\bf E}[f(T({\bf x}) \cap C)].$$
Due to the definition of a threshold set, with probability $t$ we have
$\lambda < t$ and $T({\bf x})$ contains $A = \{ i: x_i = t \} = C \setminus C'$.
Then, $f(T({\bf x}) \cap C) + f(C') \geq f(C)$ by submodularity.
We conclude that
\begin{equation}
\label{eq:1}
F({\bf x} \wedge {\bf 1}_C) \geq t (f(C) - f(C')).
\end{equation}
Next, let's analyze $F({\bf x} \vee {\bf 1}_{C'})$. We consider the ground set
partitioned into $X = C \cup \bar{C}$, and we apply Lemma~\ref{lemma:submod-split} (in the Appendix).
(Here, $\bar{C}$ denotes $X \setminus C$, the complement of $C$ inside $X$.)
We get
$$ F({\bf x} \vee {\bf 1}_{C'}) \geq {\bf E}[f((T_1({\bf x} \vee {\bf 1}_{C'}) \cap C)
 \cup (T_2({\bf x} \vee {\bf 1}_{C'}) \cap \bar{C}))].$$
The random threshold sets look as follows: $T_1({\bf x} \vee {\bf 1}_{C'}) \cap C
 = (T_1({\bf x}) \cup C') \cap C$ is equal to $C$ with probability $t$,
and equal to $C'$ otherwise. $T_2({\bf x} \vee {\bf 1}_{C'}) \cap \bar{C}
 = T_2({\bf x}) \cap \bar{C}$ is empty with probability $1-t$.
(We ignore the contribution when $T_2({\bf x}) \cap \bar{C} \neq \emptyset$.)
Because $T_1$ and $T_2$ are independently sampled, we get
$$ F({\bf x} \vee {\bf 1}_{C'}) \geq t(1-t) f(C) + (1-t)^2 f(C').$$
Provided that $t \in [0,\frac12 (3 - \sqrt{5})]$, we have $t \leq (1-t)^2$.
Then, we can write
\begin{equation}
\label{eq:1'}
F({\bf x} \vee {\bf 1}_{C'}) \geq t(1-t) f(C) + t f(C').
\end{equation}
Combining equations (\ref{eq:1}) and (\ref{eq:1'}), we get
\begin{eqnarray*}
& & F({\bf x} \vee {\bf 1}_{C'})  +  F({\bf x} \wedge {\bf 1}_C)
 \geq t (f(C) - f(C')) + t(1-t) f(C) + t \, f(C')
 = (2t - t^2) f(C).
\end{eqnarray*}
Therefore,
$$ F({\bf x}) \geq \frac12 (F({\bf x} \vee {\bf 1}_{C'}) + F({\bf x} \wedge {\bf 1}_C))
 \geq (t - \frac12 t^2) f(C).$$
Finally, we apply the pipage rounding technique which does not
lose anything in terms of objective value (see Lemma~\ref{lemma:pipage}).
\end{proof}

\paragraph{Technical remarks}
In each step of the algorithm, we need to estimate values of $F({\bf x})$
for given ${\bf x} \in P_t({\cal M})$. We accomplish this by using the expression
$F({\bf x}) = {\bf E}[f(R({\bf x}))]$ where $R({\bf x})$ is a random set associated with ${\bf x}$.
By standard bounds, if the values of $f(S)$ are in a range $[0,M]$,
we can achieve accuracy $M / poly(n)$ using a polynomial number of samples.
We use the fact that $OPT \geq \frac{1}{n} M$ (see
Lemma~\ref{lemma:solution-value} in the Appendix) and therefore
we can achieve $OPT / poly(n)$ additive error in polynomial time.

We also relax the local step condition: we move to the next solution
only if $F({\bf x} + \delta {\bf v}) > F({\bf x}) + \frac{\delta}{poly(n)} OPT$
for a suitable polynomial in $n$. This way, we can only make a polynomial number of steps.
When we terminate, the local optimality conditions (Lemma~\ref{lemma:local-opt})
are satisfied within an additive error of $OPT / poly(n)$,
which yields a polynomially small error in the approximation bound.

\subsection{Matroid base constraint}
\label{section:submod-bases}

Let us move on to the problem $\max \{f(S): S \in {\cal B}\}$ where
${\cal B}$ are the bases of a matroid.
For a fixed $t \in [0,1]$, let us consider an algorithm which can be seen
as local search inside the base polytope $B({\cal M})$, further constrained
by the box $[0,t]^X$. The matroid base polytope is defined as
$ B({\cal M}) = \mbox{conv} \{ {\bf 1}_B: B \in {\cal B} \} $
or equivalently \cite{E70} as
$ B({\cal M}) = \{ {\bf x} \geq 0: \forall S \subseteq X; \sum_{i \in S} x_i \leq r_{\cal M}(S),
 \sum_{i \in X} x_i = r_{\cal M}(X) \}, $
where $r_{\cal M}$ is the matroid rank function of ${\cal M}$. Finally, we define
$$ B_t({\cal M}) = B({\cal M}) \cap [0,t]^X = \{ {\bf x} \in B({\cal M}): \forall i \in X; x_i \leq t \}.$$
Observe that $B_t({\cal M})$ is nonempty if and only if there is a convex linear
combination ${\bf x} = \sum_{B \in {\cal B}} \xi_B {\bf 1}_B$ such that $x_i \in [0,t]$ for all $i$.
This is equivalent to saying that there is a linear combination (a fractional base packing)
${\bf x}' = \sum_{B \in {\cal B}} \xi'_B {\bf 1}_B$ such that $x_i \in [0,1]$
and $\sum \xi'_B \geq \frac{1}{t}$, in other words the fractional base packing
number is $\nu \geq \frac{1}{t}$.  Since the optimal fractional packing of bases
in a matroid can be found efficiently (see Corollary 42.7a in \cite{Schrijver}, Volume B),
we can find efficiently the minimum $t \in [\frac12,1]$ such that $B_t({\cal M}) \neq \emptyset$.
Then, our algorithm is the following.

\

\noindent{\bf Fractional local search in $B_t({\cal M})$} \\
 (given $t = \frac{r}{q}$, $r \leq q$ integer)
\begin{enumerate}
\item Let $\delta = \frac{1}{q}$.
Assume that ${\bf x} \in B_t({\cal M})$; adjust ${\bf x}$ (using pipage rounding)
so that each $x_i$ is an integer multiple of $\delta$.
In the following, this property will be maintained.
\item If there is a direction ${\bf v} = {\bf e}_j - {\bf e}_i$ such that
${\bf x} + \delta {\bf v} \in B_t({\cal M})$ and $F({\bf x} + \delta {\bf v}) > F({\bf x})$,
then set ${\bf x} := {\bf x} + \delta {\bf v}$ and repeat.
\item If there is no such direction ${\bf v}$, apply pipage rounding to ${\bf x}$
and return the resulting solution.
\end{enumerate}

\noindent{\em Notes.}
We remark that the starting point can be found as a convex linear combination
of $q$ bases, $x = \frac{1}{q} \sum_{i=1}^{q} {\bf 1}_{B_i}$, such that
no element appears in more than $r$ of them, using matroid union techniques (see Theorem 42.9 in \cite{Schrijver}).
In the algorithm, we maintain this representation.
The local search step corresponds to switching a pair of elements in one base,
under the condition that no element is used in more than $r$ bases at the same time.
For now, we ignore the issues of estimating $F({\bf x})$ and stopping the local search
within polynomial time. We discuss this at the end of this section.

Finally, we use pipage rounding to convert the fractional solution ${\bf x}$
into an integral one of value at least $F({\bf x})$ (Lemma~\ref{lemma:base-pipage} in the Appendix).
Note that it is not necessarily true that any of the bases in
a convex linear combination ${\bf x} = \sum \xi_B {\bf 1}_{B}$ achieves the value $F({\bf x})$.

\begin{theorem}
\label{thm:submod-bases-approx}
If there is a fractional packing of $\nu \in [1,2]$ bases in ${\cal M}$,
then the fractional local search algorithm with $t = \frac{1}{\nu}$
returns a solution of value at least $\frac12 (1-t) \ OPT.$
\end{theorem}

For example, assume that ${\cal M}$ contains two disjoint bases $B_1, B_2$
(which is the case considered in \cite{LMNS09}). Then,
the algorithm can be used with $t = \frac{1}{2}$ and
and we obtain a $(\frac{1}{4}-o(1))$-approximation, improving the
$(\frac{1}{6}-o(1))$-approximation from \cite{LMNS09}.
If there is a fractional packing of more than 2 bases,
our analysis still gives only a $(\frac{1}{4}-o(1))$-approximation.
If the dual matroid ${\cal M}^*$ admits a better fractional packing of bases,
we can consider the problem $\max \{f(\bar{S}): S \in {\cal B}^* \}$ which
is equivalent. For a uniform matroid, ${\cal B} = \{B: |B|=k\}$,
the fractional base packing number is either at least $2$ or the same
holds for the dual matroid, ${\cal B}^* = \{B: |B|=n-k\}$ (as noted in \cite{LMNS09}).
Therefore, we get a $(\frac{1}{4}-o(1))$-approximation for any uniform matroid.
The value $t=1$ can be used for any matroid,
but it does not yield any approximation guarantee.

\paragraph{Analysis of the algorithm}
We turn to the properties of fractional local optima.
We will prove that the point ${\bf x}$ found by the fractional local search algorithm
satisfies the following conditions that allow us to compare $F({\bf x})$ to the actual
optimum.

\begin{lemma}
\label{lemma:local-opt2}
The outcome of the fractional local search algorithm ${\bf x}$
is a ``fractional local optimum'' in the following sense.
\begin{itemize}
\item For any $i,j$ such that ${\bf x} + \delta ({\bf e}_j - {\bf e}_i) \in B_t({\cal M})$,
$$\partdiff{F}{x_j} - \partdiff{F}{x_i} \leq 0.$$
(The partial derivatives are evaluated at ${\bf x}$.)
\end{itemize}
\end{lemma}

\begin{proof}
Similarly to Lemma~\ref{lemma:local-opt},
observe that the coordinates of ${\bf x}$ are always integer multiples of $\delta$,
therefore if it is possible to move from ${\bf x}$ in the direction of
${\bf v} = {\bf e}_j - {\bf e}_i$ by any nonzero amount, then it is possible to
move by $\delta {\bf v}$.
We use the property that for any direction ${\bf v} = {\bf e}_j - {\bf e}_i$,
the function $F({\bf x} + \lambda {\bf v})$ is a convex function of $\lambda$ \cite{CCPV07}.
Therefore, if $\frac{dF}{d\lambda} > 0$ and it is possible
to move in the direction of ${\bf v}$, we would get
$F({\bf x} + \delta {\bf v}) > F({\bf x})$ and the fractional local search would continue.
For ${\bf v} = {\bf e}_j - {\bf e}_i$, we get
$$ \frac{dF}{d\lambda} = \partdiff{F}{x_j} - \partdiff{F}{x_i} \leq 0.$$
\end{proof}

We refer to the following exchange property for matroid bases
(see \cite{Schrijver}, Corollary 39.21a).

\begin{lemma}
\label{lemma:exchange2}
For any $B_1, B_2 \in {\cal B}$, there is a bijection $\pi:B_1 \setminus B_2
 \rightarrow B_2 \setminus B_1$ such that
$\forall i \in B_1 \setminus B_2$; $B_1-i+\pi(i) \in {\cal M}$.
\end{lemma}

Using this, we prove a lemma about fractional local optima
analogous to Lemma 2.2 in \cite{LMNS09}.

\begin{lemma}
\label{lemma:fractional-search2}
Let ${\bf x}$ be the outcome of fractional local search over $B_t({\cal M})$.
Let $C \in {\cal B}$ be any base. Then there is ${\bf c} \in [0,1]^X$ satisfying
\begin{itemize}
\item $c_i = t$, if $i \in C$ and $x_i = t$
\item $c_i = 1$, if $i \in C$ and $x_i < t$
\item $0 \leq c_i \leq x_i$, if $i \notin C$
\end{itemize}
such that
$$ 2 F({\bf x}) \geq F({\bf x} \vee {\bf c}) + F({\bf x} \wedge {\bf c}).$$
\end{lemma}

Note that for $t = 1$, we can set ${\bf c} = {\bf 1}_C$.
However, in general we need this more complicated formulation.
Intuitively, ${\bf c}$ is obtained from ${\bf x}$ by raising the variables $x_i, i \in C$
and decreasing $x_i$ for $i \notin C$.
However, we can only raise the variables $x_i, i \in C$, where $x_i$ is below
the threshold $t$, otherwise we do not have any information about $\partdiff{F}{x_i}$.
Also, we do not necessarily decrease all the variables outside of $C$ to zero.

\begin{proof}
Let $C \in {\cal B}$ and assume ${\bf x} \in B_t({\cal M})$ is a fractional local optimum.
We can decompose ${\bf x}$ into a convex linear combination of vertices
of $B({\cal M})$, ${\bf x} = \sum \xi_B {\bf 1}_B$.
By Lemma~\ref{lemma:exchange2}, for each base $B$ there is a bijection
$\pi_B:B \setminus C \rightarrow C \setminus B$ such that
$\forall i \in B \setminus C$; $B - i + \pi_B(i) \in {\cal B}$.

We define $C' = \{i \in C: x_i < t \}$.
The reason we consider $C'$ is that
if $x_i = t$, there is no room for an exchange step increasing $x_i$,
and therefore Lemma~\ref{lemma:local-opt2} does not give any information
about $\partdiff{F}{x_i}$.
We construct the vector ${\bf c}$ by starting from ${\bf x}$, and for each $B$
swapping the elements in $B \setminus C$ for their image under $\pi_B$,
provided it is in $C'$, until we raise the coordinates on $C'$ to $c_i=1$.
Formally, we set $c_i = 1$ for $i \in C'$, $c_i = t$ for $i \in C \setminus C'$,
and for each $i \notin C$, we define
$$ c_i = x_i - \sum_{B: i \in B, \pi_B(i) \in C'} \xi_B.$$

In the following, all partial derivatives are evaluated at ${\bf x}$.
By the smooth submodularity of $F({\bf x})$ (see \cite{CCPV09}),
\begin{eqnarray}
\label{eq:2}
F({\bf x} \vee {\bf c}) - F({\bf x}) & \leq & \sum_{j: c_j > x_j} (c_j - x_j) \partdiff{F}{x_j}
 = \sum_{j \in C'} (1 - x_j) \partdiff{F}{x_j}
  = \sum_B \sum_{j \in C' \setminus B} \xi_B \partdiff{F}{x_j}
\end{eqnarray}
because $\sum_{B: j \notin B} \xi_B = 1 - x_j$ for any $j$.
On the other hand, also by smooth submodularity,
\begin{eqnarray*}
F({\bf x}) - F({\bf x} \wedge {\bf c}) & \geq & \sum_{i: c_i < x_i} (x_i - c_i) \partdiff{F}{x_i}
 = \sum_{i \notin C} (x_i - c_i) \partdiff{F}{x_i}
 = \sum_{i \notin C} \sum_{B: i \in B, \pi_B(i) \in C'} \xi_B \partdiff{F}{x_i}
\end{eqnarray*}
using our definition of $c_i$. In the last sum,
for any nonzero contribution, we have $\xi_B > 0$, $i \in B$ and $j = \pi_B(i) \in C'$,
i.e. $x_j < t$. Therefore it is possible to move in the direction ${\bf e}_j - {\bf e}_i$
(we can switch from $B$ to $B-i+j$).
By Lemma~\ref{lemma:local-opt2},
$$ \partdiff{F}{x_j} - \partdiff{F}{x_i} \leq 0.$$
Therefore, we get
\begin{eqnarray}
F({\bf x}) - F({\bf x} \wedge {\bf c}) & \geq &
\sum_{i \notin C} \sum_{B: i \in B, j=\pi_B(i) \in C'} \xi_B \partdiff{F}{x_j}
\label{eq:3}
 = \sum_B \sum_{i \in B \setminus C: j=\pi_B(i) \in C'} \xi_B \partdiff{F}{x_j}.
\end{eqnarray}
By the bijective property of $\pi_B$, this is equal to
$\sum_B \sum_{j \in C' \setminus B} \xi_B \partdiff{F}{x_j}$.
Putting (\ref{eq:2}) and (\ref{eq:3}) together, we get
$F({\bf x} \vee {\bf c}) - F({\bf x}) \leq F({\bf x}) - F({\bf x} \wedge {\bf c})$.
\end{proof}

Now we are ready to prove Theorem~\ref{thm:submod-bases-approx}.

\begin{proof}
Assuming that $B_t({\cal M}) \neq \emptyset$, we can find a starting point ${\bf x}_0 \in B_t({\cal M})$.
From this point, we reach a fractional local optimum ${\bf x} \in B_t({\cal M})$
(see Lemma~\ref{lemma:local-opt2}).
We want to compare $F({\bf x})$ to the actual optimum; assume that $OPT = f(C)$.

As before, we define $C' = \{i \in C: x_i < t\}$.
By Lemma~\ref{lemma:fractional-search2}, we know that
the fractional local optimum satisfies:
\begin{equation}
\label{eq:4}
2 F({\bf x}) \geq F({\bf x} \vee {\bf c}) + F({\bf x} \wedge {\bf c})
\end{equation}
for some vector ${\bf c}$ such that $c_i = t$ for all $i \in C \setminus C'$,
$c_i = 1$ for $i \in C'$ and $0 \leq c_i \leq x_i$ for $i \notin C$.

First, let's analyze $F({\bf x} \vee {\bf c})$. We have
\begin{itemize}
\item $({\bf x} \vee {\bf c})_i = 1$ for all $i \in C'$.
\item $({\bf x} \vee {\bf c})_i = t$ for all $i \in C \setminus C'$.
\item $({\bf x} \vee {\bf c})_i \leq t$ for all $i \notin C$.
\end{itemize}
We apply Lemma~\ref{lemma:submod-split} to the partition $X = C \cup \bar{C}$.
We get
$$ F({\bf x} \vee {\bf c}) \geq {\bf E}[f((T_1({\bf x} \vee {\bf c}) \cap C) \cup (T_2({\bf x} \vee {\bf c}) \cap \bar{C}))] $$
where $T_1({\bf x})$ and $T_2({\bf x})$ are independent threshold sets.
Based on the information above, $T_1({\bf x} \vee {\bf c}) \cap C = C$ with probability $t$
and $T_1({\bf x} \vee {\bf c}) \cap C = C'$ otherwise. On the other hand,
$T_2({\bf x} \vee {\bf c}) \cap \bar{C} = \emptyset$ with probability at least $1-t$.
These two events are independent. We conclude that on the right-hand side,
we get $f(C)$ with probability at least $t(1-t)$, or $f(C')$ with probability
at least $(1-t)^2$:
\begin{equation}
\label{eq:5}
F({\bf x} \vee {\bf c}) \geq t(1-t) f(C) + (1-t)^2 f(C').
\end{equation}
Turning to $F({\bf x} \wedge {\bf c})$, we see that
\begin{itemize}
\item $({\bf x} \wedge {\bf c})_i = x_i$ for all $i \in C'$.
\item $({\bf x} \wedge {\bf c})_i = t$ for all $i \in C \setminus C'$.
\item $({\bf x} \wedge {\bf c})_i \leq t$ for all $i \notin C$.
\end{itemize}
We apply Lemma~\ref{lemma:submod-split} to $X = C \cup \bar{C}$.
$$ F({\bf x} \wedge {\bf c}) \geq {\bf E}[f((T_1({\bf x} \wedge {\bf c}) \cap C) \cup (T_2({\bf x} \wedge {\bf c}) \cap \bar{C}))].$$
With probability $t$,  $T_1({\bf x} \wedge {\bf c}) \cap C$ contains $C \setminus C'$
(and maybe some elements of $C'$). In this case, $f(T_1({\bf x} \wedge {\bf c}) \cap C)
 \geq f(C) - f(C')$ by submodularity.
Also, $T_2({\bf x} \wedge {\bf c}) \cap \bar{C}$ is empty with probability at least $1-t$.
Again, these two events are independent.
Therefore,
$ F({\bf x} \wedge {\bf c}) \geq t(1-t) (f(C) - f(C')).$
If $f(C') > f(C)$, this bound is vacuous; otherwise, we can replace $t(1-t)$ by
$(1-t)^2$, because $t \geq 1/2$. In any case,
\begin{equation}
\label{eq:6}
F({\bf x} \wedge {\bf c}) \geq (1-t)^2 (f(C) - f(C')).
\end{equation}
Combining (\ref{eq:4}), (\ref{eq:5}) and (\ref{eq:6}),
$$ F({\bf x}) \geq \frac12 (F({\bf x} \vee {\bf c}) + F({\bf x} \wedge {\bf c}))
 \geq \frac12 (t(1-t) f(C) + (1-t)^2 f(C)) = \frac12 (1-t) f(C).$$
\end{proof}

\paragraph{Technical remarks}
Again, we have to deal with the issues of estimating $F({\bf x})$ and
stopping the local search in polynomial time. We do this exactly
as we did at the end of Section~\ref{section:submod-independent}.
One issue to be careful about here is that if $f:2^X \rightarrow [0,M]$,
our estimates of $F({\bf x})$ are within an additive error of $M / poly(n)$.
If the optimum value $OPT = \max \{f(S): S \in {\cal B}\}$ is very small
compared to $M$, the error might be large compared to $OPT$ which would be
a problem. The optimum could in fact be very small in general.
But it holds that if ${\cal M}$ contains no loops and co-loops
(which can be eliminated easily), then $OPT \geq \frac{1}{n^2} M$
(see Appendix~\ref{app:base-value}). Then, our sampling errors are
on the order of $OPT / poly(n)$ which yields a $1/poly(n)$ error
in the approximation bound.

\section{Approximation for symmetric instances}
\label{section:symmetric}

We can achieve a better approximation assuming that the instance exhibits
a certain symmetry. This is the same kind of symmetry that we use in our hardness
construction (Section~\ref{section:hardness-proof}) and the hard instances exhibit
the same symmetry as well. It turns out that our approximation in this case
matches the hardness threshold up to lower order terms.

Similar to our hardness result, the symmetries that we consider
here are permutations of the ground set $X$, corresponding
to permutations of coordinates in ${\boldmath R}^X$. We start with some basic
properties which are helpful in analyzing symmetric instances.

\begin{lemma}
\label{lemma:grad-sym}
Assume that $f:2^X \rightarrow {\boldmath R}$ is invariant with respect to
a group of permutations ${\cal G}$ and $F({\bf x}) = {\bf E}[f(\hat{{\bf x}})]$.
Then for any symmetrized vector $\bar{{\bf c}} = {\bf E}_{\sigma \in {{\cal G}}}[\sigma({\bf c})]$,
$\nabla F |_{\bar{{\bf c}}}$ is also symmetric w.r.t. ${\cal G}$. I.e., for any $\tau \in {\cal G}$,
$$ \tau(\nabla F |_{{\bf x}=\bar{{\bf c}}}) = \nabla F |_{{\bf x}=\bar{{\bf c}}}. $$
\end{lemma}

\begin{proof}
Since $f(S)$ is invariant under ${\cal G}$, so is $F({\bf x})$,
i.e. $F({\bf x}) = F(\tau({\bf x}))$ for any $\tau \in {\cal G}$.
Differentiating both sides at ${\bf x}={\bf c}$, we get by the chain rule:
$$ \partdiff{F}{x_i} \Big|_{{\bf x}={\bf c}} =
 \sum_j \partdiff{F}{x_j} \Big|_{{\bf x}=\tau({\bf c})} \partdiff{}{x_i} (\tau(x))_j
 = \sum_j \partdiff{F}{x_j} \Big|_{{\bf x}=\tau({\bf c})} \partdiff{x_{\tau(j)}}{x_i}. $$
Here, $\partdiff{x_{\tau(j)}}{x_i} = 1$ if $\tau(j) = i$, and $0$ otherwise.
Therefore,
$$ \partdiff{F}{x_i} \Big|_{{\bf x}={\bf c}} =
 \partdiff{F}{x_{\tau^{-1}(i)}} \Big|_{{\bf x}=\tau({\bf c})}. $$
Note that $\tau(\bar{{\bf c}}) = {\bf E}_{\sigma \in {\cal G}}[\tau(\sigma({\bf c}))]
 =  {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf c})] = \bar{{\bf c}}$
since the distribution of $\tau \circ \sigma$ is equal to the distribution
of $\sigma$. Therefore,
$$ \partdiff{F}{x_i} \Big|_{{\bf x}=\bar{{\bf c}}} = \partdiff{F}{x_{\tau^{-1}(i)}}
  \Big|_{{\bf x}=\bar{{\bf c}}} $$
for any $\tau \in {\cal G}$.
\end{proof}

Next, we prove that the ``symmetric optimum''
$\max \{F(\bar{{\bf x}}): {\bf x} \in P({\cal F})\}$ gives a solution which is
a local optimum for the original instance $\max \{F({\bf x}): {\bf x} \in P({\cal F})\}$.
(As we proved in Section~\ref{section:hardness-proof}, in general
we cannot hope to find a better solution than the symmetric optimum.)

\begin{lemma}
\label{lemma:sym-local-opt}
Let $f:2^X \rightarrow {\boldmath R}$ and ${\cal F} \subset 2^X$
be invariant with respect to a group of permutations $\cal G$.
Let $\overline{OPT} = \max \{ F(\bar{{\bf x}}): {\bf x} \in P({\cal F}) \}$
where $\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$,
and let ${\bf x}_0$ be the symmetric point
where $\overline{OPT}$ is attained  ($\bar{{\bf x}}_0 = {\bf x}_0$).
Then ${\bf x}_0$ is a local optimum for the problem
$\max \{F({\bf x}): {\bf x} \in P({\cal F}) \}$, in the sense that
$({\bf x}-{\bf x}_0) \cdot \nabla F |_{{\bf x}_0} \leq 0$ for any ${\bf x} \in P({\cal F})$.
\end{lemma}

\begin{proof}
Assume for the sake of contradiction that $({\bf x}-{\bf x}_0) \cdot \nabla F|_{{\bf x}_0} > 0$
for some ${\bf x} \in P({\cal F})$. We use the symmetric properties of $f$ and ${\cal F}$
to show that $(\bar{{\bf x}} - {\bf x}_0) \cdot \nabla F|_{{\bf x}_0} > 0$ as well.
Recall that ${\bf x}_0 = \bar{{\bf x}}_0$. We have
$$ (\bar{{\bf x}} - {\bf x}_0) \cdot \nabla F|_{{\bf x}_0}
 = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x}-{\bf x}_0) \cdot \nabla F|_{{\bf x}_0}]
 = {\bf E}_{\sigma \in {\cal G}}[({\bf x}-{\bf x}_0) \cdot \sigma^{-1}(\nabla F|_{{\bf x}_0})]
 = ({\bf x}-{\bf x}_0) \cdot \nabla F|_{{\bf x}_0} > 0 $$
using Lemma~\ref{lemma:grad-sym}.  Hence, there would be a direction
$\bar{{\bf x}} - {\bf x}_0$ along which an improvement can be obtained.
But then, consider a small $\delta > 0$ such that
${\bf x}_1 = {\bf x}_0 + \delta (\bar{{\bf x}} - {\bf x}_0) \in P({\cal F})$ and also
$F({\bf x}_1) > F({\bf x}_0)$. The point ${\bf x}_1$ is symmetric ($\bar{{\bf x}}_1 = {\bf x}_1$)
and hence it would contradict the assumption that $F({\bf x}_0) = \overline{OPT}$.
\end{proof}

\subsection{Submodular maximization over independent sets in a matroid}

Let us derive an optimal approximation result for the problem
$\max \{f(S): S \in {\cal I}\}$ under the assumption that the instance is "element-transitive".

\begin{definition}
For a group ${\cal G}$ of permutations on $X$, the orbit of an element $i \in X$
is the set $\{ \sigma(i): \sigma \in {\cal G} \}$.
${\cal G}$ is called element-transitive, if the orbit of any element is
the entire ground set $X$.
\end{definition}

In this case, we show that it is easy to achieve an optimal $(\frac12-o(1))$-approximation
for a matroid independence constraint.

\begin{theorem}
\label{thm:sym-submod-independent}
Let $\max \{f(S): S \in {\cal I}\}$ be an instance symmetric with respect
to an element-transitive group of permutations ${\cal G}$. Let
$\overline{OPT} = \max \{F(\bar{{\bf x}}): {\bf x} \in P({\cal M})\}$
 where $\bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$.
Then $\overline{OPT} \geq \frac12 OPT$.
\end{theorem}

\begin{proof}
Let $OPT = f(C)$.
By Lemma~\ref{lemma:sym-local-opt}, $\overline{OPT} = F({\bf x}_0)$
where ${\bf x}_0$ is a local optimum for the problem $\max \{F({\bf x}): {\bf x} \in P({\cal M})$.
This means it is also a local optimum in the sense of Lemma~\ref{lemma:local-opt},
with $t=1$.
By Lemma~\ref{lemma:fractional-search},
$$ 2 F({\bf x}_0) \geq F({\bf x}_0 \vee {\bf 1}_C) + F({\bf x}_0 \wedge {\bf 1}_C).$$
Also, ${\bf x}_0 = \bar{{\bf x}}_0$. As we are dealing with an element-transitive
group of symmetries, this means all the coordinates of ${\bf x}_0$ are equal,
${\bf x}_0 = (\xi,\xi,\ldots,\xi)$. Therefore, ${\bf x}_0 \vee {\bf 1}_C$ is equal
to $1$ on $C$ and $\xi$ outside of $C$. By Lemma~\ref{lemma:rnd-threshold} (in the Appendix),
$$ F({\bf x}_0 \vee {\bf 1}_C) \geq (1-\xi) f(C).$$
Similarly, ${\bf x}_0 \wedge {\bf 1}_C$ is equal to $\xi$ on $C$ and $0$ outside of $C$.
By Lemma~\ref{lemma:rnd-threshold},
$$ F({\bf x}_0 \wedge {\bf 1}_C) \geq \xi f(C).$$
Combining the two bounds,
$$ 2 F({\bf x}_0) \geq F({\bf x}_0 \vee {\bf 1}_C) + F({\bf x}_0 \wedge {\bf 1}_C)
 \geq (1-\xi) f(C) + \xi f(C) = f(C) = OPT.$$
\end{proof}

Since all symmetric solutions ${\bf x} = (\xi,\xi,\ldots,\xi)$ form
a 1-parameter family, and $F(\xi,\xi,\ldots,\xi)$ is a concave function,
we can search for the best symmetric solution (within any desired accuracy)
by binary search. By standard techniques, we get the following.

\begin{corollary}
There is a $(\frac12 - o(1))$-approximation ("brute force" search
over symmetric solutions) for the problem $\max \{f(S): S \in {\cal I}\}$
for instances symmetric under an element-transitive group of permutations.
\end{corollary}

The hard instances for submodular maximization subject to a matroid
independence constraint correspond to refinements of the
Max Cut instance for the graph $K_2$ (Section~\ref{section:hardness-applications}).
It is easy to see that such instances are element-transitive,
and it follows from Section~\ref{section:hardness-proof} that a $(\frac12+\epsilon)$-approximation
for such instances would require exponentially many value queries.
Therefore, our approximation for element-transitive instances is optimal.

\subsection{Submodular maximization over bases}

Let us come back to the problem of submodular maximization over the bases
of matroid. The property that $\overline{OPT}$ is a local optimum
with respect to the original problem $\max \{F({\bf x}): {\bf x} \in P({\cal F})\}$
is very useful in arguing about the value of $\overline{OPT}$.
We already have tools to deal with local optima from
Section~\ref{section:submod-bases}. Here we prove the following.

\begin{lemma}
\label{lemma:base-local-opt}
Let $B({\cal M})$ be the matroid base polytope of ${\cal M}$ and
${\bf x}_0 \in B({\cal M})$ a local maximum for the submodular maximization problem
$\max \{F({\bf x}): {\bf x} \in B({\cal M})\}$, in the sense that $({\bf x}-{\bf x}_0) \cdot \nabla F|_{{\bf x}_0} \leq 0$
for any ${\bf x} \in B({\cal M})$. Assume in addition that ${\bf x}_0 \in [s,t]^X$. Then
$$ F({\bf x}_0) \geq \frac12 (1-t+s) \cdot OPT.$$
\end{lemma}

\begin{proof}
Let $OPT = \max \{ f(B): B \in {\cal B} \} = f(C)$.
We assume that ${\bf x}_0 \in B({\cal M})$ is a local optimum with respect
to any direction ${\bf x}-{\bf x}_0$, ${\bf x} \in B({\cal M})$, so it is also a local optimum with respect
to the fractional local search in the sense of Lemma~\ref{lemma:fractional-search2},
with $t=1$. The lemma implies that
$$ 2 F({\bf x}_0) \geq F({\bf x} \vee {\bf 1}_C) + F({\bf x} \wedge {\bf 1}_C).$$
By assumption, the coordinates of ${\bf x} \vee {\bf 1}_C$ are equal to $1$ on $C$
and at most $t$ outside of $C$. With probability $1-t$, a random threshold in $[0,1]$
falls between $t$ and $1$, and Lemma~\ref{lemma:rnd-threshold} (in the Appendix) implies that
$$ F({\bf x} \vee {\bf 1}_C) \geq (1-t) \cdot f(C).$$
Similarly, the coordinates of ${\bf x} \wedge {\bf 1}_C$ are $0$ outside of $C$,
and at least $s$ on $C$. A random threshold falls between $0$ and $s$
with probability $s$, and Lemma~\ref{lemma:rnd-threshold} implies that
$$ F({\bf x} \wedge {\bf 1}_C) \geq s \cdot f(C).$$
Putting these inequalities together, we get
$$2 F({\bf x}_0) \geq F({\bf x} \vee {\bf 1}_C) + F({\bf x} \wedge {\bf 1}_C) \geq (1-t+s) \cdot f(C).$$
\end{proof}

\

\noindent
{\bf Totally symmetric instances.}
The application we have in mind here is a special case of submodular
maximization over the bases of a matroid, which we call {\em totally symmetric}.

\begin{definition}
\label{def:totally-symmetric}
We call an instance $\max \{f(S): S \in {\cal F} \}$ totally symmetric with respect
to a group of permutations ${\cal G}$, if both $f(S)$ and ${\cal F}$ are invariant
under ${\cal G}$ and moreover, there is a point ${\bf c} \in P({\cal F})$ such that
${\bf c} = \bar{{\bf x}} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf x})]$ for every ${\bf x} \in P({\cal F})$.
We call ${\bf c}$ the center of the instance.
\end{definition}

Note that this is indeed stronger than just being invariant under ${\cal G}$.
For example, an instance on a ground set $X = X_1 \cup X_2$ could be symmetric
with respect to any permutation of $X_1$ and any permutation of $X_2$.
For any ${\bf x} \in P({\cal F})$, the symmetric vector $\bar{{\bf x}}$ is constant
on $X_1$ and constant on $X_2$. However, in a totally symmetric instance,
there should be a unique symmetric point.

\paragraph{Bases of partition matroids}
A canonical example of a totally symmetric instance is as follows.
Let $X = X_1 \cup X_2 \cup \ldots \cup X_m$ and let integers $k_1,\ldots,k_m$
be given. This defines a partition matroid ${\cal M} = (X,{\cal B})$, whose bases are
$$ {\cal B} = \{B: \forall j; |B \cap X_j| = k_j \}.$$
The associated matroid base polytope is
$$ B({\cal M}) = \{{\bf x} \geq 0: \forall j; \sum_{i \in X_j} x_i = k_j \}.$$
Let ${\cal G}$ be a group of permutations such that the orbit of each element
$i \in X_j$ is the entire set $X_j$.
This implies that for any ${\bf x} \in B({\cal M})$,
$\bar{{\bf x}}$ is the same vector ${\bf c}$, with coordinates $k_j / |X_j|$ on $X_j$.
If $f(S)$ is also invariant under ${\cal G}$, we have a totally symmetric
instance $\max \{f(S): S \in {\cal B} \}$.

\paragraph{Example: welfare maximization}
To present a more concrete example, consider $X_j = \{ a_{j1}, \ldots, a_{jk} \}$
for each $j \in [m]$, a set of bases ${\cal B} = \{B: \forall j; |B \cap X_j| = 1\}$,
and an objective function in the form $f(S) = \sum_{i=1}^{k} v(\{j: a_{ji} \in S\})$,
where $v:2^{[m]} \rightarrow {\boldmath R}_+$ is a submodular function.
This is a totally symmetric instance, which captures the welfare maximization
problem for combinatorial auctions where each player has the same valuation function.
(Including element $a_{ji}$ in the solution corresponds to allocating item $j$ to player $i$;
see \cite{CCPV09} for more details.) We remark that here we consider possibly
nonmonotone submodular functions, which is not common for combinatorial auctions;
nevertheless the problem still makes sense.

\

We show that for such instances, the center point achieves an improved approximation.

\begin{theorem}
\label{thm:sym-solution}
Let $\max \{f(S): S \in {\cal B}\}$ be a totally symmetric instance.
Let the fractional packing number of bases be $\nu$ and the fractional
packing number of dual bases $\nu^*$. Then the center point ${\bf c}$
satisfies
$$ F({\bf c}) \geq \left(1 - \frac{1}{2\nu} - \frac{1}{2\nu^*} \right) OPT.$$
\end{theorem}

Recall that in the general case, we get a $\frac12 (1-1/\nu-o(1))$-approximation
(Theorem~\ref{thm:submod-bases-approx}). By passing to the dual matroid,
we can also obtain a $\frac12 (1-1/\nu^*-o(1))$-approximation,
so in general, we know how to achieve a $\frac12 (1-1/\max\{\nu,\nu^*\}-o(1))$-approximation.
For totally symmetric instances where $\nu=\nu^*$, we improve this
to the optimal factor of $1-1/\nu$.

\begin{proof}
Since there is a unique center ${\bf c} = \bar{{\bf x}}$ for any ${\bf x} \in B({\cal M})$,
this means this is also the symmetric optimum $F({\bf c}) = \max \{ F(\bar{{\bf x}}): {\bf x} \in B({\cal M})\}$.
Due to Lemma~\ref{lemma:sym-local-opt}, ${\bf c}$ is a local optimum
for the problem $\max \{F({\bf x}): {\bf x} \in B({\cal M})\}$.

Because the fractional packing number of bases is $\nu$, we have $c_i \leq 1/\nu$
for all $i$. Similarly, because the fractional packing number of dual bases
(complements of bases) is $\nu^*$,
we have $1-c_i \leq 1/\nu^*$. This means that ${\bf c} \in [1-1/\nu^*,1/\nu]$.
Lemma~\ref{lemma:base-local-opt} implies that
$$ 2 F({\bf c}) \geq \left( 1-\frac{1}{\nu} + 1-\frac{1}{\nu^*} \right) OPT.$$
\end{proof}

\begin{corollary}
Let $\max \{f(S): S \in {\cal B}\}$ be an instance
on a partition matroid where every base takes at least
an $\alpha$-fraction of each part, at most a $(1-\alpha)$-fraction of each part,
and the submodular function $f(S)$ is invariant under a group ${\cal G}$
where the orbit of each $i \in X_j$ is $X_j$.
Then, the center point ${\bf c} = {\bf E}_{\sigma \in {\cal G}}[\sigma({\bf 1}_B)]$
(equal for any $B \in {\cal B}$) satisfies $F({\bf c}) \geq \alpha \cdot OPT$.
\end{corollary}

\begin{proof}
If the orbit of any element $i \in X_j$ is the entire set $X_j$,
it also means that $\sigma(i)$ for a random $\sigma \in {\cal G}$
is uniformly distributed over $X_j$ (by the transitive property of ${\cal G}$).
Therefore, symmetrizing any fractional vector ${\bf x} \in B({\cal M})$ gives
the same vector $\bar{{\bf x}} = {\bf c}$, where $c_i = k_j / |X_j|$ for $i \in X_j$.
Also, our assumptions mean that the fractional packing number of bases
is $1/(1-\alpha)$, and the fractional packing number of dual bases is
also $1/(1-\alpha)$.
Due to Lemma~\ref{thm:sym-solution}, the center ${\bf c}$ satisfies
$F({\bf c}) \geq \alpha \cdot OPT$.
\end{proof}

The hard instances for submodular maximization over matroid bases
that we describe in Section~\ref{section:hardness-applications} are exactly of this form
(see the last paragraph of Section~\ref{section:hardness-applications}, with $\alpha=1/k$).
There is a unique symmetric solution,
$x = (\alpha,\alpha,\ldots,\alpha, 1-\alpha,1-\alpha,\ldots,1-\alpha)$.
The fractional base packing number for these matroids is
$\nu = 1/(1-\alpha)$ and Theorem~\ref{thm:general-hardness} implies that
any $(\alpha+\epsilon) = (1-1/\nu+\epsilon)$-approximation for such matroids would
require exponentially many value queries. Therefore, our approximation
in this special case is optimal.

\section*{Acknowledgment}
The author would like to thank Jon Lee and Maxim Sviridenko for helpful discussions.

redpajama_set_name: RedPajamaArXiv