# Information Complexity of Mixed-integer Convex Optimization

Amitabh Basu  Department of Applied Mathematics and Statistics, Johns Hopkins
University
<EMAIL_ADDRESS>Hongyi Jiang  School of Civil and Environmental
Engineering, Cornell University
<EMAIL_ADDRESS>Phillip Kerger  Department of Applied Mathematics and
Statistics, Johns Hopkins University
<EMAIL_ADDRESS>Marco Molinaro  Microsoft Research (Redmond) and
Computer Science Department, PUC-Rio
<EMAIL_ADDRESS>
###### Abstract

We investigate the information complexity of mixed-integer convex optimization
under different types of oracles. We establish new lower bounds for the
standard first-order oracle, improving upon the previous best known lower
bound. This leaves only a lower order linear term (in the dimension) as the
gap between the lower and upper bounds. This is derived as a corollary of a
more fundamental “transfer” result that shows how lower bounds on information
complexity of continuous convex optimization under different oracles can be
transferred to the mixed-integer setting in a black-box manner.

Further, we (to the best of our knowledge) initiate the study of, and obtain
the first set of results on, information complexity under oracles that only
reveal _partial_ first-order information, e.g., where one can only make a
binary query over the function value or subgradient at a given point. We give
algorithms for (mixed-integer) convex optimization that work under these less
informative oracles. We also give lower bounds showing that, for some of these
oracles, every algorithm requires more iterations to achieve a target error
compared to when complete first-order information is available. That is, these
oracles are provably less informative than full first-order oracles for the
purpose of optimization.

Keywords: Mixed-integer optimization, convex optimization, information
complexity, lower bounds

##  1 First-order information complexity

We consider the problem class of mixed-integer convex optimization:

$\inf\\{f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}):({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})\in
C,({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\in{\mathbb{Z}}^{n}\times\mathbb{R}^{d}\\},$ (1)

where $f:\mathbb{R}^{n}\times\mathbb{R}^{d}\to\mathbb{R}$ is a convex
(possibly nondifferentiable) function and
$C\subseteq\mathbb{R}^{n}\times\mathbb{R}^{d}$ is a closed, convex set. Given
$\varepsilon\geq 0$, we wish to report a point
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})\in
C\cap({\mathbb{Z}}^{n}\times\mathbb{R}^{d})$ such that
$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})\leq
f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})+\varepsilon$ for
all $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})\in
C\cap({\mathbb{Z}}^{n}\times\mathbb{R}^{d})$. Such a point will be called an
$\varepsilon$-approximate solution and points in
$C\cap({\mathbb{Z}}^{n}\times\mathbb{R}^{d})$ will be called feasible
solutions. We say that ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}_{1},\ldots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}_{n}$ are the integer-valued
decision variables or simply the integer variables of the problem, and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}_{1},\ldots,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{d}$ are called the
continuous variables.

The notion of information complexity (a.k.a. oracle complexity or analytical
complexity) goes back to foundational work by Nemirovski and Yudin [12] on
convex optimization (without integer variables) and is based on the following.
An algorithm for reporting an $\varepsilon$-approximate solution to an
instance $(f,C)$ must be “given” the instance somehow. Allowing only instances
with explicit, algebraic descriptions (e.g., the case of linear programming)
can be restrictive in some settings. To work with more general, nonlinear
instances, the algorithm is allowed to make queries to an oracle to collect
information about the instance. More formally, we have the following
definition.

######  Definition 1.

An oracle $\mathcal{O}$ for an optimization problem class $\mathcal{I}$ is
given by a family $\mathcal{Q}$ of possible queries along with a set $H$ of
possible answers or responses. A query $q\in\mathcal{Q}$ is a function
$q:\mathcal{I}\rightarrow H$. We say that $q(I)\in H$ is the answer or
response to the query $q$ for the instance $I\in\mathcal{I}$.

Any algorithm using such an oracle to find an $\varepsilon$-approximate
solution for an instance makes queries about the instance in a sequence
according to some strategy depending on the queries made and answers received,
which we define formally as its query strategy.

######  Definition 2.

A query strategy is a function $D:(\mathcal{Q}\times H)^{*}\to\mathcal{Q}$,
where $(\mathcal{Q}\times H)^{*}$ denotes the set of all finite sequences over
$\mathcal{Q}\times H$, including the empty sequence. The transcript $\Pi(D,I)$
of a strategy $D$ on an instance $I=(f,C)$ is the sequence of query and
response pairs $(q_{i},q_{i}(I))$, $i=1,2,\ldots$ obtained when one applies
$D$ on $I$, i.e., $q_{1}=D(\emptyset)$ and
$q_{i}=D((q_{1},q_{1}(I)),\ldots,(q_{i-1},q_{i-1}(I)))$ for $i\geq 2$.

If different instances with no common $\varepsilon$-approximate solution
produce the same transcript for the queries an algorithm has made, then the
algorithm cannot tell them apart and will be unable to reliably report an
$\varepsilon$-solution for those instances after those queries. The goal is to
design a query strategy that can report an $\varepsilon$-approximate solution
after making the smallest number of queries. This motivates the following
definition of information complexity:

######  Definition 3.

Given a family of instances $\mathcal{I}$ and access to an oracle
$\mathcal{O}$, the $\varepsilon$-information complexity
$\operatorname*{icomp}\textstyle{{}_{\varepsilon}}(D,I,\mathcal{O})$ of an
instance $I$ for a query strategy $D$, is defined as the minimum natural
number $k$ such that the set of all instances in $\mathcal{I}$ for which
$\mathcal{O}$ returns the same responses as the instance $I$ to the first $k$
queries of $D$ have a common $\varepsilon$-approximate solution. The
$\varepsilon$-information complexity of the problem class $\mathcal{I}$ with
respect to the oracle $\mathcal{O}$, is defined as

$\operatorname*{icomp}\textstyle{{}_{\varepsilon}}(\mathcal{I},\mathcal{O}):=\inf_{D}\sup_{I\in\mathcal{I}}\operatorname*{icomp}\textstyle{{}_{\varepsilon}}(D,I,\mathcal{O})$

where the infimum is taken over all query strategies.

Thus, to prove an upper bound $u$ on
$\operatorname*{icomp}\textstyle{{}_{\varepsilon}}(\mathcal{I},\mathcal{O})$,
it suffices to construct a query strategy that requires, in the worst case, at
most $u$ queries to narrow down to a collection of instances that all have a
common $\varepsilon$-approximate solution. On the other hand, to establish a
lower bound of $\ell$ on
$\operatorname*{icomp}\textstyle{{}_{\varepsilon}}(\mathcal{I},\mathcal{O})$,
one needs to show that for any query strategy $D$, there exists a collection
of instances in $\mathcal{I}$ that give the same responses to the first $\ell$
queries of $D$ (on these instances), and there is no point in
$\mathbb{R}^{n}\times\mathbb{R}^{d}$ that is a common
$\varepsilon$-approximate solution to all these instances.

While we introduce information complexity allowing for any general choice of
oracle, the standard oracle that has been studied over the past several
decades for convex optimization is the so-called (full-information) first-
order oracle, which has two types of queries indexed by points in
$\mathbb{R}^{n}\times\mathbb{R}^{d}$: i) a separation oracle query indexed by
a point ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in\mathbb{R}^{n+d}$ reports
“YES” if ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in C$ and otherwise reports a
separating hyperplane for $\textstyle\bf z$ and $C$, ii) a subgradient oracle
query indexed by a point ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in\mathbb{R}^{n+d}$ reports
$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})$ and a subgradient for $f$
at $\textstyle\bf z$. Tight lower and upper bounds (differing by only a small
constant factor) on the number of queries required were obtained by Nemirovski
and Yudin in their seminal work [12] for the case with no integer variables;
roughly speaking, the bound is
$\Theta\left(d\log\left(\frac{1}{\varepsilon}\right)\right)$. These insights
were extended to the mixed-integer setting in [13, 3, 2], with the best known
lower and upper bounds stated in [2].

Observe that the response to any separation/subgradient query is a vector in
$\mathbb{R}^{n+d}$. Thus, each query reveals at least $n+d$ bits of
information about the instance. A more careful accounting that measures the
“amount of information” accrued would track the total number of bits of
information obtained as opposed to just the total number of oracle queries
made. A natural question, posed in [2], is whether the bounds from the
classical analysis would change if one uses this new measure of the total
number of bits, as opposed to the number of queries. The intuition, roughly,
is that one should need a factor $(n+d)\log\left(\frac{1}{\varepsilon}\right)$
larger than the number of first-order queries, because one should need to
probe at least $\log\left(\frac{1}{\varepsilon}\right)$ bits in $n+d$
coordinates to recover the full subgradient/separating hyperplane (up to
desired approximations). We attempt to make some progress on this question in
this paper.

