TREC: Transient Redundancy Elimination-based Convolution
Authors: Jiawei Guan
Feng Zhang
Jiesong Liu
Hsin-Hsuan Sung
Ruofan Wu
Xiaoyong Du
Xipeng Shen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Transient redundancy
convolution acceleration
back-propagation

Abstract: The intensive computations in convolutional neural networks (CNNs) pose challenges for resource-constrained devices; eliminating redundant computations from convolution is essential. This paper gives a principled method to detect and avoid transient redundancy, a type of redundancy existing in input data or activation maps and hence changing across inferences. By introducing a new form of convolution (TREC), this new method makes transient redundancy detection and avoidance an inherent part of the CNN architecture, and the determination of the best configurations for redundancy elimination part of CNN backward propagation. We provide a rigorous proof of the robustness and convergence of TREC-equipped CNNs. TREC removes over 96% computations and achieves 3.51x average speedups on microcontrollers with minimal (about 0.7%) accuracy loss.

TREC: Transient Redundancy Elimination-based Convolution
Jiawei Guan", Feng Zhang", Jiesong Liu", Hsin-Hsuan Sung", Ruofan Wu', Xiaoyong Du", Xipeng Shen
Key Laboratory of Data Engineering and Knowledge Engineering (MOE), and School of Information, Renmin University of China "Computer Science Department, North Carolina State University
guanjw @ ruc.edeee www.ed..ccn fengzhang @ruc.edu.co liujiesong @ ruc.edu.cn, hsung2 ncsu.edu, ruofanwu@ruc enu.en, duyong @ edu.en, xshen5 @ncsu.edu
Abstract
The intensive computations in convolutional neural networks (CNNs) pose chal- lenges for snsource-constraiigg devices; eliminating redundant computations from convolution is essential. This paper gives principled method to detect and avoid transient redundancy, a type of redundancy existing in input data or activation maps and hence changing across inferences. By introducing (TREC), this new method makes transient redundancy detection and avoidance an inherent part of the CNN architecture, and the determination of the best configura- tions for redundancy elimination part of CNN backward propagation. We provide a rigorous proof of the robustness and convergence of TREC-equipped CNNs. TREC removes over 96% computations and achieves 3.51 x average speedups on microcontrollers with minimal (about 0.7%) accuracy loss.
form of convolution
Introduction
Convolutional Neural Networks (CNNs) are computation intensive, making their deployment on resource-constrained devices (e-g., Microcontrollers equipped with 2MB memory) challenging. Removing computation redundancy in convolutions is hence an important way to speed up CNN inferences.
Depending on where the redundancy comes from, redundancy in CNN can be classified into lasting redundancy and transient redundancy. Lasting redundancy arises from CNN parameters. As the parameters typically stay unchanged after CNN is deployed for inference, such redundancy can be detected and removed through offline methods (e.g., DNN pruning 9
35 and quantization [15] 17 26 33)). Transient redundancy, on the other hand, arises from input data or activation maps, manifesting as similar tiles within an image or an activation map. Unlike lasting redundancy, transient redundancy has to be detected and removed in every inference, elusive to offline methods.
22 23
34
Although transient redundancy has been observed in images 25 and videos 16
36
37
38),
much less than to lasting redundancy. Prior studies have treated transient redundancy in an ad-hoc manner. Deep Reuse [25], for instance, diverts, before a convolution, the input images or activation maps from the DNN pipeline randomized (to avoid bias) online clustering component to detect the contained redundancy, and then redirects the clustering results back to the DNN. Such ad-hoc treatments work well sometimes on some data, but perform badly in other times (e.g., over 5% accuracy fluctuations in different runs). The reason is the lack of understanding to some fundamental aspects of transient redundancy. Examples include
understanding
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(1) How to reach the optimal setting to minimize the accuracy loss caused by redundancy elimination while maximizing the eliminated redundancy?
(2) How to ensure stable robust inference performance of transient redundancy elimination across runs?
(3) How to minimize the interference imposed by the transient redundancy elimination to the result the converged training CNN?
This paper proposes a principled way to detect and avoid transient redundancy for CNN inference. By introducing new CNN operator named TREC, it fuses the detection and avoidance of transient redundancy into CNN, making them part of its inherent architecture. With the systematic design, finding the best configuration maximize redundancy-elimin elimiintiioo benefits becomes part of the CNN training process, seamlessly integrated as part of the backward propagation. Based on the design, we are able to investigate transient redundancy elimination for CNN in a principled way, providing a rigorous proof of the robustness and convergence for TREC, and an intuitive comparative analysis of the computational complexity.
TREC is compatible with both forward and backward propagations, enabling a plug-and-play replace- ment for convolutional layers in mainstream CNNs without any additional effort. Through novel LSH pack-propagation mechanism, the optimal parameters of TREC are automatically determined; they remain deterministic, clearing the threat robust performance that hampers practical adoptions of the existing solutions.
We evaluate TREC diverse popular CNNs, CifarNet (1. SqueezeNet (with and without complex bypass) 14]. ZfNet [31, and ResNet-34 on a microcontroller (MCU). In particular, ZfNet is preprocessed with channel pruning meet the strict memory constraints of MCU. Experiments show that by removing 96.25% transient redundancy, TREC achieves an average of 4.40 speedup compared to the conventional convolution operator. When applied the full neural networks, TREC achieves an average of 3.51 speedup with virtually no accuracy loss.
2 Related Work
Extensive studies have been conducted to eliminate the lasting redundancy CNNs. Factorization 5 19, 21 29 (3), pruning [9] [0] 13 22,
23 34 [35], and quantization [75] 26, 33 techniques are some of the important methods. They exploit the redundancy contained in the CNN parameters.
Transient redundancy elimination is complementary to lasting redundancy elimination, dedicated to detecting and removing redundancy from input images actívation maps. It is more challenging to do as it has to happen during online inference. Such redundancy can be further categorized into temporal redundancy (c.g., similarities between adjacent video frames) and spatial redundancy (e.g.. similar tiles within an image). Prior studies [1] 18 30
36 37] have paid attentions mostly to temporal similarities between adjacent frames. Deep Reuse 25 is the main method proposed before for detecting and eliminating spatial redundancy within an image for CNN. It takes place as extra operations outside CNN, using Docality-Sensitie Hashing (LSH) with some random hashing vectors for online data clustering. Such an ad-hoc treatment causes important uncertainty about the impact of the clustering errors on the CNN performance. Experimental results show that Deep Reuse causes significant (e.g., 5%) fluctuations on CNN accuracy (detailed in Section
3 TREC
In this section, we elaborate on the design of our transient redundancy elimination-basee convolution. First, present the architecture of TREC and how it operates in the forward pass. Then, delve into the key challenge in the creation of TREC, how to make paok-propngation function on TREC-based CNNs.
3.1 Basic TREC Architecture
The basic architecture of our proposed TREC shown in Figure TREC comprises three components in series on top of Im2col+ GGMM based convolution: LSH-based clustering that reduces the size of the input the conversion, matrix multiplication of weights and the compressed input, and a recovery step that restores results to the original GEMM output sizes.

---

LSH-based Clustering
Forward Backward
Hash
Bit
Cluster ID
W
Binary Mapping
0101
Bindec
10
0011
Mapping
Clustcring
Recovery
x
x
Y
Y
Binary Approximation
Bindec Conversion
Figure 1: Architecture design of TREC. "@" denotes matrix multiplication.
Recall that in Im2col+ based convolution, the input feature maps and filters are unfolded input matrix X and a weight matrix W, and then the convolution is materialized multiplication. At high level, TREC uses Locality- -Sessiivee Hashing (LSH) to group vectors in the input matrix. It has four steps. First, it applies hash function matrix Hash to X. Second, performs a simple element-wise binary mapping to obtain bit matrix. Third, each row vector of the bit matrix converted decimal). These integer values indicate the cluster IDs of the neuron vectors in X. Fourth, the input matrix X reduces to X which is composed of the centroids of clusters. In this way, the size of input matrix is significantly reduced, lowering the computational complexity of the subsequent matrix multiplication. Finally, the recovery step, vectors in the same cluster reuse the computation results of the corresponding centroids to obtain the final result Y.
matrix
decimal value by bindec mapping (i.e., a mapping from binary to
3.2 Breaking the Back-Propagation Barriers for TREC
The key challenges for building a TREC-based CNN are two. The first is in making back poc-ppropagation work with TREC. It is challenging because of the discrete nature of the LSH-based clustering in TREC. The second is to understand the impact of TREC on the convergentability of CNN.
We address the first challenge in this section and address the second challenge in Section 4 At high level, our strategy consists of two key components. First, we replace the piecewise mappings in TREC with similar-shaped functions as binary approximation approaches. Second, bindec conversion algorithm to resolve the complexities in obtaining centroids. Before explaining them, we first give closer examination of the operations in the forward pass of the basic TREC, which will help the follow-up explanations.
propose
A Closer Look at Redundancy Elimination in the Forward Pass. Figure 2 iillustrates the redun- dancy elimination in the forward pass of the basic TREC. Specifically, let X R4x6 be an unfolded input matrix after Im2col. TREC first slices X into L groups vertically (L = 2 in Figure 2 Left), so each sub-matrix of size x 3. The slicing reduces vector length which can often allow the clustering to identify more similar vectors 24]] Applying the LSH clustering to each sub-matrix produces the centroid matrix X
LSH is chosen because as a lightweight online clustering method, it produces good clustering results without incurring excessive overhead. Figure shows more details of LSH clustering with an example. X, is the first sub-matrix of X in Figure Left. For each input vector in X1, it is hashed through the following function parameterized with a random vector e:
hx(x) = {
if u. >
(3.1)
if
v.
First, X1 is transformed into a projected matrix with H = 2 random hash vectors (i.c., 2 column vectors of the hash matrix). Second, the projected vectors mapped to bit vectors with 2 possibilitics, as defined by Eq. 3.I Third, the bindec rule converts each bit vector to an integer value, which can be used as the cluster ID of vector In this way, similar vectors have high chance of being mapped to the same cluster. Finally, each vector in X is computed using vectors with the same cluster ID. Note that in practice, H is much smaller than the length of neural vectors, so the overhead introduced by LSH low.
Binary Approximation. To solve the problem of discontinuity in binary mapping during back- propagation, we introduce binary approximation make it differentiable. The binary mapping handles the projected matrix in clement-wise manner, which acts as binary classification that sets
3

---

X
W
X
Hash Projected
Bit
Cluster ID
X1i
32
112
322
④
X
Y
X
Y
yf2
[
3
F1
[ 2
0-1
Binury
0
Bindec 0
3
K11
X21
322
1/2
y/2
2
0
5
2
Mapping
Mapping 3
① LSH
Recovery
Figure 2: Left: The illustration of redundancy elimination. matrix X, vectors in the same color belong to the same cluster. Right: An illustration of LSH. X1 is the first sub-matrix of X on the left.
elements greater than zero to one, and otherwise to zero. To that end, we employ a sigmoid function substitute of the binary mapping:
S(x) e-
(3.2)
where a denotes the slope and b denotes the abscissa value of the central point of the curve. The sigmoid function suits TREC because it 1) monotonic and bounded; 2) smooth and differentiable. Meanwhile, the sigmoid function offers a parameterized way to materialize the effects of binary mapping for TREC. The parameters a and in the sigmoid function are hyperparameters determined empirically. When setting them, the rationale worth mentioning is that the value of shall be large such that as few points as possible appear the mid-slope of the sigmoid function, which would allow positive and negative numbers to approach one and zero respectively. And the value of b shall shift the function slightly to the right, which would allow the value at x 0 to approach zero. The bit vectors can be then approximated by application of such sigmoid function to the projected matrix.
Bindec Conversion. Another step that impedes back propaaatiion for TREC is bindec mapping, that is, the rightmost step in the example Figure 2 which converts every binary vector into its corresponding integer value. To make this process differentiable, we design a transformation matrix as follows:
22-1111
24-1/2
2 1/2
E R Hx
(3.3)
2//1
2 /2
2 /1
20/1
20/2
2 20/2"
Eq. 3.3 shows that elements the same row of the transformation matrix have the same numerator, and elements in the column have the same denominator. Horizontally, the denominators increase from to 2 Vertically, the numerators are H2 ..... 21, 21,2% from top to bottom, which are the coefficients when converting binary number decimal.
Bit
Transformation (H x 2*) 2'/1 2//2 21 /2 /4
Quotient
Index
Average (Avg)
2 4/3
[o:0 o o
D
0 1/3
1/2
1/3 1/4
Gaussian
1
Divide N
150 0
X
2 4/3
0 0
0
010 1/3
4/3
00:0
000
1/3
Forward information
0
0 113
0
1
21 2'/4 20/1
1/4
Gaussian
T 0
Divide N
1 0
x
29/4
0 1/3
0 [ 11/3
Figure The overall idea of constructing the Aug matrix.
The overall idea of bindec conversion is shown in Figure which follows the example of Figure First, we add 1 to the rightmost column of the bit matrix. In this way. the range of the integers changes from [0, 2
to [1, 2 which is consistent with the denominators of the transformation matrix. The result matrix is then multiplied with the transformation matrix, which can be seen two steps: 1) multiply the bit vectors with the numerators of the transformation matrix's 's column vectors to obtain integer values; 2) divide the integer values by the denominators of the column vectors. As

---

result, in the quotient matrix, for row i where vector is located, Quotienti appears only at the position where the column number j equals z; 's cluster ID. For example, in Figure 33 the bit vector in the second row (i.e., row 1) is [0, 0). and the cluster ID is O. In row 1 of the quotient matrix, only column has 1, i.e., Quotienf1.0
The method can successfully do the mapping. But as ! increases, the dimension of the transformation matrix increases exponentially, resulting in huge memory waste. To ease the space and computation, we apply the above process only in the backward pass, while the forward pass still uses binary and bindec mappings. This means that the results of the forward pass such as cluster IDs, the number of vectors per cluster (denoted as No). and the number of clusters (denoted as C),, can be reused by back peekkk-rppgatonn.. Therefore, we can directly construct transformation matrix of size I x C, where each column represents known cluster ID that is derived from the forward calculation. As shown in the lower part of Figure the use of forward information can significantly avoid space waste.
Now, we can obtain an index matrix to indicate the vector-cluster relationship. We can do that by applying element-wise function to the quotient matrix, which gives 1 if the element is and otherwise. Such function is however not differentiable. To solve this problem, we introduce an impulse-like Gaussian function of the following form:
(x-1)2
G(z)= =
2n
(3.4)
is a symmetrical bell-shaped curve centered at = 1, with controlling its width. With a small the Gaussian function can be used to approximate the desired index matrix. Then, we divide the index matrix by the number of vectors per cluster Ne. and we obtain an average matrix denoted as Avg. Finally, the cluster centroids can be calculated follows:
Avg X.
(3.5)
For the example in Figure we get the cluster centroids as follows:
I
2
37
1 3
0
0
2
0
0
2
0 1
(3.6)
3
2
Parameter Setting, TREC uses Sigmoid and Gaussian functions to simulate the mappings. As mentioned, TREC needs the range of function parameters to meet certain conditions, such as using small a to narrow the width of the Gaussian function. However, fixing a a value is subject to gradient explosion, resulting
large gradient variance and convergence difficulties. Therefore, we propose a solution that dynamically sets a based on H.
We use Figure to illustrate the gradient explosion problem. The curves are of a Gaussian function with a 1 and its derivative. We can that the derivative function varies widely on both sides of 1, and its maximum and minimum values occur
Gaussian (G=0.1
Derivative of Gaussian
6
(0.9, 6.065)
4
2
>. 0
at x 1 a. The value range of the derivative func- tion increases as a increases. Therefore, manually setting a fixed a has a high chance of incurring a large gradient variance.
-2
4
(1.1, -6065)
4
1.2 1.4 x Figure 4: Gaussian function and its derivative
0.6 0.8
To address this problem, we first analyze the quotient matrix. According the rules of the transformation
with σ = 1.
matrix, the quotient matrix takes values in the range [ 22), and the difference is at least 1 2
Moreover, the ht vector has Quotienti, 1 when the cluster ID is equal to column j. Based on the observations, we avoid producing large gradients simply by ensuring
and k>
(3.7)
k. 2H
Consequently, the Gaussian function not only provides an ideal approximation of the index matrix, but also ensures the stability of the training under any H value.
5

---

4
Theoretical Analysis
In this section, we provide theoretical analysis of TREC in terms of robustness, convergence, and complexity. All proofs are available in the Appendix.
4.1 Robustness
Neural networks are sensitive to inputs 8 27 can misdirect the neural network and significantly decrease its classification accuracy. To prove that TREC does not impair the stability of the convolutional layer, we use the Lipschitz constant, which is commonly used to assess the robustness of neural networks, to upper bound the relationship between the input perturbation and output variation (28). In the following, we use || to denote the -x--norm of the matrix space m==x.
In practice, small perturbation of the input image
Definition 1. A function f: B x - = is called Lipschitz continuous if there exists a constant 0 such that
VX,Y "X,YER"XX ER"X", - - S L - 1l
(4.1)
The smallest L that makes the previous inequality true called the Lipschitz constant of f and can be denoted as L(f).
Suppose Cone: : XW is a conventional convolution operator, and TREC: : X-+ X-W is our proposed method. Recall the description of the Aeg matrix in Section 3.2 and Eq. 3.6; Σ, Avge, S satisfied for any column j. Combining Definition | with the above discussion, we have:
L(Conw) || L(TREC) = ||W @ Auy" 1| S ||
(4.2)
where denotes the Kronecker product. In summary, under the same network configuration, the Lipschitz constant of TREC is no larger than that of the conventional convolution. That is to say, TREC has the ability maintain the robustness of convolutional layers.
4.2 Convergence
In this section, we provide a theoretical analysis of the convergence of TREC-equipped CNNs. Ana- lyzing the convergence of the above CNNs directly is difficult, since the specific CNN architectures are unknown except for the convolutional layers. Instead, we address this problem by building a connection with stochastic gradient descent, and prove that the proposed method is guaranteed to converge under reasonable assumptions. In the following, we use ||æ||a to denote the L2-norm of the Hilbert space R.
We assume a CNN network with TREC layers and other layers. Without loss of generality, we use W = [Wi.... WR WR+T] 1h to denote the weights of all layers, and I! i HR] e R to denote the hash functions of all convolutional layers. In accordance with the method (2) we represent sample (or set of samples) as a random seed ć, and refer to the loss for a given (W, H. () as f(W, g). addition, given a dataset with n samples, we refer to the objective function F; TR. either F(W, H) = (W, H)E) or F(W, H) = : F.W,,,WW
Following the stochastic gradient descent, we define the parameter update rule at iteration as: WE+1 + W+- - au g(W,, Ex), Hef1 +- Hμ au q(W,, H.) where ag denotes the stepsize, g(W,, Ee) and q(W,, (e: represent the gradients of the loss function with respect to W₁ and Hy separately, which can be the stochastic gradients or the mean gradients of mini-batch:
(4.3)
Sw (We, Ex) Σ m4
V HuiEe)
(W,, Ha:
Hus WWWW,, Ex)
(4.4)
fwn, HusEe).
Now we summarize the key assumptions required to establish our results. Assumption 1 (Lipschitz-continnuuus objective gradients). The objective function F; F:BD - IR
continuously differentiable and the partial derivatives of F, namely, VFw Rdh - Rdh and
V Fn dd R are Lipschitz continous with Lipschitz constants 0, i.e.,
IV H) Fw (W, H)laa & L|IW W12, for all ( W) C R FF H) V (W, H s H| 17 for all (H, H. C R
(4.5)

---

Assumption ensuress that the partial derivatives of F do not change arbitrarily fast with respect to the parameters, thus well indicating how far move decrease To move forward, we denote the variances of o(W,, Hy; Ex) and ((Ws, Hy; [x) as:
Vea [h(We, Ex) = E., [[A, M& E+) -1 [WW,, Ex)ll) E {g.4).
(4.6)
Assumption 2 (First and second moment limits). The functionn and the stochastic gradient algorithm satisfy the following conditions:
(a) The sequence of iterations {(W,, Hx)} is contained in an open set over which F is bounded below by a scalar Fing-
(b) There exist scalars PG 2 p > O such that, for all & N.
VFw (We, (et1)" EE, W
V/W Hx)
(4.7a)
FFn "
[x)] μ FF Hx)) lo Hui [+]]][ |لم (W,, Hu)ll2,
(4.7b)
(4.7c)
[E,, (WW,, Hx: Ex]]ll> S pc]| FM (wx, Hx]l
(4.7d)
(c) There exist scalars M and My 0 such that, for all k E N, (e Hc) S M Mv VFw (W Hz) Ve, [WW,, Ex) S M + My F (W&, H
(4.8)
We first analyze the convergence with fixed stepsize and prove that the CNNs equipped with TREC can converge sub-linearly to the neighborhood of the critical points for the non-convex problem under the above assumptions.
Theorem 1 (Fixed stepsize). Assume that Assumptions 7 and 2 hold, and the fixed stepsize is
on a for all & E N satisfying 0 < ā á LMg Then, the everage-squares partial derivatives of F corresponding to the stochastic gradient iterations satisfy the following inequality for all K E N:
K
20LM
2(F
-
FWw H²)] (WF H+)1
(4.9)
K
P
Kua
Therefore, the optimal solution we can obtain is dominated by 26LM convergence with dimishing stepsize that meets the requirements in the study 2
Further, we also prove the
K lim
and lim K
o% <0.
(4.10)
Theorem (Dimishing stepsize). Assume that Assumptions and hold and the dimishing stepsize sequence {au} satisfies Eq. 4. 10 Then, with Ag == >
R
on (IVVF HOlE + IVF H7 1B)
2(F(W,, add
Pind
2LM
Σ
og
K K-000 0.
(4.11)
Remark 1. Theorem 2 has shown the decaying of gradients FW (Wa, Ha)ll and F[ even with noise when the stepsize is dimishing. This because the second condition Eq. 4.10 implies the right-hand side of Eq. 4.17 converge to fintt limit as K increases.
Hy)
Theorems I and 2 prove convergence the limit. Taking step forward, we study the theoretical bounds to understand the convergence of TREC-equipped CNNs in practical applications. According Eq. 4.9 and 4.I1 as long as the practical application satisfies Assumptions [nd we can obtain theoretical upper bound of the sum of squared gradients without considering the limit. The relevance of this theoretical upper bound to practical applications is reflected in the values of the constants
such as L, μ. .,, and the specific setting of the learning rate. From Eqs. 4.5 4.8 the constants L, M, and MG = M, + m.. which are greater than O, exist according to the 12-noom. Through experimental verification, we find that the constant is always greater than 0 during the training process and gradually converges to with time, satisfying the sufficient direction assumption. We present in Appendix B the trend of the constant μ.
7

---

4.3 Complexity
We show in Table intuitive comparative analysis of two major complexity metrics. The complexity of binary and bindec mappings are not taken into account because they are parameterless and insignificant compared with other computational overheads. For the parameter count, TREC exceeds the conventional convolution by a hash matrix of O(T. H) size, with trivial KB-level space occupancy. For the computation complexity, we define redundancy ratio: r of the input matrix to indicate the fraction of transient redundancy within input images or activation M Tr is satisfied, TREC can yield computational beneñtt. In practical
Ne/N as the size reduction
maps. As long as validation (Section 5.2). we notice that the reduction of transient redundancy of single convolutional layer reaches up to 96,,5, which brings confidence to the advantages of TREC.
Table 1: Parameter counts and FLOPs for conventional GEMM-basek convolution and TREC. The input and weight matrices unfolded by Im2col are of size N K and K x M. The hash matrix of TREC is of size L x H. N₂ denotes the number of clusters.
Parameters
FLOPS
Conventional
K- M
N K M
TREC
K- M + L.H
( +1 rd) N K M
Evaluation
5.1 Experimental Setup
Methodology, To demonstrate the efficacy of TREC on CNN inference acceleration, we first apply TREC to single convolutional layers to measure single-layer speedups and accuracy. Second, we apply TREC to the complete neural networks to measure end-to-end inference performance. Third, analyze the influence of different factors performance, including the dynamic setting of the Gaussian parameter, and the clustering configurations.
Platforms. As computation reduction is most needed on resource constrained devices, we fo- cus our evaluation on Microcontrollers (MCU). Specifically, all inferences are performed on an STM32F469NI MCU with 324KB SRAM and 2MB Flash, using the CMSIS-NN kernel optimized for Arm Cortex-M devices [20]. All trainings are performed using Py 1.10.1 (open-source software with BSD license) processor, 128GB of RAM, and an NVIDIA GeForce RTX A6000 GPU with 48 GB memory.
machine equipped with 20-core 3.60GHz Intel Core 17-12700K
Workloads. We evaluate TREC with five compact CNNs that fit MCU, CifarNet [1. ZiNet [1]. SqueezeNet with and without complex bypass [14. and ResNet- 34 [12. Most trainings and inferences
are performed on CIFAR- 10, while for ResNet, we use the downsampled ImageNet (3] with 64 x4 resolution (since the original large images cause ResNet-34 to run out of MCU memory). All networks are optimized by SGD. The learning rate starts from 0.001 and decreases by 0.1 every 15 epochs. The batch size, weight decay, and momentum are set to 256, 0.9, and 10-4, respectively. and the maximal epoch is set to 100. The batch size at inference is due to the stringent memory limit on MCU, is worth noting that ZiNet is preprocessed with channel pruning to meet the strict memory constraints of MCU. It also allows us see how well the transient redundancy elimination (TREC) works in the presence lasting redundancy elimination (pruning).
5.2
Single-Layer Performance
We report in Appendix C the single-layer speedups and accuracy loss achieved by replacing the conventional convolution with TREC. For comparison, we also include the results from Deep Reuse [25), state-of-the-an method in avoiding transient redundancy in CNN. We have the following observations. First, TREC detects and eliminates about 96. 25% of the transient redundancy. Second, TREC brings significant performance benefits for individual layers with an average speedup of 4.40 Especially for the SqueezeNet expand layers, TREC gets up to 18.66x speedup, indicating that layers. The speedup is lower than the ratio
TREC is especially beneficial to computation-intensi of transient redundancy that TREC eliminates, due to the overhead introduced by the clustering. Third, the influence on accuracy by TREC is small and mixed. When applied to some layers,
8

---

may cause around 0.8% accuracy drop, but it may also give slight accuracy improvements when applied some other layers. TREC overall preserves the accuracy much better (about 3.33% on average) than Deep Reuse does. Furthermore, the Conf. columns report the L.SH configurations in our experiments (Section 5.4 gives more details on the impacts of the hyperparameters and H). We also illustrate the impact of batch size on performance by measuring the redundancy ratio of single layer in Appendix C.2, which shows that TREC has strong redundancy removal ability at any batch size, and that this ability increases with batch size. All above results demonstrate that TREC can exert its full potential, achieving significant speedups while minimizing the accuracy loss.
5.3 End-to-End Performance
Table compares the end-to-end performance brought by TREC, Deep Reuse, and conventional convolution. Given the inherent randomness of Deep Reuse, we present its result interval of 150 runs. Note that after channel pruning. the baseline accuracy of ZfNet is slightly lower than its standard accuracy of 83%, but the model size is 7.6% of the original model, which can well meet the memory constraint of MCU.
Table 2: End-to-end performance comparison.
Network
Conv Method
Average Time per Image (ms)
Top-1 Accuracy (%)
Conventional
217.32
78.2 73.2 ~ 76.1 76.5
CifarNet
Deep Reuse
154.44
TREC
153.92
Conventional
3557.32
80.1 72.5 ~ 76.6 78.9
ZiNet
Deep Reuse
814.03
TREC
814.01
Conventional
1639.51
83.5
Vanilla SqueezeNet
Deep Reuse
328.97
79.8 ~ 81.9 83.0
TREC
327.90
Conventional
1998.86
85.3
SqueezeNet Complex Bypass
Deep Reuse
543.71
80.5 83.1
TREC
$44.03
84.6
Conventional Deep Reuse
4242.77
52.6 46.7 49.9
ResNet-34 (ImageNet-64 x44
1379.26
TREC
1378.75
52.2
Several findings can be drawn from Table 2 First, compared to the conventional convolution, TREC achieves 3.51 x speedup on average with minor (about 0.7%) accuracy loss. Second, TREC and Deep Reuse have comparable inference time, but TREC is superior in terms of stable performance and higher accuracy. Third, TREC cuts the accuracy loss of Deep Reuse from as much as 7.6% to 1.7%, an up 84% reduction.
5.4 Configuration Analysis
Dynamic and Static a of Gaussian. In this set of experiments, we measure the effect of the strategy proposed in Section 3.2 to dynamically set a based on H. To eliminate the influence of irrelevant factors, we choose the most computation-intensiie convolutional layers among four networks and replace them with TREC. As shown in Figure we compare our proposed dynamic strategy with the static approach that manually sets fixed a value of 10-² As seen, the accuracy of the models using a fixed a drops sharply after = 12, and it shows a decreasing trend as H increases. Recalling the discussion in Section 3.2, when H > 12, we have of the hash matrix tends to fall into the maximum value range of the Gaussian derivatives, resulting in large gradient variance and difficulty in model convergence. Thus, our dynamic strategy can effectively guarantee the performance.
10
Therefore, the gradient
Impacts of Hyperparameters L and H Two hyperparameters in TREC are 1) L: the width of the sub-matrices obtained by slicing, and 2) H: the number of hash functions. In application of TREC, they can be chosen empirically like other CNN hyperparameters. In this part, we provide some observations on their impacts. Figure [6 shows the accuracy of TREC, Deep Reuse, and conventional convolution under different L and H configurations. The upper part is the result of changing H with

---

0.8
0.8
0.8
Accuracy
0.7
(ifarNet(2""))
ZfNett2"h
0.6
SqueazeNet(s
Dynamic
Dynamic
Dynamic
0.4
Static(10 4)
0.6
Static(10
0.4
Static(10 4)
10
15
20
15
20
15
20
H
H
Figure 5: Effects dynamic and static settings a.
fixed L, and the range of H set to 5 20. The lower part is the result of changing with fixed H, and the range of I. changes according to the input and weight dimensions of different layers. We have the following observations: 1) TREC and Deep Reuse show a consistent trend of accuracy, which goes up as H increases, and goes down as T. increases. 2) TREC has robust and stable inference performance, which is preferable to the non-eeteriiiistic Deep Reuse. 3) TREC more inclined to stay at high accuracy, proving its ability to mine richer data features.
0.75
0.84
Accuracy
0.78
0.70
CifarNet(2"*)
0.82
SquaezeNet(4"
Regular
0.76
Regular
Regular
0.65
TREC
0.74
TREC
0.80
TREC
Deep Reuse
Deep Reuse
Deep Reuse
15
20
15
10
0.85
0.80
Avcuracy
0.7
CifarNet(2
0.80
SqueezeNet(4")
Regular
Regular
Regular
TREC
0.75
Deep Reuse
Deep Reuse
Deep Reuse
4
10
25
50
100
320800
8
12 16 24
32 48 96 160240480
4
16
24
36
72
144
L
L
Figure 6: Influence of LSH parameter configuration on accuracy.
6
Conclusion
In this paper, we propose a principled approach to detecting and avoiding transient redundancy. It introduces
form of convolutional operator called TREC, which integrates the redundancy avoidance as well as the optimal configuration determination into CNN as an intrinsic part of the CNN architecture. We experimentally and theoretically demonstrate the effectiveness of TREC. This new approach may open many new possibilities for CNN on resource-constraine. devices. As foundational research outcome, it is neutral in terms of societal impacts. limitation of this study is that it focuses on CNNs, but transient redundancy may also exist in other types of Neural Networks as well, exploration of which is left for future to explore.
Acknowledgments and Disclosure of Funding
This material is supported by the National Natural Science Foundation China (No. 62072458. 62172419, 61732014, and 62072459) and Beijing Nova Program, and is based upon work supported by the National Science Foundation (NSF) under Grants CCF- 1703487, CCF-2028850 and CNS- 1717425. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect views of NSF, Feng Zhang is the corresponding author of this paper.
10

---

References
[1] CifarNet. http://pw........aa////////aaaaa soddel_zoo/mon mwwoelssslimmmeeseeeeeeeee htt.://///.aai/eee///.aaaaattetr 2020.
pose/
[2] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223 311, 2018.
[3] Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets, arXiv preprint arXiv: www.117777..8881 2017.
[4] Misha Denil, Babak Shakibi, Laurent Dinh, Marc' Aurelio Ranzato, and Nando De Freitas. Predicting parameters in deep learning. Advances in neural information processing systems, 26, 2013.
[5] Emily Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. Advances in neural information processing systems,
27, 2014.
[6] Haisong Ding, Kai Chen, Yuan, Meng Cai, Lei Sun, Sen Liang, and Qiang Huo. A compact CNN- DBL.SMM based character model for offiine handwriting recognition with Tucker decomposition. In 2017 14th IAPR International Conference Document Analysis and Recognition (ICDAR). volume 1, pages 507-512. IEEE, 2017.
[7] Christoph Feichtenhofer, Axel Pinz, and Andrew Zisserman. Detect to track and track to detect. In Proceedings of the IEEE international conference computer vision, pages 3038-3046, 2017.
[8] lan Goodfellow, Jonathon Shlens, and Christian Szegedy, Explaining and hamesssing adversarial examples. arXiv preprint 1rXiv:1412.665 1412.657, 2014.
[9] Song Han, Huizi Mao, and William Dally. Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. arXiv preprint 15X0v:1510.000 2015.
[10] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
[11] Wei Han, Pooya Khorrami, Tom Le Paine, Prajit Ramachandran, Mohammad Babacizadeh, Honghui Shi, Jianan Li, Shuicheng Yan, and Thomas Huang. Seq-NMS for Video Object Detection. arXiv preprint arXiv:1601 08465, 2016.
[12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[13] Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE international conference on computer vision, pages 1389-1397, 2017.
[14] Forrest N landola, Song Han, Matthew W Moskewicz, Khalid Ashraf, William J Dally, and Kurt Keutzer. SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and< 0.5 MB model size. arXiv preprint N.Xi::6602.073600 2016.
[15] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer- arithmetic-only inference. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2704 2713, 2018.
[16] Dinesh Jayaraman and Kristen Grauman. Slow and steady feature analysis: higher order temporal coherence in video. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3852-3861, 2016.
[17] Sangil Jung, Changyong Son, Seohyung Lee, Jinwoo Son, Jac-Joon Han, Youngjun Kwak, Sung Ju Hwang, and Changkyu Choi. Learning to quantize deep networks by optimizing quantization intervals with task loss. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4350-4359, 2019.
[18] Kai Kang, Hongsheng Li, Junjie Yan, Xingyu Zeng, Bin Yang. Tong Xiao, Cong Zhang, Zhe Wang, Ruohui Wang, Xiaogang Wang, et al. T-CNN: Tubelets with Convolutional Neural Networks for Object Detection from Videos. IEEE Transactions on Circuits and Systems for Video Technology, 28 (8800)2899-2977, 2017.
[19] Yong-Deok Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin. Compression of deep convolutional neural networks for fast and low power mobile applications. arXiv preprint 1331v:551.006500 2015.
11

---

[20] Liangzhen Lai, Naveen Suda, and Vikas Chandra. CMSIS-NN: Efficient Neural Network Kernels for Arm Cortex-M CPUs. arXiv preprint urXiv:1801.0660) 2018.
[21] Vadim Lehedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oseledets, and Victor Lempitsky. Speeding-up Convolutional Neural Networks Using Fine-tuned Dp--Dcomposition. arXiv preprint 11Xiv:1412.6553. 2014.
[22] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning Filters for Efficient ConvNets. arXiv preprint arXiv: 160..08000007000 2016.
[23] Zhenhua Liu, Jizheng Xu, Xiulian Peng, and Ruiqin Xiong. Frequency-domaie dynamic pruning for convolutional neural networks. Advunces neural information processing systems, 31. 2018.
[24] Lin Ning, Hui Guan, and Xipeng Shen. Adaptive Deep Reuse: Accelerating CNN training the fly. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 1538 1549. IEEE, 2019.
[25] Lin Ning and Xipeng Shen. Deep Reuse: streamline CNN inference the fly via coarse-grained computation reuse. Proceedings of the ACM International Conference on Supercomputing, pages 438-448, 2019.
[26] Mohammad Rastegari, Vicente Ordonez. Joseph Redmon, and Ali Farhadi. XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks. In European conference on computer vision, pages 925-542. Springer, 2016.
[27] Christian Szegedy, Wajciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint 1312,693,,,,,9, 2013.
[28] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
[29] Peisong Wang and Jian Cheng. Accelcrating convolutional neural networks for mobile applications. In Proceedings of the 24th ACM international conference Multimedia, pages 541-545, 2016.
[30] Fanyi Xiao and Yong Jae Lee. Video object detection with an aligned spatial-temporal memory. In Proceedings of the European Conference Computer Vision (ECCV), pages 485-501, 2018.
[31] Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference compuder vision, pages 818-833. Springer, 2014.
[32] Xiangyu Zhang, Jianhua Zou, Kaiming He, and Jian Sun. Accelerating very deep convolutional networks for classification and detection. IEEE transactions pattern analysis and machine intelligence, 38( 28(10):1943- 1955, 2015.
[33] Aojun Zhou, Anbang Yao, Yiwen Guo, Lin Xu, and Yurong Chen. Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weights. arXiv preprint arXiv:1702.03044, 2017.
[34] Hao Zhou, Jose M. Alvarez, and Fatih Porikli. Less is more: Towards compact CNNs. In European conference computer vision, pages 662-677. Springer, 2016.
[35] Michael Zhu and Suyog Gupta. To prune, or not prune: exploring the efficacy of pruning for model compression. arXiv preprint
2017.
[36] Xizhou Zhu, Yujic Wang, Jifeng Dai, Lu Yuan, and Yiehen Wei. Flow-guided feature aggregation for vidco object detection. In Proceedingy of the IEEE international conference on computer vision, pages 408-417, 2017.
[37] Xizhou Zhu, Yuwen Xiong, Jifeng Dai, Lu Yuan, and Yichen Wei. Deep feature flow for video recognition. In Proceedings of the IEFF conference on computer vision and pattern recognition, pages 2359, 2017.
[38] Will Zou, Shenghuo Zhu, Kai Yu, and Andrew Ng. Deep learning of invariant features via simulated fixations in video. Advances in neural information processing systems, 25, 2012.
12


Reviews:
[{"review_id": "oah_EQztILA", "reviewer": "Reviewer_PyXK", "summary": "This paper proposes, implements and tests a method to remove transient (data-point dependent) redundancy in the prpagation and backpropagation of convolutional neural networks.", "questions": "- Do we want to train on the edge device? Or do we want to fine-tune the model for the edge device such that it performs better after optimization than the original network?\n- Any empirical evidence on data-sets besides CIFAR-10?\n- Do the theoretical evidence give rise to concrete, quantitative bounds?", "limitations": "Yes the paper addresses the limitations of the methods. I can't see any particular negative societal impact specific to this line of work besides generic concerns that would apply to any methods that improve the efficiency of neural network evaluation in general.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: medium\nThis paper proposes the use LSH for removing (transient) data-point dependent computation cost of neural networks. While the idea has been used several times earlier (eg. in the Reformer [https://arxiv.org/abs/2001.04451]), its application for convolutional networks poses several technical challenges. While it is not too hard to see the solution to those challenges, it is still important and useful for giving a clear recipe for using them in practice and measuring their effectiveness in a real world scenario. In that sense, I think this paper makes a real contribution. Also the paper gives some theoretical guarantees in the limit which are new.\n\nQuality: medium\nThis work proposes an LHS-based method to remove redundant computations in convolutional network. The method needs to do online clustering on the edge device, which results in a data-dependent reduction of computations. The paper reports an \"acceleration\" of the  layers applying this method by up to a 18X speedup. However this is not backed by a clear table of actual numbers, nor its dependence on batch size, neither ablation analysis or even mentioning the device on which this acceleration was reached. More thorough numbers are reported on the inference of the whole network for micro-controllers and the paper reports a total of 3.61X speedup on microcontrollers for the CIFAR-10X network, which would be impressive on its own and a good start.\nHowever, the lack of evidence on data sets with larger than 32x32 images is disappointing and may question the relevance of the approach for real world use cases.\nThe theoretical analysis is nice and seems sound to me, but it works only in the limit and does not come with actual bounds, so its relevance for practical application seems questionable. Also it is unclear how far the theoretical bounds are from the real situation and whether the practical situations are within the range of the theoretical results being of any relevance whatsoever.\n\nClarity: medium\nThere are several unclear points in this paper:\n- The motivation for implementing backpropagation at all is unclear: Do we want to train on the edge device? Or do we want to fine-tune the model for the edge device such that it performs better after optimization than the original network? I assume the latter, but this questions are left for the reader, while the paper puts a lot of emphasis on making backpropagation work. In the latter case (the network finetuned for higher quality evaluation), the paper lacks clear evidence and ablation analysis for the need/efficacy of that appraoch.\n\nSignificance: medium\nIf the method works it could give a clear recipe to improve the latency of CNN inference on certain compute-constrained edge devices. However, it is likely that with inroads of deep learning, specialized hardware will be used in most use cases, which might remove the need for such methods in the not too far future.\n\nGenerally, I think that the paper gives a valuable baseline and recipe for reducing the latency of inference of CNN on microcontrollers, but the experimental evidence given in this paper is not very conclusive, neither is the relevance of the theoretical evidence. I would raise my score in the presence of stronger practical evidence (evaluation on a dataset with larger images) and better motivation(/ablation analysis, if applies) for the backpropagation-related sections.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zfu5kgabGW", "reviewer": "Reviewer_ubp7", "summary": "This paper proposes a principled way to detect and avoid transient redundancy for CNN inference. By introducing a new CNN operator named TREC, it fuses the detection and avoidance of transient redundancy into CNN, making them part of its inherent architecture. TREC comprises three components in series on top of Im2col+GEMM based convolution: LSH-based clustering that reduces the size of the input to the conversion, matrix multiplication of weights and the compressed input, and a recovery step that restores results to the original GEMM output sizes.", "questions": "- “Experiments show that by removing 96.22% transient redundancy, TREC achieves an average of 4.28x speedup compared to the conventional convolution operator.” What is the maximal possible speedup if 100% transient redundancy is removed?\n\n- How would the BN layers (if the architecture has BN) be accommodated with such reduced input feature maps?", "limitations": "No limitation is discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- By introducing a new CNN operator named TREC, it fuses the detection and avoidance of transient 40 redundancy into CNN, making them part of its inherent architecture\n- TREC is compatible with both forward and backward propagations, enabling a plug-and-play replacement for convolutional layers in mainstream CNNs without additional effort.\n- Theoretical analysis on the convergence is also provided.\n\nWeakness\n- The introduction of transient redundancy is not quite clear, it would be great to have some intuitive illustrations or numbers to demonstrate the redundancy. Why TREC makes the design and how it makes inference faster in sec 3.1 is also not quite clear.\n- The evaluated CNN architecture seems not representative for common usage e.g., resnet.\n- It is not clear whether architectures with BN layers can use TREC conv layers and how BN layers to be changed with the changed input feature maps.", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "SkPpnLxxwox", "reviewer": "Reviewer_wscN", "summary": "The paper proposes a method to reduce the number of operations in a CNN by reducing the input to subsequent layers via the clustering of (intermediate) input features/pixels. The authors claim to incorporate the method to be more inherently combined with network architecture coining it, transient redundancy convolution. In particular, the method clusters the rows (convolutions) and replaces the original input with clustered centroids. The paper addresses the issues of how to perform backpropagation with the proposed formulation and provides guarantees for robustness and convergence.  \n", "questions": "In my understanding by clustering, we reduce the number of convolution operations (or scalar products given the GEMM). Theoretically, it sounds promising but in practice, can you actually obtain any speed-ups? Do you also decrease the number of channels of your model (maybe if you remove all the convolutions for a given channel)? Are you planning to release the code?\n\nI'm not sure where the terms come from. For example, in pruning literature, I never heard of the term “lasting redundancy”. Also, the phrases “eliminate 96% of the transient redundancy” can be puzzling without the proper definition in terms of FLOPs, for example.  I'd be cautious with using new terms, which may create confusion.\n", "limitations": "Little is said about the work’s limitations. \n", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea of clustering the inputs on the fly is interesting compared to the reducing the size of the input to NN only, or compressing the network and fixing its parameters. In TREC for every input data, we perform individual clustering at every stage of the forward pass to reduce further convolution operations. As a result, the redundancy is computed at every stage of the inference which makes it more flexible than reducing the size of the input to NN or decreasing the size of the network. \n\nThe analysis of complexity, convergence, and robustness is giving better insight into the theoretical guarantees of the algorithm. \n\nThe paper seems to heavily rely on the DeepReuse. It's following the same ideas, for example, using the same method for “clustering”, LSH hashing, same parameters L and H. Please state clearly the differences between the two approaches, and what elements of your method cause the improvements in TREC as compared to DeepReuse (also, I hardly see the randomness as the big disadvantage of DeepReuse).\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "F2oQgjf50EW", "reviewer": "Reviewer_us1K", "summary": "The paper proposes a convolution operation, dubbed TREC, with transient redundancy that is exploited during inference to reduce computation. Specifically, the authors use LSH to cluster layer inputs in the forward pass and use the cluster centers in the weight multiplication to compute the outputs. The authors propose a differentiable implementation for the LSH-based clustering which allows for training the TREC, thereby improving the accuracy compared to prior methods. In addition to empirical evaluations, the authors provide a theoretical analysis of the convergence and robustness of TREC.", "questions": "Please see the weaknesses above. \n\nQuestions and limitations:\n- The reported accuracies for the Deep reuse paper are quite different from what is reported in the original paper (they claim no accuracy loss). Can the authors please clarify on the main differences in the evaluation setup that causes this difference?\n\n-  Since the prior work Deep reuse, which is using a quite similar method, has evaluations on ImageNet, the authors are encouraged to add these evaluations to show that the scope of the proposed method is not limited to small datasets and the accuracy gains are persistent in more challenging benchmarks.", "limitations": "The authors have not discussed the limitations and potential negative social impact of their work", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and the ideas are clearly explained.\n- The combination of theoretical evidence with empirical results helps strengthen the claims.\n- The ideas for making the clustering differentiable are interesting.\n\nWeaknesses:\n- The LSH-based clustering is previously proposed in the Deep Reuse paper. Therefore, the main contribution here is enabling backward propagation with a differentiable implementation for the clustering. The authors should explicitly clarify this in the paper and give proper reference to the prior art.\n- The method is only evaluated on small-scale benchmarks (CIFAR-10) while prior work includes results on ImageNet. As such, a question rises regarding the applicability of the proposed method when evaluating larger scale datasets. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept