Neural Networks with (Low-Precision) Polynomial Approximations:
New Insights and Techniques for Accuracy Improvement

We initiate the investigation on how to reduce the impact on inference accuracy due to approximation errors in PANN. For the ease of writing, we say a neural network $\mathbb{F}$ is sturdy if the PANN of $\mathbb{F}$ has good resistance against approximation errors. In other words, we can use less precise approximation for a sturdy neural network to maintain the inference accuracy.

Specifically, we bound the lower bound of increased loss resulting from approximation errors and obtain the following two interesting results:

• •

  Approximation errors on negative inputs of ReLU lead to larger loss than those on positive inputs of ReLU;

• •

  The increased loss resulting from approximation errors will increase with larger weight decay and more training epochs.

To substantiate our analysis, we conduct tests and have observed the results across various model structures, datasets, and approximation methods.

Based on our findings, we present two solutions to improve “sturdiness” of neural networks, namely, the negative inputs leakage method and reducing the use of weight regularization. Our first solution is based on the insight that approximation errors on ReLU’s negative inputs lead to more loss. In more detail, our first solution introduces perturbations on the negative inputs of ReLU during baseline training. Our second solution is based on the findings that weight regularization is harmful to “sturdiness”. Intuitively, we can improve “sturdiness” by removing weight regularization during training. However, weight regularization is crucial in providing generalization. Our second solution is considered a trade-off: we use minimal weight regularization and combine it with Mixup to maintain an acceptable accuracy in the backbone model yet greatly increase its “sturdiness”. We conduct extensive experiments to illustrate the effectiveness of our solutions. For instance, we achieve the state-of-the-art non-fine-tuning accuracy on CIFAR-10 with only 40% to 60% time cost (as shown in Figure 1). We improve the accuracy of the state-of-the-art ReLU replacement scheme [2] by 3%. Compared to previous schemes, our methods have the following advantages:

• •

  Our obtained models are based on generic model structures rather than being specifically fine-tuned for particular PANNs. That means the same model can perform as the backbone (or pre-trained) model for various approximation precision and methods to enhance their performance without adjustment. This lowers the training cost and ensures better compatibility with other approaches.

• •

  Our training methods are also general without restricting to particular model structures or approximation methods. This allows for a variety of fine-tuning-based schemes to be further optimized with our approaches.

The rest of the paper is organized as follows. Section 2 gives the theorem and explanation of how approximation errors affect PANN. Section 3 introduces the related works. Section 4 describes the preliminary of our study. Section 5 provides solutions to improve low-precision PANN’s accuracy. Section 6 gives the experiment results. Finally, in Section 7, we conclude this paper and discuss potential avenues for future research.

Replacing non-polynomial functions with polynomials has become a desirable tool for applying cryptography to neural networks. Early studies often adopt simple (low-degree) polynomials in approximation. For example, CryptoNets and HCNN utilized the square function to replace activation functions [4, 7]. CryptoDL used degree 2 and degree 3 polynomials to approximate the ReLU function [13], while Faster Cryptonets leveraged minimax approximation with degree two [14]. nGraph-HE and Delphi adopt quadratic approximations to approximate activation functions [8, 1]. These methods can handle only simple model (i.e. less than 10 layers) and tasks (i.e. classification on MINIST) because the non-negligible errors accumulated throughout layers can seriously affect the model outputs.

To address this, further studies proposed highly precise approximation to reduce the approximation error and can achieve the same accuracy as the backbone model [5, 15]. A common method for these precise approximations is Minimax approximation [9, 10, 16], which combines many small-degree polynomials for approximation to reduce the computation cost. However, the reduced computational overhead of precise approximation is still unbearable. Increasing PANNs’ accuracy while reducing overheads remains an important issue.

When seeking to improve the performance of PANN, many studies fine-tune (or train) models directly on PANN. Earlier studies such as CryptoNets and Faster Cryptonets directly train models on neural networks with low-degree polynomials activation functions [4, 14]. The models obtained are essentially new models with a customized design for PANN (both in terms of structure and parameters) rather than being approximations of commonly used models. The limitations of simple polynomials activation and the customized structure make these models hard to tackle complex tasks. To better suit practical applications, recent studies tend to input pre-trained models as a starting point and then fine-tune them on PANN. For example, SNL and AutoReP fine-tune models after replacing a partial of ReLU functions with polynomials with one or two degree [17, 2]. AutoFHE fine-tunes models on precise PANN to achieve better performance and lighten the requirements for precision [11]. Another study fine-tuning models after carefully adjusting the model structure for low-degree polynomial approximations has also obtained a high accuracy [3].