The above discussion suggests that one should consider oracles that return a
desired bit of a desired coordinate of the separating hyperplane vector or
subgradient. However, one can imagine making other binary queries on the
instance; for example, one can pick a direction and ask for the sign of the
inner product of the subgradient and this direction. In fact, one can consider
more general binary queries that have nothing to do with
subgradients/separating hyperplanes. If one allows all possible binary
queries, i.e., one can use any function from the space of instances to
$\\{0,1\\}$ as a query, then one can simply ask for the appropriate bits of
the true minimizer and in $O((n+d)\log(1/\varepsilon))$ queries, one can get
an $\varepsilon$-approximate solution. A matching lower bound follows from a
fairly straightforward counting argument. Thus, allowing for all possible
binary queries gives the same information complexity bound as the original
Nemirovski-Yudin bound with subgradient queries in the $n=0$ (no integer
variables) case, but is an exponential improvement when $n\geq 1$ (see [2] and
the discussion below). What this shows is that the bounds on information
complexity can be quite different under different oracles. With all possible
binary queries, while each query reveals only a single bit of information, the
queries themselves are a much richer class and this compensates to give the
same bound in the continuous case and exponentially better bounds in the
presence of integer variables. Thus, to get a better understanding of this
trade-off, we restrict to queries that still extract information by only
acting “locally”.

###  1.1 Our contributions

##### Oracles based on first-order information.

Our first contribution is formalizing this notion of general “local” queries.
While we focus on first-order information, our framework can be readily
extended to consider, for example, information from higher-order derivatives.

######  Definition 4.

An oracle using first-order information $\mathcal{O}(\mathcal{G},\mathcal{H})$
consists of two parts:

  1. 1.

For every ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in[-R,R]^{n+d}$, there exist
three maps ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sep}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}:\mathcal{I}_{n,d,R,\rho,M}\to\mathbb{R}^{n+d}$,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{val}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}:\mathcal{I}_{n,d,R,\rho,M}\to\mathbb{R}$, and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sub}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}:\mathcal{I}_{n,d,R,\rho,M}\to\mathbb{R}^{n+d}$ such that for all
$(f,C)\in\mathcal{I}_{n,d,R,\rho,M}$ the following properties hold.

    1. (a)

$C\subseteq\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\prime}\in\mathbb{R}^{n+d}:\langle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sep}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}(f,C),{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\prime}\rangle<\langle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sep}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}(f,C),{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\rangle\\}$ if
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\not\in C$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sep}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}(f,C)={\mathchoice{\mbox{\boldmath$\displaystyle\bf
0$}}{\mbox{\boldmath$\textstyle\bf 0$}}{\mbox{\boldmath$\scriptstyle\bf
0$}}{\mbox{\boldmath$\scriptscriptstyle\bf 0$}}}$ if
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\in C$. In other words,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sep}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(f,C)$ returns a (normal
vector to a) separating hyperplane if
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\not\in C$. We will assume
that a nonzero response ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sep}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(f,C)$ has norm 1, since
scalings do not change the separation property.

    2. (b)

${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{val}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}(f,C)=f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})$. In other words,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{val}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(f,C)$ returns the function
value for $f$ at $\textstyle\bf z$.

    3. (c)

${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sub}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(f,C)\in\partial
f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})$, where $\partial
f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})$ denotes the subdifferential
(the set of all subgradients) of $f$ at $\textstyle\bf z$. In other words,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sub}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(f,C)$ returns a subgradient
for $f$ at $\textstyle\bf z$.

Such maps will be called first-order maps. A collection of first-order maps,
one for every $\textstyle\bf z$, is called a first-order chart and will be
denoted by $\mathcal{G}$.

  2. 2.

There are three sets of functions $\mathcal{H}^{\textup{sep}}$,
$\mathcal{H}^{\textup{val}}$, and $\mathcal{H}^{\textup{sub}}$ and with
domains $\mathbb{R}^{n+d}$, $\mathbb{R}$ and $\mathbb{R}^{n+d}$ respectively.
We will use the notation
$\mathcal{H}=\mathcal{H}^{\textup{sep}}\cup\mathcal{H}^{\textup{val}}\cup\mathcal{H}^{\textup{sub}}$.
$\mathcal{H}$ will be called the collection of permissible queries of the
oracle.

An algorithm for instances of (1) using $\mathcal{O}(\mathcal{G},\mathcal{H})$
can, at any iteration, choose a point $\textstyle\bf z$ and a function
$h\in\mathcal{H}$ and receive the response
$h({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sep}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(\widehat{f},\widehat{C}))$,
$h({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{val}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(\widehat{f},\widehat{C}))$ or
$h({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}^{\textup{sub}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}(\widehat{f},\widehat{C})$,
depending on whether $h\in\mathcal{H}^{\textup{sep}}$,
$h\in\mathcal{H}^{\textup{val}}$ or $h\in\mathcal{H}^{\textup{sub}}$, where
$\widehat{f}$ and $\widehat{C}$ are the objective function and feasible
region, respectively, of the unknown instance. Hence, queries to an oracle
$\mathcal{O}(\mathcal{G},\mathcal{H})$ using first-order information are
indexed by $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}},h)$,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}\in\mathbb{R}^{n}\times\mathbb{R}^{d},h\in\mathcal{H}$. Since the goal of
this paper is to provide bounds for different types of such oracles, i.e.,
with different permissible queries $\mathcal{H}$, let us define some cases of
interest.

######  Definition 5 (Examples of oracles).

  1. 1.

(Full-information first-order oracle) When $\mathcal{H}$ consists only of the
identity functions, i.e.,
$h^{\textup{sep}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sep}}(\widehat{f},\widehat{C}))={\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sep}}(\widehat{f},\widehat{C})$,
$h^{\textup{val}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C}))={\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C})$ and
$h^{\textup{sub}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sub}}(\widehat{f},\widehat{C}))={\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sub}}(\widehat{f},\widehat{C})$, we recover a full-information
first-order oracle.

  2. 2.

(Bit oracle) Let $\mathcal{H}^{\textrm{bit}}$ be the set of binary queries
that return a desired bit (of a desired coordinate) of the binary
representation of ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sep}}(\widehat{f},\widehat{C})$,
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C})$ or
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sub}}(\widehat{f},\widehat{C})$. Let
$\mathcal{H}^{\textrm{bit}^{*}}$ be the shifted bit oracle that additionally
returns a desired bit of ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C})+u$, for any $u\in\mathbb{R}$,
i.e. $\mathcal{H}^{\textrm{bit}^{*}}$ allows querying a bit of the function
value shifted by some number.

  3. 3.

(Inner product threshold queries) Let

$\displaystyle\mathcal{H}^{\textrm{dir}}$
$\displaystyle:=\\{h^{\textup{sep}}_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},c}:h^{\textup{sep}}_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},c}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sep}}(\widehat{f},\widehat{C}))=sgn(\langle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sep}}(\widehat{f},\widehat{C})\rangle-c),{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}}\in\mathbb{R}^{n+d},c\in\mathbb{R}\\}$
$\displaystyle\cup\\{h^{\textup{val}}_{u,c}:h^{\textup{val}}_{u,c}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C}))=sgn(u\cdot{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C})-c),u\in\mathbb{R},c\in\mathbb{R}\\}$
$\displaystyle\cup\\{h^{\textup{sub}}_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},c}:h^{\textup{sub}}_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},c}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sub}}(\widehat{f},\widehat{C}))=sgn(\langle{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{sub}}(\widehat{f},\widehat{C})\rangle-c),{\mathchoice{\mbox{\boldmath$\displaystyle\bf
u$}}{\mbox{\boldmath$\textstyle\bf u$}}{\mbox{\boldmath$\scriptstyle\bf
u$}}{\mbox{\boldmath$\scriptscriptstyle\bf
u$}}}\in\mathbb{R}^{n+d},c\in\mathbb{R}\\},$

where sgn denotes the sign function, be the set of binary queries that answers
whether the inner product of the separating hyperplane, function value or
subgradient, with a vector or a number of choice $\textstyle\bf u$ or $u$ in
the appropriate space, is at least some value $c$ or not. We write these as
$\mathcal{H}^{\textrm{dir}}$ since these queries allow for the choice of a
“direction” $\textstyle\bf u$, or a number $u$ in the function value case, as
part of the query.

  4. 4.

