# Hardness of Maximum Likelihood Learning of DPPs

Elena Grigorescu Purdue University<EMAIL_ADDRESS>Brendan Juba Washington
University in St. Louis<EMAIL_ADDRESS>Karl Wimmer Duquesne University,
<EMAIL_ADDRESS>Ning Xie Florida International University<EMAIL_ADDRESS>
###### Abstract

Determinantal Point Processes (DPPs) are a widely used probabilistic model for
negatively correlated sets. DPPs have been successfully employed in Machine
Learning applications to select a diverse, yet representative subset of data.
In these applications, the parameters of the DPP need to be fitted to match
the data; typically, we seek a set of parameters that maximize the likelihood
of the data. The algorithms used for this task to date either optimize over a
limited family of DPPs, or use local improvement heuristics that do not
provide theoretical guarantees of optimality.

It is natural to ask if there exist efficient algorithms for finding a maximum
likelihood DPP model for a given data set. In seminal work on DPPs in Machine
Learning, Kulesza conjectured in his PhD Thesis (2011) that the problem is NP-
complete. The lack of a formal proof prompted Brunel, Moitra, Rigollet and
Urschel (COLT 2017) to conjecture that, in opposition to Kulesza’s conjecture,
there exists a polynomial-time algorithm for computing a maximum-likelihood
DPP. They also presented some preliminary evidence supporting their
conjecture.

In this work we prove Kulesza’s conjecture. In fact, we prove the following
stronger hardness of approximation result: even computing a
$\left(1-O(\frac{1}{\log^{9}{N}})\right)$-approximation to the maximum log-
likelihood of a DPP on a ground set of $N$ elements is NP-complete. At the
same time, we also obtain the first polynomial-time algorithm that achieves a
nontrivial worst-case approximation to the optimal log-likelihood: the
approximation factor is $\frac{1}{(1+o(1))\log{m}}$ unconditionally (for data
sets that consist of $m$ subsets), and can be improved to
$1-\frac{1+o(1)}{\log N}$ if all $N$ elements appear in a $O(1/N)$-fraction of
the subsets.

In terms of techniques, we reduce approximating the maximum log-likelihood of
DPPs on a data set to solving a gap instance of a “vector coloring" problem on
a hypergraph. Such a hypergraph is built on a bounded-degree graph
construction of Bogdanov, Obata and Trevisan (FOCS 2002), and is further
enhanced by the strong expanders of Alon and Capalbo (FOCS 2007) to serve our
purposes.

###### Contents

  1. 1 Introduction
    1. 1.1 Our results
    2. 1.2 Our approach and techniques
    3. 1.3 Related work
    4. 1.4 Organization of the paper
  2. 2 Maximum likelihood learning of DPP and our main hardness result
    1. 2.1 Preliminaries
    2. 2.2 Maximum Likelihood Learning of DPPs
    3. 2.3 Proof of the Main Theorem: an outline
  3. 3 Robustness of very strong expanders – Proof of Lemma 2
    1. 3.1 BOT graphs
    2. 3.2 Properties of BOT graph and proof of Lemma 2
  4. 4 Structure of max-likelihood solutions – Proof of Theorem 5
    1. 4.1 The $L$-ensemble case
    2. 4.2 Perturbing the training example distribution
      1. 4.2.1 Proof of inequality (7)
      2. 4.2.2 Proof of inequality (8)
      3. 4.2.3 Proof of inequality (9)
      4. 4.2.4 Proof of inequality (10)
      5. 4.2.5 Putting everything together
    3. 4.3 An optimal kernel as a limiting matrix
  5. 5 An optimal kernel for $3$-colorable graphs – Proof of Theorem 6
  6. 6 Good rank-$3$ kernels exist – Proof of Theorem 7
    1. 6.1 Proof overview
    2. 6.2 Finding a good dimension-$3$ subspace
    3. 6.3 Bounding the number of “bad” vertices
    4. 6.4 Assigning projections for “bad vectors”
    5. 6.5 Bounding the likelihood function of the new kernel
    6. 6.6 Bounding the scaling factor $\beta$
  7. 7 Putting it all together – Proof of Theorem 8
  8. 8 The approximation algorithm
  9. 9 Discussion and open problems

##  1 Introduction

Determinantal Point Processes (DPPs) are a family of probability distributions
on sets that feature repulsion among elements in the ground set. Roughly
speaking, a DPP is a distribution over all $2^{N}$ subsets of
$\\{1,\ldots,N\\}$ defined by a positive semidefinite (PSD) $N\times N$ matrix
$K$ (called a _marginal kernel_ or _correlation kernel_) whose eigenvalues all
lie in $[0,1]$, such that, for any $S\subseteq\\{1,\ldots,N\\}$, random
subsets $\boldsymbol{X}$ drawn according to the distribution satisfy
$\Pr[S\subseteq\boldsymbol{X}]=\det(K_{S})$, where $K_{S}$ is the principal
submatrix of $K$ indexed by $S$.

DPPs were first proposed in quantum statistical physics to model fermion
systems in thermal equilibrium [Mac75], but they also arise naturally in
diverse fields such as random matrix theory, probability theory, number
theory, random spanning trees and non-intersecting paths [Dys62, BP93, RS96,
Sos00]. After the seminal work of [KT12], DPPs have attracted a flurry of
attention from the machine learning community due to their computational
tractability and excellent capability at producing diverse but representative
subsets, and subsequently fast algorithms have been developed for sampling
from DPPs [HKPV06, KT10, RK15, LJS16a, LJS16b, AGR16, DCV19, LGD20].
Furthermore, DPPs have since found a vast variety of applications throughout
machine learning and data analysis, including text and image search,
segmentation and summarization [LB12, KT12, ZA12, GKT12b, GKT12a, YFZ+16,
KT11a, AFAT14, LCYO16, AKFT13, CGGS15, AFT13], signal processing [XO16, KSG08,
GKS05], clustering [ZA12, Kan13, SG13], recommendation systems [ZKL+10],
revenue maximization [DRS09], multi-agent reinforcement learning [OR19,
YWW+20], modeling neural spikes [SZA13], sketching for linear regression
[DW18, DLM20], low-rank approximation [GS12], and likely many more.

##### Maximum likelihood estimation.

Many of these applications require inferring a set of parameters for a DPP
capturing a given data set. As a DPP specifies a probability distribution,
hence in contrast to supervised learning problems, the quality of a DPP cannot
be estimated by the “error rate” of the model’s predictions. The standard
approach to estimate a DPP from data is to find parameters that maximize the
_likelihood_ of the given data set being produced by a sample from the DPP
[KT12], i.e., the probability density of the observed data in the joint
distribution. When the samples are identically and independently chosen from
the DPP, the likelihood is the product of the probability densities the DPP
assigns to the sampled subsets. The goal of the maximum likelihood estimator
(MLE) method is to find a kernel matrix that maximizes the likelihood of the
data set. [BMRU17b] showed that the maximum likelihood estimate indeed
converges to the true kernel at a polynomial rate. In general, maximizing the
likelihood of a DPP gives rise to a non-convex optimization problem, and has
been approached with heuristics such as expectation maximization [GKFT14],
fixed point algorithms [MS15], and MCMC [AFAT14]. In the continuous case, the
problem has been studied under strong parametric assumptions [LMR15], or
smoothness assumptions [Bar13].

###  1.1 Our results

In spite of the wide applications of DPPs and the central role of the learning
step, no efficient algorithms are known to find a maximum likelihood DPP.
Instead, as mentioned above, two families of algorithms are known: one seeks
to learn an optimal DPP within certain parameterized families of DPP
structures [KT12, AFAT14, GPK16, MS16, GPK17, UBMR17, DB18], while the other
invokes heuristics to maximize the likelihood in an unconstrained search over
the parameter space [KT11b, GKFT14, AFAT14, MS15]. Neither of these approaches
provides any guarantees for how close the likelihood of the obtained
parameters are to the maximum over all DPPs.

Indeed, Kulesza [KT11b, Kul12] conjectured over a decade ago that the problem
of finding a set of parameters is NP-hard, but indicated that he was unable to
formally establish a reduction: his thesis includes a sketch of a reduction
from Exact-3-cover to a related problem111Technically, the reduction proposed
by Kulesza targets a variant of the maximum-likelihood DPP learning problem in
which the instance specifies a set of positive-semidefinite matrices along
with the data, and the objective is to find a DPP kernel in the cone of the
given matrices that maximizes the likelihood. with numerical evidence
suggesting its correctness but without a formal proof. The subsequent
literature adopted this belief, despite the lack of a solid theoretical
foundation.

In this work, we resolve this question by proving Kulesza’s conjecture:
computing maximum likelihood DPP kernels is indeed NP-hard. In fact, we
establish a stronger, gapped hardness result: even approximating the maximum
likelihood is NP-hard.

######  Theorem 1 (Informal Statement of the Main Theorem).

There is a ground set of size $N$ such that it is NP-hard to
$\left(1-O(\frac{1}{\log^{9}{N}})\right)$-approximate the maximum DPP log-
likelihood value of a sample set.

######  Remark 1.

Some comments on our (somewhat confusing) convention of approximation factors
are in place. Since log likelihood functions are always negative real numbers
and it is a bit awkward to work with optimizing negative quantities, we
therefore add a minus sign at the front of our definition of log likelihood
functions. Consequently, we _minimize_ log likelihood functions instead of
maximizing them. On the other hand, as our hard learning instances are reduced
from Max-$3$SAT and $3$-Coloring, to be consistent with hardness results in
the literature on these problems, we use $\alpha$-approximation (where
$0<\alpha<1$, for maximization problems) in the statements of our hardness and
algorithmic results. Note that here “$\alpha$-approximation” actually means
that the log likelihood function (in our definition and ought to be minimized)
output by an algorithm is at most $\frac{1}{\alpha}$ time the optimal log
likelihood function.

Therefore, the difficulty of learning a DPP is not tied to any particular
representation of the marginal kernel, as in fact estimating the maximum
likelihood _value_ itself is NP-hard. Note, however, that many problems in
learning are hard merely due to the difficulty of finding a specific
representation [PV88], which is not the case for our problem.

The NP-hardness of maximum likelihood learning naturally raises the question
of whether any nontrivial approximation is possible. We show that such an
approximation is possible: we present a simple, polynomial-time algorithm
obtaining a $\frac{1}{(1+o(1))\log{m}}$-approximation for a data set with $m$
subsets.

######  Theorem 2 (Informal Statement of the Approximation Algorithm).

There is a polynomial-time approximation algorithm achieving the following: on
an input data set consisting of $m$ subsets over a ground set of size $N$, it
returns a kernel that $\frac{1}{(1+o(1))\log{m}}$-approximates the maximum log
likelihood. Moreover, if every element in the ground set appears in at most
$O(1/N)$-fraction of the subsets, the kernel achieves a
$(1-\frac{1+o(1)}{\log{N}})$-approximation to the maximum log likelihood.

We stress that in contrast to the prior work on learning DPP kernels with
guarantees [UBMR17], our algorithm does not rely on the data being produced by
a DPP to have a “cycle basis” of short cycles or large nonzero entries. We
obtain an approximation to the optimal likelihood for any data set. Although a
$\frac{1}{(1+o(1))\log{m}}$-approximation is weak, when every element appears
in relatively few subsets (which is common in practice), our algorithm is much
better: the actual approximation factor is $1-\frac{1}{\log(m/a_{\max})}$,
where $a_{\max}/m$ is the fraction of the data subsets containing the most
frequent element in the ground set. Hence, if all elements appear in at most a
$\sim 1/N$-fraction of the subsets, we obtain a $(1-\frac{1+o(1)}{\log
N})$-approximation to the log likelihood. Although we don’t expect our
algorithm to obtain substantially better likelihood than various heuristics
employed in practice, it may nevertheless serve as a benchmark to estimate how
close to optimal these solutions are. Moreover, the family of instances
constructed in our reduction indeed satisfies this condition; therefore, to
improve the hardness of approximation bound beyond $1-\frac{1+o(1)}{\log N}$,
the hard instance of data set must have some elements appearing in
$\omega(1/N)$-fraction of the subsets.

###  1.2 Our approach and techniques

We show that it is NP-hard to approximate the optimal DPP likelihood function
by reducing from a coloring problem, rather than from Exact-3-Cover, which was
Kulesza’s [Kul12] initial approach.

We begin with some intuition leading to a notion of vector coloring that we
use in the reduction. As any marginal kernel $K\in\mathbb{R}^{N\times N}$ is
positive semidefinite, it can be factored as $K=Q^{\top}Q$, where
$Q\in\mathbb{R}^{k\times N}$, $Q^{\top}$ stands for the transpose of $M$, and
$k$ is called the _dimension_ of the kernel. If we denote the column vectors
of $Q$ by $q_{1},\ldots,q_{N}$, each $q_{i}\in\mathbb{R}^{k}$, then one can
think of these $q_{i}$’s as providing an embedding of the elements in
$\\{1,\ldots,N\\}$ into the space $\mathbb{R}^{k}$, and the embedding vectors
capture similarities among elements. Specifically, the preference of DPPs for
diverse subsets, roughly speaking, stems from the following fact: if a subset
$S$ includes elements that are similar, the submatrix $K_{S}$ would contain
columns that are nearly co-linear embedding vectors, and hence its determinant
(and correspondingly, the probability that $S$ is the random subset generated
by the marginal kernel $K$) is close to zero.222Recall that, since $K$ and
hence $K_{S}$ are Gram matrices, $\det(K_{S})$ is equal to the square of the
volume of the parallelepiped spanned by the embedding vectors of elements in
$S$.

Consider, for simplicity, a training set that consists of a collection of
subsets of $\\{1,\ldots,N\\}$, each of size $r$ where $r$ is a constant. What
can we say about a maximum-likelihood DPP kernel for such a data set? Ideally,
the embedding vectors should encode an “$r$-vector-coloring” of the elements
in the following sense. Each of the $r$ colors is represented by a unit vector
(after normalizations) in an orthonormal basis; to maximize the likelihood
function, every subset $S=\\{i_{1},\ldots,i_{r}\\}$ that appears in the
training set corresponds to a “rainbow coloring” of the embedding vectors
$\\{q_{i_{1}},\ldots,q_{i_{r}}\\}$ (“rainbow coloring” means that the $r$
embedding vectors are all colored differently), while for the $r$-subsets that
do not appear in the training set, we would like as many as possible of them
to contain some repeated color.333Implicitly, we would also like to have $k=r$
so that no non-degenerate parallelepiped of dimension higher than $r$ exists,
as the number of size-$(r+1)$ or larger subsets dominates those of size-$r$
subsets; see Conjecture 1 below.

Thus, it is natural to attempt a reduction from Graph $r$-Coloring to Maximum
Likelihood Learning of DPP. However, if we view each edge as a $2$-subset,
then we fail to get a hard problem to begin with, since graph $2$-coloring is
easy. We overcome this by “lifting” each edge to a size-$3$ subset (or
equivalently, we transform a graph into a $3$-uniform hypergraph, and view all
its hyperedges as size-$3$ subsets in the data set) so that we can still work
with $3$-Colorability. On an input graph $G=(V,E)$, our goal would be to show
the following: if $G$ is $3$-colorable, then there is a DPP kernel whose
likelihood is large (completeness); if $G$ is not $3$-colorable, then the
likelihood of _every_ DPP kernel is small (soundness).

As the column vectors of DPP kernels are in Euclidean spaces instead of
discrete ones, the continuous variant of coloring that works for us is the
notion of _vector coloring_ of graphs. A _vector coloring_ of a graph
$G=(V,E)$ is a mapping from vertices in $V$ to points (vectors) in some low-
dimensional metric space $\mathcal{M}$, such that the presence or absence of
edges between any pair of vertices prescribes the value of the inner product
between the two corresponding vectors. (See Section 1.3.) Our problem differs
from this one in two important ways: first, we do not care too much about the
minimum dimension of the Euclidean space in which a vector representation
exists; second, which is more subtle and will be elaborated below, we need a
“gapped” reduction.

There are several technical challenges we need to address in order to make the
reduction from $3$-Colorability work. First, we need to understand the
structure of kernels that achieve maximum likelihood values. To this end, by
an extension of an argument of [BMRU17a], we prove that the square of the norm
of every embedding vector is equal to the empirical frequency of the element.
Furthermore, via a projection argument, we show that there always exists a
good _rank- $3$_ DPP kernel without giving up too much likelihood. This
greatly simplifies the analysis of the gadgets employed in our reduction.

Secondly, instead of a “decision” hardness result on vector coloring of
hypergraphs (e.g. it is NP-hard to decide if there is a $3$-dimensional
orthogonal representation for the elements in the set that satisfies certain
orthogonality conditions), we rather require a “ _gapped_ ” reduction,
obtaining something like “starting with a Yes instance, we end up with a set
of embedding vectors so that the _average_ volume of the $3$-dimensional
parallelepipeds spanned by these embedding vectors of hyperedges is large;
starting with a No instance, then every possible embedding scheme will make
the _average_ volume of those parallelepipeds small”. Namely, in an
“averaging” sense, we need the resulting hypergraph transformed from a No
instance to be “far from” $3$-vector colorable. Accordingly, the No instance
of $3$-Colorability should have the property that, even after removing a small
fraction of the edges, it is still not $3$-colorable. On the other hand, the
strongest known hardness results [KLS00, GK04, DMR09, BG16] on coloring
$3$-colorable graphs are based on dense graphs; the requirement on No instance
mentioned above, when applied to dense graphs, would make the problem fall
into the regime of property testing, which is unfortunately known to be
computationally easy [GGR98].

We circumvent this obstacle by adapting a _sparse graph_ construction of
Bogdanov, Obata and Trevisan [BOT02] (referred to as BOT graph henceforth).
Based on the hardness of approximating Max-$3$SAT, BOT graph was used in
[BOT02] to prove query lower bound for testing $3$-Colorability in the
bounded-degree model. We fix some minor mistakes in the construction and
analysis of [BOT02], further enhance the robustness of BOT graph with the
strong expander construction of Alon and Capalbo [AC07]. These modifications
allow us to show that, for some absolute constant $\delta$, we can decode a
$3$-coloring of the vertices which satisfies at least $(1-\delta)$-fraction of
the edges in the original BOT graph, as long as the DPP log likelihood of a
training set constructed from the edges of the BOT graph were close enough to
the maximum value of a $3$-colorable graph. An overview of the reduction
sequence is illustrated in Figure 1.

$3$-CNF formulaMax-$3$SATBOT graph$3$-ColoringBOT hypergraphvector-coloringDPP
learnerMLE-DPP-kernel Figure 1: High level overview of our reductions.

##### Algorithmic results.

