What Makes Data Suitable for a Locally Connected Neural Network? A
  Necessary and Sufficient Condition Based on Quantum Entanglement
The question of what makes a data distribution suitable for deep learning is
a fundamental open problem. Focusing on locally connected neural networks (a
prevalent family of architectures that includes convolutional and recurrent
neural networks as well as local self-attention models), we address this
problem by adopting theoretical tools from quantum physics. Our main
theoretical result states that a certain locally connected neural network is
capable of accurate prediction over a data distribution if and only if the data
distribution admits low quantum entanglement under certain canonical partitions
of features. As a practical application of this result, we derive a
preprocessing method for enhancing the suitability of a data distribution to
locally connected neural networks. Experiments with widespread models over
various datasets demonstrate our findings. We hope that our use of quantum
entanglement will encourage further adoption of tools from physics for formally
reasoning about the relation between deep learning and real-world data.
Yotam Alexander, Nimrod De La Vega, Noam Razin, Nadav Cohen
What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement

###### Abstract

The question of what makes a data distribution suitable for deep learning is a fundamental open problem. Focusing on locally connected neural networks (a prevalent family of architectures that includes convolutional and recurrent neural networks as well as local self-attention models), we address this problem by adopting theoretical tools from quantum physics. Our main theoretical result states that a certain locally connected neural network is capable of accurate prediction over a data distribution _if and only if_ the data distribution admits low quantum entanglement under certain canonical partitions of features. As a practical application of this result, we derive a preprocessing method for enhancing the suitability of a data distribution to locally connected neural networks. Experiments with widespread models over various datasets demonstrate our findings. We hope that our use of quantum entanglement will encourage further adoption of tools from physics for formally reasoning about the relation between deep learning and real-world data.

## 1 Introduction

Deep learning is delivering unprecedented performance when applied to data modalities involving images, text and audio. On the other hand, it is known both theoretically and empirically [53; 1] that there exist data distributions over which deep learning utterly fails. The question of _what makes a data distribution suitable for deep learning_ is a fundamental open problem in the field.

A prevalent family of deep learning architectures is that of _locally connected neural networks_. It includes, among others: _(i)_ convolutional neural networks, which dominate the area of computer vision; _(ii)_ recurrent neural networks, which were the most common architecture for sequence (_e.g._ text and audio) processing, and are experiencing a resurgence by virtue of S4 models [26]; and _(iii)_ local variants of self-attention neural networks [60]. Conventional wisdom postulates that data distributions suitable for locally connected neural networks are those exhibiting a "local nature," and there have been attempts to formalize this intuition [64; 28; 15]. However, to the best of our knowledge, there are no characterizations providing necessary and sufficient conditions for a data distribution to be suitable to a locally connected neural network.

A seemingly distinct scientific discipline tying distributions and computational models is _quantum physics_. There, distributions of interest are described by _tensors_, and the associated computational
models are _tensor networks_. While there is shortage in formal tools for assessing the suitability of data distributions to deep learning architectures, there exists a widely accepted theory that allows for assessing the suitability of tensors to tensor networks. The theory is based on the notion of _quantum entanglement_, which quantifies dependencies that a tensor admits under partitions of its axes (for a given tensor \(\mathcal{A}\) and a partition of its axes to sets \(\mathcal{K}\) and \(\mathcal{K}^{c}\), the entanglement is a non-negative number quantifying the dependence that \(\mathcal{A}\) induces between \(\mathcal{K}\) and \(\mathcal{K}^{c}\)).

In this paper, we apply the foregoing theory to a tensor network equivalent to a certain locally connected neural network, and derive theorems by which fitting a tensor is possible if and only if the tensor admits low entanglement under certain _canonical partitions_ of its axes. We then consider the tensor network in a machine learning context, and find that its ability to attain low approximation error, _i.e._ to express a solution with low population loss, is determined by its ability to fit a particular tensor defined by the data distribution, whose axes correspond to features. Combining the latter finding with the former theorems, we conclude that a _locally connected neural network is capable of accurate prediction over a data distribution if and only if the data distribution admits low entanglement under canonical partitions of features_. Experiments with different datasets corroborate this conclusion, showing that the accuracy of common locally connected neural networks (including modern convolutional, recurrent, and local self-attention neural networks) is inversely correlated to the entanglement under canonical partitions of features in the data (the lower the entanglement, the higher the accuracy, and vice versa).

The above results bring forth a recipe for enhancing the suitability of a data distribution to locally connected neural networks: given a dataset, search for an arrangement of features which leads to low entanglement under canonical partitions, and then arrange the features accordingly. Unfortunately, the above search is computationally prohibitive. However, if we employ a certain correlation-based measure as a surrogate for entanglement, _i.e._ as a gauge for dependence between sides of a partition of features, then the search converts into a succession of _minimum balanced cut_ problems, thereby admitting use of well-established graph theoretical tools, including ones designed for large scale [29; 57]. We empirically evaluate this approach on various datasets, demonstrating that it substantially improves prediction accuracy of common locally connected neural networks (including modern convolutional, recurrent, and local self-attention neural networks).

The data modalities to which deep learning is most commonly applied -- namely ones involving images, text and audio -- are often regarded as natural (as opposed to, for example, tabular data fusing heterogeneous information). We believe the difficulty in explaining the suitability of such modalities to deep learning may be due to a shortage in tools for formally reasoning about natural data. Concepts and tools from physics -- a branch of science concerned with formally reasoning about natural phenomena -- may be key to overcoming said difficulty. We hope that our use of quantum entanglement will encourage further research along this line.

The remainder of the paper is organized as follows. Section 2 reviews related work. Section 3 establishes preliminaries, introducing tensors, tensor networks and quantum entanglement. Section 4 presents the theorems by which a tensor network equivalent to a locally connected neural network can fit a tensor if and only if this tensor admits low entanglement under canonical partitions of its axes. Section 5 employs the preceding theorems to show that in a classification setting, accurate prediction is possible if and only if the data admits low entanglement under canonical partitions of features. Section 6 translates this result into a practical method for enhancing the suitability of data to common locally connected neural networks. Finally, Section 7 concludes. For simplicity, we treat locally connected neural networks whose input data is one-dimensional (_e.g._ text and audio), and defer to Appendix E an extension of the analysis and experiments to models intaking data of arbitrary dimension (_e.g._ two-dimensional images).

## 2 Related Work

Characterizing formal properties of data distributions that make them suitable for neural networks is a major open problem in deep learning. A number of papers provide sufficient conditions on a data distribution that allow it to be learnable by some neural network architecture [5; 6; 40; 20; 21; 44]. However, the conditions under which learnability is proven are restrictive, and are not argued to be necessary. There have also been attempts to quantify the structure of data via quantum entanglement and mutual information [41; 15; 39; 7; 64; 28], yet without formally relating properties of the data to
the prediction accuracy achievable by neural networks. To the best of our knowledge, this paper is the first to derive a necessary and sufficient condition on the data distribution for accurate prediction by locally connected neural networks.

Our work follows a long line of research employing tensor networks as theoretical models for studying deep learning. These include works analyzing the expressiveness of different neural network architectures [12; 55; 9; 10; 54; 14; 35; 2; 36; 30; 37; 31; 51], their generalization properties [38], and the implicit regularization induced by optimization [48; 49; 50; 62; 24]. We focus on expressiveness, yet our results differ from the aforementioned works in that we incorporate the data distribution into our analysis and tackle the question of what makes data suitable for deep learning.

The algorithm we propose for enhancing the suitability of data to locally connected neural networks can be considered a form of representation learning. Representation learning is a vast field, far too broad for us to survey here (for an overview see [42]). most representation learning methods are concerned with dimensionality reduction, i.e the discovery of low dimensional structure in high dimensional data, e.g [3; 33]. Such methods are complementary to our approach, which preserves the dimensionality of the input, and seeks to learn a rearrangement of features that is better suited to locally connected neural networks. A notable work of this type is IGTD [65], which arranges features in a dataset to improve its suitability for convolutional neural networks. In contrast to IGTD, our method is theoretically grounded, and as demonstrated empirically in Section 6, it leads to higher improvements in prediction accuracy for locally connected neural networks.