When $\mathcal{H}$ is the the set of all possible binary functions on
$\mathbb{R}^{n}\times\mathbb{R}^{d}$ for the separating hyperplanes,
$\mathbb{R}$ for the functions values, and
$\mathbb{R}^{n}\times\mathbb{R}^{d}$ for the subgradients, we will call the
resulting oracle the general binary oracle based on $\mathcal{G}$.

These now give us a variety of oracles using first-order information, that
clearly provide very different information for each query depending on the
choice of permissible queries $\mathcal{H}$. Note that different first-order
charts will result in different oracles of each of these types that may give
different answers at any point, depending on which separating
hyperplane/subgradient the oracle’s first-order map selects at those points
for that instance.

We are now ready to state our quantitative results for lower and upper bounds
on the information complexity of mixed-integer convex optimization under
different oracles; see Table 1 for a summary. It is not hard to see that we
need to restrict the set of possible instances $\mathcal{I}$ in order to have
meaningful (finite) information complexity
$\operatorname*{icomp}_{\varepsilon}(\mathcal{I},\mathcal{O})$. We will focus
on the following standard parameterization.

######  Definition 6.

Define $\mathcal{I}_{n,d,R,\rho,M}$ to be the set of all instances of (1) such
that:

  1. (i)

$C$ is contained in the box $\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}\in\mathbb{R}^{n}\times\mathbb{R}^{d}:\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\|_{\infty}\leq R\\}$. The
case $C=\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}\in\mathbb{R}^{n}\times\mathbb{R}^{d}:\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}\|_{\infty}\leq R\\}$ will be
called unconstrained.

  2. (ii)

If $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\star},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\star})$ is an optimal
solution of the instance, then there exists
$\hat{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in\mathbb{R}^{d}$ satisfying
$\\{({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\star},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}):\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}-\hat{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}\|_{\infty}\leq\rho\\}\subseteq C$. In other words, there is a “strictly
feasible” point $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\star},\hat{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ in the same fiber as the
optimum $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\star},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\star})$.

  3. (iii)

$f$ is Lipschitz continuous with respect to the $\|\cdot\|_{\infty}$-norm with
Lipschitz constant $M$ on $\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\\}\times[-R,R]^{d}$ for all
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}\in[-R,R]^{n}\cap{\mathbb{Z}}^{n}$. In other words, for any
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}),({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{\prime})\in({\mathbb{Z}}^{n}\times\mathbb{R}^{d})\cap[-R,R]^{n+d}$ with
$\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}-{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime}\|_{\infty}\leq R$,
$|f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})-f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})|\leq
M\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}-{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime}\|_{\infty}$ with the
convention that $\infty-\infty=0$.