For the upper bound, we obtain an approximation algorithm by using some of the
properties required for the analysis of our reduction. The algorithm itself is
very simple: given a data set $X_{1},X_{2},\ldots,X_{m}$, output the DPP
marginal kernel given by the $N\times N$ diagonal matrix $K$ such that
$K_{ii}=|\\{j:X_{j}\ni i\\}|/m$ for all $i$ in the ground set. In other words,
the diagonal entries of the marginal kernel are just the empirical
probabilities of elements in the data set. Hadamard’s inequality gives a lower
bound on the optimal likelihood that is similar to the likelihood of the
diagonal kernel; if the elements all appear in at most a $a_{\max}/m$-fraction
of the subsets, the ratio $\frac{\text{log likelihood output by the
algorithm}}{\text{optimal log likelihood}}$ is at most
$1+\frac{\log((1-\frac{a_{\max}}{m})^{1-a_{\max}/m})}{\log((\frac{a_{\max}}{m})^{a_{\max}/m})}\approx
1+\frac{1}{\log N}$ when $a_{\max}/m$ is $O(1/N)$. For an unconditional upper
bound, observe that elements in all $m$ sets should occur with probability $1$
in the maximum likelihood DPP (and thus may be disregarded without loss of
generality), hence we may plug $a_{max}=m-1$ into the aforementioned bound and
obtain a $(1+o(1))\log{m}$ upper bound on the ratio.

###  1.3 Related work

##### Learning DPPs.

As mentioned earlier, [UBMR17] in particular proposed an algorithm for
recovering a DPP’s kernel up to similarity, which is efficient when (i) the
graph defined by interpreting the kernel as a weighted adjacency matrix has a
“cycle basis” of cycles of bounded length and (ii) the nonzero entries are not
too small. Furthermore, they gave a lower bound on the sample complexity of
estimating the DPP kernel, showing that it indeed depends similarly on these
quantities. Thus, when there is enough data to permit exact recovery of the
kernel, this algorithm will perform well, but otherwise there is no guarantee
that the algorithm produces a kernel for a DPP with likelihood close to
maximum.

In a companion paper, [BMRU17a] also studied the rate of estimation obtained
by the maximum likelihood kernel. Again, they determined classes of DPPs for
which it is efficient (or not). Moreover, they identified an exponential
number of saddle points, and conjectured that these are the only critical
points; they further suggested that a proof of this conjecture might lead to
an efficient algorithm for computing a maximum likelihood kernel. But, they
did not actually provide algorithms for computing the likelihood or the kernel
itself.

Starting with the pioneering work of [KT11b], various empirical learning
algorithms have been proposed for learning discrete DPPs, such as Bayesian
methods [AFAT14], expectation-maximization (EM) algorithms [GKFT14], fixed-
point iteration [MS15], learning non-symmetric DPPs [GBDK19], learning with
negative sampling [MGS19], and minimizing Wasserstein distance [AGR+20].
However, none of these algorithms has theoretical guarantees. Efficient
learning algorithms have also been designed for restricted classes of DPPs
[MS16, GPK17, DB18, ORG+18]. A related problem, namely testing DPPs, recently
has been investigated by [GAJ20].

We note that in contrast to the problem of learning the DPP kernel from a data
set as considered here, the problem of computing the mode (“MAP estimate”) of
a DPP given by its kernel has long been known to be NP-complete [KLQ95,
CMI09]. The inapproximability for this problem was recently strengthened
substantially by [Ohs21].

##### Vector coloring problems.

The notion of _orthogonal representation_ (in which there is an edge between
two vertices if and only if the two corresponding representation vectors are
orthogonal444Some authors, for example [Lov79], define orthogonal
representation by mandating the vectors of two non-adjacent vertices to be
orthogonal.) was introduced by [Lov79], and was used in the definition of the
famous Lovász’s $\vartheta$ function, which has been employed to bound
quantities such as Shannon capacity, the clique numbers or the chromatic
numbers of graphs. More generally, a _geometric representation_ of a graph is
a mapping from vertices in $V$ to points in a metric space $\mathcal{M}$, such
that two vertices are connected by an edge if and only if the distance between
the two corresponding points satisfies certain condition. For example,
orthogonal representation is a special case of the _unit-distance_ graph where
(in the framework of geometric representation) the underlying metric space is
the unit sphere (with distance $1$ replaced by sphere distance $\pi/2$).
Geometric representation of graphs is a well-studied subject, revealing many
surprising connections between parameters (e.g. dimension) of geometric
representations and properties of the original graph, such as chromatic
number, connectivity, excluded subgraphs, tree width, planarity, etc; see e.g.
[Lov79, LSS89, PP89, KMS98, LV99, LSS00, HPS+10] and the recent textbook
[Lov19].

##### Matrix completion problem.

Geometric representations of graphs are intimated connected to another class
of problems, _matrix completion problems_. For instance, the celebrated result
of [Pee96], showing NP-hardness of deciding whether a $3$-dimensional
orthogonal representation over a finite field exists for a graph, was obtained
through reducing $3$-Colorability to a low-rank matrix completion problem.
Matrix completion studies under what conditions a partially specified matrix
can be completed into one which belongs to a certain class of matrices, such
as low-rank matrices, semidefinite matrices, Euclidean distance matrices, etc.
See e.g. [Lau09] for an overview of the important results in this area.
Interestingly, a recent work of [HMRW14], which proved the hardness of low-
rank matrix completion problem under the incoherence assumption (a commonly
used assumption for many matrix completion results), was also based on gapped
versions of computationally hard problems on graphs such as the $r$-Coloring
problem and the ($r,\epsilon$)-Independent-Set problem.555In this problem, one
is given an undirected graph that is promised to be $r$-colorable and is asked
to find an independent set of size $\epsilon n$, where $\epsilon<1/r$ and $n$
is the number of the vertices in the graph.

###  1.4 Organization of the paper

The rest of the paper is organized as follows. In Section 2 we summarize
notation, definitions and theorems to be used later, define formally the
problem of maximum likelihood learning of DPPs and state our main theorem on
hardness of MLE learning DPPs. Then we outline the proof of the main theorem,
while deferring some technical proofs to later sections. Specifically, in
Section 3, we provide a detailed description of our slightly modified BOT
graph construction and prove some useful properties of these graphs. In
Section 4, we show the following: given any training set, at least one of its
optimal DPP kernels satisfy that their diagonals are equal to the empirical
frequencies of elements in the ground set. In Section 5, we explicitly
construct a rank-$3$ optimal kernel for $3$-colorable BOT graphs. For general
BOT graphs, we further prove in Section 6 that one may restrict to optimizing
over rank-$3$ DPP kernels only, without sacrificing too much in likelihood.
Then in Section 7 we put these pieces together and prove the soundness
theorem, which completes the proof of our main NP-hardness of DPP learning
theorem. In Section 8 we present and analyze our simple approximation
algorithm. Finally, we conclude in Section 9 with discussions and open
problems.

##  2 Maximum likelihood learning of DPP and our main hardness result

###  2.1 Preliminaries

Unless stated otherwise, all logarithms in this paper are to the base $e$
(i.e. natural logarithms). For positive integer $n$, we write $[n]$ to denote
the set $\\{1,2,\ldots,n\\}$. For an $n$-dimensional real vector $x$, we use
$\|x\|_{2}=\sqrt{x_{1}^{2}+\cdots+x_{n}^{2}}$ to denote the $\ell_{2}$ or
Euclidean norm of $x$.

##### Matrix analysis.

Let $A$ be an $m\times n$ matrix. The $(i,j)^{\text{th}}$ entry of $A$ will be
denoted by $A_{i,j}$. All matrices in this paper are over real numbers
$\mathbb{R}$; therefore the Hermitian adjoint of $A$, $A^{H}$ is the same as
$A^{\top}$, the transpose of $A$. By the spectral theorem, the eigenvalues of
a real, symmetric matrix $M\in\mathbb{R}^{n\times n}$ are all real numbers,
and will be denoted
$\lambda_{1}(M)\geq\lambda_{2}(M)\geq\cdots\geq\lambda_{n}(M)$. A real,
symmetric matrix $M$ is called _positive semidefinite_ (PSD) if all its
eigenvalues are non-negative (i.e., $\lambda_{n}(M)\geq 0$). Well-known
equivalent characterizations of PSD matrices include $x^{\top}Mx\geq 0$ for
all $x\in\mathbb{R}^{n}$, and the existence of a matrix
$Q\in\mathbb{R}^{k\times n}$ for some $k>0$ such that $M=Q^{\top}Q$.

A useful variational characterization of the eigenvalues of real, symmetric
matrices is the Courant-Fischer theorem, which states that for every $1\leq
k\leq n$ (when a set of vectors whose indices are outside the range $[n]$,
then the set is understood to be empty) we have

$\lambda_{k}(A)=\min_{x_{1},\ldots,x_{k-1}\in\mathbb{R}^{n}}\max_{\begin{subarray}{c}y\neq
0,\,y\in\mathbb{R}^{n}\\\ y\perp
x_{1},\ldots,x_{k-1}\end{subarray}}\frac{y^{\top}Ay}{y^{\top}y},$

and

$\lambda_{k}(A)=\max_{x_{k+1},\ldots,x_{n}\in\mathbb{R}^{n}}\min_{\begin{subarray}{c}y\neq
0,\,y\in\mathbb{R}^{n}\\\ y\perp
x_{k+1},\ldots,x_{n}\end{subarray}}\frac{y^{\top}Ay}{y^{\top}y}.$

The _singular values_ of a matrix $A\in\mathbb{R}^{m\times n}$ are defined as
the (positive) square roots of the eigenvalues of $A^{H}A=A^{\top}A$ (a real,
symmetric $n\times n$ matrix). Namely,
$\sigma_{i}(A)=\sqrt{\lambda_{i}(A^{\top}A)}$, $i=1,\ldots,n$. We also arrange
the singular values of a matrix $A$ in decreasing order, that is
$\sigma_{1}(A)\geq\sigma_{2}(A)\geq\cdots\geq\sigma_{n}(A)$. The _Frobenius
norm_ of $A$, denoted $\|A\|_{F}$, is defined to be
$\|A\|_{F}=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}|A_{i,j}|^{2}}$. It is well-known
that $\|A\|_{F}^{2}=\sigma_{1}^{2}(A)+\cdots+\sigma_{n}^{2}(A)$. Finally, the
_spectral norm_ of a square $n\times n$ matrix $A$ is defined as the square
root of the maximum eigenvalue of $A^{H}A$, i.e.,

$\|A\|_{2}=\sqrt{\lambda_{1}(A^{\top}A)}=\max_{x\neq
0}\frac{\|Ax\|_{2}}{\|x\|_{2}}=\sigma_{1}(A).$

##### Discrete determinantal point processes.

A _discrete determinantal point process_ (DPP) $\mathcal{P}$ over a finite set
$\mathcal{X}$ is a probability measure over the set of all subsets of the
ground set $\mathcal{X}$. The distribution of $\mathcal{P}$ is specified by a
marginal kernel $K\in\mathbb{R}^{\mathcal{X}\times\mathcal{X}}$, which is a
positive semidefinite matrix with eigenvalues in $[0,1]$, in the following
manner: if $\boldsymbol{Y}\subseteq\mathcal{X}$ is a random subset drawn
according to $\mathcal{P}$, then its probability mass function
$\mathcal{P}_{K}$ is defined such that, for every $S\subseteq\mathcal{X}$,

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[S\subseteq\boldsymbol{Y}]=\det(K_{S}).$

Here $K_{S}$ is the principal submatrix of $K$ indexed by
$S\subseteq\mathcal{X}$.

If it is the case that all eigenvalues of $K$ are in $[0,1)$, then
$\mathcal{P}$ is called an _$L$ -ensemble_, whose kernel can be defined to be
the positive definite666A real, symmetric matrix is called _positive definite_
(PD) if all its eigenvalues are positive. matrix $L=K(I-K)^{-1}$. In this
case, the corresponding probability mass function, denoted $\mathcal{P}_{L}$,
can be shown to be

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{L}}[\boldsymbol{Y}=S]=\frac{\det(L_{S})}{\det(I+L)},$

for every $S\subseteq\mathcal{X}$. Hence,
$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{L}}[\boldsymbol{Y}=\emptyset]={\det(I-K)}$,
and consequently a DPP is an $L$-ensemble if and only if the random variable
$\boldsymbol{Y}=\emptyset$ with non-zero probability.

###  2.2 Maximum Likelihood Learning of DPPs

We define the _Maximum Likelihood Learning of DPPs_ problem as follows. A
learning algorithm receives a training data sample
$\\{X^{\prime}_{t}\\}_{t=1}^{T^{\prime}}$ (viewed as a multiset) drawn
independently and identically from a distribution $D$ over the subsets of a
ground set $\mathcal{X}$. The goal of the learning algorithm is to find a DPP
kernel $K$ based on the training sample so that to minimize777We add a
negative sign at the front to make the estimator to be always positive, and
thus changing the maximization problem into a minimization one. To be
consistent, we still call the quantity as a “maximum” likelihood estimator;
see Remark 1. the following _maximum log likelihood estimator_

$\ell(K)=-\frac{1}{T^{\prime}}\log\prod_{t=1}^{T}\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=X_{t}]=-\frac{1}{T^{\prime}}\sum_{t=1}^{T}\log\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=X_{t}],$

where $\\{X_{1},\ldots,X_{T}\\}$ is the set of distinct elements in the
multiset $\\{X^{\prime}_{t}\\}_{t=1}^{T^{\prime}}$. When the training data
sample $\\{X^{\prime}_{t}\\}_{t=1}^{T^{\prime}}$ is clear from context, we
simply denote the value of the maximum log likelihood of an optimal DPP kernel
by $\ell^{*}$.

One common way to establish the hardness of maximum likelihood learning
problems is to show that even computing the maximum value of the log
likelihood $\ell^{*}$ is hard (if one could efficiently find an optimal DPP
kernel $K$, then since evaluations of determinants can be performed in
polynomial time, clearly the corresponding log likelihood $\ell^{*}$ would be
efficiently computable as well). That is also the approach we take in this
paper. In fact, the lower bound actually proved is much stronger: we show that
it is NP-hard even to compute a $1-O(\frac{1}{\log^{9}{N}})$-approximation of
$\ell^{*}$ for a ground set of size $N$.

######  Theorem 3 (Main).

There are infinitely many positive even integers $N$ such that the following
holds.888As we will see later that $N/2$ is the number of edges in a specially
constructed graph. We then construct a $3$-uniform hypergraph based on this
graph, and add a new node to the hypergraph for each edge in the graph. The
ground set consists of these newly added nodes together with the set of
vertices in the original graph, hence the cardinality of the ground set is at
most $N$. Let $\mathcal{X}=\\{1,2,\ldots,N\\}$. There is a training data
sample $\\{X_{t}\\}_{t=1}^{N/2}$ of size $N/2$, where
$X_{i}\subseteq\mathcal{X}$ for each $i$, such that it is NP-hard to
$\left(1-O(\frac{1}{\log^{9}{N}})\right)$-approximate the maximum log
likelihood value that a DPP kernel can achieve on the training set.

###  2.3 Proof of the Main Theorem: an outline

#####  Max-$3$SAT with bounded occurrence.

Our starting point is the hardness of Max-$3$SAT, in which given a Boolean
formula $\phi$ in $3$-CNF form, the goal is to output the maximum number of
clauses of $\phi$ that can be satisfied by any truth assignment of the
variables. A classical hardness result is the Håstad’s 3-bit PCP theorem
[Hås01], which states that it is NP-hard to $(7/8+\epsilon)$-approximate
Max-$3$SAT for any constant $\epsilon>0$. However, for our purpose, we need
the formula $\phi$ to have bounded occurrence of any variable. Let
Max-$3$SAT($k$) to denote a subclass of Max-$3$SAT, in which the instances
satisfy that every variable occurs in at most $k$ clauses. [Hås00] showed that
it is NP-hard to $7/8+1/(\log{k})^{c}$-approximate Max-$3$SAT($k$) where $c$
is some absolute constant.999We may also use the NP-hardness results of
[BKS03] for $3$-SAT instance in which every variable appears exactly $4$
times, or assuming $\mathbf{RP}\neq\mathbf{NP}$ and use the hardness result of
[Tre01] with better parameters. Therefore,

######  Lemma 1 ([Hås00]).

There are constant integer $k$ and constant $\epsilon>0$ (depending only on
$k$) such that it is NP-hard to $(1-\epsilon)$-approximate Max-$3$SAT($k$).

That is, for infinitely many integers $n$, there are two families of instances
$\phi_{Y}$ and $\phi_{N}$ in Max-$3$SAT($k$) of size $n$ each with the
following property: $\phi_{Y}$ is satisfiable; every truth assignment can
satisfy at most an $1-\epsilon$ fraction of the clauses in $\phi_{N}$; and it
is NP-hard to distinguish between the two cases.

#####  $3$-Coloring for bounded degree graphs.

Next, we adapt a gap-preserving reduction of Bogdanov, Obata and Trevisan
[BOT02], which was originally used to prove an $\Omega(n)$ query lower bound
for testing $3$-Colorability in bounded-degree graphs under the property
testing model. On input an instance $\phi$ of Max-$3$SAT($k$), the reduction
outputs a degree-bounded graph $G_{\phi}$ (BOT graph) which satisfies the
following: if $\phi$ is satisfiable then $G_{\phi}$ is $3$-colorable; and if
every truth assignment can satisfy at most $1-\epsilon$ fraction of the
clauses in $\phi$ then every $3$-coloring of the vertices of $G_{\phi}$ can
make at most $1-\epsilon^{\prime}$ fraction of the edges in $G_{\phi}$ non-
monochromatic. Here $\epsilon^{\prime}$ is a constant depending only on
$\epsilon$ and $k$.

######  Lemma 2 ([BOT02]).

There are absolute constants $d$ and $\epsilon^{\prime}>0$ such that the
following holds. For infinitely many integers $n$, there are two degree-$d$
bounded graphs $G_{\phi,Y}$ and $G_{\phi,N}$ of size $n$ such that:
$G_{\phi,Y}$ is $3$-colorable; no $1-\epsilon^{\prime}$ fraction of the edges
of $G_{\phi,N}$ is $3$-colorable; and yet it is NP-hard to distinguish between
the two cases.

##### Very strong expanders.

The main idea of the reduction of [BOT02] is to make $k$ copies of True, False
and Dummy for each variable and its negation, and use an expander to connect
these copies together to ensure truth value consistency among different
copies. Any constant-degree expander with reasonable vertex-expansion
suffices: on one hand, the resulting graph $G_{\phi}$ is of bounded degree; on
the other hand, by the expansion property, deleting a small fraction of the
edges in $G_{\phi}$ will still leave the graph with a large connected
component, using which, one can — from the coloring of $G_{\phi}$ — decode a
satisfying assignment that satisfies most of the clauses.

However, for our purpose of proving hardness of DPP Maximum Likelihood
Learning, we need the expander to have some additional properties, which are
encapsulated in the following definition.

######  Definition 1 (Very strong expanders [AC07]).

A graph $G=(V,E)$ is called a _$d$ -regular very strong expander_ on $n$
vertices if the average degree in any subgraph of $G$ on at most $n/10$
vertices is at most $d/6$, and the average degree in any subgraph of $G$ on at
most $n/2$ vertices is at most $2d/3$.

The nice properties of very strong expanders that we require are summarized in
the following theorem from [AC07].

######  Theorem 4 ([AC07]).