## 3 Preliminaries

NotationWe use \(\left\|\cdot\right\|\) and \(\left\langle\cdot,\cdot\right\rangle\) to denote the Euclidean (Frobenius) norm and inner product, respectively. We shorthand \([N]:=\{1,\ldots,N\}\), where \(N\in\mathbb{N}\). The complement of \(\mathcal{K}\subseteq[N]\) is denoted by \(\mathcal{K}^{c}:=[N]\setminus\mathcal{K}\).

### Tensors and Tensor Networks

For our purposes, a _tensor_ is a multi-dimensional array \(\mathcal{A}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\), where \(N\in\mathbb{N}\) is its _dimension_ and \(D_{1},\ldots,D_{N}\in\mathbb{N}\) are its _axes lengths_. The \((d_{1},\ldots,d_{N})\)'th entry of \(\mathcal{A}\) is denoted \(\mathcal{A}_{d_{1},\ldots,d_{N}}\).

_Contraction_ between tensors is a generalization of multiplication between matrices. Two matrices \(\mathbf{A}\in\mathbb{R}^{D_{1}\times D_{2}}\) and \(\mathbf{B}\in\mathbb{R}^{D^{\prime}_{1}\times D^{\prime}_{2}}\) can be multiplied if \(D_{2}=D^{\prime}_{1}\), in which case we get a matrix in \(\mathbb{R}^{D_{1}\times D^{\prime}_{2}}\) holding \(\sum_{d=1}^{D_{2}}\mathbf{A}_{d_{1},d}\cdot\mathbf{B}_{d,d^{\prime}_{2}}\) in entry \((d_{1},d^{\prime}_{2})\in[D_{1}]\times[D^{\prime}_{2}]\). More generally, two tensors \(\mathcal{A}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) and \(\mathcal{B}\in\mathbb{R}^{D^{\prime}_{1}\times\cdots\times D^{\prime}_{N^{ \prime}}}\) can be contracted along axis \(n\in[N]\) of \(\mathcal{A}\) and \(n^{\prime}\in[N^{\prime}]\) of \(\mathcal{B}\) if \(D_{n}=D^{\prime}_{n^{\prime}}\), in which case we get a tensor in \(\mathbb{R}^{D_{1}\times\cdots\cdot D_{n-1}\times D_{n+1}\times\cdots\times D_{ N}\times D^{\prime}_{1}\times\cdots\times D^{\prime}_{n^{\prime}-1}\times D^{ \prime}_{n^{\prime}+1}\cdots\times D^{\prime}_{N^{\prime}}}\) holding:

\[\sum\nolimits_{d=1}^{D_{n}}\mathcal{A}_{d_{1},\ldots,d_{n-1},d,d_{n+1},\ldots,d_{N}}\cdot\mathcal{B}_{d^{\prime}_{1},\ldots,d^{\prime}_{n^{\prime}-1},d,d^{ \prime}_{n^{\prime}+1},\ldots,d^{\prime}_{N^{\prime}}}\,,\]

in the entry indexed by \(\left\{d_{k}\in[D_{k}]\right\}_{k\in[N]\setminus\{n\}}\) and \(\left\{d^{\prime}_{k}\in[D^{\prime}_{k}]\right\}_{k\in[N^{\prime}]\setminus\{n^ {\prime}\}}\).

_Tensor networks_ are prominent computational models for fitting (_i.e._ representing) tensors. More specifically, a tensor network is a weighted graph that describes formation of a (typically high-dimensional) tensor via contractions between (typically low-dimensional) tensors. As customary (_cf._[43]), we will present tensor networks via graphical diagrams to avoid cumbersome notation -- see Figure 1 for details.

### Quantum Entanglement

In quantum physics, the distribution of possible states for a multi-particle ("many body") system is described by a tensor, whose axes are associated with individual particles. A key property of the distribution is the dependence it admits under a given partition of the particles (_i.e._ between a given set of particles and its complement). This dependence is formalized through the notion of _quantum entanglement_, defined using the distribution's description as a tensor -- see Definition 1 below.
Quantum entanglement lies at the heart of a widely accepted theory which allows assessing the ability of a tensor network to fit a given tensor (_cf._[16; 36]). In Section 4 we specialize this theory to a tensor network equivalent to a certain locally connected neural network.

**Definition 1**.: For a tensor \(\mathcal{A}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) and subset of its axes \(\mathcal{K}\subseteq[N]\), let \([\![\mathcal{A};\mathcal{K}]\!]\in\mathbb{R}\!\!\prod_{n\in\mathcal{K}}D_{n} \times\prod_{m\in\mathcal{K}^{c}}D_{n}\) be the arrangement of \(\mathcal{A}\) as a matrix where rows correspond to axes \(\mathcal{K}\) and columns correspond to the remaining axes \(\mathcal{K}^{c}:=[N]\setminus\mathcal{K}\). Denote by \(\sigma_{1}\geq\cdots\geq\sigma_{D_{\mathcal{K}}}\in\mathbb{R}_{\geq 0}\) the singular values of \([\![\mathcal{A};\mathcal{K}]\!]\), where \(D_{\mathcal{K}}:=\min\{\prod_{n\in\mathcal{K}}D_{n},\prod_{n\in\mathcal{K}^{c }}D_{n}\}\). The _quantum entanglement_1 of \(\mathcal{A}\) with respect to the partition \((\mathcal{K},\mathcal{K}^{c})\) is the entropy of the distribution \(\{\rho_{d}:=\sigma_{d}^{2}/\sum_{d^{\prime}=1}^{D_{\mathcal{K}}}\sigma_{d^{ \prime}}^{2}\}_{d=1}^{D_{\mathcal{K}}}\), _i.e._:

Footnote 1: There exist multiple notions of entanglement in quantum physics (see, _e.g._, [36]). The one we consider is the most common, known as _entanglement entropy_.

\[QE(\mathcal{A};\mathcal{K}):=-\sum\nolimits_{d=1}^{D_{\mathcal{K}}}\rho_{d} \ln(\rho_{d})\,.\]

By convention, if \(\mathcal{A}=0\) then \(QE(\mathcal{A};\mathcal{K})=0\).

## 4 Low Entanglement Under Canonical Partitions Is Necessary and Sufficient for Fitting Tensor

In this section, we prove that a tensor network equivalent to a certain locally connected neural network can fit a tensor if and only if the tensor admits low entanglement under certain canonical partitions of its axes. We begin by introducing the tensor network (Section 4.1). Subsequently, we establish the necessary and sufficient condition required for it to fit a given tensor (Section 4.2). For conciseness, the treatment in this section is limited to one-dimensional (sequential) models; see Appendix E.1 for an extension to arbitrary dimensions.

### Tensor Network Equivalent to a Locally Connected Neural Network

Let \(N\in\mathbb{N}\), and for simplicity suppose that \(N=2^{L}\) for some \(L\in\mathbb{N}\). We consider a tensor network with an underlying perfect binary tree graph of height \(L\), which generates \(\mathcal{W}_{\mathrm{TN}}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\). Figure 2(a) provides its diagrammatic definition. Notably, the lengths of axes corresponding to inner (non-open) edges are taken to be \(R\in\mathbb{N}\), referred to as the _width_ of the tensor network.2

Footnote 2: We treat the case where all axes corresponding to inner (non-open) edges in the tensor network have the same length merely for simplicity of presentation. Extension of our theory to axes of different lengths is straightforward.

As identified by previous works, the tensor network depicted in Figure 2(a) is equivalent to a certain locally connected neural network (with polynomial non-linearity -- see, _e.g._, [12; 10; 36; 50]). In

