Compensating for Nonlinear Reduction with Linear Computations in Private Inference

**1. Novelty of the method. **

Thanks for raising the concern. We agree that additional experiments to explore the tradeoff between FLOPs and ReLU counts can help provide more novel insights. However, we believe that our paper already offers significant novelty and contributions, and the current experiments also shed some light on the above tradeoff.

For CryptoNAS and Sphynx, their approach deviates from the PPML setting we adopt, and reduces the amount of ReLU using NAS at the expense of accuracy loss. Although they can introduce more linear operators, they will suffer from more ReLU counts with one-to-one building blocks instead of many-to-one building blocks. In contrast, we employ additional linear computation and fully reuse nonlinear operators to compensate for the accuracy loss, and achieve even better performance.

2. FLOPs-cost are ignored.

Thank you for pointing out the ASPLOS’23 paper and the issue of offline HE computation cost for generating secret share triples. We do admit that in our design, more linear operators will incur more offline HE computations, and at high request arrival rates, it may be a bottleneck in the online throughput. However, the offline HE computations can be accelerated using layer-parallel HE (LPHE) by Garimella et al. or hardware accelerators.

As shown in Figures 5 and 6, even with the extra cost of computing more linear operators, Seesaw can still achieve better accuracy-latency tradeoffs compared to the baselines on real execution performance.

3. The argument of online vs. offline latency is only valid if the optimization is performed for a single private inference in isolation

As exactly in the same ASPLOS’23 paper by Garimella et al., the offline latency can be greatly reduced by using more server computing resources to compute in parallel, even without expensive HE hardware accelerators.

In the table below, we compare our Seesaw models with the Delphi ResNet-32-300K baseline (300K ReLUs), completely considering both online and offline cost. The Delphi offline phase uses the ASPLOS’23 LPHE approach, and needs 14.44 seconds.

Because Seesaw proposes a spectrum of models with different tradeoffs, we choose two models: Seesaw-16K (16K ReLUs) that has similar linear FLOPs (and thus similar offline HE cost) and similar accuracy to the baseline, and Seesaw-45K that has 2x linear FLOPs and higher accuracy. We assume the Seesaw models use the same amount of offline computing resources as the baseline above, so the offline HE time is proportional to the linear FLOPs.

We see that even when limited to similar FLOPs as the baseline, Seesaw-16K can still save online ReLU cost while maintaining accuracy, due to a shallower network topology. It achieves over 2.4x end-to-end (offline + online) speedup.

For Seesaw-45K, even the offline HE cost is 2x more, the online save is even more significant to compensate for it, enabling end-to-end speedups. Although the speedup here is not very high, it is actually a conservative result, because we can easily accelerate the offline part by using more servers, while the online part is difficult to accelerate.

4. How does the proposed method's trade-off between ReLUs and FLOPs counts compare to the straightforward approach of widening the baseline networks, such as ResNet18?

Thanks for your references. We may add such experiments for comparison in the final version. Wider networks can be helpful, as shown in SNL [1]. However, we also need to argue that widening the networks in Seesaw is not applicable because more channels will increase the consumption of ReLU budgets. We organize the parallel linear operators at some linear cost, but widening the networks results in both linear and nonlinear cost.

[1]: Minsu Cho, Ameya Joshi, Brandon Reagen, Siddharth Garg, and Chinmay Hegde. Selective network linearization for efficient private inference. In the International Conference on Machine Learning, pp. 3947–3961. PMLR, 2022b.

1. Please list all the details about the cryptographic parameters in your implementation.

Thank you for pointing that out. We leverage the DELPHI framework to perform real performance experiments. We inherit its settings on our machines and get the real latency in Figure 5 and Figure 6, whose implementation works over the 41-bit prime finite field defined by the prime 2061584302081, and uses a 11-bit fixed-point representation (see https://github.com/mc2-project/delphi/tree/master).

2. Please give the communication costs for each result.

We break the communication cost into offline and online phases and show them as follows:

Table: Communication latency breakdown of Seesaw on CIFAR100.

Table: Communication latency breakdown of Seesaw on ImageNet.

From the tables, we see that the reduction of ReLU can save a lot of online and offline communication cost compared to DELPHI with 69% accuracy.

**3. Did you implement your models with homomorphic encryption and multiparty computation? **

We do not implement a new PPML system, but adopt the design of DELPHI (see https://github.com/mc2-project/delphi/tree/master), which is a state-of-the-art implementation of PPML using HE and MPC.

1. Analysis on the weighting parameters used in the loss function regarding the pruning of the linear branches and nonlinear operators.

Thank you for your question. We use Eq (1) to capture the loss from the variation of linear branch parameters, and Eq (2) to capture the nonlinear operator loss as the difference between the target ReLU budget and the current ReLU number. Combining these two losses, we introduce our optimization targets: finding the important linear operators and removing unnecessary nonlinear operators. We adjust $\lambda_{lin}$ and $\lambda_{nonlin}$ in Eq (3) to get the best network architecture (with dynamic learning rate from 0.05 to 0 for $\lambda_{lin}$ and 0.001 and 0.1 for $\lambda_{nonlin}$).

Figure 8 and Figure 9 provide simple analysis on weight parameters. Figure 8 shows that the variance of sampling block branch weights is likely higher towards the backend of the network, reflecting that more linear operators are pruned under the threshold. Figure 9 shows the sampling blocks at the latter stage of the network tend to have higher ReLU weights and would keep the ReLU operators.

Therefore, we get an observation that an optimized PPML network architecture needs to preserve sufficient nonlinearity in the latter blocks of the model, while at the earlier stage, it can instead increase the linear computations to increase the representation capacity.

2. The results on CIFAR100 are less significant compared to the one on Imagenet.

ImageNet requires more expressive networks for higher resolution pictures, and Seesaw provides more linear operators to achieve that. However, on CIFAR100 with low resolution, the benefits of adding linear operators are relatively low after obtaining good feature extraction capabilities. At this point, the ReLU budget is the real determinant of accuracy.

3. Is there a reason which explains why the results on accuracies on Imagenet and CIFAR100 are different with respect to SENet? We observe better results of Seesaw compared to SENet on Imagenet

The reason is similar to that of Question 2 above. SENet proposes fine-grained ReLU pruning algorithms, which can efficiently reduce the ReLU counts of existing networks. They choose ResNet18 and ResNet34 as targets, which already has enough expression ability for CIFAR100. However, linear operators of shallow ResNet are not enough for ImageNet. In summary, simple networks can achieve good results on small datasets, but not on large datasets.

4. Section 4.1, you say that with abundant ReLU budgets, Seesaw can outperform Resnet models, do you prove this statement somewhere? or It is just the assumption knowing that you have more linear operators.

We compare Seesaw with ResNet on Figure 3 and Figure 4, finding that with the same ReLU budget, Seesaw can outperform ResNet. However, we must admit that Seesaw achieves such performance with more linear operators.