What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement.
Authors: Yotam Alexander
Nimrod De La Vega
Noam Razin
Nadav Cohen
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Deep Learning
Locally Connected Neural Networks
Data Distributions
Quantum Entanglement
Tensor Networks
TL;DR: Importing tools from quantum physics and tensor analysis, we study what makes a data distribution suitable for locally connected neural networks, and develop, based on our theory, an algorithm for enhancing the suitability of data to such models.

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.

What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement
Yotam Alexander',
Nimrod De La Vega", Noam Razin, Nadav Cohen Tel Aviv University
ninrod,, nimrodd, www.mooommmnnnooo in tau. ac il, cohennadav8cs tau. ac.
Abstract
The question of what makes data distribution suitable for deep learning is funda- mental open problem. Focusing on locally connected neural networks (a prevalent family of architectures that includes convolutional and recurrent neural networks well as local self-attention models), we address this problem by adopting theoretical tools from quantum physics. Our main theoretical result states that certain locally connected neural network capable of accurate prediction over data distribution and only if the data distribution admits low quantum entanglement under certain canonical partitions of features. As practical application of this result, derive 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 quantum entanglement will encourage further adoption of tools from physics for formally reasoning about the relation between deep learning and
data.
Introduction
Deep learning delivering unprecedented performance when applied 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 data distribution suitable for deep learning is a fundamental open problem in the field.
which deep learning utterly fails. The question of what makes
prevalent family of deep learning architectures is that of locally connected neural networks. 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 resurgence by virtue of S4 models [26]; and (iii) local variants self-attention neural networks [46]. 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 [66, 28, 15]. However, to the best of our knowledge, there are no characterizations providing necessary and sufficient conditions for data distribution be suitable a locally connected neural network.
seemingly distinct scientific discipline tying distributions and computational models is quantum physics. There, distributions of interest are described by lensors, and the associated computational models are tensor networks. While there 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 the notion of quantum
"Fqual contribution
'Due to lack of space, significant portion of the paper deferred to the appendices. We refer reader to [2] for a self-cootained version of the text.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

entanglement, which quantifies dependencies that tensor admits under partitions of its axes (for a given tensor A and a partition of its axes to sets K and IC", the entanglement is a non- non-negative number quantifying the dependence that A admits between K. and KC").
In this paper, we apply the foregoing theory to a tensor network equivalent to 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 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 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 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 data distribution 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, based measure as a surrogate for entanglement, i.e. as a gauge for dependence between sides of partition of features, then the search converts into a succession of minimum bulanced cuf 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 substantially improves prediction accuracy of common locally connected neural networks (including modern convolutional, recurrent, and local self-attention neural networks).
we employ certain correlation-
The data modalities 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.
2 Preliminaries
For simplicity, the main text treats locally connected neural networks whose input data is one dimensional (e.g. text audio). We defer to Appendix J extension of the analysis and experiments to models intaking data of arbitrary dimension (e.g. two-dimensional images). Due to lack of space, we also defer our review of related work to Appendix A.
We use Il and (: to denote the Euclidean (Frobenius) norm and inner product, respectively. We shorthand [N] = (1....,N), N), where N E N. The complement of K. C [N] is denoted by JC",
i.e. 1C := [ A.C.
2.1 Tensors and Tensor Networks
For our purposes, a tensor is an array with multiple axes A E Dix DN, where N E N is its order and Di,..., DN E N are its axes lengths. The (di...., .....,,,)) )x I'th entry of A is denoted Ad,....Nn Contraction between tensors is generalization of multiplication between matrices. Two matrices A E xD> and E x can be multiplied if D2 = D', in which case we get a matrix in D xD' holding Dde, Adj.d Ba,d; in entry (di, dg,) E [DI]] x [D}]. More generally, two tensors A E TR. DR x... Dx and B E DDD'xx'D''s can be contracted along axis n E [N] of A and n' E [N'] of B if D2 n = =D,,, in which case we get tensor of size D1 x.. D,, x Dn41 X ... x DN X Dí X
x 1 x Dar41" x D'y' holding Dd= Adi....d, Idd.d..i....ddd BB.....d de in the entry indexed by {de E [DAI)REINT)) and {d' E [DiDkeeNTTNN"
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 (typically high-order)

---

D2
W
D1
Mv
M
D2
D2
Dy
(a)
(b)
(c)
Figure Tensor networks form graphical language fitting (i.e. representing) tensors through lensor contractions. Tensor network definition: Every node in a tensor network is associated with a tensor, whosc order 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 2) where the weight of the edge signifies the respective axes lengths. Tensor networks may also contain open edges, i.e. edges that connected to node one side and open on the other. The number of such open edges is equal the order of the tensor produced by contracting the lensor network. Illustrations: Presented are exemplar tensor network diagrams of: (a) an order N tensor A E R Xx>xxx; x (b) vector matrix multiplication between M E _e x D2 and E I Ds, which results in vector Mv E R P and (c) tensor network generating W Dr Ds
tensor via contractions between (typically low-order) tensors. As customary (cf. [42]), we will present tensor networks via graphical diagrams to avoid cumbersome notation see Figure for details.
2.2 Quantum Entanglement
In quantum physics, the distribution of possible states for a multi 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 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 's description as tensor see Definition I below.
Quantum entanglement lies at the heart of widely accepted theory which allows assessing the ability of tensor network to fit given tensor (cf. [16, 35]). In Section 3 we specialize this theory to a tensor certain locally connected neural network. The specialized theory will be used (in Section 4) to establish our main theoretical contribution: a necessary and sufficient condition for when the locally connected neural network is capable of accurate prediction
network equivalent
data distribution.
Definition 1. For tensor A E D xD and subset of its axes K. C [N], let [A:A] E RlTex P. xIInexs Dn be the arrangement of A as matrix where columns correspond to the remaining axes 1C := [N]]K. Denote by 0 2 ... 2 DD E Rxo the sin- gular values of [A;; K], where Dx min A with respect to the partition (C") is the entropy of the distribution {ps o Dr o Id=1" iec. QE(A:K) == Ede Pa In(p)). By convention, = then QE(A;; = 0.
correspond to axes K. and
Dn, ImExx D,). The quantum entanglement of DR
3 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 fit 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 3.1). Subsequently, we establish the necessary and sufficient condition required for it to fit given tensor (Section 3.2). For conciseness, the treatment in this section is limited to one-dimensional (sequential) models; see Appendix J. for an extension to arbitrary dimensions.
3.1 Tensor Network Equivalent to Locally Connected Neural Network
Let N N, and for simplicity suppose that N = - for some L E N. We consider a tensor network with an underlying perfect binary tree graph of height L, which generates WIN IR xpx..xxxx... Figure 2(a) provides its diagrammatic definition. For simplicity of presentation, the lengths of axes corresponding to inner (non-open) edges are taken all be equal some R N, referred to as the width of the tensor network.
"There exist multiple notions of entanglement in quantum physics (see, e.g., [35]). The one consider is the most common, known entanglement entropy.
3

---