Figure 1: Tensor networks form a graphical language for fitting (_i.e._ representing) tensors through tensor contractions. **Tensor network definition:** Every node in a tensor network is associated with a tensor, whose dimension is equal to the number of edges emanating from the node. An edge connecting two nodes specifies contraction between the tensors associated with the nodes (Section 3.1), where the weight of the edge signifies the respective axes lengths. Tensor networks may also contain open edges, _i.e._ edges that are connected to a node on one side and are open on the other. The number of such open edges is equal to the dimension of the tensor produced by contracting the tensor network. **Illustrations:** Presented are exemplar tensor network diagrams of: **(a)** an \(N\)-dimensional tensor \(\mathcal{A}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\); **(b)** a vector-matrix multiplication between \(\mathbf{M}\in\mathbb{R}^{D_{1}\times D_{2}}\) and \(\mathbf{v}\in\mathbb{R}^{D_{2}}\), which results in the vector \(\mathbf{M}\mathbf{v}\in\mathbb{R}^{D_{1}}\); and **(c)** a more elaborate tensor network generating \(\mathcal{W}\in\mathbb{R}^{D_{1}\times D_{2}\times D_{3}}\).
particular, contracting the tensor network with vectors \(\mathbf{x}^{(1)}\in\mathbb{R}^{D_{1}},\ldots,\mathbf{x}^{(N)}\in\mathbb{R}^{D_{N}}\), as illustrated in Figure 2(b), can be viewed as a forward pass of the data instance \((\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(N)})\) through a locally connected neural network. This computation results in a scalar equal \(\left\langle\otimes_{n=1}^{N}\mathbf{x}^{(n)},\mathcal{W}_{\mathrm{TN}}\right\rangle\), where \(\otimes\) stands for the outer product.34 In light of its equivalence to a locally connected neural network, we will refer to the tensor network as a _locally connected tensor network_. We note that for the equivalent neural network to be practical (in terms of memory and runtime), the width of the tensor network \(R\) needs to be of moderate size. Specifically, \(R\) cannot be exponential in the dimension \(N\), meaning \(\ln(R)\) needs to be much smaller than \(N\).

Footnote 3: For any \(\left\{\mathbf{x}^{(n)}\in\mathbb{R}^{D_{n}}\right\}_{n=1}^{N}\), the outer product \(\otimes_{n=1}^{N}\mathbf{x}^{(n)}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) is defined element-wise by \(\left[\otimes_{n=1}^{N}\mathbf{x}^{(n)}\right]_{d_{1},\ldots,d_{N}}=\prod_{n= 1}^{N}\mathbf{x}^{(n)}_{d_{n}}\), where \(d_{1}\in[D_{1}],\ldots,d_{N}\in[D_{N}]\).

Footnote 4: Contracting an arbitrary tensor \(\mathcal{A}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) with vectors \(\mathbf{x}^{(1)}\in\mathbb{R}^{D_{1}},\ldots,\mathbf{x}^{(N)}\in\mathbb{R}^{D_{ N}}\) (where for each \(n\in[N]\), \(\mathbf{x}^{(n)}\) is contracted against the \(n\)’th axis of \(\mathcal{A}\)) yields a scalar equal to \(\left\langle\mathcal{A},\otimes_{n=1}^{N}\mathbf{x}^{(n)}\right\rangle\). This follows from the definitions of the contraction, inner product and outer product operations.

By virtue of the locally connected tensor network's equivalence to a deep neural network, it has been paramount for the study of expressiveness and generalization in deep learning [12; 9; 10; 13; 14; 54; 35; 36; 2; 30; 31; 37; 48; 49; 50; 51]. Although the equivalent deep neural network (which has polynomial non-linearity) is less common than other neural networks (_e.g._, ones with ReLU non-linearity), it has demonstrated competitive performance in practice [8; 11; 55; 58; 22]. More importantly, its analyses (through its equivalence to the locally connected tensor network) brought forth numerous insights that were demonstrated empirically and led to development of practical tools for common locally connected architectures. Continuing this line, we will demonstrate our theoretical insights through experiments with widespread convolutional, recurrent and local self-attention architectures (Section 5.3), and employ our theory for deriving an algorithm that enhances the suitability of a data distribution to said architectures (Section 6).

### Necessary and Sufficient Condition for Fitting Tensor

Herein we show that the ability of the locally connected tensor network (defined in Section 4.1) to fit (_i.e._ represent) a given tensor is determined by the entanglements that the tensor admits under the following _canonical partitions_ of \([N]\).

**Definition 2**.: The _canonical partitions_ of \([N]\) (illustrated in Figure 3) are:

\[\mathcal{C}_{N}:= \!\!\left\{\left(\mathcal{K},\mathcal{K}^{c}\right):\,\mathcal{K}= \left\{2^{L-l}\cdot(n-1)+1,\ldots,2^{L-l}\cdot n\right\},\,l\in\left\{0, \ldots,L\right\},\;n\in\left[2^{l}\right]\right\}.\]
By appealing to known upper bounds on the entanglements that a given tensor network supports [16, 36], we establish that if the locally connected tensor network can fit a given tensor, that tensor must admit low entanglement under the canonical partitions of its axes. Namely, suppose that \(\mathcal{W}_{\mathrm{TN}}\) -- the tensor generated by the locally connected tensor network -- well-approximates an \(N\)-dimensional tensor \(\mathcal{A}\). Then, Theorem 1 below shows that the entanglement of \(\mathcal{A}\) with respect to a canonical partition cannot be much larger than \(\ln(R)\) (recall that \(R\) is the width of the locally connected tensor network), whereas the entanglement attainable by an arbitrary tensor with respect to a canonical partition can be linear in the dimension \(N\).

In the other direction, Theorem 2 below implies that low entanglement under the canonical partitions is not only necessary for a tensor to be fit by the locally connected tensor network, but also sufficient.

**Theorem 1**.: _Let \(\mathcal{W}_{\mathrm{TN}}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) be a tensor generated by the locally connected tensor network defined in Section 4.1, and let \(\mathcal{A}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\). For any \(\epsilon\in[0,\|\mathcal{A}\|/4]\), if \(\|\mathcal{W}_{\mathrm{TN}}-\mathcal{A}\|\leq\epsilon\), then for all canonical partitions \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) (Definition 2):5_

Footnote 5: If \(\mathcal{A}=0\), then \(\epsilon=0\). In this case, the expression \(\epsilon/\|\mathcal{A}\|\) is by convention equal to zero.

\[QE(\mathcal{A};\mathcal{K})\leq\ln(R)+\frac{2\epsilon}{\|\mathcal{A}\|}\cdot \ln(D_{\mathcal{K}})+2\sqrt{\frac{2\epsilon}{\|\mathcal{A}\|}}\,, \tag{1}\]

_where \(D_{\mathcal{K}}:=\min\{\prod_{n\in\mathcal{K}}D_{n},\prod_{n\in\mathcal{K}^{c }}D_{n}\}\). In contrast, there exists \(\mathcal{A}^{\prime}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) such that for all canonical partitions \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\):_

\[QE(\mathcal{A}^{\prime};\mathcal{K})\geq\min\{|\mathcal{K}|,|\mathcal{K}^{c}| \}\cdot\ln(\min_{n\in[N]}D_{n})\,. \tag{2}\]

Proof sketch (proof in Appendix G.2).: In general, the entanglements that a tensor network supports can be upper bounded through cuts in its graph [16, 36]. For the locally connected tensor network, these bounds imply that \(QE(\mathcal{W}_{\mathrm{TN}};\mathcal{K})\leq\ln(R)\) for any canonical partition \((\mathcal{K},\mathcal{K}^{c})\). Equation (1) then follows by showing that if \(\mathcal{W}_{\mathrm{TN}}\) and \(\mathcal{A}\) are close, then so are their entanglements. Equation (2) is established using a construction from [18], providing a tensor with maximal entanglements under all partitions of its axes. 