Type of first-order oracle $\mathcal{O}(\mathcal{G},\mathcal{H})$ |  Variables |  Lower bound |  Upper bound
---|---|---|---
$\mathcal{H}$ is hereditary |  Mixed |  $\Omega(2^{n}\ell)$, where
${\ell\leq\operatorname*{icomp}_{\varepsilon}(\mathcal{I}_{0,d,R,\rho,M},\mathcal{O}(\mathcal{G},\mathcal{H}))}$
(Theorem 7)
|
Full-information first-order oracle |  Mixed |  $\Omega\left(2^{n}d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$
(Corollary 8)
|
$O\left(2^{n}d(n+d)\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$
(Oertel [13], Basu-Oertel [3])
$\mathcal{H}^{bit},\mathcal{H}^{bit^{*}},\mathcal{H}^{dir}$, or General Binary Queries |  Mixed |  $\tilde{\Omega}\left(2^{n}\max\left\\{d^{\frac{8}{7}},d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right\\}\right)$
(Theorem 9) |  $O\left(2^{n}d\,(n+d)^{2}\log^{2}\left(\frac{(n+d)MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$
(Theorem 10)
|  Continuous |  $\tilde{\Omega}\left(\max\left\\{d^{\frac{8}{7}},d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right\\}\right)$
(Theorem 9)
|
$O\left(d^{2}\log^{2}\left(\frac{dMR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$
(Theorem 11)
General Binary |  Mixed |  $\tilde{\Omega}\left(2^{n}\max\left\\{d^{\frac{8}{7}},d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right\\}\right)$
(Theorem 9)
|
$O\left(\log|\mathcal{I}|+2^{n}d(n+d)\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$
(Corollary 13)
|  Continuous |  $\tilde{\Omega}\left(\max\left\\{d^{\frac{8}{7}},d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right\\}\right)$
(Theorem 9) |  $O\left(\log|\mathcal{I}|+d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$
(Corollary 13)
Table 1: Summary of results on the information complexity of mixed-integer
convex optimization for the class of instances $\mathcal{I}_{n,d,R,\rho,M}$
that have $n$ integer variables, $d$ continuous variables, the feasible region
lies in the box $[-R,R]^{n+d}$ and has a “$\rho$-deep feasible point” on the
optimal fiber, and the objective function is $M$-Lipschitz with respect to
$\ell_{\infty}$ (see Definition 6). The table presents simplified bounds
showing only the main parameters.

##### Lower bounds.

Our first result is a “transfer” theorem that will be a powerful tool for
obtaining concrete mixed-integer lower bounds under different oracles. This
theorem lifts lower bounds for unconstrained optimization from the continuous
to the mixed-integer setting. In particular, if one has a lower bound $\ell$
with respect to an oracle using first-order information (Definition 4) for the
information complexity for some family of purely continuous instances, then
one can “transfer” that lower bound to the mixed-integer case as
$\Omega(2^{n}\ell)$ with access to the “same” oracle in the $n+d$ dimensional
space. For this notion, we require the set of permissible queries
$\mathcal{H}$ to be hereditary. Roughly speaking, this means that the set of
queries has the same richness on a purely continuous space as it is in a
mixed-integer space. We formally define hereditary queries in Section 2, and
note that all of the types of permissible queries discussed in Definition 5
satisfy this property, except for $\mathcal{H}^{bit}$ (the slightly enhanced
$\mathcal{H}^{bit^{*}}$ queries are hereditary).

######  Theorem 7.

Let $\mathcal{H}_{n,d}$ be any class of hereditary permissible queries, and
assume $\mathcal{H}_{0,d}$ contains function threshold queries $h_{c}$ that
answer $h_{c}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C})):=sgn({\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf
z$}}}^{\textup{val}}(\widehat{f},\widehat{C})+c)$ for any $c\in\mathbb{R}$.
Let $\varepsilon\geq 0$. Suppose, for some $d\geq 1$, there exists a class
$\mathcal{I}\subseteq\mathcal{I}_{0,d,R,\rho,M}$ of continuous convex
(unconstrained) optimization problems in $\mathbb{R}^{d}$, and a first order
chart $\mathcal{G}_{0}$ for $\mathcal{I}$ such that
$\operatorname*{icomp}_{\varepsilon}(\mathcal{I},\mathcal{O}(\mathcal{G}_{0},\mathcal{H}_{0,d}))\geq\ell$.
Suppose further that all instances in $\mathcal{I}$ have the same optimal
value. Then, for any number of integer variables $n\geq 1$, there is a first
order chart $\mathcal{G}_{n}$ such that
$\operatorname*{icomp}_{\varepsilon}(\mathcal{I}_{n,d,R,\rho,M},\mathcal{O}(\mathcal{G}_{n},\mathcal{H}_{n,d}))\geq
2^{n-1}\ell$.

As a first consequence of this transfer theorem we obtain a sharpened lower
bound for the standard full-information first-order oracle case for mixed-
integer problems. For this setting, Basu [2] proved the lower bound of
$\Omega\big{(}2^{n}\cdot d\log\big{(}\frac{2R}{3\rho}\big{)}\big{)}$. However,
this bound is independent of the Lipschitz constant $M$ of the objective
function, and thus does not capture the hardness of the problem as $M$
increases. By applying Theorem 7 to the classical lower bound of
$\Omega\big{(}d\log\big{(}\frac{MR}{\varepsilon}\big{)}\big{)}$ for continuous
convex optimization with the standard first-order oracle by Nemirovski and
Yudin [12], and combining the result with the existing mixed-integer lower
bound, we obtain the following improved bound.

######  Corollary 8.

There exists a first-order chart $\mathcal{G}$ such that for the full-
information first-order oracle based on $\mathcal{G}$ (i.e., $\mathcal{H}$
consists of the identity functions) we have

$\operatorname*{icomp}\textstyle{{}_{\varepsilon}}(\mathcal{I}_{n,d,R,\rho,M},\mathcal{O}(\mathcal{G},\mathcal{H}))=\Omega\left(2^{n}\left(1+d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)\right).$

Moving on to “non-standard” oracles, we consider mixed-integer convex
optimization under the general binary oracle. Recall from Definition 5 that
this means that the algorithm can make any binary query on
subgradients/separating hyperplanes. Despite the power of these queries, we
prove a separation between the information complexity under the standard full-
information first-order oracle and the general binary oracle, i.e., the latter
provides quantitatively less information for solving the problem. For example,
in the pure continuous setting, $O(d)$ queries suffice (ignoring the
logarithmic dependence on other parameters) under the full-information first-
order oracle. However, we show that $\Omega(d^{8/7})$ queries are needed under
the general binary oracle. More precisely, we show the following lower bound.

######  Theorem 9.

For every $n\geq 0$, there exists a first-order chart $\mathcal{G}$ such that
for the general binary oracle based on $\mathcal{G}$ we have

$\operatorname*{icomp}\textstyle{{}_{\varepsilon}}(\mathcal{I}_{n,d,R,\rho,M},\mathcal{O}(\mathcal{G},\mathcal{H}))=\tilde{\Omega}\left(2^{n}\left(1+\max\left\\{d^{\frac{8}{7}},d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)\right\\}\right),$

where $\tilde{\Omega}$ hides polylogarithmic factors in $d$.

We note that, since $\mathcal{H}^{bit}$, $\mathcal{H}^{bit^{*}}$ and
$\mathcal{H}^{dir}$ are more restrictive than the general binary oracle, this
lower bound applies to oracles with those permissible queries as well. The
proof of this result relies on a connection between information complexity and
_memory constrained_ algorithms for convex optimization, and the recent lower
bound for the latter from [11] (in addition to Theorem 7 for lifting the
result to the mixed-integer case).

##### Upper bounds.

We now present upper bound results that illustrate the connection between
information complexity based on full-information first-order oracles and
information complexity based on binary queries on separating hyperplanes and
subgradients. We first formalize the intuition that by making roughly
$O\left((n+d)\log\left(\frac{1}{\varepsilon}\right)\right)$ bit or inner
product sign queries on a separating hyperplane or subgradient, one should
have enough information to solve the problem as with full information
(Theorems 10 and 11). Next, in Theorem 12 and Corollary 13, we show how this
natural bound can be improved in certain settings.

######  Theorem 10.

Assume $d\geq 1$. For $U>0$, consider the subclass of instances of
$\mathcal{I}_{n,d,R,\rho,M}$ whose objective function values lie in $[-U,U]$,
and the fiber over the optimal solution contains a $\textstyle\bf z$ such that
the $(n+d)$-dim $\rho$-radius $\ell_{\infty}$ ball centered at $\textstyle\bf
z$ is contained in $C$. There exists a query strategy for this subclass that
reports an $\varepsilon$-approximate solution by making at most

$O\left(2^{n}d\,(n+d)\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)\cdot\left((n+d)\log\left(\frac{(n+d)MR}{\rho\varepsilon}\right)+\log\frac{U}{\varepsilon}\right)$

queries to an oracle $\mathcal{O}(\mathcal{G},\mathcal{H})$, where
$\mathcal{G}$ is any first-order chart and $\mathcal{H}$ is either
$\mathcal{H}^{\textup{bit}}$ or $\mathcal{H}^{\textup{dir}}$.

Prescribing an a priori range for objective function values is not a serious
restriction for two reasons: i) The difference between the maximum and the
minimum values of an objective function in $\mathcal{I}_{n,d,R,\rho,M}$ is at
most $2MR$, and ii) All optimization problems whose objective functions differ
by a constant are equivalent. We also comment that while we assume $d\geq 1$
in Theorem 10, similar bounds can be established for the $d=0$ (pure integer)
case. We omit this here because a unified expression for the $d=0$ and $d\geq
1$ cases becomes unwieldy and difficult to parse.

The main idea behind Theorem 10 is to show that existing methods with the best
known information complexity for mixed-integer convex optimization that use
full-information first-order oracles can also work with approximate separation
and subgradient oracles that return desired approximations of the true vectors
(with no loss in the information complexity). Then one shows that one can
produce these approximations with roughly
$O\left((n+d)\log\left(\frac{1}{\varepsilon}\right)\right)$ bit or inner
product sign queries on a separating hyperplane or subgradient. With bit
queries, this is just a matter of probing enough bits of each coordinate of
the vector. The case with inner product sign queries is a bit more involved
and our main tool is a result that shows how to approximate any vector up to
desired accuracy with such queries (Lemma 30).

Subsequently, using similar techniques we present an enhanced upper bound for
the scenario where $n=0$ (pure continuous case).

######  Theorem 11.

For $U>0$, consider the subclass of instances of $\mathcal{I}_{n,d,R,\rho,M}$
where $n=0$ (pure continuous case) and the objective function values lie in
$[-U,U]$. There exists a query strategy for this subclass that reports an
$\varepsilon$-approximate solution by making at most

$O\left(d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)\cdot\left(d\log\left(\frac{dMR}{\rho\varepsilon}\right)+\log\frac{U}{\varepsilon}\right)$

queries to an oracle $\mathcal{O}(\mathcal{G},\mathcal{H})$, where
$\mathcal{G}$ is any first-order chart and $\mathcal{H}$ is either
$\mathcal{H}^{\textup{bit}}$ or $\mathcal{H}^{\textup{dir}}$.

Finally, we provide a kind of transfer result that allows one to transfer
algorithms designed for full-information first-order oracles to the (harder)
setting of a general binary oracle.

######  Theorem 12.

Suppose there exists an algorithm that reports an $\varepsilon$-approximate
solution for instances in $\mathcal{I}_{n,d,\rho,M,R}$ with at most $u$
queries to the full-information first-order oracle based on a first-order
chart $\mathcal{G}$. Then, for any subclass of finitely many instances
$\mathcal{I}\subset\mathcal{I}_{n,d,R,\rho,M,R}$, there exists a query
strategy for this subclass using the general binary oracle based on
$\mathcal{G}$ that reports an $\varepsilon$-approximate solution by making at
most

$O\big{(}\log|\mathcal{I}|+u\big{)}$

queries.

Using the centerpoint-based algorithm from [13, 3], we obtain the following
corollary:

######  Corollary 13.

Given any subclass of finitely many instances
$\mathcal{I}\subset\mathcal{I}_{n,d,R,\rho,M}$ and any first-order chart
$\mathcal{G}$, there exists a query strategy for this subclass using the
general binary oracle based on $\mathcal{G}$ that reports an
$\varepsilon$-approximate solution by making at most

$O\left(\log|\mathcal{I}|+2^{n}\,d\,(n+d)\log\left(\frac{dMR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$

queries. In the (pure continuous) case of $n=0$,
$O\left(\log|\mathcal{I}|+d\log\left(\frac{MR}{\min\\{\rho,1\\}\varepsilon}\right)\right)$
queries suffice.

In particular, when the number of instances under consideration is
$|\mathcal{I}|=O(2^{2^{n}d(n+d)})$, Corollary 13 gives a strictly better upper
bound than Theorem 10. Similarly, for $n=0$, in the case when
$|\mathcal{I}|=O(2^{d})$, we get a better upper bound compared to Theorem 11;
in fact, we beat the lower bound provided by Theorem 9. This demonstrates that
even with exponentially many instances under consideration, the case of finite
instances yields a lower information complexity than the case of infinitely
many instances. We point out that the first-order chart $\mathcal{G}$ must be
known to implement the query strategy in Theorem 12. In contrast, the
algorithms in Theorems 10 and 11 are oblivious of the first order chart, i.e.,
they work with any first order chart.

###  1.2 Discussion and future avenues

The concept of information complexity in continuous convex optimization and
its study go back several decades, and it is considered a fundamental question
in convex optimization. In comparison, much less work on information
complexity has been carried out in the presence of integer constrained
variables. Nevertheless, we believe there are important and challenging
questions that come up in that domain that are worth studying. Further, even
within the context of continuous convex optimization, the notion of
information complexity has almost exclusively focused on the number of full-
information first-order queries. As we hope to illustrate with the results of
this paper, considering other kinds of oracles leads to very interesting
questions at the intersection of mathematical optimization and information
theory. In particular, the study of binary oracles promises to give a more
refined understanding of the fundamental question “How much information about
an optimization instance do we need to be able to solve it with provable
guarantees?”. For instance, establishing any superlinear (in the dimension)
lower bound for the continuous problem with binary oracles, like the one in
Theorem 9, seems to be nontrivial. In fact, the results from [11], on which
Theorem 9 is based, were considered a breakthrough in establishing superlinear
lower bounds on space complexity of convex optimization. Even so, the right
bound is conjectured to be quadratic in the dimension (see Theorem 11) and our
Theorem 9 is far from that at this point. These other oracles also have a
practical motivation. Obtaining exact first-order information may be difficult
or impossible in many practical situations, and one has to work with
approximations of separating hyperplanes and subgradients. The binary oracles
can be viewed as providing these approximations and information complexity
under these oracles becomes important from a practical standpoint.

We thus view the results of this paper as expanding our understanding of
information complexity of optimization in two different dimensions: what role
does the presence of integer variables play and what role does the nature of
the oracle play (with or without integer variables)? For the role of integer
variables, in the pure optimization case Theorem 7 provides a lifting of lower
bound from the continuous case. Allowing for constraints, Corollary 8 brings
the lower bound closer to the best known upper bound on information complexity
based on the classical subgradient oracle. The remaining gap is now simply a
factor linear in the dimension. A conjecture in convex geometry first
articulated in [13, Conjecture 4.1.20] and elaborated upon in [3, 2] would
resolve this and would show that the right bound is essentially equal to the
lower bound we prove in this paper.

Beyond the contributions discussed above, our work also opens up new future
directions for study. We believe the following additional conjectures to be
good catalysts for future research, especially in regard to understanding the
interplay of integer variables and other oracles.

The first conjecture is a generalization of our Theorem 7 to incorporate
constraints as well. This would make this “transfer” tool more powerful, and
would, for example, give Corollary 8 as a special case without appealing to
[2] for the feasibility lower bound.

######  Conjecture 1.

If there exist continuous, constrained convex optimization instances such that
$\ell$ is a lower bound for this family on the information complexity with
respect to an oracle, then for every $n\geq 1$, there exist mixed-integer
instances with $n$ integer variables such that the information complexity of
these mixed-integer instances is lower bounded by $\Omega(2^{n}\cdot\ell)$ for
the same oracle.

Another consequence of resolving this conjecture is that if future research on
the information complexity of continuous convex optimization results in
better/different lower bounds based on feasibility, these would immediately
imply new lower bounds for the mixed-integer case. For instance, we believe
the following conjecture to be true for the mixed-integer convex optimization
problem.

######  Conjecture 2.

There exists a first-order chart $\mathcal{G}$ such that the general binary
oracle based on $\mathcal{G}$ has information complexity
$\Omega\left(2^{n}\Big{(}1+d^{2}\log\left(\frac{MR}{\rho\varepsilon}\right)\Big{)}\right)$.

A version of Conjecture 2 is also stated in the language of “memory-
constrained” algorithms in [16, 11] for the continuous case (see Section 3
below); the way we have stated the conjecture here presents its transfer to
the mixed-integer case.

Analogously, it would be nice to have “transfer” theorems for upper bounds as
well. In the spirit of Theorems 10, 11 and 12, we believe a useful result
would be a theorem that takes upper bound results proved in the full-
information first-order oracle setting and obtains upper bound results in the
general binary oracle setting. A use case of such a result would be the
following: if the upper bound for the general mixed-integer problem with full-
information first-order oracles is improved by resolving the convex geometry
conjecture mentioned above (and we believe the lower bound is correct and the
upper bound is indeed loose), then this would also give better upper bounds
for the general binary oracle setting. Thus, we make the following conjecture.

######  Conjecture 3.

If there exists a query strategy with worst case information complexity
$u(n,d,R,\rho,M,\mathcal{G})$ under the full-information first-order oracle
based on a first-order chart $\mathcal{G}$, then there exists a query strategy
with worst case information complexity bounded by

$u(n,d,R,\rho,M,\mathcal{G})\cdot
O\left((n+d)\log\left(\frac{MR}{\rho\varepsilon}\right)\right)$

under the general binary oracle based on $\mathcal{G}$.

We focus on oracles that use first order information in this paper
(Definitions 4 and 5). Oracles that use “zero-order information” have also
been studied in the literature, beginning with the seminal work of Yudin and
Nemirovski [12]; see [8] for an exposition of how those ideas can be used in
the mixed-integer setting and [5] for an exposition in the nonconvex setting.
Such oracles report function values only for the objective, with no
subgradient information, and only report membership for the constraints, with
no separating hyperplanes. A related oracle is the “value comparison” oracle
that has found many applications. These oracles comprise of questions of the
form “Is $f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})\leq
f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}^{\prime})$?”, with no access
to the subgradients of $f$. Such algorithms are particularly useful in
learning from users’ behaviors, since while a user typically cannot accurately
report its (dis)utility value $f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})$ for an option
$\textstyle\bf z$, it can more reliably compare the values
$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})$ and
$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}}^{\prime})$ of two options;
see [10, 14] and references therein for discussions and algorithms in the
continuous convex case. The mixed-integer setting under the value comparison
oracle has been extensively studied in recent work [4, 6, 7, 15]. The ideas in
this paper can also be adapted to give algorithms for mixed-integer convex
optimization using the comparison oracle, but we do not undertake a deeper
study here. There seems to be scope for future research in this direction,
especially in tying together these different strands of ideas for “zero order
information”.

