Securing Neural Networks with Knapsack Optimization
MLaaS Service Providers (SPs) holding a Neural Network would like to keep the
Neural Network weights secret. On the other hand, users wish to utilize the
SPs' Neural Network for inference without revealing their data. Multi-Party
Computation (MPC) offers a solution to achieve this. Computations in MPC
involve communication, as the parties send data back and forth. Non-linear
operations are usually the main bottleneck requiring the bulk of communication
bandwidth. In this paper, we focus on ResNets, which serve as the backbone for
many Computer Vision tasks, and we aim to reduce their non-linear components,
specifically, the number of ReLUs. Our key insight is that spatially close
pixels exhibit correlated ReLU responses. Building on this insight, we replace
the per-pixel ReLU operation with a ReLU operation per patch. We term this
approach 'Block-ReLU'. Since different layers in a Neural Network correspond to
different feature hierarchies, it makes sense to allow patch-size flexibility
for the various layers of the Neural Network. We devise an algorithm to choose
the optimal set of patch sizes through a novel reduction of the problem to the
Knapsack Problem. We demonstrate our approach in the semi-honest secure 3-party
setting for four problems: Classifying ImageNet using ResNet50 backbone,
classifying CIFAR100 using ResNet18 backbone, Semantic Segmentation of ADE20K
using MobileNetV2 backbone, and Semantic Segmentation of Pascal VOC 2012 using
ResNet50 backbone. Our approach achieves competitive performance compared to a
handful of competitors. Our source code is publicly available:
https://github.com/yg320/secure_inference.
Yakir Gorski, Amir Jevnisek, Shai Avidan
# Securing Neural Networks with Knapsack Optimization

###### Abstract

Deep learning inference brings together the data and the Convolutional Neural Network (CNN). This is problematic in case the user wants to preserve the privacy of the data and the service provider does not want to reveal the weights of his CNN. Secure Inference allows the two parties to engage in a protocol that preserves their respective privacy concerns, while revealing only the inference result to the user. This is known as Multi-Party Computation (MPC).

A major bottleneck of MPC algorithms is communication, as the parties must send data back and forth. The linear component of a CNN (i.e. convolutions) can be done efficiently with minimal communication, but the non-linear part (i.e., ReLU) requires the bulk of communication bandwidth.

We propose two ways to accelerate Secure Inference. The first is based on the observation that the ReLU outcome of many convolutions is highly correlated. Therefore, we replace the per pixel ReLU operation by a ReLU operation per patch. Each layer in the network will benefit from a patch of a different size and we devise an algorithm to choose the optimal set of patch sizes through a novel reduction of the problem to a knapsack problem.