**Theorem 2**.: _Let \(\mathcal{A}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) and \(\epsilon>0\). Suppose that for all canonical partitions \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) (Definition 2) it holds that \(QE(\mathcal{A};\mathcal{K})\leq\frac{\epsilon^{2}}{(2N-3)\|\mathcal{A}\|^{2}} \cdot\ln(R)\).6 Then, there exists an assignment for the tensors constituting the locally connected tensor network (defined in Section 4.1) such that it generates \(\mathcal{W}_{\mathrm{TN}}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) satisfying:_

Footnote 6: When the approximation error \(\epsilon\) tends to zero, the sufficient condition in Theorem 2 requires entanglements to approach zero, unlike the necessary condition in Theorem 1 which requires entanglements to become no greater than \(\ln(R)\). This is unavoidable. However, if for all canonical partitions \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) the singular values of \(\llbracket\mathcal{A};\mathcal{K}\rrbracket\) trailing after the \(R\)’th one are small, then we can also guarantee an assignment for the locally connected tensor network satisfying \(\|\mathcal{W}_{\mathrm{TN}}-\mathcal{A}\|\leq\epsilon\), while \(QE(\mathcal{A};\mathcal{K})\) can be on the order of \(\ln(R)\) for all \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\). See Appendix A for details.

\[\|\mathcal{W}_{\mathrm{TN}}-\mathcal{A}\|\leq\epsilon\,.\]

Proof sketch (proof in Appendix G.3).: We show that if \(\mathcal{A}\) has low entanglement under a canonical partition \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\), then the singular values of \(\llbracket\mathcal{A};\mathcal{K}\rrbracket\) must decay rapidly (recall that \(\llbracket\mathcal{A};\mathcal{K}\rrbracket\) is

Figure 3: The canonical partitions of \([N]\), for \(N=2^{L}\) with \(L\in\mathbb{N}\). Every \(l\in\{0,\ldots,L\}\) contributes \(2^{l}\) canonical partitions, the \(n\)’th one induced by \(\mathcal{K}=\{2^{L-l}\cdot(n-1)+1,\ldots,2^{L-l}\cdot n\}\).
the arrangement of \(\mathcal{A}\) as a matrix where rows correspond to axes \(\mathcal{K}\) and columns correspond to the remaining axes). The approximation guarantee is then obtained through a construction from [25], which is based on truncated singular value decompositions of every \(\llbracket\mathcal{A};\mathcal{K}\rrbracket\) for \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\). 

## 5 Low Entanglement Under Canonical Partitions Is Necessary and Sufficient for Accurate Prediction

This section considers the locally connected tensor network from Section 4.1 in a machine learning setting. We show that attaining low population loss amounts to fitting a tensor defined by the data distribution, whose axes correspond to features (Section 5.1). Applying the theorems of Section 4.2, we then conclude that the locally connected tensor network is capable of accurate prediction if and only if the data distribution admits low entanglement under canonical partitions of features (Section 5.2). This conclusion is corroborated through experiments, demonstrating that the performance of common locally connected neural networks (including convolutional, recurrent, and local self-attention neural networks) is inversely correlated with the entanglement under canonical partitions of features in the data (Section 5.3). For conciseness, the treatment in this section is limited to one-dimensional (sequential) models and data; see Appendix E.2 for an extension to arbitrary dimensions.

### Accurate Prediction Is Equivalent to Fitting Data Tensor

As discussed in Section 4.1, the locally connected tensor network generating \(\mathcal{W}_{\mathrm{TN}}\in\mathbb{R}^{D_{1}\times\cdots\times D_{N}}\) is equivalent to a locally connected neural network, whose forward pass over a data instance \((\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(N)})\) yields \(\left\langle\otimes_{n=1}^{N}\mathbf{x}^{(n)},\mathcal{W}_{\mathrm{TN}}\right\rangle\), where \(\mathbf{x}^{(1)}\in\mathbb{R}^{D_{1}},\ldots,\mathbf{x}^{(N)}\in\mathbb{R}^{D_ {N}}\). Motivated by this fact, we consider a binary classification setting, in which the label \(y\) of the instance \((\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(N)})\) is either \(1\) or \(-1\), and the prediction \(\hat{y}\) is taken to be the sign of the output of the neural network, _i.e._\(\hat{y}=\mathrm{sign}\big{(}\big{\langle}\otimes_{n=1}^{N}\mathbf{x}^{(n)}, \mathcal{W}_{\mathrm{TN}}\big{\rangle}\big{)}\).

Suppose we are given a training set of labeled instances drawn i.i.d. from some distribution, and we would like to learn the parameters of the neural network through the soft-margin support vector machine (SVM) objective, _i.e._ by optimizing:

\[\min\!_{\|\mathcal{W}_{\mathrm{TN}}\|\leq B}\frac{1}{M}\sum\!_{m=1}^{M}\max \!\left\{0,1-y^{(m)}\big{\langle}\otimes_{n=1}^{N}\mathbf{x}^{(n,m)}, \mathcal{W}_{\mathrm{TN}}\big{\rangle}\right\}, \tag{3}\]

for a predetermined constant \(B>0\).7 We assume instances are normalized, _i.e._ the distribution is such that all vectors constituting an instance have norm no greater than one. We also assume that \(B\leq 1\). In this case \(\big{|}y^{(m)}\big{\langle}\otimes_{n=1}^{N}\mathbf{x}^{(n,m)},\mathcal{W}_{ \mathrm{TN}}\big{\rangle}\big{|}\leq 1\), so our optimization problem can be expressed as:

Footnote 7: An alternative form of the soft-margin SVM objective includes a squared Euclidean norm penalty instead of the constraint.

\[\min\!_{\|\mathcal{W}_{\mathrm{TN}}\|\leq B}1-\left\langle\mathcal{D}_{ \mathrm{emp}},\mathcal{W}_{\mathrm{TN}}\right\rangle\,,\]

where

\[\mathcal{D}_{\mathrm{emp}}:=\frac{1}{M}\sum\!_{m=1}^{M}y^{(m)}\cdot\otimes_{n =1}^{N}\mathbf{x}^{(n,m)} \tag{4}\]

is referred to as the _empirical data tensor_. This means that the accuracy over the training data is determined by how large the inner product \(\left\langle\mathcal{D}_{\mathrm{emp}},\mathcal{W}_{\mathrm{TN}}\right\rangle\) is.

Disregarding the degenerate case of \(\mathcal{D}_{\mathrm{emp}}=0\) (_i.e._ that in which the optimized objective is constant), the inner products \(\left\langle\mathcal{D}_{\mathrm{emp}},\mathcal{W}_{\mathrm{TN}}\right\rangle\) and \(\left\langle\frac{\mathcal{D}_{\mathrm{emp}}}{\|\mathcal{D}_{\mathrm{emp}}\|}, \mathcal{W}_{\mathrm{TN}}\right\rangle\) differ by only a multiplicative (positive) constant, so fitting the training data amounts to optimizing:

\[\max\!_{\|\mathcal{W}_{\mathrm{TN}}\|\leq B}\left\langle\frac{\mathcal{D}_{ \mathrm{emp}}}{\|\mathcal{D}_{\mathrm{emp}}\|},\mathcal{W}_{\mathrm{TN}}\right\rangle\,. \tag{5}\]
If \(\mathcal{W}_{\mathrm{TN}}\) can represent some \(\mathcal{W}\), then it can also represent \(c\cdot\mathcal{W}\) for every \(c\in\mathbb{R}\).8 Thus, optimizing Equation (5) is the same as optimizing:

Footnote 8: Since contraction is a multilinear operation, if a tensor network realizes \(\mathcal{W}\), then multiplying any of the tensors constituting it by \(c\) results in \(c\cdot\mathcal{W}\).

\[\max_{\mathcal{W}_{\mathrm{TN}}}\left\langle\frac{\mathcal{D}_{\mathrm{emp}}}{ \|\mathcal{D}_{\mathrm{emp}}\|},\frac{\mathcal{W}_{\mathrm{TN}}}{\|\mathcal{ W}_{\mathrm{TN}}\|}\right\rangle\,,\]