Let $G=(V,E)$ be a very strong $d$-regular expander on $n$ vertices. If we
delete an arbitrary subset of $m^{\prime}\leq nd/150$ edges from $G$ and
denote the resulting graph by $G^{\prime}$, then $G^{\prime}$ contains a
subgraph $H$ on at least $n-15m^{\prime}/d$ vertices and the diameter of $H$
is $O(\log{n})$.

The known _explicit_ constructions of Ramanujan graphs [LPS88, Mar88] yield
families of $d$-regular strong expanders on $n$ vertices for infinitely many
$n$’s.

#####  $3$-uniform hypergraph.

To obtain the training data sample, we transform a BOT graph $G_{\phi}=(V,E)$
into a $3$-uniform hypergraph $H_{\phi}=(V^{\prime},E^{\prime})$ as follows.
The vertex set $V^{\prime}(H_{\phi})$ is $V(G)\cup E(G)$, and for notational
convenience, we will simply label the “graph-vertex” vertices by $a_{v}$ for
every $v\in V(G)$, and label the “graph-edge” vertices in
$V^{\prime}(H_{\phi})$ by $a_{(u,v)}$ for every edge $(u,v)\in E(G)$. Then the
set of hyper-edges is
$E^{\prime}(H_{\phi})=\\{(a_{u},a_{v},a_{(u,v)}):(u,v)\in E(G)\\}.$ It follows
that $H_{\phi}$ is a $3$-uniform hypergraph with101010In order to not overload
the statement in Theorem 3 with multiple parameters, we may add isolated
vertices to graph $G_{\phi}$ so that $n=m$ and hence the ground set size is
$N$ and the sample size is $m=N/2$. $N=|V^{\prime}(H_{\phi})|=n+m$ and
$|E^{\prime}(H_{\phi})|=m$, where $n$ and $m$ denote the number of vertices
and edges of the BOT graph $G_{\phi}$, respectively.

Now, what happens if we use the set of hyper-edges of $H_{\phi}$ as the
training data sample $\\{X_{t}\\}_{t=1}^{m}$, and feed it to a DPP Maximum
Likelihood Learning algorithm? Our first step in understanding the optimal DPP
kernel is to establish a connection between DPP kernel of learning BOT
hypergraphs and a problem called “vector coloring”.

##### Connecting DPP kernels with vector colorings.

Since $K$ is a positive semidefinite matrix, we can write $K$ as $K=Q^{\top}Q$
for some matrix $Q$. Let $q_{1},\ldots,q_{N}\in\mathbb{R}^{k}$ be the columns
of $Q$. We can further decompose these vectors as
$q_{i}=\|q_{i}\|_{2}\chi_{i}$, where $\chi_{i}\in\mathbb{R}^{k}$ is a unit
vector. The quantity $\|q_{i}\|_{2}$ is a measure of the “importance” of item
$i$, and $\chi_{i}$ is a normalized vector which encodes diversity features of
item $i$. Now the entries of the marginal kernel satisfy
$K_{ij}=\|q_{i}\|_{2}\chi_{i}^{\top}\chi_{j}\|q_{j}\|_{2}$, where
$\chi_{i}^{\top}\chi_{j}\in[-1,1]$ is a signed measure of the similarity
between item $i$ and item $j$. In particular, the diagonal entries satisfy
that $K_{ii}=\|q_{i}\|^{2}_{2}$ for every $i\in[N]$.

We prove the following theorem, which allows us to somewhat decouple
$\|q_{i}\|_{2}$ and $\chi_{i}$ for each item $i$, and identify (from the
training set) the value of the “importance” (i.e. value $\|q_{i}\|_{2}$) for
each item.111111It is no coincidence that our simple algorithm (see Section 8
for details), using this “first-moment” information from the training set in a
similar manner, constructs its DPP that achieves nontrivial worst-case
approximation to the optimal log likelihood. Our result essentially determines
at least one of the optimal settings of the importance of each item.

######  Theorem 5.

Let $K$ be a marginal kernel with likelihood $\ell(K)$. Then there exists a
marginal kernel $K^{\prime}$ with $\ell(K^{\prime})\leq\ell(K)$ such that the
diagonal of $K^{\prime}$ (indexed by vertices and edges of $G_{\phi}$)
satisfies

$K^{\prime}_{ii}=\begin{cases}\frac{\deg_{G_{\phi}}(u)}{m}&\mathrm{for\;}i=u\in
V(G_{\phi});\\\ \frac{1}{m}&\mathrm{for\;}i=(u,v)\in E(G_{\phi}).\end{cases}$

Thus, it remains to determine the diversity features that maximize the
likelihood. To this end, we use a variant of $3$-colorability in which the
“colors” are generalized to vectors in $\mathbb{R}^{k}$ and the “coloring
constraint” for an edge $(i,j)$ is satisfied if the vectors $\chi_{i}$ and
$\chi_{j}$ assigned to the vertices $i$ and $j$ are orthogonal.

More formally, let $S^{k-1}$ be the unit sphere in $k$-dimensional Euclidean
space; that is, $S^{k-1}=\\{x\in\mathbb{R}^{k}:\|x\|_{2}=1\\}$. Given a graph
$G=(V,E)$, we define a _vector $k$-coloring_ of $G$ to be a function
$\chi:V(G)\to S^{k-1}$. We say that a vector $k$-coloring $\chi$ is
_orthogonal_ if, for every edge $(u,v)\in E(G)$, we have
$\chi_{u}^{\top}\chi_{v}=0$. We define the _error_ of a vector $k$-coloring
$\chi$ of $G$ to be

$\mathrm{err}_{\chi}(G):=\frac{1}{|E(G)|}\sum_{(u,v)\in
E(G)}|\chi_{u}^{\top}\chi_{v}|^{2}$

so that a vector $k$-coloring $\chi$ of $G$ is orthogonal if and only if
$\mathrm{err}_{\chi}(G)=0$. Since $\chi_{u}$ and $\chi_{v}$ are unit vectors,
$|\chi_{u}^{\top}\chi_{v}|=|\cos\theta_{uv}|$ for all $(u,v)\in E(G)$, where
$\theta_{uv}$ is the angle between $\chi_{u}$ and $\chi_{v}$.

Now, by combining Theorem 5 with the fact that any $3$-coloring of $G$
naturally induces a vector $3$-coloring of $G$, it is not hard to prove the
following “completeness” theorem.

######  Theorem 6 (Completeness theorem).

Let $G_{\phi}$ be a BOT graph, and let $n=|V(G_{\phi})|$ be the number of
vertices and $m=|E(G_{\phi})|$ be the number of edges of $G_{\phi}$,
respectively. If $\phi$ is satisfiable, then there exists a rank-$3$ DPP
marginal kernel $K$ such that

$\ell(K)=\ell^{*}=3\log{m}-\frac{1}{m}\sum_{(u,v)\in
E(G_{\phi})}\left(\log(\deg_{G_{\phi}}(u))+\log(\deg_{G_{\phi}}(v))\right).$

##### Projecting DPP kernels to $\mathbb{R}^{3}$.

Intuitively, the maximum likelihood marginal kernel has dimension $3$ so that
zero probability measure will be assigned for subsets of size at least $4$. We
were unable to prove this, but we nevertheless manage to show that the loss in
making such an assumption is not too great:

######  Theorem 7.

Let $G_{\phi}$ be a BOT graph with maximum degree at most $k$. There is a
constant $C_{k}$ depending only on $k$ such that the following holds. Let $K$
be an optimal marginal kernel with likelihood $\ell(K)\leq\ell^{*}+\delta$ for
some $0<\delta\leq 1/(128k)^{2}$, then there exists a marginal kernel
$K^{\prime}$ of dimension $3$ such that
$\ell(K^{\prime})\leq\ell^{*}+C_{k}\delta^{1/4}$.

We conjecture that an even stronger statement is in fact true.

######  Conjecture 1 (Cardinality-rank conjecture).

If the cardinality of every subset in a training set is at most $k\geq 1$,
then every optimal maximum likelihood marginal kernel for the training set has
dimensional at most $k$.

This conjecture may be of independent interest outside the realm of maximum
likelihood learning of DPPs.

##### Decoding truth assignments from vector colorings.

Because of Theorem 7, from now on we assume that the dimension of $Q$ is $3$.
Therefore, for each $(a_{u},a_{v},a_{(u,v)})\in E^{\prime}(H_{\phi})$,

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=\\{a_{u},a_{v},a_{(u,v)}\\}]=\det(K_{\\{a_{u},a_{v},a_{(u,v)}\\}}),$

where $K=Q^{\top}Q$ is the marginal kernel of DPP $\mathcal{P}$. To maximize
the likelihood, we want to maximize the product of determinants of the above
form. Since each $a_{(u,v)}$ occurs in only one sample, we can assume that
$\chi_{a_{(u,v)}}$ is always taken to be orthogonal to $\chi_{a_{u}}$ and
$\chi_{a_{v}}$. Thus, the likelihood contribution from
$(a_{u},a_{v},a_{(u,v)})$ is maximized when
$\chi_{a_{u}}^{\top}\chi_{a_{v}}=0$; or equivalently, when $\chi_{a_{u}}$ and
$\chi_{a_{v}}$ are orthogonal. We formally prove this correspondence between
the “orthogonality” of the associated vector $3$-coloring of $G_{\phi}$ and
the likelihood of the corresponding DPP with marginal kernel $K=Q^{\top}Q$,
where the column of $Q$ corresponding to vertex $u$ is
$\|q_{a_{u}}\|_{2}\chi_{a_{u}}$. Moreover, we can even decode the truth-
assignment of the Boolean formula $\phi$ if the vector $3$-coloring of
$G_{\phi}$ is very close to satisfying all edges of $G_{\phi}$.

######  Theorem 8 (Soundness theorem).

Let $\ell^{*}$ be the optimal log likelihood as in Theorem 6. Then there
exists a constant $C>0$ which depends only on $k$ and $\epsilon^{\prime}$ as
those defined in Theorem 2, such that the following holds. If there is a DPP
marginal kernel $K$ of rank $3$, which satisfies
$\ell(K)\leq\ell^{*}+\frac{C}{\log^{2}{n}}$ where $n=|V(G_{\phi})|$ is the
number of vertices in the BOT graph, then there is a truth assignment that
satisfies at least $(1-\epsilon)$ fraction of the clauses in $\phi$, where
$\epsilon$ is the constant defined in Theorem 1.

To see why Theorem 8 implies our main theorem, Theorem 3, consider that we
start the reduction with two families of instances $\phi_{Y}$ and $\phi_{N}$
in Max-$3$SAT($k$) which are NP-hard to distinguish. Then we construct their
corresponding BOT hypergraphs, $H_{\phi_{Y}}$ and $H_{\phi_{N}}$, and use the
edge sets of these two hypergraphs as training sets of size $m$ for a DPP
maximum likelihood learning algorithm. The log likelihood estimator of
$\phi_{Y}$ is $\ell^{*}=\Theta(\log{N})$ by Theorem 6. What is the log
likelihood estimator of $\phi_{N}$? Well, by Theorem 7, if the marginal kernel
of $G_{\phi_{N}}$ has log likelihood $\ell(K)\leq\ell^{*}+\delta$ for some
small enough $\delta>0$, then there exists a marginal kernel $K^{\prime}$ of
dimension $3$ such that $\ell(K^{\prime})\leq\ell^{*}+C_{k}\delta^{1/4}$. By
Theorem 8, we must have $\delta=\Omega(\frac{1}{\log^{2}{N}})$ for $\phi_{N}$.
That is, the log likelihood estimator of $\phi_{N}$ is
$\ell^{*}+\Omega(\frac{1}{\log^{8}{N}})$. Now if there were an polynomial-time
algorithm $\mathcal{A}$ which approximates the log likelihood estimator within
a factor of $1-1/\Omega(\log^{9}{N})$, then $\mathcal{A}$ would be able to
tell apart $\phi_{Y}$ from $\phi_{N}$ — thus solving an NP-complete problem —
simply by approximating the maximum log likelihood estimators on training data
sample from $H_{\phi_{Y}}$ and $H_{\phi_{N}}$, respectively.

##  3 Robustness of very strong expanders – Proof of Lemma 2

###  3.1 BOT graphs

$D_{i}^{(j)}$$F_{i}^{(j)}$$T_{i}^{(j)}$$\overline{D}_{i}^{(j)}$$\overline{F}_{i}^{(j)}$$\overline{T}_{i}^{(j)}$$\mathbf{x_{i}^{(j)}}$-block$\mathbf{\bar{x}_{i}^{(j)}}$-block$x_{i}^{(j)}$$\bar{x}_{i}^{(j)}$
Figure 2: Literal blocks. This gadget enforces that the $j^{\text{th}}$ copy
of literal $x_{i}$ and $\bar{x}_{i}$ will always be assigned opposite truth
values, as long as the assignments of True, False and Dummy nodes in
$x_{i}^{(j)}$-block and $\bar{x}_{i}^{(j)}$-block are consistent with their
corresponding nodes in the rest of the graph.

$x$$y$$u$$v$ (a) The equality gadget for $x=y$.

$T_{1}^{(3)}$$\overline{T}_{3}^{(2)}$$T_{5}^{(4)}$$x_{1}^{(3)}$$\bar{x}_{3}^{(2)}$$x_{5}^{(4)}$$u_{a}$$u_{b}$$u_{c}$$v_{a}$$v_{b}$$v_{c}$

(b) The clause gadget for a clause $(\ell_{a}\lor\ell_{b}\lor\ell_{c})$. For
concreteness, we illustrate the construction with $\ell_{a}=x_{1}$ (using the
$3$rd copy), $\ell_{b}=\bar{x}_{3}$ (using the $2$nd copy) and
$\ell_{c}=x_{5}$ (using the $4$th copy).

Figure 3: Two basic gadgets of BOT graphs.

Very Strong Expander $G([2kn],E)$$\mathbf{x_{1}^{(1)}}$
block$\mathbf{\bar{x}_{1}^{(1)}}$
block$\mathbf{\cdots\cdots}$$\mathbf{\bar{x}_{1}^{(k)}}$
block$\mathbf{{x}_{1}^{(k)}}$
block$\mathbf{\cdots\cdots}$$\mathbf{\cdots\cdots}$$\mathbf{\bar{x}_{n}^{(k)}}$
block$\mathbf{{x}_{n}^{(k)}}$ block

(a) The underlying expander with literal blocks as vertices.

$D_{i}^{(j)}$$F_{i}^{(j)}$$T_{i}^{(j)}$$D_{i^{\prime}}^{(j^{\prime})}$$F_{i^{\prime}}^{(j^{\prime})}$$T_{i^{\prime}}^{(j^{\prime})}$$u^{T}_{i^{(j)},i^{\prime(j^{\prime})}}$$v^{T}_{i^{(j)},i^{\prime(j^{\prime})}}$$u^{D}_{i^{(j)},i^{\prime(j^{\prime})}}$$v^{D}_{i^{(j)},i^{\prime(j^{\prime})}}$$u^{F}_{i^{(j)},i^{\prime(j^{\prime})}}$$v^{F}_{i^{(j)},i^{\prime(j^{\prime})}}$

(b) A block equality gadget that is created in step 6 if $x_{i}^{(j)}$-block
is connected with $x_{i^{\prime}}^{(j^{\prime})}$-block in the underlying
expander.

Figure 4: The expander part of BOT graph.

We now provide a detailed description and analysis of the construction in
[BOT02], as our hardness proof relies crucially on the properties of BOT
graphs.

Recall that in the classic reduction from $3$-SAT to $3$-Coloring, there are
three designated nodes True, False and Dummy which form a triangle so that in
any $3$-coloring of the graph they must be assigned to different colors. The
reduction then connects the nodes in literal gadgets and clause gadgets to
these three nodes so that every literal is connected to the Dummy node, and
any $3$-coloring of the graph can be decoded into a satisfying assignment
simply by reading the color of every literal node. On the other hand, any
satisfying assignment of the variables can also be transformed into a valid
$3$-coloring of the graph by assigning “True” literal nodes the same color as
the True node and assigning “False” literal nodes the same color as the False
node.

The basic idea of the construction in [BOT02] is to make $k$ “local” copies
for each literal node as well as for the three designated True, False and
Dummy nodes, so that each local copy of these nodes used only _once_ in the
clause gadgets. The benefit of doing so is that deleting any single node or
any single edge will affect (or “destroy”) a single clause, hence makes the
reduction from $3$-SAT to $3$-Coloring (up to a constant factor) distance-
preserving. However, this introduces a new difficulty: we need to make sure
that all $k$ copies of literal nodes (True, False and Dummy nodes) should be
assigned with the same color. Such consistency is ensured by embedding these
local copies on an expander so that the graph is robust against deletions of a
small number of edges or nodes, and at the same time the blowup in the maximum
degree is bounded.

Specifically, given a Boolean formula $\phi$ in $3$-CNF form, in which $\phi$
has $n$ variables, $m$ clauses and each literal appears in at most $k$
clauses, construct an undirected graph $G_{\phi}(V,E)$ as follows:

  1. 1.

Create $2kn$ literal nodes: for each variable $x_{i}$, $1\leq i\leq n$, create
$k$ copies of it $x_{i}^{(j)}$, and another $k$ copies of its negation
${\bar{x}_{i}}^{(j)}$, where $j=1,\ldots,k$;

  2. 2.

For each of the $2kn$ literal nodes $x_{i}^{(j)}$ (resp. $\bar{x}_{i}^{(j)}$),
create a block — called _$x_{i}^{(j)}$ -block_ (resp. _$\bar{x}_{i}^{(j)}$
-block_) — of $3$ color nodes $T_{i}^{(j)},F_{i}^{(j)},D_{i}^{(j)}$ (resp.
$\bar{T}_{i}^{(j)},\bar{F}_{i}^{(j)},\bar{D}_{i}^{(j)}$), which serve as local
copies of True, False and Dummy nodes. Add a triangle on
$(T_{i}^{(j)},F_{i}^{(j)},D_{i}^{(j)})$ (resp.
$(\bar{T}_{i}^{(j)},\bar{F}_{i}^{(j)},\bar{D}_{i}^{(j)})$) for each literal
block;

  3. 3.

For each literal, add an edge between the literal node and its negation node,
so that literals and their negations will always be assigned to different
colors. These edges, as well as the $x_{i}^{(j)}$-block and the
$\bar{x}_{i}^{(j)}$-block, are illustrated in Fig. 2;

  4. 4.

For each literal $x_{i}$ (resp. $\bar{x}_{i}$), use the _equality gadget_ as
illustrated in Fig. 3(a) to connect between each pair of its $k$ copies. That
is, create a “$k$-clique” among $\\{x_{i}^{(j)}\\}_{j\in[k]}$ (resp.
$\\{\bar{x}_{i}^{(j)}\\}_{j\in[k]}$) such that each “edge” in the “clique” is
actually an independent copy of the equality gadget;

  5. 5.

For each clause, add a _clause gadget_ to connect $3$ literals in that clause
together with their corresponding True nodes (in the blocks that are created
in step 1) with $6$ auxiliary nodes as shown in Fig 3(b). Note that all
literal nodes and True nodes in the clause gadgets are used only once; and

  6. 6.