Despite its efficiency in improving PANN accuracy, several issues are involved. Firstly, polynomials are not appropriate for training when used as activation functions. The derivative of these polynomials is unbounded, which can lead to unstable values during gradient descent and get unexpected results (i.e. the parameter instability issues in AutoReP [2]). Secondly, a fine-tuned model is customized for the weights and polynomials it’s trained on. The model must be retrained whenever you want to adjust the PANN’s approximation precision and overhead (discussed in Section 4.2), which will result in additional training costs. Thirdly, generic model structures and activation functions are usually well-validated. Designing extra network structures for PANN results in higher design and test costs and is undesirable for other applications. Therefore, our study prefers to solve PANN’s accuracy reduction problems on generic model structures crossing different approximation methods and precision requirements without fine-tuning.

Reducing the number of activation functions in PANN can significantly reduce computation costs since they are the main part requiring approximation and cryptographic operations. SNL first achieves this by designing a parametric ReLU (PReLU) and applying a loss function to gradually adjust ReLU functions to linear functions [17]. This method can reduce the ReLU number in a ResNet-18 model from 491.52K to 49.9K while maintaining 73.75% accuracy (baseline 77.8% on CIFAR-100). AutoRep improves the method by introducing parameterized discrete indicator function, hysteresis loop update function, and distribution-aware polynomial approximation [2], which improves the accuracy to 75.48%.

Though ReLU replacement can significantly reduce the computational overhead of PANN, two factors reduce the accuracy of obtained PANNs in this process. First, the structure of the pre-trained model is different from PANN. However, the pre-training parameters are not resistant to perturbations caused by structural changes. Although this effect can by reduced by fine-tuning, there is still much room for improvement. Second, the activation functions during backpropagation and the activation functions in the final obtained models are also different. This further reduces PANN’s accuracy.

Actually, the two factors point to the same problem that the model is not resistant to approximation errors (we say “poor sturdiness”). While our solutions, which increase model sturdiness based on general structures, can serve as a supplementary to ReLU replacement schemes. By taking our models as pre-trained and teacher models, the performance of SNL and AutoRep with different ReLU counts can all be further improved.

Bicoptor [18] first proposed an efficient three-party computation (3PC) protocol for ReLU based on truncation and Bicopter2.0 [19] further improved it. For a fix-point input $x$ with $l_{x}$ bit length, the protocol will right-shift the complement code of $x$ for $l_{x}$ times with truncation and get $l_{x}$ shares. By securely checking if zero appears in these shares, the protocol will determine the sign of $x$ (i.e., $x=0b00001010$ right shift 4 bit will get $0$) and enable the computing of $\operatorname{ReLU}(x)$. Since this process involves transferring $lx$ truncation results, the communication cost will increase with $l_{x}$ ($(+2)l$ bit for Bicoptor, $(l_{x}+1)(l_{x}+1)$ for Bicoptor2.0).

This means choosing a suitable (small) $l_{x}$ in ReLu protocol can effectively reduce the communication overhead at the cost of computation precision. We considered this error also a kind of approximation error. Though it’s different from polynomial approximation, the effects is still in line with the results of our analyses and can apply our solutions.

Differential privacy (DP) protects the privacy of individual tuples in a database [20, 21, 22, 23]. It ensures that attackers cannot infer the membership of any tuple from the released data while the statistical properties are preserved for usage. By applying DP in machine learning, models can be trained without exposing sensitive information [24, 25, 26, 27]. DP-based machine learning does not require time-consuming cryptographic computation and thus is highly practical. However, several serious issues are involved. Firstly, the statistics information of the dataset is also valuable. Especially when the data collection is costly, data owners may be reluctant to disclose any information. Secondly, DP cannot absolutely protect user privacy. Attackers can still get information about some users, though with a low probability. Thirdly, DP aims to hide data in a database, which should contain a large amount of data. This requirement cannot be satisfied in scenarios like privacy-preserving inference.

