{'fraction_non_alphanumeric': 0.04447288433850584, 'fraction_numerical': 0.01205140510851597, 'mean_word_length': 4.359674192626465, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Memorized Sparse Backpropagation

Neural network learning is typically slow since backpropagation needs to compute full gradients and backpropagate them across multiple layers. Despite its success of existing work in accelerating propagation through sparseness, the relevant theoretical characteristics remain unexplored and we empirically find that they suffer from the loss of information contained in unpropagated gradients. To tackle these problems, in this work, we present a unified sparse backpropagation framework and provide a detailed analysis of its theoretical characteristics. Analysis reveals that when applied to a multilayer perceptron, our framework essentially performs gradient descent using an estimated gradient similar enough to the true gradient, resulting in convergence in probability under certain conditions. Furthermore, a simple yet effective algorithm named memorized sparse backpropagation (MSBP) is proposed to remedy the problem of information loss by storing unpropagated gradients in memory for the next learning. The experiments demonstrate that the proposed MSBP is able to effectively alleviate the information loss in traditional sparse backpropagation while achieving comparable acceleration.


Introduction
Training neural networks tends to be time-consuming [8,16,19], especially for architectures with a large number of learnable model parameters. An important reason why neural network learning is typically slow is that backpropagation requires the calculation of full gradients and updates all parameters in each learning step [23]. As deep networks with massive parameters become more prevalent, more and more efforts are devoted to accelerating the process of backpropagation. Among existing efforts, a prominent research line is sparse backpropagation [23,26,28], which aims at sparsifying the full gradient vector to achieve significant savings on computational cost.
One effective solution for sparse backpropagation is top-k sparseness, which only keeps k elements with the largest magnitude in the gradient vector and backpropagates them across different layers. For instance, meProp [23] employs the top-k sparseness to compute only a very small but critical portion of the gradient information and update corresponding model parameters for the linear transformation. Going a step further, [26] implements the top-k sparseness for backpropagation on convolutional neural networks. Experimental results demonstrate that these methods can achieve significant acceleration of the backpropagation process. However, despite its success in saving computational cost, the top-k sparseness for backpropagation still suffers from some intractable drawbacks, elaborated on as follows.
analysis illustrates that when applied to a multilayer perceptron, the proposed framework essentially employs an estimated gradient similar enough to the true gradient to perform gradient descent, which leads to convergence in probability under certain conditions.
On the empirical side, we find that top-k sparseness for backpropagation tends to result in the loss of information contained in unpropagated gradients. Although it can propagate the most crucial gradient information by keeping only k elements with the largest magnitude in the gradient vector, the unpropagated gradient may also contain a certain amount of useful information. Such information loss usually results in some adverse effects like poor stability in model performance. 1 To remedy this, we propose memorized sparse backpropagation (MSBP), which stores unpropagated gradients in memory for the next learning while propagating a critical portion of the gradient information. Compared to the previous work [23,26], the proposed MSBP is capable of alleviating the information loss with the memory mechanism, thus improves model performance significantly. To sum up, the main contributions of this work are two-fold: 1. We present a unified sparse backpropagation framework and prove that some existing methods [23,26] are special cases under this framework. In addition, the theoretical characteristics of the proposed framework are analyzed in detail to provide theoretical guarantees for related work.
2. We propose memorized sparse backpropagation, which aims at alleviating the information loss by storing unpropagated gradients in memory for the next learning. The experiments demonstrate that our approach is able to effectively alleviate the information loss while achieving comparable acceleration.

A Unified Sparse Backpropagation Framework
This section presents a unified framework for sparse backpropagation, which can be used to explain some existing representative approaches [23,26]. We first define the EGD algorithm in Section 3.1) and then formally introduce the proposed framework in Section 3.2.