Build a constant-degree expander graph of size $2kn$, with
$x_{i}^{(j)}$-blocks and $\bar{x}_{i}^{(j)}$-blocks, $1\leq i\leq n$ and
$1\leq j\leq k$, as its vertices. Then, for any two blocks that are connected
by an edge in the expander, connect their corresponding True nodes (resp.
False nodes and Dummy nodes) with an independent copy of the equality gadget.
See Fig. 4 for an illustration.

Note that for a bounded occurrence instance $\phi$ of $3$-CNF formula, the
number of clauses is at most $m\leq 2kn/3$.

###  3.2 Properties of BOT graph and proof of Lemma 2

We first record the following correctness result of $G_{\phi}$ from [BOT02],
which follows a similar proof of the classic reduction from $3$-SAT to
$3$-Coloring.

######  Proposition 1 ([BOT02]).

The $3$-CNF formula $\phi$ is satisfiable if and only if graph $G_{\phi}$ is
$3$-colorable.

Next we do some simple calculations on the parameters of $G_{\phi}$.

######  Proposition 2.

Suppose the underlying expander is $d$-regular, then $G_{\phi}$ satisfies the
following.

  * •

The maximum degree is $\max(2d+3,2k+1)\leq 2\max(k,d)+3$;

  * •

$|V(G_{\phi})|=O(nk)\cdot\max(k,d)$; and

  * •

$|E(G_{\phi})|=O(nk)\cdot\max(k,d)$.

###### Proof.

The maximum degree follows by noticing that (for simplicity, we only consider
nodes for the un-negated literals) $\deg(D_{i}^{(j)})=2d+3$,
$\deg(F_{i}^{(j)})=2d+2$, $\deg(T_{i}^{(j)})\leq 2d+3$, and
$\deg(x_{i}^{(j)})\leq 2k+1$.

Note that every equality gadget introduces $2$ auxiliary nodes and $5$
additional edges. Similarly, every clause gadget introduces $6$ auxiliary
nodes and $12$ additional edges. The nodes in $G_{\phi}$ consists of $2nk$
literals nodes, $6nk$ literal block nodes and auxiliary nodes introduced by
gadgets. That is

$\displaystyle|V(G_{\phi})|$ $\displaystyle=8nk+2n\cdot\frac{k(k-1)}{2}\cdot
2+3\cdot\frac{2nk\cdot d}{2}\cdot 2+6m$ $\displaystyle\leq
8nk+2n(k^{2}-k)+6nkd+4nk=O(nk)\cdot\max(k,d),$

where in the second last step we use the bound $m\leq 2kn/3$. Finally,

$\displaystyle|E(G_{\phi})|$
$\displaystyle=nk(3+6)+2n\cdot\frac{k(k-1)}{2}\cdot 5+3\cdot\frac{2nk\cdot
d}{2}\cdot 5+12m$ $\displaystyle\leq
9nk+5n(k^{2}-k)+15nkd+8nk=O(nk)\cdot\max(k,d),$

where the first term counts the edges in Fig. 2 for all $k$ copies of each
_variable_ , and the next two terms count the total number of edges in the
equality constraints and the last term counts the total number of edges in the
clause gadgets. ∎

We say an equality gadget is _broken_ if any of the $5$ edges in Fig. 3(a) is
deleted, and say a literal node $(x_{i}^{(j)}$ (resp. $\bar{x}_{i}^{(j)})$) is
_isolated_ if either all its $k-1$ equality connections with other copies of
$x_{i}$ (resp. $\bar{x}_{i}$) are all broken, or all its $d$ equality
connections with other literal nodes in the expander graph are all broken. We
say a literal pair $(x_{i}^{(j)},\bar{x}_{i}^{(j)})$ is _damaged_ if any of
the edges within the two literal blocks in Fig. 2 is deleted, or either
$x_{i}^{(j)}$ node or $\bar{x}_{i}^{(j)}$ node becomes isolated.

Let $E^{\prime}\subset E(G_{\phi})$ be a subset of the edges of graph
$G_{\phi}$. What happens if we delete all the edges in $E^{\prime}$? Define
the _survived subgraph induced by $E^{\prime}$_ of $G_{\phi}$, denoted
$G^{\prime}_{\phi,E^{\prime}}$ as follows. Delete all literal pairs that are
damaged from deleting edges in $E^{\prime}$, and delete all the edges
connected with damage pairs; delete all clause gadgets that contain one or
more damaged literals. We make the following two simple observations on a
survived subgraph $G^{\prime}_{\phi,E^{\prime}}$.

######  Claim 1.

Let $\phi^{\prime}$ be the $3$-CNF formula by keeping only the survived
clauses in $G^{\prime}_{\phi,E^{\prime}}$. Then $\phi^{\prime}$ is satisfiable
if and only if $G^{\prime}_{\phi,E^{\prime}}$ is $3$-colorable.

###### Proof.

This follows directly by noticing that $G^{\prime}_{\phi,E^{\prime}}$ can be
regarded as the BOT graph constructed from formula $\phi^{\prime}$. ∎

######  Claim 2.

If we delete a subset of edges $E^{\prime}$, then the number of survived
clauses in $\phi^{\prime}$ is at least $m-2|E^{\prime}|$.

###### Proof.

This is because deleting an edge causes at most one literal pair damaged, and
thus affects at most two clauses. ∎

Our main goal in this Section is the prove the following lemma on the gap-
preserving reduction from Max-$3$SAT($k$) to $3$-Coloring of bounded-degree
graphs of Bogdanov, Obata and Trevisan [BOT02].

######  Lemma 2 (restatement).

There are absolute constants $d$ and $\epsilon^{\prime}>0$ such that the
following holds. For infinitely many integers $n$, there are two degree-$d$
bounded graphs $G_{\phi,Y}$ and $G_{\phi,N}$ of size $n$ such that:
$G_{\phi,Y}$ is $3$-colorable; no $1-\epsilon^{\prime}$ fraction of the edges
of $G_{\phi,N}$ is $3$-colorable; and yet it is NP-hard to distinguish between
the two cases.

###### Proof.

Recall that, by Lemma 1, there are constant integer $k$ and constant
$\epsilon(k)>0$ such that there are two families of instances $\phi_{Y}$ and
$\phi_{N}$ in Max-$3$SAT($k$) of size $n$ each, $\phi_{Y}$ is satisfiable and
any truth assignment can satisfy at most $1-\epsilon(k)$ fraction of the
clauses in $\phi_{N}$, and it is NP-hard to distinguish between these two
formulas. Now, use the very strong expander given in Theorem 4 to construct
the corresponding BOT graphs $G_{\phi,Y}$ and $G_{\phi,N}$ for $\phi_{Y}$ and
$\phi_{N}$, respectively (we just need to make sure that the number of
vertices of the very strong expander is at least $2nk$; if the number of
vertices is larger, then we can simply make some of the literals more than $k$
copies). Let $n$ be the number of variables and $m$ be the number of clauses
of the Boolean formula, where $m\geq n$. Define
$\epsilon^{\prime}=\frac{\epsilon\cdot n}{2|E(G_{\phi,N})|}$. Since both $k$
and $d$ are constants, then by Proposition 2, $\epsilon^{\prime}$ is an
absolute constant depending on $\epsilon$, $k$ and the degree $d$ of the
underlying expander graph. Clearly $G_{\phi,Y}$ is $3$-colorable. It is also
not hard to prove that $G_{\phi,N}$ is not $(1-\epsilon^{\prime})$
$3$-colorable. Indeed, suppose that $G_{\phi,N}$ is $(1-\epsilon^{\prime})$
$3$-colorable. Then we can delete at most $\epsilon^{\prime}|E(G_{\phi,N})|$
edges from $G_{\phi,N}$, obtain a survived subgraph with at least
$m-\epsilon\cdot n\geq(1-\epsilon)m$ clauses which is $3$-colorable. Now by
Claim 1, the $3$-coloring of the survived subgraph can be decoded into a
satisfying assignment for the survived, at least $(1-\epsilon)m$ clauses of
$\phi_{N}$, a contradiction. Finally the constant degree bound of the
constructed BOT graphs follows from the first item of Proposition 2. ∎

##  4 Structure of max-likelihood solutions – Proof of Theorem 5

For convenience of the reader, we repeat Theorem 5 here.

######  Theorem 5 (restatement).

Let $K$ be a marginal kernel with likelihood $\ell(K)$. Then there exists a
marginal kernel $K^{\prime}$ with $\ell(K^{\prime})\leq\ell(K)$ such that the
diagonal of $K^{\prime}$ (indexed by vertices and edges of $G_{\phi}$)
satisfies

$K^{\prime}_{ii}=\begin{cases}\frac{\deg_{G_{\phi}}(u)}{m}&\mathrm{for\;}i=u\in
V(G_{\phi});\\\ \frac{1}{m}&\mathrm{for\;}i=(u,v)\in E(G_{\phi}).\end{cases}$

The proof follows from the following slightly stronger lemma, which implies
that we can assume that the diagonal of a max likelihood kernel $K$ (indexed
by vertices and edges of $G_{\phi}$) satisfies that $K_{ii}$ is equal to the
normalized frequency of element $i$ in the training set.

######  Lemma 3.

Let $[N]$ be the ground set, $\mathcal{S}=\\{X_{j}\\}_{j=1}^{m}$ be a set of
$m$ samples with each $X_{j}\subseteq[N]$. Let $D$ be the empirical
distribution induced by the sample set $\mathcal{S}$: namely, for every
$X\subseteq[N]$, $D(X)=|\\{X\in\mathcal{S}\\}|/m$ if $X$ is in the sample set,
and $D(X)$ is zero otherwise. Then there is a maximum likelihood marginal
kernel $K$ which satisfies that the diagonal entry of $K$ at each element in
$[N]$ is equal to the element’s empirical frequency in the sample set. That
is, $K_{ii}=\displaystyle\sum_{X\in\mathcal{S}:X\ni i}D(X)$ for every
$i\in[N]$.

The rest of this section is devoted to a proof of Lemma 3.

###  4.1 The $L$-ensemble case

We start by assuming that all of $K$’s eigenvalues are in $(0,1)$, and follow
a similar strategy as of the proof of Proposition $13$ in [BMRU17a]. Note that
in this case the DPP is an $L$-ensemble, where $L=K(I-K)^{-1}$. If $K$ is a
maximum likelihood DPP, then the corresponding $L$ is a critical point of the
likelihood function, and accordingly the directional derivative of the
likelihood function in every direction is zero. Thus, in “direction” of any
matrix $H\in\mathbb{R}^{N\times N}$, we get

$\sum_{X\subseteq[N]}D(X)\mathrm{Tr}(L_{X}^{-1}H_{X})-\mathrm{Tr}((I+L)^{-1}H)=0$

Fix $t_{1},t_{2},\ldots,t_{n}\in\mathbb{R}$, and let $T$ be the diagonal
matrix with diagonal $t_{1},t_{2},\ldots,t_{n}$. Setting
$H=\frac{1}{2}LT+\frac{1}{2}TL$ (this ensures that we consider symmetric
kernels), we get $H_{X}=\frac{1}{2}L_{X}T_{X}+\frac{1}{2}T_{X}L_{X}$. Since
$(I+L)^{-1}$ and $L$ commute, and the trace is invariant under cyclic
permutations, we get

$\sum_{X\subseteq[N]}D(X)\sum_{j\in
X}t_{j}=\mathrm{Tr}(KT)=\sum_{j=1}^{N}K_{jj}t_{j}$

Fix $i\in[N]$, and consider the setting where $t_{i}=1$ and $t_{j}=0$ for all
$j\neq i$. The above equation becomes

$\sum_{X\subseteq[N]:X\ni i}D(X)=K_{ii},$ (1)

completing the proof of the lemma for the $L$-ensemble case.

###  4.2 Perturbing the training example distribution

To deal with the non $L$-ensemble case, we apply a continuity argument:
specifically, we employ a Lipschitz property of the log likelihood function
with respect to small perturbations of the training example distribution. In
the rest of the proof we think $N$ (hence both $n$ and $m$) as a fixed
constant and let the small quantities such as $\epsilon$ tend to zero
independent of $N$.

Let $D$ be the original empirical distribution induced by the sample set
$\mathcal{S}$ of size $m$. Without loss of generality, we assume121212For if
$D(\emptyset)\neq 0$, any optimal DPP kernel for $D$ is necessarily an
$L$-ensemble. We further assume $D([N])=0$ to simplify exposition. It is easy
to see that the there are two parts in the definition of $K^{*}_{\epsilon}$
below: the rescaling part is to deal with DPP kernel singularity at
$\emptyset$, and the spectrum shifting part is to deal with DPP kernel
singularity at $[N]$. One can therefore keep only the rescaling part in
$K^{*}_{\epsilon}$ when $D([N])$ is bounded away from zero. both
$D(\emptyset)=0$ and $D([N])=0$. We perturb $D$ by adding very tiny
probabilities at $\emptyset$ and $[N]$ so that the corresponding correlation
kernel is an $L$-ensemble.131313Making the empirical distribution to be non-
zero at $\emptyset$ ensures that the kernel is an $L$-ensemble; however, in
order to apply the matrix derivative argument in [BMRU17a], we need to make
the distribution to be non-zero at $[N]$ as well. Formally, define
$D_{\epsilon}$ to be a distribution on $2^{[N]}$ such that for any
$X\subseteq[N]$

$D_{\epsilon}(X)=\begin{cases}(1-\epsilon)D(X)&\text{if $X\in\mathcal{S}$;
}\\\ \epsilon/2&\text{if $X=\emptyset$; }\\\ \epsilon/2&\text{if $X=[N]$; }\\\
0&\text{otherwise.}\end{cases}$ (2)

We stress that the small quantity $\epsilon$ is independent of the DPP
learning instance under consideration.

In the following, we will use $K^{*}$ to denote a (non $L$-ensemble) optimal
marginal kernel for the original training distribution $D$, and use
$K_{\epsilon}$ to denote an optimal marginal kernel for the perturbed training
distribution $D_{\epsilon}$. Since $D_{\epsilon}(\emptyset)>0$ and
$D_{\epsilon}([N])>0$, $K_{\epsilon}$ is necessarily an $L$-ensemble and hence
by our previous argument, the diagonals of $K_{\epsilon}$ satisfy (1). In
particular, for every $i\in[N]$

$\displaystyle(K_{\epsilon})_{ii}=\frac{\epsilon}{2}+\sum_{X\in\mathcal{S}:X\ni
i}(1-\epsilon)D(X),$ (3)

which approaches $\sum_{X\in\mathcal{S}:X\ni i}D(X)$ when $\epsilon$ tends to
zero.

To make the dependency of the maximum log likelihood estimator on the
empirical distribution explicit, we write $\ell(K,D)$ for the log likelihood
function of DPP kernel $K$ on training distribution $D$. Therefore,

$\displaystyle\ell(K^{*},D)=\sum_{X\in\mathcal{S}}D(X)\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}}}[\boldsymbol{Y}=X]}\right),$
(4)

and

$\displaystyle\ell(K_{\epsilon},D_{\epsilon})=$
$\displaystyle\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K_{\epsilon}}}[\boldsymbol{Y}=\emptyset]}\right)+\sum_{X\in\mathcal{S}}(1-\epsilon)D(X)\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K_{\epsilon}}}[\boldsymbol{Y}=X]}\right)$
$\displaystyle+\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K_{\epsilon}}}[\boldsymbol{Y}=[N]]}\right).$
(5)

The main goal in this subsection is to prove the following inequality, which
says that the $L$-ensemble marginal kernel $K_{\epsilon}$, which is defined to
be optimal for the perturbed training distribution $D_{\epsilon}$, is also
close to being optimal for the original training distribution $D$.

######  Proposition 3.

Let $D$, $K^{*}$, $D_{\epsilon}$ and $K_{\epsilon}$ be defined as before. Then
for every $\epsilon>0$ that is small enough

$\displaystyle\ell(K_{\epsilon},D)\leq\ell(K^{*},D)+O(\epsilon\log{\frac{1}{\epsilon}}),$
(6)

where the hidden constant in the $O(\epsilon\log{\frac{1}{\epsilon}})$ term
depends only on $N$.

###### Proof.

Let $I_{N}$ denote the $N\times N$ identity matrix. Define a new marginal
kernel $K^{*}_{\epsilon}$ as

$K^{*}_{\epsilon}=(1-\epsilon)K^{*}+\frac{\epsilon}{2}I_{N}.$

Clearly, since $K^{*}$ is PSD, $\lambda_{N}(K^{*}_{\epsilon})\geq\epsilon/2$.
It is also not hard to verify that
$\lambda_{1}(K^{*}_{\epsilon})=(1-\epsilon)\lambda_{1}(K^{*})+\epsilon/2\leq
1-\epsilon/2$. It follows that $K^{*}_{\epsilon}$ is indeed a DPP marginal
kernel.

We will prove the following sequence of inequalities

$\displaystyle\ell(K^{*}_{\epsilon},D)$
$\displaystyle\leq\ell(K^{*},D)+O(\epsilon).$ (7)
$\displaystyle\ell(K^{*}_{\epsilon},D_{\epsilon})$
$\displaystyle\leq\ell(K^{*}_{\epsilon},D)+O(\epsilon\log{\frac{1}{\epsilon}}).$
(8) $\displaystyle\ell(K_{\epsilon},D_{\epsilon})$
$\displaystyle\leq\ell(K^{*}_{\epsilon},D_{\epsilon}).$ (9)
$\displaystyle\ell(K_{\epsilon},D)$
$\displaystyle\leq\ell(K_{\epsilon},D_{\epsilon})+O(\epsilon).$ (10)

First of all, let’s state and prove two useful bounds.

######  Fact 1.

Let $D^{\prime}$ be an arbitrary empirical distribution over the ground set
$[N]$, and let $\ell^{*}(D^{\prime})$ denote the optimal value of the DPP
maximum log likelihood estimator for $D^{\prime}$. Then
$\ell^{*}(D^{\prime})\leq N\log{2}$.

###### Proof.

This is because the trivial diagonal kernel $K_{I}:=\frac{1}{2}I_{N}$, which
corresponds to the uniform distribution over all $2^{[N]}$ subsets, is a legal
DPP marginal kernel for any distribution $D^{\prime}$ over $[N]$, and its log
likelihood estimator is easily seen to be $N\log{2}$. ∎

######  Fact 2.

Let $\mathcal{S}=\\{X_{j}\\}_{j=1}^{m}$ be a set of $m$ samples with each
$X_{j}\subseteq[N]$, the ground set. Let $K$ be any maximum likelihood
marginal kernel of the empirical distribution induced by the sample set
$\mathcal{S}$. Then, for any $X_{j}\in\mathcal{S}$,

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=X_{j}]\geq
e^{-\log{2}\cdot mN}>e^{-\log{2}\cdot N^{2}}.$

###### Proof.

This follows by combining Fact 1 with the fact that in (4), $D(X_{j})\geq
1/m$. ∎

####  4.2.1 Proof of inequality (7)

For any DPP marginal kernel $K$ and $X\subseteq[N]$, it is well-known that
using inclusion-exclusion principle, we can express
$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=X]$ in terms of $K$ as