and multiplying the result by \(B\). Fitting the training data therefore boils down to minimizing \(\left\|\frac{\mathcal{W}_{\mathrm{TN}}}{\|\mathcal{W}_{\mathrm{TN}}\|}-\frac{ \mathcal{D}_{\mathrm{emp}}}{\|\mathcal{D}_{\mathrm{emp}}\|}\right\|\). In other words, the accuracy achievable over the training data is determined by the extent to which \(\frac{\mathcal{W}_{\mathrm{TN}}}{\|\mathcal{W}_{\mathrm{TN}}\|}\) can fit the normalized empirical data tensor \(\frac{\mathcal{D}_{\mathrm{emp}}}{\|\mathcal{D}_{\mathrm{emp}}\|}\).

The arguments above are independent of the training set size, and in fact apply to the population loss as well, in which case \(\mathcal{D}_{\mathrm{emp}}\) is replaced by the _population data tensor_:

\[\mathcal{D}_{\mathrm{pop}}:=\mathbb{E}_{(\mathbf{x}^{(1)},\ldots,\mathbf{x}^ {(N)}),y}\big{[}y\cdot\otimes_{n=1}^{N}\mathbf{x}^{(n)}\big{]}\,. \tag{6}\]

It follows that the achievable accuracy over the population is determined by the extent to which \(\frac{\mathcal{W}_{\mathrm{TN}}}{\|\mathcal{W}_{\mathrm{TN}}\|}\) can fit the normalized population data tensor \(\frac{\mathcal{D}_{\mathrm{pop}}}{\|\mathcal{D}_{\mathrm{pop}}\|}\). We refer to the minimal distance from it as the _suboptimality in achievable accuracy_.

**Definition 3**.: In the context of the classification setting above, the _suboptimality in achievable accuracy_ is:

\[\mathrm{SubOpt}:=\min_{\mathcal{W}_{\mathrm{TN}}}\left\|\frac{\mathcal{W}_{ \mathrm{TN}}}{\|\mathcal{W}_{\mathrm{TN}}\|}-\frac{\mathcal{D}_{\mathrm{pop}} }{\|\mathcal{D}_{\mathrm{pop}}\|}\right\|.\]

### Necessary and Sufficient Condition for Accurate Prediction

In the classification setting of Section 5.1, by invoking Theorems 1 and 2 from Section 4.2, we conclude that the suboptimality in achievable accuracy is small if and only if the population data tensor \(\mathcal{D}_{\mathrm{pop}}\) admits low entanglement under the canonical partitions of its axes (Definition 2).

**Corollary 1**.: _Consider the classification setting of Section 5.1, and let \(\epsilon\in[0,1/4]\). If there exists a canonical partition \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) (Definition 2) under which \(QE(\mathcal{D}_{\mathrm{pop}};\mathcal{K})>\ln(R)+2\epsilon\cdot\ln(D_{ \mathcal{K}})+2\sqrt{2\epsilon}\), where \(D_{\mathcal{K}}:=\min\{\prod_{n\in\mathcal{K}}D_{n},\prod_{n\in\mathcal{K}^{c }}D_{n}\}\), then:_

\[\mathrm{SubOpt}>\epsilon\,.\]

_Conversely, if for all \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) it holds that \(QE(\mathcal{D}_{\mathrm{pop}};\mathcal{K})\leq\frac{\epsilon^{2}}{8N-12}\cdot \ln(R)\),9 then:_

Footnote 9: Per the discussion in Footnote 6, when \(\epsilon\) tends to zero: _(i)_ in the absence of any knowledge regarding \(\mathcal{D}_{\mathrm{pop}}\), the entanglements required by the sufficient condition unavoidably approach zero; while _(ii)_ if it is known that for all \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) the singular values of \([\![\mathcal{D}_{\mathrm{pop}};\mathcal{K}]\!]\) trailing after the \(R\)’th one are small, then the entanglements in the sufficient condition can be on the order of \(\ln(R)\) (as they are in the necessary condition).

\[\mathrm{SubOpt}\leq\epsilon\,.\]

Proof sketch (proof in Appendix G.5).: Follows from Theorems 1 and 2 after accounting for the normalization of \(\mathcal{W}_{\mathrm{TN}}\) in the suboptimality in achievable accuracy. 

Directly evaluating the conditions required by Corollary 1 -- low entanglement under canonical partitions for \(\mathcal{D}_{\mathrm{pop}}\) -- is impractical, since: _(i)_\(\mathcal{D}_{\mathrm{pop}}\) is defined via an unknown data distribution (Equation (6)); and _(ii)_ computing the entanglements involves taking singular value decompositions of matrices with size exponential in the number of input variables \(N\). Fortunately, as Proposition 1 below shows, the entanglements of \(\mathcal{D}_{\mathrm{pop}}\) under all partitions are with high probability well-approximated by the entanglements of the empirical data tensor \(\mathcal{D}_{\mathrm{emp}}\). Moreover, the entanglement of \(\mathcal{D}_{\mathrm{emp}}\) under any partition can be computed efficiently, without explicitly storing or manipulating an exponentially large matrix -- see Appendix B for an algorithm (originally proposed in [41]). Overall, we obtain an efficiently computable criterion (low entanglement under canonical partitions for \(\mathcal{D}_{\mathrm{emp}}\)), that with high probability is both necessary and sufficient for low suboptimality in achievable accuracy -- see Corollary 2 below.
**Proposition 1**.: _Consider the classification setting of Section 5.1, and let \(\delta\in(0,1)\) and \(\gamma>0\). If the training set size \(M\) satisfies \(M\geq\frac{128\ln(\frac{2}{3})(\ln(\max_{\mathcal{K}^{c}\subseteq[N]}\mathcal{D} _{\mathcal{K}^{c}}))^{4}}{\|\mathcal{D}_{\mathrm{pop}}\|^{2}\gamma^{4}}\), where \(D_{\mathcal{K}^{c}}:=\min\{\prod_{n\in\mathcal{K}^{c}}D_{n},\prod_{n\in \mathcal{K}^{c}}D_{n}\}\) for \(\mathcal{K}^{c}\subseteq[N]\), then with probability at least \(1-\delta\):_

\[|QE(\mathcal{D}_{\mathrm{emp}};\mathcal{K})-QE(\mathcal{D}_{\mathrm{pop}}; \mathcal{K})|\leq\gamma\,\text{ for all }\mathcal{K}\subseteq[N]\text{.}\]

Proof sketch (proof in Appendix G.4).: A standard generalization of the Hoeffding inequality to random vectors in a Hilbert space allows bounding \(\|\mathcal{D}_{\mathrm{emp}}-\mathcal{D}_{\mathrm{pop}}\|\) with high probability. Bounding differences between entanglements via Euclidean distance concludes the proof. 

**Corollary 2**.: _Consider the setting and notation of Corollary 1, with \(\epsilon\neq 0\). For \(\delta\in(0,1)\), suppose that the training set size \(M\) satisfies \(M\geq\frac{128\ln(\frac{2}{3})((16N-24)\ln(\max_{\mathcal{K}^{c}\subseteq[N]}D _{\mathcal{K}^{c}}))^{4}}{\|\mathcal{D}_{\mathrm{pop}}\|^{2}(\ln(R)\cdot \epsilon^{2})^{4}}\). Then, with probability at least \(1-\delta\) the following hold. First, if there exists a canonical partition \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) (Definition 2) under which \(QE(\mathcal{D}_{\mathrm{emp}};\mathcal{K})>(1+\frac{\epsilon^{2}}{16N-24}) \cdot\ln(R)+2\epsilon\cdot\ln(D_{\mathcal{K}})+2\sqrt{2\epsilon}\), then:_

\[\mathrm{SubOpt}>\epsilon\,.\]

