Deep Networks from the Principle of Rate Reduction
Authors: Kwan Ho Ryan Chan
Yaodong Yu
Chong You
Haozhi Qi
John Wright
Yi Ma
Venue:  (2021)

Abstract: This work attempts to interpret modern deep (convolutional) networks from the principles of rate reduction and (shift) invariant classification. We show that the basic iterative gradient ascent scheme for maximizing the rate reduction of learned features naturally leads to a deep network, one iteration per layer. The architectures, operators (linear or nonlinear), and parameters of the network are all explicitly constructed layer-by-layer in a forward propagation fashion. All components of this ``white box'' network have precise optimization, statistical, and geometric interpretation. Our preliminary experiments indicate that such a network can already learn a good discriminative deep representation without any back propagation training. Moreover, all linear operators of the so-derived network naturally become multi-channel convolutions when we enforce classification to be rigorously shift-invariant. The derivation also indicates that such a convolutional network is significantly more efficient to learn and construct in the spectral domain.

Under review as a conference paper at ICLR 2021
DEEP NETWORKS FROM THE PRINCIPLE OF RATE REDUCTION
Anonymous authors
Paper under double-blind review
ABSTRACT
This work attempts interpret modern deep (convolutional) networks from the principles of rate reduction and (shift) invariant classification. We show that the basic iterative gradient ascent scheme for maximizing the rate reduction of learned features naturally leads to deep network, one iteration per layer. The architec- tures, operators (linear or nonlinear), and parameters of the network are all explic- itly constructed layer-by-layer in a forward propagation fashion. All components of this "white box" network have precise optimization, statistical, and geomet- ric interpretation. Our preliminary experiments indicate that such a network can already learn a good discriminative deep representation without any back propa- gation training. Moreover, all linear operators of the so-derived network naturally become multi-channel convolutions when we enforce classification to be rigor- ously shift-invariant. The derivation also indicates that such convolutional net- work is significantly more efficient to learn and construct in the spectral domain.
INTRODUCTION AND MOTIVATION
In recent years, various deep (convolution) network architectures such as AlexNet (Krizhevsky et al., 2012), VGG (Simonyan Zisserman, 2015). ResNet (He al., 2016), DenseNet (Huang et al., 2017), Recurrent CNN, LSTM (Hochreiter & Schmidhuber, 1997), Capsule Networks (Hinton et al., 2011), etc., have demonstrated very good performance in classification tasks of real-world datasets such as speeches or images. Nevertheless, almost all such networks are developed through years of empirical trial and error, including both their architecturessoperatorss and the ways they are to be ef- fectively trained. Some recent practices even take to the extreme by searching for effective network structures and training strategies through extensive random search techniques, such as Neural Archi- tecture Search (Zoph & Le. 2017: Baker et al., 2017), AutoML (Hutter et al., 2019), and Learning to Learn (A (Andrychowicz et al., 2016).
Despite tremendous empirical advances, there is still lack of rigorous theoretical justification of the need or reasons for "deep" network architectures and lack of fundamental understanding of the associated operators (e.g- multi-channel convolution and nonlinear activation) in each layer. As a result, deep networks are often designed and trained heuristically and then used as a "black box." There have been a severe lack of guiding principles for each of the stages: For a given task, how wide or deep the network should be? What are the roles and relationships among the multiple (convolution) channels? Which parts of the networks need to be learned and trained and which can be determined in advance? How to evaluate the optimality of the resulting network? As consequence, besides empirical evaluation, it is usually impossible to offer any rigorous guarantees for certain performance of trained network, such as invariance to transformation (Azulay & Weiss, 2018; Engstrom et al., 2017) or overfitting noisy or even arbitrary labels (Zhang et al., 2017).
In this paper, we do not intend to address all these questions but we would attempt to offer a plausible interpretation of deep (convolution) neural networks by deriving a class of deep networks from first principles. We contend that all key features and structures of modern deep (convolution) neural networks can be naturally derived from optimizing a principled objective, namely the rate reduction recently proposed by Yu et al. (2020), that seeks a compact discriminative (invariant) representation of the data. More specifically, the basic iterative gradient ascent scheme for optimizing the objective naturally takes the form of a deep neural network, one layer per iteration.
This principled approach brings a couple of nice surprises: First, architectures, operators, and param- eters of the network can be constructed explicitly layer-by-layer in forward propagation fashion, and all inherit precise optimization, statistical and geometric interpretation. As result, the so con- structed "white box" deep network already gives good discriminative representation (and achieves good classification performance) without any back propagation for training the deep network. Sec- ond, in the case of seeking a representation rigorously invariant to shift translation, the network convolutional network. Moreover, the derivation indicates
naturally lends itself to a such convolutional network is computationally more efficient to learn and construct in the spectral

---

Under review as a conference paper at ICLR 2021
(Fourier) domain, analogous to how neurons in the visual cortex encode and transit information with their spiking frequencies (Eliasmith & Anderson, 2003; Belitski et al., 2008).
TECHNICAL APPROACH
Consider a basic classification task: given a of samples X (az x E TR and their associated memberships т (x=) E [K] in & different classes, a deep network is typically used to model a direct mapping from the input data æ K" to its class label f(x, 0) æ + y R*, where y is typically a "one-hot" vector encoding the membership information π(x); the j-th entry of y is iff (2)) = j. The parameters 0 of the network is typically learned to minimize certain prediction loss, say the cross entropy loss, via this popular approach provides people a direct and effective way to train a network that predicts the class information, the so learned representation is however implicit and lacks clear interpretation.
type back propagation. Although
2.1 PRINCIPLE OF RATE REDUCTION AND GROUP INVARIANCE
The Principle of Maximal Coding Rate Reduction. To help better understand features learned in deep network, the recent work of Yu et al. (2020) has argued that the goal of (deep) learning is to learn a compact discriminative and diverse feature representation' z = f'x=) E RR" of the data æ
before any subsequent tasks such as classification: x _(xx) h(z) y. To be more precise, instead of directly fitting the class label y. principled objective is to learn a feature map f(x) : x + z which transforms the data æ onto a set of most discriminative low-dimensional linear subspaces {S))
j==1 C R","" one subspace S¹ per class j E [k].
Let Z = [z!....,, x='] ] = [ f(x"") ] be the features of the given samples X. WLOG, we may assume all features 2² are normalized to of unit norm: z' E g--1, For convenience, let II' e Rmxm be diagonal matrix whose diagonal entries encode the membership of samples/features belong to the j-th class: (i. = (xx') = (==).. Then based on principles from lossy data compression (Ma et al., 2007), Yu al. (2020) has suggested that the optimal representation Z. c g--1 should maximize the following coding rate reduction objective, known as the MCR? principle:
Rate Reduction:
AR(Z)= = log det (I+aZZ'
Yi log det (I (I+azZIIZ))
(1)
2
R(Z)
where a = n/(m²²), a, ( 7/- = t/m for = 1,..., k. Given a prescribed quantization error e, the first term R of AR(Z) measures the total coding length for all the features Z and the second term R. is the sum of coding lengths for features in each of the & classes.
In Yu et al. (2020), the authors have shown the optimal representation Z. that maximizes the above object indeed has desirable nice properties. Nevertheless, they adopted conventional deep network (e.g. the ResNet) as a black box to model and parameterize the feature mapping: z = fxx 0). It has empirically shown that with such choice, one can effectively optimize the MCR² objective and obtain discriminative and diverse representations for classifying real image data sets.
However, there remain several unanswered problems. Although the resulting feature representation is more interpretable, the network itself is still not. It is not clear why any chosen network is able to optimize the desired MCR2 objective: Would there be any potential limitations? The good empirical results (say with a ResNet) do not necessarily justify the particular choice in architectures and operators of the network: Why is a layered model necessary, how wide and deep is adequate, and is there any rigorous justification for the use of convolutions and nonlinear operators used? In Section 2.2 we show that using gradient ascent to maximize the rate reduction A R Z) naturally leads to a "white box" deep network that represents such mapping. All linear/nonlinear operators and parameters of the network are explicitly constructed in a purely forward propagation fashion.
Group Invariant Rate Reduction. So far, we have considered the data and features vectors. In many applications, such as serial data or imagery data, the semantic meaning (labels) of the data and their features are invariant to certain transformations g E G (for some group G) (Cohen & Welling, 2016). For example, the meaning of an audio signal is invariant to shift in time; and the identity of an object in an image is invariant to translation in the image plane. Hence, we prefer the feature mapping f(r, 0) is rigorously invariant to such transformations:
'To simplify the presentation, we assume for now that the feature and x: have the same dimension n. But in general they can be different we will soon see, say in the case is multi-channel extracted from
2

---