$\displaystyle\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=X]$
$\displaystyle=\sum_{T\supseteq X}(-1)^{|T\setminus
X|}\det(K_{T})=(-1)^{|X|}\sum_{T\supseteq X}(-1)^{|T|}\det(K_{T})$
$\displaystyle=(-1)^{|X|}\det(I_{\bar{X}}-K)=|\det(K-I_{\bar{X}})|,$

where $I_{\bar{X}}$ stands for the diagonal matrix whose $(i,i)$-entry is $1$
if $i\in\bar{X}$ and is $0$ otherwise.

Now fix any $X\in\mathcal{S}$. Then
$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}}}[\boldsymbol{Y}=X]=|\det(K^{*}-I_{\bar{X}})|=|\det(A)|$,
where $A:=K^{*}-I_{\bar{X}}$. By Fact 2, $|\det(A)|\geq e^{-mN\log{2}}$.
Similarly,

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=X]=|\det(K^{*}_{\epsilon}-I_{\bar{X}})|=|\det(A+\epsilon
E)|,$

where $E:=\frac{1}{2}I_{N}-K^{*}$.

We use the following result to bound the difference between $\det(A+\epsilon
E)$ and $\det(A)$.

######  Theorem 9 ([IR08]).

Let $A$ and $E$ be two $N\times N$ complex matrices. Let
$\sigma_{1}\geq\cdots\geq\sigma_{N}$ be the singular values of $A$, and
suppose that the spectral norm of $E$ satisfies $\lVert E\rVert_{2}<1$. Then

$\left|\det(A+E)-\det(A)\right|\leq s_{N-1}\lVert E\rVert_{2}+O(\lVert
E\rVert_{2}^{2}),$

where $s_{N-1}$ is the $(N-1)^{\text{st}}$ elementary symmetric function in
the singular values of $A$ and is upper bounded by
$N\sigma_{1}\cdots\sigma_{N-1}$.

Since $A=K^{*}-I_{\bar{X}}$ is symmetric,
$\\{\sigma_{1}(A),\ldots,\sigma_{N}(A)\\}=\\{|\lambda_{1}(A)|,\ldots,|\lambda_{N}(A)|\\}$.
To bound the singular values of $A$, we recall Weyl’s theorem on the changes
to eigenvalues of a Hermitian matrix that is perturbed. Specifically, the
theorem states that if $A,B$ and $C$ are Hermitian matrices of size $n\times
n$, $C=A+B$, then

$\displaystyle\lambda_{1}(A)+\lambda_{n}(B)$
$\displaystyle\leq\lambda_{1}(C)\leq\lambda_{1}(A)+\lambda_{1}(B)$
$\displaystyle\cdots$ $\displaystyle\cdots\cdots$
$\displaystyle\lambda_{n}(A)+\lambda_{n}(B)$
$\displaystyle\leq\lambda_{n}(C)\leq\lambda_{n}(A)+\lambda_{1}(B)$

Now all the eigenvalues of $K^{*}$ are in $[0,1]$, and all the eigenvalues of
$-I_{\bar{X}}$ are in $\\{-1,0\\}$, therefore, all the eigenvalues of
$A=K^{*}-I_{\bar{X}}$ are in $[-1,1]$. It follows that
$\sigma_{1},\ldots,\sigma_{N}\in[0,1]$ and $s_{N-1}\leq N$.

Since $E=\frac{1}{2}I_{N}-K^{*}$, its eigenvalues are just the corresponding
eigenvalues of $-K^{*}$ but shifted by $\frac{1}{2}$, hence all eigenvalues of
$E$ are in $[-\frac{1}{2},\frac{1}{2}]$ and $\lVert
E\rVert_{2}\leq\frac{1}{2}$.

Now we can plug in all these bounds into Theorem 9 to obtain

$\displaystyle\left|\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}}}[\boldsymbol{Y}=X]-\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=X]\right|$
$\displaystyle\leq\left|\det(K^{*}-I_{\bar{X}})-\det\left(K^{*}-I_{\bar{X}}+\epsilon(\frac{I_{N}}{2}-K^{*})\right)\right|$
$\displaystyle\leq\frac{\epsilon N}{2}+O(\frac{\epsilon^{2}}{4})<\epsilon N,$

for all small enough $\epsilon$.

It follows that, for all small enough $\epsilon$,

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=X]\geq\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}}}[\boldsymbol{Y}=X]-\epsilon
N\geq\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}}}[\boldsymbol{Y}=X](1-Ne^{\log{2}\cdot
N^{2}}\epsilon)\geq\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}}}[\boldsymbol{Y}=X]e^{-O(\epsilon)},$

where the last step follows from the inequality that $1-x\geq
e^{-\frac{3}{2}x}$ for all $0\leq x\leq 1/2$.

Since this lower bound on DPP probability of kernel $K^{*}_{\epsilon}$ holds
for every $X\in\mathcal{S}$, plugging it into the log likelihood estimator (4)
for empirical distribution $D$ proves inequality (7).

####  4.2.2 Proof of inequality (8)

Since $D(\emptyset)=D([N])=0$, we have

$\displaystyle\ell(K^{*}_{\epsilon},D_{\epsilon})$
$\displaystyle=(1-\epsilon)\ell(K^{*}_{\epsilon},D)+\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=\emptyset]}\right)+\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=[N]]}\right)$
$\displaystyle\leq\ell(K^{*}_{\epsilon},D)+\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=\emptyset]}\right)+\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=[N]]}\right).$

We can lower bound
$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=\emptyset]$
and
$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=[N]]$,
using the bounds on $\lambda_{1}(K^{*}_{\epsilon})$ and
$\lambda_{N}(K^{*}_{\epsilon})$ obtained right after the definition of
$K^{*}_{\epsilon}$, as follows.

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=\emptyset]=\det(I-K^{*}_{\epsilon})=\prod_{i=1}^{N}\left(1-\lambda_{i}(K^{*}_{\epsilon})\right)\geq(\frac{\epsilon}{2})^{N}.$

Similarly,

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K^{*}_{\epsilon}}}[\boldsymbol{Y}=[N]]=\det(K^{*}_{\epsilon})=\prod_{i=1}^{N}\lambda_{i}(K^{*}_{\epsilon})\geq(\frac{\epsilon}{2})^{N}.$

Therefore,

$\ell(K^{*}_{\epsilon},D_{\epsilon})\leq\ell(K^{*}_{\epsilon},D)+N\epsilon\log{\frac{2}{\epsilon}}=\ell(K^{*}_{\epsilon},D)+O(\epsilon\log{\frac{1}{\epsilon}}).$

####  4.2.3 Proof of inequality (9)

This follows directly from the fact that $K_{\epsilon}$ is an optimal kernel
for the sample distribution $D_{\epsilon}$.

####  4.2.4 Proof of inequality (10)

Recall that

$\displaystyle\ell(K_{\epsilon},D_{\epsilon})=$
$\displaystyle\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K_{\epsilon}}}[\boldsymbol{Y}=\emptyset]}\right)+\sum_{X\in\mathcal{S}}(1-\epsilon)D(X)\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K_{\epsilon}}}[\boldsymbol{Y}=X]}\right)$
$\displaystyle+\frac{\epsilon}{2}\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K_{\epsilon}}}[\boldsymbol{Y}=[N]]}\right).$

Therefore,

$\displaystyle\ell(K_{\epsilon},D)$
$\displaystyle=\sum_{X\in\mathcal{S}}D(X)\log\left(\frac{1}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K_{\epsilon}}}[\boldsymbol{Y}=X]}\right)$
$\displaystyle\leq\frac{1}{1-\epsilon}\ell(K_{\epsilon},D_{\epsilon})$
$\displaystyle\leq(1+2\epsilon)\ell(K_{\epsilon},D_{\epsilon})\qquad\text{(as
long as $\epsilon\leq 1/2$)}$
$\displaystyle\leq\ell(K_{\epsilon},D_{\epsilon})+(2\log{2})N\epsilon$
$\displaystyle=\ell(K_{\epsilon},D_{\epsilon})+O(\epsilon),$

where in the second last step we use the fact that $K_{\epsilon}$ is an
optimal DPP kernel for $D_{\epsilon}$ and the bound in Fact 1.

####  4.2.5 Putting everything together

Adding inequalities (7), (8), (9) and (10) together yields
$\ell(K_{\epsilon},D)\leq\ell(K^{*},D)+O(\epsilon\log{\frac{1}{\epsilon}})$,
which completes the proof of Proposition 3. ∎

###  4.3 An optimal kernel as a limiting matrix

Let $\varepsilon$ be a small enough positive number so that Proposition 3
holds. Define an infinite decreasing sequence
$\\{\epsilon_{1},\ldots,\epsilon_{k},\ldots\\}$, where
$\epsilon_{k}=\varepsilon/k$. Define an infinite sequence of distributions
$\\{D_{\epsilon_{1}},\ldots,D_{\epsilon_{k}},\ldots\\}$ as in (2) for each
$\epsilon_{k}$. Correspondingly, let
$\\{K_{\epsilon_{1}},\ldots,K_{\epsilon_{k}}\ldots\\}$ be a sequence of
optimal DPP kernels for distributions
$\\{D_{\epsilon_{1}},\ldots,D_{\epsilon_{k}},\ldots\\}$. Note that, since
there can be more than one optimal DPP kernel for each distribution, such an
infinite sequence of kernels is in general not unique. We just fix one such
sequence.

If we view141414Correspondingly, the underlying matrix norm is the Frobenius
norm. the set of all (symmetric) $N\times N$ positive semidefinite matrices
whose maximum eigenvalues are bounded by $1$ as a subset $\mathcal{P}$ of
$\mathbb{R}^{N^{2}}$, then for any $M\in\mathcal{P}$,

$\sum_{i,j=1}^{N}|M_{i,j}|^{2}=\sum_{k=1}^{N}\sigma^{2}_{k}(M)=\sum_{k=1}^{N}\lambda^{2}_{k}(M)\leq
N,$

where $\sigma_{k}(M)$ denotes the $k^{\text{th}}$ singular value of matrix
$M$. It follows that $\mathcal{P}$ is a bounded set.

Consider $\\{K_{\epsilon_{1}},\ldots,K_{\epsilon_{k}},\ldots\\}$, which is an
infinite sequence in $\mathcal{P}$. Recall the Bolzano-Weierstrass theorem,
which states that every bounded infinite sequence in a finite-dimensional
Euclidean space $\mathbb{R}^{N^{2}}$ has a convergent subsequence. Therefore
there exists an infinite sequence of indices $i_{1},\ldots,i_{k},\ldots$ of
$\mathbb{N}$ such that the infinite subsequence of matrices
$\\{K_{\epsilon_{i_{1}}},\ldots,K_{\epsilon_{i_{k}}},\ldots\\}$ converge in
$\mathcal{P}$.

Let $K_{\infty}$ be the limiting matrix of the converging sequence
$\\{K_{\epsilon_{i_{1}}},\ldots,K_{\epsilon_{i_{k}}},\ldots\\}$. That is,

$K_{\infty}:=\lim_{k\to\infty}K_{\epsilon_{i_{k}}}.$

Since each of the marginal kernel in
$\\{K_{\epsilon_{i_{1}}},\ldots,K_{\epsilon_{i_{k}}},\ldots\\}$ satisfies the
diagonal entry condition in (3), so does $K_{\infty}$. That is, for every
$j\in[N]$

$(K_{\infty})_{jj}=\lim_{k\to\infty}(K_{\epsilon_{i_{k}}})_{jj}=\lim_{\epsilon\to
0}\left(\frac{\epsilon}{2}+\sum_{X\in\mathcal{S}:X\ni
j}(1-\epsilon)D(X)\right)=\sum_{X\in\mathcal{S}:X\ni j}D(X).$

Moreover, by Proposition 3,

$\ell(K_{\infty},D)=\lim_{k\to\infty}\ell(K_{\epsilon_{i_{k}}},D)\leq\ell(K^{*},D)+\lim_{k\to\infty}O(\epsilon_{i_{k}}\log{\frac{1}{\epsilon_{i_{k}}}})=\ell(K^{*},D),$

which shows that $K_{\infty}$ is an optimal DPP kernel for the original sample
distribution $D$. This completes the proof of Lemma 3.

##  5 An optimal kernel for $3$-colorable graphs – Proof of Theorem 6

We now prove Theorem 6, which states that if formula $\phi$ is satisfiable
(hence the corresponding BOT graph $G_{\phi}$ is $3$-colorable), then there
exists a rank-$3$ optimal DPP marginal kernel $K$, and the log likelihood
function is $\ell(K)=3\log{m}-\frac{1}{m}\sum_{(u,v)\in
E(G_{\phi})}\left(\log(\deg_{G_{\phi}}(u))+\log(\deg_{G_{\phi}}(v))\right)$.

###### Proof.

From Theorem 5, we can assume that the diagonal of $K$ (indexed by vertices
and edges of $G_{\phi}$) satisfies

$K_{ii}=\begin{cases}\frac{\deg_{G_{\phi}}(u)}{m}&\mathrm{for\;}i=u\in
V(G_{\phi})\\\ \frac{1}{m}&\mathrm{for\;}i=(u,v)\in E(G_{\phi})\\\
\end{cases}.$

We first prove a lower bound on the log likelihood function of any marginal
kernel $K$, by means of the Hadamard inequality.

######  Lemma 4 (Hadamard’s inequality, see e.g. Theorem 7.8.1 in [HJ12]).

For every positive semidefinite matrix $B$, $\det(B)\leq\prod_{i}B_{ii}$, with
equality if and only if $B$ is diagonal.

Therefore, for every example $T=(a_{u},a_{v},a_{(u,v)})\in
E^{\prime}(H_{\phi})$, we can upper bound the probability that marginal kernel
$K$ outputs $T$ as

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=T]\leq\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[T\subseteq\boldsymbol{Y}]=\det({K_{T}})\leq\frac{\deg_{G_{\phi}}(u)}{m}\frac{\deg_{G_{\phi}}(v)}{m}\frac{1}{m}=\frac{\deg_{G_{\phi}}(u)\deg_{G_{\phi}}(v)}{m^{3}},$

The average log likelihood of the DPP associated with any marginal kernel $K$
thus satisfies

$\displaystyle\ell(K)$ $\displaystyle\geq 3\log
m-\frac{1}{m}\displaystyle\sum_{(u,v)\in
E(G_{\phi})}\left(\log\deg_{G_{\phi}}(u)+\log\deg_{G_{\phi}}(v)\right).$

Next, for any $3$-colorable BOT graph $G_{\phi}$, we construct a rank-$3$
marginal kernel $K$ with matching log likelihood function, hence proving the
optimality of the kernel. The kernel $K$ is constructed by the natural
$3$-dimensional embedding induced by the vertex coloring of $G_{\phi}$.

Let $\chi:V(G_{\phi})\to\\{1,2,3\\}$ be a proper $3$-coloring of $G_{\phi}$.
We extend the coloring function $\chi$ to include the edge set $E(G_{\phi})$
in the natural way: for every $(u,v)\in E(G_{\phi})$, let
$\chi((u,v))=\\{1,2,3\\}\setminus\\{\chi(u),\chi(v)\\}$. Since $\chi$ is a
proper coloring of $G_{\phi}$, such an extended definition of $\chi$ is
unambiguous.

Let $\mathbf{e}_{1}=\begin{pmatrix}1\\\ 0\\\ 0\end{pmatrix}$,
$\mathbf{e}_{2}=\begin{pmatrix}0\\\ 1\\\ 0\end{pmatrix}$, and
$\mathbf{e}_{3}=\begin{pmatrix}0\\\ 0\\\ 1\end{pmatrix}$. Let
$N=|V(G_{\phi})|+|E(G_{\phi})|$. Let $Q$, the embedding matrix of coloring
$\chi$, be a $3\times N$ matrix whose columns are indexed by the vertices and
edges of $G_{\phi}$:

$Q=\begin{pmatrix}\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\\\
q_{1}&q_{2}&\cdots&q_{N}\\\
\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\end{pmatrix},$

Each $q_{i}$ is a $3$-dimensional column vector set as follows:

  * •

If $i=u\in V(G_{\phi})$, then set
$q_{i}=\sqrt{\frac{\deg_{G_{\phi}}(u)}{m}}\mathbf{e}_{\chi(u)}$;

  * •

if $i=(u,v)\in E(G_{\phi})$, then set
$q_{i}=\sqrt{\frac{1}{m}}\mathbf{e}_{\chi((u,v))}$.

Finally, define the marginal kernel as $K=Q^{\top}Q$.

Clearly, $\mathrm{rank}(K)=3$. Since $K$ is a Gram matrix, it is positive
semidefinite and the diagonals of $K$ satisfy the conditions specified in
Theorem 5. Next we prove that $\lambda_{1}(K)$ — the largest eigenvalue of $K$
— is equal to $1$, which would imply that $K$ is indeed a DPP marginal kernel.

By Courant-Fischer’s variational formulation of the eigenvalues,

$\lambda_{1}(K)=\sup_{x\in\mathbb{R}^{N},\text{ }\lVert
x\rVert_{2}=1}x^{\top}Kx=\sup_{x\in\mathbb{R}^{N},\text{ }\lVert
x\rVert_{2}=1}\lVert Qx\rVert^{2}.$

For notational convenience, for each column vector in $Q$, let
$q_{i}=\sqrt{p_{i}}\mathbf{e}_{j}$ where $j\in\\{1,2,3\\}$ is the color of
node $i$ in hypergraph $H_{\phi}$. That is,
$p_{i}=\frac{\deg_{G_{\phi}}(i)}{m}$ if node $i$ corresponds to a vertex in
$G_{\phi}$ and $p_{i}=\frac{1}{m}$ if node $i$ corresponds to an edge in
$G_{\phi}$. Let $W_{1}=\sum_{i\in[N]:\chi(\text{node
$i$})=1}x_{i}\sqrt{p_{i}}$, and similarly define $W_{2}$ and $W_{3}$. Also
define $P_{1}$ (respectively $P_{2}$ and $P_{3}$) to be
$W_{1}=\sum_{i\in[N]:\chi(\text{node $i$})=1}p_{i}$. An important observation
is that, since $\chi$ is a proper $3$-coloring of $G_{\phi}$,
$P_{1}=P_{2}=P_{3}=1$.

Clearly

$Qx=\begin{pmatrix}W_{1}\\\ W_{2}\\\ W_{3}\end{pmatrix},$

and by the Cauchy-Schwarz inequality

$W_{1}^{2}\leq\left(\sum_{i\in[N]:\chi(\text{node
$i$})=1}p_{i}\right)\left(\sum_{i\in[N]:\chi(\text{node
$i$})=1}x_{i}^{2}\right)=\sum_{i\in[N]:\chi(\text{node $i$})=1}x_{i}^{2}.$

Similar inequalities hold for $W_{2}$ and $W_{3}$. Therefore,

