Circuit Lower Bounds for the p-Spin Optimization Problem

We begin by describing the optimization problem of finding the ground state value of a $p$-spin model. Let $J\in\{\pm 1\}^{n^{p}}$ denote a $p$-tensor on $\mathbb{R}^{n}$ with $\{\pm 1\}$-valued entries. That is, $J=\left(J_{i_{1},\ldots,i_{p}},1\leq i_{1},i_{2},\ldots,i_{p}\leq n\right)$ and $J_{i_{1},\ldots,i_{p}}=\pm 1$ for each $p$-tuple $i_{1},\ldots,i_{p}$. For every $\sigma\in\{\pm 1\}^{n}$, we let

The optimal value of the optimization problem

is called the ground state energy of the $p$-spin model with coupling $J$. Any optimizer $\sigma$ achieving the optimal value is called the ground state. We will assume that the entries of $J$ are i.i.d. equiprobable $\pm 1$ (that is, Rademacher) entries. In this setting, we denote the optimal value of (1) by $\eta^{*}_{n,p}$, which is a random variable. The normalization by $n^{p+1\over 2}$ in the objective function is chosen so that the ground state energy is typically order 1. In particular, we recall here the following well-known concentration result.

The existence of the limit above follows from a rather simple interpolation argument based essentially on Gaussian comparison inequality techniques. This was shown first by Guerra and Toninelli [GT02]. The value of $\eta^{*}_{p}$ can be computed to any desired precision using the powerful Parisi variational representation as was done first by Parisi [Par80], and rigorously verified later by Talagrand [Tal06]. See Panchenko [Pan13] for a book treatment of the subject.

We now state the ensemble overlap gap property (e-OGP) exhibited by the $p$-spin model above. For this purpose we need to consider an ensemble of random tensors constructed as follows. Let $J$ and $\tilde{J}$ be two independent copies of the random $p$-spin model above with Rademacher entries constructed as follows. Let $\leq_{R}$ denote the (random) total order on $[n^{p}]$, given by drawing points from that set uniformly at random without replacement. We call this the uniform at random order. Let $I_{t}\in[n^{p}]$ be the point that was drawn at time $t$. Starting with $J_{0}=J$, let $J_{t}$ denote the random tensor obtained from $J_{t-1}$, by resampling the entry indexed by $I_{t}$ according to the Rademacher distribution, independently. Define $\tilde{J}=J_{n^{p}}$. Note that for each fixed $t$, the values $J_{t},J$ and $\tilde{J}$ are identically distributed (but not independent). We now formally state the e-OGP.

The proof is given in Section 3.2. Informally, e-OGP states that for every pair of instances in the interpolated family, including the case of identical instances (that is $t_{1}=t_{2}$), every two solutions achieving multiplicative factor $\eta_{\rm OGP,p}/\eta^{*}$ to optimality in those two instances are either close or far from each other. Furthermore, for the case of independent instances (that is $t_{1}=0,t_{2}=n^{p}$), only the latter is possible. Theorem 2.2 was proved in [GJ21] for the case of Gaussian as opposed to Rademacher distribution, but its adaptation to the latter case follows from standard universality-type arguments based on Lindeberg’s approach, which can be found in the original paper [GT02] which established the existence of the limit $\eta_{p}^{*}$. For a recent work that covers many examples of such arguments see [Sen18] and for a textbook presentation of this and related spin glass results, see [Pan13].

The core of the proof in [GJ21] is the case of a single-instance (non-ensemble) OGP for the Gaussian case which was done in [CGPR19]. Its adaptation to the ensemble case follows in a rather straightforward way using the chaos property exhibited by the $p$-spin models. Adaptation to non-Gaussian distribution, as we said, uses standard universality arguments.

We now turn to the discussion of Boolean circuits. Formal definitions of those can be found in most standard textbooks on algorithms and computation [AB09, Sip97, AS04]. Informally, these are functions from $\{0,1\}^{M}\to\{0,1\}^{n}$ obtained by considering a directed graph with $M$ input nodes which have in-degree zero, and $n$ output nodes which have out-degree zero. Each intermediate node corresponds to one of three standard Boolean operation $\vee,\wedge$ or $\neg$. The size of the circuit is the number of nodes in the associated graph and its depth is the length of its longest directed path. Equivalently, one may consider instead functions from $\{\pm 1\}^{M}\to\{\pm 1\}^{n}$ by adopting the appropriate logical functions in gates. We also adopt this assumption for convenience. In particular, when $M=n^{p}$, such a Boolean function maps any $p$-tensor with $\pm 1$ entries into an $n$-vector with $\pm 1$ entries. Thus given an $n$-output, $M=n^{p}$-input Boolean circuit $C$ and $p$-tensor $J$ with $\pm 1$ entries, we denote by $C(J)$ the binary vector in $\{\pm 1\}^{n}$ produced when $C$ takes input $J$. We denote by $C_{j}$ the single-output Boolean circuit associated with the $j$-th component of $C$ so that $C(J)=(C_{j}(J),1\leq j\leq n)$.