Estimated Gradient Descent
Here we introduce the definition of the estimated gradient descent algorithm, which provides a framework for analyzing the convergence of sparse backpropagation. Definition 5 (EGD). Suppose = (w; D) is the training loss defined on the dataset D and w ∈ R n is the parameter vector to learn. The estimated gradient descent (EGD) algorithm adopts the following parameter update: (1) where w t is the parameter at time-step t, η t > 0 is the learning rate, and g w t is an estimation of the true gradient ∂ ∂wt for parameter updates.
Some existing optimizers can be regarded as special cases of EGD. For instance, when g w t is defined as the true gradient ∂ ∂wt , EGD is essentially the gradient descent (GD) algorithm. Several other works (e.g. Adam [10], AdaDelta [27]) can also be summarized as different expressions of EGD when g w t is implemented as different estimates. More importantly, the sparse backpropagation employs the estimated gradient to approximate the true gradient for model training in essence, which can also be regarded as a special case of EGD. This connection casts the cornerstone of subsequent theoretical analysis of sparse backpropagation.
In this work, we theoretically prove that once the gradient estimation angle δ(w t ) of the parameter w t satisfies certain conditions for each time-step t, the EGD algorithm can converge to the global minima w * under some reasonable assumptions. This conclusion is demonstrated in Theorem 3. Readers can refer to Appendix.E for the detailed proofs and we discuss the convergence speed of EGD in Appendix.G. Theorem 1 (Convergence of EGD). Suppose w t is the parameter vector, w * is the global minima, and training loss = (w; D) defined on the dataset D is µ-strongly convex and L−smooth. When applying the EGD algorithm to minimize , if the gradient estimation angle δ(w t ) of w t satisfies δ(w t ) + φ( ) ≤ θ < π/2, then there exists learning rate η t > 0 for each time-step t such that For the given training loss = (w; D), φ( ) is a fixed value. Therefore, the above theorem demonstrates that the EGD algorithm can converge to the global minima w * when the angle δ(w t ) between the estimated gradient g w t and the true gradient ∂ ∂wt is small enough at each time-step.

Proposed Unified Sparse Backpropagation
In this section, we present a unified sparse backpropagation framework via sparsifying function (Definition 8). The core idea is that when performing backpropagation, the gradients propagated from the next layer are sparsified to achieve acceleration. Algorithm 1 presents the pseudo code of our unified sparse backpropagation framework, which is described in detail as follows.
Considering that a computation unit composed of one linear transformation and one activation function is the cornerstone of various neural networks, we elaborate on our unified sparse backpropagation framework based on such a computational unit: where x ∈ R n is the input vector, W ∈ R m×n is the parameter matrix, and σ(·) : R m → R m denotes a pointwise activation function. Then, the original backpropagation computes the gradient of the parameter matrix W and the input vector x as follows: h ← Wx 7: z ← σ(h) 8: Propagate z to the next layer 9: /* backward */ 10: Get ∂ ∂z propagated from the next layer 11: In the proposed unified sparse backpropagation framework, the sparsifying function (Definition 8) is utilized to sparsify the gradient ∂ ∂h propagated from the next layer and propagates them through the gradient computation graph according to the chain rule. Note that ∂ ∂h is also an estimated gradient passed from the next layer. The gradient estimations are finally performed as follows: Since top k is a special sparsifying function (see Section 2), some existing approaches (e.g., me-Prop [23], meProp-CNN [26]) based on the top-k sparseness can be regarded as special cases of our framework. Dependended on the specific task, the sparsifying function can be defined as the different expression to improve model performance.
However, an intractable challenge for sparse backpropagation is the lack of theoretical analysis. To remedy this, here we analyze the theoretical characteristics of the proposed framework. With the fact that sparse backpropagation is a special case of EGD (Section 3.1), we theoretically illustrate that when applied to a multi-layer perceptron (MLP), the proposed framework can converge to the global minima in probability under several reasonable conditions, which is formalized in Theorem 4.
Theorem 2 (Convergence of unified sparse backpropagation). For an ideal 4 dataset D, if the training loss = (w; D) is µ-strongly convex and L−smooth, when applying the unified sparse backpropagation to train a MLP 5 , there exists a sparse ratio r ∈ (0, 1) and learning rates η t such that w t can converge to the global minima w * if we set the sparse ratio of sparsifying functions to r.
The crucial idea to prove the above theorem is illustrating that the angle between the sparse gradient and the true full gradient is small enough for sparse backpropagation. Under this circumstance, the condition of the gradient estimation angle in Theorem 3 is satisfied, leading to the desired convergence in probability. Readers can refer to Appendix.F for the detailed proofs.
Although Theorem 4 is constrained by the base architecture of multi-layer perceptron and several additional conditions, it is able to provide a degree of theoretical guarantee for the proposed unified sparse backpropagation framework. Our efforts in these theoretical analyses are valuable because they help explain the effectiveness of not only our framework but also some existing approaches [23, 26] on the theoretical side. 4 It means that |D| is large enough and data instance (x, y) ∈ D obeys independent and identical distribution 5 There are several trivial constraints on MLP. Please refer to Appendix.D.5 for more details.