$\displaystyle\lambda_{1}(K)$ $\displaystyle=\sup_{x\in\mathbb{R}^{N},\text{
}\lVert x\rVert_{2}=1}\lVert Qx\rVert_{2}^{2}=W_{1}^{2}+W_{2}^{2}+W_{3}^{2}$
$\displaystyle\leq\sum_{i\in[N]:\chi(\text{node
$i$})=1}x_{i}^{2}+\sum_{i\in[N]:\chi(\text{node
$i$})=2}x_{i}^{2}+\sum_{i\in[N]:\chi(\text{node $i$})=3}x_{i}^{2}$
$\displaystyle=\sum_{i\in[N]}x_{i}^{2}=1.$

Furthermore, it is easy to see that we can choose $q_{i}$’s such that $q_{i}$
is proportional to $\sqrt{p_{i}}$ for every $i\in[N]$, thus making the Cauchy-
Schwarz inequalities to be equalities. This shows that the spectral norm of
$K$ is indeed one.151515We remark that, for $G_{\phi}$ that is not
$3$-colorable, a marginal kernel constructed from a $3$-coloring may fail to
be an optimal DPP kernel for two reasons. Firstly, such a coloring necessarily
make some edges in $G_{\phi}$ monochromatic, and hence the corresponding DPP
probabilities vanish. Secondly, it may incurs some discrepancy among three
colors. Since $P_{1}+P_{2}+P_{3}=3$ always holds, the discrepancy then implies
$\lambda_{1}(K)=\max\\{P_{1},P_{2},P_{3}\\}>1$, and consequently we need to
scale down the matrix $K$ by a factor larger than one in order to make it a
DPP kernel. This in turn implies that kernel such constructed can not be an
optimal one, as indicated by Theorem 5.

It is well-known that, if $q_{1},\ldots,q_{k}$ are $k$ vectors in an inner
product space and form the $k\times k$ Gram matrix $A$ whose $(i,j)$ entry is
the inner product between $q_{i}$ and $q_{j}$, then $\det(A)$ is equal to the
square of the volume of the $k$-dimensional parallelepiped spanned by
$q_{1},\ldots,q_{k}$. Now by our construction, for every example
$T=(a_{u},a_{v},a_{(u,v)})\in E^{\prime}(H_{\phi})$, the $u^{\text{th}}$,
$v^{\text{th}}$, and $(u,v)^{\text{th}}$ column vectors of $Q$ are pairwise
orthogonal. It follows that, since $\mathrm{rank}(K)=3$,

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=T]=\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[T\subseteq\boldsymbol{Y}]=\det(K_{T})=\frac{\deg_{G_{\phi}}(u)}{m}\frac{\deg_{G_{\phi}}(v)}{m}\frac{1}{m}.$

Consequently,

$\ell(K)=3\log m-\frac{1}{m}\displaystyle\sum_{(u,v)\in
E(G_{\phi})}\left(\log\deg_{G_{\phi}}(u)+\log\deg_{G_{\phi}}(v)\right),$

which completes the proof of the theorem. ∎

##  6 Good rank-$3$ kernels exist – Proof of Theorem 7

In this section we prove Theorem 7, which shows that, if the log likelihood
function is already close to optimal, then there exists correspondingly a
_rank- $3$_ kernels whose log likelihood function is also close (with worse
proximity parameter) to optimal.

######  Theorem 7 (restatement).

Let $G_{\phi}$ be a BOT graph with maximum degree at most $k$. There is a
constant $C_{k}$ depending only on $k$ such that the following holds. Let $K$
be an optimal marginal kernel with likelihood $\ell(K)\leq\ell^{*}+\delta$ for
some $0<\delta\leq 1/(128k)^{2}$, then there exists a marginal kernel
$K^{\prime}$ of dimension $3$ such that
$\ell(K^{\prime})\leq\ell^{*}+C_{k}\delta^{1/4}$.

###  6.1 Proof overview

Without loss of generality, we can assume that the diagonal of $K$ is
consistent with Theorem 5, namely it satisfies that the diagonal is

$K_{ii}=\begin{cases}\frac{\deg_{G_{\phi}}(u)}{m}&\mathrm{for\;}i=u\in
V(G_{\phi})\\\ \frac{1}{m}&\mathrm{for\;}i=(u,v)\in E(G_{\phi})\\\
\end{cases}.$

By our construction of $G_{\phi}$, we may assume that every element
$i\in[m+n]$ occurs in at most $k$ training examples in $\mathcal{T}$ for some
absolute constant $k$.

Since $K$ is PSD, there exists a matrix $Q$ such that $K=Q^{\top}Q$. Let
$q_{1},q_{2},\ldots,q_{N}$ denote the columns of $Q$, and for a set
$T\subseteq[N]$, define $Q_{T}=\mathrm{span}(\\{q_{i}:i\in T\\})$. Recall that
we need to compare

$\ell^{*}=\ell^{*}(K)=3\log m-\frac{1}{m}\displaystyle\sum_{(u,v)\in
E(G_{\phi})}\left(\log\deg_{G_{\phi}}(u)+\log\deg{G_{\phi}}(v)\right),$

which corresponds to an embedding with perfect vector coloring, with

$\ell(K)\geq 3\log{m}-\frac{1}{m}\sum_{(u,v)\in
E(G_{\phi})}\left(\log(\deg_{G_{\phi}}(u))+\log(\deg_{G_{\phi}}(u))+\log(\sin^{2}\theta_{(u,v)})\right).$

Note that $\ell(K)$ can be greater than the RHS above because, for some edge
$(u,v)\in E(G_{\phi})$, the edge vector $q_{(u,v)}$ may not be perpendicular
to the plane spanned by $q_{u}$ and $q_{v}$. Since “vertex” $(u,v)$ in the
hypergraph $H_{\phi}$ is connected only with vertices $u$ and $v$, and our
goal is to maximize the likelihood of $K$ (hence minimize the log likelihood
$\ell(K)$), from now on we assume that $q_{(u,v)}$ is always taken to be
orthogonal to both $q_{u}$ and $q_{v}$, for every $(u,v)\in E(G_{\phi})$.

It is more convenient to work with likelihood functions, which are
$L(K)=\exp(\ell(K))$ and $L^{*}(K)=\exp(\ell^{*}(K))$. After simple
manipulations, we have

$\displaystyle\frac{L^{*}(K)}{L(K)}=\frac{\prod_{(u,v)\in
E(G_{\phi})}\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=\\{u,v,(u,v)\\}]}{\prod_{(u,v)\in
E(G_{\phi})}\|q_{u}\|_{2}^{2}\cdot\|q_{v}\|_{2}^{2}\cdot\|q_{(u,v)}\|_{2}^{2}}=\prod_{(u,v)\in
E(G_{\phi})}\sin^{2}\theta_{(u,v)}\geq\exp(-\delta m),$ (11)

by our assumption that $\ell(K)\leq\ell^{*}+\delta$.

That is, the ratio between the likelihood of a marginal kernel $K$ and the
likelihood of a perfect coloring kernel is just the product of
$\sin^{2}\theta_{(u,v)}$, over all edges $(u,v)\in E(G_{\phi})$.

To construct a good dimension-$3$ kernel $K^{\prime}$ from kernel $K$, our
basic idea is to project each column vector of $Q$ onto a subspace of
dimension $3$ (so that the dimension of the new kernel is at most $3$), and
show that the likelihood does not decrease too much. However, there are
several issues we need to cope with. First, how to find such a subspace?
Second, there can be pairs of column vectors $q_{u}$ and $q_{v}$ of $Q$ such
that the angle $\theta_{(u,v)}$ between them is small, and this angle may
become even smaller or even zero upon projection. Last, there can be column
vectors whose projections onto the subspace have extremely small or even zero
lengths.

Since the log likelihood function of $K$ is close to optimal, there exists an
edge $(u,v)\in E(G_{\phi})$ such that $q_{u}$ and $q_{v}$ are nearly
orthogonal (recall that we always take $q_{(u,v)}$ to be orthogonal to the
plane spanned by $q_{u}$ and $q_{v}$) by a simple probabilistic argument. The
subspace spanned by $\\{q_{u},q_{v},q_{(u,v)}\\}$ will be the dimension-$3$
subspace onto which we project each column vector of $Q$. To tackle the other
two issues mentioned above, we employ a simple counting method and the
negative association property of conditional DPPs to bound the numbers of
column vectors involved in these two bad situations, and apply a greedy
algorithm to assign new directions for these vectors while keep their norms
unchanged. This allows us to lower bound the probabilities of seeing these
“bad edges” under the new DPP kernel. Finally, we lower bound the likelihood
function of the new kernel on the training set by providing an upper bound on
the scaling factor needed to ensure that the new kernel’s eigenvalues are
bounded by $1$.

###  6.2 Finding a good dimension-$3$ subspace

Let $K=Q^{\top}Q$ be a marginal kernel such that $L(K)\geq\exp(-\delta
m)L^{*}(K)$. If $\mathrm{rank}(Q)\leq 3$, we are done. So we assume that
$\mathrm{rank}(Q)>3$. By geometric averaging, there exists a size-$3$ subset
$S=\\{u,v,(u,v)\\}$ such that

$\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=S]\geq\exp(-\delta)\prod_{i\in
S}\|q_{i}\|_{2}^{2}.$

In the following, we use $\bar{S}:=[N]\setminus S$ to denote the complement of
$S$.

Denote the dimension-$3$ subspace spanned by the embedding vectors of these
three elements by $V$, namely

$V=\mathrm{span}\\{q_{u},q_{v},q_{(u,v)}\\}.$

Then $V$ will the subspace onto which we project all column vectors of $Q$.
More importantly, we will show that the average length orthogonal to $V$ of
the column vectors of $Q$ is small.

######  Lemma 5.

Let $V$ be a dimension-$3$ subspace as constructed above, then

$\sum_{i\in\bar{S}}\|\mathrm{proj}_{V^{\perp}}q_{i}\|_{2}^{2}\leq\delta,$

where $V^{\perp}$ denotes the dimension $\mathrm{rank}(Q)-3$ subspace
orthogonal to $V$.

###### Proof.

Let $\boldsymbol{Y}$ be a random set distributed according to the DPP kernel
$K$, and let $\boldsymbol{Y}_{S}$ be a random set which is distributed
according kernel $K$, conditioned on $S$ occurring in $\boldsymbol{Y}_{S}$. It
is well-known that conditioning a DPP on the event that all of the elements in
a fixed set are observed gives rise to another DPP distribution (over the
ground set $\bar{S}$) (see, e.g. [Kul12]). Therefore if we define
$\boldsymbol{Z}:=\boldsymbol{Y}_{S}\setminus S$ as the random set containing
elements outside $S$ which appear in $\boldsymbol{Y}_{S}$, then
$\boldsymbol{Z}$ is distributed as a DPP.161616 In fact, $\boldsymbol{Z}$ is
distributed as a DPP with marginal kernel
$K-K_{\bar{S}S}K_{S}^{-1}K_{S\bar{S}}$ [BR05], where $K_{AB}$ denotes the
submatrix of $K$ consisting of the rows in $A$ and columns in $B$. However,
the actual form of the DPP kernel is unimportant for our argument here.

By our choice of subset $S$,

$\displaystyle\qquad\exp(-\delta)\prod_{i\in
S}\|q_{i}\|_{2}^{2}\leq\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=S]$
$\displaystyle=\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[S\subseteq\boldsymbol{Y}]\cdot\Pr[\boldsymbol{Y}_{S}=S]=\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[S\subseteq\boldsymbol{Y}]\cdot\Pr[\boldsymbol{Z}=\emptyset]$
$\displaystyle=\det(K_{S})\cdot\Pr[\boldsymbol{Z}=\emptyset].$

Since $\det(K_{S})\leq\prod_{i\in S}\|q_{i}\|_{2}^{2}$, it follows that
$\Pr[\boldsymbol{Z}=\emptyset]\geq\exp(-\delta)$.

Recall that a set of random variables
$\boldsymbol{X}_{1},\boldsymbol{X}_{2},\ldots,\boldsymbol{X}_{N}$ is said to
be _negatively associated_ (NA) if for any two disjoint index subsets
$S,T\subset[N]$ and any two functions $f,g$ that depend only on variables in
subsets $S$ and $T$ respectively, and are either both monotone increasing or
both monotone decreasing, we have

$\mathrm{E}\left[f(\boldsymbol{X}_{i}:i\in S)\cdot g(\boldsymbol{X}_{j}:j\in
T)\right]\leq\mathrm{E}\left[f(\boldsymbol{X}_{i}:i\in
S)\right]\cdot\mathrm{E}\left[g(\boldsymbol{X}_{j}:j\in T)\right].$

Lyons [Lyo03] proved that the indicator random variables of elements in the
set are negatively associated if the probability distribution on the set is a
DPP.

######  Claim 3.

If $\boldsymbol{X}_{1},\boldsymbol{X}_{2},\ldots,\boldsymbol{X}_{N}$ are
negatively associated $\\{0,1\\}$-valued random variables such that
$\Pr[\bigwedge_{i=1}^{N}(\boldsymbol{X}_{i}=0)]\geq\exp(-\alpha)$, then
$\mathrm{E}[\sum_{i=1}^{N}\boldsymbol{X}_{i}]\leq\alpha$.

###### Proof.

First of all, define
$f_{i}(\boldsymbol{X}_{i}):=\mathbbm{1}{(\boldsymbol{X}_{i}=0)}$ for every
$i\in[N]$. Note that for disjoint subsets $S$ and $T$, $f:=\prod_{i\in
S}f_{i}$ and $g:=\prod_{i\in T}f_{i}$ depend on disjoint subsets of variables
and are both monotone decreasing. Therefore, applying inductively the
negatively associated property of
$\boldsymbol{X}_{1},\boldsymbol{X}_{2},\ldots,\boldsymbol{X}_{N}$, we have
$\mathrm{E}\left[\prod_{i\in[N]}f_{i}(\boldsymbol{X}_{i})\right]\leq\prod_{i\in[N]}\left(\mathrm{E}[f_{i}(\boldsymbol{X}_{i})]\right)$,
or equivalently

$\Pr[\bigwedge_{i=1}^{N}(\boldsymbol{X}_{i}=0)]\leq\prod_{i=1}^{N}\Pr[\boldsymbol{X}_{i}=0].$

Therefore,

$\displaystyle\exp(-\alpha)$
$\displaystyle\leq\Pr[\bigwedge_{i=1}^{N}(\boldsymbol{X}_{i}=0)]\leq\prod_{i=1}^{N}\Pr[\boldsymbol{X}_{i}=0]$
$\displaystyle=\prod_{i=1}^{N}(1-\Pr[\boldsymbol{X}_{i}=1])\leq\prod_{i=1}^{N}\exp(-\Pr[\boldsymbol{X}_{i}=1])$
$\displaystyle=\exp(-\sum_{i=1}^{N}\Pr[\boldsymbol{X}_{i}=1])=\exp(-\mathrm{E}[\sum_{i=1}^{N}\boldsymbol{X}_{i}]).$

Hence the claim follows. ∎

######  Claim 4.

Let $\boldsymbol{Z}$ be the random set containing elements outside $S$ which
appear in $\boldsymbol{Y}_{S}$ as before, then
$\mathrm{E}[|\boldsymbol{Z}|]\leq\delta$.

###### Proof.

Define $\boldsymbol{X}_{i}$ to be the $\\{0,1\\}$-indicator random variable
corresponding to the event $i\in\boldsymbol{Z}$ for each $i\in\bar{S}$. Then
applying Claim 3 to these variables, and observing that
$|\boldsymbol{Z}|=\sum_{i\in\bar{S}}\boldsymbol{X}_{i}$ proves the claim. ∎

Now we have

$\mathrm{E}[|\boldsymbol{Z}|]=\sum_{i\in\bar{S}}\Pr[i\in\boldsymbol{Z}]=\sum_{i\in\bar{S}}\frac{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[S\cup\\{i\\}\subseteq\boldsymbol{Y}]}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[S\subseteq\boldsymbol{Y}]}=\sum_{i\in\bar{S}}\frac{\det(K_{S\cup\\{i\\}})}{\det(K_{S})},$

and interpreting the determinants as squared volumes of parallelepipeds, we
have

$\sum_{i\in\bar{S}}\frac{\det(K_{S\cup\\{i\\}})}{\det(K_{S})}=\sum_{i\in\bar{S}}\|\mathrm{proj}_{V^{\perp}}q_{i}\|_{2}^{2}$

and applying Claim 4 completes the proof. ∎

###  6.3 Bounding the number of “bad” vertices

Let $\epsilon_{0}<\frac{1}{8}$ be a fixed constant. Define

$B_{e}=\\{(u,v)\in E(G_{\phi}):\sin^{2}\theta_{(u,v)}<\epsilon_{0}\\}.$

######  Lemma 6.

The size of $B_{e}$ can be upper bounded as $|B_{e}|\leq\delta m$.

###### Proof.

If we rewrite (11) as

$\exp(-\delta m)L^{*}(K)\leq L(K)\leq L^{*}(K)\prod_{(u,v)\in
E(G_{\phi})}\sin^{2}\theta_{(u,v)},$

then

$\exp(-\delta m)\leq\prod_{(u,v)\in
E(G_{\phi})}\sin^{2}\theta_{(u,v)}<{\epsilon_{0}}^{|B_{e}|}.$

Taking logarithms on both sides yields $-\delta
m\leq|B_{e}|(\log\epsilon_{0})\leq|B_{e}|\log(1/8)$, so
$|B_{e}|\leq\dfrac{\delta m}{\log{8}}\leq\delta m/2$. ∎

Define $B_{1}$ as the set of “bad” vertices of the first kind; that is, the
set of vertices whose embedding vectors that are too close to some of their
neighboring (in graph $G_{\phi})$) embedding vectors:

$B_{1}=\\{u\in V(G_{\phi}):\exists
v\mathrm{\;such\;that\;}\sin^{2}\theta_{(u,v)}<\epsilon_{0}\\}.$

Then clearly,

$\displaystyle|B_{1}|\leq 2|B_{e}|\leq\delta m.$ (12)

###  6.4 Assigning projections for “bad vectors”

Define $B_{2}$ to be the set of “bad” vertices of the second kind; these are
vertices whose embedding vectors’ (relative) norms along $V^{\perp}$ are not
small (consequently, the norms of the projections onto $V$ of such vectors are
not large enough):

$B_{2}=\\{i\in[N]:\|\mathrm{proj}_{V^{\perp}}q_{i}\|_{2}^{2}\geq\sqrt{\delta}\|q_{i}\|_{2}^{2}\\}.$

Let $B:=B_{1}\cup B_{2}$ be the set of all “bad” vertices (correspondingly,
“bad” embedding vectors). We will call a vertex (and its corresponding
embedding vector) “good” if it is not “bad”.

First of all, since $\|q_{i}\|_{2}^{2}\geq\frac{1}{m}$ for each $i\in[N]$, by
Lemma 5, the size of $B_{2}$ can be bounded by

$\displaystyle|B_{2}|\leq\sqrt{\delta}m.$ (13)

Combined with (12), this gives

$\displaystyle|B|\leq 2\sqrt{\delta}m.$ (14)

For every “good” vertex $u\notin B$, let

Assigning embedding vectors for “good” vertices
$q_{u}^{\prime}\leftarrow\mathrm{proj}_{V}q_{u}$