The remainder of this paper is dedicated to the formal proofs of our main
results discussed above.

##  2 Proof of Theorem 7

The high-level idea for the proof of Theorem 7 is to construct difficult
mixed-integer instances by taking hard instances of the continuous case,
“placing” one of them on each fiber
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}\times\mathbb{R}^{d},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$, and
interpolating between fibers appropriately. We do this in a way such that
effectively one needs to solve the continuous problems obtained by restricting
to each fiber, which leads the $\Omega(2^{n}\ell)$ lower bound from an $\ell$
lower bound on the continuous problems – namely, there will be one difficult
function from the continuous case placed on each of the $2^{n}$ fibers, so if
one can’t do better than solving each of them separately, one ends up with an
$\Omega(2^{n}\ell)$ lower bound. To make this idea work, the interpolation
needs to be done in a way that no query in the full
$[0,1]^{n}\times\mathbb{R}^{d}$ space reveals information about two (or more)
of the continuous functions placed on different fibers, or reveals
significantly more information about a function on a fiber than a query on
that fiber would. For example, we need to ensure that a single query at the
point
$(\frac{1}{2},\ldots,\frac{1}{2},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ for
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}\in R^{d}$ does not reveal
information about multiple functions on different fibers.

###  2.1 Game-theoretic perspective

So far we have described the information complexity of optimization using an
oracle $\mathcal{O}$ over a family of instances $\mathcal{I}$ based on having
an optimization algorithm that in each round $t$ makes a query $q_{t}$ to
$\mathcal{O}$ and receives as answer the result $q_{t}(\widehat{I})$ for the
unknown instance $\hat{I}$ it is trying to optimize. However, for obtaining
lower bounds on the information complexity, it is more helpful to consider the
algorithm as interacting with an _adversary_ for the family of instances under
$\mathcal{O}$, instead of the unknown instance $\hat{I}$. More precisely, at
round $t$, the adversary receives the query $q_{t}$ of the algorithm and
produces, possibly based on all the previous queries $q_{1},\ldots,q_{t-1}$, a
response $r_{t}$. The only requirement is that there must always exist at
least one instance $\bar{I}\in\mathcal{I}$ that is _consistent_ with all of
its responses, namely $r_{t}=q_{t}(\bar{I})$ for all $t$, under the oracle
$\mathcal{O}$ being considered. With each such response, the set of instances
that are consistent with all responses given may change, motivating the
following definition:

######  Definition 14.

Given a class of instances $\mathcal{I}$, an oracle $\mathcal{O}$, and a
transcript of query-response pairs $(q_{1},r_{1}),...,(q_{t},r_{t})$, the set
of surviving instances for $(q_{1},r_{1}),...,(q_{t},r_{t})$ under
$\mathcal{O}$ is

$\\{I\in\mathcal{I}:q_{j}(I)=r_{j}\,\forall\,j\in[t]\\},$

i.e., the set of instances consistent with the responses in the transcript
under the oracle $\mathcal{O}$. When all instances in $\mathcal{I}$ are
unconstrained, let the set of surviving functions be the set of functions
corresponding to the surviving instances.