_Second, if for all \((\mathcal{K},\mathcal{K}^{c})\in\mathcal{C}_{N}\) it holds that \(QE(\mathcal{D}_{\mathrm{emp}};\mathcal{K})\leq\frac{\epsilon^{2}}{16N-24}\cdot \ln(R)\), then:_

\[\mathrm{SubOpt}\leq\epsilon\,.\]

_Moreover, the conditions above on the entanglements of \(\mathcal{D}_{\mathrm{emp}}\) can be evaluated efficiently (in \(\mathcal{O}(DN^{2}M^{2}+NM^{3})\) time \(\mathcal{O}(DNM+M^{2})\) and memory, where \(D:=\max_{n\in[N]}D_{n}\))._

Proof.: Implied by Corollary 1, Proposition 1 with \(\gamma=\frac{\epsilon^{2}}{16N-24}\cdot\ln(R)\) and Algorithm 2 in Appendix B. 

### Empirical Demonstration

Corollary 2 establishes that, with high probability, the locally connected tensor network (from Section 4.1) can achieve high prediction accuracy if and only if the empirical data tensor (Equation (4)) admits low entanglement under canonical partitions of its axes. We corroborate our formal analysis through experiments, demonstrating that its conclusions carry over to common locally connected architectures. Namely, applying convolutional neural networks, S4 (a popular recurrent neural network; see [26]), and a local self-attention model [60] to different datasets, we show that the achieved test accuracy is inversely correlated with the entanglements of the empirical data tensor under canonical partitions. Below is a description of experiments with one-dimensional (_i.e._ sequential) models and data. Additional experiments with two-dimensional (imagery) models and data are given in Appendix E.2.3.

Discerning the relation between entanglements of the empirical data tensor and performance (prediction accuracy) of locally connected neural networks requires datasets admitting different entanglements. A potential way to acquire such datasets is as follows. First, select one a dataset which locally connected neural networks perform well, in the hopes that it admits low entanglement under canonical partitions; natural candidates are datasets comprising images, text or audio. Subsequently, create "shuffled" variants of the dataset by repeatedly swapping the position of two features chosen at random.10 This erodes the original arrangement of features in the data, and is expected to yield higher entanglement under canonical partitions.

Footnote 10: It is known that as the number of random position swaps goes to infinity, the arrangement of the features converges to a random permutation [19].

We followed the blueprint above for a binary classification version of the Speech Commands audio dataset [63]. Figure 4 presents test accuracies achieved by a convolutional neural network, S4, and a local self-attention model, as well as average entanglement under canonical partitions of the empirical data tensor, against the number of random feature swaps performed to create the dataset. As expected, when the number of swaps increases, the average entanglement under canonical partitions becomes higher. At the same time, in accordance with our theory, the prediction accuracies of the locally connected neural networks substantially deteriorate, showing an inverse correlation with the entanglement under canonical partitions.
## 6 Enhancing Suitability of Data to Locally Connected Neural Networks

Our analysis (Sections 4 and 5) suggests that a data distribution is suitable for locally connected neural networks if and only if it admits low entanglement under canonical partitions of features. Motivated by this observation, we derive a preprocessing algorithm aimed to enhance the suitability of a data distribution to locally connected neural networks (Sections 6.1 and 6.2). Empirical evaluations demonstrate that it significantly improves prediction accuracies of common locally connected neural networks on various datasets (Section 6.3). For conciseness, the treatment in this section is limited to one-dimensional (sequential) models and data; see Appendix E.3 for an extension to arbitrary dimensions.

### Search for Feature Arrangement With Low Entanglement Under Canonical Partitions

Our analysis naturally leads to a recipe for enhancing the suitability of a data distribution to locally connected neural networks: given a dataset, search for an arrangement of features which leads to low entanglement under canonical partitions, and then arrange the features accordingly. Formally, suppose we have \(M\in\mathbb{N}\) training instances \(\left\{\left((\mathbf{x}^{(1,m)},\ldots,\mathbf{x}^{(N,m)}),y^{(m)}\right) \right\}_{m=1}^{M}\), where \(y^{(m)}\in\{1,-1\}\) and \(\mathbf{x}^{(n,m)}\in\mathbb{R}^{D}\) for \(n\in[N],m\in[M]\), with \(D\in\mathbb{N}\). Assume without loss of generality that \(N\) is a power of two (if this is not the case we may add constant features as needed). The aforementioned recipe boils down to a search for a permutation \(\pi:[N]\rightarrow[N]\), which when applied to feature indices leads the empirical data tensor \(\mathcal{D}_{\mathrm{emp}}\) (Equation (4)) to admit low entanglement under the canonical partitions of its axes (Definition 2).

A greedy realization of the foregoing search is as follows. Initially, partition the features into two equally sized sets \(\mathcal{K}_{1,1}\subset[N]\) and \(\mathcal{K}_{1,2}:=[N]\setminus\mathcal{K}_{1,1}\) such that the entanglement of \(\mathcal{D}_{\mathrm{emp}}\) with respect to \((\mathcal{K}_{1,1},\mathcal{K}_{1,2})\) is minimal. That is, find \(\mathcal{K}_{1,1}\in\mathrm{argmin}_{\mathcal{K}\subset[N],|\mathcal{K}|=N/2} \,QE(\mathcal{D}_{\mathrm{emp}};\mathcal{K})\). The permutation \(\pi\) will map \(\mathcal{K}_{1,1}\) to coordinates \(\{1,\ldots,\frac{N}{4}\}\) and \(\mathcal{K}_{1,2}\) to \(\{\frac{N}{2}+1,\ldots,N\}\). Then, partition \(\mathcal{K}_{1,1}\) into two equally sized sets \(\mathcal{K}_{2,1}\subset\mathcal{K}_{1,1}\) and \(\mathcal{K}_{2,2}:=\mathcal{K}_{1,1}\setminus\mathcal{K}_{2,1}\) such that the average of entanglements induced by these sets is minimal, _i.e._\(\mathcal{K}_{2,1}\in\mathrm{argmin}_{\mathcal{K}\subset\mathcal{K}_{1,1},| \mathcal{K}|=|\mathcal{K}_{1,1}|/2}\,\frac{1}{2}\big{[}QE(\mathcal{D}_{\mathrm{emp }};\mathcal{K})+QE(\mathcal{D}_{\mathrm{emp}};\mathcal{K}_{1,1}\setminus \mathcal{K})\big{]}\). The permutation \(\pi\) will map \(\mathcal{K}_{2,1}\) to coordinates \(\{1,\ldots,\frac{N}{4}\}\) and \(\mathcal{K}_{2,2}\) to \(\{\frac{N}{4}+1,\ldots,\frac{N}{2}\}\). A partition of \(\mathcal{K}_{1,2}\) into two equally sized sets \(\mathcal{K}_{2,3}\) and \(\mathcal{K}_{2,4}\) is obtained similarly, where \(\pi\) will map \(\mathcal{K}_{2,3}\) to coordinates \(\{\frac{N}{2}+1,\ldots,\frac{3N}{4}\}\) and \(\mathcal{K}_{2,4}\) to \(\{\frac{3N}{4}+1,\ldots,N\}\). Continuing in the same fashion, until we reach subsets \(\mathcal{K}_{L,1},\ldots,\mathcal{K}_{L,N}\) consisting of a single feature index each, fully specifies the permutation \(\pi\).

Unfortunately, the step lying at the heart of the above scheme -- finding a balanced partition that minimizes average entanglement -- is computationally prohibitive, and we are not aware of any