As stated in the introduction, we are interested in Boolean circuits with bounds on their size and depth. Fix any two $n$-dependent positive integer-valued sequences $s(n),d(n)$ and a constant $0<\rho<1$. We denote by $\mathcal{C}_{p}(n,s(n),d(n),\rho)$ the family of all $n^{p}$-input, $n$-output Boolean circuits $C$ which satisfy the following properties:

1. (a)

   The size (the number of gates) of $C$ is at most $s(n)$ and its depth is at most $d(n)$.

2. (b)

   For every tensor $J\in\{\pm 1\}^{n^{p}}$ such that the value in (1) is non-negative, the output $C(G)$ satisfies

   $\displaystyle\langle J,C(J)\rangle\geq\rho\max_{\sigma\in\{\pm 1\}^{n}}\langle J,\sigma\rangle.$

   If the value in (1) is negative, the output $C(J)$ can be arbitrary.

In other words, this is a family of circuits which is required to produce a solution with value which is at least a multiplicative constant $\rho$ away from optimality when the value of the optimization problem is non-negative. Clearly a family of such circuits can be empty if either $s(n)$ or $d(n)$ is too restrictive.

We now state our main result.

The result above essentially rules out poly-size circuits with the stated bound on depth that obtain a solution with value at least $\rho$ times the optimum value, where $\rho$ is any constant larger than $\eta_{\rm OGP,p}/\eta^{*}_{p}$. The proof is given in Section 3.1. The constant $2$ in the depth lower bound can be slightly improved, although it appears that it has to be larger than $1$ for our analysis to go through. We note that $\alpha$ does not appear in the claimed lower bound on the circuit depth because the bound holds even for mildly super-polynomially sized circuits. We will not attempt to find the optimal growth rate.

We fix any $\alpha>0$ and any circuit $C\in\mathcal{C}_{p}(n,n^{\alpha},d(n),\rho)$. Recall that the output of the Boolean circuit $C$ acting on any input $J\in\{\pm 1\}^{n^{p}}$ is a vector in $\{\pm 1\}^{n}$ and thus has $\|\cdot\|_{2}^{2}$ norm equal $n$. Fix a constant $\kappa>0$. Consider any two tensors $J_{1},J_{2}\in\{\pm 1\}^{n^{p}}$ which differ in at most one entry. Namely, there exists $1\leq i_{1},\ldots,i_{p}\leq n$ such that $J_{1}$ and $J_{2}$ are identical at all multi-indices $(i_{1}^{\prime},\ldots,i_{p}^{\prime})$ that are distinct from the $p$-tuple $(i_{1},\ldots,i_{p})$. We say that the pair $(J_{1},J_{2})$ is $\kappa$-bad if

Fix two independent copies $J$ and $\tilde{J}$ of a random $p$-tensor with i.i.d. $\pm 1$ entries and consider the discrete interpolation $J=J_{0},J_{1},J_{2},\ldots,J_{n^{p}}=\tilde{J}$ associated with the statement of Theorem 2.2. The following “stability” result is a direct analogue of Theorem 4.2 in [GJW20] (but for circuits instead of low-degree polynomials).

The constants $\kappa,\alpha,\eta_{\rm OGP,p}$ will be subsumed by $\log n$ as we will see. Note that this probability converges to zero if $d(n)$ is bounded away from zero. For our purposes, we will need the rate of convergence in this bound to be no faster than exponential. (In particular, this requirement will control our depth bound.)

The proof of Theorem 3.1 (which we include for completeness) is similar to Theorem 4.2 of [GJW20] but with two minor changes: first we observe that [GJW20] applies not just to functions of bounded degree but more generally to functions of bounded total influence; we then use the Linial-Mansour-Nisan Theorem to bound the total influence of any low-depth circuit.

Let’s first see how Theorem 3.1 implies the result.