We say that an adversary Adv is _$\varepsilon$ -hard for $\ell$ rounds_ if for
any algorithm Alg, after $\ell$ rounds there are surviving instances in
$\mathcal{I}$ that do not have a common $\varepsilon$-approximate solution,
i.e., if $q_{1},\ldots,q_{\ell}$ and $r_{1},\ldots,r_{\ell}$ are Alg’s queries
and Adv’s responses, respectively, then there is a collection of instances
$\mathcal{J}\subset\mathcal{I}$ that have no common $\varepsilon$-approximate
solution but such that $r_{t}=q_{t}(I)$ for all $I\in\mathcal{J}$ and
$t=1,\ldots,\ell$. Since the sets of $\varepsilon$-approximate solutions of
instances in $\mathcal{I}_{n,d,R,\rho,M}$ are compact convex sets, this
collection $\mathcal{J}$ of instances may always be taken to be finite111If a
collection of compact sets has empty intersection, then there exists a finite
subcollection that already has empty intersection.. Intuitively, the existence
of such an adversary should imply that no algorithm can reliably report an
$\varepsilon$-approximate solution within $\ell$ iterations, that is,
$\operatorname*{icomp}_{\varepsilon}(\mathcal{O},\mathcal{I})>\ell$. The next
result shows that this adversary-based perspective is indeed equivalent to
information complexity, and may be of independent interest (for a proof see
Appendix A).

######  Lemma 15.

Consider a class of instances $\mathcal{I}$ and an oracle $\mathcal{O}$. Then
$\operatorname*{icomp}_{\varepsilon}(\mathcal{I},\mathcal{O})>\ell$ if and
only if there exists an adversary under $\mathcal{O}$ using $\mathcal{I}$ that
is $\varepsilon$-hard for $\ell$ rounds.

###  2.2 Proof for the full-information first-order oracle

The full proof of Theorem 7 is a bit technical and requires a few conceptual
connections. For a better exposition, we first prove the theorem in the case
that the oracle is the full-information first-order oracle. As $\mathcal{H}$
thus consists of the identity maps, throughout this subsection we will write
oracles using first-order information as $\mathcal{O}(\mathcal{G})$, where
$\mathcal{G}$ is the corresponding first order chart.

Given the assumption of the theorem and the equivalent adversarial perspective
from Lemma 15, assume there is a family of continuous, unconstrained instances
$\mathcal{I}_{cont}\subseteq\mathcal{I}_{0,d,R,\rho,M}$, all with the same
optimal value OPT, and a full-information first-order adversary Adv-Cont for
$\mathcal{I}$ that is $\varepsilon$-hard for $\ell-1$ rounds. Let us use
$\mathcal{F}_{cont}$ to denote the objective functions of the instances
$\mathcal{I}_{cont}$. In the full-information first-order case, queries of an
optimization algorithm consist of points
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}_{1},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{2},\ldots\in\mathbb{R}^{d}$,
and either query the function value or the subgradient. For simplicity, let us
allow the algorithm to query both the function value and subgradient in a
single query, so that the queries become simply
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}_{1},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{2},\ldots\in\mathbb{R}^{d}$
and the responses of an adversary consist of a sequence of consistent function
values and subgradients, namely a sequence
$(v_{1},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{1}),(v_{2},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf
g$}}}_{2}),\ldots\in\mathbb{R}\times\mathbb{R}^{d}$ such that there is some
$f\in\mathcal{F}_{cont}$ satisfying
$v_{t}=f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})$ and
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t}\in\partial
f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})$ for all rounds $t$.

To prove the theorem, we will construct a full-information first-order
adversary Adv-MI for a family of mixed-integer instances over
$\\{0,1\\}^{n}\times\mathbb{R}^{d}$ that is $\varepsilon$-hard for
$2^{n}\ell-1$ rounds. As alluded to before, the very high-level is to place a
copy of the continuous adversary Adv-Cont on each of the continuous fibers
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\times\mathbb{R}^{d}$ for
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$. In fact, we
will work with a slightly modified version of the continuous adversary that is
constructed next.

####  2.2.1 Modifying the continuous adversary Adv-Cont

For the mixed-integer adversary Adv-MI, it will be important to render a fiber
“useless” for the optimization algorithm after it queries (close to) this
fiber too many times, so as to intuitively force it to query (close to) other
fibers, or gain no new information otherwise. This will be done by modifying
the continuous adversary Adv-Cont such that whenever it is probed $\ell$ or
more times, it commits to answering all future queries consistently with a
single function that has optimal value $>\textup{OPT}+\varepsilon$; since our
mixed-integer instances will be constructed to have optimal value OPT,
gathering more information about the function on such fibers will not help the
algorithm solve the mixed-integer problem. To do this, the modified continuous
adversary will also keep track of the set $S$ of surviving functions
(Definition 14) given its responses. More precisely, here are its main
properties.

######  Lemma 16.

There is a family of convex functions $\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
corresponding to instances $\mathcal{I}_{0,d,R,\rho,M}$ of the purely
continuous case, a first-order chart $\mathcal{G}$ and a full-information
first-order adversary Adv-Cont+ that, for any algorithm Alg, maintains a set
of functions $S_{t}\subseteq\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
for every query-response round $t$ with the following properties:

  1. 1.

In every round $t\geq 1$, all functions in $S_{t}$ are consistent with the
responses returned by Adv-Cont+ thus far, under some oracle using first-order
information $\mathcal{O}(\mathcal{G})$.

  2. 2.

In the first $t\leq\ell-1$ rounds, there is a finite collection of functions
in $S_{t}\cap\mathcal{F}_{cont}$ that do not share an
$\varepsilon$-approximate solution. In particular, Adv-Cont+ is still
$\varepsilon$-hard for $\ell-1$ rounds.

  3. 3.

For all rounds $t\geq 1$, $S_{t}$ is closed under taking maxima of finitely
many of its elements, and also contains a function that has minimum value
$>\textup{OPT}+\varepsilon$.

  4. 4.

For rounds $t\geq\ell$, $S_{t}$ contains a single function with minimum value
$>\textup{OPT}+\varepsilon$.

Item 1. means that for rounds $t<\ell$, there exists a full-information first-
order oracle $\mathcal{O}(\mathcal{G})$ such that $S_{t}$ is exactly the set
of surviving functions under $\mathcal{O}(\mathcal{G})$ given the responses
produced by Adv-Cont+ up to round $t$. Hence, we will refer to this $S_{t}$ as
the set of surviving functions maintained by Adv-Cont+ at round $t$. We now
make precise our modification to the continuous adversary Adv-Cont and prove
Lemma 16. As a preliminary, let $\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
denote the closure of $\mathcal{F}_{cont}$ under taking maxima of finitely
many functions, i.e. for any finite collection
$\mathcal{J}\subset\mathcal{F}_{cont}$, $\max_{f\in\mathcal{J}}\\{f\\}\in\hbox
to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$.
Notice these functions are still convex. The following lemma highlights the
key property of $\mathcal{F}_{cont}$ we will make use:

######  Lemma 17.

Let $\mathcal{J}\subset\mathcal{F}$ be a finite set. If $f\in\mathcal{J}$ do
not have a common $\varepsilon$-solution, then the pointwise maximium function
$\max_{f\in\mathcal{J}}\\{f\\}$ has minimum value greater than
$OPT+\varepsilon$.

###### Proof.

Suppose for sake of contradiction that there exists a point $\textstyle\bf z$
such that
$\max_{f\in\mathcal{J}}\\{f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})\\}\leq OPT+\varepsilon$.
Then $f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
z$}}{\mbox{\boldmath$\textstyle\bf z$}}{\mbox{\boldmath$\scriptstyle\bf
z$}}{\mbox{\boldmath$\scriptscriptstyle\bf z$}}})\leq OPT+\varepsilon$ for all
$f\in\mathcal{J}$, which means $\textstyle\bf z$ is an $\varepsilon$-solution
for all $f\in\mathcal{J}$, which contradicts the assumption that they do not
share an $\varepsilon$-solution. ∎

We now formally describe Adv-Cont+, and then prove that it satisfies the
invariants of Lemma 16.

######  Procedure 1.