While cryptographic methods can protect the information of all inputs (both statistical information and individual tuples) and have no requirements for the dataset. In more detail, cryptographic schemes can ensure that every ciphertext in the computation process does not reveal the plaintext information if the attacker doesn’t have the key. Cryptographic techniques such as FHE and MPC can compute the data in the ciphertext format, and the result is generated and stored in ciphertext, which can only be revealed after decryption.

Weight decay is a powerful regularization technique that has been very widely used in training deep neural networks. It can improve model generalization and accuracy [28]. However, recent studies have shown that this benefit comes with side effects [29, 12]. Weight decay has been proved to increase bad minima when applied in training neural networks [29]. Further study has proved that weight decay can lead to large gradient norms at the final phase of training, which often indicates bad convergence and poor generalization [12]. This large gradient norm problem is significant in the presence of scheduled or adaptive learning rates and has been recognized as harmful to neural networks. In our study, we have also confirmed that weight decay reduces the sturdiness of the model, which to some extent, supports these arguments.

We denote a neural network as $\mathbb{F}$, benign inputs and label as ($x$, $y$). we use $\widetilde{\cdot}$ (i.e., $\widetilde{y}$) to represent the values in PANN (with approximation errors). We use $W_{i}$ to denote the $i$-th row vector of a matrix $W$. A small value is represented by $\epsilon$. The error bound for approximation is $2^{-\beta}$ determined by $\beta$. The approximation of $\operatorname{sgn}$ and $\operatorname{ReLU}$ are denoted by $\operatorname{Appsgn}$ and $\operatorname{AppReLU}$ respectively.

Polynomial Approximation of Neural Networks (PANN) is the neural network replacing all (or part of) non-polynomial functions with polynomial approximations. Common approaches for approximation in PANNs include low-degree polynomials, Taylor polynomials, Minimax approximation, etc. Among these methods, low-degree polynomial is the fastest but yields low accuracy, thus generally requires customized model structures and fine-tuning models directly on PANN. In contrast, Minimax approximation with high-degree polynomials is slow but can yield negligible approximation errors, which can achieve PANN with the same accuracy as backbones.

In this paper, we refers to $p(z)$ as a polynomial approximation of a function $g(z)$. The approximation error of this approximation is defined as:

Mixup is the method that introduces interpolated samples to the training set [30], which was proved to help model robustness and generalization [31]. For parameter $\lambda$ and samples $(x,y)$ and $(x^{\prime},y^{\prime})$ randomly selected from the training set, the interpolated sample is:

We propose a solution to enhance “sturdiness” based on Theorem 2.1 that approximation errors on the negative inputs of ReLU increase more loss than those on positive inputs. Intuitively, because some gradients stop updating due to negative inputs to ReLU having zero derivative, we can leak the information of ReLU’s negative inputs to the next layer and can guide the training to approach the stationary point of PANN, thus increasing the sturdiness.

Formally, for a neural network with layered architectures, the input layer is numbered $0$, the output layer is numbered $H$, and the hidden layers $h_{l}$ are numbered $1$, $\dots,H-1$. We denote $z_{l}$ as the input at layer $l$ before the activation function and $z_{H}$ is the output of the neural network, $x_{l}$ as the vector after application of the activation function (to $z_{l-1}$) and $x_{0}=x$ is the neural network input. For normal models, $z_{l}=h_{l}(x_{l})$ and $x_{l+1}=\operatorname{ReLU}(z_{l})$. For our method, we use $\overline{\mathbb{F}}(x)$ to represent the $\mathbb{F}(x)$ replacing all $x_{l+1}$ with $\overline{x}_{l+1}=\operatorname{z_{l}}+\epsilon_{in,l}$, use $\beta^{\prime}$ to represent the amplification due to the multiplication of errors with intermediate values. We are looking for a neural network that satisfies the following:

When trying to implement this method, there are two considerations. First, approximation errors affect every input to ReLU. Second, approximation errors are generated in almost every layer. The wide-range perturbations after accumulated and amplified result in a much larger noise amplitude, which will affect the training and reduce the accuracy of the backbone model (baseline), which can limit the upper bound of PANN accuracy.