Under review as a conference paper at ICLR 2021
Group Imvariacce oz f(z, 0), Vg G,
where "~"" indicates two features belonging to the same equivalent class. The recent work of Zaheer et al. (2017); Maron et al. (2020) characterize properties of networks and operators for set permu- tation groups. Nevertheless, it remains challenging to learn features via a deep network that are guaranteed to be invariant even to simple transformations such translation and rotation (Azulay & Weiss, 2018; Engstrom et al., 2017). In Section 2.3, we show that the MCR² principle is com- patible with invariance in very natural and precise way: we only need to assign all transformed versions {ær g E G} into the same class as x and map them all to the same subspace S.? We will rigorously show (in the Appendices) that, when the group G is (discrete) circular ID shifting or 2D translation, the resulting deep network naturally becomes a multi-channel convolution network!
2.2 DEEP NETWORKS FROM MAXIMIZING RATE REDUCTION
Gradient Ascent for Rate Reduction the Training Samples. First let us directly try max- imize the objective AR(Z) Z as function in the training samples Z C g"-1, To this end, we may adopt a (projected) gradient ascent scheme, for some step size 17 > 0:
OAR
Ze+1 & Ze +
subject to Ze+1 C C
Oz Z.
This scheme can be interpreted as how one should incrementally adjust locations of the current features Ze in order for the resulting Ze+1 to improve the rate reduction A I(Z). Simple calculation shows that the gradient
A&R entails evaluating the following derivatives of the terms in (1):
02
0 log det (I + aZZ")
a I aZeZz)) Ze
0z
Es E2nxa
1 1 (1g det I + a; ZII ))))
% a + a Z.I
Z
R
(5)
2
az
C/ CR
Notice that in the above, the matrix E, only depends on Ze hence it aims expand all the features increase the overall coding rate; the matrix C/ depends on features from each class and aims com- press them to reduce the coding rate of each class. See Remark 1 in Appendix A for the geometric and statistic meaning of Eg and CV- Then the complete gradient OAR is of the following form: az
z,
0AR
Eg
Ze
7
C
Z
E ER
(6)
az
Z:
Expansion
j=1
Compression
Gradient-Guided Feature Map Increment. Notice that in the above, the gradient ascent consid-
ers all the features Z, = [ ......,,77 2²]² ] as free variables. The increment Z - Z, = 1y a2 Z. does
PAR
not yet give a transform on the entire feature domain Zς E R Hence, in order to find the optimal
f 0) explicitly, we may consider constructing small increment transform 0z) on the l-th layer feature z, to emulate the above (projected) gradient scheme:
Ze+1 2t + g(ze, 0₂) subject to ze+1 S
such that: [g(=]] 0z)...... [(2 0z)] ~
0AR
oz z, That is, we need to approximate the gradient flow
BAR that locally deforms each (training) feature {=])m² with a continuous mapping g(z) defined 02
on the entire feature space zς E R". See Remark 2 in Appendix A for conceptual connection and difference from the Neural ODE framework proposed by Chen et al. (2018).
By inspecting the structure of the gradient (6), it suggests that a natural candidate for the increment transform g( 0z) is of the form:
& g( 0τ) EIZE En,Clzee'
RR"
(8)
where (z²) E [0, 1] indicates the probability of 2e belonging to the j-th class.² 3 Notice that the increment depends on 1). A linear map represented by E, that depends only on statistics of all features from the preceding layer; 2). A set of linear maps [ and memberships { (ze)) of the features.
'Hence, any subsequent classifiers defined on the resulting set of subspaces will be automatically invariant such transformations.
*Notice that on the training samples Zr. for which the memberships II' are known, the so defined g(zz, 0)
gives exactly the values for the gradient eAR
2
3

---

Under review as a conference paper at ICLR 2021
Since we only have the membership π for the training samples, the function defined in (8) can only be evaluated on the training samples. To ex- trapolate the function to the entire feature space, need estimate T' (zz) in its second term. In the conventional deep learning, this map is typi- cally modeled deep network and learned from the training data, say via back propagation. Nev- ertheless, our goal here is not to learn a precise classifier x' (zy) already. Instead, we only need good enough estimate of the class information in order for to approximate the gradient 2AR well.
E
ge
Figure 1:
Layer structure of the ReduNet: from iteration of gradient ascent for rate reduction.
From the geometric interpretation of the linear maps Eg and Cj given by Remark I in Appendix A, the term p\ = C/ can be viewed projection of xą onto the orthogonal complement of each class j. Therefore, lpp small if z is in class j and large otherwise. This motivates us to estimate exp (-)))))=))))
its membership based on the following softmax function: (ze) Σ oxpppp (x af(l)
E [0, 1].
Hence the second term of (8) can be approximated by this estimated membership:"
(x = Σ Enjolee (z)) = (iC)ze...... Cf
R"
which is denoted as a nonlinear operator (-) on outputs of the feature 2e through & banks of filters: [C)...., C.1. Notice that the nonlinearality arises due to "soft" assignment of class membership based on the feature responses from those filters. Overall, combining (7), (8), and (9), the increment
feature transform from Z₁ to 1 now becomes:
2e+1 X Zt + 1j E 1 1)
[(,,z subject to 2e+1 E S
(10)
with the nonlinear function a defined above and Og collecting all the layer-wise parameters in- cluding E,, C% 7i and X, and with features at each layer always "normalized" onto a sphere Sa-1, denoted as P3n-1. The form of increment in (10) can be illustrated by diagram in Figure 1.
Deep Network from Rate Reduction. Notice that the increment is constructed to emulate the gradient ascent for the rate reduction AR. Hence by transforming the features iteratively via the above process, expect the rate reduction to increase, we will see in the experimental section. This iterative process, once converged say after L iterations, gives the desired feature map f(x, #) on the input 2n x. precisely in the form of deep network, in which each layer has the structure shown in Figure 1:
(11) As this deep network is derived from maximizing the rate reduction, we call it the ReduNet. Notice that all parameters of the network are explicitly constructed layer by layer in a forward propugation fashion. Once constructed, there is need of any additional supervised learning, say via back propagation. As suggested in Yu et al. (2020), the so learned features can be directly used for classification via nearest subspace classifier.
(xx 0) d o o (x)), with (z),0) Pa--i + g(ze,
o
Comparison with Other Approaches and Architectures. Structural similarities between deep networks and iterative optimization schemes, especially those for solving sparse coding, have been long noticed. In particular, Gregor & LeCun (2010) has argued that algorithms for sparse cod- ing, such as the FISTA algorithm (Beck & Teboulle. 2009), can be viewed deep network and be trained for better coding performance, known as LISTA. Later Monga et al. (2019): Sun et al. (2020) have proposed similar interpretation of deep networks as unrolling algorithms for sparse coding- Like all networks that are inspired by unfolding certain iterative optimization schemes, the structure of the ReduNet naturally contains a skip connection between adjacent layers as in the ResNet (He
"The choice of the softmax is mostly for its simplicity as it is widely used in other (forward components of) deep networks for purposes such as selection, gating (Shazeer et al., 2017) and routing (Sabour et al., 2017). In principle, this term can be approximated by other operators, say using ReL.U that is more amenable to training with back propagation, see Remark 3 in Appendix A.
4

---

Under review as a conference paper at ICLR 2021
et al., 2016). Remark 4 in Appendix A discusses possible improvement the basic gradient scheme that may introduce additional skip connections beyond adjacent layers. The remaining k + parallel channels E, C³ of the ReduNet actual draw resemblance to the parallel structures that people later found empirically beneficial for deep networks, e.g. ResNEXT (Xie et al., 2017) or the mixture of experts (MoE) module adopted in Shazeer et al. (2017). But major difference here is that all components (layers, channels, and operators) of the ReduNet are by explicit construction from first principles and they all have precise optimization, statistical and geometric interpretation. Further- more, there is no need to learn them from back proo-ppop,gation, although in principle one still could if further tinettnnigg of the network needed (see Remark 3 of Appendix A for more discussions).
2.3 DEEP CONVOLUTION NETWORKS FROM SHIFT-INVARIANT RATE REDUCTION
We next examine ReduNet from the perspective of invariance to transformation. Using the basic and important case of shift/translation invariance as an example, we will show that for data which are compatible with an invariant classifier, the ReduNet construction automatically takes the form of (multi-channee convolutional neural network, rather than heuristically imposed upon.
1D Serial Data and Shift Invariance. For one-dimensional data x E R" under shift symmetry, we take G be the group of circular shifts. Each observation x' generates family {æ o g g G} of shifted copies, which are the columns of the circulant matrix circ(x') E guxxn (see Appendix B. or Kra& & Simanca (2012) for properties of circulant matrices).
What happens if we construct the ReduNet from these families Zi [circ(x") ,,...,, "irr(aaa)..,,,rc((aa")) The data covariance matrix:
z = [circ(==),... )i (circ(=")....._ circ(a"") = circ(x=)circ((")) E RR"
associated with this family of samples is automatically (symmetric) circulant matrix. Moreover, because the circulant property is preserved under sums, inverses, and products, the matrices Ej and C are also automatically circulant matrices, whose application to a feature vector z can be implemented using cyclic convolution "@" (see Proposition B.1 of Appendix B):
Z2 21 77 ( 02) 2 + 7) e 2 1) a (cc] 21,-.., of 3 z1l)
(12)
Because , 01) consists only of operations that co-vary with eyclic shifts, the features Z2 the next level again consist of familics of shifts: Z.- = farc(x++ngh (0))), ,01))....
circ(x +1g 0m))] Continuing inductively, we see that all matrices E, and C based on such Ze are circulant. By virtue of the properties of the data, ReduNet has taken the form of convolutional network, with no need to explicitly choose this structure!
The Role of Multiple Channels and Sparsity. There is one problem though: In general, the set of all circular permutations of a vector give full-rank matrix. That is, the "augmented" features associated with each sample (hence each class) typically already span the entire space R". The MCR" objective (1) will not be able to distinguish classes as different subspaces.
One natural remedy is to improve the separability of the data by "lifting" the features to higher dimensional space, e.g.. by taking their responses to multiple, filters k,,...,ke kc R"
2|c] k.
circ(ke)z ER", c=
(13)
The filers can be pre-designed prommtin filters, or adaptively learned from the data, or randomly selected as we do in our experiments. This operation lifts each original feature vector R to a C-channel feature, denoted z = [[C]] E RCxn, If we stack the multiple channels of a feature & as a column vector vec(æ) E RTC the associated circulant version circ(E) and its data covariance matrix, denoted as Σ, for all its shifted versions are given as:
circ(=(1))
circ(=(1])
circ(z)=
Σ=
[cire( (incs(l) e R=C (14)
[crc(2[C]]
cire(+]C))
'For ID signals like audio, one may consider the conventional short time Fourier transform (STFT); for 2D images, one may consider 2D wavelets as the Scattering (Bruna & Mallat, 2013). Foor learned filters, one can learn filters the principal components of samples as in the PCANet (Chan al., 2015) from convolution dictionary learning (Li & Bresler, 2019; Qu al., 2019).
5

---

Under review as a conference paper at ICLR 2021
where circ(z|cl) R= with [C] is the circulant version of the c-th channel of the feature s. Then the columns of circ(z) will only span at most an n--dimensional proper subspace in IR".,
However, this operation does not yet render the classes separable features associated with other classes will span the same n-dimensional subspace. This reflects a fundamental conflict between linear (subspace) modeling and invariance. One way of resolving this conflict to leverage addi- tional structure within each class, in the form of sparsity: signals within each class can be assumed to be generated not as arbitrary linear combinations of basis vectors, but as sparse combinations of atoms of different (incoherent) dictionaries D,. Under this assumption, if the convolution kernels {ke] match well the sparsifying dictionaries," 7 the multi-channel responses should be sparse. Hence we may take an entry-wise
nonlinear thresholding, say T(-). on the filter outputs by setting small (say absolute value below e) or negative responses to be zero:
- [circ((k)] = circkkc))) E _
(15)
These features can be assumed to lie on a lower-dimensional (nonlinear) submanifold of R which can be linearized and separated from the other classes by subsequent ReduNet layers.
This multi-channel ReduNet retains the good invariance properties described above: all Eg and C matrices are block circulant, and represent B.2 of Appendix B for a rigorous statement and proof):
1D circular convolutions (see Proposition
E()) é 3 x, (²) @ z
ERR j=1,..,,
(16)
where é, e RCxxxn Hence by construction, the resulting ReduNet is deep convolutional network for multi-channel ID signals. Unlike Xception nets Chollet (2017), these multi-channel convolutions in general are not depthwise separable."
Fast Computation in the Spectral Domain. Since all circulant matrices can be simultaneously diagonalized by the discrete Fourier transform matrix 10 F: circ(2) - F DF (see Fact 5 in Ap- pendix B.1), all E of the form (14) can be converted to standard "blocks of diagonals" form:
p
Dn " Dic
F o
Σ
=
0
1oop
0.:00
E ERuCxnC
(17)
Do
Dec
where each block Dyr is an n X n diagonal matrix. The middle of RHS of (17) is a block diagonal matrix after a permutation of rows and columns. Hence, to compute E and C' E BaCxnC we only have to compute in the frequency domain the inverse of x C. blocks for n times and the overall complexity would be O(nC3) instead of (((nC)²) for inverting generic nC x nC matrix." "I More details for implementing the network in the spectral domain can be found in Appendix B.3 (see Theorem B.3 for rigorous statement and Algorithm I for implementation details).
Connections to Recurrent and Convolutional Sparse Coding. The sparse coding perspective of Gregor & LeCun (2010) is later extended recurrent and convolutional networks for serial data, e.g. Wisdom et al. (2016); Papyan et al. (2016); Sulam et al. (2018); Monga et al. (2019). Although both sparsity and convolution are advocated as desired characteristics for deep networks, they do not explicitly justify the necessity of sparsity and convolutions from the objective of the network, say classification. In our framework, we see how multi-channel convolutions (E, C³), different nonlinear activations (#t T), and the sparsity requirement are derived from, rather than heuristi- cally proposed for, the objective of maximizing rate reduction of the features while enforcing shift invariance.
2D Images and Translation Invariance. In the case of classifying images invariant to arbitrary 2D translation, we may view the image (feature) z E R HC as a function defined on a torus T (discretized as W H grid) and consider G to be the (Abelian) group of all 2D (circular)
"There is vast literature on how learn the most compact and optimal sparsifying dictionaries from sample data, c.g. (Li & Bresler, 2019; Qu et al., 2019). Nevertheless, in practice, often sufficient number of random filters suffice the purpose of ensuring fcatures of different classes are separable (Chan et al., 2015).
'eere the nonlincar operator can be chosen to be a soft thresholding or ReLU.
It remains open what additional structures on the data would lead to depthwise separable convolutions.
H0Here we scaled the matrix F to be unitary, hence it differs from the conventional DFT matrix by 1/
"There are strong scientific evidences that neurons in the visual cortex encode and transmit information in the rate of spiking, hence the so-called spiking neurons (Softky & Koch, 1993; Fliasmith & Anderson, 2003). Nature might be exploiting the computational efficiency in the frequency domain for achieving shift invariance.

---

Under review as a conference paper at ICLR 2021
13
Lenn
LyxD
(a) Maai (2D) (b) Zimin (2D) Loss (2D) (d) m (3D) (e) Zunin (3D) (1) Loss (3D)
Figure 2: Original samples and learned representations for 2D and 3D Mixture of Gaussians. We visualize data points X (before mapping) and features Z (after mapping) by scatter plot. In each scatter plot, each color represents one class of samples. We also show the plots for the progression of values of the objective functions.
translations on the torus. As we will show in the Appendix C, the associated linear operators E and C act on the image feature z as multi-channel 2D circular convolutions. The resulting network will be a deep convolutional network that shares the same multi-channel convolution structures as conventional CNNs for 2D images (LeCun et al., 1995; Krizhevsky et al., 2012). The difference is that, again, the architectures and parameters of our network are derived from the rate reduction objective, and so are the nonlinear activation 7' and T. Again, our derivation in Appendix shows that this multi-channel 2D convolutional network can be constructed more efficiently in the spectral domain (see Theorem C. of Appendix C for a rigorous statement and justification).
3 EXPERIMENTS
We now verify whether the so constructed ReduNet achieves its design objectives through experi- ments synthetic data and real images. The datasets and experiments are chosen to clearly demon- strate the behaviors of the network obtained by our algorithm, in terms of learning the correct dis- criminative representation and truly achieving invariance. It is not the purpose of this work to push the state of the art on any real datasets with highly engincered networks and systems, although we believe this framework has this potential in the future. All code is implemented in Python mainly using NumPy. All our experiments are conducted in a computer with 2.8 GHz. Intel i7 CPU and 16GB of memory. Implementation details and more experiments and can be found in Appendix D.
Learning Mixture of Gaussians in g' and S². Consider mixture of two Gaussian distributions in RR2 that is projected onto S!. We first generate data points from these two distributions, X = [x] i........... xx"] E I2 æf ~ N(u,, o I), and π ( = 1; X2 [ (.......
x E 2 æ N(u2, o2l), and π (x+) = 2. We set m = 500, 01 = 02 = 0.1 and μ1, 22 E S. Then we project all the data points onto S', i..., x3/l 2 [l2. To construct the network (computing E, C for each layer), we set the of iterations/layers L 2, 000, 12 step size r) 0.5, and precision c 0.1. As shown in Figure 2a-2b, we can observe that after the mapping f(- 0), samples from the same class converge to a single cluster and the angle between two different clusters is approximately ' n/2, which is well aligned with the optimal solution Z, of the MCR loss in St. MCR loss of features on different layers can be found in Figure 2c, Empirically, we find that our constructed network is able to maximize MCR2 loss and converges stably. Similarly, we consider mixture of three Gaussian distributions in Ra with means μl, U22 23 uniformly in S?, and variance 01 = 02 = 03 = 0.1, and all data points projected onto S (See Figure 2d-2f). We can observe similar behavior in $ ie., samples from the same class converge to one cluster and different clusters are orthogonal to each other. Moreover, we sample new data points from the same distributions for both cases and find that new samples form the same class consistently converge to the same cluster as the training samples. More examples and details can be found in Appendix D.
Learning Shift Invariant Features. As described in $ 2.3, by maximizing the rate reduction via Eq. (12), we are able to explicitly construct operators that are invariant to (circular) shifts. To verify the effectiveness of our proposed network on shift invariance tasks, we apply our network to classify signals sampled from two different ID functions. The underlying function of the first class is sinusoidal signal hy (1) = sin(l) e, and the second class is composition of sign and sin function, h2(()) sign(sin(()) + e, where e ~ (1, 0.1). (See Figure in Appendix D). Each sample is generated by first picking to [0, 10x). then obtaining equidistant point within the boundaries [to, to + 2T with i.d.d Gaussian noise. Detailed implementations for sampling from h1 and h2 can be found in Appendix D.3. We generate dataset which contains m samples, with m/2 samples in each class, i.e., X = X, X²1 E R Then each sample is lifted to a C-
It is remarkable see how easily our framework leads to working deep networks with thousands of layers! But this also indicates the efficiency of the layers is high. Remark 4 provides possible ways to improve.
7

---

Under review as a conference paper at ICLR 2021
196 5.
700 rinrrde 1'aami
Layers
Similarity
(a) ahhttt (1D)
(b) Zurn (1D)
Loss (1D)
(d) Similarity (1D)
6015
Coaut
Layers
Similarity
(0) X shift (MNIST) (f) Zan (MNIST)
(g) Loss (MNIST)
(h) Similarity (MNIST)
Figure 3: Heatmaps of cosine similarity between data Xlan/learned features Zain. MCR² loss, and distance between shift samples and subspaces. For (a), (b), (e). (I), we pick one sample from each class and augment the sample with its every possible shifted ones. then calculate the cosine similarity between these augmented samples. For (d), (h), we first augment each samples in the datasct with its every possible shifted ones, then we evaluate the cosine similarity (in absolute value) between pairs across classes: for each pair, one sample from training and one sample is from test which belong to different classes.
channel feature as defined in (13), i.e., X E (n-C))m x For training data, We set the number of features n = 150, samples m 400, channels C = 7, iterations/layers 0.1. We sample the same number of test data points followed by the same procedure. As shown in Figure 8, we observe that the network can map the two classes of signals to orthogonal subspaces both of the network, we first pick 5 signal samples from each class (from test dataset) and get their corresponding augmented samples by shifting. Then we have m 105 augmented samples for each original signal, X E TR 1,500 and we visualize the pairwise inner product of X and their representations, Zuniti E (150-7)) 1,500 in Figure 3a-3b. Moreover, we augment every sample (from the test dataset) with its all possible shifted versions and calculate the cosine similarity between their representations and the representations of all the training samples from the other class (in Figure 3d). We find that the proposed network can map different classes of signals (including all shifted augmentations) to orthogonal subspaces, to increase the MCR loss (shown in Figure 3c).
= 2, 000, step size
7 0.1, and precision
training and test datasets. To verify invariance property
Rotational Invariance on MNIST Digits. We study the ReduNet on learning rotation invariant features on MNIST dataset (LeCun, 1998). We impose a polar grid on the image E #R with its geometric center being the center of the 2D polar grid. For each radius rs. i E [C]. we can sample I' pixels with respect to each angle ' [ (2nr/T) with E [T'. Then given image sample from the dataset, we represent the image in a polar coordinate representation x(p) = (nt,,, v1.1) E RT'C Our goal is to learn rotation invariant features, i.e., we expect to learn f(. O) such that (f(x(p) g. geG lie in the same subspace, where g the shift transformation in polar angle. By performing polar coordinate transformation for images from digit "0' and digit '1' in the training dataset, we can obtain the data matrix X (p) E x( We use m = 2, 000 training samples, set 0.1, step-
I' 200 and C = 5 for polar transformation, and set iteration L = 3, 500, precision size 17 = 0.3. We generate 1, 000 test samples followed by the same procedure. In Figure 10, we see that proposed ReduNet is able to map most samples from different classes orthogonal subspaces (w.r.t. class) on test dataset. Meanwhile, in Figure 3e, 3f, and 3h, we observe that the learnt features are invariant shift transformation in polar angle (i.e., arbitrary rotation in æ)).
4 CONCLUSIONS AND FUTURE WORK
This work offers an interpretation of deep (convolutional) networks by construction from first prin- ciples. provides a rigorous explanation for the deep architecture and components from the per- spective of optimizing the rate reduction objective. Simulations and experiments on basic data sets clearly verify the so-constructed ReduNet achieves the desired functionality and objective. Although in this work the ReduNet is forward constructed, one may study how to effectively fine tune it via back propagation. We believe rate reduction provides a principled framework for designing new networks with interpretable architectures and operators that scale up to real-world datasets and problems, with better performance guarantees. This framework can also be naturally extended to settings of online or unsupervised learning if II is partially not known and is be optimized.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Mongi A Abidi, Andrei V Gribok, and Joonki Paik. Optimization Techniques in Computer Vision Springer, 2016.
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. Advances in neural information processing systems, pp. 3981-3989, 2016.
Aharon Azulay and Yair Weiss. Why do deep convolutional networks generalize so poorly to small image transformations? arXiv preprint arXiv: 1805. 2177,2015
Bowen Baker, Otkrist Gupta, N. Naik, and R. Raskar. Designing neural network architectures using reinforcement learning. ArXiv, abs/161 1.011677 2017.
Amir Beck and Mare Teboulle. fast iterative
algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-200 2009.
Andrei Belitski, Arthur Gretton, Cesare Magri, Yusuke Murayama, Marcelo A. Montemurro, Nikos K. Logothetis, and Stefano Panzeri. Low-frequency local field potentials and spikes in primary visual cortex convey independent visual information. Journal of Neuroscience, 28 (22):5696-5709, 2008. ISSN 0270-6474. doi: 10. (001523/NEUROSSIL000000 https: /www.
URL
wwt.or/g///oo/////eeeeeee 22 5696.
Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3576):187211886, 2013.
Tsung- Han Chan, Kui Jia, Shenghua Gao, Jiwen Lu, Zinan Zeng, and Yi Ma. PCANet: A simple deep learning baseline for image classification? IEEE transactions on image processing. (4(::): 5017-5032, 2015.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differ- ential equations. In Advances in Neural Information Processing Systems, pp. 6571-6583, 2018.
François Chollet. Xception: Deep learning with depthwise separable convolutions. 2017 IEEE
Conference Computer Vision and Pattern Recognition (CVPR), pp. 1800-1807, 2017.
Taco S. Cohen and Max Welling. Group equivariant convolutional networks.
CoRR,
abs//660..0776. 2016. URL
org/ aaw/aasss00 07576.
Dheeru Dua and Casey Graff. Uci machine learning repository, 2017. URL http://archive.
ics. wui. edu/ml.
Chris Eliasmith and Charles Anderson. Neural Engineering: Computation, Representation and Dynamics in Neurobiological Systems. Cambridge, MA, 01 2003.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. A rotation and translation suffice: Fooling CNNs with simple transformations. arXiv preprint arXiv:1712.02779, 2017.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 399-406 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Geoffrey E. Hinton, A. Krizhevsky, and Wang. Transforming auto-encoders. In ICANN, 2011.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory, Neural computation, 9:1735- 80, 12 1997. doi: 10. 10.11666 9ttp://cc..199.9....
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 2261-2269, 2017.

---

Under review as a conference paper at ICLR 2021
Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren Automatii Machine Learning: Methods, Systems, Challenges. Springer, 2019.
Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, vol-
ume 75 of Proceedings of Machine Learning Research, pp. 1042-1085, PMLR, 2018. URL
http:/ pwwpceooediicooo ngs m www.s/esssss 3i5i//imm jinl Ba html.
Irwin Kra and Santiago R Simanca. On circulant matrices. Notices of the American Mathematical Sociery, 59:368-37777 00088-3772227 2012.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Andrew Lavin and Scott Gray. Fast algorithms for convolutional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4013-4021, 2016.
Yann LeCun. The MNIST database of handwritten digits. http://yann. lecun. com/exdb/mnist// 1998.
Yann LeCun, L.D. Jackel, Leon Bottou, Corinna Cortes, S. Denker, Harris Drucker, I. Guyon, U.A.
Muller, Eduard Sackinger, Patrice Simard, and Vapnik. Learning algorithms for classification: A comparison on handwritten digit recognition, pp. 261-276. World Scientific, 1995.
Yanjun Li and Yoram Bresler. Multichannel sparse blind deconvolution on the sphere. IEEE Trans- actions on Information Theory, 65 (5(11))77155-433 2019.
Yi Ma, Harm Derksen, Wei Hong, and John Wright. Segmentation of multivariate mixed data via lossy data coding and compression. IEEE transactions on pattern analysis and machine intelligence, 544-1566, 2007.
Haggai Maron, O. Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. ArXiv, abs/2002.08557 088599 2020.
Michael Mathicu, Mikael Henaff, and Yann LeCun. Fast training of convolutional networks through ffts, 2013.
Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. arXiv preprint arXiv:1912.105577 2019.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of conver- gence o (1/K* 2). Doklady AN USSR, volume 269, pp. 543-547, 1983.
Vardan Papyan, Yaniv Romano, and Michael Elad. Convolutional neural networks analyzed via convolutional sparse coding. Journal of Machine Learning Research, 18, 07 2016.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning python. the Journal of machine Learning research, 12:2825-288 2830. 2011.
Qing Qu, Xiao Li, and Zhihui Zhu. A nonconvex approach for exact and efficient multichannel sparse blind deconvolution. In Advances in Neural Information Processing Systems, pp. 4017- 4028, 2019.
Sara Sabour, Nicholas Frosst, and Geoffrey E. Hinton. Dynamic routing between capsules. CoRR, 2017. URL http: http::/arxiv.... org/ abs 1700. 09829.
Hanie Sedghi, Vineet Gupta, and Philip Long. The singular values of convolutional layers. arXiv preprint arXiv: 1805. 10408, 2018.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. In ICLR, 2017. URL https:ttp/// http:::////ppeeiiiieeeee eew. f d= ckMDqlg.
10

---

Under review as a conference paper at ICLR 2021
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2013.
William R Softky and Christof Koch. The highly irregular firing of cortical cells is inconsistent with temporal integration of random EPSPs. Journal of Neuroscience, 13(1):334-350 1993.
Jeremias Sulam, Vardan Papyan, Yaniv Romano, and Michael Elad. Multilayer convolutional sparse modeling: Pursuit and dictionary learning. IEEE Transactions on Signal Processing, 66(15): 4090 2018.
Xiaoxia Sun, Nasser Nasrabadi, and Trac Tran. Supervised deep sparse coding networks for image classification. IEEE Transactions Image Processing. 29:405-418, 2020.
Nicolas Vasilache, J. Johnson, Michaël Mathieu, Soumith Chintala, Serkan Piantino, and Y. LeCun. Fast convolutional nets with fbfft: A gpu performance evaluation. CoRR, abs/1412.7580, 2015.
Scott Wisdom, Thomas Powers, James Pitton, and Les Atlas. Interpretable recurrent neural networks using sequential sparse recovery. ArXiv, abs/161 1.07252, 2016.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual trans- formations for deep neural networks. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 5987-5995, 2017.
Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade-off for generalization of neural networks. In International Conference on Machine Learning (ICML), 2020.
Yaodong Yu, Kwan Ho Ryan Chan, Chong You, Chaobing Song, and Yi Ma. Learning diverse and discriminative representations via the principle of maximal coding rate reduction. arXiv preprint wwXi::2006.08558, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 3391-3401. Curran Associates, Inc., 2017. URL 6931 deep- sets.pet pdf.
nips. cc/paper/
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. 2017.
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. 2017. URL https: hamps://arxee //tpxiavvvvv///////////////aaavl wwg/ooogg......oooooooo........e a /6611. 01578.

---

Under review as a conference paper at ICLR 2021
A ADDITIONAL REMARKS AND EXTENSIONS
Remark (Interpretation of the Two Linear Operators) For any ž1 we have
I + oZ.Z;) = Zeqi where qi argmin allze Zeqe + q
(18)
qe
Notice that qi exactly the solution to the ridge regression by all the data points Ze concerned. Therefore, Eg (similarly for C is approximately (i.e. when m large enough) the projection onto the orthogonal complement of the subspace spanned by columns of Ze. Another way to interpret the matrix Eg is through eigenvalue decomposition of the covariance matrix Zi Assuming that Zi Zi UAA.Už where De- = di,g Oa), we have
Es U2 diag 1 + (0)
1 (oO Ui.
(19)
Therefore, the matrix Eg operates on a vector Ze by stretching in way that directions of large variance are shrunk while directions of vanishing variance are kept. These are exactly the directions (4) in which we move the features so that the overall volume expands and the coding rate will increase, hence the positive sign. To the opposite effect, the directions associated with (5) are exactly "residuals" of features of each class deviate from the subspace which they are supposed to belong. These are exactly the directions in which the features need to be compressed back onto their respective subspace, hence the negative sign.
Essentially, all linear operations in the ReduNet are determined by data conducting "auto- regressions" " among themselves. The recent renewed understanding about ridge regression in an peeepparameterized setting ( (Yang al., 2020) indicates that using seemingly redundantly sampled data (from each subspaces) as regressors do not lead to overfitting
Remark (Connection and Difference from Neural ODE) Notice that one may interpret the in- crement (7) discretized version of a continuous ordinury differential equation (ODE):
[z, 0).
(20)
Hence the (deep) network so constructed can be interpreted as certain neural ODE (Chen et al., 2018). Nevertheless, unlike neural ODE where the flow is chosen to be some generic structures, here our g(z. 8) is to emulate the gradient flow of the rate reduction on the feature set
Ž OAR
(21)
az
and its structure is entirely derived fully determined from this objective, without any other priors or heuristics.
Remark 3 (Approximate with ReLU Network) In practice, there are many other simpler non- linear activation functions that one can use to approximate the membership (-) and subsequently the nonlinear operation in (9). Notice that the geometric meaning of in (9) is compute the "residual" of each feature against the subspace to which it belongs. So when we restrict all our fea- tures to be in the first (positive) quadrant of the feature space, one may approximate this residual using the rectified linear units operation, ReLUs, on Pj C. t or its orthogonal complement:
(zz)) α 2t Σ ( j=1
(22)
where (C,) is the projection onto the j-th class and ReLU(z) max(0, z). The above approximation good under the more restrictive assumption that projection of z; on the correct class via P is mostly large and positive and yet small or negative for other classes.
The resulting ReduNet will be network primarily involving ReLU operations and feature normal- ization (onto Sa-1) between each layer. Although in this work, we have argued that the forward- constructed ReduNet network already works large extent, in practice one certainly can conduct back- back- propagation to further fine tune the so-obtained network, say to correct some remaining errors in predicting labely of the training data. Empirically, people have found that deep networks with ReLU activations are easier to train via back propagation (Krizhevsky et al., 2012).
13 Most current neural networks seem to adopt this regime.
P/ can he viewed the orthogonal complement C.
12

---

Under review as a conference paper at ICLR 2021
Remark 4 (Accelerated Optimization via Additional Skip Connections) Empirically. people have found that additional skip connections across multiple layers may improve the network performance, e.g. the DenseNet (Huang al., 2017). In our framework, the role of each layer is precisely interpreted as one iterative gradient ascent step for the objective function AR. our experiments (see Section 3), have observed that the basic gradient scheme sometimes converges slowly, resulting in deep networks with thousands of layers (iterations)! To improve the efficiency of the basic ReduNet, one may consider in the future accelerated gradient methods such as the Nesterov acceleration (Nesterov, 1983) or perturbed accelerated gradient descent (Jin et al., 2018). Say to minimize or maximize a function h(z). such accelerated methods usually take the form:
Pi-1 2e + Be (Zt -Z(-1); 2e+1
(23)
Pe+1 7) Wh(p(+1)-
Hence they require introducing additional skip connections among three layers E-1, and 1. For typical convex or nonconvex programs, the above accelerated schemes can often reduce the number of iterations by magnitude.
13

---

Under review as a conference paper at ICLR 2021
B 1D CIRCULAR SHIFT INVARIANCE
It has been long known that to implement a convolutional neural network, one can achieve higher computational efficiency by implementing the network in the spectral domain via the fast Fourier transform (Mathieu et al., 2013; Lavin & Gray, 2016; Vasilache et al., 2015). However, our purpose here is different: We want show that the linear operators E and C derived from the gradient flow of MCR are naturally convolutions when we enforce shift-invariance rigorously. Their convolution structure derived from the rate reduction objective, rather than heuristically imposed upon the net- work. Furthermore, the computation involved in constructing these linear operators has naturally the spectral domain via fast Fourier transform. Arguably this work
efficient implementation the first to show multi-channel convolutions, together with other convoluiion-presevve operations in the ReduNet, are both necessary and sufficient to ensure shift invariance.
nonlinear
To be somewhat self-contained and self-consistent, this section, first introduce our notation and review some of the key properties of circulant matrices which will be used to characterize the properties of the linear operators E and C and to compute them efficiently. The reader may refer to Kra & Simanca (2012) for more rigorous exposition circulant matrices.
B. PROPERTIES OF CIRCULANT MATRIX AND CIRCULAR CONVOLUTION
Given vector 2 [20, 21,.... circulant matrix form as
2n-1]" E R
15
we may arrange all its circular shifted versions in
20
žn
22
21
21
20
2n
circ(z)
E RRRN
(24)
Zn
2n
Zn-1
2n
21
20
Fact 1 (Convolution matrix multiplication via circulant matrix) The multiplication of cir- culant matrix circ(z) with a vector x E Rh gives a circular (or cyclic) convolution, i.e.,
circ(z) ===
(25)
where
x)1 Z mod
(26)
Fact 2 (Properties of circulant matrices) Circulant matrices have the following properties:
Transpose of a circulant matrix, say circ(2)), is circulant;
Multiplication of two circulant matrices is circulant, for example circ(z)circ(22)
For non-singular circulant matrix, its inverse is also circulant (hence representing circular convolution).
These properties of circulant matrices are extensively used this work as for characterizing the convolution structures of the operators E and C².
Given a set of vectors [z!,..., E R=xm, let circ(2') Bexa be the circulant matrix for z!
Then we have the following:
Proposition B.1 (Convolution structures of E and Ci) Given a set of vectors Z = [z] ..... ")) the matrix:
E = a Σ circ(= ((r==)"circ(zt))))
a circulant matrix and represents a circular convolution:
Ez 6 z,
where e is the first column vector of E. Similarly, the matrices C associated with any subsets of Z
also circular convolutions.
We superscript indicate (conjugate) transpose of matrix
14

---

Under review as a conference paper at ICLR 2021
B.2 CIRCULANT MATRIX AND CIRCULANT CONVOLUTION FOR MULTI-CHANNEL SIGNALS
In the remainder of this section, we view z as ID signal such as audio signal. Since we will deal with the more general case of multi-channel signals, we will use the traditional notation denote the temporal length of the signal and C' for the number of channels. Conceptually, the "dimension" n such a multi-channel signal, viewed as vector, should be n = CT. 16 As we will also reveal additional interesting structures of the operators E and C2 in the spectral domain, use as the index for time, p for the index of frequency, and c for the index of channel.
Given multi-channel ID signal & E CxT we denote
=[1]*]
2
[=(0), (1)... z(T 1)] (E0))
(27)
=[O]"
To compute the coding rate reduction for a collection of such multi-channel ID signals, we may flatten the matrix representation into a vector representation by stacking the multiple channels of as column vector. In particular, we let
vec(z) [a] ((1())) -1) 1))
(CXT).
(28)
Furthermore, to obtain shift invariance for the coding rate reduction, we may generate a collection of shifted copies of (along the temporal dimension). Stacking the vector representations for such shifted copies as column vectors, we obtain
circ(=[1])
circ(2)= =
E ((CTTT)
(29)
circ(z|C))
In above, we overload the notation "circ(-)" defined in (24).
We now consider collection of m multi-channel 1D signals (z E RC Compactly repre- senting the data by Z E CxT'xm in which the i-th slice on the last dimension is 2', we denote
% 1 [c] smh [c]l RTxx
(t) (t)......... =n (t)) cCmm
(30)
In addition, we denote
vec Z [vec(z)) ),. vec (=") R (CCT])x
(31)
circ Z = [circ( ,,..., circ(z"") E (R(XXT)((TXM)
Then, we define the shift invariant coding rate reduction for Z E RCxTx as
Afcire ZZ II) = 1 -((cirr(()).
k
1
log det det
Iia-circ 2)*
Ti
log det T+ay--crdd circ( (2) 2). circ(2)*
2T
27
(32)
where a m722 ship matrix in an obvious way. Note that we introduce the normalization factor T in (32) because the circulant matrix circ(2 Z) contains T' (shifted) copics of each signal.
CT
a
r(TD)TT2 a
CT
C
tr( and I is augmented member-
By applying (4) and (5), obtain the derivative of A Rerre (2, IT) as
1 0 log det (I + acirc( (Zrirc()))rr(Z)))
2 Oog det (I+ (circ(()))rrr(())) òcirc Ø)
1
2T
@vec Z)
acirc Z) a acirc (circ(Z)cir((Z)))
2T
Ovec Z)
(33)
vec(2),
E xI(C
'Notic that in the main paper, for simplicity, we have used to indicate both the ID "temporal" or 2D "spatial" dimension of signal, just to be consistent with the vector case, which corresponds to 7 here. All notation should be clear within the context.
15

---

Under review as a conference paper at ICLR 2021
0 log det I + ( cirr)))(( 7j (1 axyiie ()circ(2 vec 2 2)11²
7j
27
Ōvec Z)
Ci ER(OXT)X(CXX)
(34)
In the following, we show that E vec(z) represents a multi-channel circular convolution. Note that
T+o E.m dire(2 dire(" [[])crc(( (I))
Eis: circ(z' (1)c=(())crc(((=([]]
=
(35)
D_,,circf [C])crc(=>
I+E adirc(s "C)dcs=(C))dre( [C])"
By using Fact 2, the matrix in the inverse above is a block circulant matrix, i.e., block matrix where each block is a circulant matrix. A useful fact about the inverse of such matrix is the following.
Fact 3 (Inverse of block circulant matrices) The inverse of block circulant matrix is block cir- culant matrix (with respect to the same block partition).
The main result of this subsection is the following.
Proposition B.2 (Convolution structures E and C3) Given collection of multi-channel ID the matrix E is a block circulant matrix, i.e.,
signals { E C Ji=p
E
Σ1.
E
(36)
EC11
Еc,c
where each Ee,e' E RTXT circulant matrix. Moreover, represents multi-channel circular convolution, i.e., for any multi-channel signal z E CXT we have
E v
@).
In above, E RCXCXT is multi-chamnel convolutional kernel with é/c, c) E RRT being the first column vector of Ee,c' and e @ & RCXT is the multi-channel circular convolution (with "@" overloading the notation from Eq. (26)) defined as
(e C
[d = elc, dx(c], vc= Le.,,..,CC.
(37)
d=11
Similarly, the matrices Oo associated with any subsets of Z are also multi-channel circular convo- lutions.
Note that the calculation of E in (35) requires inverting matrix of size (C' x T)) (CxI) T). In the following, we show that this computation can be accelerated by working the frequency domain.
B.3 FAST COMPUTATION IN SPECTRAL DOMAIN
Circulant matrix and Discrete Fourier Transform. A remarkable property circulant matrices that they all share the same set of eigenvectors that form a unitary matrix. We define the matrix:
w
0
w
w
w
I
w/
Fr = 1
E TTXT
(38)
VT
2T-
(T-2)(T-1)
w/
w
wi
W/
w/
WT
T-1
WT
(T (T
WT
(T-
where WT = exp( 2x/-1) is the roots of unit (as wT = 1). The matrix Fr a unitary matrix: Fr and the well known Vandermonde matrix. Multiplying a vector with Fr is known as the discrete Fourier transform (DFT), Be aware that the conventional DFT matrix differs from our definition of Fr here by a scale: it does not have the vT
in front. Here for simplicity, we scale it so that Fr a unitary matrix and its inverse is simply its conjugate transpose Fř, columns of which represent the eigenvectors of circulant matrix (Abidi et al., 2016).
16

---

Under review as a conference paper at ICLR 2021
Fact 4 (DFT matrix-vector multiplication) The DFT of a vector R can be computed
DFT(z) Fr. EC,,
(39)
where
T-1 Σ
DFT(2)()) VT
2(t) wT
vp 0,1,..,,T-1 11
(40)
1=
The Inverse Discrete Fourier Transform (IDFT) of signal v E Ct can be computed as
IDFT(v) = Fi EC
(41)
where
IDFT(v)(t) VT Σ v(p) wp) wT v= 0,=0,,..... --1.
(42)
Regarding the relationship between circulant matrix (convolution) and discrete Fourier transform, we have:
Fact 5 An n X n matrix M C is a circulant matrix if and only if diagonalizable by the unitary matrix F.:
F,MF= D or M F. DF.
(43)
where D is diagonal matrix of eigenvalues.
Fact 6 (DFT are eigenvalues of the circulant matrix) Given vector z E CT, we have
Fr circ(z) Fi diag(DFT(z)) or circ(z) Fj diag(DFT(z)) Fr. That is, the eigenvalues of the circulant matrix associated with vector are given by its DFT.
(44)
Fact 7 (Parseval's theorem) Given any CT, we have |||||2 [DFT(=)]l2 More precisely,
T-1
T-1
| 1=
[p]
(45)
This property allows us easily "normalize" features after each layer onto the sphere S directly the spectral domain (see Eq. (10) and (62)).
Circulant matrix and Discrete Fourier Transform for multi-channel signals. We now consider multi-channel ID signals z e CCT Let DFT(=) E CCXT be matrix where the e-th row is the DFT of the corresponding signal i.c.,
DFT(2
DFT(=) =
E CCXT
(46)
DFT(=
Similar to the notation in (27), denote
DF
DFT(2)
(3)) (FF(())))..,DFT(())T)) 1))
DF
(DFT(3](())) (47)
As such, have DFT(= [FC.
By using Fact 6, circ(z) and DFT(=) are related follows:
F- (iag(DFT(( Fr
Fr
0
diag (iag(DFF()(L))
circ(z)=
Fr. (48)
F (iag(())))(())) Fr
Fr diag(DFT(=(CI))
17

---

Under review as a conference paper at ICLR 2021
We now explain how this relationship can be leveraged to produce fast computation of E defined in (33). First, there exists permutation matrix P such that
(2 11) diag (DFT (2)))
())
0
0
(L)())
(49)
_diag(DFT(=(()) Combining (48) and (49), we have
0
DFT(3) 1)
Fi
0
Fr
circ(z) circ(z)*
:
P D(2) p
(50)
0
Fr
Fr
where
DFT(=)(0) DFT(3)(0)
(
(51)
DF 1) DFT( -
Now, consider collection of m multi-channel ID signals Z E RC Similar to the notation in (30), we denote
DFT DFT (eF. DFT [c]] E R Tx
(52)
DFT(Z) (
(F) Rcmm
By using (50), we have
Fi
Fr
0
E
:
P
I ((**)
P
(53)
0
F7
1=1
0
Fr
Note that a [I + a. Σm D( equal
(4)DFT(2)())DDF))) DFT((")
0
(54)
Therefore, the calculation of only requires inverting T matrices size x C. This motivates us construct the ReduNet in the spectral domain for the purpose of accelerating the computation, as we explain next.
Shift-invariant ReduNet in the Spectral Domain. Motivated by the result (54), we introduce the notations E(p) e CxCxT and (p) E R CxCXT given by
E(p) = a. [ IIa- DF)(()()) -FF( Coxo
(55)
('(p) = aj [ I+ (FT II, DFT( coo.
(56)
In above, E(p) (resp., (p)) is the p-th slice of & (resp., (+) the last dimension. Then, the gradient of A Raie (2 II) with respect to Z can calculated by the following result.
Theorem B.3 (Computing culti-channel convolutions E and C³) Let U CexTXm and Wi E CCxTxm l,...,k be given by
Ü(p) = E(p) (p)).
(57)
('()) = ('()) (FT(2)()) -= ;=1,...;hk
(58)
18

---

Under review as a conference paper at ICLR 2021
for each p {O..... T 1}. Then, we have
T 1}.
1 a llgg det + a circ( circ
IDFT(U),
(59)
21
0z
Yj log det aa circ Z circ ()))
IDF)(W"IT))
(60)
27
dz
By this result, the gradient ascent update in (3) (when applied to AReir Z, II)) can be equivalently expressed as an update in frequency domain on Vi (FF((z)) as
Ve+1()) & Ve(p) + (E(()) Ve(p) Σ (,C((t) Ve(())T). p p= 0 1. (61) 1=1
Similarly, the gradient-guided feature map increment in (10) can be equivalently expressed as an update in frequency domain on 0, (=;) as
det (p) or(p) &(( - a (c) ..... (CCT)/6()).....C.....
p p= (62)
subject to the constraint that |/ | 1| F 1 (the first equality follows from Fact 7). We summarize the training, or construction to be more precise, of ReduNet in the spectral domain
Algorithm
Proof: [Proof to Theorem (B.3)) From (4), (53) and (48), we have
3 log det
[ [+ acirc (()rr((())r))))) -Eirrc(z))= =
F
diag(DFT(='11))
Fr
2
(circ(z*)
dig(DFF(=*(C))
(63)
DFT(3"XO)
P
I+a
E
Fr (64)
(TT
F
DF)
P
Fr
(65)
E(T D)
F
70(
Fr.
diag(n [1]
P
Fr
Fr
(66)
(T--1)
diag( (CT)
(67)
Therefore, we have
Ölog det (I + a circ(2) circ(
det
0 log det (I a circ( circ(Z)'
Øcirc
2
0z
2
òcirc(2')
0z
T IDFT(u').
(68)
By collecting the results for all i, we have
27 log det I I+a circ(Z) circ(Z)*
IDFT(UU)
(69)
az
In similar fashion, get
i Th log det I a+ circ(Z) (Z) H cir)
2T
73 IDFT(WS.IP)
(70)
az
19

---

Under review as a conference paper at ICLR 2021
Algorithm Training Algorithm (ID Signal, Shift Invariance, Spectral Domain)
Input: Z RRCxXx xm II, 6 > 0, X, and a learning rate n
1: Set c mez, {aj (( } fog = t((1)) )
f==1-
2: Set Vo (p)(p) E CC pp=0,i=1 = DFT(Z) E CCXTxm
3: for = 1.2..... do
4: # Step Compute & and C.
5: for p- 0, ,,..., T 1 do
6:
Compute Ee(p) E CCCC and (c) E ecxoOs
f==1
(p) = a [ a Ve-(()) ( (p) = aj [I Vz-1 II VV-1 end for
7:
8:
# #Step 2: Update i² for each i. do
9:
for =
10:
# Compute projection at each frequency
for p 0, 1, 1,.... T do Compute (p: (p) (p) up) (cx1) 1=
13:
end for
14:
# Compute overall projection by aggregating over frequency p.
15:
Let (P') = !p: (O).... ........, . (T 1)] E (CxT)) 1j=13
16:
# Compute soft assignment from projection.
exp( p\)))) }*
17:
Compute / Ei= - $=1
18:
# Compute update at each frequency p.
for p 0, I,..,,T T
1 do
20:
(p()) = 0. (p) end for i 5t |
(p())))()) Ej 75 . (x) o((())
21:
22:
23:
end for
24:
Set Z. = IDFT(V;) as the feature at the f-th layer;
25:
# Evaluate the objective value.
27 +NO (log + a Vp(r) V((r))) t((1))
log del [I + aa ao; Ve(p) II' Be6or1):
26:
m
27:
end for
Output: features Zr, the learned filters {E((p)ee and (p)
20

---

Under review as a conference paper at ICLR 2021
C 2D CIRCULAR TRANSLATION INVARIANCE
To large degree, both conceptually and technically, the 2D case is very similar to the ID case that have studied carefully in the previous Appendix B. For the sake of consistency and completeness, we here gives brief account.
C.I DOUBLY BLOCK CIRCULANT MATRIX
In this section, we consider 2D signal such as image, and use H and W to denote its "height" and "width", respectively. will convenient to work with both a matrix representation
z(0.0)
x(0, 1)
200 W - -1) (1,, W 1)
x(1,0)
x(1,1)
(71)
cH 1,0)
2(H 1,
*(H - 1, 1)
as well as vector representation
vec(z) = 0) =00 W 1); =), (1.,)),...,......... W - 1),...
(1),.....
2 1,0) 2(H W -.w-]]] D]]" (Hxw) (72)
We represent the circular translated version of z as trans (z) E Hx by amount of p and on the vertical and horizontal directions, respectively. That is, we let
(ransp..(=)(M.. w) z(h - mod H, w q mod W)) v(h, w) {0,..... H 1} x (O...., W 1]. (73)
is obvious that transo.o z. Moreover, there total number of H W distinct translations given by {transp.g (z), (p, q) E {O...., H 1} 1} x W - 1}}. We may arrange the vector representations of them into a matrix and obtain
circ(=)= = ve(trros_of).....eeeetrsss..)))
vec(trans1,0 vec(trans),
((( (74)
The matrix circ(2) ) is known as the doubly block circulant matrix associated with z (see, e.g., Abidi et al. (2016); Sedghi et al. (2018)).
We now consider a multi-channel 2D signal represented as a tensor ž E CC where C is the number of channels. The e-th channel of is represented as z|c] Hx and the (h, w)-th pixel is represented as (h, w) E RC, To compute the coding rate reduction for a collection of such multi-channel 2D signals, we may flatten the tenor representation into a vector representation by concatenating the vector representation of each channel, i.e., we let
vec(z) = [vec(=[4])",....... vec(=(C]) E (CCHHXW)
(75)
Furthermore, to obtain shift invariance for coding rate reduction, we may generate a collection of translated versions of z (along two spatial dimensions). Stacking the vector representation for such translated copies as column vectors, we obtain
circ(=(1))
= =
E B[CCHXW))(BXWW)
(76)
We define translation invariant coding rate reduction for multi-channel 2D signals. Con- sider a collection m multi-channel 2D signals {z' E RRC*HxW m Compactly representing the data by Z Cxxx xm where the i-th slice on the last dimension is 21, we denote
circ( Z [circ(="), circ(="")
RR XCxHXx))x(XX (HX xm)
(77)
21

---

Under review as a conference paper at ICLR 2021
Then, define
A Reire ZIII)=
AR(iic 2), II)
log det
[I circ( circ( 2)¹
HW
2HW
Ni
log det [+aa--ird( III circ( Z)"*
(78)
2HW
j=1
CHW where a mHW? mc aj = U(TP HHW?
CHW
tr LI') and II is augmented
TT y2 7/
membership matrix in an obvious way.
By following an analogous argument as the ID case, one can show that ReduNet for multi-channel 2D signals naturally gives rise to the multi-channel 2D circulant convolution operations. We omit the details, and focus on the construction of ReduNet in the frequency domain.
C.2 FAST COMPUTATION IN SPECTRAL DOMAIN
Doubly block circulant matrix and 2D-DFT. Similar to the case of circulant matrices for ID signals, all doubly block circulant matrices share the same set of eigenvectors, and these eigenvectors form unitary matrix given by
FH Fw (C(TX))((XX))
(79)
where @ denotes the Kronecker product and FH, Fw are defined in (38).
Analogous Fact 4, F defines 2D-DFT follows.
Fact 8 (2D-DFT as matrix-vector multiplication) The 2D-DFT of a signal & E Hx can be computed as
vec(DFT(z)) -ec((z) E c(HHwW),
(80)
where
H- W-1
D=
Σ
Σ
2(h, w)
p-h a-w wi
VH.
h=0
w=D
v(p.g) --. 10,.... ... W-
-1. 1}. (81)
The 2D-IDFT of a signal v e CH can be computed as
vec(IDFT(e)) = Fj vec(1:)
E (((x)))
(82)
where
H-1W-1
(h,
u(p, 9) wH wi
VH. W
P=U 0=0
v(h, w) (O..... H - (O.....--111 x (O...., W - -1.. (83)
Analogous to Fact 9, F relates (z) and circ(z) follows.
Fact 9 (2D-DFT are eigenvalues of the doubly block circulant matrix) Given signal HH xW we have
F circ(z)) F" ==iaa(vee(DF((()) or circ(z) = F (DFg(ve) F. (84)
Doubly block circulant matrix and 2D-DFT for multi-channel signals.. We now consider multi- channel 2D signals z E Xx Let (FT(z) CCxNXW be matrix where the e-th slice the first dimension is the DFT of the corresponding signal x fc.. That is, DFT(())cc = (= e ( xW
We use DFT(2)(p, q) CC to denote slicing of z the frequency dimensions.
22

---

Under review as a conference paper at ICLR 2021
By using Fact 9, circ(z) and (#) are related follows:
F digg( F
circ(2)= F" diag(ve(((DFT(((()))) F
F
(iag(vec( DFFT (=())
F.. (85)
F"
dlag(vec(DFF((2((1))
Similar to the ID case, this relation can be leveraged to produce a fast implementation of ReduNet in the spectral domain.
eranslation-invariia ReduNet in the Spectral Domain. 2D signals Z XRO xm we denote
Given collection of multi-channel
DFT g) RCCCXXx and (p. E RCXCXHx given by
E cxm
(86)
We introduce the notations E(p.g)
E(p,g) = a [I (P. DFT (FT (p.1)) = oj a DFT (p. II DFT (p,, COO.
9) ECOxC
(87)
(88)
In above, e) (resp., (p. is the (p. 9)-th slice of E (resp.. C³) on the last dimensions. Then, the gradient of A Raire (Z, with respect to Z can be calculated by the following result.
Theorem C.1 (Computing multi-channel 2D convolutions E and C*) Let U CCXXXxXx and W E CX xm = =1...., , be given by
Ú(p.4) -((p.q) DFT( 9). (p,9) = (p.)))) OFT(Z)(2) q), j= j=1....,, for each (p,9) E {0, ..... 11 - t0...., . W 1}. Then, we have
(89)
(90)
Olog det(I + a: circi 2 circ()))rc((2))
IDFT(U),
(91)
2HW
az
0 (7g log det(1 + aa circ Z circ
% IDFT(W
(92)
2HW
0z
This result shows that the calculation of the derivatives for the 2D case analogous to that of the 1D case. Therefore, the construction of the ReduNet for 2D translation invariance can be performed using Algorithm with straightforward extensions.
23

---

Under review as a conference paper at ICLR 2021
D IMPLEMENTATION DETAILS AND ADDITIONAL EXPERIMENTS
Code for reproducing the results in this work will be made publicty available with the publication of this paper. Disclaimer: in this work we do not particularly optimize any of the hyper parameters, such the number initial channels, kernel sizes, and learning rate etc., for the best performance. The choices are mostly for convenience and just minimally adequate to verify the concept, due to limited computational resource.
D.1 ADDITIONAL EXPERIMENTS ON LEARNING MIXTURE OF GAUSSIANS IN 9 AND @
We provide the cosine similarity results for the experiments described in Figure 2. The results are shown in Figure 4. We can observe that the network can map the data points orthogonal subspaces.
(a) Xuain
(b) Zeain
(c) X
(d) Zrest
79
79
790
700
X
(1) Zumin
(g)
Xiest
(h) Ziest
Figure 4: Cosine similarity (absolute value) for 2D and 3D Mixture of Gaussians. Lighter color implies samples are more orthogonal.
Additional experiments on Sl and S We also provide additional experiments on learning mixture of Gaussians in S! and S Figure 5. We can observe similar behavior of the proposed ReduNet: the network map data points from different classes orthogonal subspaces.
Additional experiments on S! with more than classes. We try to apply ReduNet to learn mixture of Gaussian distributions on S² with the number of class is larger than 2. Notice that these are the cases to which the existing theory about MCR² (Yu et al., 2020) no longer applies. These exper- iments suggest that the MCR² still promotes between-class discriminativeness with so constructed ReduNet. In particular, the case the left of Figure 6 indicates that the ReduNet has "merged" two linearly correlated clusters into one on the same line. This consistent with the objective of rate reduction group data linear subspaces.
D.2 EXPERIMENTS ON UCI DATASETS
We evaluate the proposed ReduNet on some real datasets, namely the two UCI tasks (Dua Graff, 2017): iris and mice. There are 3 classes in iris dataset and the number of features is 4. For mice dataset, there are classes and the number of features is 82. We randomly select 70% data as the training data, and use the rest for evaluation. The results summarized in Table 1. We compare our method with logistic regression, SVM, and random forest, and we use the implementations by sklearn (Pedregosa et al., 2011). From Table 1, we find that the forward-constrie able to achieve comparable performance with classic methods such as logistic regression, SVM. and random forest.
ReduNet is
24

---

Under review as a conference paper at ICLR 2021
100 M0 60
Layers
X (2D) (left: scatter plot; right: co- (b) (2D) (left: scatter plot; right: co- sine similarity visualization)
sine similarity visualization)
(c) Loss
Laves
Layers
(d) (3D) (left: scatter plot; right: (e) (3D) (left: scatter plot; right: sine similarity visualization)
sine similarity visualization)
Loss
Figure 5: Learning mixture of Gaussians in St and S². (Top) For 31, we σ 02 =0.1; (Bottom) For S², we set 0 = 03 0.1.
1.3
1.0
1.
1.
0.5
0.
05
1.0
0.1 0.5 10
(a) 3 classes. (Left) X; (Right) Z
(b) 6 classes. (Left) X; (Right) Z
Figure 6: Learning mixture of Gaussian distributions with more than classes. For both cases, use step size = 0.5 and precision = O.1. For (a), we set iteration I. = 2, 500; for (b), we set iteration 4, 000.
D.3 ADDITIONAL EXPERIMENTS ON LEARNING SHIFT INVARIANT FEATURES
We provide additional experiments for Learning Shift Invariant Features in $3. The code for sam- pling from (t) sin(f) + and (t) sign(sin(t)) + e described in Algorithm 2, and the pseudocode for sampling from classes {hr, h2) described as follows, we sample training and test signals using the same procedure.
to rр rancom. uniform (Low=0, high=10+np.pp size=samples)
x = mp. (t0, 20+2+np.pi, time).
noisel np. www.daadd....a..... (0, 0.1, si (samples, time))
x1 np.sin (x) noisel
noise2 np. www.aaannooaaa..... (0, 0.1, size- (samples, time) )
x2 sp.sign (np. (in noise2
data = np.vstack ( (IX1, x21)
labels hstask ( [npp. ones (samples) +1,
np. ones (samples) x2]) asstype (np int
We also provide cosine similarities between samples in Figure 8, We visualize the cosine similarities
for the input Xurin Xest as well as the learned representations Zusin- Zust- The cosine similarity between sample pairs selected from different classes shown in Figure 9. We observe that the original data not orthogonal w.r.t. different classes, and the the ReduNet is able to learn discriminative (orthogonal) representations.
25

---

Under review as a conference paper at ICLR 2021
Table I: Performance (Accuracy) on iris and mice the UCI datasets.
REDUNET
LOGISTIC REGRESSION
SVM
RANDOM FOREST
IRIS
0.978
0.933 0.855
0.933 0.975
0.978
MICE
0.972
0.985
Algorithm 2 Pseudocode for sampling signals from 1D functions
Input: Number of samples m, number of classes k, number of features n, function {Aq....,,14 1/3
I: for = 1.2..... k do
2: for 1, ................................ m do
3:
to ~ Uniform [0, 10x); t (fo. tn + 2% /n. to (2m/n) 2, to + (2m/n) (trr/nn....... 3o + (2m/n) (m- 1)];
4:
5:
x; = ht) + # broadcast over vector t;
6:
end for
7: X; 23. x;
8: end for
9: X [X, X2, Xx);
10: shuffle X.
Output: outputs X.
D.4 ADDITIONAL EXPERIMENTS ON LEARNING ROTATIONAL INVARIANCE ON MNIST
We provide additional experiments for learning rotational invariance on MNIST in $3. Examples of rotated images are shown in Figure 12. We compare the accuracy (both the original test data and the shifted test data) of the ReduNet (without considering invariance) and the shift invariant ReduNet. For ReduNet (without considering invariance), we use the same training dataset as the shift invariant ReduNet, we set iteration L 3, 500, step size = 0.5, and precision e = 0.1. The results summarized in Table 2. With the invariant design, we can from Table 2 that the shift invariant ReduNet achieves better performance in terms of invariance on the MNIST binary classification task.
We also provide cosine similarities between samples in Figure 10. We visualize the cosine similari- ties for the input Ximin; Xest as well as the learned representations Zurin Ziea- The cosine similarity between sample pairs selected from different classes are shown in Figure 11. We observe that the constructed ReduNet is able to learn discriminative (orthogonal) and invariant representations for MNIST digits.
Table 2: Comparing network performance on learning rotational-invarian representations on MNIST.
REDUNET
REDUNET (SHIFT-INVARIAT)
AcC (ORIGINAL TEST DATA)
0.983
0.996
ACC (TEST DATA WITH ALL POSSIBLE SHIFTS)
0.707
0.993
D.5 EXPERIMENTS ON LEARNING 2D TRANSLATION INVARIANCE ON MNIST
In this part, we provide experimental results for verifying the invariance property of ReduNet under
2D translations. We construct 1). ReduNet (without considering invariance) and 2). 2D translation- invariant ReduNet for classifying digit '0' and digit 'I' on MNIST dataset. We use m = 1, 000 samples (500 samples from each class) for training the models, and use another 500 samples (250 samples from each class) for evaluation. To evaluate the 2D translational invariance, for each test image Viest E IR. HW we consider all translation augmentations of the test image with a stride=7.
More specifically, for the MNIST dataset, we have H = W 28. So for each image, the total number of all cyclic translation augmentations (with stride=7) is 4 4 = 16. Examples of translated images shown in Figure 13. Notice that such translations are considerably larger than normally considered the literature since we consider invariance to the entire group of cyclic translations on the H x W grid torus. See Figure 13 for some representative test samples.
26

---

Under review as a conference paper at ICLR 2021
1.5
1,3
1.0
0.5
0.5-
0.0
0.0
0.5
0.5
-1.5
-1.3
31
70
Radions, Bo.tu + 2s]
Radions, (oo.f 26]
Figure 7: Visualization of signals in ID. Blue dots represent the sampled signal used for training with dimension n 150. Red curves represent the underlying ID function (noiseless). (Leff) One sample from class 1; (Right) One sample from class 2.
X
(b) Zezin
(c) X
(d) Z
Figure 8: Cosine similarity (absolute value) of training/test data well as training/test representa- tions for learning ID functions.
For ReduNet (without considering translation invariance), set iteration L 2, 000, step size
= 0.1, and precision = 0.1. For translation-invan invariant ReduNet, we set L = 2, 000, step size 0.1, number of channels C
1 = 0.5, precision
and kernel size is set as 3 x 3. We summarize the results in Table 3. Similar to the 1D rotational results on the MNIST dataset, the translation-invarial ReduNet achieves better performance under translations compared with the RedeNet without considering invariance. The accuracy drop of the translation-invarian ReduNet is much less than the one of ReduNet without invariance design.
Table Comparing network performance on learning translation invariant representations on MNIST.
REDUNET
REDUNET (TRANSLATION-NNVAAAAAT))
ACC (ORiGINAL TEST DATA)
0.980
0.975 0.540
ACC (ToST DATA POSSIBLE SHIFTS)
0.909
27

---

Under review as a conference paper at ICLR 2021
Cannt
Count
Count
022
60
02
Similarity
Similarity
Samalariy
Sumilarit
(a) X (train) (tet)))
(b) (ttrrin)) X (test)
(ttrii))) X2(test)
(d) (tttrain)) (
R.B.B.E F.F.C.
Count
Count
Counte
Comes
14
62
81 Similarity
8.1
05
Similarity
Sanilarit
Similarity
(e) (train) vs. Zz(test)
(1 Zu(trinn) vs (tes)
( vs Zz(tes)
(h) (trrnin)) vs Z (test)
Figure 9: Histogram of cosine similarity between pairs sampled from different classes for learning ID function. The histogram of cosine similarity between training data X as well as representations Ze vs. testing (shifted) data X as well (shifted) representations Ze' where we let denote the class index and + c'
100
200
(a) X
(b) Z
(c)
X lest
(d) Z
Figure 10: Cosine similarity (absolute value) of training/test data well traning/test representa- tions for learning rotational invariant representations on MNIST.
Count
Count
Count
Count
Sumilarity
Samilarity
Similarity
Sinilariyy
(a) X (train) vs. Xattest)
(b) X2 vs X (test)
(train) xattest)
(d) ((rani) vs X (test)
Connt
Count
Conte
Courre:
635
62
62
03 02
81
40
600
014
000 05
13
600
62
03
04
060
25
Similarity
Samilarity
Simi arity
Simillrity
(e) (tmmin) (zstes)
( Z2tiiin)) vs (tets))
(tmin) (2ess))
(h) (2ttiinn)
Z (lest)
Figure II: Histogram cosine similarity between pairs sampled from different classes for learning rotational invariant representations MNIST. The histogram of cosine similarity between training data X. as well as representations Z, vs. testing (shifted) data X as well as (shifted) representa- tions Zei where let e denote the class index and o c'
28

---

Under review as a conference paper at ICLR 2021
Figure 12: Examples rotated images of MNIST digits for testing rotation invariance, each rotated
by 18 (Left) digit '0', (Right) digit '1'.
c
o
co
oo
co
Figure 13: Examples of translated images of MNIST digits (with stride=7) for testing cyclic trans- lation invariance of the ReduNet. (Left) digit '0'. (Right) digit '1'.
29


Reviews:
[{"review_id": "s8-yFQbmGr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary\nThis paper proposes a theoretical understanding of neural architecture using the  principle of rate reduction. Yu et.al 2020 and the derived optimization steps naturally leads to operations such as network layers and identity residual. By enforcing shift invariant, it can also lead to convolutional operation. The network can be constructed with a forward propagation fasion, which conserves good discriminative ability. \n\n#### Novelty\nTheorectical guidance of network design is one of the key direction in representation learning. \nThe paper proposes a novel perspective (rate reduction) in network construction that generalized to the design of networks such as resnet and resnext. However, there are a bunch or other networks such as denseNet, non-local network etc., which are also performing well in practice and designed with huerestics of larger context and better gradient propagation, will the author also include these representations within the objective of rate reduction? \n\nOr does the generation process from rate reduction (compact discriminative representation) come with additional guidance of what network, or answer the question in introduction, what is the object is optimal for network design, which could show to be effective on multiple tasks. \n\nI think the major issue of current result is that we can see the objective explain  that the set up of networks (resNet) seeks a compact representation, but the author has not shown strong experiments that their yielded alternatives by optimizing the objective (rate reduction) has positive relation with the network generalization. Is higher rate reduction leads network with better performance on multiple tasks ? \n\nLast, it is obvious that shift invariance leads to convolution, which is effective for classification of 2D objects. However, in realistic senario, we may seem equivalent disentangled representation rather  than invariance, is it possible for the objective leads to convolution without explicit inducing shift invariance ?  \n\n#### Writing and reference\n\nThe writing is good and easy to follow, checked few derivatives which are correct. I think the paper could also related to optimization inspired network design, e.g. Optimization Algorithm Inspired Deep Neural Network Structure Design, which delivers another perspective. \n\n\nIn general, I think the objective is novel, but not generalized enough to explain lots of high performance networks yet. However more exploration of theoretical study should be encouraged.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lfZzHF5AlB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper formulates an iterative process of deriving encoding of data into feature space as a deep model, called ReduNet, where each layer corresponds to iteration of the optimisation process the feature space according to the MCR^2 principle.  The MCR^2 optimisation maps points of different classes into separate subspaces, with volume of each subspace being minimized while the volume of the entire space is maximized.   It is analogous to pushing like things together and unlike things apart.  The novelty of the paper is in that formulation of the feature optimisation is baked-in into a deep architecture. \n\nMCR^2 principle seems like a sensible approach to learning, especially given that embedding algorithms (such as face encoding) use it already.  It’s nice to see some rigorous mathematical treatment on this.  However, I get confused pretty early on by the notations.  If f(x,\\theta)\\in \\mathcal{R}^k and z=f(x)\\in \\mathcal{R}^n….then since y=h(z), then f(x,\\theta)=h(f(x))…and so f(x,\\delta) and f(x) are two different functions.  Yet later in the text z=f(x,\\theta).  And from then on, including equation 11, f(x,\\delta)=\\psi^L(z_L+\\etag(z_{L-1},\\theta_{L-1})…which would make it seem f(x,\\theta)\\in \\mathca{R}^n.  And what is g(z_l,\\theta_1)?  Equation 8 tells us what g(z_l,\\theta_1) must approximate…but what is it exactly?   Is that a neural network, or some model, with parameters \\theta_l?  Or is Equation 8 a definition of g(z_l,\\theta_l)…in which case what is \\theta_l?  I don’t think the math is necessarily wrong…just notation is confusing and definitions changing/not consistent.\n\nI have also questions about equation 11, where number of layers is equivalent to iterations while maximizing MCR^2 and the width of each layer corresponds to m, the training points in the dataset.  So, in order to do a mapping of an input x, we need to perform L iterative steps using the entire m points every time?  Isn’t that equivalent to doing a massive learning process, using the entire dataset, for each mapping?  How computationally costly is that?  I also don’t quite understand how \\psi^l(z_1,\\theata_1) works - how does \\theta_l change over iterations?  Experimental section is not helping me with this, since it’s stated that E, C^j are computed for each layer…but there are no details on what \\theta_l is and how g(z_1,\\theta_1) is evaluated.  And if f(x,\\theta)=z^L…then how do we get classification from that?  Is it just based on definition of \\hat{\\pi}^j(z_l) from page 4?\n\nFinally, I am not sure if the result of obtaining a convnet architecture in ReduNet when translation invariance constraint is added the embedding is all that surprising.  Isn't it somewhat obvious that if each layer of ReduNet is invariant in some way, then the entire network is invariant?  It feels like that what we are learning here is not that in order to have translation-invariant mapping we must have a convent...but rather that we can obtain a translation invariant deep architecture with translation invariant layers. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "QXKDL_JOG1W", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a deep network approach using the principle of rate reduction as a loss under a gradient ascent approach, avoiding traditional backpropagation. Besides, the work attempts to interpret the proposed framework from both geometrical and statistical views. Then, shift-invariant properties are discussed. The innovative method allows the inclusion of a new layer structure named ReduNet, which could benefit the deep learning community. Though the experiments are not challenging concerning the studied databases, the authors aim to probe the concept without a complete implementation tuning. Overall, the paper is illustrative enough regarding the mathematical foundation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PreuNpBJaBq", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In their submission the authors discuss an alternative learning rule to backpropagation called “maximal coding rate reduction” that was introduced recently in Yu et a. 2020. As far as I could tell, as a non-expert, maximizing the coding rate reduction objective encourages inputs from different classes to be maximally incoherent with respect to one another (spanning the largest possible volume) while inputs from the same class should be highly correlated.\n\nIn the present submission, the authors show that gradient ascent on the coding rate reduction naturally takes the form of a “neural network” with a particular residual network architecture that they term ReduNet. The authors argue that sending an input through the layers of ReduNet naturally leads to representations that (approximately) maximize the coding rate. The authors continue to show that when the representation is required to be group-equivariant with respect to shifts, a convolutional structure naturally emerges. This allows the authors to compute the update using layerwise fourier transformations. Finally, the authors show that on several example tasks ReduNet leads to outputs that have a large coding rate with no parameters learned via backpropagation.\n\nThere were several aspects of this submission that I liked a lot. I think the construction seems interesting and the rate reduction metric seems like a reasonable thing to optimize. I found the relationship of coding rate maximization to ReduNet to be quite clever and the experiments seemed to suggest that the approximations employed in the paper (e.g. the estimated membership in eqn 9) did not spoil the mapping.\n\nHaving said this, I don’t know that I agree with the authors’ interpretation of their results and I believe they might be somewhat overstated -- of course I am happy to be corrected if I am incorrect in my assessment.\n\n1) My primary concern is the claim that the maximum rate reduction principle gives first-principles insight into convolutional networks. The authors show that a particular convolutional architecture, namely ReduNet, approximates projected gradient ascent on the MCR2 metric. However, it is not at all clear to me that standard convolutional networks or residual network architectures are well-described by ReduNet. In fact, it seems that the very particular structure of ReduNet has a number of features that are at odds with standard convolutional networks: nonlinearity only enters into ReduNet via the approximate membership (which enters via a softmax-like function) and outputs of each layer are projected onto the (n-1)-sphere. \n\n2) Since the relationship between ReduNet and commonplace CNNs seems tenuous to me, it seems there is a significant burden on the authors to probe this question empirically. For example, do CNNs trained via backpropagation lead to architectures that resemble ReduNet? Unfortunately, as far as I could tell, the authors did not include experiments of this type.\n\n3) If the authors are proposing ReduNet as an alternative to modern CNNs, it would be nice to see how ReduNet performs on some common tasks with well-established baselines (possibly with some fine-tuning step). However, as far as I could tell most of the experiments focused on verifying the properties of ReduNet. Note that I do not think one needs to achieve state-of-the-art performance here, but it would be nice to see how ReduNet fairs since this will probably affect its impact.\n\nA few more minor points:\n\n1) I may be missing something, but given the construction of ReduNet, I feel as though the emergence of a convolutional structure subject to translation invariance is not terribly surprising. Indeed I feel like this result has high overlap with Cohen and Welling [1]. This is not necessarily a criticism of the result per-se, but I think the phrasing could do a bit more to note this connection.\n\n2) It was not obvious to me why Z had to be constrained to S^{n-1}. Can the authors provide some intuition here?\n\n3) The authors note that non-linearity enters the network via the estimated membership. However, as far as I could tell, the estimated membership is only used for test points. Does this imply that the network is linear when the membership is known?\n\n[1] Cohen, T. and Welling M. “Group Equivariant Convolutional Networks” JMLR 2016\n\nUpdate: After discussion with the authors, I am inclined to lower my score. While I find the architecture proposed by the authors to be interesting, I do not think they have done enough to motivate the connection with neural networks. I find this especially troubling since the language used by the authors continues to imply that the connection is obvious. I would encourage the authors to look into the literature on scattering networks (e.g. https://arxiv.org/abs/1203.1513) for another approach to explaining networks from first principles that, I think, does a better job of making the connection to realistic neural network architectures. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6HSxwFexCRm", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a network derived from maximizing of rate reduction, known as the MCR^2 principle, where  all parameters are explicitly constructed layer by layer in a forward propagation fashion. Compared with exiting work by Yu et al. (2020), the proposed work is more like a \"white box\" that each layer is more interpretable.  Results showed the proposed network can learn a good discriminative deep representation without any back propagation training. The derivation of the network also suggests that the network is more efficient to learn and construct in the spectral domain.\n\nOverall, the proposed work looks reasonable. The paper is well-structured. The derivation and experiments seem convincing.  Unfortunately, the proposed work is out of the reviewer's expertise and therefore it is hard to provide valuable comments.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received borderline scores, which makes for a difficult recommendation. Unfortunately, two of the reviews were too short and thus were of limited use in forming a recommendation. That includes the high-scoring one, which did not adequately substantiate its score.

There is much to admire in this submission. Reviewers appreciated the originality of this research, linking rate reduction optimization to deep network architectures:
* R1: "The paper proposes a novel perspective"
* R4: "The novelty of the paper is in that formulation of the feature optimisation is baked-in into a deep architecture"
* R5: " I think the construction seems interesting and the rate reduction metric seems like a reasonable thing to optimize. I found the relationship of coding rate maximization to ReduNet to be quite clever"
* R3 (short): "The innovative method allows the inclusion of a new layer structure named ReduNet"

Reviewers also applauded the paper's clarity, including R4 who raised their score to 6 based on satisfying clarity revisions from the authors:
* R1: "The writing is good and easy to follow"
* R4 post-discussion: "Clarity is not an issues anymore - additional explanations provided by the authors and one more careful reading of the paper helped in understanding of all the aspects of the model"
* R2 (short): "The paper is well-structured."

However, there were some core questions around how well the main significance claims of the paper are supported. The most in-depth discussion on these topics is in the detailed thread with R5. In that thread there are many points discussed, but the two issues seem to be:
1. whether the connection between ReduNet and standard neural net architectures is sufficiently substantiated so as to constitute an explanation for behaviors of those standard architectures, like CNNs; and
2. whether the emergence of ReduNet's group invariance/equivariance is surprising or qualitatively new.

The first is much more central. On the first issue, R5 writes in summary:
"Fundamentally I think the authors propose a hypothesis: that ReduNets explain DL models. However, the authors do not take meaningful steps towards validating this hypothesis. [...] I would contrast this with, for example, the scattering networks paper (https://arxiv.org/abs/1203.1513) which did an exceptional job of arguing for an ab initio explanation of convolutional networks."

I find R5's perspective on this point to be compelling, in that the paper currently doesn't do enough to justify these main claims, either through drawing precise nontrivial mathematical connections or through experimental validation. (The thread has a much more detailed and nuanced discussion.)

The second issue is not quite as central to the significance of the paper, but it was noted by multiple reviewers:
* R5: "I may be missing something, but given the construction of ReduNet, I feel as though the emergence of a convolutional structure subject to translation invariance is not terribly surprising."
* R4: "Finally, I am not sure if the result of obtaining a convnet architecture in ReduNet when translation invariance constraint is added the embedding is all that surprising."
* R4 post-discussion: "Reading the exchange between the authors and R5 I am still not fully convinced that translation invariance property is all that surprising, but for me that's not a reason to reject."

At the least, the paper as written hasn't yet convinced some readers (myself included) on these claims.

As I mentioned at the start, this paper is borderline, but because I am largely aligned with R5's perspectives, I think this paper does not quite pass the bar for acceptance. I recommend a rejection, but I look forward to seeing a strengthened version of this work in the future. I hope the feedback here has been useful to bringing about that stronger version.
Decision: Reject