What about “bad” vertices? For each $v\in B$, we will use the greedy algorithm
outlined in Fig. 5 to find a good direction $\mathbf{z}$ (as the direction of
its new embedding vector $q^{\prime}_{v}$) so that the angle between
$\mathbf{z}$ and the new embedding vector of any neighbor (in graph
$G_{\phi}$) of $v$ is not too small. Note that in the description of the
algorithm, we assume that the the projection subspace $V=\mathbb{R}^{3}$ and
use $\theta(x,y)$ to denote the angle between any two vectors $x$ and $y$ in
$\mathbb{R}^{3}$.

######  Claim 5.

There is an absolute constant $\tau_{k}$ depending on $k$ only such that, for
all $(u,v)\in E(G_{\phi})$ with at least one of $u$ and $v$ is “bad”, the
angle between their new embedding vectors satisfies that
$\sin^{2}\theta(q^{\prime}_{u},q^{\prime}_{v})\geq\tau_{k}$.

###### Proof.

Recall that every element $u\in V(G_{\phi})$ has at most $k$ neighbors in
$V(G_{\phi})$. Then we can take $\tau_{k}$ to be the solution to the following
optimization problem

$\displaystyle\min_{x_{1},x_{2},\ldots,x_{k}\in S^{2}}\max_{y\in
S^{2}}\min_{i}\sin^{2}\theta(x_{i},y),$

Observe that $\tau_{k}$ is an absolute constant between $0$ and $1$. Indeed,
one can obtain a simple lower bound on $\tau_{k}$ as follows: let $r_{k}$ be
the maximum radius of a spherical cap such that $k+1$ identical such caps can
be placed disjointly on the surface of a unit sphere. Now for any
configuration of $x_{1},x_{2},\ldots,x_{k}\in S^{2}$, at least one cap will
contain no $x_{i}$. Letting $y$ be the center of such a cap is a certificate
that $\tau_{k}\geq r_{k}^{2}$. ∎

Assigning embedding vectors for “bad” vertices 1. order all $n$ vertices
arbitrarily 2. for each $v\in V(G_{\phi})$ If $v$ is “good” continue (that is,
$q^{\prime}_{v}\leftarrow\mathrm{proj}_{V}q_{v}$ as we did before) Else ($v$
is “bad”) let $\mathcal{N}$ be the set of neighboring vertices of $v$ that
appear before $v$ let $\mathbf{z}=\mathrm{argmax}\displaystyle\max_{y\in
S^{2}}\min_{u\in\mathcal{N}}\sin^{2}\theta(u,y)$ (such maximal direction in
general is not unique: any one works) assign
$q^{\prime}_{v}\leftarrow\|q_{v}\|_{2}\mathbf{z}$

Figure 5: Algorithm for computing the new embedding vector for “bad” vertices.

Once we set new embedding vector for every vertex $v\in V(G_{\phi})$, let

$Q^{\prime}=\begin{pmatrix}\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\\\
q^{\prime}_{1}&q^{\prime}_{2}&\cdots&q^{\prime}_{N}\\\
\rule[-4.30554pt]{0.5pt}{10.76385pt}&\rule[-4.30554pt]{0.5pt}{10.76385pt}&&\rule[-4.30554pt]{0.5pt}{10.76385pt}\end{pmatrix},$

and set

$K^{\prime}=\beta(Q^{\prime})^{\top}Q^{\prime},$

where $\beta$ is a parameter to be determined later to make the eigenvalues of
$K^{\prime}$ at most $1$.

###  6.5 Bounding the likelihood function of the new kernel

To lower bound the likelihood function of new kernel $K^{\prime}$ on the
training set, we compare the probabilities of kernels $K$ and $K^{\prime}$
seeing an arbitrary subset $T:=\\{u,v,(u,v)\\}$ in the training set. We
distinguish between two cases.

##### Both $u$ and $v$ are “good” vertices.

Since $u$ is “good”, the angle $\theta^{\prime}_{u}$ between $q_{u}$ and its
projection $q_{u}^{\prime}$ is small. Indeed, since
$\|q_{u}^{\prime}\|_{2}^{2}>(1-\sqrt{\delta})\|q_{u}\|_{2}^{2}$, we have
$\sin{\theta^{\prime}_{u}}<\delta^{1/4}$, or
$\theta^{\prime}_{u}<\sin^{-1}\delta^{1/4}\leq\frac{2}{\pi}\delta^{1/4}<\delta^{1/4}$.
It follows that, if both $u$ and $v$ are “good” vertices, and denote the angle
between their projected vectors by $\theta^{\prime}_{(u,v)}$, then we have

$\displaystyle\theta^{\prime}_{(u,v)}>\epsilon_{0}-2\delta^{1/4},$ (15)

by triangle inequality.

Therefore, we have

$\displaystyle\;\quad\frac{\Pr_{\boldsymbol{Y}^{\prime}\sim\mathcal{P}_{K^{\prime}}}[\boldsymbol{Y}^{\prime}=\\{u,v,(u,v)\\}]}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=\\{u,v,(u,v)\\}]}\geq\frac{\Pr_{\boldsymbol{Y}^{\prime}\sim\mathcal{P}_{K^{\prime}}}[\boldsymbol{Y}^{\prime}=\\{u,v,(u,v)\\}]}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\\{u,v,(u,v)\\}\subseteq\boldsymbol{Y}]}$
$\displaystyle=\frac{\det(K^{\prime}_{T})}{\det(K_{T})}\qquad\text{(since
$K^{\prime}$ is a dimension-$3$ DPP marginal kernel)}$
$\displaystyle=\beta^{3}\dfrac{\|q^{\prime}_{u}\|^{2}_{2}\|q^{\prime}_{v}\|^{2}_{2}\sin^{2}\theta^{\prime}_{(u,v)}}{\|q_{u}\|^{2}_{2}\|q_{v}\|^{2}_{2}\sin^{2}\theta_{(u,v)}}$
$\displaystyle\geq\beta^{3}(1-\sqrt{\delta})^{2}\dfrac{\sin^{2}(\epsilon_{0}-2\delta^{1/4})}{\sin^{2}\epsilon_{0}}\qquad\text{($\|q^{\prime}_{i}\|^{2}_{2}/\|q_{i}\|^{2}_{2}>1-\sqrt{\delta}$
for ``good'' embedding vectors and using \eqref{ineq:bound-on-new-angle})}$
$\displaystyle\geq\beta^{3}(1-\sqrt{\delta})^{2}\left(1-\frac{2\delta^{1/4}}{\sin^{2}\epsilon_{0}}\right)\qquad\text{(using
the fact that $|\frac{\mathrm{d}}{\mathrm{d}x}(\sin^{2}x)|\leq 1$ for all
$x$)}$
$\displaystyle\geq\beta^{3}(1-\sqrt{\delta})\left(1-\frac{3\delta^{1/4}}{\sin^{2}\epsilon_{0}}\right),$

where the factor $\beta^{3}$ comes from the scaling factor $\beta$ in our
definition of $K^{\prime}$, and the fact that these probabilities are
determinants of $3\times 3$ principal minors of
$\beta(Q^{\prime})^{\top}Q^{\prime}$.

##### At least one of $u$ and $v$ is “bad”.

Using Claim 5, we have for such edges

$\displaystyle\;\quad\frac{\Pr_{\boldsymbol{Y}^{\prime}\sim\mathcal{P}_{K^{\prime}}}[\boldsymbol{Y}^{\prime}=\\{u,v,(u,v)\\}]}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=\\{u,v,(u,v)\\}]}\geq\frac{\Pr_{\boldsymbol{Y}^{\prime}\sim\mathcal{P}_{K^{\prime}}}[\boldsymbol{Y}^{\prime}=\\{u,v,(u,v)\\}]}{\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\\{u,v,(u,v)\\}\subseteq\boldsymbol{Y}]}=\frac{\det(K^{\prime}_{T})}{\det(K_{T})}$
$\displaystyle=\beta^{3}\dfrac{\|q^{\prime}_{u}\|^{2}_{2}\|q^{\prime}_{v}\|^{2}_{2}\sin^{2}\theta^{\prime}_{(u,v)}}{\|q_{u}\|^{2}_{2}\|q_{v}\|^{2}_{2}\sin^{2}\theta_{(u,v)}}$
$\displaystyle\geq\beta^{3}(1-\sqrt{\delta})\tau_{k},$

since at least one of $u$ and $v$ is a “bad” vertex, and
$\|q^{\prime}_{i}\|^{2}_{2}/\|q_{i}\|^{2}_{2}=1$ for such vertices.

##### Putting the two cases together.

$\displaystyle\;\quad\frac{L(K^{\prime})}{L(K)}=\frac{\prod_{(u,v)\in
E(G_{\phi})}\Pr_{\boldsymbol{Y}^{\prime}\sim\mathcal{P}_{K^{\prime}}}[\boldsymbol{Y}^{\prime}=\\{u,v,(u,v)\\}]}{\prod_{(u,v)\in
E(G_{\phi})}\Pr_{\boldsymbol{Y}\sim\mathcal{P}_{K}}[\boldsymbol{Y}=\\{u,v,(u,v)\\}]}$
$\displaystyle\geq\displaystyle\prod_{\begin{subarray}{c}(u,v)\in
E(G_{\phi})\\\ u\notin B\text{ and }v\notin
B\end{subarray}}\beta^{3}(1-\sqrt{\delta})\left(1-\dfrac{3\delta^{1/4}}{\sin^{2}\epsilon_{0}}\right)\displaystyle\prod_{\begin{subarray}{c}(u,v)\in
E(G_{\phi})\\\ u\in B\text{ or }v\in
B\end{subarray}}\beta^{3}(1-\sqrt{\delta})\tau_{k}$
$\displaystyle\geq\beta^{3m}(1-\sqrt{\delta})^{m}\left(1-\dfrac{3\delta^{1/4}}{\sin^{2}\epsilon_{0}}\right)^{m-k|B|}\tau_{k}^{k|B|}$
$\displaystyle\geq\beta^{3m}(1-\sqrt{\delta})^{m}\left(1-\dfrac{3\delta^{1/4}}{\sin^{2}\epsilon_{0}}\right)^{(1-2k\sqrt{\delta})m}\tau_{k}^{2k\sqrt{\delta}m}$
$\displaystyle\geq\beta^{3m}\exp\left[-\left(\frac{3\delta}{2}+\dfrac{3\delta^{1/4}}{\sin^{2}\epsilon_{0}}(1-2k\sqrt{\delta})+2k\log(\frac{1}{\tau_{k}})\sqrt{\delta}\right)m\right]$
$\displaystyle\geq\beta^{3m}\exp\left(-C^{\prime\prime}_{k}\delta^{1/4}m\right),$

where $C^{\prime\prime}_{k}$ is some constant depending only on $k$ and in the
second last step we use the inequality $1-x\geq\exp(-3x/2)$ for all $0\leq
1/2\leq x$. It follows that

$\displaystyle\quad\frac{L(K^{\prime})}{L^{*}(K)}\geq\beta^{3m}\exp\left(-C^{\prime\prime}_{k}\delta^{1/4}m\right)\cdot\exp(-\delta
m)\geq\beta^{3m}\exp\left(-C^{\prime}_{k}\delta^{1/4}m\right),$ (16)

for some absolute constant $C^{\prime}_{k}$ depending on $k$ only.

###  6.6 Bounding the scaling factor $\beta$

We finish the proof by providing a lower bound on $\beta$. First, we consider
$K^{\prime\prime}=(Q^{\prime\prime})^{\top}Q^{\prime\prime}$, where the
$i^{\text{th}}$ column of $Q^{\prime\prime}$ is $\mathrm{proj}_{V}q_{i}$ for
_every_ $i\in[N]$. Recall that the spectral norm of a matrix $A$, $\|A\|_{2}$,
is the largest singular value of $A$, we have
$\|Q^{\prime\prime}\|_{2}\leq\|Q\|_{2}\leq 1$, as $Q^{\prime\prime}$ is a
projection onto a subspace spanned by a subset of its columns. By our bound on
the number of “bad” embedding vectors (14), at most $2\sqrt{\delta}m$ of the
columns of $Q^{\prime}$ are not the same projection as in $Q^{\prime\prime}$.
Each column is replaced by a vector of the same length, which is at most
$\sqrt{k/m}$. We use the Frobenius norm of $Q^{\prime\prime}-Q^{\prime}$ to
upper bound its spectral norm as follows. For every “bad” vertex $i$,

$\|q_{i}-q^{\prime}_{i}\|_{2}^{2}=\|q_{i}\|_{2}^{2}+\|q^{\prime}_{i}\|_{2}^{2}-2\langle
q_{i},q^{\prime}_{i}\rangle\leq 4\|q_{i}\|_{2}^{2}\leq 4k/m.$

Therefore,

$\|Q^{\prime\prime}-Q^{\prime}\|_{2}^{2}\leq\|Q^{\prime\prime}-Q^{\prime}\|^{2}_{F}=\sum_{i=1}^{N}\|q_{i}-q^{\prime}_{i}\|_{2}^{2}=\sum_{i\in
B}\|q_{i}-q^{\prime}_{i}\|_{2}^{2}\leq 2\sqrt{\delta}m\cdot
4k/m=8k\sqrt{\delta}.$

Now, by the triangle inequality, we have

$\|Q^{\prime}\|_{2}\leq\|Q^{\prime\prime}\|_{2}+\|Q^{\prime\prime}-Q^{\prime}\|_{2}\leq
1+\sqrt{8k\sqrt{\delta}}.$

In order for $K^{\prime}=\beta Q^{\top}Q$ to be the marginal kernel of a DPP,
we need to ensure that $\|K^{\prime}\|_{2}\leq 1$. As
$\|K^{\prime}\|_{2}=|\beta|\|Q^{\top}Q\|_{2}=|\beta|\|Q\|_{2}^{2}$, we can
take $\beta=\frac{1}{(1+\sqrt{8k\sqrt{\delta}})^{2}}\geq
1-2\sqrt{8k\sqrt{\delta}}=1-\sqrt{32k\sqrt{\delta}}\geq\exp\left(-\sqrt{72k}\delta^{1/4}\right)$.

Finally, plugging the bound
$\beta\geq\exp\left(-\sqrt{72k}\delta^{1/4}\right)$ into (16) to get that

$\quad\frac{L(K^{\prime})}{L^{*}(K)}\geq\beta^{3m}\exp\left(-C^{\prime}_{k}\delta^{1/4}m\right)\geq\exp\left(-\sqrt{648k}\delta^{1/4}m\right)\cdot\exp\left(-C^{\prime}_{k}\delta^{1/4}m\right)=\exp\left(-C_{k}\delta^{1/4}m\right),$

where $C_{k}=C^{\prime}_{k}+\sqrt{648k}$. Or equivalently,
$\ell(K^{\prime})\leq\ell^{*}+C_{k}\delta^{1/4}$ for some constant $C_{k}$
which depends only on $k$. This completes the proof of Theorem 7.

##  7 Putting it all together – Proof of Theorem 8

Now it is time to assemble the parts we have built so far and prove the
following soundness theorem, which basically says that there must be a gap
between the log likelihood functions of the training set derived from the YES
instance BOT graph and that from the NO instance BOT graph.

######  Theorem 8 (Soundness theorem, restatement).

Let $\ell^{*}$ be the optimal log likelihood as in Theorem 6. Then there
exists a constant $C>0$ which depends only on $k$ and $\epsilon^{\prime}$ as
those defined in Theorem 2, such that the following holds. If there is a DPP
marginal kernel $K$ of rank $3$, which satisfies
$\ell(K)\leq\ell^{*}+\frac{C}{\log^{2}{n}}$ where $n=|V(G_{\phi})|$ is the
number of vertices in the BOT graph, then there is a truth assignment that
satisfies at least $(1-\epsilon)$ fraction of the clauses in $\phi$, where
$\epsilon$ is the constant defined in Theorem 1.

In conventional graph coloring, a coloring $\chi:V\to\\{c_{1},\ldots,c_{k}\\}$
_satisfies_ an edge $(u,v)$ if the edge is non-monochromatic, i.e.
$\chi(u)\neq\chi(v)$. In other words, an edge connecting $u$ and $v$ forces
the colors of the two vertices to be different. In vector coloring, the notion
of edge $(u,v)$ being non-monochromatic is generalized to vectors assigned to
$u$ and $v$ being (almost) orthogonal. From Lemma 2 we know that an “almost
perfect” $3$-coloring of the vertices in $G_{\phi}$ can be used to decode a
truth assignment that satisfies “almost all” the clauses in $\phi$. However,
in our maximum likelihood DPP learning reduction, we represent vertices by
their embedding vectors and work with vector coloring accordingly, therefore
it is natural to ask: Given an _almost_ perfect vector $3$-coloring of the
vertices in $G_{\phi}$, can we still decode a truth assignment that satisfies
“almost all” the clauses in $\phi$, like what we did from a $3$-coloring of
$G_{\phi}$? Our key observation is that the equality gadgets and clause
gadgets in [BOT02] are “robust” even for a vector $3$-coloring, with the help
of several simple facts about spherical geometry.

From now on, for any vector $v\in\mathbb{R}^{3}$, we use $(v_{1},v_{2},v_{3})$
to denote its Cartesian coordinates.

######  Claim 6.

Let $a,b,c,d\in S^{2}$ be unit vectors in $\mathbb{R}^{3}$ and let $0\leq
t\leq 1/5$. If $|\langle a,b\rangle|\leq t$, $|\langle b,c\rangle|\leq t$,
$|\langle c,a\rangle|\leq t$, $|\langle d,b\rangle|\leq t$, then $|\langle
a,d\rangle|\geq 1-5t^{2}$.

Intuitively, if vectors $a,b$ and $c$ in $S^{2}$ are close to forming an
orthonormal basis, and a fourth vector $d\in S^{2}$ is almost orthogonal to
both $b$ and $c$, then $d$ is necessarily close to $a$.

###### Proof.

Without loss of generality, assume that $b=(0,0,1)$. Then
$0\leq|a_{3}|,|c_{3}|,|d_{3}|\leq t$. Let $a^{\prime},c^{\prime}$ and
$d^{\prime}$ be the projection to the $X$-$Y$ plane of $a,c$ and $d$,
respectively. Note that $\lVert a^{\prime}\rVert,\lVert
c^{\prime}\rVert,\lVert d^{\prime}\rVert\geq\sqrt{1-t^{2}}$, and since
$|\langle a,c\rangle|\geq\langle a^{\prime},c^{\prime}\rangle-|a_{3}||c_{3}|$,
we have $|\langle a^{\prime},c^{\prime}\rangle|\leq t+t^{2}$. Similarly,
$|\langle d^{\prime},c^{\prime}\rangle|\leq t+t^{2}$.

Without loss of generality, assume that $c^{\prime}=(0,\lVert
c^{\prime}\rVert)$. Then, because $|\langle a^{\prime},c^{\prime}\rangle|\leq
t+t^{2}$ and $\lVert c^{\prime}\rVert\geq\sqrt{1-t^{2}}$, we have
$|a_{2}|\leq\frac{t+t^{2}}{\sqrt{1-t^{2}}}$, and consequently $|a_{1}^{2}|\geq
1-t^{2}-\left(\frac{t+t^{2}}{\sqrt{1-t^{2}}}\right)^{2}$. Similar bounds hold
for $d$. Now