Therefore, we consider restricting perturbations only to specific positions by taking into account two specific properties. First, as implied in Theorem 2.1, approximation errors on ReLU’s negative inputs are more harmful. Second, approximation errors are usually the polynomial of ReLU inputs $z$ such that the error amplitude is proportional to the amplitude of $z$. The two properties suggest that adding perturbations to negative values with large magnitudes is the most effective and has minimal effect on the backbone model’s performance.

With the reasons above, we design a noise generator for negative values with large magnitude (NGNV) in activation function inputs during the training phase. For the smallest $r$ (e.g.: 0.3) percent negative values in the ReLU inputs (the negative value with the largest magnitudes), we generate Gaussian noise $\epsilon_{gau}$ to simulate $\epsilon_{sgn}$ and multiply with these values. The products are then multiplied by a parameter $\lambda$ (e.g.: 0.05) and added to ReLU inputs. In other words, for a ReLU input $z$, we generate intra-model perturbations $\delta_{int}$ as:

Considering that the approximation error $\epsilon_{relu}$ has boundaries. We can extract signs from $\epsilon_{g}$ and simulate the worst case by setting a fixed $\lambda$. The process is:

As discussed in Theorem 2.2, weight regularization increases PANNs’ test loss and reduces accuracy as training processes. One potential solution is to use minimal weight regularization combined with early stopping. However, it will lead to poor generalization, which can reduce the accuracy of backbone models (baseline) and ultimately limit PANN’s accuracy by decreasing its upper bound.

To address this, we choose Mixup as a remedy method. Mixup [30] introduces globally linear behavior in-between data manifolds. It can reduce unexpected behavior of neural networks and enhance generalization and robustness by expanding the input set. Our experiments show that Mixup can somewhat compensate for the reduced accuracy due to poor regularization. The test results based on minimal regularization and Mixup are presented in Section 5.2, which shows good performance on some model structures and precision. However, it is important to note that this approach is only effective when regularization is not crucial. For deeper models, the problem of low backbone accuracy under poor regularization is still challenging. Besides, Mixup may decrease PANN’s accuracy for certain models, such as Shufflenetv2. Thus, we regard use of low weight regularization and Mixup as a trade-off.

Evaluation Setup: We conduct tests on PANN with ResNet [32], DLA [33], MobilenetV2 [34], and ShufflenetV2 [35] models for classification tasks on CIFAR-10. We also test ResNet on CIFAR-100 and Tiny Imagenet dataset [36, 37]. Training on CIFAR dataset takes 200 epochs, and on Tiny Imagenet takes 150 epochs. All learning rates begin with 0.1, and were multiplied by 0.1 on epochs 100 and 150 on CIFAR dataset, multiplied by 0.1 on epochs 50 and 100 on Tiny Imagenet. The momentum is 0.9. We test weight decay on 0, 0.0001, and 0.0005. Note that the ResNet-18 models removed the Maxpool layer to suit small images. $\lambda$ for Mixup are selected from distribution $\operatorname{Beta}(0.5,0.5)$. The approximation intervals are $[-50,50]$ for CIFAR and $[-100,100]$ for Tiny Imagenet, except the case values exceed the approximation interval. The average accuracy of the backbone models and PANN with precision $2^{-8}$ and $2^{-9}$ on CIFAR-10 dataset are presented in Table II. The experiments on CIFAR-100 (C100) and Tiny Imagenet are shown in Table III. The highest accuracy for each model and approximation precision are highlighted in bold.

Effects of Weight Regularization: From Table II and Table III, we observe that weight regularization can severely destroy the model’s resistance to approximation errors in various models and precisions. For example, PANN on models trained with weight decay 0 outperforms those with weight decay 5e-4 in nearly all vanilla models, suggesting minimal weight decay. Note that this discipline doesn’t always hold. Poor regularization caused by no regularization can limit backbone models’ accuracy, thus reducing PANN’s accuracy by limiting the upper bound. For example, ResNet-20 models with weight decay 1e-4 can outperform those with zero weight decay in precision $2^{-9}$.

Evaluation of Minimal Regularization with Mixup: Table II and Table III shows that Mixup can effectively compensate for the lack of generalization and reduced backbone accuracy caused by poor regularization. Therefore, models can benefit from strong resistance to approximation errors which come with minimal weight regularization. This method can improve PANN performance in many cases. For example, Mixup can outperform vanilla models on precision $2^{-9}$ with zero weight decay in ResNet-20 and DLA-34. However, this advantage may not always hold. In some cases, Mixup might be harmful to PANN (e.g.: DLA-34, weight decay 0, precision $2^{-8}$).