WIN
( win)
WTx
Pa-1
12 122 1/5 04 (a)
Py-2
0g-4
Dy
(b)
Figure 2: The analyzed tensor network equivalent locally connected neural network. (a) We consider
tensor network adhering to perfect binary tree connectivity with N = 2 leaf nodes, for L E N. generating Wrn E PP Xx Axes corresponding to open edges are indexed such that open edges descendant any node of the tree have contiguous indices. The lengths of axes corresponding inner (non-open) edges are equal to E N. referred to as the width the tensor network. (b) Contracting WTN with vectors (N) E It produces (07=1x(" Wrs). Performing these contractions from leaves to root can be viewed as forward pass of a data instance (x(*) .....
,...,''' x (N) through a certain locally connected neural network (with polynomial non-linearity; see, e.g. [12, 10, 35, 49]). Accordingly, we call the tensor network generating WIN locally connected tensor network.
As identified by previous works, the tensor network depicted in Figure 2(a) is equivalent to certain
locally connected neural network (with polynomial non-linearity - see, e.g., [12, 10, 35, 49)). In
particular, contracting the tensor network with vectors x(1) ,....... x()) E DN as illustrated in Figure 2(b), can be viewed as a forward pass of the data instance (x(2), ,...., xN)) through locally connected neural network, whose hidden layers are of width R. This computation results in a
scalar equal to ( WrN). where @ stands for the outer product. 3 In light of its equivalence to locally connected neural network, we will refer to the tensor network tensor network. We note that for the equivalent neural network to practical (in terms of memory and runtime), the width R needs to be of moderate size (typically no more than few thousands). Specifically, R cannot be exponential in the order N, meaning In(R) needs to be much smaller than N. By virtue of the locally connected tensor network's 's equivalence to deep neural network, it has been paramount for the study of expressiveness and generalization in deep learning [12, 9, 10, 13, 14, 54, 34, 35, 3, 30, 31, 36, 47, 48, 49, 50]. 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 theoretical analyses, through the 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 4.3), and employ our theory for deriving an algorithm that enhances the suitability of a data distribution said architectures (Section 5).
locally connected
3.2 Necessary and Sufficient Condition for Fitting Tensor
Herein we show that the ability of the locally connected tensor network (defined in Section 3.1) to fit (i.e. represent) a given tensor is determined by the entanglements that the tensor admits under the below-defined canonical partitions of [N]. Note that each canonical partition comprises a subset of contiguous indices, so low entanglement under canonical partitions can be viewed as a formalization of locality.
Definition 2. The canonical partitions of [N] = [24] (illustrated in Figure 4 of Appendix B) are:
CN = (K, KC K= (22-1, (n + ,,..,,,.,.. 24-1 n}. lE (o...... 4). [21]].
By appealing known upper bounds the entanglements that given tensor network supports [16. 35], we now establish that if the locally connected tensor network can fit a given tensor, that tensor
'For any (x( E B PeP N I= the outer product x (1) E R DD is defined element-wise by
N (1)) dyy....y = 1I x where di [Di]..... dN [Dx].

---

must admit low entanglement under the canonical partitions of its axes. Namely, suppose that WIN - the tensor generated by the locally connected tensor network - well-approximates an order N tensor A. Then, Theorem below shows that the entanglement of A with respect to every canonical partition (K., KC9) CN cannot be much larger than In (R) (recall that R is the width of the locally connected tensor network, and that in practical settings In( Rt) is much smaller than N), whereas the expected entanglement of random tensor with respect to (C)) is on the order of min (KC) | (which is linear in N for most canonical partitions).
In the other direction, Theorem 2 below implics that low entanglement under the canonical partitions not only necessary for a tensor to be fit by the locally connected tensor network, but also sufficient.
x-.xx Theorem 1. Let Wix E Px DN be a tensor generated by the locally connected tensor network defined in Section 3.1, and let A E DD,x.." DDxx."DD, For any [0. ||A|| /4], if J|WTN A] c. then for all canonical partitions (K E CN (Definition 2) it holds that QE(A:K)
< In
TAAII (n(D)))2
2c
[[A|I where Dx == min[IInex Dn. Inees= D. In contrast, a random tensor
2e
A' E ERD, D.....DDD drawn according the uniform distribution over the set of unit norm tensors. satisfies ([QF((A'))))) X.] 2 min [ell)I((minne D₂) + (n(()) 2 for all canonical partitions E
Proof sketch (proof in Appendix M.2). In general. the entanglements that a tensor network supports can be upper bounded through cuts in its graph [16, 35]. For the locally connected tensor network, these bounds imply that QE(WiN;; K.) S In(R) for any canonical partition (K., K.9). The upper bounds on the entanglements of A then follow by showing that if Wrn and A are close, then so are their entanglements. The lower bounds on the expected entanglements of a random tensor are derived based on a characterization from [52].
Theorem 2. Let A E R. Xx and 0. Suppose that for all canonical partitions (K,, K.))
CN (Definition 2) it holds that QE(A:K) K3) S (2N-3) In()). Then, there exists an assignment for the tensors constituting the locally connected tensor network (defined in Section 3.1) such that it generates WIN E P.Pxx satisfying [|WNN All S.
Proof sketch (proof in Appendix M.3). We show that has low entanglement under a canonical partition (X, KC9) E Cn. then the singular values of [A: XC] must decay rapidly (recall that [4; []] the arrangement of A as matrix where rows correspond to axes indexed by K. and columns correspond to the remaining axes). The approximation guarantee is then obtained through a con- struction from [25], which is based on truncated singular value decompositions of every [AA; K.] for (K,, KC E C..
4 Low Entanglement Under Canonical Partitions Is Necessary and Sufficient for Accurate Prediction
In this section we consider the locally connected tensor network from Section 3.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 features (Section 4.1). Applying the theorems of Section 3.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 4.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 4.3). For conciseness, the treatment in this section is limited to one-dimensional (sequential) models and data; see Appendix J.2 for an extension to arbitrary dimensions.
'If A = O, then c = 0. In this case, the expression e/I is by convention equal to zero.
"hen the approximation error tends zero, the sufficient condition in Theorem 2 requires entanglements to approach zero, unlike the necessary condition in Theorem which requires entanglements to become no greater than In. This is unavoidable. However, if for all canonical partitions (IC, KC)) E Cx the singular values of [[A; A] trailing after the R'th one are small, then we can also guarantee an assignment for the locally connected tensor network satisfying J WWrx All < e, while (AAA;K) K)) can be on the order of In( R)) for all (IC, Cv. See Appendix C for details.
5

---

4.1 Accurate Prediction Is Equivalent to Fitting Data Tensor
As discussed in Section 3.1, the locally connected tensor network generating WTN E P xhxxx.DD D is equivalent to locally connected neural network, whose forward pass over data instance (x("). x) yields ( WIN), where x()) E
x.. x(N) E PN, Motivated by this fact, consider binary classification setting, in which the label y of the instance (x(1),...,xxN))) x(N) is either or 11 and the prediction ý is taken to be the sign of the output of the neural network, i.e. 1 = sign (een(((gs (0 x WrN)).
3.....
Suppose we are given training set of labeled instances ((. (M),)) ) } m=1 drawn i.id. 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:
M min I| M m=1
max 0, (rn) ( (1.m) WIT))..
(1)
for a predetermined constant > O. We assume instances are normalized, i.e. the distribution is such that all vectors constituting instance have norm no greater than one. We also assume that B S 1. In this case [y(mm) ( 1 x(n,,), WIN) I 1, so our optimization problem can be expressed as wixllw 1- (Demp: WTN), where
(
D Demp"
M m== (m)
N x==1 (7.
(2)
M
referred to as the empirical data tensor. This means that the accuracy over the training data is determined by how large the inner product (Demp. Wrx) is.
Disregarding the degenerate case of D Demp = 0 (in which the optimized objective is constant), the inner products (Demp, WrN) and (Demp/ /lemm/l/Deepllll WTN) differ by only multiplicative (positive) WTN).
constant, so fitting the training data amounts to optimizing maX/WW If WTN can represent some W, then it can also represent e W for every c R. Thus, we may equivalently optimize maXwex (Demp/ (DDmmplll ll. Wrx/ /|//N//II II) and multiply the result by B. Fitting the training data therefore boils down to minimizing
||. accuracy achievable over the training data is determined by the extent to which
Wrs
D Damp
In other words, the
[[as
Wirs fit the [[ewll
normalized empirical data tensor
Demp
[[Pamp
The arguments above are independent of the training set size M, and in fact apply to the population loss as well, in which case Domp is replaced by the population data tensor:
D Dpop- == Bxx()) E(xx,....x(())..)))
N x
(3)
Disregarding the degenerate case of Poop 0 (i.e. that in which the population loss is constant), it follows that the achievable accuracy over the population is determined by the extent which Wrx can fit the normalized population data tensor suboptimality in achievable accuracy.
[[Tx
We refer to the minimal distance from the ||Ppool|'
Definition 3. In the context of the classification setting above, the suboptimality in achievable accuracy is SubOpt == minwex
Wis.
Ppep
PPpopll
4.2 Necessary and Sufficient Condition for Accurate Prediction
In the classification setting of Section 4.1, by invoking Theorems 1 and from Section 3.2, we conclude that the suboptimality in achievable accuracy is small if and only if the population data tensor D Ppop admits low entanglement under the canonical partitions of its axes (Definition 2). This is formalized in Corollary below. The quantum entanglement of Dpop with respect to an arbitrary measure of dependence between the data features indexed by K. and those indexed by KC - see Appendix D for intuition behind this. Thus, Corollary 1 implies that the suboptimality in achievable accuracy is small if and only if the data admits low dependence under the canonical partitions of features. Since canonical partitions comprise a subset with contiguous indices, obtain formalization of the intuition by which data distributions suitable for locally connected neural networks are those exhibiting a "local nature."
partition of its axes (K,, KC9), where K. C [N],
Directly evaluating the conditions required by Corollary 1 - low entanglement under canonical partitions for D Dpop is impractical, since: (i) Dpop is defined via an unknown data distribution

---

(Equation (3)); 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 in Appendix E shows, Ppop is with high probability well-approximated by the empirical data tensor Damp. Moreover, the entanglement of Demp under any partition can be computed efficiently, without explicitly storing or manipulating an exponentially large matrix - see Appendix F for an algorithm (originally proposed in [40]). Overall, obtain an efficiently computable criterion (low entanglement under canonical partitions for Demp), that with high probability is both necessary and sufficient for low suboptimality in achievable accuracy (see Corollary 2 in Appendix E for a formalization).
Corollary 1. Consider the classification setting of Section 4.1, and let E [0, 1/4/. If there exists canonical partition (K, K.) CN (Definition 2) under which QE(Ppopi K) In(R) + 2E In(Dx) + 2/2r, where R is the width of the locally connected tensor network and Dr := min [ITEx Dn. Se.IInes Inggs Dn), then SubOpt > e. Conversely, if for all (K,KC) E CN it holds that QE IC) S 8N-12
RR. then SubOpt c.
Proof sketch (proof in Appendix M.4). The result follows from Theorems and after accounting for the normalization of WTx in the definition of SubOpt (Definition 3).
4.3 Empirical Demonstration
Corollary establishes that, with high probability, the locally connected tensor network (from Sec- tion 3.1) can achieve high prediction accuracy if and only if the empirical data tensor (Equation (2)) 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 [46] to different datasets. we show that the achieved test accuracy is inversely correlated with the entanglements of the empirical data tensor un- der 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 J.2.3.
Discernngg the relation between entanglements of the empirical data tensor and performance (pre- diction accuracy) of locally connected neural networks requires datasets admitting different entan- glements. A potential way to acquire such datasets is as follows. First, select dataset on 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. 6 This erodes the original arrangement of features in the data, and is expected to yield higher entanglement under canonical partitions.
We followed the blueprint above for a binary classification version of the Speech Commands audio dataset [64]. Figure presents test accuracies achieved by 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.
5 Enhancing Suitability of Data to Locally Connected Neural Networks
Our analysis (Sections 3 and 4) suggests that 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 data distribution to locally connected neural networks (Section 5.1 and Appendix G). Empirical evaluations demonstrate that it significantly improves prediction accuracies of common locally connected neural networks on various datasets (Section 5.2). For conciseness, the treatment in this section is limited to one-dimensional (sequential) models and data; see Appendix J.3 for an extension to arbitrary dimensions.
'It is known that as the number of random position swaps goes to infinity, the arrangement of the features converges to random permutation [18].
7

---

Ckh
Enlanglereen Under
Canonitaa Farticall Partitions
1.0-
Test Accuracy (%)
54
Loca Allent on
0.8.
70-
80
50
500
10000 1500
2000
25000
3000 3500 4000
500
1000 1500 2000 2500
3000
3500 4000
Number of Fealure Swaps in Data
Number of Feature Swaps in Data
Figure 3: 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 4.1 and 4.2). Left:: Average entanglement under canonical partitions (Definition of the empirical data tensor (Equation (2)), for binary classification variants of the Speech Commands audio dataset [64] 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 local self-attenticn attenttnn model [46], 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 J.2.3 for experiments over ((wo-dimensional) image data and Appendix I. for implementation details.
5.1 Search for Feature Arrangement With Low Entanglement Under Canonical Partitions
Our analysis naturally leads recipe for enhancing the suitability of a data distribution 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 A E N training instances { ((x(1.m)) ,...,, M)), ((N.)) y(m))) } M where ymm) E {1. and
x(),))) E Rd for E [N], E [M]. with e N. Assume without loss of generality that N is power of two (if this is not the case we may add constant features as needed). The aforementioned recipe boils down to search for permutation æ [N] - [N], which when applied to feature indices leads the empirical data tensor Demmp (Equation (2)) 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 K1,1 c [AV] and K1,2 == [N] \ K1,1 such that the entanglement of Demp with respect to (K1,1, K2.2) is minimal. That is, find K1,1 E ( QE K.). The permutation will map Ki,1 coordinates (1...., , 7) and K1,, to 1 + 1,,..; NJ. Then, partition 11,1 into two equally sized sets K2,1 K1 and K2,2 == K1,1 (22,1 such that the average of entan- glements induced by these sets is minimal, i.e. K2,1 E ,,
1 (E(Deepppp)) KC) QF(Demp: K1,1 \ [C)]- The permutation æ will map 12,11 to coordinates (1...., , N and K2,2 to 1 +1... N. A partition of K1,22 into two equally sized sets 122,3 and K2,1 is obtained similarly, where ı will map K2.3 to coordinates { ( + 1, 1,..., 3N ) and K2,4 to { 3N + 1,...,, N.. Continuing in the same fashion, until we reach subsets KL, KL. consisting of a single feature index each, fully specifies the permutation
Unfortunately, the step lying at the heart of the above scheme - finding balanced partition that minimizes average entanglement - is computationally prohibitive, and we are not aware of any tools that alleviate the computational difficulty. However, as discussed in Appendix G. if one replaces entanglement with an appropriate surrogate measure, then each search for balanced partition minimizing average entanglement converts into a minimum balanced cut problem, which enjoys wide array of established approximation tools [29]. We thus obtain practical algorithm for enhancing the suitability of a data distribution to locally connected neural networks.
5.2 Experiments
We empirically evaluate our feature rearrangement method, detailed in Appendix G, using common locally connected neural networks convolutional neural network, S4 (popular recurrent neural network; see [26]), and a local self-attention model [46] over randomly permuted audio datasets (Section 5.2.1) and several tabular datasets (Section 5.2.2). For brevity, we defer some experiments and implementation details to Appendices K and L. Additional experiments with two-dimensional
data are given in Appendix J.3.3.
5.2.1 Randomly Permuted Audio Datasets
Section 4.3 demonstrated that audio data admits low entanglement under canonical partitions of features, and that randomly permuting the position of features Ieads this entanglement to increase,
8

---

Table I: Arranging features of randomly permuted audio data via our method (detailed in Appendix G) significantly improves the prediction accuracies of locally connected neural networks. Reported are test accuracies (mean and standard deviation over random sceds) a convolutional neural network (CNN), S4 (a popular recurrent neural network; see [26]), and a local self-attention model [46], over Speech Commands dataset [64] subject to different arrangements of features: (i) random arrangement; (ti) an arrangement provided by applying our method to the random arrangement; and (iii) an arrangement provided by applying an adaptation of IGTD [67] arrangement. For each model, we highlight (in boldface) the highest mean accuracy if the difference between that and the second-highen mean accuracy is statistically sigmificant (namely, larger than the standard deviation corresponding the former). Our method leads to significant improvements in prediction accuracies, surpassing the improvements brought forth by IGTD, See Appendix K for experiments demonstrating its scalability and implementation details.
heuristic scheme designed for convolutional neural networks - to the random
Randomly Permuted
Our Method
IGTD
CNN
5.5 + 0.5
18 1.6
5.7 = 0.6
9.4 + 0.8
30.1 + 1.8
12.8 1.3
Local-Attention
7.8 - 0.5
12.9 + 0.6
7 0.6
while substantially degrading the prediction accuracy of locally connected neural networks. A sensible test for our method to evaluate its ability to recover performance lost due to the random permutation of features.
For the Speech Commands dataset [64], Table compares prediction accuracies of locally connected neural networks on the data: (i) subject to random permutation of features; (ii) attained after rearranging the randomly permuted features via our method; and (iii) attained after rearranging the randomly permuted features via IGTD [67] - heuristic scheme designed for convolutional neural networks (see Appendix A). As can be seen, our method leads to significant improvements, surpassing those brought forth by IGTD. Note that the performance lost due the random permutation of features is not entirely recovered.? ? We believe this relates to phenomena outside the scope of the theory underlying our method (Sections 3 and 4), for example translation invariance in data being beneficial in terms of generalization. Investigation of such phenomena and suitable modification of our method are regarded as promising directions for future work.
The number of features in the audio dataset used in the experiment above is 2048. We demonstrate the scalability of Algorithm 2 by including in Appendix an experiment over audio data with 50,000 features. In this experiment, instances of the minimum balanced cut problem encountered in Algorithm 2 entail graphs with up to 25- 10 edges. They are solved using the well-known edge sparsification algorithm of [57] that preserves weights of cuts, allowing for configurable compute and memory consumption (the more resources are consumed, the more accurate the solution will be).
5.2.2 Tabular Datasets
The prediction accuracies of locally connected neural networks on tabular data, i.e. on data in which features arranged arbitrarily, is known to be subpar [56]. Tables 2 and 5 report results of experiments with locally connected neural networks over standard tabular benchmarks (namely "semeion", "isolet" and "dna" [60]), demonstrating that arranging features via our method leads to significant improvements in prediction accuracies, surpassing improvements brought forth by IGTD (a heuristic scheme designed for convolutional neural networks [67]). Note that our method does not lead to state of the art prediction accuracies on the evaluated benchmarks." 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.
Conclusion
6.1 Summary
The question of what makes a data distribution suitable for deep learning is a fundamental open problem. Focusing on locally connected neural networks 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 oolf-attention models
address this problem by
Accuracies on the original data are 59.8, 69.6 and 48.1 for CNN, S4 and Local-Attention respectively. EoBooott e.g. achieves prediction accuracies 91, 95.2 and 96 over semeion, isolet and dua, respectively.

---

Table Arranging features tabular datasets via our method (detailed in Appendix G) significantly improves the prediction accuracies of locally connected neural networks. Reported are results of experiments analogous to those of Table I, but with the "semeion"" and "isolet" tabular classification datasets [60]. Since to the arrangement of features in a tabular dataset is intended to be arbitrary, we regard as bascline 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- second-highest mean accuracy is statistically significant (namely, is larger than the standard deviation corresponding the former). As in the experiment Table I, rearranging the features according to our method leads to significant improvements in prediction accuracies, surpassing the improvements brought forth by IGTD. See Appendix K for experiments with an additional tabular datasct ("dna") and implementation details.
Dataset: semeion
Dataset: isolet
Baseline
Our Method
IGTD
Baseline
Our Method
IGTD
CNN
77.7 + 1.4
80.0 + 1.8
78.9 + 1.9
91.0 1 0.6
92.5 + 0.4
92.0 1:
S4 Local-Attention
82.5 + 1.1
89.7 0.5
86.0 0.7
92.3 + 0.4
93.4 + 0.3
92.7 = 0.5
60.9 + 4.9
78.0 1.7
67.8
2.6
82.0 + 1.6
89.0 + 0.6
85.7 +: 1.9
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 may be enhanced by arranging features such that low entanglement under canonical partitions is attained. Employing 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.
data distribution to locally connected neural networks
6.2 Limitations and Future Work
Neural network architecture We theoretically analyzed a locally connected neural network with polynomial non- oon-linearity, by employing its equivalence to tensor network (cf. Section 3.1). Ac- counting for neural networks with connectivities beyond those considered (e.g. connectivities that are non-local or ones involving skip connections) is an interesting topic for future work. It requires modification of the equivalent tensor network and corresponding modification of the definition of canonical partitions, similarly to the analysis in Appendix J. Another valuable direction is to ac- count for neural networks with other non-linearities, e.g. ReLU, We believe this may be achieved through a generalized notion of tensor networks, successfully used in past work to analyze such architectures [9].
The analysis in Section 4 assumes a binary soft-margin SVM objective. Extend- ing it to other objective functions, e.g. multi-class SVM, may shed light on the relation between the objective and the requirements for a data distribution to be suitable to neural networks.
Objective function
Textual data Our experiments (in Section 4.3 and Appendix J.2.3) show that the necessary and sufficient condition we derived for a data distribution to be suitable locally connected neural network namely, low quantum entanglement under canonical partitions of features - is upheld by audio and image datasets. This falls in line with the excellent performance of locally connected neural networks over these data modalities. In contrast, high performant architectures for textual data typically non-local [61]. Investigating the quantum entanglements that textual data admits and, in particular, under which partitions they are low, may allow designing more efficient architectures with connectivity tailored to textual data.
6.3 Outlook
The data modalities which deep learning 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 branch of science concerned with formally reasoning
data. Concepts and tools from physics 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.
10

---

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), the Tel Aviv University Center for Al and Data Science. the Adelis Research Fund for Artificial Intelligence, Len Blavatnik and the Blavatmik Family Foundation, and Amnon and Anat Shashua. NR is supported by the Apple Scholars in AI/MI PhD fellowship.
References
[1] Emmanuel Abbe and Colin Sandon. Provable limitations of deep learning, arXiv preprint I 1812.06369. 2018.
[2] Yotam Alexander, Nimrod De La Vega, Noam Razin, and Nadav Cohen. What makes data suitable for locally connected neural network? necessary and sufficient condition based quantum entanglement. arXiv preprint arXiv:2303. 1149, 2023.
[3] Emilio Rafael Balda, Arash Behboodi, and Rudolf Mathar. A tensor analysis dense connectivity via convolutional arithmetic circuits. Preprint, 2018.
[4] Rajendra Bhatia. Matrix analysis. Springer- Verlag, 1997.
Springer-Verlag,
[5] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International Conference Machine Learning (ICML), pages 605-614, 2017.
[6] Alon Brutzkus, Amir Globerson, Fran Malach, Alon Regev Netser, and Shai Chalev-Schwards Efficient learning of CNNs using patch based features. In Kamalika Chaudhuri, Stefanie Jegelka. Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2336-2360 2356, PMLR, 17-23 Jul 2022. URL https: / http//poooeeen...e.e// alr.press. wr16//buutuuu22e html.
[7] Song Cheng, Jing Chen, and Wang. Information perspective to probabilistic modeling: Boltzmann machines versus born machines. Entropy, 20(8):583, 2018.
[8] Nadav Cohen and Amnon Shashua. Simnets: A generalization of convolutional networks. Advances in Neural Information Processing Systems (NeurlPS), Deep Learning Workshop, 2014.
[9] Nadav Cohen and Amnon Shashua. Convolutional rectifier networks as generalized tensor decompositions. International Conference on Machine Learning (ICML), 2016.
[10] Nadav Cohen Amnon Shashua. Inductive bias deep convolutional networks through pooling geometry. International Conference on Learning Representations (ICLR), 2017.
[11] Nadav Cohen, Or Sharir, and Amnon Shashua. Deep simnets. IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2016.
[12] Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor analysis. Conference On Learning Theory (COLT), 2016.
[13] Naday Cohen, Or Sharir, Yoav Levine, Ronen Tamari, David Yakira, and Amnon Shashua. Analysis and design of convolutional networks via hierarchical tensor decompositions. Intel Collaborative Research Institute for Computational Intelligence (ICRI-CT CI) Special Issue on Deep Learning Theory, 2017.
[14] Naday Cohen, Ronen Tamari, and Amnon Shashua. Boosting dilated convolutional networks with mixed tensor decompositions. International Conference on Learning Representations (ICLR). 2018.
[15] Ian Convy, William Huggins, Haoran Liao, and K Birgitta Whaley. Mutual information scaling for tensor network machine learning. Machine learning: science and technology. 3(1):015017, 2022.
[16] Shawn X Cui, Michael Freedman, Or Sattath, Richard Stong, and Greg Minton. Quantum max-flow/min- cut. Journal of Mathematical Physics, (766)20, 2016.
[17] Wei Dai, Chia Dai, Shuhui Qu, Juncheng Li, and Samarjit Das. Very deep convolutional neural networks for raw waveforms. In 2017 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 421-425. IEEE, 2017.
[18] Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Zeitschrifi für Wahrschheinicchkeiisheeeee und verwandte Gebiete, 57(2) 179, 1981.
11

---

[19] Simon S Du and Surbhi Goel. Improved learning of one-hiddennlayer convolutional neural networks with overlaps. arXiv preprint arXiv: 180500780 2018.
[20] Simon S Du, Jason D Lee, Yuandong Tian, Aarti Singh, and Barnahas Poczos. Gradient descent learns one-hidden-layer cmn: Don't be afraid of spurious local minima. In International Conference on Machine Learning (ICML). pages 1339-1348, 2018.
[21] Anatoly Dymarsky and Kirill Pavlenko. Tensor network to learn the wave function of data. Physical Review Research, 4(4):043111, 2022.
[22] Timo Felser, Marco Trenti, Lorenzo Sestini, Alessio Gianelle, Davide Zuliani, Donatella Lucchesi, and Simone Montangero. Quantum-inspired machine learning on high-energy physics data. npj Quantum Information, 7(1):1-8, 2021.
[23] Michael Garey and David Johnson. Computers and intractability. A Guide to the Theory of NP- Completeness, 1979.
[24] Rong Ge, Yunwei Ren, Xiang Wang. and Mo Zhou. Understanding deflation process in over- weerparametrried tensor decomposition. In Advances Neural Information Processing Systems (NeurlPS), S). 2021.
[25] Lars Grasedyck. Hierarchical singular value decomposition of tensors. SIAM journal matrix analysis and applications, 31(4):2029-205 2054, 2010.
[26] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. International Conference on Learning Representations (ICLR), 2022.
[27] Siu-Was Ho and Raymond W Yeung. The interplay between entropy and variational distance. IEEE Transactions on Information Theory, 56(12):596-5992, 2010.
[28] Zhih-Aha Jia, Lu Wei, Yu-Chun Wu. Guang- Guo, and Guo-Ping Guo. Entanglement area law for shallow and deep quantum neural network states. New Journal of Physics, 22(5):053022, 2020.
[29] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing. 20(1):359-39) 1998.
[30] Valentin Khrulkov, Alexander Novikov, and Ivan Oseledets. Expressive power of recurrent neural networks. International Conference Learning Representations (ICLR), 2018.
[31] Valentin Khrulkov, Oleksii Hrinchuk, and Ivan Oscledets. Generalized tensor models for recurrent neural networks. International Conference on Learning Representations (ICLR), 2019.
[32] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 142.69880 2014.
[33] Alex Krizhevsky, Learning multiple layers features from tiny images. Technical report, 2009.
[34] Yoav Levine, Or Sharir, and Amnon Shashua. Benefits of depth for long-term memory of recurrent networks. International Conference on Learning Representations (ICLR) Workshop, 2018.
[35] Yoav Levine, David Yakira, Nadav Cohen, and Amnon Shashua. Deep learning and quantum entanglement: Fundamental connections with implications to network design. International Conference on Learning Representations (ICLR), 2018
[36] Yoav Levine, Or Sharir, Nadav Cohen, and Amnon Shashua. Quantum entanglement in deep learning architectures. To appear in Physical Review Letters, 2019.
[37] Jingling Li, Yanchao Sun, Jiahao Su, Taiji Suzuki, and Furong Huang. Understanding generalization in deep learning via tensor methods. In International Conference on Artificial Intelligence and Statistics, pages 504-515. PMLR, 2020.
[38] Sirui Lu, Márton Kanász-Nage Ivan Kukuljan, and Ignacio Cirac. Tensor networks and efficient descriptions of classical data. arXiv preprint 1x3iv:200330687. 2021.
[39] Eran Malach and Shai Shalev-Shwartz, provably correct algorithm for deep learning that actually works. arXiv preprint arXiv:1803 00011000320222 2018
[40] John Martyn, Guifre Vidal, Chase Roberts, and Stefan Leichenauer. Entanglement and tensor networks for supervised image classification. arXiv preprint arXiv:2007.06s 06082, 2020.
[41] Kento Nozawa and Issei Sato, Empirical evaluation and theoretical analysis for representation learning: A survey, arXiv preprint arXiv:2204.0822 2022.
12

---

[42] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of physics, 349:117-1588 2014.
[43] Samet Oymak and Mahdi Soltanolkotahi, End-to-end learning of a convolutional neural network via deep tensor decomposition. arXiv preprint arXiv:1805.06522: 2018.
[44] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vito,,, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS-W, 2017.
[45] Giovanni Puccetti. Measuring linear correlation between random vectors. Available SSRN 31 16066, 2022.
[46] Jack Rae and Ali Razavi. Do transformers need deep rongerange memory? In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, Online, July 2020. Association for Computational Linguistics. URL pesttp::/wwwrr aclweb. org/ anthooogygoo/20....... acl-main. 672.
[47] Noam Razin and Nadav Cohen. Implicit regularization in deep lcarning may not be explainable by norms. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[48] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. International Conference on Machine Learning (ICML), 2021.
[49] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks. International Conference on Machine Learning (ICML), 2022.
[50] Noam Razin, Tom Verbin, and Nadav Cohen. On the ability of graph neural networks to model interactions between vertices. arXiv preprint arXiv:2211.16494 2022.
[51] Lorenzo Rosasco, Mikhail Belkin, and Emesto De Vito. On learning with integral operators. J. Mach. Learn. Res., 11:905-934, mar 2010. ISSN 1532-4435.
[52] Siddhartha Sen. Average entropy of a quantum subsystem. Physical review letters, 77(1):1 1996.
[53] Shai Shalev-Shwaree Ohad Shamir, and Shaked Shammah. Failures of gradient- based deep learning. In International Conference on Machine Learning, pages 3067-3075. PMLR, 2017.
[54] Or Sharir and Amnon Shashua. On the expressive power of overlapping architectures of deep learning. International Conference on Learning Representations (ICLR), 2018
[55] Or Sharir, Ronen Tamari, Nadav Cohen, and Amnon Shashua. Tensorial mixture models. arXiv preprint arXiv:1610.04167, 2016.
[56] Ravid Shwartz-ZZi Zii and Amitai Armon. Tabular data: Deep learning is not all you need. Information Fusion, 81:84-90, 2022.
[57] Daniel A Spielman and Shang- Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing. 40(4):981-1025, 2011.
[58] E Miles Stoudenmire. Learning relevant features of data with multi-scale tensor networks. Quantum Science and Technology. 3(3)0034033, 2018
[59] Edwin Stoudenmire and David J Schwab. Supervised learning with tensor networks. In Advances in Neural Information Procexsing Systems (NeurIPS), 2016.
[60] Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo. Openml: networked science in machine learning. SIGKDD Explorations, 15(2):99-60, 2013. doi: 10.1145/2641190.0 198. URL. http:/ //tp://doiii/o/ acm. orgo 10. 1111/114///191111 264119.
[61] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[62] Qingcan Wang et al. Exponential convergence of the deep neural network approximation for analytic functions. arXiv preprini arXiv: 2018
[63] Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond lazy training for over- parameterized tensor decomposition. Advances in Neural Information Processing Systems, 33:21934- 21944, 2020.
13

---

[64] Pete Warden. Speech commands: A dataset for limited-vocabulaty speech recognition. arXiv preprint arXiv: arXiv: 1804.0329, 2018.
[65] Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Newral Networks, 94:103-114, 2017.
[66] Ya-Hui Zhang. Entanglement entropy of target functions for image classification and convolutional neural network. arXiv preprint arXiv:1710.05520 2017.
[67] Yitan Zhu, Thomas Brettin, Fangfang Xia, Alexander Partin, Maulik Shukla, Hyunscung Yoo, Yvonne Evrard, James H Doroshow, and Rick L Stevens. Converting tabular data into images for deep learning with convolutional neural networks, Scientifie reports, 11(1):1-11, 2021.
14

---

A Related Work
Characterizing formal properties of data distributions that make them suitable for deep learning is major open problem in the field. A number of papers provide sufficient conditions on a data distribution which imply that it learnable by certain neural networks [5, 65, 39, 19, 20, 43, 62, 6]. However, these sufficient conditions are restrictive, and are not argued to be necessary for any aspect of learning (i.e. for expressiveness, optimization or generalization). To the best of our knowledge, this paper is the first to derive a verifiable condition on a data distribution that is both necessary and sufficient for aspects of learning to be achievable by a neural network. We note that the condition derive resembles past attempts to quantify the structure of data via quantum entanglement and mutual information [40, 15, 38, 7, 66, 28, 21]. However, such quantifications have not been formally related to learnability by neural networks.
The current paper follows a long line of research employing tensor networks as theoretical models for studying deep learning. This line includes works analyzing the expressiveness of different neural network architectures [12, 55, 9, 10, 54, 14, 34, 3, 35, 30, 36, 31, 50], their generalization [37], and the implicit regularization induced by their optimization [47, 48, 49, 63, 24]. Similarly to prior works we focus on expressiveness, yet our approach differs in that we incorporate the data distribution into the 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 form of representation learning. Representation learning is a vast field, far too broad to survey here (for an overview see [41]). Our algorithm, which learns a representation via rearrangement of features in the data, is complementary in the literature. A notable method that is also based on feature rearrangement is IGTD [67] - a heuristic scheme designed for convolutional neural networks. In contrast to IGTD, our algorithm is theoretically grounded. Moreover, we demonstrate empirically in Section 5 that leads to higher prediction accuracies.
most representation learning methods
B Illustration of Canonical Partitions
1=0 0
E
1=1
1=2
1=L
Figure 4: The canonical partitions of [. for N = 2 with L E N. Every I E (0. ( L) contributes 2' canonical partitions, the n one induced by K. = (21-1- (n 1) + 1,..., 24-1 n).
C Impossibility Result for Improving the Sufficient Condition in Theorem 2
The sufficient condition in Theorem 2 (from Section 3.2) for approximating A E IR Dr requires entanglements to approach zero as the desired approximation error e does, in contrast to the necessary condition in Theorem 1 where they approach In R). As Proposition 1 shows, this is unavoidable in the absence of further knowledge regarding A. However, for all canonical partitions (K,,CC) E C2 the singular values of [A; XC] trailing after the R''h one are small, then we can also guarantee an assignment for the locally connected tensor network satisfying |[WTN - All < e, while QE(A;K) can be on the order of In( Rt) for all (K,, KC) E Cn. Indeed, this follows directly from a result in [25], which we restate Lemma 7 for convenience.
Proposition 1. Let f R R2o be monotonically increasing in its second variable. Suppose that the following statement holds: if a tensor A Pr satisfies QE(A:K) < f[[AA], e) for all canonical partitions (X., K9) E Cn (Definition 2). then there exists an assignment for the tensors constituting the locally connected tensor network (defined in Section 3.1) for which Win
15

---

R x Ds upholds:
[WINN All c.
Then, for any A E RDixx=XN,, as the desired approximation error goes to zero, so does the sufficient condition on entanglements, i.e.:
lim c) 0.
Proof. Suppose otherwise, i.e. that there exists some infe>o c)) = > 0. Let AA be a tensor with ||||| = a such that QE(A:K) < c for all canonical partitions (K, K.9) E Cv. Then by assumption, for all > 0 there exist tensor generated by the locally connected tensor network, which we denote by WTN(E) e PP x..xx that satisfies:
0 such that lim f(a =
[[WIN(() - All E
By Lemma 5, for all 0 we have that
rank([W>x(():K]) S R.
so by the lower semicontinuity of the matrix rank, we have that (ank([A;;]]]] < as well. But, there are tensors for which this leads to contradiction, namely tensors with arbitrary low entanglement across all partitions but nearly maximal rank. Indeed, consider tensors of the form
2 (n) + B | (m) + 8 55]
( = a
E ERDIX-XDN,
where (v(M) DR. J ) (non-zero) vectors, 5 > 0 and B RD is tensor with matricizations of maximal rank across all canonical partitions (for proof of the existence of such a tensor see Claim 3 in [35]). Note that [[)]]|| for all 8 > 0. By the triangle inequality have
266) a
3 @
8 8-1|B]
(m)
(m)
18
N
v
(())
+ + BBI
+8 B
==
and so
Q(6)
N v(()
lim
= 0.
8-0
a
18 n== vin)]]
Thus, from Lemma 9 we know that
2
lim QE
K
QE
1 v(n) k
0
6
for all K?) Cy- Furthermore, for any KK)) E CN: N v(m))] | 1C = 0,
v(a) 1
QE
and therefore by Theorem for sufficiently small we have
QE(Q()):K)) < for all (K,, K E CN. However, rank([Q(5); AC]) is (nearly) maximal for all canonical partitions. Indeed, by the triangle inequality for matrix rank we get
rank( KJ) rank (IB; rank ([ v(n); Dx 1,
where Dx: min mln Dm, InEKee D.).
D Quantum Entanglement as Measure of Dependence Between Features
In this appendix, we provide intuition behind the following statement made in Section 4.2: the quantum entanglement of Dpop with respect to an arbitrary partition of its axes (K., K9), where K. C [N], is a measure of dependence between the data features indexed by K. and those indexed by KC. Consider the case where the features indexed by are statistically independent of those indexed by KC,, and all features are statistically independent of the label Then Q E popi (hopp)) K.) = O (see Lemma 1 below for proof of this fact). If the features are not statistically independent of y, but when conditioned on y the features indexed by K. are statistically independent of those indexed by XCe, then QD(D pop' XC) < ln(2) (this fact is also established by Lemma below). In general, the higher (D K.) is, the farther the distribution is from the aforementioned situations of independence, implying stronger dependence between the features indexed by I. and those indexed by X.
16

---

Lemma 1. Consider the classification setting of Section 4.1, and let K. S [N]. If the features
indexed by K. are independent of those indexed by K (i.e. (x(")) JEE are independent of (x(") mexe)) conditioned on the label y, then QD pops K.) I In(2). Furthermore, if the features are also independent of y. then (D popi K.)
O.
Proof. For brevity, denote X (x(2) ), Xx (x(1)) and Xx: == (x necK. By the law of total expectation, the entry of pop corresponding to an index tuple (iI,..., iN) E [Di] x [Dn] satisfies:
(m)
(D (Dpop)in.....n Ex.9
x
in
= P 1) Ex
= P(y 11
Ex
n=1
Thus, the features indexed by 1C are independent of those indexed by IC given y, it holds that:
(D (Dpop)it.....kk = Pyy = Exx
II
x (2)
= Exx=
II
(m) y=1
nEK
-P -1 Exx
nEX Xin < -1 Exx II 1 --
(4)
This implies that can write [D [Ppopi IRllexx DaxIIneke D. the arrangement of Ppop as a matrix whose rows correspond to axes indexed by K. and columns correspond to the remaining axes - as a weighted sum two outer products. Specifically, define vx. ux E IllTex D., to be the vectors holding for each possible indexing tuple (in)ex: the values Exg [[nxx < 1y= and x ( ly = -1], respectively (with the arrangement of entries in the vectors being consis- Exg [
tent with the rows of [Ppop; K.l).. Furthermore, let VKs, Ux= IR D. be defined analogously by replacing IC with KC (with the arrangement of entries in the vectors being consistent with the columns of [Ppopi K... Then. by Equation (4):
[Dpopi K] Ppy 1) Vx & VK= P(y = -1) uk ug
Since each outer product forms rank one matrix, the subaddititivty of rank implies that the rank of pooop XC] is at most two. As a result, [Dpop: KC] has at most two non non-zero singular values and
@E(Dpopi pop: IC) < (2) (the entropy of a distribution is at most the natural logarithm of the size of its support).
If, addition, all features the data are independent of the label y. then vx: ux: and VK- uycs meaning [Ppop: KC] = (P(y- 1) P 1)) Vx @ Vxc. In this case, the rank of [ [Ppopp K. is most one, QD (Ppopi XC)
E Efficiently Computable Criterion for Low Suboptimality in Achievable Accuracy
In this appendix, provide the formal claims deferred from Section 4.2. Specifically, Proposition shows that D p D is, with high probability, well-approximated by the normalized empirical data tensor D D empp ||- Corollary 2 establishes the efficiently computable criterion (low entangle- ment under canonical partitions for Demp), that with high probability is both necessary and sufficient for low suboptimality in achievable accuracy.
Proposition 2. Consider the classification setting of Section 4.1, and let â E (0, 1) and 7 > 0. If the 2lm(?)
training set size M satisfies M Z ||P P.2,
then with probability at least 1 - 5:
D pop [ippopll
Demp
S
liDempll
Proof sketch (proof in Appendix M.5). A standard generalization of the Hoeffding inequality to ran- dom vectors in a Hilbert space yields a high probability bound on |jDemp D Dpopll, which is then translated to a bound on the normalized tensors.
D
17

---

Algorithm Entanglement Computation for the Empirical Data Tensor
1: Input: := { [(x(1.m). ..... x(N.))) ] -
M E N data instances comprising N E features
each, K. C [N] subset of feature indices
2: Output: QE
3: Compute G G( E BRNxM given element-wise by:
1. = y0y (Onexx(mi)) SnEXx((1)) = y00 IINE (xelmed) (elmi)))e(ms))) xe(mo)) Vi,j E [M] (
Wi, E [M] (( (8nek) (n1)) BneK (n.)) = IINEXO (xelm))) xlmnnly
4: Compute eigenvalue decompositions ( and G( ie:
( g()g (U(K))
G (K*) (1*) g(()) (K9) (U(K")
where U(K), U(K) E MxM are orthogonal matrices and ((x)) ) E RXM are diagonal holding the eigenvalues G(K) and ((*),, respectively
5: Compute Q = (S())) (UOO)) U (S())) E RRM
6: Compute a singular value decomposition of Q obtain its singular values oj (Q)......
7: Let Pm = o (Q)/ Em p (Q) for E [M]
8: return @E KC) DM Pm In(pm)
(if Q 0, then return 0)
Corollary 2. Consider the setting and notation of Corollary 1, with E (0, 1/.) For 5 E (0, 1),
Sln( ()
suppose that the training set size M satisfies M z TP + Then, with probability at least 1 -
the following hold. First, if there exists a canonical partition (9) E CN (Definition 2) under which (D(Dompi K.) > In(B) 3 ln(Dx) + 22/3,, then:
SubOpt > c.
Second, for all (K) E CN it holds that QE((empi K.) S 32N-48 In(R), then:
2
SubOpt S..
Moreover, the conditions above on the entanglements of Demp can be evaluated efficiently (in + MIDNM++ND)
time O(DNM M2) and memory, where D == max D.).
Proof sketch (proof in Appendix M.6). Implied by Corollary 1, Proposition with y = 5 and Algo- rithm 1 in Appendix F.
2
F Efficiently Computing Entanglements of the Empirical Data Tensor
For a given tensor, its entanglement with respect to partition of axes (Definition 1) determined by the singular values of its arrangement
matrix according to the partition. Since the empirical data tensor Demp (Equation (2)) has size exponential the number of features N, it infeasible naively compute its entanglement (or even explicitly store it in memory). Fortunately, as shown in [40], the specific form of the empirical data tensor admits an efficient algorithm for computing entanglements, without explicitly manipulating an exponentially large matrix. Specifically, the algorithm runs in O O(DNM) M² + M3 time and requires O(DNM the maximal feature dimension (i.e. axis length of Demp). N is the number of features in the data (i.e. number of axes that D Demp has), and M is the number of training instances. For completeness, we outline the method in Algorithm while referring the interested reader to Appendix [40] for further details.
M2) memory, where D maxpe[N] D,, is
18

---

G Practical Algorithm via Surrogate for Entanglement
To efficiently implement the scheme from Section 5.1, we replace entanglement with surrogate measure of dependence. The surrogate is based on the Pearson correlation coefficient for multivariate features [45], and its agreement with entanglement is demonstrated empirically in Appendix I. Theoretically supporting this agreement is left for future work.
Definition 4. Given a set of M E N instances X' := {(x(1.m)) x (N,)) E (R W M by Pr,x' the multivariate Pearson correlation between features n' E [N]. For K m= denote surrogate entanglement of X' with respect to the partition (X,, IC9), denoted (X;;; K.), is the sum of absolute values of Pearson correlation coefficients between pairs of features, the first belonging to IC and the second KC == [N] \ K. That is, (E(: == _nEK,n'Ex |Pa,x'--
S [N], the
As shown by Proposition below, replacing entanglement with surrogate entanglement in the scheme from Section 5.1 converts each search for balanced partition minimizing average entanglement into 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 data distribution to locally connected neural networks - see Algorithm 2.
Proposition 3. For any R S [N] of even size, the following optimization problem can be framed as a minimum balanced cut problem over a complete graph with [K]
vertices:
min 1 (SE(XX + -E(X;K)K)) |CR,/
(5)
Specifically, there exists complete undirected weighted graph with vertices K. and edge weights w K. x K. + R such that for any K. C. K., the weight of the cut in the graph induced by E w((n, tion (5), iee. to (EE + (E(X:K))))
w n'n,,')) n')) is equal, up to additive constant, to the term minimized in Equa-
Proof. Consider the complete undirected graph whose vertices are K and where the weight of an edge (n,n') E K x IC is w((n, n²t)) })) Pr,,' (recall that Pr, stands for the multivariate Pearson correlation between features and n' in 2². For any IC C. K. it holds that:
EneKweRRe "'(n, n') (F(() SS((X 1 (F(;
where (2(; does not depend on K.. This concludes the proof.
H Definition of the Multivariate Pearson Correlation from [45]
Appendix G introduces a surrogate measure for entanglement based on the multivariate Pearson correlation from [45]. For completeness. this appendix provides its formal definition.
Given set of M N instances X' {(x(().m))........ ((.,))..x((())) (No))
M let E()) be the empirical covariance matrix of feature n E [N] and E(nx") be the empirical cross-covariance matrix of features n. n' E [N), Le::
(RP)N)M
{(a)
M m-1 (xe(x.m)) (m)))) @ (m)m))
1
E M
I(ann) 1
m- ( (1.)) (n) @ (x('' - (1)(
M
(n.m) for E [N]. With this notation, the multivariate Pearson correlation of n, n' E [N] from [45] is defined by Pu.n' SracceE(n.n (rr))((E())("))
where (m)) : 37 MM
For completeness, Appendix H provides formal definition of the multivariate Pearson correlation.
19

---

Algorithm 2 Enhancing Suitability of Data to Locally Connected Neural Networks
1: Input: x= {(x((1.)))... (_.,m,,)___)))))) m=
M E N data instances comprising N E features
2: Output: Permutation æ [N] - [M] to apply to feature indices
3: Let Ko,1 := [M] and denote == (NV
4: # We assume for simplicity that N is power of two, otherwise one may add constant features
5: for 0 ..... L 1, . 2
do
6: Using reduction to a minimum balanced cut problem (Proposition 3); find an approximate solution K1+1,2n-1 C Ki,n for:
+
\
7: Let K1+1,2n = K1,n KK44122011
8: end for
9: # At this point, KL.1,..... KL,N each contain single feature index
10: return n that maps E KL, to n, for every n E [N]
I Entanglement and Surrogate Entanglement Are Strongly Correlated
In Appendix G, we introduced surrogate entanglement measure (Definition 4) to facilitate efficient implementation of the feature arrangement search scheme from Section 5.1. Figure supports the viability of the chosen surrogate, demonstrating empirically that it is strongly correlated with entanglement of the empirical data tensor (Definition and Equation (2)).
7.0e+04
Entanglement Under
Cananical Partitions
1.0
Entanglerment
Surtagate Ertanglement
6.8e+04
Surrggate Entanglement
Under Canonical Partitioss
6.50+04
6.20+04
6.0e+04
0.6
5.8e+04
5.5e+00
5.2e+04
500
1000
1500
2000
2500
3000
3500
4000
Number Feature Data
Figure 5: Surrogate entanglement (Definition 4) is strongly correlated with the entanglement (Detinition 1) of the empirical data tensor. Presented are average entanglement and average surrogate entanglement under canonical partitions, admitted by the Speech Commands audio datasets [64] considered Figure 3. Remarkably, the Pcarson correlation between the quantities is 0.974. For further details see caption of Figure 3 as well Appendix L.
J Extension to Arbitrary Dimensional Models and Data
In this appendix, extend our theoretical analysis and experiments, including the algorithm for enhancing the suitability of data to locally connected neural networks, from one-dimensional (se- quential) models and data to P-dimensional models and data (such as two-dimensional image data three-dimensional video data), for P e N. Specifically, Appendix J.1 extends Section 3, Appendix J.2 extends Section 4 and Appendix J.3 extends Section 5.
To ease presentation, consider P P-dimensional data instances whose feature vectors associated with coordinates (ni...., np) E [N]]", where N = 2 for some L E (if this is not the case we may add constant features as needed).
20

---

WIN
two dimensional coordinates
axes indices of Win
[8]
[8]
[64]
2
3
4
7
8
19
20
23
24
4
(a)
Dytus
Datu Dyta Par
4
11
12
15
16
27
28
31
32
Mm x"
Wix)
33
54
WIN
6
35
36
39
40
51
52
55
56
Ari fra no km
8
43
44
47
48
59
60
63
64
(b)
(d)
Figure 6: The analyzed tensor network equivalent locally connected neural network operating over P- dimensional data, for P = 2. (a) The tensor network adheres to a perfect 2 -ary tree connectivity with N leaf nodes, where N = 2" for some L N, and generates Wfx I xxxxxppp Axes corresponding open edges indexed such that open edges descendant to any node of the have contiguous indices. The lengths axes corresponding to inner (non-open, edges are equal to R e referred to as the width of the tensor network. (b) Exemplar [N] + [N*) compatible with the locally connected tensor network (Definition 5), mapping P-dimensional coordinates to axes indices of W (c) Contracting Wix with vectors
(x(m1....mp) "nioo.pp according to compatible μ produces (0 xx (n), Wfk). Performing these contractions be viewed forward pass of certain locally connected neural network (with polynomial non-lincarity) over the data instance {x (") ("sppppp]
[pE[., (see, e,g., [12, 10, 35, 49)).
J.1 Low Entanglement Under Canonical Partitions Necessary and Sufficient for Fitting Tensor
We introduce the locally connected tensor network equivalent locally connected neural network that operates over P-dimensional data (Appendix J.1.1). Subsequently, we establish a necessary and sufficient condition required for it to fit given tensor (Appendix J.1.2), generalizing the results of Section 3.2.
J.1.1 Tensor Network Equivalent to a Locally Connected Neural Network
For P-dimensional data, the locally connected tensor network we consider (defined in Section 3.1 for one-dimensional data) has underlying perfect 2--ary graph of height L.. We denote the tensor it generates by WiN E D x--xxxpx Figure 6(a) provides its diagrammatic definition. As in the one-dimensional casc, the lengths of axes corresponding inner edges taken to be R N, referred to as the width the tensor network.
The axes Wi are associated with P-dimensional coordinates through a bijective function μ [N] + [.
Definition 5. say that a bijective function μ [N] - [NP] is compatible with the locally
connected tensor network if, for any node in the tensor network, the coordinates mapped to indices of WPy axes descendant to that node form a contiguous P- P-dimensional cubic block [N] (e.g.. square block when P = 2) see Figure 6(b) for an illustration. With slight abuse of notation, for K. C [
we denote ((KC) [p(m....... np):
) (m.,..., nP) K. C [NP).
Contracting the locally connected tensor network with (x....... IR Pprer according to compatible μ., depicted in Figure 6(c), can be viewed as a forward pass of the data instance (x(m)....)))) ).....)))....................... JPENN through locally connected neural network (with polynomial non-linearity), which produces the scalar n= xx (n), WPx) (see, e.g., [12, 10, 35, 49]).
R [[N]
21

---

Canonical Partitions of [M]]
K K
==
1=L
Figure 7: The canonical partitions of [N] for P = 2 and = 2" with L E N. Every E (0..... ... L} contributes 2 canonical partitions, cach induced by xp=1 (26-1 (n, 1) ,,..., 26-1 mpp for ..,,..., np [2'].
J.1.2 Necessary and Sufficient Condition for Fitting Tensor
The ability of the locally connected tensor network, defined in Appendix J.1.1, fit (i.e. represent) tensor is determined by the entanglements that the tensor admits under partitions of its axes, induced by the following canonical partitions of [NV]*.
Definition 6. The canonical partitions of [N]P, illustrated in Figure for P 2, are:
(<,KKK :K= x {2 (n, 1) 11+1... 1,...,,. npp
2
LE {0. [o......). L).
E [27]]
n1
With the definition of canonical partitions for P-dimensional data in place, Theorem 3 generalizes The- orem particular, suppose that WPf the tensor generated by the locally connected tensor network apel--aproo A IR D
Then, given compatible μ : [N] [N (Definition 5), Theorem 3 establishes that the entanglement of A with respect to (M((C), ((K)s) where KC)) E C cannot be much larger than In(R), whereas the expected entanglement attained by random tensor with respect (u(K), ((C)s) is on the order of min [AC (which is linear in P for some canonical partitions).
(#(K),,(XC))
In the other direction, Theorem implies that low entanglement under partitions of axes induced by canonical partitions of [N] is not only necessary for tensor to be by the locally connected tensor network, but also sufficient.
Theorem 3. Let WiP R xxp be a tensor generated by the locally connected tensor network defined in Appendix J.1.1, and p: [N] + [NP] be compatible map from P-dimensional coordinates to axes indices of WP (Definition 5). For any A R D. x..x xxx and [0, [|4, if [[WP All S then for all canonical partitions (X., KC) E Ch (Definition 6):
2c
2c
QE(A:)(()) S In(R) + |A|
(n(D)x))+22
+2 ||A||
(6)
FoFor sets St...., Sp, denote their Cartesian product by Sp=
22

---

where DucKy= == min ke Dn. Insatt Dut. In contrast. random A' E D.DxxmxDye drawn according to the uniform distribution over the set of unit norm tensors, satisfies for all canonical partitions (K, K2) Cj:
1
E(QE(A) 2 min[]/], [K9]] In(minee Dn) +
(7)
Proof sketch (proof in Appendix M.7). The proof is analogous to that of Theorem 1.
Theorem 4. Let A E DR x.. Np and > O. Suppose that for all canonical partitions (K, K.) E
CN (Definition 6) it holds that (B(A;((K)) (2NF A]] -IIn R),, where p [N]] - [NP] ] is
compatible with the locally connected tensor network (Definition 5). Then, there exists an assignment for the tensors constituting the locally connected tensor network (defined in Appendix J.1.1) such that generates Win DDD1 X.. yP satisfying:
I - A E.
Proof sketch (proof in Appendix M.8). The claim follows through reduction from the locally con- nected tensor network for P-dimensional data to that for mie-dimensional data (defined in Section 3. D). Lee. from perfect -ary to perfect binary tree tensor networks. Specifically, we consider modified locally connected tensor network for one-dimensional data, where axes corresponding to different inner edges can vary in length (as opposed to all having length R). We then show, by arguments anal- ogous to those in the proof of Theorem that it can approximate A while having certain inner axes, R. The proof concludes by establishing
related to the canonical partitions of [N] of lengths at most that, any tensor represented by such locally connected tensor network for one-dimensional data can be represented via the locally connected tensor network for P-dimensional data (where the length of each axis corresponding an inner edge is R).
J.2 Low Entanglement Under Canonical Partitions Necessary and Sufficient for Accurate Prediction
In this appendix, we consider the locally connected tensor network from Appendix J.1.1 in machine learning setting, and extend the results and experiments of Section 4 from one-dimensional to P-dimensional models and data.
J.2.1 Accurate Prediction Is Equivalent to Fitting Data Tensor
The locally connected tensor network generating WiN E XPDxx--DDpP is equivalent to a locally connected neural network operating over P-dimensional data (see Appendix J.1.1). Specifically, for- ward pass of the latter over {x (x...)). E ER (ppppeps...p)) ) ( yields (8 (n), W(-).
for a compatible μ [N]P - [N*] (Definition 5). Suppose we are given a training set of labeled instances { {(x((ms.....m).)))) Ai "R....PE((N) (mm)) (m)) m=1 drawn i.i.d. from some distribution, where ((()) E [1, }1} for E [M]. Learning the parameters of the neural network through the soft-margin support vector machine (SVM) objective amounts to optimizing:
min wills M m=1 max 0, 00, (-11-y(m) No x(" ((n),m) Win)
Σ
M
for predetermined constant B > O. This objective generalizes Equation (1) from one dineensnsio to P-dimensional model and data. Assume that instances are normalized, i.e. [x((#1....p)).m)) || < 1 for all Mi,...., np E [N], m E [M), and that B 1. By derivation analogous to that succeeding Equa- tion (1) in Section 4.1, if follows that minimizing the SVM objective is equivalent to minimizing wi
D.P
where:
DD
DPP
M ΣM
(m) y )
N ( (n).m)
(8)
extends the notion of empirical data tensor to P-dimensional data. In other words, the accuracy w.
achievable over the training data determined by the extent to which
can fit the normalized [[W]
D
empirical data tensor DF
23

---

The same arguments apply to the population loss, in which case Demp is replaced by the population data tensor:
D f pop :- (x (p)))) ppeee
S x (n)
(9)
W
The achievable accuracy over the population is therefore determined by the extent to which
[[
De.
can fit the normalized population data tensor from it the supobtimality in achievable accuracy, generalizing Definition 3 from Section 4.1.
Accordingly, we refer the minimal distance
Definition 7. In the context of the classification setting above, the suboptimality in achievable accuracy is:
W [WES
D
SubOpt" == mi W
D
pop
J.2.2 Necessary and Sufficient Condition for Accurate Prediction
In the classification setting of Appendix 1. by invoking Theorems and from Appendix J.1.2, we conclude that the suboptimality achievable accuracy small if and only the population (empirical) data tensor D (Demp)) admits low entanglement under the canonical partitions of features (Definition 6). Specifically, we establish Corollary 3, Proposition 4 and Corollary 4, which generalize Corollary 1, Proposition 2 and Corollary 2 from Section 4.2, respectively, P-dimensional model and data.
Corollary 3. Consider the classification setting of Appendix 1.2.1, and let 10,1/4). If there exists canonical partition (K, KCS) C2 (Definition 6) under which QE papi p(C)) In(R) + 2
(n(D) + 2e, where Du(K)= == min DR. InEm(Kyy- Dnh, then:
SubOpt?>> >6
2 Conversely, for all (K, Cl holds that QE ((pp)(((())) S 8NP-12 In(R), then:
SubOpt" <.
Proof. Implied by Theorems 3 and 4 after accounting for WiN being normalized in the suboptimality in achievable accuracy, as done in the proof of Corollary 1.
Proposition Consider the classification setting of Appendix 1.2.1, and let ô (0, 1) and y 0. the training set size M satisfies M 2
2lm(²)
then with probability at least 1 8:
IDP
D |D
D omp D
S
Proof. The claim established by following steps identical to those in the proof of Proposition
Corollary 4. Consider the setting and notation of Corollary 3. with (0. d). For 5 (0, 1), suppose that the training size M satisfies M 2 T Then, with probability at least -
sln(2)
5 the following hold. First, if there exists a canonical partition (K, E Cf (Definition 6) under which (D p(K)) > In(R) + 3e In(Duox)) + 22,3e, then:
SubOpt >c
2 Second, for all (K)) Cl it holds that QD ((K)) S 32N"-48 In then:
SubOpt Se.
Moreover, the conditions above the entanglements of D.P be evaluated efficiently (in O(DNPM2 N M²) time O(DNPM 22) and memory, where D = max Dn).
Proof. Implied from Corollary 3. Proposition 4 with = and Algorithm I in Appendix F by following steps identical to those in the proof of Corollary 2.
L

---

1.4.
CNN
Entanglement Under
Canonical Partitions
1.3
Test Accuracy (96)
Mobilellet
VGG
1.3
1.0-
75-
0.9
0.8
500
1000
2500
1000 1500
2000
2500
Number Feature Swaps
Number Feature Swaps Data
Figure 8: The prediction accuracies convolutional neural networks are inversely correlated with the entan- glements of image data under canonical partitions of features, in compliance with our theory (Appendices J.1 and J.2). This figure is identical to Figure 3, except that the measurements were carried over binary classifica- tion version of the CIFARIO image dataset, as opposed one- dimensional (sequential) audio dataset, using three different convolutional neural network architectures. For further details see caption of Figure well as Appendix L.
J.2.3 Empirical Demonstration
Figure 8 extends the experiments reported by Figure Section 4.3 from oie-dimensional (se- quential) audio data to awo-dimensional image data. Specifically, it demonstrates that the prediction accuracies of convolutional neural networks over variant of CIFARIO [33] is inversely correlated with the entanglements that the data admits under canonical partitions of features (Definition 6), i.e. with the entanglements of the empirical data tensor under partitions of its induced by canonical partitions.
J.3 Enhancing Suitability of Data to Locally Connected Neural Networks
We extend the preprocessing algorithm from Section 5, aimed to enhance the suitability of a data distribution locally connected neural networks, from mee-dmmnsionall P-dimensional models and data (Appendices 1.3.1 and J.3.2). Empirical evaluations demonstrate that it significantly improves prediction accuracy of common architectures (Appendix J.3.3).
J.3.1 Search for Feature Arrangement With Low Entanglement Under Canonical Partitions
Suppose we have M E N training instances { (xx(().....))))..))) [pE (mm) M
((m)....pp..m) E RP and y ((m) E {1, [1,-1} for Ri...., Rp E [N]. E [M], with m= where models intaking P-dimensional data, the recipe for enhancing the suitability of data distribution to locally connected neural networks from Section 5. boils down to finding a permutation π [N]
N. For
[N]P, which when applied feature coordinates leads the empirical data tensor Demp (Equation (8))
to admit low entanglement under canonical partitions (Definition 6).
greedy realization, analogous to that outlined in Section 5.1, is as follows. Initially, partition the features into 2 equally sized disjoint sets (K1,((a.....k)) C [N]P) ( Jk.....pe/ such that the average of D entanglements induced by these sets is minimal. That is, find an element of:
argmin (12 ..... C[N]")
2P Σ
1
QF(De omp p ((K))....p)))
Ape
s.t. Uk kp Ap N%, k.... Vki.... kp " E(2) |K I Ky.
where μ [N] [NP] is compatible map from coordinates in [N] P to axes indices (Definition 5). The permutation æ will map each (1,(k.....kp) to coordinates x x NN (kp 1) + 1...., No. kp). for ki,..., kp [2]. Then, partition similarly each of {Kr,(k)....pp)) le.....rel
into 2" equally sized disjoint sets. Continuing the same fashion, until we reach subsets (KC.,(k,..... kp) krE.N consisting of single feature coordinate each, fully specifies the permutation æ.
11 "'Ehanciig the suitability data distribution with instances of dimension different than P to P- dimensional models is possible by first arbitrarily mapping features to coordinates in [N] and then following the scheme for rearranging P-dimensional data.
25

---

Algorithm 3 Enhancing Suitability of P P-Dimensional Data to Locally Connected Neural Networks
1: Input: x= -==+(x(ee (1 I E m== M E N data instances comprising NP
features each
2: Output: Permutation т. [N]P [N] to apply to feature coordinates
3: Let (1........) [N] and denote := logg (N)
4: # We assume for simplicity that N is a power of two, otherwise one may add constant features
5: for -= 0..... L.......-- 1 hi,..., kp = .,... 2 do
6: Using reduction to minimum balanced 2 -cut problem (Proposition 5), find approximate solution 1K 2kp-sp) C
in)....... for:
min [Kag (k toote (pE11) My (hr kr I...... 1= k
2 Σ
SE ( KR;....). KpE
7: end for
8: At this point, (K kp) I kamnk each contain a single feature coordinate
9: return that maps (NI, np)) E (k..(k....kk)) to (ki...., kp), for every .i...., kp E [N]
As in the case of min-dimensional models and data (Section 5.1), the step lying at the heart of the above scheme finding balanced partition into 2" sets that minimizes average entanglement - is computationally prohibitive. In the next supappendix we will see that replacing entanglement with surrogate entanglement brings forth a practical implementation.
J.3.2 Practical Algorithm via Surrogate for Entanglement
To efficiently implement the scheme from Appendix 1, we replace entanglement with surrogate entanglement (Definition 4), which for P-dimensional data is straightforwardly defined as follows.
M ) Jni....pP[[N]] m=11 N instances == { (((().....)) (RP)
Definition 8. Given a set
denote by P(n ("...... the multivariate Pearson correlation between features (n1..... np) E [N] and (n/ (n.....,7p. n.p) E [N] For K. C [N] the surrogate entanglement of X' with respect the partition (K,, (,), denoted SE(X'; KC), is the sum Pearson correlation coefficients between pairs of features, the first belonging to and the second to IC = [N] K. That is:
SE(X;K)= = =x (6..
P(a (r)..,...
Analogously to the case of one-dimensional data (Appendix G), Proposition 5 shows that replacing the entanglement with surrogate entanglement in the scheme from Appendix J.3.1 converts each search for a balanced partition minimizing average entanglement into minimum balanced 2P -cur problem. Although the minimum balanced -ct problem is NP-hard (see, e.g., [23]), similarly to the minimum balanced (2-) cut problem, it enjoys a wide array of well-established approximation implementations, particularly ones designed for large scale [29, 57]. We therefore obtain practical algorithm for enhancing the suitability of data distribution with P-dimensional instances to locally connected neural networks see Algorithm 3.
Proposition 5. For any [ of size divisible by 2", the following optimization problem can be framed minimum balanced 2 -cut problem over a complete graph with [K] vertices:
min (Ka Ci
2F Σ K kpe
SE(X; 8 K K.......r))
(10)
st. Uk i Seta Kin Kk.....kp R.
Yki.....ppkkk Mi up E() (K Kuq....Kg.!
Specifically, there exists a complete undirected weighted graph with vertices and edge weights K x K + R such that, for any partition of K. into equally sized dis-
26

---

Table 3: Arranging features of randomly permuted image data via Algorithm significantly improves the prediction accuracies convolutional neural networks. Reported are the results experiments analogous to those Table I, carried out over the CIFARIO image dataset (as opposed to an audio dataset) using Algorithm For further details see caption of Table as well as Appendix L.
Randomly Permuted Algorithm
IGTD
CNN
35.1 +
38.2 0.4 36.2 + 0.7
Table 4: Our feature rearrangement method (Algorithm 2 in Appendix G) can be efficiently applied to data with large number of features. Reported the results of experiment identical to that of Table but over version of the Speech Commands [64] datasct which every instance has 50,000 features. Instances of the minimum balanced cut problem solved as part Algorithm entail graphs with up 25 10 edges. They are solved using the well-known edge sparsification algorithm of [57] that preserves weights of cuts, allowing for configurable compute and memory consumption (the more resources are consumed, the more accurate the solution will be). As can be seen, Algorithm 2 leads to significant improvements in prediction accuracies. See Appendix L for further implementation details.
Randomly Permuted
Our Method
CNN
15.0 + 1.6
65.6 + 1.1
S4
18.2 + 0.5
82.2 + 0.4
joint sets [Krr....kr Ma kpE the weight of the 2" -cut in the graph induced by them
w w((() .(pp)) equal, up multiplicative additive constants, to the term minimized Equation (5).
Proof. Consider the complete undirected graph whose vertices are K. and where the weight of an edge {(11..... n,), (n/....,, n/p)3 E K. K. is:
w(((n1..... ... np), (n (rq:...,, n(p))) (())....pp
(recall that P(ni (p) stands for the multivariate Pearson correlation between features (ng....,,), np) and (nf,....,ly n'p) in X). For any partition of K into equally sized disjoint sets (Kki....pp kp KpE()) it holds that:
2 Σ 2kmnnnppe (m)....p))KK,
Σ
[
n(r)))
ml)ck K Key.....
1 E K SF((; Kky SF(::R)
where (x) does not depend on (Kki by kp This concludes the proof.
J.3.3 Experiments
We supplement the experiments from Section 5.2 for one-dimensional models and data, by empiri- cally evaluating Algorithm 3 using two-dimensional convolutional neural networks over randomly permuted image data. Specifically, Table presents experiments analogous to those of Table from Section 5.2.1 over the CIFARIO [33] image dataset. For brevity, we defer some implementation details to Appendix I..
K Further Experiments
Table 4 supplements the experiment of Table from Section 5.2.1, demonstrating that Algorithm can be applied to data with a large number of features (e.g. with tens of thousands of features). In the experiment, instances of the minimum balanced cut problem solved part of Algorithm 2 entail graphs with up to 25 10 edges. They are solved using the well-known edge sparsification algorithm of [57] that preserves weights of cuts, allowing for configurable compute and memory consumption (the more resources are consumed, the more accurate the solution will bc). contrast, this approach is not directly applicable for improving the efficiency of IGTD.
27

---

Table Arranging features tabular datasets via our method (detailed in Appendix significantly improves the prediction accuracies of locally connected neural networks, Reported are results of experiments identical to those of Table 2, but over the "dna" tabular classification dataset [60]. For further details, see caption of Table and Appendix I..
Dataset: dna
Baseline
Our Method
IGTD
CNN
82.5 + 1.7
91.2 + 1.1
87.4 + 1.1
S4 Local-Attention
86.4 + 1.7
89.1 + 3.7
89.9 + 1.1
79.2 + 4.0
85.7 + 4.5
82.7 7 3.2
Table 5 supplements Table from Section 5.2.2 by reporting results of experiments with an additional tabular benchmark -a---ddan "dna".
L Further Implementation Details
We provide implementation details omitted from our experimental reports (Section 4.3, Section 5, Ap- pendix J.2.3, Appendix J.3.3 and Appendix K). Source code for reproducing our results and fig- ures, based on the PyTorch [44] framework, can be found at https: /htbbb..... com/ com/nmd99 ht////mm9///da _ suitable _______c_______________________e ___ aaccc_n_oooee code. All experiments were run single Nvidia RTX A6000 GPU.
L.1 Empirical Demonstration of Theoretical Analysis (Figures 3, 5, and
L.1.1 Figures and 5
Dataset: The SpeechCommands dataset [64] contains raw audio segments of length up 16000, split into 84843 train and 1 11055 test segments. We zero-padded all audio segments to have a length of 16000 and resampled them using sinc interpolation (default Py Torch implementation). We allocated 1 11005 audio segments from the train set for validation, i.e. the dataset was split into 73838 train, 11005 validation and 1005 test audio segments, and created binary one-vs-all classification version of SpeechCommande by taking all audio segments labeled by the class "33" (corresponding to the word "yes"), and sampling equal amount of segments from the remaining classes (this process was done separately for the train, validation and test sets). The resulting balanced classification dataset had 5610 train, 846 validation and 838 test segments. Lastly, we resampled all audio segments in the dataset from 16000 to 4096 features using sinc interpolation.
Random feature swaps: Starting with the original order of features, we created increasingly "shuf- fled" versions of the dataset by randomly swapping the position of features. For each number of random position swaps is E {0, 250, 4000), we created ten datasets, whose features were subject to k random position swaps between features, using different random seeds.
Quantum entanglement measurement:
Each reported value in the plot is the average of entangle-
ments with respect to canonical partitions (Definition corresponding levels 1, 2, 3, 4, 5, We used Algorithm I described in Appendix F on two mini-batches of size 500, randomly sampled from the train set. As customary (cf. [59]), every input feature x was embedded using the following sine-cosine scheme:
<<x) = (sin(T0x), cos(T(e)) R....
with 0.085.
Neural network architectures:
CNN: An adaptation of the M5 architecture from [17], which is designed for audio data. Our implementation is based on https://gittihe com hom/danielajissaeee htwii/aaaieaaaaaaaaaaaaaaaaoooee Imper_Imploee ementation.
S4: Official implementation of [26] with a hidden dimension of 128 and 4 layers.
Local-Attention: Adaptation of the local-attention model from [46), as implemented in https: //github. com/lucidrains/ /loaalslllllloooeo -otal-nttention. We a multi-layer perceptron (MLP) for mapping continuous (raw) inputs to embeddings, which are fed as input the the local-attention model. For classification, mcan-pooling and pass the result into an MLP classification head. The network had attention dimension 128 (with 2 heads of dimension 64), depth 8, hidden dimension of MLP blocks 341
collapse the spatial dimension of the network's 's output using
28

---

(computed automatically by the library based on the attention dimension) and local-attention window size 10.
The binary cross-entropy loss was minimized via the Adam optimizer [32] with default B coefficients. Batch sizes chosen to be the largest powers of two that fit in the GPU memory. The duration of optimization was 300 epochs for all models (number of epochs was taken large enough such that the train loss plateaued). After the last training epoch, the model which performed best on the validation set was chosen, and average test accuracy reported. Additional optimization hyperparameters are provided in Table 6. We note that for S4 [26]. in accordance with its official implementation, we use cosine annealing learning rate scheduler.
Training and evaluation:
Table 6: Optimization hyperparameters for the experiments of Figure 3.
Model
Optimizer
Learning Rate
Weight Decay
Batch Size
CNN
Adam
0.001
0.0001
128
S4
AdamW
0.001
0.01
64
Local-Attention
Adam
0.0005
0
32
L.1.2 Figure 8
Dataset: We created one-vs-all binary classification datasets based on CIFARIO [33] as follows. All images were converted to grayscale using the PyTorch default implementation. Then, we allocated 7469 images from the train set for validation, i.e. the dataset was split into 42531 train, 7469 validation and 1000 test images. We took all images labeled by the class "O" (corresponding to images of airplanes), and uniformly sampled an equal amount of images from the remaining classes (this process was done separately for the train, validation and test sets). The resulting balanced classification dataset had 8506 train, 1493 validation and 2001 test images.
Random feature swaps: We created increasingly "shuffled" versions of the dataset according to the protocal described in Appendix L.I.I.
Quantum entanglement measurement: Each reported value in the plot the average entanglements with respect to canonical partitions (Definition 6) corresponding to levels | = 1,
Neural network architectures:
Same architecture used for the experiments of Table 2 (see Appendix L.2.3), but with one-dimensional convolutional layers replaced with two-dimensional convolutional layers. See Table 7 for the exact architectural hyperparameters.
CNN:
VGG: Adaptation of the VGG16 architecture, as implemented in the PyTorch framework, for binary classification tasks on grayscale images. Specifically, the number of input channels is set to one and the number of output classes is set to two.
Adaptation of the MobileNet V2 architecture, as implemented in the PyTorch framework, for binary classification on grayscale images. Specifically, the number of input channels is set to one and the number of output classes is set to two.
MobileNet:
Table Architectural hyperparameters for the convolutional neural network (referred to as "CNN") used in the experiments of Figure and Table 3.
Hyperparameter
Value
Stride
(3, 3)
Kernel size
(3, 3)
Pooling window size
(3, 3)
Number of blocks 8
Hidden dimension
32
Training and evaluation: The binary cross-entropy loss minimized for 150 epochs via the Adam optimizer [32] with default 31, 32 coefficients (number of epochs was taken large enough such that the train loss platcaued). Batch size was chosen to be the largest power of two that fit in the
29

---

GPU memory. After the last training epoch, the model which performed best on the validation set was chosen, and its average test accuracy reported. Additional optimization hyperparameters are provided in Table 8.
Table 8: Optimization hyperparameters for the experiments of Figure 8.
Model
Optimizer
Learning Rate
Weight Decay
Batch Size
CNN VGG
Adam
0.001
0.0001
128
Adam
0.0001
0.0001
64
MobileNet
Adam
0.001
0.0001
64
L.2
Enhancing Suitability of Data to Locally Connected Neural Networks (Tables 2, 4,
and 5)
L.2.1
Feature Rearrangement Algorithms
Algorithm 2, 3 and IGTD [67] were applied to the training set. Subsequently, the learned feature rearrangement was used for both the validation and test data. In instances where three-way cross- validation was used, distinct rearrangements were learned for each separately.
Algorithm 2 and Algorithm 3: Approximate solutions to the minimum balanced cut problems were obtained using the METIS graph partitioning algorithm [29], as implemented in pettp:///ithuu wwwwwrkk.eeeteeeeeoeo...oeeooe.. metis.
IGTD [67]:
The original IGTD implementation supports rearranging data only into two-dimensional images. We adapted its implementation to support mne-dimensionll (sequential) data for the experi- ments of Tables and
L.2.2 Randomly Permuted Audio Datasets (Table 1)
Dataset: To facilitate efficient experimentation, we downsampled all audio segments in SpeechCom- mands to have 2048 features. Furthermore, for the train, validation and test sets separately, used 20% the audio segments available for each class.
Neural network architectures:
CNN: Same architecture used for the experiments Figure (see Appendix L.1.1).
S4: Same architecture used for the experiments of Figure 3 (see Appendix L.1.1).
Local-Attention: Same architecture used in the experiments of Figure 3, but with a depth 4 network (we reduced the depth to allow for more efficient experimentation).
The cross-entropy loss was minimized via the Adam optimizer [32] with default 31, 32 coefficients. Batch sizes were chosen to the largest powers two that fit in the GPU memory. The duration of optimization was 200, 200 and 450 epochs for the CNN, S4 and Local-Attention models, respectively (number of epochs was taken large enough such that the train loss platcaued). After the last training epoch, the model which performed best on the validation set was chosen, and its average test accuracy is reported. Additional optimization hyperparameters provided in Table 9. We note that for $4 [26), in accordance with its official implementation, we use cosine annealing learning rate scheduler.
Training and evaluation:
Table 9: Optimization hyperparameters for experiments of Table 1.
Model
Optimizer
Learning Rate
Weight Decay
Batch Size
CNN
Adam
0.001
0.0001 0.01
128
AdamW
0.001
64
Local-Attention
Adam
0.0001
32
L.2.3 Tabular Datasets (Tables and 5)
Datasets:
The datasets "dna", "semeion" and "isolet" are all from the OpenML repository [60]. For each dataset we split the samples intro three folds, which were used for evaluation according to
30

---

standard three-way way cross- cross-validation protocol. That is, for each of the three folds, we used one third of the data test and the remaining for train and validation. One third of the samples in the remaining folds (not used for testing) were allocated for the validation set.
Neural network architectures:
CNN: We used ResNet adapted for tabular data. It consisted of residual blocks of the following form:
Block (x) = dropout(x + (N(mappoo((eeeL]((m(()))))))
After applying predetermined amount of residual blocks, global average pooling and fully connected layers were used output the prediction. The architectural hyperparameters are specified in Table 10.
S4: Same architecture used for the experiments of Figure 3 (see Appendix L.1.1), but with hidden dimension of 64.
Local-Attention: Same architecture used for the experiments of Figure (see Appendix L.1.1), but with 4 attention heads of dimension 32 and a local-attention window size of 25.
Table 10: Architectural hyperparameters convolutional neural network used the experiments Tables and
Hyperparameter
Value
Stride
Kernel size
Pooling window size
Number of blocks
8
Hidden dimension
32
Training and evaluation: The cross-entropy loss was minimized for 300 epochs via the Adam optimizer [32] with default 31, B2 coefficients (number of epochs was taken large enough such that the train loss plateaued). Batch sizes were chosen to be the largest powers of two that fit in the GPU memory. After the last training epoch, the model which performed best according the validation sets was chosen, and test accuracy was measured on the test set. The reported accuracy is the average over the three folds. Additional optimization hyperparameters are specified in Table 11. We note that for S4 [26], in accordance with its official implementation, we use a cosine annealing learning rate scheduler.
Table 11: Optimization hyperparameters for the experiments of Table 2.
Model
Optimizer
Learning Rate
Weight Decay
Batch Size
CNN
Adam Adam W
0.001
0.0001 0.01
64
S4
0.001
64
Local-Attentin
Adam
0.00005
64
L.2.4 Randomly Permuted Image Datasets (Table
Dataset: The data acquisition process followed the protocol described in Appendix L.1.2, except that the data was not converted into a binary one-vs-all classification dataset.
Neural network architectures:
CNN: Same architecture used for the experiments Figure (see Appendix L.1.)).
Training and evaluation: The cross-entropy loss was minimized for 500 epochs via the Adam optimizer [32] with default (1, B2 coefficients (number of epochs was taken large enough such that the train loss plateaued). Batch size was chosen to be the largest power of two that fit in the GPU memory. After the last training epoch, the model which performed best the validation set was chosen, and its average test accuracy is reported. Additional optimization hyperparameters are provided in Table 12.
31

---

Table 12: Optimization hyperparameters for the experiments of Table 3.
Model
Optimizer
Learning Rate
Weight Decay
Batch Size
0.001 (multiplied by 0.1 after 300 epochs)
CNN
Adam
0.0001
128
L.2.5
Randomly Permuted Audio Datasets With a Large Number of Features (Table 4)
Dataset: The data acquisition process followed the protocol described in Appendix I.,1.1, except that the data was not transformed into binary one-vs-all classification dataset and the audio segments were upsampled from 16,000 to 50,000.
To facilitate running the METIS graph partitioning algorithm over the minimum balanced cut problems encountered as part of Algorithm we first removed edges from the graph us- ing the spectral sparsification algorithm of [57]. Specifically, we used the official Julia implementation (https: / titb com/
Edge Sparsification:
j1) with hyperparameter e 0.15.
Neural network architectures:
CNN: Same architecture used for the experiments of Table 2 (see Appendix L.2.3).
S4: Same architecture used for the experiments of Table (see Appendix L.1.I), but with hidden dimension of 32 (we reduced the hidden dimension due GPU memory considerations).
The cross-entropy loss was minimized for 200 epochs via the Adam optimizer [32] with default B1, B2 coefficients (number of epochs was taken large enough such that the train loss platcaued). Batch sizes were chosen to be the largest powers of two that in the GPU memory. After the last training epoch, the model which performed best the validation set was chosen, and its average test accuracy reported. Additional optimization hyperparameters are provided in Table 13. We note that for $4 [26], in accordance with its official implementation, we use a cosine annealing learning rate scheduler.
Training and evaluation:
Table 13: Optimization hyperparameters for the experiments of Table 4.
Model
Optimizer
Learning Rate
Weight Decay
Batch Size
CNN
Adam
0.001 0.001
0.0001
64
S4
AdamW
0.01
64
M
Deferred Proofs
M.1 Useful Lemmas
Below we collect a few useful results, which we will use in our proofs.
Lemma 2. We denote the vector of singular values of a matrix X (arranged in decreasing order) by
S(X). For any A,B DR it holds that:
[[S(A) - S(B) < S(A -B)II
Proof. See Theorem 11I.4.4 of [4].
Lemma 3. Let P = (p1, ................................ PN). Q (11: AN be two probability distributions supported on
[N), and denote by (VV Q) = Σ -ー Ppn qnl their total variation distance. ffr 10,)
it holds that TV(P, Q) S then:
[H(P) H (Q) < Ho(e) +e -n-In(N.
where H(P) := - Pr. In(p,)) is the entropy Pf and Hy(c) = -c In(c) - (1- - 1n((1 c) is the binary entropy of a Bernoulli distribution parameterized by E 10.
Proof. See, egg. Theorem 11 of [27].
32

---

Lemma 4 (Hoeffding inequality in Hilbert space), Let X1..., XN be an i.i.d. sequence of random variables whose range some separable Hilbert space H. Suppose that E [[Xx] 0 and |X,]] S e for all n E [ Then, for all & 2 0:
Nt 2r
Pr
Xa 21)
S 2 2exp
n=1
where |1-11 refers to the Hilbert space norm.
Proof. See Section 2.4 of [51].
Lemma 5 (adapted from [35]). Le (V, be the perfect binary tree graph, with vertices V and edges E, underlying the locally connected tensor network that generates Wrn E R Di x Dy (defined in Section 3. For K S [M], let Vv: V and Vg= C be the leaves G corresponding to axes indices K. and Ke WTT,, respectively. Lastly, given cul (A, B) V, i.e. A C V and B S V disjoint and AU B V, denote by C(A, == (fu, o) E u A. B) the edge-cut set. Then:
rank(PWix:AI]] s min cur (A,B) of V.CA. R C(A,
In particular, if K9) E Cn. then:
rank([WrN: KT) S R.
Proof. See Claim 1 in [35] for the upper bound the rank of [WTN; K] for any K. C [N]. If (IC, IC9) E Cn, since there exists a cut (A, B) of V such that Vg S A and Vi S whose edge-cut set is of a singleton,
get that rank rank([WrN: ([WIN; KT]) R.
Lemma 6 (adapted from [35]). Ler G (V, E) be the perfect 2n -ary tree graph, with vertices V and edges E, underlying the locally connected tensor network that generates W E RDi x--x Dx (defined in Appendix J.1.1). Furthermore, let [N] + [N'] be compatible map from P- dimensional coordinates to axes indices of WPN (Definition 5). For J S [NP), let VJ S V and VJ= S. V be the leaves in G corresponding to axes indices J and Je of W respectively. Lastly, given cut (A, B) V, ie. A C. V and B C V are disjoint and A U B = V, denote by C(A, B) = (Lu, v) E E. u E A, E B} the edge-cut set. Then:
rank( (Ww: JJ]) I min ar of a Vo [(A.B]]
In particular, if (K, E Ch then:
rank([WTNn S R.
Proof. See Claim in [35] for the upper bound on the rank of [Wix: J] for any J C [] (KC, Cb, since there exists a cut (A, B) of V such that ((()) S A and Vµ(Ky C B whose edge-cut set is of singleton, we get that rank( [M)fNin(K))) I R.
Lemma 7 (adapted from Theorem 3.18 in [25]). Let A RD.x...XDy and > 0. For each canonical partition (K,,K)) KC) CN, let σx,1 2 ...OKDDK be the singular values of [A; KT], where D= == miniIInex Dn. InEKS D,}. Let (nx))εeC E NC be an assignment of an integer to each K. C.C.N For any such assignment, consider the set of tensors with Hierarchical Tucker (HT) rank at most (nx)xEE) as follows:
HT ((mK))ECW) = (VERDIX--XD VK E CN rank(((;) S <nx}
Suppose that for all (K,,K%) E CN it holds that VID R.d S V2N-3 Then, there exists
W e HT ((nx)Rec)) satisfying:
[[ - SE
In particular, for all (K,,K)) Cx it holds that Ede K.
32N-3' then there exists
WIN E D generated by the locally connected tensor network (defined in Section 3.1) satisfying:
[TNN- All S.
33

---

Lemma 8 (adapted from Theorem 3.18 in [25]). Let (nx)xceN E N be an assignment of an integer to each E CN. For any such assignment, consider the set of tensors with Hierarchical Tucker (HT) rank al most (nK)xEeN as follows:
HT ((nx))eex) == (V RDIx=XDN, :CC CN, rankkn(([ S nk)
Consider a localty connected tensor network with varying widths (nx)) i.e. a tensor network conforming to perfect binary tree graph which the lengths of inner axes are as follows (in contrast to all being equal to R as in the locally connected tensor network defined in Section 3. l). An axis corresponding
edge that connects a node with descendant leaves indexed by K. to its parent is assigned the length n.g. Then, every A E HT ((nx))eCC)) can be represented by said locally connected tensor network with varying widths, meaning there exists an assignment to the tensors of the tensor network such that it generates A. In particular, if ff = for all E CN, then A can be generated by the locally connected tensor network with all inner axes being of length R.
Lemma 9. Let V, W D..xx--XX be lensors such that ||]|| || and IV WIl
Then, for any (K, K9) ) CN it holds that:
[QE(V; K)) QE(W;K)) & Ho(IV - WIl) + 11V - -|I- In(()),
where Hc(c) == (c In(c) + (1 (1-c) Im(1 c)) is the binary entropy of Bernoulli distribution parameterized by c E [0. 11. and Dx == min[Ilnek Dn, InEx. D.).
Proof. For any matrix M E DixD with == min D1, D2}, let S(M) = (o., be the vector consisting of its singular values. First note that
I - WIl = || - W; xDDI = |1 - [W].
So by Lemma 2
||[[V - S([; s /| WIl-
Let 01 2 ... 2 UD and wi 2 ... 2 WDE be the singular values of [V; XC] and [V; KT] respectively, We have by the Sauchy-Schwand inequality that
Dx
2
Dx
2
Dr
Dr
Σ
wa val lwa + val
S
Σ
(wa - va)²
Σ d=1
(wa + va)²
d=1
d=1
Now the first term is upper bounded by 1|V WIl and for the second we have
Dr
DR
Dx
De
Σ
ww + va)2 = Σ w
+
Σ
vt + 20awe 2
Σe
Tawa S 4,
d=1
d=1
where we use the fact that ||| = || = 1, and again Cuachy-Schward Overall we have:
Drc
Σ d=1
U < 2
Note that the left hand side of the inequality above equals twice the total variation distance between the distributions defined by &s De, and ( Therefore by Lemma we have:
[QE(;K)) -E((;))) H((wi)) - H((a))) < IIV - WIll In(Dx) + H&(IV - WIl)
Lemma 10. Let = (p(z))ee(s) where S E N, be probability distribution. and denote its entropy by HPP) == Ex-p [In (1 (1/((x))) [ Then, for any O < < 1, there exists a subset T C [S] such that
Prowp(TT) S and [T] S
Proof. By Markov's ' inequality we have for any a 1:
Praup (fzie- 2 p(x)))) Przup (fr:11) p(x)
H(P) a H(P1)) Sa.
Let T (x:e- H(P)
<p(z)} C [S.. Note that
T Σ
NET p(z) $ E Exers) p(z) =1
and [T] Se" H(P) and Prawp (T S required.
34

---

M.2 Proof of Theorem 1
If A 0 the theorem is trivial, since then QF(A:K) for all KC) Cn.
A + 0. We have:
WIN
A
||||
WTN - -11
|Al
||Al|
[|VTN]
1
||A||
111-1111 11MTNN + 11WTN All)
[|
(III-Il - 11VrN 1IWIN - AlI)
= |||
2e
||
Now, let A == [[T and WTN- Win be normalized versions of and Wrx. respectively, and let
[PPN
c=
2e Note that c [|
A|l
4
A
2' and therefore by Lemma 9 we have:
QE(A:K) QE = QE
( (Ax) QE (VTTNN)))
s. Sc. (n(x)) + Ho(c).
By Lemma 5 we have that
QE (Wix: < In(rank((WTxx:X])) s In(R)
and therefore
Q (E(AAK) I In(R) + cll((D)) + Hb(c).
Substituting c
2x and invoking the elementary inequality H₂(x) S 2/ we obtain [
2e
2e
QF(A:K) S In(R)
In(Dx) +2/ ||A||
[A|
as required.
As for the expected entanglements of random tensor, let A' E PP to the uniform distribution over the set unit norm tensors. According to [52], for any canonical partition (AC, (C9) Cx it holds that:
XD be drawn according
D
De-Di 1
DK - 2D
B[QE(A;])))
D K.
where D&= == max ne Dn, ITEE Dn) and recall that Dr == min [ThEx Dn. InEK- Dn). By the elementary inequality of >x 2k=g 1/k 2 In(p) - In(q) we therefore have that:
Dx -
E(QE(4)))) > In(Dx -2x) In(D' + +1)
2D'
D's
Dx -
=In(Dk) + In
D'x +
2D'
Since Dr < D'2 and Dx 2 1, holds that (Dx-1)/2D4 < 1/2 and In(D's + +)) 2 In(1/2).
Thus:
(1
E[QE(A 2 (n() + In
min([ICC, In(min Da) + In
2 2
2 2
35

---

M.3 Proof of Theorem 2
Consider, for each canonical partition (K,, E CN, the distribution
Pk
pk(()
||
iE(Pk]
where 0x,1 2 022 2 ... D..xx are the singular values of [AA: KC] (note that 11p ||l oks
Px: is indeed probability distribution). Denoting by (Pkk) Re-Pe [In (1/px the entropy of Pk, by assumption:
LAIL TAI
22 |A - 3) In(R).
Q S
2 for all (K, E CN. Thus, taking |LA||3(2N 3)
obtain by Lemma 10 that there exists
subset Tx S [Dx] such that
6²
PK(TTE I
(2N 3) |A|
and [Tcll Se H(Px) elu(R) = R. Note that
of Σ i=1 |||]
R
Px(Tk)
Since this holds for any subset of cardinality at most R. Taking complements obtain
Dx
of ||ll
S Px(TR),
R=
SO
Σ
Dx
of
i=R+1
(22 -3)
We can now invoke Lemma 7, which implies that there exists some WIN E R x generated by the locally connected tensor network satisfying:
[WTN All SE
M.4 Proof of Corollary 1
Notice that the entanglements of a tensor are invariant to multiplication by constant. In particular, QE IC) = (D D |l; XC) for any (K,, KC)) E Cy. Hence, if there exists a canonical partition (XC, 1C9) E CN under which Q QE(Dpopp K.) > In(R)) + 2e (nelnn(x) + 2v 2e, then Theorem implies that minwex Wrr Dpop/ || |Ill > c. Now, for any non-zero W E TR Dj x...N gener- ated by the locally connected tensor network, can also represent W/|[W]|| by multiplying any of the tensors constituting the tensor network by 1/[[W]| (contraction a multilinear operation). Thus:
WTn. [WTx ||
Dpop
Dpop
SubOpt := minwes
minwes
Win
>E,
['ppopl
|Poplll
which concludes the first part of the claim, i.e. the necessary condition for low suboptimality in achievable accuracy.
For the sufficient condition, if for all (K, E Cy it holds that QE((D PopppopiKe S 8N-12 In (R). then by Theorem 2 there exists an assignment for the locally connected tensor network such that [Wrx PPopp/12pppl e/2. From the triangle inequality obtain:
Win
Dpop
<
Win
Dpop
|WIN
Wrn [|rxll
S 5
MIN
Wrx [Wrx (11)
[Wrll
PPpop
36

---

Since [WIN - Doop/ pop |II| - c/2 holds that [|rvl] [WTN
& 1 + c/2. Combined with the fact that
Win
[WTN]]
1, we get that |WTN
WTx
S c/2. Plugging this into Equa-
[Wrl
[rxxll
tion (11) yields:
WTN
D Poo
Se.
||TTN|l
1
and so SubOpt == minwes
WYn
Doop
S E.
[WTN
Pp
M.5 Proof of Proposition
We have the identity
Dpop
D Demp
Doop D Dempl
D Dempl
Doop
12 popll
1 DDemmpl
=
pppp
Demmll
D pop
DD DDmmpl
|| -
Demp
Deepp + Demp
D Dempll
D Demp Ppopll
|Ppopl
[Pempll
By the triangle inequality the above is bounded by
| Pop Dempl
Poplll
[Dempll]
12 pppolll
12 |ppopll
For E [M]. let (mm) -y(mm) ((.))) - -ppap- These are i.i.d. random variables with
[[X(()] = and | || S for all m [M]. Note that
Σ MM
(mm)
l[Demp -poplll
M
so by Lemma with 2,t liDoopl1 2
assuming M
2lm(3) ||
we have with probability at
least 1 -
PPpopl
|||
Deemp
S
D Dempll <
2
and therefore
|ipop - Dempll
Ppopl
|I
[Dpop
D (Dpopl
M.6 Proof of Corollary 2
1l(( })
First, by Proposition 2, for M 2
we have that with probability at least
DDopp Pea
Dpop [Ppupll
Demp ['Dempll
(12)
2
Now, we establish the necessary condition on the entanglements of Demp. Assume that there exists canonical partition (K, K()) CN under which
QE K.) In(R) + 3e In(D)) + 2v
We may view Demp as the population data tensor for the uniform data distribution over the training M m Thus, Corollary implies that
instances { ((x(1. (M,,))), m(())
Wrn Demp Wrxll
minwex
1.5c.
[[Demp
Using the triangle inequality after adding and subtracting
Deop ||Ppooll
follows that
Wrx
Dpop
Dpop I|ppopll
Demp
minwex
> 1.5c.
[ [Dpop
[Dmmp
37

---

Hence, combined with Equation (12) this concludes the current part of the proof:
Wrn [Wrrl]
Pop
pop
Demp
6 = c.
SubOpt := minwes
> 1.5c
2 1.cc
poplll
[Dpopll
[Dempll
2
We turn our attention to the sufficient condition on the entanglements of Damp- Suppose that
QE I 32N-18 In(R) for all canonical partitions (K,, E Cn. Invoking Corollary while viewing Pemp as the population data tensor for the uniform data distribution over the training instances { ((x(().)) "( xM,,))), y(m))
M
get that
m=1"
WTN
D Domp
minWex
S 2
[eempll
Combined with Equation (12), and by the triangle inequality, conclude:
WIN
Dpop
SubOpt == minWrs
[TNl
WTN
Demp
D Ppop
Demp
<
minWrx
+
[Wrx
(Dempl
| popll
[Demp
S..
Lastly, the fact that the entanglements of D Demp can be evaluated efficiently is discussed in Appendix F.
M.7 Proof of Theorem 3
If A 0 the theorem is trivial, since then (F(AA(((C)) 0 for all (KC, Cf.- assume A of 0. We have:
WIP WAII II
1
|A|
WPP - A
[A|
|||
1
(1 |||||
S
|naffill + IIWifN - All
||||I
1
||||| (II--II - 1
+ +IW
-
Al))
2e
Now, let = A
[TA and W
Wf
be normalized versions of A and W respectively, and let
[ II
2c c= ||l Note that c <
2||
2. and therefore by Lemma 9 we have:
4
|Al
QE(A: QE(A) u(K)) | (B:((A(())) QE (EEVWiis
sc-In(Duux)) + Hb(c).
By Lemma we have that
QE WW (wfNx < In(rank( (MNiFi s IIn())
and therefore
QE( (A())(())) < In( + cIn(D Hb(().
Substituting c == || and invoking the elementary inequality Hτ(x) S 2// we obtain
2c
2c
QE(A:H(C)) S In(R) + [A
(n(D)o)) +2 ||A|
required.
38

---

As for Equation (7), let A'' E RD xPDxx.xX Dx xyx be drawn according to the uniform distribution over the set of unit norm tensors. According to [52], for any canonical partition K9) CN it holds that:
x
E[QE(A'; E Daccy Plece
DM(K-1
moxy+1 D
2D' M(K)
where we denote D (x)) = max Pa. InEx(K)) Dn) and recall that Du(K)
min (TTTTTe) Dns InEm(X]e Dn}. By the elementary inequality Σk-y 1/h 2 In(p) - In(1)
we therefore have that:
E[QE(A;s 2 In(D D(cKE) (n(D)<K) +1) D((K) -1
2D M(K)
D' D' (((K) +1
DUCKI= -1
=In(DD(k)) + In
2D ((X)
Since DI()) S D' ((K) and D((K) 2 1, we have that:
D PunK) -1
2 In 115 D' D'ccs+ +1
- In
2D ((K)
Thus:
1
[[QE(A'))(()) 2 (n(D) + In
2
1 2 2
1
min [K]] In(minnn Dn) + In
M.8 Proof of Theorem 4
Let CNP be the one-dimensional canonical partitions of [N (Definition 2). Note that (( {u(K)= K. E C C CNP. For an assignment (mx) E Nºv of integers to one-dimensional canonical partitions K. E Cyy,, we consider the set of tensors whose matricization with respect to each K. CNp has rank at most ny. This set also known in the literature as the set of tensors with Hierarchical Tucker (HT) rank at most (MK)xEENP (cf. [25]). Accordingly, we denote it by:
HT ((MK))CEC = (V R xPPxx-DAA VKC E rank([[;k]]]]]]]] S mx)
Now, define (NK)) E NN by:
R if (C) E C₁ DD
VK E CNP: nie
( $ c
where Dx == min min[IneR Dn, ImEXI Dn). We show that for any tensor A that satisfies for all K. E CP:
QE(A: S
(2NP- |A1 In (R)
there exists tensor V HT ((nk) such that ||A VI1 Consider, for each canonical partition (X,, 1C9) CP. the distribution
Pk
px(() = |A
iE[Dx]
where 0K, 2 0x,2 ... DK are the singular values of [A; [(C)] (note that 1 LAI!2 TAp 1 so Px is indeed probability distribution). Denoting by (P == Ei-Pe [In (1/px(i))
TAI Σの
the entropy of PK. by assumption:
QE(A))((O) = H((E)) < |A
3) In(R).
39

---

for all (K,, KC9) E CN. Thus, taking TA we get by Lemma 10 that there exists a subset
Tx I [Dx] such that
e Pk(TR) S (2N - -J A
and [Tk] S H(Pk)
= (nn(() Note that
o Px(Tk) Σ iml |||
Since this holds for any subset of cardinality at most R. Taking complements we obtain
Σ Dx
of
S Px(TR),
R+ aall
so
DE Σ Ri- R.
V(2NP- -3)
We can now invoke Lemma 7 (note that if 1 (x)) trivially fullfiled with respect to the partition (0) since nie = Dx), which implies that there exists some W HT ((xk))EEcy)) satisfying:
Clyy then the requirements of Lemma
II - All ce
as required.
The proof concludes by establishing that for any tensor W E HT ((nk) there exists assignment for the tensors constituting the P-dimensional locally connected tensor network (defined in Figure 6) such that it generates W.
To see why this is the case, note that by Lemma 8 any tensor W E HT ((nk) can be repre- sented by (one-dimensional) locally connected tensor network with varying widths (nx)xxec Le. a tensor network conforming to a perfect binary tree graph in which the lengths of inner axes are follows: axis corresponding to edge that connects node with descendant leaves indexed by K to its parent is assigned the length nic- We can obtain an equivalent representation of any such tensor P-dimensional locally connected tensor network (described in Appendix J.1.1) via the following procedure. For each node level E (0, P, ................................ (L- P) the tree (recall N 2 for L E N), contract it with its descendant nodes at levels +1+ 1,...... + , + (P - 1)). 12 This results in tensor network whose underlying graph is perfect 2 -ary tree and the remaining edges all correspond to inner axes of lengths equal to nip- = for CN i.e. in a representation of W as P-dimensional locally connected tensor network.
F2 concrete example, let N 2 1 and P = (i.e. L 2). In this case, the perfect binary tree underlying one-dimensional locally connected tensor network of varying widths height = and has N 16 leaves. It is converted into perfect 4-ary tree tensor network of height L 2 by contracting the root with its two children and the nodes at level two with their children.
40


Reviews:
[{"review_id": "1TIcY23oXA", "reviewer": "Reviewer_SJKu", "summary": "The fundamental question of what makes a data distribution suitable for deep learning is addressed in this study, focusing on locally connected neural networks. The study uses theoretical tools from quantum physics to tackle this problem. The main theoretical finding is that a specific type of locally connected neural network can accurately predict over a data distribution if, and only if, the data distribution shows low quantum entanglement under specific feature partitions. The study suggests that using quantum entanglement could inspire further use of physics tools to understand the relationship between deep learning and real-world data.", "questions": "- The whole study targtes at locally connected neural networks. What happens to a NN with high connectivity? Does entanglement help the learning task?\n- Entanglement entropy is a typical metric. But what does entanglement mean in the dataset? If it is used to quantify the temporal/spatial non-locality in the data, why not use other metrics such as autocorrelation or other metrics from information theory? Why choose entanglement specifically?\n- Why use a tensor network as the equivalent model instead of directly evaluating on locally connected neural networks?\n- Will the code be available to reproduce the findings?", "limitations": "Not found.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper technically sounds correct and claims well supported by theoretical analysis and experimental results.\n- Related works and background knowledge are covered and discussed.\n- Experiments are conducted extensively in different locally connected neural networks (CNN, RNN, local self-attention), and experimental results are thoroughly discussed.", "weaknesses": "- Need more discussion on the motivation of using quantum entanglement.\n- Need more discussion on the limitations of this study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, and specifically for noting the soundness of our theory and experiments, as well as our account for background and related work. We respond to your comments and questions below. If our response is satisfactory, we would greatly appreciate it if you would consider raising your score.\n\n> *Need more discussion on the motivation of using quantum entanglement.*\n\nThe motivation for using quantum entanglement is discussed in the introduction (Section 1). As stated there, quantum entanglement facilitates a widely accepted theory that allows for assessing the suitability of a distribution to a computational model, where distributions are described by tensors and the computational models are tensor networks. This, along with a known equivalence between tensor networks and certain deep neural networks, allows us to make progress on the question of what makes a (data) distribution suitable for deep learning.\n\nWe hope the above addresses your comment. If not, and the intent behind “motivation of using quantum entanglement” is for an intuition behind its connection to neural networks, then please see our response to the first point raised by Reviewer CJsr.\n\n> *Need more discussion on the limitations of this study.*\n\nLimitations are currently discussed throughout the paper (for example, the fact that, as you mention, our theory is restricted to a specific type of locally connected neural network, is explicitly conveyed in Section 3.1). Following your comment, we plan to use additional space in the camera-ready version for a concentrated account of limitations.\n\n> *The whole study targtes at locally connected neural networks. What happens to a NN with high connectivity? Does entanglement help the learning task?*\n\nOur study is indeed limited to locally connected neural networks, which, while prevalent in practice, do not account for all deep learning architectures being used. When adding connectivity to a locally connected neural network its representational capacity is generally enhanced, so the condition we derived (which is both necessary and sufficient before connectivity is added) remains sufficient. We do not expect it to remain necessary though. Investigation of necessary conditions for a data distribution to be suitable to a neural network with high connectivity is a promising direction for future research; we hope that our work will inspire such progress. We will mention the above in the camera-ready version of the paper; thank you!\n\n> *Entanglement entropy is a typical metric. But what does entanglement mean in the dataset? If it is used to quantify the temporal/spatial non-locality in the data, why not use other metrics such as autocorrelation or other metrics from information theory? Why choose entanglement specifically?*\n\nIn general, entanglement is a concept which, given a collection of elements $[N] := \\\\{ 1, 2, … , N \\\\}$ partitioned into two sets $\\\\mathcal{K}$ and $\\\\mathcal{J}:= [N] \\\\setminus K$, quantifies how dependent $\\\\mathcal{K}$ and $\\mathcal{J}$ are. When the elements $[N]$ are features of a dataset ordered by time/space, and the partition is such that $\\\\mathcal{K}$ is contiguous (this is the case for all canonical partitions), then the entanglement can indeed be viewed as quantifying the temporal/spatial non-locality in the data.\n\nThe reason we use entanglement and not other measures as you suggest is laid out in our response to your first comment. Namely, entanglement facilitates a widely accepted theory in quantum physics, which allows us to make progress on the question of what makes a data distribution suitable for deep learning.\n\n> *Why use a tensor network as the equivalent model instead of directly evaluating on locally connected neural networks?*\n\nAs discussed in the introduction (Section 1), tensor networks tie to a widely accepted theory from quantum physics, which we imported for addressing our question of study (what makes a data distribution suitable for deep learning). Although it is possible to present our analysis solely through the lens of locally connected neural networks, we chose to include the tensor network formalism since it reflects the connection to physics — a branch of science we believe will be key to formally reasoning about the relation between deep learning and real-world data.\n\nWe note that tensor networks were central to many past studies of expressiveness and generalization in deep learning. See lines 128-138 of the paper for further details.\n\n> *Will the code be available to reproduce the findings?*\n\nCode for reproducing our experiments is available in the supplementary material. A public repository holding this code will be referenced in the camera-ready version of the text.\n"}, {"review_id": "vbjpHzIuhU", "reviewer": "Reviewer_CJsr", "summary": "This paper investigates the representation power of locally connected neural networks, a prevalent family of deep learning architectures, using tools from quantum physics. In particular, following the established equivalence between locally connected neural network and locally connected tensor network, the authors showed that the necessary and sufficient condition of a locally connected neural network fitting an objective tensor is the entanglements of the tensor admits under canonical partitions being small enough. As an application, the authors discuss the condition of making accurate predictions using locally connected neural networks, accompanied by empirical demonstrations. Notably, the findings suggest that the representation power of locally connected neural networks can potentially be enhanced by reorganizing the features to achieve reduced entanglements under canonical partitions. ", "questions": "I don't have more questions other than the existing ones above.", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The authors successfully extend the connection between deep learning and quantum physics by revealing a compelling link between representation power and entanglement – two fundamental concepts in both domains. From my perspective, the results are not only theoretically elegant but also closely related to illustrations of practical situations. ", "weaknesses": "The paper's presentation could benefit from further improvement, especially in providing more qualitative discussions to enhance readers' intuition regarding the technical correspondence between representation power and entanglement. While the link between these two concepts is established, the paper lacks sufficient qualitative explanations to make the connection more accessible.\n\nFurthermore, the tensor network's width, denoted as $R$ in the paper, seems to be crucial in the derived bounds. However, the definition of this parameter remains somewhat unclear, so I'm not fully convinced on why it is usually small.\n\nFurthermore, the current results solely focus on the representation of tensors using locally connected neural networks. It would be good to include an explanation as to why other types of underlying functions for representation were not considered.\n\nIf these questions are addressed, I'm happy to further increase my evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and support! We greatly appreciate your willingness to further increase your evaluation if your questions are addressed. We treat them below.\n\n> *The paper's presentation could benefit from further improvement, especially in providing more qualitative discussions to enhance readers' intuition regarding the technical correspondence between representation power and entanglement. While the link between these two concepts is established, the paper lacks sufficient qualitative explanations to make the connection more accessible.*\n\nThank you for raising this point! In line with your suggestion, we plan to use additional space in the camera-ready version for qualitative discussions aimed to enhance readers’ intuition. Below is an initial discussion on the technical correspondence between representation power and entanglement.\n\nRoughly speaking, entanglement is a concept which, given a collection of elements $[N] := \\\\{ 1, 2, … , N \\\\}$ partitioned into two sets $\\\\mathcal{K}$ and $\\\\mathcal{J} := [N] \\\\setminus K$, quantifies how dependent $\\\\mathcal{K}$ and $\\\\mathcal{J}$ are. In quantum physics the elements in $[N]$ are particles, and the entanglement quantifies the dependence, i.e. the quantum interaction, between the particles in $\\\\mathcal{K}$ and those in $\\\\mathcal{J}$. In the context of neural networks, the elements in $[N]$ are input variables (e.g. pixels, text tokens or audio samples), and the entanglement quantifies the dependence that a neural network can represent between the variables in $\\\\mathcal{K}$ and those in $\\\\mathcal{J}$. \n\nTo gain some intuition on the latter (entanglement quantifying the dependence that a neural network can represent between the variables in $\\\\mathcal{K}$ and those in $\\\\mathcal{J}$), consider the case of entanglement being equal to zero. There, a function $f ( \\\\cdot )$ realized by the neural network must be separable with respect to $\\\\mathcal{K}$ and $\\\\mathcal{J}$, meaning it can be written as $f ( X ) = g ( X_\\\\mathcal{K} ) h ( X_\\\\mathcal{J} )$, i.e. as a product of two functions, one that intakes only variables in $\\\\mathcal{K}$, and another that intakes only variables in $\\\\mathcal{J}$. This means that there is no dependence between $\\\\mathcal{K}$ and $\\\\mathcal{J}$. Indeed, in a statistical setting, where $f ( \\\\cdot )$, $g ( \\\\cdot )$ and $h ( \\\\cdot )$ are probability density functions, this is the definition of $\\\\mathcal{K}$ and $\\\\mathcal{J}$ being statistically independent. Moving to the general case (where the entanglement is not necessarily zero), one may view the entanglement as the distance from the above-described independence, i.e. the distance $f ( \\\\cdot )$ can have from the closest function which is separable with respect to $\\\\mathcal{K}$ and $\\\\mathcal{J}$. The higher the entanglement, the more dependence can be represented, and vice versa.\n\n> *Furthermore, the tensor network's width, denoted as R  in the paper, seems to be crucial in the derived bounds. However, the definition of this parameter remains somewhat unclear, so I'm not fully convinced on why it is usually small.*\n\nThe width of the tensor network $R$ corresponds to the width of hidden layers in the equivalent neural network, thus in practice (i.e. in any situation where the neural network is to be implemented) $R$ must be of moderate size (typically no more than a few hundreds or thousands), and in particular $\\ln ( R )$ is much smaller than the number of input elements $N$. This is discussed in lines 124-127 of the paper. We will broaden that portion of the text to further clarify. Thank you for bringing this up!\n\n> *Furthermore, the current results solely focus on the representation of tensors using locally connected neural networks. It would be good to include an explanation as to why other types of underlying functions for representation were not considered.*\n\nIn Section 4.1 we show that, for the analyzed model (locally connected neural network) over a standard SVM objective, accurate prediction is equivalent to fitting (representing) a tensor. Extending this equivalence to other types of objectives, e.g. multi-class SVM, is viewed as an interesting direction for future work. We will mention this in the conclusion; thank you!\n\n*P.S.*\n$\\\\,$ If we misunderstood the intent behind “other types of underlying functions for representation” please let us know and we will gladly elaborate.\n"}, {"review_id": "QVVcp21T5W", "reviewer": "Reviewer_jhrZ", "summary": "This paper focuses on the problem that which data distribution is more learnable by locally-connected neural networks such as CNN, RNN, and local-attention. The paper introduces the notation of quantum entanglement, theoretically proves and empirically verifies that the network can achieve accurate predictions if and only if the data distribution exhibits low quantum entanglement under canonical partitions of features.", "questions": "1. In Theorem 1, the authors derive an upper bound for quantum entanglement. However, it is not clear whether this upper bound truly ensures *low* entanglement. There are mainly two terms in the bound, $\\ln(R)$ and $\\ln(D_\\mathcal{K})$. The magnitude of the first term is already addressed by the authors, but it is not clear whether the second term can be extremely large. The authors are encouraged to have a discussion on this issue and show that this upper bound is indeed much smaller than the entanglement of a random tensor (as a baseline).\n\n2. How will the network architecture affect the main theoretical results in Section 3.1, 4.1, and 4.2? For example, I wonder if the results still hold if the neural network has skip connections and batch normalization operations.\n\n3. What does feature (re)arrangement mean in Section 5.1? Let us take textual data as an example and consider a sentence with N words. Does a feature rearrangement mean that the words (as well as their embeddings) in the sentence are randomly permuted? The authors are suggested to make this clearer, and better with examples.\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper introduces the notation of quantum entanglement from physics, which provides new insights into the problem of which data distribution is more learnable by a specific family of neural networks.\n\n2. The paper provides a comprehensive theoretical analysis of the above problem.\n\n3. Overall speaking, the paper is easy to read and follow.\n", "weaknesses": "1. The notion of entanglement is not very intuitive. Although the authors formally introduce the mathematical definition of quantum entanglement, it is still not clear what characteristics a data distribution would exhibit if the distribution has low entanglement. I suggest the authors illustrate this low-entanglement property on toy datasets and/or textual data. This intuitive illustration might provide valuable insights to the machine learning community.\n\n2. The authors are encouraged to conduct comprehensive experiments on more architectures and datasets. For example, for image classification, it is suggested to test on classical CNN architectures such as AlexNet, VGG, and ResNet. Besides, textual data should also be investigated.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, and specifically for noting the soundness of our theory and the clarity of our presentation. We respond to your comments and questions below. If our response is satisfactory, we would greatly appreciate it if you would consider raising your score.\n\n> *The notion of entanglement is not very intuitive. … it is still not clear what characteristics a data distribution would exhibit if the distribution has low entanglement. I suggest the authors illustrate this low-entanglement property … . This intuitive illustration might provide valuable insights … .*\n\nThank you for raising this! In line with your suggestion, we will add to the text more intuition behind entanglement, in general and in the context of data distributions. Below is an initial discussion along this line.\n\nGenerally, entanglement is a concept which, given a collection of elements $[N] := \\\\{ 1, 2, … , N \\\\}$ partitioned into two sets $\\mathcal{K}$ and $\\mathcal{J} := [N] \\setminus K$, quantifies how dependent $\\mathcal{K}$ and $\\mathcal{J}$ are. In quantum physics the elements in $[N]$ are particles, and the entanglement quantifies the dependence (quantum interaction) between the particles in $\\mathcal{K}$ and those in $\\mathcal{J}$. In the context of data distributions, the elements in $[N]$ are features (e.g. pixels, text tokens or audio samples), and the entanglement is a measure of dependence between the features in $\\mathcal{K}$ and those in $\\mathcal{J}$. \n\nTo gain some intuition on entanglement as a measure of dependence between the features in $\\mathcal{K}$ and those in $\\mathcal{J}$, consider the case of entanglement equal to zero. There, the population data tensor (Eq. (3)) can be written as an outer product between two tensors, one corresponding to $\\mathcal{K}$ and the other to $\\mathcal{J}$. This may be interpreted as zero correlation between the features in $\\mathcal{K}$ and those in $\\mathcal{J}$ (indeed, by Eq. (3), the population data tensor holds expectations of products of features, and the expectation of a product being equal to a product of expectations is the definition of zero correlation). Moving to the case where entanglement is non-zero, one may view it as a measure of distance from zero correlation — the higher the entanglement, the farther we are from this state, and vice versa.\n\n> *The authors are encouraged to conduct comprehensive experiments on more architectures and datasets ... .*\n\nAs stated in the paper (experimental sections and Appendix J), our experiments currently include the following architectures:\n\n- M5 and ResNet CNNs;\n- S4 RNN; and\n- local self-attention,\n\nand the following datasets:\n\n- Speech Commands audio;\n- CIFAR10 images; and\n- semeion, isolet and dna tabular benchmarks.\n\nTo our knowledge, for a paper whose nature is primarily theoretical, this empirical evaluation is relatively broad. \n\nNotwithstanding the above, following your comment, we began conducting additional experiments with more architectures and more datasets (including textual data). These experiments will take several weeks to run on our hardware. We did however manage to obtain complete results for VGG CNN architecture, and these are qualitatively identical to the CNN results reported in the paper. We will include a full account of the additional experiments in the text once they are complete.\n\n> *In Theorem 1 … it is not clear whether this upper bound truly ensures low entanglement. There are mainly two terms in the bound, $\\ln (R)$  and $\\ln (D_{\\mathcal{K}})$. The magnitude of the first term is already addressed by the authors, but it is not clear whether the second term can be extremely large. The authors are encouraged to have a discussion on this issue and show that this upper bound is indeed much smaller than the entanglement of a random tensor … .*\n\nNote that in Theorem 1, the term $\\ln ( D_{\\mathcal{K}} )$ (which up to a logarithmic factor is on the order of the number of axes $N$) is **multiplied by $\\epsilon$**, the desired degree of approximation. Accordingly, in the regime of interest (low $\\epsilon$), the upper bound is indeed small. In contrast, the theorem shows that there exist tensors for which entanglements are on the order of $\\ln ( D_{\\mathcal{K}} )$. This in fact holds for random tensors as well; a point that will be clarified in the text. Thank you for the question! \n\n> *How will the network architecture affect the main theoretical results … ? For example, I wonder if the results still hold if the neural network has skip connections and batch normalization … .*\n\nIt is possible to extend our analysis to tensor networks, and corresponding neural networks, with connectivities beyond those considered (e.g. connectivities that are non-local, or ones involving skip connections). Such extensions can follow the lines of Appendix I (which lifts the one-dimensional analysis in paper body to arbitrary dimensions). In particular, under such extensions, our theoretical results will still hold, but the definition of canonical partitions (Def. 2) will require adaptation. With regards to batch normalization, as long as it maintains representational capacity (as is typically the case), it will be automatically accounted for by our theory. We will add to the text a discussion including the above, as well as architectural extensions that require further research. Thank you for the question!\n\n> *What does feature (re)arrangement mean in Section 5.1? Let us take textual data as an example … . Does a feature rearrangement mean that the words … are randomly permuted? … .*\n\nIn our context, feature (re)arrangement means applying a permutation to the features in each data instance (e.g. the word embeddings in each sentence, the pixels in each image, or the samples in each audio recording). Note that the permutation need not be random. In fact, Section 5.1 concerns searching for a specific permutation which satisfies a specific property (low entanglement under canonical partitions).\n"}, {"review_id": "AFKdZ5nxIh", "reviewer": "Reviewer_tJGs", "summary": "The paper investigates criterion that make data distributions suitable for being accurately fit by neural networks using tools from tensor networks. Specifically, it shows that some locally connected neural networks (with polynomial activations) fit a data distribution accurately if and only if the quantum entanglement of the data tensor is sufficiently low under all canonical partitions of the axes. The argument uses the previously established fact that a certain tensor network (locally connected tensor network) is equivalent to a locally connected neural network. The main theoretical contribution is to show that low quantum entanglement across canonical partitions is a necessary and sufficient condition for an arbitrary tensor $T$ to be approximated by the locally connected tensor network $\\mathcal{W}_\\mathrm{TN}$. The problem of a locally connected neural network fitting a distribution is then identified with the corresponding data tensor being well-approximated by $\\mathcal{W}_\\mathrm{TN}$, to establish the main claim.\n\nNumerical simulations are performed to show that under random swaps of the features of standard datasets (that are known to be well fit by local neural networks), more swaps results in more entanglement and this corresponds to the predictive performance being correspondingly lower. The authors also suggest a heuristic method for improving the compatibility of data to a local neural network architecture, by searching for permutations of the axes that result in a low entanglement.", "questions": "Does the suggested pipeline lead to any accuracy improvements for natural datasets (without randomly permuted features) and local networks that already achieve good performance on them?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The main result is compelling, providing a clean and computationally efficient measure that may be used to quantify the suitability of a data distribution to certain local neural network architectures. Despite the minor limitations (such as polynomial activations) placed on the corresponding network, this still seems to be significant progress on an important and difficult question.  The potential of systematically searching for feature permutations to improve the predictive power of locally connected networks is also an intriguing possibility.\n\nThe theoretical results seem sound and correct to the best of my knowledge, although I did not check every detail.\n\nThe numerical results do provide evidence of an increase in predictive power from searching for low entanglement feature permutations.", "weaknesses": "1. The presentation of the paper is rather dense in some places, which is understandable due to the breadth of material covered, but makes the exposition hard to follow in places. It would be helpful to have some intuition about how the notions defined in the paper correspond to standard ones in deep learning. For example, the definition of canonical partitions seems unmotivated at first and it may be helpful to the reader if the connection to locality is highlighted. \n\nAs a minor comment, there are a few terms that are defined once and then used in later statements without context: for example, it would be helpful to mention in Definition 2 that $N = 2^L$, and to have a reminder about $R$ near Corollary 1.\n\n2. Section 5.2.2 only presents numerical results for the proposed preprocessing pipeline against a baseline of randomly permuted features. It is not clear to me whether these improvements manifest for real data ie. data already suited to a locally connected network, with the goal being to improve predictive accuracy. It is unlikely in practice that a preprocessing step would be used to improve the performance of a model with very low predictive accuracy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback, and in particular for describing our contributions as “significant progress on an important and difficult question”! We respond to your comments and questions below.\n\n> *The presentation of the paper is rather dense in some places, which is understandable due to the breadth of material covered, but makes the exposition hard to follow in places. It would be helpful to have some intuition about how the notions defined in the paper correspond to standard ones in deep learning. For example, the definition of canonical partitions seems unmotivated at first and it may be helpful to the reader if the connection to locality is highlighted.*\n\nThank you for raising this point! In line with your suggestion, we plan to use additional space in the camera-ready version for discussions providing more intuition behind the notions we use and their relation to deep learning. Below is an initial discussion about canonical partitions.\n\nThe motivation for defining canonical partitions (Definition 2) is that, per Theorem 1, low entanglement under these partitions characterizes the ability of the locally connected tensor network to fit a given tensor. In general, the entanglement under a partition $( \\mathcal{K} , \\mathcal{J} )$ characterizes the dependence between $\\mathcal{K}$ and $\\mathcal{J}$. This, together with the fact that in canonical partitions $\\mathcal{K}$ consists of contiguous indices, imply that low entanglement under canonical partitions can indeed be viewed as a formalization of locality.\n\n> *As a minor comment, there are a few terms that are defined once and then used in later statements without context: for example, it would be helpful to mention in Definition 2 that \n\\(N=2^{L}\\), and to have a reminder about R near Corollary 1.*\n\nThank you for the suggestions! They will be incorporated into the text.\n\n> *Section 5.2.2 only presents numerical results for the proposed preprocessing pipeline against a baseline of randomly permuted features. It is not clear to me whether these improvements manifest for real data ie. data already suited to a locally connected network, with the goal being to improve predictive accuracy. It is unlikely in practice that a preprocessing step would be used to improve the performance of a model with very low predictive accuracy.*\n\n> *Does the suggested pipeline lead to any accuracy improvements for natural datasets (without randomly permuted features) and local networks that already achieve good performance on them?*\n\nThe preprocessing algorithm we propose (in Section 5.1) is not designed for data on which locally connected neural networks already achieve high prediction accuracies. Indeed, we have shown (in Figures 3 and 8) that on such data, namely on audio and image datasets, the criterion sought after by the algorithm — low entanglement under canonical partitions — is satisfied to begin with. In contrast, on tabular data (which may also be real data) the prediction accuracies of locally connected neural networks are known to be subpar (see lines 328-329 of the paper), and our preprocessing algorithm may lead to significant improvements. We demonstrated this in Section 5.2.2 with standard datasets. Note that in tabular data features are by definition arranged arbitrarily, so randomly permuting them (as we did) prior to applying a non-permutation invariant learning architecture (e.g. a locally connected neural network) is the correct thing to do (otherwise, results may be skewed by implicit structure in the default feature arrangement, which is not supposed to exist).\n"}, {"review_id": "Hp2i7sA5HG", "reviewer": "Reviewer_AvgR", "summary": "By utilizing theoretical tools from quantum physics, the authors propose that a locally connected neural network can accurately predict data if and only if the data distribution exhibits low quantum entanglement under certain feature partitions. Based on this result, they develop a preprocessing method to enhance the compatibility between data distributions and locally connected neural networks. Experimental evaluations using various datasets and models validate their findings.", "questions": "1. In corollary 1(line 223), does it still work under other partitions? and what's the motivation for choosing \"canonical partition\"? \n2. It demonstrates that the locally connected neural network is capable of accurate prediction over distribution if only if it admits low entanglements. In the experiments, it increases the entanglement of data via randomly swapping the feature and provides the comparison between a random permutation of features and proposed methods. Why the proposed method, in the numerics (Table 1, 2), is applied to random arrangement data instead of original data? After we manually randomly arrange the data feature, the data might be meaningless which is expected to get bad performance. Thus, is it appropriate to support the argument? If I miss some thing, please correct me.\n", "limitations": " ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "It investigates what makes a data distribution suitable for machine learning from the theories of tensor network and quantum entanglement, which provides a new perspective and tools from other fields to explore the learning theory.", "weaknesses": "The numerical experiments are insufficient, it is only applied to randomly arranged data instead of original data which might be more convincing to support the argument.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We respond to your comments and questions below. If our response is satisfactory, we would greatly appreciate it if you would consider raising your score.\n\n> *The numerical experiments are insufficient, it is only applied to randomly arranged data instead of original data which might be more convincing to support the argument.*\n\n> *It demonstrates that the locally connected neural network is capable of accurate prediction over distribution if only if it admits low entanglements. In the experiments, it increases the entanglement of data via randomly swapping the feature and provides the comparison between a random permutation of features and proposed methods. Why the proposed method, in the numerics (Table 1, 2), is applied to random arrangement data instead of original data? After we manually randomly arrange the data feature, the data might be meaningless which is expected to get bad performance. Thus, is it appropriate to support the argument? If I miss some thing, please correct me.*\n\nOur experimentation (Figures 3 and 8, and Tables 1 to 5) establishes the following:\n* Audio and image datasets, on which locally connected neural networks achieve high prediction accuracies, satisfy the necessary and sufficient condition we derive — low entanglement under canonical partitions.\n* Randomly permuting features in the above datasets leads the condition to be violated, i.e. the entanglement under canonical partitions to be higher, and accordingly prediction accuracies of locally connected neural networks deteriorate.\n* Applying our preprocessing algorithm (which is designed to ensure that the condition is met, i.e. that entanglement under canonical partitions is low) to the permuted datasets recovers a significant portion of the performance lost.\n* Applying our preprocessing algorithm to tabular datasets, on which the prediction accuracies of locally connected neural networks are known to be subpar, leads to significant gains in performance.\n\nIt is important to note that in tabular data, features are by definition arranged arbitrarily, so randomly permuting them (as we did) prior to applying a non-permutation invariant learning architecture (e.g. a locally connected neural network) is the correct thing to do (otherwise, results may be skewed by implicit structure in the default feature arrangement, which is not supposed to exist).\n\nNote also that randomly permuting the features of a dataset does not render it meaningless. Indeed, learning architectures that are permutation invariant (for example fully connected neural networks) are completely unaffected by such permutation, and their prediction accuracies are often high, and in particular far better than chance.\n\n> *In corollary 1(line 223), does it still work under other partitions? and what's the motivation for choosing \"canonical partition\"?*\n\nThe motivation for defining canonical partitions (Definition 2) is that, per our analysis (Corollary 1 in particular), low entanglement under these partitions characterizes the ability of a locally connected neural network to achieve high prediction accuracy. If you are asking about the intuition behind canonical partitions, note that, in general, the entanglement under a partition $( \\mathcal{K} , \\mathcal{J} )$ characterizes the dependence between $\\mathcal{K}$ and $\\mathcal{J}$. This, together with the fact that in canonical partitions $\\mathcal{K}$ consists of contiguous indices, imply that low entanglement under canonical partitions can be viewed as a formalization of locality.\n\nWith regards to extension of Corollary 1 to other partitions: \nIt is oftentimes the case that entanglement is low under canonical partitions, while being high under other partitions. Accordingly, Corollary 1 will not hold true if one replaces the canonical partitions with an arbitrary set of partitions. Nonetheless, if the architecture of the locally connected neural network is modified, then in order for Corollary 1 to hold, the definition of canonical partitions (Definition 2) needs to be modified as well. In that sense, Corollary 1 can be extended to account for other partitions.\n\nWe hope the above discussion adequately addresses your questions (please let us know if not and we will happily elaborate). It is planned to be included in the camera-ready version. Thank you!\n"}]

Author rebuttal:

Meta-review: The paper investigates criteria that make data distributions suitable for being accurately fit by neural networks using tools from tensor networks. The major technical contribution is the establishment of the connection between locally connected neural networks and locally connected tensor networks. Based on that, the authors identified the conditions for whether a locally connected network fitting an objective tensor could be derived from the entanglement (a concept in quantum physics) when applied to the corresponding tensor network.  As a result, the paper provides a mathematically elegant and computationally efficient measure, inspired by quantum physics, to characterize the suitability of a data distribution to certain local neural network architectures.  There is a consensus that this is significant progress on an important and difficult problem, with many potentials yet unexplored, which justifies the recommendation. 

However, there is also a consensus that the paper would benefit from a better presentation of the key ideas. Especially, some conceptual discussions about quantum entanglement, and about the built connection between the expressive power of neural networks and the entanglement, would greatly improve the accessibility of the contribution.  The authors are also advised to include more comprehensive empirical results, as well as other changes,  as promised in the rebuttal.
Decision: Accept (spotlight)