Memorized Sparse Backpropagation
Although traditional sparse backpropagation is able to achieve significant acceleration by keeping only part of elements in the full gradient, the unpropagated gradient may also contain a certain amount of useful information. We empirically find that such information loss tends to bring negative effects (e.g., performance degradation in extremely sparse scenarios, poor stability in performance). To remedy this, here we propose memorized sparse backpropagation (MSBP), which aims at alleviating the information loss by storing unpropagated gradients in memory for the next learning.
The core component of the proposed MSBP is the memory mechanism, which enables MSBP to store unpropagated gradients for the next learning while propagating a critical portion of the gradient information. Formally, different from the unified sparse backpropagation in Section 3.2, we adopt the following gradient estimations: where S I k (·) is a given sparsifying function and m is the memory storing unpropagated gradients from the last learning step. Then, the memory m is updated by the information of unpropagated gradients at the current learning step. Formally, where γ ∈ (0, 1) is the memory ratio, a hyper-parameter controlling the ratio of memorizing unpropagated gradients. When γ is set to 0, the proposed MSBP degenerates to the unified sparse backpropagation that completely discards unpropagated gradients. Algorithm 2 presents the pseudo code of MSBP. Before the model training begins, we initialize memory m to zero vector. Intuitively, by storing unpropagated gradients with the memory mechanism, the information loss in backpropagation due to sparseness can be alleviated. The experiments also illustrate that the proposed MSBP is more advantageous in various respects than approaches that completely discards unpropagated gradients. In fact, we find that for MSBP, the angle between the sparse gradient and true full gradient tends to be small. Furthermore, this angle is smaller than that in traditional sparse backpropagation. According to theoretical analysis in Section 3, a smaller gradient estimation angle is more conducive to model convergence. This observation explains the effectiveness of our MSBP to a certain extent on the theoretical side. Readers can refer to Section 5.4 for a more detailed analysis.
Comparison to sparsified SGD with memory. A work that looks similar to this paper is sparsified SGD with memory [21]. It calculates full gradients in backpropagation and sparsifiers gradients to be communicated in a distributed system. Therefore, different from that we sparsify gradients in backpropagation, the backpropagation process in [21] remains unchanged and cannot be accelerated. Besides, [21] is an optimization approach that can only be used in distributed systems, while our MSBP is a backpropagation framework that applies to both distributed and centralized systems.

Experiments
Following meProp [23], we adopt S I k (·) = top k (·) as the sparsifying function. For simplicity, we use SBP to represent the traditional sparse backpropagation that completely discards unpropagated gradients. Table 4 presents a comparison of time and memory complexity of traditional SBP and our proposed MSBP. Readers can refer to Appendix.A for the detailed discussions.

Evaluation Tasks
We evaluate the proposed MSBP on several typical benchmark tasks in computer vision as well as natural language processing. The baselines used for comparison on each task are also introduced. Due to page limitations, we include all details of dataest and experimental settings in Appendix.B. . h refers to the hidden size of MLP. r is the sparse ratio of sparsifying function and γ denotes the memory ratio of our MSBP. BP (s) refers to the backpropagation time cost on CPU in seconds (a× is compared to baseline). Acc and UAS denote the averaged accuracy and unlabeled attachment score, respectively (+a/−a is compared to baseline). MNIST image recognition (MNIST): This task aims to recognize the numerical digit (0-9) of each image and the evaluation metric is the accuracy of classification. We use the standard MNIST handwritten digit dataset [12] and adopt a 3-layer MLP as the base model.
Transition-based dependency parsing (Parsing): Following previous work, the dataset is selected as English Penn TreeBank (PTB) [13] and the evaluation metric is unlabeled attachment score (UAS). We implement a parser using MLP following [1] as the base model.