Evaluation of Negative Inputs Leakage Solution: Table II and Table III prove that NGNV (or NGNV with Mixup), can achieve the best accuracy in all precisions (bolded). It can also improve PANN accuracy significantly in almost all cases, even if the weight decay is large. For instance, on Shufflenetv2 and Mobilenetv2, our models can improve PANN accuracy by up to 60% on weight decay 0 and precision $2^{-8}$, by over 40% on weight decay 1e-4 and precision $2^{-9}$.

Cross-work comparison: Table IV and V provide a cross-work comparison for different schemes. Note that due to the large amount of fine-tuning and structural adjustment involved in the different schemes, it’s difficult to assess the magnitude of errors in them. So we only present the highest accuracy obtained. And in this experiment, our scheme uses the same approximation precision as MPCNN [5]. The results indicate that though our models are trained on the original backbone structure without fine-tuning with approximation functions, they can achieve nearly the same accuracy as the baseline when loaded in PANN. In contrast, model modification and fine-tuning are necessary for other high-accuracy schemes (e.g., reducing the number of layers containing activation functions). ²²2Note that our method has the potential to be integrated with these fine-tuning schemes and enhance their performance, but due to the limited open-source material available in this specific area, we have only conducted tests using a subset of the available schemes.

In a word, by combining these methods, models can exhibit strong “sturdiness” to approximation errors. We can significantly improve low-precision PANN’s accuracy and thus reduce the time cost. Table I illustrates some time costs for PANN with different precision on different models. Previous schemes require at least $2^{-12}$ precision to achieve satisfactory accuracy, but our method only needs $2^{-9}$ (Kindly refer to the appendix for the selection of parameters). The time required for PANN with our models to achieve the state-of-the-art [15, 5] accuracy is given in Figure 4. Our solution can reduce the PANN time cost by 40% to 60% compared to models provided by these schemes. This improvement makes it easier to design cryptographic schemes for various scenarios.

Our method is based on standard structures without fine-tuning (mentioned in Section 1.1), which ensures our model can benefits other schemes by improving sturdiness. For instance, our models can serve as pre-trained and teacher models (for distillation) to enhance the accuracy of ReLU Replacement schemes SNL [17] and AutoReP [2].

Table VI presents the performance of AutoReP and SNL with (or without) our pre-trained ResNet-18 model on CIFAR-100 dataset. We also give the accuracy of Sphynx [17], DeepReduce [38] for comparison. Our models are trained on the backbone structure with weight decay 1e-4 for 200 epochs. Learning rates begin with 0.1, multiplied by 0.1 on epochs 100 and 150. The table shows that our models can enhance both the accuracy of both SNL and AutoRep. For example, we can improve the accuracy of AutoRep with 50K, 12.9K, and 6K ReLUs to near the upper bound (baseline).

We also give the accuracy of SNL and AutoReP with models pre-trained and fine-tuned with different weight decay in Table VII. It shows that approximations with 1-degree (in SNL) and 2-degree (in AutoRep) polynomials also comply with Theorem 2.2, demonstrating that weight decay enlarges the loss increment due to approximation errors. Note that this improvement is achieved without using our training methods in fine-tuning, which means it can be further improved.

The fixed-point bits ($l_{x}$) of ReLU’s inputs are positively correlated with communication overhead in certain MPC schemes due to bit-wise operations such as truncation. By choosing a small $lx$, MPC can significantly reduce communication costs at the expense of accuracy. Our scheme’s increasing model sturdiness can effectively mitigate the accuracy reduction resulting from a small $l_{x}$.

Table VIII shows the accuracy on models with different ReLU inputs bits. The model training uses the same setting as Section 6.2. And we apply the computation methods in [18]. We set the first half of the bits in lx represent integers and the second half represent decimals.

The table shows that this case still experiencing external losses due to weight decay. Though the large weight decay outperforms the small weight decay in some precision because of the baseline difference, the reduced accuracy in weight decay 1e-4 is still smaller than that in 5e-4. Furthermore, by applying our methods in training backbone, models can achieve the desired accuracy at much lower precision, ultimately reducing communication overhead.