$\displaystyle|\langle a,d\rangle|$ $\displaystyle\geq|\langle
a,d\rangle|-|a_{3}||d_{3}|$
$\displaystyle\geq|a_{1}||d_{1}|-|a_{2}||d_{2}|-t^{2}$ $\displaystyle\geq
1-t^{2}-\left(\frac{t+t^{2}}{\sqrt{1-t^{2}}}\right)^{2}-\frac{t^{2}(1+t)^{2}}{1-t^{2}}-t^{2}$
$\displaystyle=1-2t^{2}-2t^{2}\frac{1+t}{1-t}$ $\displaystyle\geq 1-5t^{2},$

where the last step we use $\frac{1+t}{1-t}\leq 3/2$ for $0\leq t\leq 1/5$. ∎

######  Corollary 1.

Let $a,b,c,d$ be unit vectors in $S^{2}$ satisfy that
$\frac{\pi}{2}-\theta\leq\theta_{(a,b)},\theta_{(a,c)},\theta_{(b,c)},\theta_{(b,d)},\theta_{(c,d)}\leq\pi/2$
with $0\leq\theta\leq\theta_{0}=\sin^{-1}(1/5)$. Then $\theta_{(a,d)}\leq
3\theta$.

###### Proof.

Let $(x,y)\in\\{(a,b),(a,c),(b,c),(b,d),(c,d)\\}$ and $t=\sin\theta$. Then
$|\langle x,y\rangle|=\cos\theta_{(x,y)}\leq\cos(\pi/2-\theta)=\sin\theta=t$,
so by Claim 6, $|\langle a,d\rangle|\geq 1-5\sin^{2}\theta$. It follows that
$\theta_{(a,d)}\leq\cos^{-1}(1-5\sin^{2}\theta)\leq 3\theta$, because
$\sin^{2}(3\alpha)\geq 5\sin^{2}\alpha$ for all $0\leq\alpha\leq\pi/7$ and
$\theta_{0}<\pi/7$. ∎

The following Claim facilitates transforming between the angle between a pair
of vectors in $S^{2}$ and their inner product, especially for the cases when
the two vectors are almost orthogonal or very close to each other.

######  Claim 7.

We have the following inequalities between inner product of unit vectors and
the angle between them.

  1. 1.

Suppose $0\leq\theta\leq\pi/2$ and $\sin^{2}\theta=1-\epsilon$ for some
$0\leq\epsilon<1$. Let $\alpha:=\pi/2-\theta$ be the angular distance between
$\theta$ and $\pi/2$. Then
$\sqrt{\epsilon}\leq\alpha\leq\frac{\pi}{2}\sqrt{\epsilon}$.

  2. 2.

If $u,v\in S^{2}$ and $|\langle u,v\rangle|=\epsilon$ (i.e. $u$ and $v$ are
close to orthogonal), and let $\alpha:=\pi/2-\theta_{(u,v)}$ be the angular
distance between $\theta_{(u,v)}$ and $\pi/2$, then
$\epsilon\leq\alpha\leq\frac{\pi}{2}\epsilon$.

  3. 3.

If $u,v\in S^{2}$ and $|\langle u,v\rangle|=1-\epsilon$ (i.e. $u$ and $v$ are
$\epsilon$-close), then
$\sqrt{2\epsilon}\leq\theta_{(u,v)}\leq\frac{\pi}{\sqrt{2}}\sqrt{\epsilon}$.

###### Proof.

Item $1$ follows from the equality $\sin^{2}{\alpha}=\epsilon$ and the fact
that, for $\alpha\in[0,\pi/2]$,
$\frac{2}{\pi}\alpha\leq\sin{\alpha}\leq\alpha$. Item $2$ follows directly
from the above inequality. For Item $3$, since
$\sin{\theta_{(u,v)}}=1-\epsilon$,
$\sin^{2}\frac{\theta_{(u,v)}}{2}=\epsilon^{2}/2$. Now apply Item $1$ to
$\frac{\theta_{(u,v)}}{2}$. ∎

######  Remark 2.

Note that our vector $3$-coloring only specifies the inner-product between any
pair of vertex vectors $\chi^{\top}(u)\chi(v)$, and for the purpose of proving
hardness of DPP learning, all we care is
$\sin^{2}\theta_{(u,v)}=1-|\chi^{\top}(u)\chi(v)|^{2}$. This information does
not uniquely determine all the vertex vectors on $S^{2}$ though, even if we
fix certain vertex vector to be $(1,0,0)$, say. This is because, for a fixed
vector $\chi(v)$, $\chi(u)$ and $-\chi(u)$ give rise to the same value of
$\sin^{2}\theta_{(u,v)}$. Therefore, from now on, we will not distinguish
between $\chi(u)$ and $-\chi(u)$, and always assume $\theta_{(u,v)}$ to be in
$[0,\pi/2]$.

Now we can show that the equality gadget in Fig. 3(a) is robust against small
noise.

######  Lemma 7 (The equality gadget is robust).

Let $\chi:V(G_{\phi})\to S^{2}$ be a vector $3$-coloring which satisfies that
$\theta_{(u,v)}\geq\pi/2-\delta$ for every $(u,v)\in E(G_{\phi})$. Then, for
the the equality gadget in Fig. 3(a), the angle between node $x$ and node $y$
is at most $3\delta$.

###### Proof.

This follows directly by plugging $a=\chi(x)$, $b=\chi(y)$, $c=\chi(u)$ and
$d=\chi(v)$ into Corollary 1. ∎

The case of clause gadget requires a bit more work. Note that we make no
attempt to optimize the robustness parameters in the following statements, but
focus on arguing qualitatively that the clause gadgets are robust against
small noise.

Abusing notation, in the following, we use the names of nodes in the gadget to
also denote the coloring vectors of the nodes.

######  Lemma 8 (The clause gadget is robust).

Let $\chi:V(G_{\phi})\to S^{2}$ be a vector $3$-coloring which satisfies that
$\theta_{(u,v)}\geq\pi/2-\delta_{e}$ for every $(u,v)\in E(G_{\phi})$, where
$\delta_{e}=o(1)$ for our BOT hypergraph setting. Further, assume that for any
pair of two True nodes in the clause gadgets as shown in Fig. 3(b) or for any
pair of two Dummy nodes in the literal blocks as shown in Fig. 2, the angle
between the two color vectors $u$ and $v$ satisfy that
$\theta_{(u,v)}\leq\delta_{p}$, where $\delta_{p}=\pi/300$ is some small
absolute constant. Consider the clause gadget as shown in Fig. 3(b). Then at
least one of the three literals must be “assigned” value True in the sense
that its color vector is close to that of its corresponding True node: there
exists at least one $i\in\\{a,b,c\\}$ such that
$|\langle\ell_{i},T_{i}\rangle|>t_{0}$, where $t_{0}=0.98$ (this corresponds
to $\theta_{(\ell_{i},T_{i})}<\pi/15$).

We first need to argue about the coloring vectors of a simplified clause
gadget as shown in Fig. 6.

$T$$\ell$$u$$D$ Figure 6: The simplified clause gadget.

######  Claim 8.

Let $D,T,u,\ell\in S^{2}$ be unit vectors in $\mathbb{R}^{3}$ and $t_{0}=0.98$
as in Lemma 8. Suppose that $|\langle D,T\rangle|\leq\epsilon$, $|\langle
D,\ell\rangle|\leq\epsilon$, $|\langle u,T\rangle|\leq\epsilon$, $|\langle
u,\ell\rangle|\leq\epsilon$. If $|\langle T,\ell\rangle|\leq t_{0}$, then
$|\langle D,u\rangle|\geq 1-202\epsilon^{2}$.

Basically the Claim asserts that if the vector $3$-coloring satisfies all four
edges in the gadget with closeness parameter $1-\epsilon$, then if vectors $T$
and $\ell$ are not close to each other, this would force vectors $D$ and $u$
to be aligned along almost the same direction — or equivalently, be assigned
to the same “color” (note that if $T$ and $\ell$ are very close, then $u$
would have the freedom to choose between the color of $D$ or the color that is
“orthogonal” to both $T$ and $D$; namely, the color of False nodes).

###### Proof.

For convenience, we take the plane spanned by $T$ and $\ell$ to be the $X$-$Y$
plane and in particular set $T=(1,0,0)$ and $t:=|\langle T,\ell\rangle|\leq
t_{0}$. Then without loss of generality, let $\ell=(t,\sqrt{1-t^{2}},0)$. Let
$u=(u_{1},u_{2},u_{3})$. From $|\langle u,T\rangle|\leq\epsilon$ and $|\langle
u,\ell\rangle|\leq\epsilon$, we deduce that $|u_{1}|\leq\epsilon$ and
$|u_{2}|\leq\frac{1+t}{\sqrt{1-t^{2}}}\epsilon=\sqrt{\frac{1+t}{1-t}}\epsilon\leq
10\epsilon$. It follows that $u_{3}^{2}\geq 1-101\epsilon^{2}$. By symmetry,
the same bounds hold for the three coordinates of vector $D$. Therefore

$\displaystyle|\langle D,u\rangle|$
$\displaystyle=|D_{1}u_{1}+D_{2}u_{2}+D_{3}u_{3}|\geq|D_{3}||u_{3}|-|D_{1}||u_{1}|-|D_{2}||u_{2}|$
$\displaystyle\geq 1-101\epsilon^{2}-\epsilon^{2}-(10\epsilon)^{2}$
$\displaystyle=1-202\epsilon^{2}.$

∎

###### Proof of Lemma 8.

Pick any fixed pair of True node and Dummy node in a literal block (see Fig.
2) and denote them by $T$ and $D$ respectively.

Now suppose that none of the literal color vectors $\ell_{a},\ell_{b}$ and
$\ell_{c}$ in Fig. 3(b) is close to their corresponding True node, i.e.
$|\langle T_{i},\ell\rangle_{i}|\leq t_{0}$, for every $i\in\\{a,b,c\\}$.

Let us consider nodes $\ell_{a}$ and $u_{a}$. Since $\ell_{a}$ is connected to
some $D_{a}$ node in its literal block (so the angle between $\ell_{a}$ and
$D_{a}$ is $\pi/2-o(1)$), and the angle between $D_{a}$ and the fixed Dummy
node $D$ is at most $\delta_{p}$, it follows that
$\theta_{(\ell_{a},D)}\geq\pi/2-\delta_{p}-o(1)$. On the other hand, since $D$
and $T$ is connected by an edge, they are very close to orthogonal; moreover,
the angle between $T_{a}$ and $T$ is at most $\delta_{p}$. Therefore,
$\theta_{(T_{a},D)}\geq\pi/2-\delta_{p}-o(1)$. Since $u_{a}$ is connected to
both $T_{a}$ and $\ell_{a}$, we have $\theta_{(T_{a},u_{a})}\geq\pi/2-o(1)$
and $\theta_{(\ell_{a},u_{a})}\geq\pi/2-o(1)$. Therefore, the conditions of
Claim 8 are met for vectors $D$, $T_{a}$, $u_{a}$ and $\ell_{a}$ for
$\epsilon=\sin(\delta_{p}+o(1))\leq\delta_{p}+o(1)\leq 1.01\delta_{p}$ for all
sufficiently large BOT graph size $n$. Hence, by Claim 8, $|\langle
D,u_{a}\rangle|\geq 1-202\epsilon^{2}\geq 1-207\delta_{p}^{2}$. By the same
reasoning, we have $|\langle D,u_{b}\rangle|\geq 1-207\delta_{p}^{2}$ and
$|\langle D,u_{c}\rangle|\geq 1-207\delta_{p}^{2}$. By Claim 7, item 3, the
angle between $D$ and each of the $u_{a},u_{b}$ and $u_{c}$ is at most
$32\delta_{p}$.

To finish the proof, note that, since each $u_{i}$ is connected with $v_{i}$
for every $i\in\\{a,b,c\\}$, it follows that the angle between $D$ and each
$v_{i}$ is at least $\pi/2-33\delta_{p}$ (whenever $n$ is large enough).
Applying Corollary 1 and noting that $v_{a}$, $v_{b}$ and $v_{c}$ form an
almost orthonormal basis, and $D$ is close to orthogonal to both $v_{a}$ and
$v_{b}$ with closeness parameter $\theta=33\delta_{p}$, we conclude that
$\theta_{(D,v_{c})}\leq 99\delta_{p}$. But we also know that the angle between
$D$ and $v_{c}$ is at least $\pi/2-33\delta_{p}$, therefore we reach a
contradiction as long as $\delta_{p}<\pi/264$. ∎

###### Proof of Theorem 8.

We begin by writing the log maximum likelihood estimator of a DPP kernel $K$
as

$\ell(K)=3\log{m}-\frac{1}{m}\sum_{(u,v)\in
E(G_{\phi})}\left(\log(\deg_{G_{\phi}}(u))+\log(\deg_{G_{\phi}}(v))+\log(\sin^{2}\theta_{(u,v)})\right).$

Let $K$ be a DPP kernel rank $3$ which satisfies that
$\ell(K)\leq\ell^{*}+\frac{C}{\log^{2}{n}}$, where $C$ is some very small
absolute constant to be determined later. Therefore, $\mathrm{E}_{(u,v)\in
E(G_{\phi})}[\log(\sin^{2}\theta_{(u,v)})]\geq-\frac{C}{\log^{2}{n}}$. By
Markov inequality, except for an $\epsilon^{\prime\prime}$ fraction of the
edges in the BOT graph $G_{\phi}$, all edges $(u,v)$ satisfy that

$\log(\sin^{2}\theta_{(u,v)})\geq-\frac{C/\epsilon^{\prime\prime}}{\log^{2}{n}},$

where $\epsilon^{\prime\prime}$ is an absolute constant to be specified later.
Call an edge in the BOT graph that satisfies this condition _good_ , and _bad_
otherwise. Consequently,

$\sin^{2}\theta_{(u,v)}\geq e^{-\frac{C/\epsilon^{\prime}}{\log^{2}{n}}}\geq
1-\frac{C}{\epsilon^{\prime}\log^{2}{n}},$

By Claim 7, the angle between all good edges $(u,v)$ satisfies that
$\theta_{(u,v)}\geq\frac{\pi}{2}-\sqrt{\frac{C\pi}{2\epsilon^{\prime\prime}}}\frac{1}{\log{n}}$.

Next we record some facts about the “robustness” of a very strong expander
against deletion of a small fraction of its edges. First, following Alon and
Capalbo, we note the following notion of expanders which is slightly weaker
than _very strong_ expanders.

######  Definition 2 (Strong expanders [AC07]).

A graph $G=(V,E)$ is called a _$d$ -strong expander_ on $n$ vertices if its
minimum vertex degree is at least $d$, the average degree in any subgraph of
$G$ on at most $n/10$ vertices is at most $2d/9$, and the average degree in
any subgraph of $G$ on at most $n/2$ vertices is at most $8d/9$.

######  Lemma 9 ([AC07]).

Let $G=(V,E)$ be a very strong $d$-regular expander on $n$ vertices. Let
$E^{\prime}\subset E$ be an arbitrary subset of edges satisfying
$|E^{\prime}|\leq\frac{nd}{150}$. Consider the process that we first delete
$E^{\prime}$ from $G$, and then repeatedly delete from $G$ the set of vertices
with degree smaller than $3d/4+2$ (and all the edges incident to such
vertices) as long as such vertices exist. Let $\mathrm{Dense}(G,E^{\prime})$
be the resulting subgraph of $G$ of this vertex-trimming process, and let $S$
denote the set of vertices deleted from $G$ during this process. Then
$|S|\leq\frac{15|E^{\prime}|}{d}$.

It is easy to check (by lower bounding the number of edges between any subset
of vertices $X$ of size at most $n/10$ and $n/2$ respectively, with the rest
of the vertices in $G$; namely $|E(X,V-X)|$) that the following lemma holds.

######  Lemma 10 ([AC07]).

Any subgraph of minimum degree at least $\frac{3d}{4}$ of a very strong
$d$-regular expander is a $\frac{3d}{4}$-strong expander.

It follows that $\mathrm{Dense}(G,E^{\prime})$ is a $\frac{3d}{4}$-strong
expander.

Lastly, the following lemma shows that the diameter of
$\mathrm{Dense}(G,E^{\prime})$ is $O(\log{n})$.

######  Lemma 11 ([AC07]).

For any $d$ and $n$, a $d$-regular strong expander on $n$ vertices has
diameter at most $\frac{2}{3}\log{n}+14$ (which is at most $\log{n}$ for all
large enough $n$).

Let $n$ be the number of variables in the $3$-CNF instance $\phi$. Then the
underlying very strong expander has $|V(G_{\mathrm{exp}})|=2nk$ vertices and
$|E(G_{\mathrm{exp}})|=nkd$ edges, where $d$ is the degree of the very strong
expander. Also recall that the BOT graph has
$|V(G_{\phi})|=O(nk)\cdot\max(k,d)$ vertices and
$|E(G_{\phi})|=O(nk)\cdot\max(k,d)$ edges.

Now, if we set the constant $\epsilon^{\prime\prime}$ such that
$\epsilon^{\prime\prime}|E(G_{\phi})|\cdot\frac{15}{d}=\epsilon n$, or
$\epsilon^{\prime\prime}=\frac{nd}{15|E(G_{\phi})|}\epsilon$, where $\epsilon$
is the constant in Lemma 1, then removing any
$\epsilon^{\prime\prime}$-fraction of the edges in $G_{\phi}$ makes at least
$(1-\epsilon)$-fraction of the clauses intact and thus can be satisfied. Note
that, since both $d$ and $k$ are constants,
$\epsilon^{\prime\prime}=\theta(\epsilon)$, another (small) constant.

Let $G^{\prime}_{\phi}$ be the subgraph of $G_{\phi}$ after removing all the
bad edges. Note that this can be translated into deleting edges of the
underlying very strong expander $G_{\mathrm{exp}}$; namely, if any of the
equality gadget edges between two literal blocks is deleted, delete the edge
between the corresponding two vertices in $G_{\mathrm{exp}}$. Now we perform
the vertex trimming process as described in Lemma 9 to $G_{\mathrm{exp}}$.
That is, if an edge between two vertices in $G_{\mathrm{exp}}$ is deleted in
the process, then we delete the gadget between the two corresponding literal
blocks in $G^{\prime}_{\phi}$. Let $G^{\prime\prime}_{\phi}$ be the resulting
graph. Now by our argument in the previous paragraph and Lemma 11, there is a
truth assignment that satisfies at least $(1-\epsilon)$ fraction of the
clauses in $G^{\prime\prime}_{\phi}$. Moreover, every edge in
$G^{\prime\prime}_{\phi}$ is good and the distance between any two vertices in
$G^{\prime\prime}_{\phi}$ is $O(\log{n})$.

Now we can unambiguously decode all the True nodes, False nodes and Dummy
nodes in $G^{\prime\prime}_{\phi}$.

######  Lemma 12.