Figure 4: The prediction accuracies of common locally connected neural networks are inversely correlated with the entanglements of the data under canonical partitions of features, in compliance with our theory (Sections 5.1 and 5.2). **Left:** Average entanglement under canonical partitions (Definition 2) of the empirical data tensor (Equation (4)), for binary classification variants of the Speech Commands audio dataset [63] obtained by performing random position swaps between features. **Right:** Test accuracies achieved by a convolutional neural network (CNN) [17], S4 (a popular class of recurrent neural networks; see [26]), and a local self-attention model [60], against the number of random feature swaps performed to create the dataset. **All:** Reported are the means and standard deviations of the quantities specified above, taken over ten different random seeds. See Appendix E.2.3 for experiments over (two-dimensional) image data and Appendix F for further implementation details.
tools that alleviate the computational difficulty. In the next subsection we will see that replacing entanglement with a surrogate measure paves way to a practical implementation.

### Practical Algorithm via Surrogate for Entanglement

To efficiently implement the scheme from Section 6.1, we replace entanglement with a surrogate measure of dependence. The surrogate is based on the Pearson correlation coefficient for multivariate features [46],11 and its agreement with entanglement is demonstrated empirically in Appendix D. Theoretically supporting this agreement is left for future work.

Footnote 11: For completeness, Appendix C provides a formal definition of the multivariate Pearson correlation.

**Definition 4**.: Given a set of \(M\in\mathbb{N}\) instances \(\mathcal{X}:=\{(\mathbf{x}^{(1,m)},\ldots,\mathbf{x}^{(N,m)})\in(\mathbb{R}^ {D})^{N}\}_{m=1}^{M}\), denote by \(p_{n,n^{\prime}}\) the multivariate Pearson correlation between features \(n,n^{\prime}\in[N]\). For \(\mathcal{K}\subseteq[N]\), the _surrogate entanglement_ of \(\mathcal{X}\) with respect to the partition \((\mathcal{K},\mathcal{K}^{c})\), denoted \(SE(\mathcal{X};\mathcal{K})\), is the sum of Pearson correlation coefficients between pairs of features, the first belonging to \(\mathcal{K}\) and the second to \(\mathcal{K}^{c}:=[N]\setminus\mathcal{K}\). That is:

\[SE\big{(}\mathcal{X};\mathcal{K}\big{)}:=\sum\nolimits_{n\in\mathcal{K},n^{ \prime}\in\mathcal{K}^{c}}p_{n,n^{\prime}}\,.\]

As shown in Proposition 2 below, replacing entanglement with surrogate entanglement in the scheme from Section 6.1 converts each search for a balanced partition minimizing average entanglement into a _minimum balanced cut problem_. Although the minimum balanced cut problem is NP-hard (see, _e.g._, [23]), it enjoys a wide array of well-established approximation tools, particularly ones designed for large scale [29; 57]. We therefore obtain a practical algorithm for enhancing the suitability of a data distribution to locally connected neural networks -- see Algorithm 1.

**Proposition 2**.: _For any \(\bar{\mathcal{K}}\subseteq[N]\) of even size, the following optimization problem can be framed as a minimum balanced cut problem over a complete graph with \(|\bar{\mathcal{K}}|\) vertices:_

\[\min_{\mathcal{K}\subset\bar{\mathcal{K}},|\mathcal{K}|=|\bar{\mathcal{K}}|/2} \frac{1}{2}\Big{[}SE\big{(}\mathcal{X};\mathcal{K}\big{)}+SE\big{(}\mathcal{ X};\bar{\mathcal{K}}\setminus\mathcal{K}\big{)}\Big{]}\,. \tag{7}\]

_Specifically, there exists a complete undirected weighted graph with vertices \(\bar{\mathcal{K}}\) and edge weights \(w:\bar{\mathcal{K}}\times\bar{\mathcal{K}}\to\mathbb{R}\) such that for any \(\mathcal{K}\subset\bar{\mathcal{K}}\), the weight of the cut in the graph induced by \(\bar{\mathcal{K}}\) -- \(\sum_{n\in\mathcal{K},n^{\prime}\in\bar{\mathcal{K}}\setminus\mathcal{K}}w(\{ n,n^{\prime}\})\) -- is equal, up to an additive constant, to the term minimized in Equation (7), i.e. to \(\frac{1}{2}\big{[}SE\big{(}\mathcal{X};\mathcal{K}\big{)}+SE\big{(}\mathcal{ X};\bar{\mathcal{K}}\setminus\mathcal{K}\big{)}\big{]}\)._

Proof.: Consider the complete undirected graph whose vertices are \(\bar{\mathcal{K}}\) and where the weight of an edge \(\{n,n^{\prime}\}\in\bar{\mathcal{K}}\times\bar{\mathcal{K}}\) is \(w(\{n,n^{\prime}\})=p_{n,n^{\prime}}\) (recall that \(p_{n,n^{\prime}}\) stands for the multivariate Pearson correlation between features \(n\) and \(n^{\prime}\) in \(\mathcal{X}\)). For any \(\mathcal{K}\subset\bar{\mathcal{K}}\) it holds that:

\[\sum\nolimits_{n\in\mathcal{K},n^{\prime}\in\bar{\mathcal{K}}\setminus\mathcal{ K}}w(\{n,n^{\prime}\})=\frac{1}{2}\Big{[}SE\big{(}\mathcal{X};\mathcal{K} \big{)}+SE\big{(}\mathcal{X};\bar{\mathcal{K}}\setminus\mathcal{K}\big{)} \Big{]}-\frac{1}{2}SE\big{(}\mathcal{X};\bar{\mathcal{K}}\big{)}\,,\]

where \(\frac{1}{2}SE\big{(}\mathcal{X};\bar{\mathcal{K}}\big{)}\) does not depend on \(\mathcal{K}\). This concludes the proof. 

### Experiments