Part-of-speech tagging (POS-Tag):
We use the standard benchmark dataset [3] derived from the Penn Treebank corpus and the evaluation metric is per-word accuracy. We adopt a 2-layer bidirectional LSTM (Bi-LSTM) as our base model.
Polarity classification and subjectivity classification: Both tasks are designed to perform sentence classification, with accuracy as the evaluation metric. We use the dataset constructed by [14] and implement TextCNN [9] as the base model.

Experimental Results
The experimental results on three tasks of MNIST, Parsing, and POS-Tag are shown in Table 2. We conduct an in-depth analysis of the results from the following aspects.
Improving model performance. As shown in Table 2, the proposed MSBP achieves the best performance on all tasks. For instance, on the parsing task, MSBP achieves 0.44% absolute improvement over traditional SBP and also outperforms the base model by 0.65% in the UAS score. Considering that our ultimate goal is to accelerate neural network learning while achieving comparable model performance, such results are promising and gratifying. Compared to traditional SBP [23, 26], MSBP employs the memory mechanism to store unpropagated gradients. This reduces the information loss during backpropagation, leading to improvements in the model performance.
Accelerating backpropagation. In contrast to traditional SBP, our MSBP memorizes unpropagated gradients to alleviate information loss. However, a potential issue is that the introduction of memory containing unpropagated gradients may impair the acceleration of backpropagation. Table 4 illustrates that MSBP exhibits the same time complexity as traditional SBP. Here we further verify this conclusion with experiments. As shown in Table 2, either traditional SBP or our proposed MSBP is able to achieve great acceleration of backpropagation, and the latter shows only negligible increase in computational cost compared to the former. This illustrates that our MBSP can achieve comparable acceleration while improving model performance.
Applicability to extremely sparse scenarios. In sparse backpropagation, the sparse ratio r controls the trade-off between acceleration and model performance. In pursuit of ultra-large acceleration, r tends to be set extremely small in real-scenarios. However, we empirically find that traditional SBP usually results in a significant degradation in model performance in this case. Table 2 shows that traditional SBP brings a 1.90% reduction in accuracy on MNIST image classification for r = 0.002. The reason is that for small r values, only a very small amount of gradient information is propagated. Therefore, there exists serious information loss during backpropagation, leading to a significant degradation in model performance. In contrast, results show that our MSBP is still effective in these extremely sparse scenarios. With the memory mechanism, the current unpropagated gradient information is stored for the next learning, reducing the information loss caused by sparseness.

Further In-Depth Analysis
In this section, we conduct further analysis of the proposed approach and experimental results.
Universality to base network architectures. Here we compare traditional SBP and the proposed MSBP on the CNN base model to verify the universality of our approach. Results show that traditional SBP improves the model performance on shallow CNNs (sentence classification) but fails on deeper networks, e.g., PreAct-ResNet-18 (image classification). As shown in Table 3, traditional SBP suffers from significant degradation of classification accuracy on CIFAR10 image classification. In contrast, the proposed MSBP improves the performance of the base model on both sentence classification and image classification. This demonstrates that our MSBP is universal, which applies to not only different types of base networks, but also different depths of models.
Improvement in model stability. We find that our MSBP is also effective in improving model stability, meaning that it contributes to reducing the variance of the model performance in repeated experiments. To verify this conclusion, for each setting, we repeat 20 experiments on the MNIST task with different random seeds. The mean and standard deviation of the accuracy of repeated experiments are presented in Figure 1 and Figure 2 respectively. Results show that the traditional SBP (γ = 0) suffers from poor model stability in repeated experiments, whose standard deviation is nearly 1.7 times of the base model (MLP). In contrast, all experiments conducted with MSBP (γ = 0) have better stability than traditional SBP and most of them are even better than the base model.
Insensitivity to hyper-parameters. As depicted in Figure 1, for the same k, MSBP (γ > 0) performs better than traditional SBP [23] (γ = 0) regardless of the choice of γ. The difference in accuracy between MSBP and traditional SBP ranges from 0.4% to 0.8%, while that between MSBP with different γ settings lies between 0.1% to 0.3%. This illustrates that the performance of MSBP is not very sensitive to γ compared to the improvement gained by the memory mechanism.