The second way to accelerate Secure Inference is based on cutting the number of bit comparisons required for a secure ReLU operation. We demonstrate the cumulative effect of these tools in the semi-honest secure 3-party setting for four problems: Classifying ImageNet using ResNet50 backbone, classifying CIFAR100 using ResNet18 backbone, semantic segmentation of ADE20K using MobileNetV2 backbone and semantic segmentation of Pascal VOC 2012 using ResNet50 backbone. Our source code is publicly available: [https://github.com/yg320/secureinference](https://github.com/yg320/secureinference).

## 1 Introduction

With the recent rise in popularity of machine learning algorithms, an increasing number of companies have begun offering machine learning as a service (MLaaS). This trend extends to convolutional neural network (CNN)-based computer vision algorithms as well.

In a typical scenario, two parties, a client with an image and an ML-provider server with a deep-learning model, seek to collaborate for the purpose of running inference. However, privacy concerns often impede such cooperation as both the client's image and the server's model may contain information that neither party is willing to share. To overcome this limitation, a Privacy-preserving deep learning framework has been proposed by researchers.

Ideally, secure inference can be done using Homomorphic Encryption (HE) that lets the service provider work directly on encrypted data, with no need for back and forth communication. Although possible in theory, this approach is painfully slow in practice. The vast majority of secure inference algorithms rely on Multi-Party Computation (MPC) that involves multiple rounds of communication. These cryptographic protocols vary in terms of the level of secu

Figure 1: **Reducing the number of DReLUs:** We show the impact of reducing the number of DReLUs (i.e., non-linearities) on performance, compared to inference on a non-secure baseline model. The accuracy for classification tasks (ImageNet in blue, CIFAR100 in red) and mIoU for segmentation (ADE20K in green, Pascal VOC 2012 in purple) relative to the non-secure baseline model is plotted as a function of the DReLU budget (expressed in percentage). Observe that when the percentage of DReLUs is above \(5\%\) we actually improve mIoU for ADE20K. We plot DeepReDuce’s solution for the CIFAR100 dataset in dashed red. Securely evaluated working points are denoted by bold circles.
rity they provide, the type of information they hide and the number of parties involved. These protocols share a common drawback, they are slow compared to their non-secure counterparts and often consume substantial amount of communication bandwidth. Moreover, if not devised well, they often inflict a significant accuracy hit.

One challenge faced by many cryptographic protocols is the cost of a comparison operation (i.e., ReLU [12]) that, in many cases, takes the vast majority of communication bandwidth. Therefore, we aim to reduce the cost and the amount of these operations. Our key insight is that the ReLU outcome of nearby pixels is highly correlated. Therefore, we propose to use a single ReLU operation per patch. The question now becomes what should be the optimal patch size? To address this we evaluate multiple patch sizes per layer and use a novel, Knapsack-based optimization strategy, to find an optimal configuration of patch sizes for all layers in the network.

Additionally, we propose and implement a straightforward and practical approach to lower the cost of comparison operations, which can be applied to various protocols. We achieve this by disregarding some of the most and least significant bits of the activation layers.

Our method has been successfully applied to four distinct tasks: (1) Classifying ImageNet using ResNet50 backbone (2) classifying CIFAR100 using ResNet18 backbone (3) semantic segmentation of ADE20K using DeepLabV3 with MobileNetV2 backbone, and (4) semantic segmentation of Pascal VOC 2012 using DeepLabV3 with ResNet50 backbone. We demonstrate that by accepting a slight decrease in performance, we can reduce the number of comparisons by over \(90\%\).

Figure 1 shows the trade-off between a drop in DReLU (which is the step function that returns 1 for positive values and 0 for negative values) and performance. As can be seen, using just \(10\%\) of the DReLU operations leads to a drop of \(5\%\) in accuracy for the classification tasks, about \(2\%\) for the Pascal VOC 2012 segmentation task and improves mIoU of ADE20K segmentation. Since ReLU operations contribute the most to communication bandwidth, we save a considerable amount of network traffic.

With our implementation of the semi-honest secure 3-party setting of the SecureNN protocol on three instances within the same AWS EC2 region, the image classification models can be executed in about 5.5 seconds on ImageNet and 1.5 seconds on CIFAR100, and the semantic segmentation models can be executed in about 32 seconds on ADE20K and 85 seconds on Pascal VOC 2012, with performance comparable to OpenMMLab's non-secure models [6, 7]

To summarize, the main contributions of this paper are:

* We develop a generic, Knapsack-based, data-driven algorithm that greatly reduces the number of comparisons in a given network.
* We build and release an optimized, purely Pythonic, wrapper code over OpenMMLab based packages that secures models taken from their model zoo.
* We demonstrate a significant decrease in run-time at the cost of a slight reduction in accuracy for four of OpenMMLab's most common models and datasets.
* We present a secure semantic segmentation algorithm that preserves the model accuracy while being 10 times faster than a comparable secure baseline protocol.

## 2 Related Work

Privacy Preserving Deep LearningThe research on privacy preserving deep learning shows significant differences across various aspects. These include the number of parties involved, threat models (Semi-honest, Malicious), supported layers, techniques used (e.g., Homomorphic encryption, garbled circuits, oblivious transfer, and secret sharing) and the capabilities provided (training and inference).

The pioneers in the field of performing prediction with neural networks on encrypted data were CryptoNets [15]. They employed leveled homomorphic encryption, replacing ReLU non-linearities with square activations in order to perform inference on ciphertext. SecureML [39] utilized three distinct sharing methods: Additive, Boolean, and Yao sharing, along with a protocol to facilitate conversions between them. They used linearly homomorphic encryption (LHE) and oblivious transfer (OT) to precompute Beaver's triplets. MiniONN [34] proposed to generate Beaver's triplets using additively homomorphic encryption together with the single instruction multiple data (SIMD) batch processing technique. GAZELLE [27] suggested to use packed additively homomorphic encryption (PAHE) to make linear layers more communication efficient. FALCON [1] achieved high efficiency by running convolution in the frequency domain, using Fast Fourier Transform (FFT) based ciphertext calculation. Chameleon [42] builds upon ABY [41] and employs a Semi-honest Third Party (STP) dealer to generate Beaver's triplets in an offline phase. SecureNN [48] suggested three-party computation (3PC) protocols for secure evaluation of deep learning components. The Porthos component of CrypTFlow [32] is an improved semi-honest 3-party MPC protocol that builds upon SecureNN. FALCON [49], combines techniques from SecureNN and ABY\({}^{3}\)[38], replacing the MSB and Share Convert protocols in SecureNN with cheaper Wrap\({}_{3}\) protocols.

ReLU SavingsThere are several methods to reduce ReLU expense through non-cryptographic means. CryptoDL [23] and Blind Faith [30] proposed to use polynomial approximations to approximate non linear functions.
In [45], the authors proposed to use partial activation layers and only apply ReLUs to a portion of the channels. DELPHI [37] suggested to quadratically approximate ReLU layers. They designed a planner that automatically discovers which ReLUs to replace with quadratic approximations using neural architecture search (NAS). SAFENET [35] suggested a more fine-grained channel-wise activation approximation. They exploited Population Based Training (PBT) [25] to derive the optimal polynomial coefficients. In CryptoNAS [14] the authors developed a NAS over a fixed-depth, skip connections architectures to reduce ReLU count. The current state-of-the-art method for ReLU pruning, DeepReDuce [26], proposed a three-step process to decrease the number of ReLUs. Like our method, it uses a trained network to guide the placement of ReLU reduction and incorporates knowledge distillation to enhance accuracy in the pruned network. In [22], which is the work that has most influenced us, the authors used statistics from neighboring activations and shared DReLUs among them. However, they did not provide a satisfactory method for determining the neighborhood. Finally, Circa [13] proposed the Stochastic ReLU layer and showed that we can use prior knowledge about the absolute size of activations to reduce the complexity of garbled circuits while maintaining a low error probability. They also demonstrated that neural networks can handle clipping of the least significant bits, which further reduces circuit complexity. While we share similar observations with Circa, our approximate ReLU layer differs in its application, as we ignore the shares' most significant bits instead of the negligible probability event of a shares summation overflow. This enables us to better control bandwidth with error probability, which is especially useful when reducing shares precision, as in [49].

Network PruningNetwork pruning is a technique applied to reduce model complexity by removing weights that contribute the least to model accuracy. Our method can be seen as a specialized pruning technique that targets DReLU operations instead of weights. Different approaches use various measures of importance to identify and eliminate the least important weights, such as magnitude-based pruning (e.g., [17, 18]), similarity and clustering methods (e.g., [47, 43, 10]), and sensitivity methods (e.g., [19]). Some methods, including ours, score filters based on the reconstruction error of a later layer (e.g., [21, 36, 28]). The pioneers of Knapsack based network pruning [4] used the 0/1 Knapsack solution to eliminate filters in a neural network, whereby an item's weight was based on the number of FLOPs, and its value was based on the first-order Taylor approximation of the change to the loss. Similarly, in [46] the authors optimized network latency using the Knapsack paradigm. The authors of [24] applied Integer Programming to optimize post training quantization.

## 3 Method

Our method effectively secures a pre-trained model. It accomplishes this by replacing the ReLU layers with a less expensive layer, while minimizing any distortion (i.e., error) to the network. Our work is based on SecureNN [48] and, for completeness, we refer the readers to a brief summary of that protocol in the appendix.

### Approach

Following SecureNN notations, we refer to the ReLU decision of an activation unit as its DReLU. Mainly:

\[DReLU(x)=\begin{cases}1&\text{if }x\geq 0\\ 0&\text{otherwise}\end{cases} \tag{1}\]

Then, ReLU is defined as:

\[ReLU(x)=x\cdot DReLU(x) \tag{2}\]

Block ReLU (bReLU)The key insight that allows for a reduction in the number of DReLUs is that neighboring activation units tend to have similar signs. As depicted in Figure 2, this is demonstrated by the probability that two activation units at a specific spatial distance will share their sign (Segmentation on the ADE20K dataset with MobileNetV2 backbone). To exploit this property, we propose the block ReLU (bReLU) layer.

In this layer, we utilize the local spatial context of an activation unit to estimate its ReLU decision. Each activation channel is partitioned into rectangular patches of a specified size.

Figure 2: **Activation correlation** The probability that two activation units in the same channel have the same sign, based on their spatial distance, calculated using the activation statistics of a trained MobileNetV2. As can be seen, the lowest probability is about \(0.7\).
Let \(x\) be an activation unit, Let \(P(x)\) be its neighborhood induced by this partition. We define the patch ReLU decision (pDReLU) as the DReLU of the mean activation value of the neighbourhood. I.e.,

\[pDReLU(x)=DReLU(\frac{1}{|P(x)|}\Sigma_{a\in P(x)}a) \tag{3}\]

The ReLU decision of each pixel in the neighborhood is then replaced by the patch decision of that pixel.

\[bReLU(x)=x\cdot pDReLU(x) \tag{4}\]

As a result, we perform a single DReLU operation in the \(P(x)\) patch, instead of \(|P(x)|\) DReLU operations. Figure 3 illustrates a \(2\times 3\) bReLU operating on a \(6\times 6\) activation channel.

Knapsack OptimizationOne can use patches of different size for different channels in the network, and our goal is to determine the optimal size for each individual channel. We formulate this problem as a discrete constraint optimization problem, where we set a desired DReLU budget \(\mathcal{B}\), and attempt to allocate this budget in the most efficient manner.

In what follows, the term \(C_{i}\) denotes the \(i^{th}\) channel in a neural network such that all of its channels are enumerated across all of its layers. To illustrate, in a network consisting of two layers, with the first layer having 32 channels and the second layer having 64 channels, \(C_{40}\) would refer to the \(8^{th}\) channel in the second layer.

Now, we define \(P_{i}\) as the list of patch-sizes available for selection by \(C_{i}\), and \(P_{ij}\) as the \(j\)-th item within this list. \(\mathcal{D}(i,j)\) is then defined as the distortion caused to the network as a result of replacing the ReLUs of \(C_{i}\) with a bReLU of patch size \(P_{ij}\).

Formally, let \(F\) be a neural network, and let \(F^{i,j}\) denote the network obtained by replacing the ReLUs of \(C_{i}\) of \(F\) with a bReLU of a patch size \(P_{ij}\). Let \(F(X)\) and \(F^{i,j}(X)\) be the last activation layer of \(F\) and \(F^{i,j}\) operating on an image \(X\). Then the distortion \(\mathcal{D}(i,j)\) is defined as:

\[\mathcal{D}(i,j)=\mathbb{E}[\|F^{i,j}(X)-F(X)\|^{2}] \tag{5}\]

Specifically, we perform a forward pass on the network \(F\) with image \(X\). Then, for each channel in each layer and for each candidate patch size, we perform a forward pass with only this change to the original network.

We define the cost \(\mathcal{W}(i,j)\) as the number of DReLUs remaining in \(C_{i}\) of \(F^{i,j}\), which is a function of both the patch-size as well as the activation channel size. Finally, we define \(m\) as the number of channels in \(F\), and by \(S_{i}\) the set of indices \(\{1,...,|P_{i}|\}\). Using our notations, the minimization variant of the Multiple-Choice Knapsack Problem [29] is formulated as:

\[\min_{\varphi_{ij}} \sum_{i=1}^{m}\sum_{j\in S_{i}}\mathcal{D}(i,j)\cdot\varphi_{ij}\] (6) subject to \[\sum_{i=1}^{m}\sum_{j\in S_{i}}\mathcal{W}(i,j)\cdot\varphi_{ij} \leq\mathcal{B},\] \[\sum_{j\in S_{i}}\varphi_{ij}=1,\quad i=1,...,m,\] \[\varphi_{ij}\in\{0,1\},\quad i=1,...,m,\quad j\in S_{i}\]

\(\varphi_{ij}=1\) indicates that the \(P_{ij}\) patch size has been selected for \(C_{i}\). The second constraint ensures that no multiple patch sizes can be selected for this channel. This problem is naturally solved using a dynamic programming approach with a table \(DP\) consisting of \(m\) rows and \(\mathcal{B}\) columns. The table \(DP\) is iteratively populated using the recursive formula:

\[DP[i,j]=\min_{1\leq l\leq S_{i}}\{DP[i-1,j-\mathcal{W}(i,l)]+\mathcal{D}(i,l)\} \tag{7}\]

Since this table is column independent, we are able to parallelize finding the solution \(DP[m,\mathcal{B}]\). We use GPU implementation to take full advantage of this property.

AnalysisUsing Equation 5 makes the strong assumption that the bReLU distortion is additive. That is, that the distortion caused by the ReLU-bReLU replacement in two channels equals to the sum of distortions caused by the replacement in each channel individually. Interestingly, we can actually use a less strict assumption.

Figure 3: **Block ReLU (bReLU):** An illustration of the bReLU layer (Equation 4). In bReLU the ReLU decision is based on the average of all activations in the block (i.e., patch). Left: a \(6\times 6\) input activation channel overlaid by the induced bReLU partitioning of a \(2\times 3\) patch size. Right: the output activation channel. As can be seen, the average of the top left patch values is negative, therefore, all the activations in this patch are zero. The average of the top right patch values is positive, therefore, all the values in this patch are preserved, including the erroneous -0.6 value. In this example we execute 6 DReLU operations, as opposed to the original 36, and as a result, we introduce 12 DReLU sign flips.
Formally, let \(L\) be a list of indices corresponding to the channels patch size, such that \(|L|=m\), and \(L[i]\in S_{i}\). We denote by \(F^{L}\) the network that is obtained by replacing the ReLUs of each channel \(C_{i}\) of \(F\) with a bReLU with a patch size of \(P_{i,L[i]}\).

We define the additive distortion \(\mathcal{D}_{a}(L)\) as:

\[\mathcal{D}_{a}(L)=\sum_{i=1}^{m}\mathcal{D}(i,L[i]) \tag{8}\]

and the real distortion \(\mathcal{D}_{r}(L)\) as:

\[\mathcal{D}_{r}(L)=\mathbb{E}[\|F^{L}(X)-F(X)\|^{2}] \tag{9}\]

We would like to have some indication that the argument that minimizes \(\mathcal{D}_{a}(L)\) roughly minimizes \(\mathcal{D}_{r}(L)\) as well. A sufficient condition for that is if the real distortion is a monotonically non-decreasing function of the additive distortion.

Formally, Let \(L1\) and \(L2\) be any two lists of indices satisfying the DReLU budget constraint \(\mathcal{B}\). Then, our assumption is that:

\[\mathcal{D}_{a}(L1)\leq\mathcal{D}_{a}(L2)\rightarrow\mathcal{D}_{r}(L1)\leq \mathcal{D}_{r}(L2) \tag{10}\]

The accuracy of this assumption determines how close the Knapsack solution is to the optimal solution.

We verified our assumption on the ImageNet classification task using ResNet50. We characterized the relationship between \(\mathcal{D}_{a}\) and \(\mathcal{D}_{r}\) using randomly drawn \(L\) lists, with the underlying implicit assumption that this characterization is preserved around minimum points. Specifically, we selected a random patch index list \(L\), and calculated both \(\mathcal{D}_{a}(L)\) and \(\mathcal{D}_{r}(L)\) using \(512\) samples. This procedure was repeated for \(3000\) such lists \(L\), and the results are shown in Figure 4. As can be seen, the real distortion is roughly a monotonically non-decreasing function of the additive distortion. This indicates that our assumption is reasonable.

Homogeneous ChannelsWe noticed that the activation units that make up certain channels rarely have different sign values. To make use of this characteristic, we augment the items in each \(P_{i}\) list with an additional special item: the identity channel, with a weight of \(\mathcal{W}=0\), since no DReLUs are employed.

### Approximate DReLU

In protocols that utilize additive sharing, the cost of a comparison operation is usually proportional to the number of bits used to represent the shares, as is evident in the depth of a Yao's Garbled Circuit, and in SecureNN-based protocols. It has been previously observed [40, 13] that by tolerating a small probability of DReLU error, the complexity of comparison operations can be significantly reduced.

The main idea is that when comparing two uniformly distributed \(n\)-bit integer numbers, the outcome can be approximated with a negligible error probability of \(\frac{1}{2^{n-k+1}}\), even if \(k\) of the least significant bits are ignored. This is done simply by comparing the remaining \((n\)-\(k)\) bits.

Moreover, when dealing with numbers that are not uniformly distributed, if we have prior knowledge about the probability of their absolute sum exceeding a certain limit, we can reduce the number of most significant bits we consider accordingly, while bounding the probability of error. This is because in 2's complement numbers, as the probability of a number having high values decreases, the probability of the \(i^{th}\) most significant bit being the same as the \((i-1)^{th}\) most significant bit increases. In 2-party additive sharing protocols, the two numbers are the shares, while their comparison is the DReLU taken over their sum.

The activation values of deep learning networks often exhibit this behavior. The decimal portion tends to be uniform, and the absolute values tend to be low. In Figure 5, we can empirically observe the behavior of ResNet50 with bReLU layers trained on the ImageNet dataset by examining millions of activation values. The graph displays the probability of a DReLU error as a function of the number of most and least significant bits ignored. According to the analysis, we can safely disregard 43 of the most significant bits and 5 of the least significant bits, resulting in a DReLU error probability of about \(5e-4\). The empirical activation statistics, together with our observation enable us to differentiate protocols that require high precision (e.g., Conv2d) from protocols that require low precision (e.g., Private Compare).

### Other Non-Linear Layers

MaxPool and ReLU6MaxPool and ReLU6 are computationally costly layers with limited benefits. To enhance the performance of our algorithm, we substitute ResNet's MaxPool layer with an AveragePool layer and MobileNet's

Figure 4: **Distortion approximation:** The relationship between actual distortion and estimated distortion for ImageNet classification using the ResNet50 backbone, determined through \(3000\) random trials. Each point represent one evaluation of Equation 8
ReLU6 layers with ReLU layers. If required, we also adjust the models through fine-tuning.

### Security Analysis

Our method offers the same level of security as the underlying cryptographic protocol, SecureNN in our case. Accordingly, we protect both the client image and server model weights under the relevant thread model. However, we do make the patch sizes public, which typically consists of approximately 40K discrete parameters that we infer based on the training data statistics. It is important to note that any hyperparameters or architectural structures that are revealed may result in some degree of training data information leakage. Therefore, researchers should be aware of this gray area and determine what level of model disclosure is acceptable. Other than image size, the user's image information is entirely protected.

## 4 Experiments

Implementation DetailsOur algorithm was evaluated on four different tasks: (1) Classifying ImageNet [9], using ResNet50 [20] backbone, (2) classifying CIFAR100 [31], using ResNet18 backbone, (3) ADE20K [50] semantic segmentation using DeepLabV3 [5] with MobileNetV2 [44] backbone and (4) Pascal VOC 2012 [11] semantic segmentation using DeepLabV3 and ResNet50 backbone.

Other than CIFAR100, trained models were obtained from OpenMMLab's model zoo and served as our baseline. As MMClassification does not provide a baseline ResNet18 model on the CIFAR100 dataset, we trained two models from scratch (See: Section 4.1 for more details)

Prior to disotortion calculation, ResNet50's MaxPooling layer was replaced with an AveragePooling layer and fine-tuned for 15 epochs for ImageNet and 3K iterations for Pascal VOC 2012 at a learning rate of \(1e-4\), while MobileNetV2's ReLU6 layers were replaced with ReLU layers without further tuning.

The per channel, per patch-size distortions were then calculated using 512, 2048, 48 and 30 samples for ImageNet, CIFAR100, ADE20K and Pascal VOC 2012, respectively. The size of a patch-size list depends on the size of the channel. Channels of size \(512\times 512\) can have as many as \(103\) possible patch-sizes, while channels of size \(4\times 4\) will have as little as \(8\) patch-sizes to consider. The optimal patch-sizes were then determined using our CUDA-based Multiple-Choice-Knapsack solver.

Finally, the ReLU layers were replaced with bReLU layers, parameterized by the Knapsack-optimal patch-sizes, and the models were retrained for an additional 25, 120 epochs for ImageNet and CIFAR100, using a low learning rate of \(5e-3\) with a gradual step-based decrease toward \(1e-4\). For ADE20K and Pascal VOC 2012 we further trained for 40K, 20K steps, respectively, using learning rate of \(5e-4\) with a gradual polynomial decrease toward \(1e-4\). A warmup [16] low learning-rate for all tasks was applied. With the exception of the learning rate scheduling, we inherited all other parameters as they were in the OpenMMLab configuration files. This includes using batch sizes of 256 for ImageNet, 128 for CIFAR100, and 16 for ADE20K and Pascal VOC 2012. In addition, we followed the common practice of utilizing the additional augmentation training data available in Pascal VOC 2012.

Figure 5: **Approximate DReLU:** The probability of a DReLU error as a function of the number of most and least significant bits ignored. As can be seen, we can safely disregard 43 of the MSB bits and 5 of the LSB bits. We use 64 bits to represent numbers, so we can only evaluate \(16=64-43-5\) bits.

Figure 6: **Runtime and Bandwidth Vs. Performance:** We measure the impact of our approach on runtime, bandwidth and performance relative to the baseline secure model. The factor reduction in bandwidth (top) and runtime (bottom) at different accuracy points for classification (ImageNet in blue, CIFAR100 in red) and mIoU points for segmentation (ADE20K in green, Pascal VOC 2012 in purple). Securely evaluated working points are denoted by bold circles.
EvaluationThe evaluation metrics for segmentation and classification tasks are mIoU and accuracy, respectively. The number of validation images varies among different datasets, with ImageNet containing 50K images, CIFAR100 containing 10K images, ADE20K containing 2K images, and Pascal VOC 2012 containing 1449 images.

As per SecureNN, we conducted inference over 3 Amazon EC2 c4.8xlarge Ubuntu-running instances in the same region (eu-west-1). We developed our own Numba [33] based Python implementation of the SecureNN protocol. We use shares over the \(\mathbb{Z}_{2^{64}}\) ring and our comparison protocol is run over the \(\mathbb{Z}_{67}\) field. We used 16 bits approximate-DReLU for classification tasks (ignoring 5 LSBs and 43 MSBs) and 20 bits for segmentation tasks (ignoring 44 MSBs). To implement the secure bReLU layer, we made the trivial conversion of the MatMul protocol from [48] to support scalar-vector multiplication as well.

Our measurements include both the online and offline phases of Beaver's triples generation. We allocate 12 bits for segmentation and 16 bits for classification to represent the values' decimal part. We avoided sending truly random shares between parties, and computed them as the output of a pseudo random function (prf).

Since the image sizes in our segmentation tasks are not constant, we measured the runtime and bandwidth using the average size of validation images, as determined by the MMSegmentation data pipeline. The image size was set to \(512\times 673\times 3\) for ADE20K and \(512\times 713\times 3\) for Pascal VOC 2012. For classification tasks, we used image sizes of \(32\times 32\times 3\) for CIFAR100 and \(224\times 224\times 3\) for ImageNet. We obtained the runtime measurements for each case by averaging three samples for segmentation and ten samples for classification. The baseline models we used include neither bReLU nor approximate ReLU. The MobileNet baseline model has ReLU non-linearities in place of ReLU6. Finally, the ReLU MaxPool switching optimization was performed in ResNet models (see [32] for more details).

Figure 1 illustrates the relationship between a reduction in DReLU operations and the relative decrease in mIoU (for segmentation) and accuracy (for classification) from baseline models. We have securely evaluated some of the working points in the graph which are indicated by bold circles. We further emphasize that this relationship is not specific to any particular protocol. Interestingly, in the case of ADE20K dataset, mIoU was actually better than the non-secure baseline OpenMMLab model, when the number of DReLU evaluations was above \(5\%\).

Figure 6 demonstrates the cumulative effect of the different components of our algorithm on run-time and performance (top) as well as bandwidth and performance (bottom) for these four tasks in the semi-honest secure 3-party setting of SecureNN. Similar to Figure 1, secure evaluations are indicated by bold circles. We refer the readers to the Section 4.2 for a comparison between secure and non-secure evaluation.

Figure 7 displays the distribution of patch sizes for the top 10 patches selected by our Multiple-Choice-Knapsack solver on the ADE20K dataset using MobileNetV2. Observe how the wide and short patch sizes are consistent with the higher horizontal activation correlation, as demonstrated in Figure 4.

Table 1 displays the cost of communication for the various layers in the SecureNN protocol, with the CrypTFlow convolution optimization being utilized. We define \(h\) as the activation dimension. \(i\) and \(o\) are the number of activation input and output channels. \(f\) is the convolution kernel size. \(\ell\) is the number of bits used to represent activation values. \(\ell^{*}\) is the number of bits used in approx. DReLU. \(P\) is a list of patch-sizes such that \(|P|=o\). We set \(r=6\)log\(\ell+14\ell\) (3,968 in our case), \(r^{*}=6\)log\(\ell^{*}+14\ell\) (1,664 in our case) and \(q=\frac{1}{o}\sum_{i=1}^{o}\frac{1}{P_{1}}\), the ratio of DReLUs left. The communication cost of ReLU and bReLU is defined as the communication that remains after DReLU and pDReLU have been applied. The communication cost of some typical values (\(i=128,o=256,f=3,h=64,\ell=64,\ell^{*}=16,q=0.1\)) is shown. The complexity reduction caused by using identity channels is not shown. Finally, theoretically, in approximate DReLU layer, we can further reduce communication by decreasing the \(\mathbb{Z}_{p}\) field size, as the only requirement is that \(p\) is a prime such that: \(p>2+\ell^{*}\).

The usage of bReLU layer does not decrease the number of communication rounds required in comparison to a standard ReLU layer. This holds true irrespective of whether or not approximate DReLU is utilized. As a result, the bReLU layer incurs a cost of 10 communication rounds. We refer the readers to [48] for more details.

\begin{table}
\begin{tabular}{|c|c|c|c|} \hline  & Layer & Communication & Typical \\  & & & Values \\ \hline \hline
1 & Conv2d\({}_{h,i,f,o}\) & \(h^{2}(2i+o)\ell\) & 21MB \\  & & \(+2f^{2}oi\ell\) & \\ \hline
2 & DReLU\({}_{h,o}\) & \(h^{2}ro\) & \(520\)MB \\
3 & App. DReLU\({}_{h,o}\) & \(h^{2}r^{*}o\) & \(218\)MB \\ \hline
4 & pDReLU\({}_{h,o,P}\) & \(h^{2}rqo\) & \(52\)MB \\
5 & App. pDReLU\({}_{h,o,P}\) & \(h^{2}r^{*}qo\) & \(22\)MB \\ \hline
6 & ReLU\({}_{h,o}\) & \(5oh^{2}\ell\) & \(42\)MB \\
7 & bReLU\({}_{h,o,P}\) & \((3+2q)oh^{2}\ell\) & \(27\)MB \\ \hline \hline
8 & Conv2d+ReLU & (1) + (2) + (6) & \(583\)MB \\
9 & Conv2d+bReLU & (1) + (5) + (7) & \(70\)MB \\ \hline \end{tabular}
\end{table}
Table 1: **Communication convexity:** Communication complexity of Conv2D and ReLU layers. Our approximation (line (9)) requires almost an order of magnitude less communication bandwidth, compared to the baseline approach (line (8)). See discussion and details in the text.
### Comparison with Previous Methods

The DeepReduce group [26] developed a new approach to pruning ReLU using a measure of ReLU criticality and distilled learning. They demonstrated the relationship between ReLU budget and CIFAR100 accuracy using their method. As DeepReduce outperformed all previous methods (E.g. [37, 35, 14]), we compared our approach to theirs. DeepReDuce employed different ResNet18 variants for different budgets by decreasing the activation dimensions. We adopted a similar strategy, training two ResNet18 models on the CIFAR100 dataset: a standard ResNet18 and a lightweight version with half the activation sizes in each dimension (height, width, channels). We trained the networks for 200 epochs using SGD with a learning rate of 0.1, momentum of 0.9, and weight decay of \(1e-3\), reducing the learning rate by a factor of 5 in epochs 60,120 and 160. We used the vanilla ResNet18 for high DReLU budget (\(>5\%\)) and the lightweight-ResNet18 for the rest. We then applied our Knapsack algorithm with the appropriate DReLU budget based on the distortion of 2048 samples, and fine-tuned it for an additional 120 epochs using an initial learning rate of \(5e-3\) which was warmed up for 5 epochs and reduced by a factor of 4 every 30 epochs. We apply momentum of 0.9, and weight decay of 1e-3.

The results are presented in Figure 1, along with DeepReduce's results. The plotted graph displays the accuracy of secure evaluation for CIFAR100, as it varies with the DReLU budget. The results demonstrate that, for the majority of the budget range, our method outperforms DeepReduce. In addition, Figure 8 shows the pruned DReLU distribution across layers for both our method and DeepReduce. DeepReduce prunes ReLUs at the layer level, effectively making the network shallower. While this may be convenient for linear layer merging, it goes against the trend of working with deeper networks (E.g., [3, 2]). Interestingly, as can be seen later in Section4.2, CIFAR100 is the dataset that benefits the least from fine-grained DReLU budget characterization at the channel level. Lastly, we believe that our method, like DeepReduce's, can also benefit from knowledge distillation.

### Ablation Study

Alternative Patch Sizes SetsWe investigate the effect on performance of using a different set of patch-sizes instead of the Knapsack optimal patch-sizes. Table 2 presents a comparison of three different patch size sets: (1) A set of naive \(4\times 4\) constant patch sizes, (2) Channel-shuffled Knapsack patch sizes, which are similar to Knapsack-optimized patch sizes but are shuffled among channels within the same layer, and (3) Knapsack-optimized patch sizes using the same DReLU budget as the constant version. The purpose of the third set is to differentiate between the respective contributions of the coarse-grained budget allocation across layers and the fine-grained budget allocation across channels within the same layer. We note that shuffling preserves the patch size layer distribution, and thus only partially isolate the contribution of this fine grained allocation.

Contribution of FinetuningSince our algorithm utilizes fine-tuning to enable network security, we would like to explore the portion of performance improvement that can be solely attributed to further training OpenMMLab's models. Table 3 compares the classification and segmentation performance of three training approaches. The first approach

Figure 8: **DReLU layer histogram** The allocation of the DReLU budget (49.15K) among different layers. The green bars represent the allocation by DeepReDuce, which concentrates the entire budget on four layers and effectively reduces ResNet18 to a 4 layer network. The blue bars represent the allocation using our Knapsack approach to distribute the DReLU budget.

Figure 7: **Patch Size Distribution:** The patch size distribution of MobileNetV2 on the ADE20K dataset (Target DReLU = 9%). Observe that less than 1K layers (out of about \(17K\)) kept using the standard \(1\times 1\) ReLU. The Identity bar refers to homogeneous channels, where no DReLU evaluation is required for the entire channel.
is OpenMMLab's reported results, as well as our results on the CIFAR100 baseline model. The second approach is our results obtained using a DReLU budget of \(12\%\). The third approach uses the same training process as our algorithm, but ReLU layers are left intact.
contribution from approximate DReLU.

## 5 Conclusions

We proposed a new optimization technique to reduce the number of DReLUs in a neural network by about an order of magnitude. This is based on the observation that DReLU operations are highly correlated across neighboring pixels. Therefore, one DReLU per patch is enough to approximate a naive per-pixel DReLU evaluation. Based on this observation we formulate a knapsack optimization that determines, for each layer, what should be the optimal patch size of that layer. In addition, we show that we can further accelerate communication by cutting both MSB and LSB bits from the number representations used during the secure inference.

We evaluated the proposed techniques on two datasets for classification (CIFAR100, ImageNet) and two datasets for semantic segmentation (ADE20K, Pascal VOC 2012) and observed significant gains in performance. To the best of our knowledge, we are the first to demonstrate secure semantic segmentation on large images (\(512\times 512\) images).

The secure inference was implemented within the secure 3-party SecureNN protocol, but there is nothing in our technique that prevents it from being used in other protocols as well. Our source code has been made public.