Before turning to the proof of Theorem 3.1, let us briefly recall the following notions from Boolean analysis/Fourier analysis on $\{\pm 1\}^{m}$; see e.g. [O’D14] for a reference. (In our setting, we will always work with the specific case $m=n^{p}$.) Consider the standard Fourier expansion of functions on $\{\pm 1\}^{m}$ associated with the uniform measure on $\{\pm 1\}^{m}$. The basis of this expansion are monomials of the form $x_{S}\triangleq\prod_{i\in S}x_{i},\,S\subset[m]$. For every function $g:\{\pm 1\}^{m}\to\mathbb{R}$, the associated Fourier coefficients are

where the expectation is with respect to the uniform measure on $x=(x_{1},\ldots,x_{m})\in\{\pm 1\}^{m}$. Then the Fourier expansion of $g$ is $g=\sum_{S\subset[m]}\hat{g}_{S}x_{S}$, and the Parseval (or Walsh) identity states that $\sum_{S}\hat{g}_{S}^{2}=\mathbb{E}\!\left[g(x)^{2}\right]$. For $i\in[m]$, let $L_{i}$ denote the Laplacian operator:

and let $I(g)$ be the total influence

Also note that

where for $\ell=\pm 1$, $x_{-i,\ell}\in\{\pm 1\}^{m}$ is obtained from $x$ by fixing the $i$-th coordinate of $x$ to $\ell$.

The proof of Theorem 2.2 is similar to that in the Gaussian case after a coupling argument where we couple the path $J_{t}$ above to a discretized $\hat{J}_{t}$ induced by correlated Rademacher random vectors. We explain here the key steps that are different. In the following for two mean zero random vectors we say that $X\sim_{\rho}Y$, if $(X_{i},Y_{i})$ and $(X_{j},Y_{j})$ are independent for $i\neq j$ and $\mathbb{E}\!\left[X_{i}Y_{i}\right]=\rho$ for each $i$.

Let us begin with the following construction of $\leq_{R}$ which corresponds to said coupling. Fix $\delta>0$ so that $1/\delta$ is an integer, and let $0=\rho_{0}<\rho_{1}<\ldots<\rho_{\frac{1}{\delta}}=1$ be $\rho_{k}=k\delta$. We now construct a sequence of correlated instances of Rademacher random vectors as follows. Let $\hat{J}_{0}$ be an i.i.d. Ber(1/2) random vector. Now for each entry of $\hat{J}_{0}$, we resample it independently with probability $\rho_{1}$ and leave it as it was with probability $1-\rho_{1}$, to obtain $\hat{J}_{1}$. Notice that $\hat{J}_{1}\sim_{1-\rho_{1}}\hat{J}_{0}$. Now for those entries of $\hat{J}_{1}$ that have not been resampled, resample them with probability $(\rho_{2}-\rho_{1})/(1-\rho_{1})$. Repeat this process $1/\delta$ times to obtain a sequence $\hat{J}_{k}$ of vectors each of which has i.i.d. Ber(1/2) entries and are such that if $\rho_{k}>\rho_{\ell}$ then $\hat{J}_{k}\sim_{1-(\rho_{k}-\rho_{\ell})}\hat{J}_{\ell}$. Furthermore, notice that as $\rho_{1/\delta}=1$, in the last step of this sequence, all of the remaining entries are resampled (independently) with probability 1, so that $\hat{J}_{1/\delta}$ is an independent copy of $\hat{J}_{0}$. Now for each $k=1,\ldots,1/\delta$, let ${\cal I}_{k}$ be indices that have been resampled when going from $\hat{J}_{k-1}$ to $\hat{J}_{k}$. We now define $\leq_{R}$ in the obvious way: if $I\in{\cal I}_{k},I^{\prime}\in{\cal I}_{\ell}$, then $I\leq_{R}I^{\prime}$ if $k\leq\ell$. Within ${\cal I}_{k}$ we let $\leq_{R}$ be the uniform at random order for ${\cal I}_{k}$. Note that $\{{\cal I}_{k}\}$ is a partition of $[n^{p}]$. Evidently the law of $\leq_{R}$ is that of the uniform at random order. Notice that if we construct $(J_{k})$ in the corresponding way and let $\tau_{k}$ be such that $\tau_{0}=0$ and $\tau_{k}-\tau_{k-1}=\lvert\mathcal{I}_{k}\rvert$, then $J_{\tau_{k}}=\hat{J}_{k}$.