We empirically evaluate Algorithm 1 using common locally connected neural networks -- a convolutional neural network, an S4 (popular recurrent neural network; see [26], and a local self-attention model [60] -- over randomly permuted audio datasets (Section 6.3.1) and several tabular datasets (Section 6.3.2). For brevity, we defer some implementation details to Appendix F.

#### 6.3.1 Randomly Permuted Audio Datasets

Section 5.3 demonstrated that audio data admits low entanglement under canonical partitions of features, and that randomly permuting the position of features leads this entanglement to increase, while substantially degrading the prediction accuracy of locally connected neural networks. A sensible test for Algorithm 1 is to evaluate its ability to recover performance lost due to the random permutation of features.
```
1:Input:\(\mathcal{X}:=\{(\mathbf{x}^{(1,m)},\ldots,\mathbf{x}^{(N,m)})\}_{m=1}^{M}\)\(\ldots\)\(M\in\mathbb{N}\) data instances comprising \(N\in\mathbb{N}\) features
2:Output: Permutation \(\pi:[N]\rightarrow[N]\) to apply to feature indices
3:Let \(\mathcal{K}_{0,1}:=[N]\) and denote \(L:=\log_{2}(N)\)
4:# We assume for simplicity that \(N\) is a power of two, otherwise one may add constant features
5:for\(l=0,\ldots,L-1\), \(n=1,\ldots,2^{l}\)do
6: Using a reduction to a minimum balanced cut problem (Proposition 2), find an approximate solution \(\mathcal{K}_{l+1,2n-1}\subset\mathcal{K}_{l,n}\) for: \[\min_{\mathcal{K}\subset\mathcal{K}_{l,n},|\mathcal{K}|=|\mathcal{K}_{l,n}|/2} \frac{1}{2}[SE(\mathcal{X};\mathcal{K})+SE(\mathcal{X};\mathcal{K}_{l,n} \setminus\mathcal{K})]\]
7: Let \(\mathcal{K}_{l+1,2n}:=\mathcal{K}_{l,n}\setminus\mathcal{K}_{l+1,2n-1}\)
8:endfor
9:# At this point, \(\mathcal{K}_{L,1},\ldots,\mathcal{K}_{L,N}\) each contain a single feature index
10:return\(\pi\) that maps \(k\in\mathcal{K}_{L,n}\) to \(n\), for every \(n\in[N]\)
```

**Algorithm 1** Enhancing Suitability of Data to Locally Connected Neural Networks

For the Speech Commands dataset [63], Table 1 compares the prediction accuracies of locally connected neural networks on: _(i)_ the data subject to a random permutation of features; _(ii)_ the data attained after rearranging the randomly permuted features via Algorithm 1; and _(iii)_ the data attained after rearranging the randomly permuted features via IGTD [65] -- a heuristic scheme designed for convolutional neural networks (see Section 2). As can be seen, Algorithm 1 leads to significant improvements, surpassing those brought forth by IGTD. Note that Algorithm 1 does not entirely recover the performance lost due to the random permutation of features.12 We believe this relates to phenomena outside the scope of the theory underlying Algorithm 1 (Sections 4 and 5), for example translation invariance in data being beneficial in terms of generalization. Investigation of such phenomena and suitable modification of Algorithm 1 are regarded as promising directions for future work.

Footnote 12: The prediction accuracies on the original data are \(59.8\ \pm\ 2.6\), \(69.6\ \pm\ 0.6\) and \(48.1\ \pm\ 2.1\) for CNN, S4 and Local-Attention, respectively.

#### 6.3.2 Tabular Datasets

The prediction accuracies of locally connected neural networks on tabular data, _i.e._ on data in which features are arranged arbitrarily, is known to be subpar [56]. Table 2 reports results of experiments with locally connected neural networks over standard tabular benchmarks (namely "dna", "semeion" and "isolet" [61]), demonstrating that arranging features via Algorithm 1 leads to

\begin{table}
\begin{tabular}{l c c c} \hline \hline  & Randomly Permuted & Algorithm 1 & IGTD \\ \hline CNN & \(5.2\ \pm\ 0.7\) & \(\mathbf{17.4}\ \pm\ 1.7\) & \(6.1\ \pm\ 0.4\) \\ S4 & \(9.5\ \pm\ 0.6\) & \(\mathbf{30.3}\ \pm\ 1.6\) & \(13\ \pm\ 2.4\) \\ Local-Attention & \(7.8\ \pm\ 0.3\) & \(\mathbf{12.9}\ \pm\ 0.7\) & \(6.4\ \pm\ 0.5\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Arranging features of randomly permuted audio data via Algorithm 1 significantly improves the prediction accuracies of locally connected neural networks. Reported are test accuracies (mean and standard deviation over ten random seeds) of a convolutional neural network (CNN), S4 (a popular recurrent neural network; see [26]), and a local self-attention model [60], over the Speech Commands dataset [63] subject to different arrangements of features: _(i)_ a random arrangement; _(ii)_ an arrangement provided by applying Algorithm 1 to the random arrangement; and _(iii)_ an arrangement provided by applying an adaptation of IGTD [65] — a heuristic scheme designed for convolutional neural networks — to the random arrangement. For each model, we highlight (in boldface) the highest mean accuracy if the difference between that and the second-highest mean accuracy is statistically significant (namely), is larger than the sum of corresponding standard deviations). As can be seen, Algorithm 1 leads to significant improvements in prediction accuracies, surpassing the improvements brought forth by IGTD. See Appendix F for implementation details.
significant improvements in prediction accuracies, surpassing improvements brought forth by IGTD (a heuristic scheme designed for convolutional neural networks [65]). Note that Algorithm 1 does not lead to state of the art prediction accuracies on the evaluated benchmarks.13 However, the results suggest that it renders locally connected neural networks a viable option for tabular data. This option is particularly appealing in when the number of features is large settings, where many alternative approaches (_e.g._ ones involving fully connected neural networks) are impractical.

Footnote 13: XGBoost for example achieves prediction accuracies \(96\), \(91\) and \(95.2\) over dna, semeion and isolet, respectively.

## 7 Conclusion

The question of what makes a data distribution suitable for deep learning is a fundamental open problem. Focusing on locally connected neural networks -- a prevalent family of deep learning architectures that includes as special cases convolutional neural networks, recurrent neural networks (in particular the recent S4 models) and local self-attention models -- we address this problem by adopting theoretical tools from quantum physics. Our main theoretical result states that a certain locally connected neural network is capable of accurate prediction (_i.e._ can express a solution with low population loss) over a data distribution _if and only if_ the data distribution admits low quantum entanglement under certain canonical partitions of features. Experiments with widespread locally connected neural networks corroborate this finding.

Our theory suggests that the suitability of a data distribution to locally connected neural networks may be enhanced by arranging features such that low entanglement under canonical partitions is attained. Employing a certain surrogate for entanglement, we show that this arrangement can be implemented efficiently, and that it leads to substantial improvements in the prediction accuracies of common locally connected neural networks on various datasets.

The data modalities to which deep learning is most commonly applied -- namely ones involving images, text and audio -- are often regarded as natural (as opposed to, for example, tabular data

\begin{table}
\begin{tabular}{l l l l} \multicolumn{4}{l}{Dataset: dna} \\ \hline  & Baseline & Algorithm 1 & IGTD \\ \hline CNN & \(81.1\pm 2.2\) & \(\mathbf{91.1}\pm 0.7\) & \(86.9\pm 0.7\) \\ S4 & \(87.7\pm 2.3\) & \(89.8\pm 2.9\) & \(90\pm 1.2\) \\ Local-Attention & \(77.5\pm 3.6\) & \(\mathbf{85.5}\pm 3.6\) & \(81\pm 2.5\) \\ \hline \multicolumn{4}{l}{Dataset: semeion} \\ \hline  & Baseline & Algorithm 1 & IGTD \\ \hline CNN & \(77.5\pm 1.8\) & \(80.7\pm 1\) & \(80.2\pm 1.8\) \\ S4 & \(82.6\pm 1.1\) & \(\mathbf{89.8}\pm 0.5\) & \(85.9\pm 0.7\) \\ Local-Attention & \(60.6\pm 3.8\) & \(\mathbf{78.6}\pm 1.3\) & \(68\pm 0.9\) \\ \hline \multicolumn{4}{l}{Dataset: isolet} \\ \hline  & Baseline & Algorithm 1 & IGTD \\ \hline CNN & \(91.6\pm 0.4\) & \(92.5\pm 0.4\) & \(90.5\pm 2.2\) \\ S4 & \(92\pm 0.3\) & \(93.3\pm 0.5\) & \(92.8\pm 0.3\) \\ Local-Attention & \(78\pm 2.0\) & \(\mathbf{87.7}\pm 0.4\) & \(83.9\pm 0.8\) \\ \hline \end{tabular}
\end{table}
Table 2: Arranging features of tabular datasets via Algorithm 1 significantly improves the prediction accuracies of locally connected neural networks. Reported are results of experiments analogous to those of Table 1, but with the “dna”, “semeion” and “isolet” tabular classification datasets [61]. Since to the arrangement of features in a tabular dataset is intended to be arbitrary, we regard as a baseline the prediction accuracies attained with a random permutation of features. For each combination of dataset and model, we highlight (in boldface) the highest mean accuracy if the difference between that and the second-highest mean accuracy is statistically significant (namely, is larger than the sum of corresponding standard deviations). Notice that, as in the experiment of Table 1, rearranging the features according to Algorithm 1 leads to significant improvements in prediction accuracies, surpassing the improvements brought forth by IGTD. See Appendix F for implementation details.
fusing heterogeneous information). We believe the difficulty in explaining the suitability of such modalities to deep learning may be due to a shortage in tools for formally reasoning about natural data. Concepts and tools from physics -- a branch of science concerned with formally reasoning about natural phenomena -- may be key to overcoming said difficulty. We hope that our use of quantum entanglement will encourage further research along this line.

## Acknowledgments and Disclosure of Funding

This work was supported by a Google Research Scholar Award, a Google Research Gift, the Yandex Initiative in Machine Learning, the Israel Science Foundation (grant 1780/21), Len Blavatnik and the Blavatnik Family Foundation, and Amnon and Anat Shashua. NR is supported by the Apple Scholars in AI/ML and the Tel Aviv University Center for AI and Data Science (TAD) PhD fellowships.