Why MSBP Works
As analyzed in Section 3, for sparse backpropagation, a smaller gradient estimate angle can better guarantee the convergence of approach. Therefore, we show the averaged gradient estimate angle calculated in the proposed MSBP and traditional SBP to empirically explain the effectiveness of our method. As shown in Figure 3, higher k results in smaller gradient estimation angles and for the same k, the gradient estimation angles in MSBP are smaller than that in SBP. This illustrates that by employing the memory mechanism to store unpropagated gradients, the sparse gradient calculated by our approach gives a more accurate estimate of true gradient, which is also consistent with results in Figure 1. In addition, the gap between the gradient estimation angles of SBP and MSBP tends to be bigger for lower k because SBP suffers from the loss of unpropagated gradients more for lower k, under which circumstances our proposal improves the performance more greatly.

Related Systems of Evaluation Tasks
Here we present evaluation scores of related systems on each task. Our MSBP can benefit complicated base models to advance corresponding scores, but this is not the focus of this work. Therefore, we adopt MLP, LSTM, and CNN as the base model, due to their crucial roles in deep learning.

Conclusion
This work presents a unified sparse backpropagation framework. Some previous representative approaches can be regarded as special cases of it. Besides, the theoretical characteristics of the proposed framework are analyzed in detail to provide theoretical guarantees for the relevant methods. Going a step further, we propose memorized sparse backpropagation (MSBP), which aims at alleviating the information loss in tradition sparse backpropagation by utilizing the memory mechanism to store unpropagated gradients. The experiments demonstrate that the proposed MSBP exhibits better performance in both model performance and stability while achieving comparable acceleration.
[7] Huang, Z., Xu, W., Yu, K.: Bidirectional lstm-crf models for sequence tagging. arXiv preprint arXiv:1508.01991 (2015) [ Following meProp [23], we adopt S I k (·) = top k (·) as the sparsifying function. For simplicity, we use SBP to represent the traditional sparse backpropagation that completely discards unpropagated gradients. In contrast, our proposed memorized sparse backpropagation is denoted as MSBP. Table 4 presents a comparison of time and memory complexity of the two approaches.  consists of 60,000 training handwritten digit images and additional 10,000 test handwritten digit images. This aim of MNIST dataset is to recognize the numerical digit (0-9) of each image. We split the training images into 5,000 development images and 55,000 training images. The evaluation metric is the accuracy of the classification. We adopt a 3-layer MLP model as a baseline.
CIFAR-10 image recognition (CIFAR-10) Similar to MNIST, the goal of this task is to predict the category of each image. We conduct experiments on the CIFAR-10 dataset [11], which consists of 50,000 training images and additional 10,000 test images. The evaluation metric is accuracy and PreAct-ResNet-18 [6] is implemented as the base model. Polarity classification and subjectivity classification In these two tasks, we implement the base model as TextCNN [9]. We evaluate different approaches on the dataset in [14] and the evaluation metric is the accuracy of classification.

B.2 Experimental Settings
MNIST, Parsing, and POS-Tag We train 20, 20, 10 epochs on three tasks of MNIST, Paring, and POS-Tag, respectively. The batch size is set to 32, 1024, and 128, respectively. The dropout probability is set to 0.1, 0.2, 0.5, respectively. We use the Adam optimizer [10] with the learning rate 10 −3 on all three tasks.
CIFAR-10 For the CIFAR-10, we report the averaged accuracy on the test set of all epochs. The batch size is set to 128 and the dropout probability is 0.5. We conduct experiments with SGD and Adam two optimizers on this task. We apply a momentum [17] (with a weight decay of 5 × 10 −4 and momentum value of 0.9) on SGD. For SGD, the initial learning rate is 0.1 and we use a multi-step learning rate scheduler and the milestones are 150, 250 and the decay rate is 0.1. For Adam, the initial learning rate is 10 −3 . Other hyper-parameters and optimizing techniques on CIFAR-10 are the same as those in [6].
Polarity classification and subjectivity classification For these two tasks, we report the averaged accuracy on the test set of all epochs. For the base model (TextCNN), the filter window sizes are 3, 4, and 5, with 100 feature maps each. The batch size is set to 32. We conduct experiments with Adam optimizer with a learning rate of 10 −3 .

C Review of Definitions and Theorems in Paper
In this section, we review some important definitions and theorems introduced in the paper.

C.1 Definitions
This section presents several definitions. Given the dataset D = {(x, y)}, the training loss of an input instance x is defined as w; (x, y) , where w denotes the learnable model parameters and (·, ·) is some loss function such as 2 or logistic loss. Further, the training loss on the whole dataset D is defined as (w; D) = 1 |D| (x,y)∈D w; (x, y) . We represent the angle between the vector a and the vector b as a, b ∈ [0, π]. Definition 6 (Convex-smooth angle). If the training loss (w; D) on the dataset D is µ-strongly convex and L-smooth for parameter vector w, the convex-smooth angle of is defined as φ( ) = arccos( µ/L) ∈ (0, π 2 ). Definition 7 (Gradient estimation angle). For any vector v and training loss on an instance or the dataset, we use g v to represent an estimation of the true gradient ∂ ∂v . Then, the gradient estimation angle between the estimated gradient g v and the true gradient ∂ ∂v is defined as δ(v) = g v , ∂ ∂v . 6 Definition 8 (Sparsifying function). Given an integer k ∈ [0, n], the function S I k (·) is defined as where v is the input vector, and I k (v) is a binary vector consisting of k ones and n − k zeros determined by v. If S I k (v) satisfies S I k (v), v ≤ arccos( k/n) for any v, we call S I k (v) as sparsifying function and define its sparse ratio as r = k/n.

Definition 9 (top k ). Given an integer k, for vector
In other words, the top k function only preserves k elements with the largest magnitude in the input vector.
It is easy to verify that top k is a special sparsifying function (see Appendix.D.3.). Definition 10 (EGD). Suppose = (w; D) is the training loss defined on the dataset D and w ∈ R n is the parameter vector to learn. The estimated gradient descent (EGD) algorithm adopts the following parameter update: where w t is the parameter at time-step t, η t > 0 is the learning rate, and g w t is an estimation of the true gradient ∂ ∂wt for parameter updates.

C.2 Theorems
Theorem 3 (Convergence of EGD). Suppose w t is the parameter vector, w * is the global minima and training loss = (w; D) defined on the dataset D is µ-strongly convex and L−smooth. When applying the EGD algorithm to minimize , if the gradient estimation angle δ(w t ) of w t satisfies δ(w t ) + φ( ) ≤ θ < π/2, then there exists learning rate η t > 0 for each time-step t such that Theorem 4 (Convergence of unified sparse backpropagation). For an ideal 7 dataset D, if the training loss = (w; D) is µ-strongly convex and L−smooth, when applying the unified sparse backpropagation framework to train a MLP 8 , there exists a sparse ratio r ∈ (0, 1) and learning rates η t such that w t can converge to the global minima w * if we set the sparse ratio of sparsifying functions to r. 6 After both the training loss and the estimation method of the gradient are defined, the gradient estimation angle δ(v) depends only on v.
7 It means that |D| is large enough and data instance (x, y) ∈ D obeys independent and identical distribution 8 There are several trivial constraints on MLP, please refer to Appendix.D.5 for more details.

D Preparation and Lemmas
Here we introduce some key definitions and lemmas throughout the appendix. All vectors and matrices are assumed to belong to the real number field. In Appendix, vectors (e.g. x, y) and matrices (e.g. W, A) are in bold formatting.

D.1 Vectors
We first introduce two vector-related lemmas. Lemma D.1. For any vectors a, b and c, we have and P is an orthogonal matrix. We define σ min = min i σ i and σ max = max i σ i . If ρ ≥ σmax σmin ≥ 1, for any n-dimension vectors u and v, we have

D.2 Loss Function
We define the loss function = (w; D) as µ-strongly convex if for µ > 0, ∇ 2 (x) µI, where I denotes identity matrix. If the loss function is µ-strongly convex , for any vectors a, b, we have We define the loss function = (w; D) as L-smooth if for L > 0, ∇ 2 (x) LI, where I denotes identity matrix. If the loss function is L-smooth, for any vectors a, b, we have For the loss function , we define w * as its global minima. If is L-smooth, for any w, we have From Eq. 12 and Eq. 13, we can see, in other words, µ ≤ L. When µ = L, we have (b) = (a) + ∇ (a) · (b − a) + L 2 b − a 2 , in other words,when we set a = 0 = (0, 0, · · · , 0) T and b = x, (x) = (0) + (a) · x + L 2 x 2 , where it has a closed-form solution and is trival. Therefore, we assume in most cases, 0 < µ < L.

D.3 top k Function
We will prove the top k function is a special sparsifying function.
Given an integer k ∈ [0, n], for vector v = (v 1 , · · · , v n ) T ∈ R n where |v π1 | ≥ · · · ≥ |v πn |, the top k function is defined as top k (v) = I k (v) v where the i-th element of I k (v) is s i = I(i ∈ {π 1 , · · · , π k }). It is easy to verify that In other words, Therefore, the top k function is a special sparsifying function.

D.4 Linear Layer Trained with SBP
Consider a linear layer with one linear transformation and one increasing pointwise activation function where x ∈ R n is the input sample, W ∈ R m×n is the parameter matrix (m ≥ n), n is the dimension of the input vector, m is the dimension of the output vector and σ is an increasing pointwise activation function (e.g., σ(x) = x, σ(x) = tanh(x) or σ(x) = sigmoid(x)).
For matrix W ∈ R m×n , we define flattening function to flatten it into a vector in R nm as f latten(W) = [W :,1 ; · · · ; W :,n ], where W :,i represents the i-th column of W and the semicolon denotes the concatenation of many column vectors to a long column vector. In other words,f latten(W) (j−1)m+i = W ij . Assume x = (x 1 , x 2 , · · · , x n ) T , h = (h 1 , h 2 , · · · , h m ) T and W = (W ij ) 1≤i≤m,1≤j≤n , then h i = n j=1 W ij x j , when backpropagating In the proposed unified sparse backpropagation framework, the sparsifying function (Definition 8) is utilized to sparsify the gradient ∂ ∂h propagated from the next layer and propagates them through the gradient computation graph according to the chain rule. Note that ∂ ∂h is also an estimated gradient passed from the next layer. The gradient estimations are finally performed as follows: in other words, We introduce a lemma: For a linear layer trained with SBP, the sparse ratio of the sparsifying function in SBP is r. Denote w = f latten(W) .If = (w, (x, y)) is the loss of MLP trained with SBP on this input instance and the input of this layer is x which satisfies x = 0, we use SBP to estimate ∂ /∂w and ∂ /∂x. suppose WW T is a positive definite matrix, the eigenvalue decomposition of WW T is WW T = PΣP T ∈ R m×m , Σ = diag{s 1 , s 2 , · · · s m } (s i > 0) and P is an orthogonal matrix. We define s min = min It is easy to verify that s min > 0 and σ min > 0 because WW T is a positive definite matrix and σ is increasing. If

D.5 MLP Trained with SBP
Consider a MLP trained with SBP, it is a N -layer multi-layer perception (MLP), every layer except the last layer is a linear layer with SBP. x (1) ∈ R n1 is the input of the MLP, x (N +1) ∈ R n N +1 is the output of the MLP. The i-th layer of MLP is defined as where x (i) ∈ R ni , W (i) ∈ R ni+1×ni and n i+1 ≥ n i , σ i is an increasing pointwise activation function of layer i (i < N ). Note that the last layer is not a linear layer trained with SBP. Therefore, σ N need not to be an increasing pointwise activation function. It can be softmax function, which is not a pointwise activation function.
Assume w is the parameter vector of MLP defined as We use the condition number to measure how sensitive the output is to perturbations in the input data and to roundoff errors made during the solution process. Define condition number of matrix A as cond(A) = A A −1 , when we adopts the spectral norm A = A 2 , then cond(A) = λmax λmin , where λ max and λ min are the maximum and minimum singular value of A respectively.
If the condition number is small, we say the matrix is well-posed and otherwise ill-posed. If a matrix is singular, then its condition number is infinite, it is very ill-posed.
For a MLP trained with SBP, we assume that it is ρ-well-posed if there exist ρ 1 > 1, ρ 2 > 1 in any layer i and any time step t such that We introduce a lemma here to ensure that the gradient estimation angle of the parameter vector can be arbitrarily small for an input instance with its label as input in MLP trained with SBP. Lemma D.4. For a MLP trained with SBP, for any input instance x (1) = x with its label y which satisfies x = 0. Assume w is the parameter vector. If the MLP is ρ-well-posed, then for any θ ∈ (0, π/2), there exsits r ∈ (1/ρ 2 , 1) such that if we set the sparse ratio of every sparsifying function in SBP as r, we can get g w;(x,y) , an estimation of ∇ w; (x, y) to make gradient estimation angle satisfy δ(w) < θ.

D.6 Review of the Term "In Probability"
A sequence of random variables X n converges to a random variable X in probability if for any > 0 lim n→∞ P(|X n − X| ≥ ) = 0 We introduce a lemma here Lemma D.5. For a sequence of random variables X n , when n → ∞, if Var(X n ) → 0 and E(X n ) → a, then X n converges to a in probability.

E Proofs of Theorem 3
Proof. According to the Ineq. 11, According to Ineq. 16, Combining Ineq. 29 with Ineq. 30, we have in other words, we have

F Proof of Theorem 4
Proof. The proof only consider a single time step t.
, where n is the number of data instances. Define We introduce a lemma here and we will prove it later. u i and v i in the lemma is defined above.
Lemma F.1. Dataset D has n independent and identically distributed (i.i.d.) data instances. Suppose for any θ ∈ (0, π 2 ) and any (x i , y i ) ∈ D we can find r ∈ (1/ρ 2 , 1) such that if we set the sparse ratio of every sparsifying function in SBP as r, then u i , v i < θ and u i = v i . Then for any ∈ (0, π 2 ), there exists r ∈ (1/ρ 2 , 1) such that when n → ∞ and we set the sparse ratio of every sparsifying function in SBP as r, δ(w t ) < holds in probability.
According to Lemma D.4, for any θ ∈ (0, π 2 ) and any (x i , y i ) ∈ D we can find r ∈ (1/ρ 2 , 1) such that if we set the sparse ratio of every sparsifying function in SBP as r, then u i , v i < θ and u i = v i (Eq. 93). We also have a large enough dataset D, which has n independent and identically distributed (i.i.d.) data instances. The condition of Lemma F.1 is satisfied.
, there exists r ∈ (1/ρ 2 , 1) such that when n → ∞ and we set the sparse ratio of every sparsifying function in SBP as r,δ(w t ) < α holds in probability.
According to Theorem 3, when δ(w t ) < α and is µ-strongly convex and L-smooth, Therefore, MLP trained with SBP converges in probability.

G Discussion of the Convergence Speed
In Theorem 3, if we define a(θ) = 1 log 1 sin θ , where we have a(θ) > 0. a(θ) decreases monotonically as θ increases (0 < θ < π/2). Therefore in other words, We have To ensure that w T −w * ≤ , we just have to ensure that log w T −w * + T a(θ) ≤ log w 0 −w * ≤ log + T a(θ) . In other words, we just have to ensure that T ≥ a(θ) log w0−w * . Therefore, for any T such that we can get weights -close to the global minimal, in other words, w T − w * ≤ , where a(θ) > 0 is determined by θ and increases monotonically as θ increases.
Therefore, the smaller the gradient estimation angle is, the faster EGD converges. Experimental results of the average cosine value of gradient estimation angles of parameters in MNIST dataset show that the gradient estimation angles of memorized SBP and SBP are smaller than SGD in most cases. In other words, SBP and our proposal converge even faster than linear layer even their backpropagation is sparse.

H Proofs of Lemmas
Proof of Lemma D.1. Without loss of generality, we assume a = b = c = 1.
Define a 1 = a − (a · c)c and b 1 = b − (b · c)c. We have and in other words, a, b ≤ a, c + b, c .
Proof of Lemma D.2. Without loss of generality, we assume u = v = 1.
We can see D T = D and for any vector and We define a = P T u and b = P T v, we have and similarly we have similarly Then and in other words, Proof of Lemma D.3. First, let's consider δ(x).
Without loss of generality, we assume On one hand, On the other hand, combined with Eq. 87 and Eq. 88 in other words,δ(w) = δ(f latten(W)) = δ(h).
in other words, where we defineβ = n i=1 u i /(n ū ).
Combined with Eq. 138, then