Adv-Cont+ Initialize set of surviving functions $S_{0}=\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
For each round $t=1,2\ldots$ : 1. Receive query point
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t}\in\mathbb{R}^{d}$ from
the optimization algorithm 2. If $t\leq\ell-1$: Send
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t}$ to the adversary Adv-
Cont, receiving back a value $v_{t}$ and subgradient
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t}$. Obtain $S_{t}$ by
removing from $S_{t-1}$ the functions $f$ that are not consistent with this
response for any first-order chart $\mathcal{G}$, namely where
$f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})\neq v_{t}$ or
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t}\notin\partial
f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})$. Send the response
$(v_{t},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t})$ to the optimization
algorithm. 3. If $t=\ell$: Since Adv-Cont if $\varepsilon$-hard for $\ell-1$
rounds, there is a finite collection of functions
$\\{f_{1},...,f_{k}\\}\subset S_{t-1}\cap\mathcal{F}_{cont}$ that do not share
an $\varepsilon$-solution. Define their pointwise maxima
$f_{\max}=\max\\{f_{1},...,f_{k}\\}$ and set $S_{t+k}=\\{f_{\max}\\}$, for all
$k=0,1,2...$. Set the value $v_{t}$ to be
$f_{\max}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})$ and set
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t}$ to be a subgradient in
$\partial f_{\max}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})$ (consistent with what
the first order chart $\mathcal{G}_{0}$ gives for $f_{1},\ldots,f_{k}$ at
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t}$, if
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t}$ has been queried in an
earlier round), and send the response
$(v_{t},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t})$ to the optimization
algorithm. 4. If $t>\ell$: Let $f_{\max}$ be the only function in $S_{t-1}$.
If ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t}$ was queried in an
earlier round $k$, answer
$(v_{k},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{k})$. Otherwise, set the
value $v_{t}$ to be $f_{\max}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})$ and set
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t}$ to be any subgradient in
$\partial f_{\max}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t})$, and send the response
$(v_{t},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t})$ to the optimization
algorithm.

###### Proof of Lemma 16.

We will proceed by induction on the number of rounds $t$. The lemma clearly
holds for $S_{0}$, so suppose it holds for $S_{t-1}$.

If $t\leq\ell-1$, then $S_{t}$ satisfies Item 1 due to to the update rule in
the procedure for obtaining $S_{t}$, since all functions that are not
consistent with the given response are removed. More precisely, since the
responses given are those produced by Adv-Cont, these functions in $S_{t}$ are
consistent with the responses under exactly the oracle
$\mathcal{O}(\mathcal{G}_{0})$ that Adv-Cont is hard under. $S_{t}$ also
satisfies Item 2 because Adv-Cont is assumed to be $\varepsilon$-hard for
$\ell-1$ rounds, so there exists a finite collection of functions
$\\{f_{1},...,f_{k}\\}\subset\mathcal{F}_{cont}$ with no common
$\varepsilon$-solution that are consistent with all responses given to Adv-
Cont+ by Adv-Cont; thus $S_{t}$ contains them. For Item 3, to show the closure
under taking maxima, we need to argue that if functions $f_{1},...,f_{k}$ were
not removed from $S$, then neither was $\max(f_{1},...,f_{k})$. Since
$f_{1},...,f_{k}$ are convex, then $\partial
f_{j}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\subset\partial\max\\{f_{1},...,f_{k}\\}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ for any $j$ such that
$f_{j}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\max\\{f_{1}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}),...,f_{k}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})\\}$. Hence, if
$f_{1},...,f_{k}$ all have function value $v_{t}$ and subgradient
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t}$ at $\textstyle\bf y$,
then so does $\max\\{f_{1},...,f_{k}\\}$, so $\max\\{f_{1},...,f_{k}\\}$ was
not removed from $S$, as desired. Furthermore, if $f_{1},...,f_{k}$ are taken
to be the functions guaranteed by Item 2, Lemma 17 implies that
$\max\\{f_{1},...,f_{k}\\}$ has optimal value greater than
$\textup{OPT}+\varepsilon$, so since we just showed
$\max\\{f_{1},...,f_{k}\\}\in S_{t}$, the remainder of item 3 follows.

If $t=\ell$, $S_{t}$ contains the single function $f_{\max}$, which has
optimal value greater than $\textup{OPT}+\varepsilon$ by its construction as a
consequence of Lemma 17. Hence, Item 3 follows. To prove item 1, we will use
that $S_{t-1}$ satisfies Item 1, and by Item 3 applied to $S_{t-1}$,
$f_{\max}$ is consistent with the responses returned by the procedure up to
round $t-1$. For round $t$ itself, consistency follows from the definition of
$v_{t}$ and ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t}$, and so $f_{\max}$ is
consistent with all responses given. Item 2 does not apply in this case and
Item 4 is immediate by the construction of $S_{t}:=\\{f_{\max}\\}$.

If $t>\ell$, then $S^{t}=S^{t-1}=\\{f_{\max}\\}$ and it suffices to check that
the response $(v_{t},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}}_{t})$ is compatible with
$f_{\max}$, which follows immediately from the definition of the response.

Hence, Items 1-4 of the lemma follow. It remains to show that Adv-Cont+ is
indeed a well-defined adversary under a full-information first-order oracle.
For rounds $t\leq\ell-1$, this is inherited from Adv-Cont, while for
$t\geq\ell$, this is ensured because if the queried point
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t}$ is the same as
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}_{t^{\prime}}$ for some round
$t^{\prime}<t$, Adv-Cont+ provides the same response in round $t$ as in round
$t^{\prime}$. Thus, there is indeed a first-order chart $\mathcal{G}$ (derived
from the first order map $\mathcal{G}_{0}$ for Adv-Cont) such that Adv-Cont+
is an adversary under the corresponding full-information first-order oracle
$\mathcal{O}(\mathcal{G})$.∎

####  2.2.2 Constructing the mixed-integer adversary Adv-MI

We now construct the family $\mathcal{F}_{MI}$ of functions over
$\mathbb{R}^{n}\times\mathbb{R}^{d}$ used to transfer the lower bound to the
mixed-integer setting, along with the adversary Adv-MI for that family. We
call functions over $\mathbb{R}^{n}\times\mathbb{R}^{d}$ full-dimensional to
distinguish them from the functions over $\mathbb{R}^{d}$, the continuous part
of the problem. As indicated previously, these full-dimensional functions
$\psi$ in $\mathcal{F}_{MI}$ will be obtained by considering combinations of
selecting one function $f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}$ from $\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
for each of the mixed-integer fibers
$\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}\times\mathbb{R}^{d},\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\in\\{0,1\\}^{n}$, letting
$\psi$ equal the appropriate function selected over each corresponding fiber,
and applying an interpolation scheme between the fibers. This interpolation is
illustrated in Figure 1 and described in detail later in this section.

For the behavior of Adv-MI, we instantiate a copy of the modified continuous
adversary Adv-Cont+ on each fiber. Whenever the optimization algorithm queries
a point $(\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ on a fiber, we send
$\textstyle\bf y$ to the continuous adversary on the fiber and report back the
response $(v,{\mathchoice{\mbox{\boldmath$\displaystyle\bf
g$}}{\mbox{\boldmath$\textstyle\bf g$}}{\mbox{\boldmath$\scriptstyle\bf
g$}}{\mbox{\boldmath$\scriptscriptstyle\bf g$}}})$ received, although
$\textstyle\bf g$ needs to be appropriately lifted to the full
$\mathbb{R}^{n}\times\mathbb{R}^{d}$ space to be consistent with the way we
interpolate the functions between the fibers. If the optimization algorithm
only probes on these fibers, then it is intuitive that such an adversary would
be $\varepsilon$-hard for $2^{n}\ell-1$ rounds: informally, up to this round,
at least one of the $2^{n}$ fibers that has received no more than $\ell-1$
queries, so using the hardness of Adv-Cont+ (Item 2 of Lemma 16) we can obtain
full-dimensional functions that do not share an $\varepsilon$-approximate
solution, which confirm the desired $\varepsilon$-hardness of the mixed
integer adversary Adv-MI.

The crucial element is how to deal with queries on points outside of the
mixed-integer fibers. If such queries provide the algorithm with more
information about the full-dimensional functions $\mathcal{F}_{MI}$ than
queries on the fibers do, then we may not have full-dimensional functions with
no common $\varepsilon$-approximate solution surviving for $2^{n}\ell-1$
rounds. To handle this issue, the interpolation used to define the full-
dimensional functions $\psi$ guarantees that its behavior on a fractional
point $(\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\notin\\{0,1\\}^{n}\times\mathbb{R}^{d}$ is completely determined by the
value of the function $f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ from $\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
selected for the fiber $\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\times\mathbb{R}^{d}$, where
$\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\in\\{0,1\\}^{n}$ is the
closest 0/1 point to $\tilde{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$. Thus, Adv-MI can also
answer such a query at a fractional point by making a query to the appropriate
continuous adversary Adv-Cont+ on
$\left\\{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}\right\\}\times\mathbb{R}^{d}$, and the hardness of the latter can still
be leveraged.

We now formally define the functions $\mathcal{F}_{MI}$ and the adversary Adv-
MI.

Figure 1: (Left) Illustration of two possible functions $f_{0},f_{1}\in\hbox
to0.0pt{\hskip
0.875pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
(blue and red) of the continuous adversary Adv-Cont+, for $d=1$. (Right)
Illustration of the function $\psi_{(f_{0},f_{1})}$ for the mixed-integer
adversary Adv-MI obtained by placing the functions $f_{0}$ and $f_{1}$ on the
fibers $\\{0\\}\times\mathbb{R}$ and $\\{1\\}\times\mathbb{R}$ and
interpolating appropriately between the fibers.

##### Construction of the functions $\mathcal{F}_{MI}$.

For a 0/1 point $\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\in\\{0,1\\}^{n}$ and a
function $f\in\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
in $\mathbb{R}^{d}$, we first define its (convex) extension to the full-
dimensional space $\mathbb{R}^{n+d}$ as

$\displaystyle\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\max\Big{\\{}f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})+\langle\mathbf{M}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}\rangle~{},~{}\textup{OPT}\Big{\\}},$ (2)

with $\mathbf{M}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}:=3MR\cdot
sgn(\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}-0.5\cdot\mathbf{1}),$ where
$sgn$ denotes the sign function. This construction effectively places $f$
along the $\textstyle\bf y$ space at the fiber
$\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$ and extends it in each of
the $\textstyle\bf x$ variables via a linear function with slope $\pm 3MR$, in
a way that it decreases the value as it moves into the unit cube, or
equivalently, away from $\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$; it then truncates the
final value to being at least OPT; see Figure 2 for an illustration. We note
for later use that wherever the extension is not truncated by OPT, a
subgradient is given by appending the vector
$\mathbf{M}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}$ to a subgradient of $f$,
and otherwise the all zeroes vector is a subgradient. More precisely, we have

$\displaystyle\partial\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\supseteq\left\\{\begin{array}[]{ll}\\{\mathbf{M}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}\\}\times\partial
f({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})&\textrm{, if
$\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})>\textup{OPT}$}\\\
\\{\bm{0}\\}&\textrm{, otherwise.}\end{array}\right.$ (5)

Figure 2: An example of a possible function from $f\in\mathcal{F}_{cont}$
(left) together with an illustration of its truncated extension
$\hat{f}_{0}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ (right) as constructed in
(2).

Given a collection
$\texttt{F}=(f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}})_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}$ with one function
$f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}\in\hbox to0.0pt{\hskip
1.52779pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$\mathcal{F}$}}_{cont}$
for each 0/1 point $\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$, we combine them into the
convex function

$\displaystyle\psi_{\texttt{F}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}):=\max_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}\in\\{0,1\\}^{n}}\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}),$ (6)

where we abuse notation slightly and write the convex extension
$(\widehat{f_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}})_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$ as simply
$\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}$ to simplify the notation.
As mentioned above, a crucial property of these functions is that their
behavior between the fibers is determined by the behavior on the closest
fiber. Intuitively, the slope $\pm 3MR$ guarantees that as the $\textstyle\bf
x$ argument moves away from the base fiber
$\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$ of each extended function
$\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}$,
$\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}$ decreases rapidly enough
so that the maximum in (6) is always achieved by the extended function at the
closest fiber to $\textstyle\bf x$. Figure 1 illustrates this, where one can
see that both functions placed on the fibers get fully truncated in between
the fibers. To make this precise, let
$r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}):[0,1]^{n}\rightarrow\\{0,1\\}^{n}$ map any $\textstyle\bf x$ in the box
to its closest 0/1 point in $\ell_{\infty}$-norm, that is
$r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}):=\operatorname*{argmin}_{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime}}\\{\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}-{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime}\|_{\infty}:{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}^{\prime}\in\\{0,1\\}^{n}\\}$.

######  Lemma 18.

For every collection
$\texttt{F}=(f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}})_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}}$, for every point
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})\in[0,1]^{n}\times[-R,R]^{d}$
we have

$\displaystyle\psi_{\texttt{F}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\hat{f}_{r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}})}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}),~{}~{}~{}~{}\textrm{ and
}~{}~{}~{}~{}\partial\psi_{\texttt{F}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\partial\hat{f}_{r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}})}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$

###### Proof.

Define $B_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}:=\left\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime}\in\mathbb{R}^{n}:\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}\|_{\infty}\leq\frac{1}{3}\right\\}$ for every
$\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$. Consider an
arbitrary $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\in[0,1]^{n}\times[-R,R]^{d}$.

Case 1: ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\not\in
B_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$ for any
$\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$. This
implies that for every $\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$, we have

$\displaystyle f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})+\langle\mathbf{M}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\rangle$
$\displaystyle=f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})+\sum_{j\in[n]}3MR\cdot
sgn(\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}_{j}-0.5)\cdot({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}_{j}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}_{j})$ $\displaystyle\leq
f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})-3MR\cdot\max_{j\in[n]}|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}_{j}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}_{j}|<f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})-MR\leq\textup{OPT},$

Thus, $\hat{f}_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})=\textup{OPT}$ for all
$\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$. As a
result, $\psi_{F}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\textup{OPT}=\hat{f}_{r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}})}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$.

Moreover, since $f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})+\langle\mathbf{M}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\rangle<\textup{OPT}$ for all
$\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$, there
exists a neighborhood of $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ such that for any point
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})$ in the
neighborhood, it holds that
$f_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{\prime})+\langle\mathbf{M}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\rangle<\textup{OPT}$, and
$\hat{f}_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})=\textup{OPT}$ for
all $\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$. As a
result, $\partial\hat{f}_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
0$}}{\mbox{\boldmath$\textstyle\bf 0$}}{\mbox{\boldmath$\scriptstyle\bf
0$}}{\mbox{\boldmath$\scriptscriptstyle\bf 0$}}}\\}$ for all
$\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$, and
$\partial\psi_{F}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\\{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
0$}}{\mbox{\boldmath$\textstyle\bf 0$}}{\mbox{\boldmath$\scriptstyle\bf
0$}}{\mbox{\boldmath$\scriptscriptstyle\bf 0$}}}\\}.$

Case 2: ${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in
B_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$ for some
$\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$. In this
case, $r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}})=\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}$. This is because for any
$\tilde{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}\in\\{0,1\\}^{n}\backslash\\{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\\}$, we have that

$\displaystyle\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}-\tilde{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}\|_{\infty}\geq\frac{2}{3}>\frac{1}{3}\geq\|{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}-\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}\|_{\infty}.$ (7)

It is also true that
$\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})\geq\textup{OPT}=\hat{f}_{\tilde{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ for any
$\tilde{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}\neq\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$, which holds due to the
result from Case 1.

Moreover, the arguments from Case 1 and (7) imply that there exists a
neighborhood of $({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}})$ such that for any point
$({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})$ in the
neighborhood, it holds that $r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime})=r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}})=\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$, and
$\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{\prime})\geq\textup{OPT}=\hat{f}_{\tilde{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})$ for all
$\tilde{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}\neq\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}}$. As a result,
$\psi_{F}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{\prime})=\hat{f}_{\bar{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{\prime})=\hat{f}_{r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime})}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}}^{\prime})=\hat{f}_{r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}})}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}^{\prime},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}^{\prime})$ and
$\partial\psi_{F}(x,y)=\partial\hat{f}_{\bar{{\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}}}}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf
y$}}})=\partial\hat{f}_{r({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}})}({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf
x$}}},{\mathchoice{\mbox{\boldmath$\displaystyle\bf
y$}}{\mbox{\boldmath$\textstyle\bf y$}}{\mbox{\boldmath$\scriptstyle\bf
y$}}{\mbox{\boldmath$\scriptscriptstyle\bf y$}}}).$ ∎

##### Construction of the mixed-integer adversary Adv-MI.

We finally describe Adv-MI in Procedure 2. Its main property is captured in
the following invariant.

######  Procedure 2.

Adv-MI Instantiate a copy of Adv-Cont+ on each fiber
${\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}}\in\\{0,1\\}^{n}$, and let
$S({\mathchoice{\mbox{\boldmath$\displaystyle\bf
x$}}{\mbox{\boldmath$\textstyle\bf x$}}{\mbox{\boldmath$\scriptstyle\bf
x$}}{\mbox{\boldmath$\scriptscriptstyle\bf x$}}})$ denote the set of surviving
functions maintained in every round by this copy, initialized to