AutoFHE: Automated Adaption of CNNs for Efficient Evaluation over FHE
Authors: Wei Ao
Vishnu Boddeti
Venue: Submitted to ICLR 2023 (2023)
Keywords: Fully Homomorphic Encryption
Multi-Objective Co-Evolutionary Search
RNS-CKKS

Abstract: Secure inference of deep convolutional neural networks (CNNs) was recently demonstrated under the RNS-CKKS fully homomorphic encryption (FHE) scheme. The state-of-the-art solution uses a high-order composite polynomial to approximate non-arithmetic ReLUs and refreshes zero-level ciphertext through bootstrapping. However, this solution suffers from prohibitively high latency, both due to the number of levels consumed by the polynomials ($47\%$) and the inference time consumed by bootstrapping operations ($70\%$). Furthermore, it requires a hand-crafted architecture for homomorphically evaluating CNNs by placing a bootstrapping operation after every Conv-BN layer. To accelerate CNNs on FHE and automatically design a homomorphic evaluation architecture, we propose AutoFHE: Automated adaption of CNNs for evaluation over FHE. AutoFHE exploits the varying sensitivity of approximate activations across different layers in a network and jointly evolves polynomial activations (EvoReLUs) and searches for placement of bootstrapping operations for evaluation under RNS-CKKS. The salient features of AutoFHE include: i) a multi-objective co-evolutionary (MOCoEv) search algorithm to maximize validation accuracy and minimize the number of bootstrapping operations, ii) a gradient-free search algorithm, R-CCDE, to optimize EvoReLU coefficients, and iii) polynomial-aware training (PAT) to fine-tune polynomial-only CNNs for one epoch to adapt trainable weights to EvoReLUs. We demonstrate the efficacy of AutoFHE through the evaluation of ResNets on CIFAR-10 and CIFAR-100 under RNS-CKKS. Experimental results on CIFAR-10 indicate that in comparison to the state-of-the-art solution, AutoFHE reduces inference time (50 images on 50 threads) by 1,000 seconds and amortized inference time (per image) by $28\%$ and $17\%$ for ResNet-20 and ResNet-32, respectively.

Under review as a conference paper at ICLR 2023
AUTOFHE: AUTOMATED ADAPTION OF CNNS FOR EF- FICIENT EVALUATION OVER FHE
Anonymous authors Paper under double-bling review
ABSTRACT
Secure inference of deep convolutional neural networks (CNNs) was recently demonstrated under the fully homomorphic encryption (FHE) scheme, specifically (RNS-CKKS)
the Full Residue Number system variant of Theon-Kim-Kim-te The state-of-the-art solution uses a high-order composite polynomial to approxi- mate non-arithmetic ReLUs and refreshes zero-level ciphertext through bootstrap- ping. However, this solution suffers from prohibitively high latency, both due the number of levels consumed by the polynomials (47%) and the inference time consumed by bootstrapping operations (70%). Furthermore, it requires a hand-crafted architecture for homomorphically evaluating CNNs by placing boot- strapping operation after every Conv-BN layer. To accelerate CNNs on FHE and automatically design homomorphic evaluation architecture, we propose AutoFHE: Automated adaption of CNNs for evaluation over FHE. AutoFHE exploits the varying sensitivity of approximate activations across different layers in a network and jointly evolves polynomial activations (EvoReL.Us) and searches for placement of bootstrapping operations for evaluation under RNS-CKKS. The salient features of AutoFHE include: i) a multi-objective coevolutionary (MOCoBv) search algo- rithm to maximize validation accuracy and minimize the number of bootstrapping operations, ii) gradient-free search algorithm, R-CCDE, to optimize EvoReLU coefficients, and iii) polynomial-award training (PAT) to fine-tune polynomial-only CNNs for few epochs to adapt trainable weights to EvoReL.S.. We demonstrate the efficacy of AutoFHE through the evaluation of ResNets on encrypted CIFAR-10 and 1-FAR-100 under RNS-CKKS. Experimental results CIFAR-10 R- indicate that in comparison to the state-of-the-art solution, AutoFHE can reduce inference time (50 images on 50 threads) by up to 3,297 seconds (43%) while preserving the accuracy (92.68%). AutoFHE also improves the accuracy of ResNet-32 on CIFAR-10 by 0.48% while accelerating inference by 382 seconds (7%).
INTRODUCTION
Fully homomorphic encryption (FHE) is a promising solu- tion for secure inference of neural networks
93.5
AutoFHE
ResNet56
et al.
2016 Brutzkus et al,, 2019 Lou & Jiang] 2021 Lee
93.0
RosNo132
ResNette
al.
2022b a). However, Homomorphically evaluating
Vol Top-1 (78)
92.5
ResNot3
1297s
RewNeede
CNNs on encrypted data is challenging in two respects: I)
the design of homomorphic evaluation architecture of deep
92.0
FHE-MP-CNN
CNNs with arbitrary depth and 2) non-arithmetic operations
Bundsstapping
91.5
like ReLU, Recently, FHE-MP-CC MP-CNN (Lee al. (2022a) suc- cessfully implemented a homomorphic evaluation architec- ture of ResNets by using bootstrapping (Cheon al. 2018 Bossuat et al., 2021) to refresh zero-level ciphertext under the full residue number system (RNS) variant of Cheon- Kim-Kim-Song (RNS-CKKS) scheme (Cheon et al. 2017 2018b). However, since FHE supports only homomorphic multiplication and addition, non-arithmetic operations
ResNet20
13
29
91.0
7
9
10
Inference Time (1000 Seconds
30 Images)
Figure 1: Pareto fronts of AutoFHE ver- FHE-MP FEE-MP-CNN CN- encrypted CIFAR- 10 under the RNS-CKKS FHE scheme.
approximated by polynomials Gilad Bachrach et al. 2016; Chou et al.) 2018 Brutzkus et al., 2019 Lee et al., [02 2022a). For example, FHE-MP-CNN adopts high-precision Minimax composite polynomial (Lee et al. 202

---

Under review as a conference paper at ICLR 2023
90
ResNet20
Val Top- (50)
75
60
Sxam
Daddhiss Misel AuaFFR
RasNet32
30
400
ResNul34
ResNet56
200
300
100
15
20
30
23
35
Depth
Foortat rapping
tndux
Figure 2: Motivating AutoFHE. Left: depth consumption of AppReLUs based on ResNet-20 backbone on CIFAR-10. The purple line is when the same precision AppReLU is used in all layers, while the red circles show 5000 andomly-samples combinations of mixed -eeed-preiiion layerwise AppReL.Us. Middle: the number of bootstrapping operations where we show trade-off's of the same AppReLU and mixed AppReL.Us as in the left panel. We also show a multi-objective search result using mixed preediicciiiion layerwise AppReLUS and the Pareto front of the proposed AuEoFHE, Right: distributions of pre-activations (the maximum absolute values) of ResNets on CIFAR-10 where the green line corresponds to B, the scale value of AppRel.U in FHE-MP-CNN.
with degree {15, 15, 27} to approximate ReLUs (AppReLU). A more comprehensive discussion of related work in Appendix B
FHE-MP-CNN, the state-of-the-art approach, is limited by three main design choices. First, high- precision approximations like AppReI.U only consider function-level approximation and neglect the potential for end-to-end optimization of the entire network response. As such, the same high-precision AppReLU is used to replace all the network's ReLU layers, which necessitates the evaluation of very deep circuits. Secondly, due to the high number of levels required for each AppReLU, ciphertexts encrypted with leveled HE schemes like CKKS quickly exhaust their levels. Therefore, a bootstrapping operation is necessary for each AppReLU to refresh the level of zero-level ciphertexts. While these design choices are collectively very effective at maintaining the performance of the plaintext networks under FHE, they require many multiplicative levels and, consequently, numerous bootstrapping operations. Thindly, due to the constraints imposed by the cryptographic scheme (RNS-CKKS in this case), inference of networks in FHE requires the codesign of AppReLU and the homomorphic evaluation architecture. These include the careful design of AppReL.U (number of composite polynomials and their degrees), cryptographic parameters, placement of bootstrapping operations, and choice of network architectures to evaluate.
We illustrate the limitations of FHE-MP-CNN's design choices through case study (Figure 2 of ResNet-22 on CIFAR-10. We consider two plausible solutions to trade-off accuracy and com- putational burden of FHE-MP-CNN, (i) Same Precision AppReLU: We replace all ReLU layers with AppReLU of a given precision. We can trade-off (purple line in the left panel) accuracy and depth consumption using AppReL.U with different precision. However, as the middle panel shows, these solutions (purple dots) do not necessarily translate to a trade-off between accuracy and the number of bootstrapping operations due to many wasted levels. All the trade-off solutions collapse to either 15 or 30 bootstrapping operations. (ii) Mixed- Precision AppReLU: Each ReLU layer in the network can be replaced by AppReLU of any precision. We randomly sample 5,000 combina- tions of mixeddpprecisio layerwise AppReLUs and show (red dots) their depth consumption and the number of bootstrapping operations in the left and middle panels, respectively. Observe that AppReI.U leads to a better trade-off between accuracy and the number of bootstrapping operations. However, FHE-MP-CNT neglects the layerwise sensitivity (range) of ReLU rreaactvattoos (the right panel shows the distribution of the layerwise maximum absolute value of pre-activation) and uses AppReLU which is optimized for a ReLU with a large pre-activation range. Therefore, the Pareto front of mixed-precision layerwise AppReLU optimized by a multi-objective search algorithm NSGA-II Deb et al. (2002) is still inferior to AutoFHE, our proposed solution, by a significant margin. In summary, while both the solutions we considered were able to reduce the number of bootstrapping operations, unlike AutoFHE, it also lead to severe loss in performance.
layerwise
In this paper, we relax the design choices of FHE-MP-CNN and accelerate the inference of CNNs over homomorphically encrypted data while maximizing performance. The main premise behind our approach is to directly optimize the end-to-end function represented by the network instead of optimizing the function represented by the activation function. This idea allows us to exploit the varying sensitivity of activation function approximation across different layers in a network. Therefore, theoretically, evolving layerwise polynomial approximations of ReLUs (EvoReLU) should reduce the total multiplicative depth required by the resulting polynomial-onhe networks, and thus the number of time-consuming bootstrapping operations and the inference time encrypted data. To
2

---

Under review as a conference paper at ICLR 2023
this end, we propose AutoFHE, a search-driven approach to jointly optimize layerwise polynomial approximations of ReLU and the placement of bootstrapping operations. Specifically, we propose multi-objective co-evolutionary (MOCoEv) algorithm that seeks to maximize accuracy while simultaneously minimizing the number of bootstrapping operations. AutoFHE, jointly searches for the parameters of the approximate activation functions all layers, i.e., degrees and coefficients and the optimal placement of the bootstrapping operations in the network. Our contributions are three-fold:
AutoFHE automatically searches for EvoReLUs and bootstrapping operations. provides diverse set of Pareto-effective solutions that span the trade-off between accuracy and inference time under RNS-CKKS.
2. From an algorithmic perspective,
(a) We propose a simple yet effective multi-objective co-evolutionary (MOCoEv) algorithm to effectively explore and optimize over the large search space (1079 10230) and optimize nigh-dimensional vectors (114 ~ 330) corresponding to our formulation.
(b) We design gradient-free algorithm, regularized co-operative co-evolutionary differentiable evolution (R-CCDE), to optimize the coefficients of high-degree composite polynomials.
(c) We introduce polynomial-awarc training (PAT) to finetune EvoReLU DNNs for a few epochs.
Experimental results (Figure D on encrypted CIFAR-IO and CIFAR- 100 under RNS-CKKS show that, compared to CHEEMP--NNN the state-of-the-ar approach, AutoFHE can effectively trade-off' accuracy and inference time and result in a better Pareto front. On CIFAR-10, AutoFHE reduces inference time (50 images on 50 threads) by up to 3,297 seconds (43%) while preserving the accuracy (92.68% 68%). Specifically, AutoFHE reduces inference time of ResNet-20, ResNett32 (21 bootstrapping operations) and ResNet-56 by 25%, 23% and 12%, respectively, while improving accuracy up to 0. 0.28%. Aut also improves accuracy of ResNet-32 (29 bootstrapping opera- tions) on CIFAR-10 by 0.48% while accelerating inference by 382 seconds (7%). On CIFAR-100, AutoFHE saves inference time by 972 seconds (17%) while preserving accuracy.
2
PRELIMINARIES
RNS-CKKS:
The full residue number system (RNS) variant of Cheon-Kim Beeton---------eeee
Kim-Song (RNS-
CKKS) (Cheon et al. 2017, 2018b) is a leveled homomorphic encryption (HH) scheme for ap- proximate arithmetic. Under RNS-CKKS, a ciphertext e E R2,, satisfies the decryption circuit [(e, sh)le, = m + e, where (.-) the dot product and [ll is the modular reduction function. Rq, Zq, (XI/(x++1) is the residue cyclotomic polynomial ring. The modulus is Q2 = II - le- where < t S L. E is a non-negative integer referred to as level, and it denotes the capacity of homo- morphic multiplications. sk is the secret key with Hamming weight h. m is the original plaintext message, and is a small error that provides security. A ciphertext has N/2 slots to accommodate N/2 complex real numbers. RNS-CKKS supports homomorphic addition and multiplication:
Homomorphic Addition: Decrypt @ e') = (ecrypt(c) + Decrypt(ce)) Rs m + ml
(1)
Homomorphic Multiplication: Decrypt & e') = (ecrypt(e) x Decrypt(ce) R m x ml
Leveled HE only allows a finite number of homomorphic multiplications, with each multiplication consuming level due to rescaling. Once ciphertext's level reaches zero, a bootstrapping operation is required to refresh it to higher level and allow more multiplications. The number of levels needed evaluate a circuit is known its depth. RNS-CKKS with boot- strapping (Cheon et al. 2018a) is an FHE scheme that can evaluate circuits of arbitrary depth. It enables us homomorphicall, evaluate deep CNNs on encrypted data. Conceptually, bootstrapping homomorphically evaluates the decryption circuit and raises the modulus from Qo to Q2 by using the isomorphism Rgo 2 RRgo x RR,, x... x Ryy, (Bossuat et al. 2021). Practically, bootstrapping (Cheon et al. 2018a) homomorphically evaluates modular reduction Fil by first approximating scaled sine function, which is further approximated through polynomials (Cheon et al.) 2018a| Lee et al. 2020). Bootstrapping BBossuat et al. (2021) has four stages, including ModRaise, Soeff EvalMod, and SlotToCoeff. These operations involve a lot of homomorphic multiplications and rotations, both of which costly operations, especially the latter. The refreshed ciphertext has level f= = L K, where K levels are consumed by bootstrapping (Bossuat et al.) 2021) for polynomial approximation of modular reduction.
Bootstrapping:
by
3

---

Under review as a conference paper at ICLR 2023
FHE-MP-CNE Lee al. 2022a) is the ofate-of-the-ar framework for homomorphically evaluating deep CNNs on encrypted data under
with high accuracy. Its salient features include 1) Compact Packing: All channels of tensor packed into a single ciphertext. Multiplexed parallel (MP) convolution was proposed to process the ciphertext efficiently. 2) Homomorphic Evaluation Architecture: Bootstrapping operations are placed after every Conv-BN, except for the first one, to refresh zero-level ciphertexts. This hand-crafted homomorphic evaluation architecture for ResNets determined by the choice of cryptographic parameters, the level consumption of operations, and ResNet's architecture. 3) AppReLU: It replaces all ReLUU with the same high- order Minimax composite polynomial Lee et al. (221a of degrees {15, 15, 27). By noting that ReLU(z) x (0.5 + 0.5 sgn(z)), where synt r is the sign function, the approximated ReLU (AppReLUU) is modeled as (p) = z- (0.5 0.5 (z)) [-1,1) Pa
) is the composite Mínimax polynomial. The precision is defined as Paa (x) sgn(x)] 2 AppReI.U is expanded to arbitrary domains x E [-B, of pre-activations in CNNs by scaling it as B AAppReLU B). However, this reduces approximation precision to B 2-a To estimate the maximum dynamic range B (40 for CIFAR-10 and 65 for CIFAR- 100) of ReLUs, FHE-MP-CNN evaluates the pre- trained network on the training dataset. FHE-MP-CNN uses the same dynamic range B for all polynomials and neglects the uneven distribution of pre-activations as shown in Figure 2 Explicitly accounting for this uneven distribution allows us smaller B3 and a' but with the same precision, i... B' 2- CNN sets N = 21h L = 30 and Hamming weight h = 192. Please refer to Lee et al. (022a)
[-1.1].
2 for B'
and a' a. 4) Cryptographic Parameters: FHE-MP-
for the detailed implementation of FHE-MP-CNN and other parameters. These parameters provide 128-bits of security [heon et al. (201)) 5) Depth Consumption: To reduce level consumption, FHE-MP-CNN integrates scaling parameter into Conv-BN, The multiplicative depth consumption of Bootstrapping (i.e.. K), AppReLU, Conv, DownSampling, AvgPool, FC and BN layers are 14, 14, 2, 1, 1, 1, O, respectively. Statistically, when using FHE-MP-CND to homomorphically evaluate ResNet-18/32/44/55 CIFAR- 10 or CIFAR- 100, AppReLUs consume 47% of total levels and bootstrapping operations consume ~ 70% of inference time.
3 AUTOFHE: JOINT EVORELU AND BOOTSTRAPPING SEARCH
To minimize the latency of secure inference dominated by bootstrapping operations induced by high-degree polynomials and automatically design suitable homomorphic evaluation architecture, we propose AutoFHE. is designed search for layerwise polynomial approximation of ReLU jointly with the placement of bootstrapping. Furthermore, we directly optimize the end-to-end objective to facilitate finding the optimal combination of layerwise polynomials.
3.1 EVORELU
x. (0.5 + (0.++)(x))) x E [-1,1],y E [0, The composite polynomial pxx) (p o....op (()) (x), K approximates 0.5 (55-gg((z) (z).
EvoReLU is defined as = EvoReLU(()) x
The composite polynomial p((x) has K sub-polynomial functions and degree = I structure for EvoReLU bears similarity to the Minimax composite polynomial in Lee et al. 2021c
This
2022a). However, the objective for optimizing the coefficients is significantly different. We represent
the composite polynomial pa(z by its degree vector d = {d. [d and each sub-polynomial pk du (x) as linear combination of Chebyshev polynomials of degree dy, i.c., PE (z) 3% Σ = (z), where T; (x) are the Chebyshev bases of the first kind, o are the coefficients for linear combination
de
and 3g is a parameter to scale the output. The coefficients ae = {a,) dd, control the polynomial's ,ak,,
shape, while 8g controls its amplitude. X (a1, B,,... ,0kk Bk, ,KK, : 3x) are the learnable
parameters of EvoReLU with the degree d.
The ResNet architecture comprises two types of connec- tions, a chain, and a residual connection (see Fig. 3). To extend the domain of EvoReLU from [-1, to [-B, , B] but avoid extra depth consumption for scaling, we scale the plaintext weight and bias of BatchNorm by 1/B in advance for chain connections. But for residual connections, we cannot integrate the scale 1/B into BatchNorm's 's weight and bias. In this case, we scale the ciphertext output of the residual connection by 1/B B at the expense of one level. Finally, we integrate B into coefficients dx of PK (zr) re-scale the output of EvoReLU by B. Given the pre-activation [- B, B), the scaled
Homomorphie Evaluation Architecture:
4

---

Under review as a conference paper at ICLR 2023
FHE-MP-CNN
BSN
AppiteLi
Clar
AppRoLi
AntoFUI
Loon
BSS
Conr
EvottoU
Clain Counection
Rociual Counaciion
Figure 3: Homomorphic evaluation architectures of the chain and residual connections. Upper: standard ResNet Conv-BN- BeN--BN-eLUU triplet He et al. (201)). Middle: FHE-MP- CEEEMN--NN, Bottom: AutoFHE, where dashed rectangles placement of bootstrapping layers search.
Topo Accnney
EvoReLU
holistoo
Cocvelationnry
Popuzation
Cnoaever
Floor
Oftyrring
R-CCDE
Update Pareo Front
FAT
(Bavstrappoua
Figure 4: Overview of Multi-objective e--evolutoonayy (MOCoEv) search algorithm.
EvoReL.U with the degree d is parameterized by A:
y EvoReI.U(x, X; d) = x (0.5 + 105++p(000 (x)), where E [- BJ, [0, B] where we estimate B values for layerwise EvoReI.Us on the training dataset. From Figure 3 FHE- MP-CNN places bootstrapping after every Conv-BN, while AutoFHE will search for placement of bootstrapping operations by adapting to different depth consumption of layerwise EvoReLUs.
The Depth Consumption of EvoReLU is
E
[log2 + 1)] when using the Baby-Step =k=
Giant-Step (BSGS) algorithm Lee et al. 2020
Bossuat et al. (2021) to evaluate (I))
3.2 MOCOEv: MULTI-OBJECTIVE Co-EVOLUTIONARY SEARCH
Given a neural network function with I, ReL.Us and the pre-trained weights wo. our goal is to maximize the accuracy of the network while minimizing its inference latency encrypted data. A possible solution to achieve this goal to maximize validation accuracy while minimizing the total multiplicative depth of the network with EvoReLUs. However, this solution does not practically accelerate inference since bootstrapping contributes most to latency, and this solution may not necessarily lead to fewer bootstrapping operations. Therefore, optimize the parameters of all the EvoReLUs to maximize accuracy and directly seek to minimize the number of bootstrapping layers through a multi-objective optimization problem:
Search Objectives:
min s.t. A arg max (Aco (foo): A(D),
{1 (f A (D), Boot(B))
(3)
w arg arg min Cirain (f(w); (D))
where Accoat is the Top-1 accuracy on a validation dataset val, Boot is the number of bootstrap- ping operations, D {di .2..... dr.) is the degree vector of all EvoReLUs, the corresponding ((w)) is the neural network with the pre-trained weights wo- parameters are A = A2, Ar Cirain is the training loss. Given degree vector D, the number and placement of bootstrapping operations can be deterministically determined. Given D, we can optimize A to maximize the validation accuracy. We further fine-tune the network f(.) to minimize the training loss Ltrain- The objectives in equation guide the search algorithm to, i) explore layerwise EvoReLU includ- ing its degrees and coefficients; 2) discover the placement of bootstrapping to work well with EvoReLU; 3) trade-off between validation accuracy and inference speed to return diverse set of Pfreto-effective solutions. In this paper, we propose MOCoEv to optimize the multi-objective minD 11 Acceal (f(w");; (D), D), Boot (D)). We propose R-CCDE and use evolution- ary criterion to maximize Acc (wwo); A(D), D). We propose PAT to fine-tune approximated networks with Us to minimize Ltrain ( D).
5

---

Under review as a conference paper at ICLR 2023
Search Space: Our search space includes the number of sub nub-polynomials (K) in our composite polynomial, choice of degrees for each sub-polynomial (dæ) and the coefficients of the polynomials A. Table Ia shows the options for each of these variables. Note that choice d2 0 corresponds to an identity placeholder, so theoretically, the composite polynomial may have fewer than K sub- polynomials. Furthermore, when the degree of (pg o P =x)) less than or equal to 31 (maximum degree of a polynomial supported on RNS-CKKS [Lee et al. (202Ta we merge the two sub- polynomials into a single sub-polyne coab--ooyoomillla Pkc (px=)))(x) with degree de -d- S 31 before computing its depth. This helps reduce the size of the search space and leads to smoother exploration. Tab. [b lists the number of ReLUs of our backbone models and the corresponding dimension and size of search space for D.
Variable
Option
ARol.Us
Dimension
Search Space Size
coefficicuts (A)
# polymonials (K) poly degree (dg)
{0, 5, R
6
RecNas-30
ResNes-44
ResNes-32
ResNet 56
55
19
330
114
19
10
1
167h
(a)
(h)
Table I: (a) Search variables and options; (b) AutoFHE search space for ResNets.
MOCoEv: To overcome the challenge of multi-objective search over a high-dimensional D and explore the massive search space, we propose a multi cuulti-objective co-evolutionary (MOCoBv) search algorithm. Our approach is inspired by the divide-and-conquet strategy of cooperative co-evolution (CC))aagg et al. (008);; Mei et al. (2016); Ma et al. (2018). The key idea of MOCoEv is to decompose the higl-dimensional multi-objectivy search problem to multiple low-dimenss -inddimenioonal sub- problems. MOCoEv includes i) Decomposition: given a Pareto-effective solution D = (di, d2.
d }. MOCoEy improves D by locally mutating de, 1 < l < L so that D' (d1, d2, d/. dr) dominates D = =dd, d2.... dz....... di......,,, d.) in terms of the validation accuracy and the number of maintain the Pareto front as the context Meil itt al. (2016) so we can evaluate the locally mutated solutions cooperatively with each other dj. # 2, j S L. Figure f shows step of one iteration of MOCoEv. During one iteration, we repeat the step L times until we update all EvoReLUs. We design crossover and co-evolutionary mutation of MOCoEv to explore and exploit: (1) Crossover: given the current Pareto front, we select mating individuals to generate offspring and crossover offspring to exchange genes across EvoReL.Us. For example, given two mating individuals D, and D2, we crossover them to obtain Dí (b: be E Di D2. S l < L}. D =(b; b E (Di U D2)/Di, < < L}; (2) Co-Evolutionary Mutation: we mutate the L-th EvoReLU offspring, obtain a new Pareto front from mutated offspring and the current population, and finally update the current population. Then, we move onto the (f + 1) EvoReLU and repeat (1)(2) until L EvoReL.Us are updated. Therefore, we update the Pareto front L times the end of each iteration. We design three types of operators to mutate a composite polynomial function. i) randomly replace one polynomial sub-function with a new polynomial. ii) randomly remove sub-function. iii) randomly insert new polynomial. Please refer to Appendix(C]oor background on evolutionary search algorithms. The implementation details of MOCoEv algorithm are Appendix D.I]
dd.....
bootstrapping; and ii) Cooperative Evaluation:
3.3 REGULARIZED COOPERATIVE DIFFERENTIABLE CO-EVOLUTION
To solve A = argmax A (Acoaal (s(w)); A(D). D)} in equation 3 where D - [de 1 < L}. A = (Xel < < < L), we propose regularized cooperative co-evolutionary differentiable evolution (R-CCDE). Given degree de it optimizes A for function approximation level. However, the function approximation solution A maybe not the optimal solution for max (Acc (f(w): A(D). D)). So. we use MOCoFy to update the Pareto front in terms of the validation accuracy and the number of bootstrapping. R-CCDE decomposes X into {a1, ... , ,ek,, 3x} corresponding to polynomial sub-functions 1/1 = di (x) ar) 31) = P2 (y1 a22, 32), ... = Pk the forward architecture, x 1/1 + 1/2 + yK-1 + y. We adopt gradient-free differentiable evolution (DE) Rauf et al. (2021) to learn a and 33. DE uses the difference between individuals for mutation. Given the context vector X", we optimize ag and Sk. 1 S k S K alternatively
dx (yk-лạaк 3K) by using
a arg min L(a X*), a X (ai 87 Okk, 3k)
(4)
ax
8 = arg min C(3x + 7 3g A = (ai ,i,. ... Br. "a..., 9K)
(5)
3,
6

---

Under review as a conference paper at ICLR 2023
where L()) is the ( distance between (z) and 0.5 sgn(z)) aj and [ then used to update X We introduce a regularization term for optimizing the scale parameters, where y is the scaling decay. Scale parameters can prevent polynomials from growing exponentially during the initial iterations. The decay helps guide the parameters gradually toward a value of one and eventually select promising coefficients. Our R-CCDE algorithm is detailed in Appendix [D.2
3.4
PAT: POLYNOMIAL-AWARE TRAINING
Replacing ReLU with EvoReLU in pre-trained neural networks injects minor approximation errors, which leads to performance loss. Fine-tuning can mitigate this performance loss by allowing the learnable weights to adapt to the approximation error. However, backpropagation through EvoReLU leads to exploding gradients due to high-degree polynomials. Thanks to precise forward approximation of EvoReLU, we can use gradients from the original non- non-arithmetic ReLU function for backpropagation, specifically, during forward pass, EvoReLU injects slight errors, which are captured by objective functions like cross-entrops loss. During the backward pass, we bypass EvoReL. U and use ReLU to compute gradients to update the weights of the linear trainable layers (e-g.. convolution or fully connected). We refer to this procedure, which bears similarity to STE [Bengio et (2133) and Jacob et al. (2018), as polynomial-aware training (PAT). The following pseudocode illustrates this procedure for simple example, EvoReLU(z)) function, we first scale the coefficients of fa by B so that the output range of y is [0, B). In the backward function, we compute the gradient ay (xx) instead of dy (evoReL
=00.5 + (fs fz fi (z)). In the forward
def EvoReLU EvoReL.Ufoorwace forward B) f3 f3 * B y = (31 y x00.5 +) return y
def EvoReLU htwpluubbawwarddeeo (x, grad):
y = ReLU (x) gradLy = dy/dx
grad grad grad
return grad
4 EXPERIMENTS
We benchmark AutoFHE on CIFAR-I0 and CIFAR- 100 Krizhevsky et al. 2009); Both datasets have 50,000 training and 10,000 validation images at resolution of 32 x 32. The validation images are treated as private data and used only for evaluating the final networks. We randomly select 5,120 images from the training split as minival Tan & Le (2021) dataset to guide the search process. The Top-1 accuracy on the minival dataset optimizes equation 3 In addition, PAT uses the training split to fine-tune polynomial networks. Finally, our final result, report the Top-1 accuracy the encrypted validation dataset under RNS- RNS-CKKS. To evaluate AutoFHE under RNS-CKKS, we adopt the publicly available code of FHE-MP-CNN and adapt it for inference with layerwise EvoReL During inference, we keep track of the ciphertext levels and call the bootstrapping operation when the level reaches zero, thanks the optimal placement of bootstrapping operations found by AutoFHE. For a fair comparison between AutoFHE and the baseline FHE-MP-CNN, we use the pre-trained network weights provided by FHE-MP-CNN.
Setup:
Hyperparameters: For MOCoBv, we use population size of 50 and run it for 20 generations. We set the probability of polynomial replacement to 0.5, the probability of polynomial removal to 0.4, and the probability of polynomial insertion to 0.1. For R-CCDE, we set the search domain of a to 20. For a, we set the population size equal to 10x the number of variables. We set the scaling decay to 7 0.01 and the number of iterations to 200, For PAT, we use a batch size 512 and weight decay of 5 x 10-3 and clip the gradients to 0.5. We use learning rates of 5 x 10- for CIFAR-10 and 2 x 10-4 for CIFAR- 100. During MOCoEV search, we set the fine-tuning epoch to one. After the search is done, fine-tune searched polynomial networks for ten epochs. On one NVIDIA RTX A6000 GPU, the search process for ResNett200/3/444556 on CIFAR-10 took 59 hours, 126 hours, 200 hours, 281 hours, respectively. The search for ResNet-32 on CIFAR-100 took 140 hours.
[-5,5] and that of 3 to [1, 5). We set the population size for optimizing
7

---

Under review as a conference paper at ICLR 2023
ResNet-20
ResNet-32
ResNet-44 44
RosNet-56
RosNet-32/CIFAR
Val Top-1 (%)
70
75
68
60
66
45
30
64
Val
62
Backiooee
Aut:Fuu
ActaFiic
60
10 8
12
14
16
13
17
21
25
29
20
24
28
32
36
26 31
36
41
46
15
17
19
21
23
# Bootstrapping
Figure 5: Pareto fronts of AutoFHE. We report the accuracy on plaintext validation datasets and the numher of bootstrapping operations. Left: ResNet-20/52/44/5 on CIFAR-I0; Right: ResNet-32 on CIFAR- 100.
Backhone
AutoFHE
Dataset
Network
Top-1
Boot
T66-1"(%)
Inference
Amoriized
Boot
Top- (16)
Inference
Amortized
ResNet- 20
91.86
18
91.31
3,532s
71x
13
91.39
2,643s
53s
20
92.25
4,201s
84s
CIFAR-10
ResNet-32
92.80
30
92.40
5,768s
115s
21
92.68
4,435s
89s
29
92.88
3,3866
108s
ResNet-44
93.13
7,732s
38
7,20%
144s
ResNet-56
93.49
54
93.07
9,837s
197s
47
93.27
8,684s
174s
21
67.75
3,908s
78s
CIFAR 100
ResNet-32 32
69.38
30
69.43
5,684s
114s
22
68.66
4.573%
23
69.37
4.7126
94s
Table AutoFHE under the RNS-CKKS scheme. Top-1" accuracy for FHE-MP-CNN, as reported in Lee al. 2022aa..
The inference time 50 images is evaluated on AMD EPYC 7H12 64-core processor using 50 threads. Boldiace denotes the best criterion on backbone network, like the best Top-1 accuracy and the least inference time; underline denotes AutoFHIE outperforms FHE-MP-CNN,
4.1 PARETO FRONTS OF AUTOFHE
Figure 3 shows Pareto-effective solutions found by AutoFHE on CIFAR-I0 and CIFAR- 100 for different ResNet models. The trade-offs are between the Top-1 validation accuracy on plaintext data and the number of bootstrapping operations required for the corresponding homomorphic evaluation architecture. By optimizing the end-to-end network prediction function, AutoFHE adapts to the differing sensitivity of the activation layers to approximation errors and reduces the number of levels required compared to using the same high-degree AppReLU in all the layers. Thus, AutoFHE significantly reduces the number of bootstrapping operations. For ResNet-32 on CIFAR- 10, AutoFHE removes 10 bootstrapping operations (33.33%) compared to FHE-MP-CN negligible accuracy loss 0.08% compared the original network with ReLUs. Lastly, AutoFHE provides a family of solutions offering different trade-offs rather than a single solution, thus providing flexible choices for practical deployments.
with the
4.2 SECURE INFERENCE OF AUTOFHE UNDER RNS-CKKS
Due to the high computation cost of validating net- works performance on encrypted data under the RNS- CKKS, select nine solutions for evaluation machine with AMD EPYC 7H12 64-Core Processor and 1000 GB RAM. In Table 2 evaluate three so- lutions for ResNet-32 on both CIFAR-10 10 and CIFAR- 100 and evaluate one solution for - We estimate the inference time for 50 images on 50 CPU threads. Amortized inference time is amortized runtime for each image. We report the Top-1 accu- racy of AutoFHE on all (10,000) encrypted validation images under the RNS-CKKS. We plot Pareto fronts CIFAR-10 of AutoFHE versus the baseline in Figure D
ResNet-32
ResNet-33 COI1--32///FFR---AA 100
93.0
70.0
92.8
69.5
972s
92.6
0.48%
1333s
68.5
92.4
68.0
Reiddnn
67.5
92.0
67.0
4.2
4.7
6.2
5.7
4.0
4.5
5.
5.5
Indecence
Soconds
100 Images)
Figure 6: Pareto fronts of AutoFHE for ResNet-32 on CIFAR-10/-100 under RNS-CKKS.
Pareto fronts of AutoFHE of ResNet- 32 on encrypted CIFAR-10/-109 We observe that. CIFAR- 10, AutoFHE provides significant acceleration while having better accuracy or preserving accuracy. AutoFHE of ResNet-32 with 21 bootstrapping operations has slightly better accuracy than the baseline of ResNet-44 and accelerates inference by 3,297 seconds
8

---

Under review as a conference paper at ICLR 2023
Figure 7: Depth consumption of layerwise EvoReLU for ResNet-56 with 36, and 47 bootstrapping. The green dash line denotes the depth consumption of FHE-MP-CNN.
(43%). AutoFHE reduces inference time of ResNet-20, ResNet-32 (21 bootstrapping operations)
and ResNet-56 by 25%, 23% and 12% compared with the corresponding solutions of FHE-MP- CNN while improving accuracy up to 0.28%. AutoFHE with 29 bootstrapping operations improves accuracy of ResNet-32 by great margin 0.48% while accelerating inference by 382 seconds (7%). AutoFHE can achieve Top-1 accuracy of 91.39% on encrypted CIFAR- 10 under the RNS-CKKS an amortized inference latency of under one minute (53 seconds) per image, which brings us closer towards practically realizing secure inference of deep CNNs under RNS-CKKS. On CIFAR- 100, AutoFHE saves inference time by 972 seconds (17%) while preserving the accuracy. The experiments prove that Aut can find Pareto-effective solutions that trade-off accuracy and inference time. Furthermore, the results validate assumption that directly reducing the number of bootstrapping operations can effectively accelerate inference speed.
Depth Distributions of Layerwise EvoReLU for ResNet-56 with 36, 42, 47 bootstrapping operations are in Figure ( (see Appendix H for more results). Chain EvoReI.U and residual EvoReI.U refer to EvoReLU in the chain connection and the residual connection shown in Figure3] We make three observations: (1) residual EvoReLUs consume more levels than chain EvoReLUs, suggesting that residual ReLU layers have less tolerance to approximation errors; (2) since pre-activations of chain EvoReLUs are normalized, they follow a tighter distribution and need smaller scaling values; (3) the last EvoReLU close to the output does not need high-pree gigh-precision approximation.
4.3 ABLATION STUDY
1. Evaluating Co-evolution:
To evaluate the effectiveness of co-evolution in MOCoEy, we compare MOCoEv with a standard multi-objective evolution algorithm NSGA-II Deb al. (2002) in Appendix E optimization landscape of high-dimensional variables more effectively.
The experimental results in Figure and and Table Sable show that co-evolution explores the
Evaluating Layerwise Approximation: To evaluate the effectiveness of adaptive layerwise approximation of AutoFHE, we compare it with uniformly distributed Minimax composite poly- nomials Appendix Figure shows that by exploiting the varying approximation sensitivity of different layers AutoFHE has better trade-off than uniformly distributed Minimax polynomials.
3. Evaluating Auto FHE on ImageNet: We demonstrate the efficacy of AutoFHE on ImageNet Rus sakovsky al. (2015), a large-scale high-resolution image dataset, Appendix G The exper- imental result in Figure I1 shows that AutoFHE can effectively trade-off the accuracy and the depth consumption on large-scale datasets with high-resolution images.
CONCLUSION
This paper introduced AutoFHE, an automated approach for accelerating CNNs on FHE and au- tomatically designing homomorphic evaluation architecture. AutoFHE seeks to approximate the end-to-end function represented by the network instead of approximating each activation function. We exploited the varying sensitivity of approximate activations across different layers in network to jointly evolve composite polynomial activation functions and search for placement of bootstrapping operations for evaluation under RNS-CKKS Experimental results over ResNets CIFAR-10 10 and CIFAR-100 100 indicate that AutoFHE can reduce the inference time by up to 3,297 seconds (43%) while preserving the accuracy. AutoFHE also improves the accuracy by up to 0.48%. Although focus in this paper was on ResNets, and consequently RELU, AutoFiE is a general- algorithm that agnostic to the network architecture the type of activation function.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Proceedings of the 2012 ACM conference on Computer and communications security, pp. 784-796, 2012.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville, Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 130xv.:3308.33 2013.
Jean- Jean-Philippe Bossuat, Christian Mouchet, Juan Saancoso-Pastorizaa and Jean-Pierre Hubaux. Effi- cient bootstrapping for approximate homomorphic encryption with non-sparse keys. In Annual International Conference the Theory and Applications of Cryptographic Techniques, pp. 587- 617. Springer, 2021.
Alon Brutzkus, Ran Gilad-Bachrach, and Oren Elisha. Low latency privacy preserving inference. In International Conference on Machine Learning, pp. 812- PMLR, 2019.
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In International conference the theory and application of cryptology and information security, pp. 409-437. Springer, 2017.
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. Bootstrapping for approximate homomorphic encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 360-384. Springer, 2018a
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. A full mss variant of approximate homomorphic encryption. In International Conference on Selected Areas in Cryptography, pp. 347-368. Springer, 2018b.
Jung Hee Cheon, Minki Hhan, Seungwan Hong, and Yongha Son. A hybrid of dual and meet-in-the- middle attack on sparse and teraayy secret lwe. IEEE Access, 7:89497-89506, 2019.
Edward Chou, Josh Beal, Daniel Levy, Serena Yeung, Albert Haque, and Li Fei-Fei. Faster cryptonets: Leveraging sparsity for real-world encrypted inference. arXiv preprint arXiv:/8/1.00 /,09953, 2018.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiob- jective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182-197, 2002.
Carlos M Fonseca, Luis Paquete, and Manuel López-lbánez. An improved dimension-sweep algorithm for the hypervolume indicator: In 2006 IEEE international conference evolutionary compulation, pp. 1157-1163. IEEE, 2006.
Zahra Ghodsi, Nandan Kumar Jha, Brandon Reagen, and Siddharth Garg. Circa: Stochastic relus for private deep learning. Advances in Neural Information Processing Systems, 34:2241-2252, 2021.
Ran Gilad-Bachradd Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International conference on machine learning, pp. 201-210 PMLR, 2016.
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, 2016.
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer- arithmetic-only inference. In IEEE Conference on Computer Vision and Pattern Recognition, 2018.
Max Jaderberg. Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint arXiv: /7/ /t.i:://11100///00 1.09846, 2017.
Chiraag Juvekar, Vinod Vaikuntanathan. and Anantha Chandrakasan. {GAZELLE): A low latency framework for secure neural network inference. In 27th USENIX Security Symposium (USENIX Security 18), pp. 1651-1669, 2018
10

---

Under review as a conference paper at ICLR 2023
Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. Crypten: Secure multi-party computation meets machine learning. Advances in Neural Information Processing Systems, 34:4961-4999 2021.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Eunsang Lee, Joon-Woo Lee, Young-Sik Kim, and Jong-Seon No. Minimax approximation of sign function by composite polynomial for homomorphic comparison. IEEE Transactions Dependable and Secure Computing, 2021a.
Eunsang Lee, Joon-Wooe Lee, Junghyun Lec, Young-Sit Sik Kim. Yongjune Kim, Jong-Seon No, and Woosuk Choi. Low-complexity deep convolutional neural networks on fully homomorphic encryp- tion using multiplexed parallel convolutions. In International Conference on Machine Learning. pp. 12403-12422 PMLR, 2022a.
Joon-Wor Lee, Eunsang Lee, Yongwoo Lee, Young-Sik Kim, and Jong-Seon No. Optimal minimax polynomial approximation of modular reduction for bootstrapping of approximate homomorphic encryption. JACR Cryptol. ePrint Arch., 2020:552, 2020.
Joon-Woo Lee, Eunsang Lee, Yongwoo Lee, Young-Sik Kim, and Jong-Seon No. High-precision bootstrapping of mssckks homomorphic encryption using optimal minimax polynomial approxima- tion and inverse sine function. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 618-647. Springer, 2021b.
Joon-Woo Lee, HyungChul Kang, Yongwoo Lee, Woosuk Choi, Jieun Eom, Maxim Deryabin, Eunsang Lee, Junghyun Lee, Donghoon Yoo, Young-Sik Kim, et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access, 10:30039~ 30054, 2022b.
Junghyun Lee, Eunsang Lee, Joon- Woo Lee, Yongjune Kim, Young-Sik Kim, and Jong-Seon No. Precise approximation of convolutional neural networks for homomorphically encrypted data. arXiv preprint arXiv:2105. 10879,, 2021c
Jian Liu, Mika Juuti, Yao Lu, and Nadarajah Asokan. Oblivious neural network predictions via minionn transformations. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, pp. 619-631, 2017.
Qian Lou and Lei Jiang. Hemet: A commomorphic--eccyyiion---iii neural network architecture. In International conference on machine learning, pp. 7102-7110. PMLR, 2021.
privacy-preserving mobile
Qian Lou, Yilin Shen, Hongxia Jin, and Lei Jiang. Safenet: secure, accurate and fast neural network inference. In International Conference on Learning Representations, 2020.
Xiaoliang Ma, Xiaodong Li, Qingfu Zhang, Ke Tang, Zhengping Liang, Weixin Xie, and Zexuan Zhu. A survey on cooperative co-evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 23(3):421-455 2018.
Yi Mei, Mohammad Nabi Omidvar, Xiaodong Li, and Xin Yao. competitive ddwidd-andd-onqueee al- gorithm for unconstrained large-scale black- blx optimization. ACM Transactions on Mathematical Software (TOMS), 42(2):1 2016.
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In USENIX Security Symposium, 2020.
Jaiyoung Park, Michael Jaemin Kim, Wonkyung Jung, and Jung Ho Ahn. Aespa: Accuracy preserving low-degree polynomial activation for fast private inference. arXiv preprint arXiv:2201.0666 06699, 2022.
Deevashwer Rathee, Mayank Rathee, Rahul Kranti Kiran Goli, Divya Gupta, Rahul Sharma, Nishanth Chandran, and Aseem Rastogi. Simm: A math library for secure mnn inference. 2021 IEEE Symposium Security and Privacy (SP), pp. 1003-1020. IEFE, 2021.
11

---

Under review as a conference paper at ICLR 2023
Hafiz Tayyab Rauf, Waqas Haider Khan Bangyal, and M Ikramullah Lali. An adaptive hybrid differential evolution algorithm for continuous optimization and classification problems. Neural Computing and Applications, 33(17):10841-1088 2021.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-252 2015.
Nidamarthi Srinivas and Kalyanmoy Deb. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary computation, 2(3):221-2444 1994.
Mingxing Tan and Quoe Le. Efficientmetv2: Smaller models and faster training, In International Conference on Machine Learning, 2021.
Zhenyu Yang, Ke Tang, and Xin Yao. Large scale evolutionary optimization using cooperative cocvolution. Information sciences, 178(15):2985-299)) 2008.
Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfes 1986). pp. 162-167, IEEE, 1986.
APPENDIX
In this appendix, we include the following:
Appendix
A
Notations;
Appendix
An expanded discussion of related work for secure inference;
Appendix
Background and related work for evolutionary algorithms;
Appendix
Implementation of the MOCoEv and R-CCDE algorithms in D. and D.2 respectively;
Appendix
Experimental details for evaluating co-evolution;
Appendix
Experimental details for evaluating layerwise comparison;
Appendix
Evaluation of AutoFHE plaintext ImageNet;
Appendix
EvoReL.Us of ResNet-56 CIFAR-10.
A
NOTATIONS
We list variable notations of the RNS-CKKS and EvoReLU in Table
B RELATED WORK
Secure inference is promising solution for resolving the safety and privacy concerns in applications driven by deep learning as a service (DLaaS). Fully homomorphic encryption (FHE) and secure multiparty computation (MPC) becoming thede-facto standard of secure inference of deep learning. Secure inference-based FHE Gilad-Bachrach et al. (2016); Brutzkus al. 2 Lou & Jiang (2021): Lee al. (2022b a) better takes advantage of the Cloud service provider's infrastructure. Customers only need to encrypt their private data, send ciphertexts to the
Secure Inference:
Cloud, and decrypt the encrypted result. On the other hand, secure MPC Liu et al. (2017): Juvekar
et al. (2018); Mishra et al. (2020); Lou et al.] (2020); Ghodsi et al. (2021); Knott et al. (2021); Rathec al. 2021) requires regular communication between customers and the Cloud. FHE cannot directly evaluate ReLU because it only allows arithmetic homomorphic addition and multiplication. However,
Rathee
secure MPC can evaluate ReLU using Garbled Circuits (GC) Yao 1986);; Bellare et (2012) but suffers from high online computation and communication costs Mishra et al. (2020). Adaption of CNNs to secure inference by polynomial approximation of non-ard non-arithmetic functions, is necessary pre-procee processing stage. Polynomial approximation enables to homomorphically evaluate encrypted data on FHE, while it also can greatly reduce online computation and communication costs of secure MPC.
12

---

Under review as a conference paper at ICLR 2023
Notation
Domain
Description
N
g+
degree of polynomial rings
{0, 1....
level
Qr
z+
modulus Q: = II
where @r are primes
Ro,
residual cyclotomic poleooommmppplyoomiiiaa polynomial ring
m
Roy
plaintext
c
Ray
error
R2g
ciphertext
sk
R2.
private key
(.-)
dol product
Hlle
modular reduction function
Hamming weight
2. y
IR
scalar
B
IR
the maximum absolute value of pre-activations of ReLU
Pa(-)
Minimax composite polynomial with precision
a composite polynomial (z)) = (p% - pt .... px)
(x)
where 1 v k S K and degree d = 1lk=1
sub-polynomial function 1 (x) Ba Σ (x)
re (x)
a; E R. 3, E R, is the Chebyshev bases of the first kind
d
{d. dx
degrees of all sub- polynomials
{a
coefficients of a sub- pobb-oollnmiill function
EvoReLU
(v))eLU(()) = x (0.5- x I [-1, []
A
EvoReLU's parameters À (a1, B1, , 8K)
Table 3: Variable Notations.
Polynomial Approximation of ReLU: A simple square activation function x2 is used in Cryp- toNets Bachhach et al. (211)). LoLa Brutzkus et al. (2019) and Deiphi Mishra et al. (2020). Faster CryptoNets Chou et al. (2018) exploits more accurate low-degree approximation 2 30 +2 + SAFENet et al. (2020) adopts 22 + azx? 433 + or b, baxr + and uses SGD to train coefficients. When applying SGD to train low-degree polynomial coeffi- cients and network weights simultaneously. polynomials easily lead to exploding gradients. On the other hand, low-degree polynomials need to train approximated networks from scratch, cannot use pre-trained weights, and has big accuracy gap compared with ReLU networks. More recently, AESPA Park et al. (022) proposes basis-wise normalization to address the problem of exploding gradients in low-degree polynomial approximated networks. Delphi and SAFENet apply population- based training (PBT) Jaderberg et al. (2017) to search for placement of polynomials. Because Delphi and SAFENet are evaluated under secure MPC, they maintain some ReLUs preserve accuracy. SAFENet also observed that layerwise and channel-wise mixed-precision approximation could better take advantage of the varying sensitivity different layers. Minimax composite polynomials Lee et al. (2021a c) are specially designed to approximate ReLU under FHE with high precision using composite polynomials. FHE-MP-CNN Lee al.) (2022a) applies the Minimax composite poly- nomial with degree [15, 15, 27) and proves it can maintain the performance of pretrained ResNets under the RNS-CKKS FHE scheme. Unlike the abovementioned methods, learn trainable weights, including coefficients of polynomial-only networks, by optimizing cross Entropy loss. Minimax is function-leewe level approximation by optimizing the polynomial interpolation of ReLU. Given the depth, Minimax uses dynamic programming optimize degrees of composite polynomials and applies improved multi-interve Remez algorithm Lee et al. (20216) to solve coefficients. So, Minimax can achieve high approximation precision given depth. However, it neglects i) the learning ability of
13

---

Under review as a conference paper at ICLR 2023
neural networks to adapt to polynomial approximation, 2) the layerwise varying sensitivity, and 3) the combination of all polynomial activations in network. In this paper, we consider both high-precision approximation and network performance. MOCoEv searches for degrees across all layers and directly optimizes validation accuracy. We consider function-level approximation using R-CCDE to minimize the & distance. We use pre-trained ResNets and propose PAT to fine-tune network trainable weights to adapt to EvoReLUs for just few epochs.
C EVOLUTIONARY SEARCH ALGORITHMS
Evolutionary Algorithms (EAs) are a class of search algorithms inspired by Darwin's natural selection. Each candidate solution is individual. NP individuals constitute the population with the population size N.. Individuals are assigned fitness related to the objective, like validation accuracy for image classification. Based fitness, randomly select mating individuals. Crossover combine mating individuals to generate offspring. Offspring can be further mutated to better exploit current knowledge. Finally, offssring is used to update the current population. We can iteratively repeat this process many times. Each iteration is called generation. The number of generations is simple criterion for stopping the EA search.
Multi-Objective EA (MOEA): Given two d-dimensional vectors and 22 for minimization
problem, 11. < Zg.i. Vi E f1,2, d} and æ1.j < Ø2.j. Ej E f1.2. .d), 21 dominates 22 Srinivas & Deb (1994). It means 21 is better than Ø2- It is denoted æ1 < 22- Pareto front or Pareto-effeccive solutions are those not dominated by others. Delphi Mishra al. (2020) and Lou et al. (2020) combine two objectives (accuracy and ReLU replacement ratio) into single objective by weighted sum. It a widely-used trick to release multi-objective problems to a single objective. However, it only obtains single solution balancing multiple objectives and cannot get Pareto-effective solutions. This is why we apply multi-objective search to obtain Pareto-effective solutions corresponding different accuracy and latency requirements. EA is naturally well suited for multi-objective search due to population-base of Pareto-effective solutions in single run. NSGA-II Deb al. (2002) is the most well-known evolutionary multi-obe multi-obeeective algorithm. The proposed MOCoEv adopts nondominated sorting and crowding distance from NSGA-II. The nondominated sorting can return all Pareto fronts, while crowding distance selects the uniformly distributed individuals within Pareto front.
optimization. It allows us to obtain the entire
Differentiable Evolution (DE) is a gradient- free evolutionary algorithm used to optimize continuous variables Rauf et al. (2021). Given population X {I1 22, ZNP), where each individual Vx E RRd 1 S P. the mutation, crossover and selection of DE are defined as:
Mutation: In. + F (Ix,, - 2x₂) ; T1, T2, T3 S NP
Uj
u(0, 1) < CR 1sisd
Crossover: U, FTrjj
Otherwise
(6)
u,
F(u) 2 F(æm)
Selection: Teiyy
Otherwise
where F is scaling factor, CR is crossover rate, F(.) is the fitness evaluation function, and 2((0, 1) is the uniform distribution between ( and
Cooperative Co-Evolution (CC) algorithms were proposed address the challenge of optimizing high-dimensional variables) Yang et al. (2008) Mei al. (206)): Ma al, (0188.. Co-evolution decom- poses the high-dimensional optimization problem into dindenensional sub-problems. Then, apply EAs or DE to solve sub-problems for discrete or continuous variables, respectively. CC includes two major stages, decomposition and cooperative evaluation. Decomposition refers grouping vari- ables. Simple grouping strategies include random or interaction based (gradient-based, grouping Mei al. (2016). When the proposed R- R-CCDE searches for parameters À (Q1, E.oRee.U A(d), we decompose X to 31,,...... ,K,, Ax corresponding to polynomial sub- functions y1 Pi (z/)01,,) 31), 31),22 y22
.K.. : 3g) of
da P22 (yı |022, 32)...., y Pk dx (リK-IlaR, (x)). Because the scaling parameter is used to adjust the amplitude of polynomials, we evolve 3 followed by We maintain 2K populations for a1 .i...... SK. separately. These populations are called sub-populations or species in CC. This decomposition of R-CCDE takes advantage of the forward architecture of composited polynomials, x y11 ..... + DK-1 y.
14

---

Under review as a conference paper at ICLR 2023
When the proposed MOCoEV searches for D {dl, d2. ,pp. to minimize the objective {1 - (f(==) ( D), B)) we evolve sub-populations for d1, d,. di, sepa- rately. It decomposes original problems with dimension 114 ~ 330 to dimension six and greatly reduces the search space size from 10 ~ 10a30 to 10 Cooperative evaluation refers to cooper- atively evaluating individual's fitness in a sub-population. We should take into account other sub-populations when evaluating the individual. R-CCDE is a single objective optimization, so we maintain context vector Mei et al. 2016) X (at Si.
ai s When evaluate oek or Sk. we just need to replace the corresponding ag or 3 and assign a 3 with the fitness of (at. :..... Q............................... k 55) ) or (a7. ... 3x o 3g). In the beginning, the context vector is randomly initialized. Finally, R-CCDE outputs the context vector as the searched result. We extend the context vector for multi-objective optimization. MOCoEv maintains context vectors that are the current Pareto Front. Therefore, MOCoEv can effectively improve the Pareto Front using CC.
D
THE PROPOSED SEARCH ALGORIHTMS
D.1 MUI.TI-OIJCTTVV COOPERATIVE EVOLUTION
Algorithm|] shows the details of our proposed MOCoEv search algorithm. MOCoEv takes as input a neural network f with I. ReLUs that will be replaced by EvoReL.Us, the number of sub-functions of a composite polynomial K, the population size NP, the number of iterations T, the initial population size No. No > N because random initialization will generate invalid individuals. Invalid individuals refer to those that will lead to negative levels. The dataset, like CIFAR-10, with training and validation datasets, will be used. We will randomly sample a subset from the training dataset as minival dataset used for search. The training dataset will be used for fine-tuning During search and fine-tuning, the validation dataset is strictly unseen. We will report the Top-1 I validation accuracy on the validation dataset as the final result. MOCoEv will output the Pareto front, namely the population. The population is composed of non-dominated individuals with varying numbers of bootstrapping.
Algorithm 1: MOCoEv
input : The Network ff with ReLUs, the number of sub-functions of composite polynomial K, the population size NP, the number of iterations T, the initial population size No >> NP, the replace probability Preplace. the remove probability Premove. the insert probability Pinsert, the training dataset Training, the mini-validation dataset Minival;
output: The Pareto front Population;
initial: : :Population {Di, D2, DN,) + LHS (No, L, where D [di,".- dr.):
foreach d in D do À + R-CCDE (d);
foreach D in Population do Acc + Evalaute (f) Minival):
Population + Pareto (Population. Acc, NP)
foreach D Population do w +- PAT (f(D, A), Training):
foreach D in Population do Acc <- Evalaute (fww, D,A), A), Minival);
for / <- to T do for i 1 to L do
Offspring + Select (Population);
Offspring f Crossover ( (Offspring):
Offspring < Mutate (Offspring {;;
foreach in Offspring [] do X < R-CCDE (d);
foreach D in Offspring do w PAT (S((D A), Training):
foreach D in Offspring do Acc <- Eva vralauue (ww,, D, A), Minival); Population +- Pareto (Population + +ffsspring, Acc, NP)
In the initialization, we randomly initialize the population with No individuals, (Di, D2..... Dr, where D, = {di,... J E _ j < No. d,, 1 < < L is the degrees of composite polynomial and randomly sampled using the Latin hypercube sampling (LHS) method. The composite polynomials with the layer index constitute the i-th sub-populations of CC. The proposed R-CCDE searched for coefficients of composite polynomials. The Pareto function is first to use nondominated sorting to find Pareto fronts and then crowding distance select individuals given
15

---

Under review as a conference paper at ICLR 2023
the population size NP. In iteration t, we sequentially evolve EvoReLUs one by one. Given i-th EvoReLU, we first randomly select mating individuals from the population based on their accuracy on the minival dataset. We crossover mating individuals to generate offspring. Crossover operates at the network level. Then, we mutate the i-th sub-population. We randomly replace, remove and insert polynomials of the i-th uub-population with the probability Preplaces Pemove and Psseert. respectively, So, we need to apply R-CCDE to search coefficients of the i-th sub-population and also use PAT fine-tune the network. We evaluate the fine-tuned networks on the minival dataset. Finally, we use Parcto function to obtain the new Pareto front given the population size NP. Individuals in the Pareto front will be used to replace the population.
D.2 REGULARIZED CO-OPERATIVE DIFFERENTIAL CO-EVOLUTION
Algorithm 2: R-CCDE
input :A composite polynomial (xx) = (p* o PK o... op. (z) with parameters
dx
À {a1, ...... ak 3K J. the target non non-arithmetin function ((x),, the number of iterations T, the scaling decay
output: :hh context vector X initial: :A" f- LHS
for / <-11 1 to T do
for k - to do
a arg mi (as X*), au = (af Bi, ..k. Bk):
A < (ai, B7, .. og.
Bk)):
9 = arg ming, ( (3x (*) +7 Bb, Ax = (oj.011." Bk. ..... BK);
X (at, 37, ".. ak. 3k);
Algorithm 2 details the proposed R-CCDE searches for coefficients of a composite polynomial.
R-CCDE takes as input a composite polynomial (x)), the target non-arithmetic function q(r), the number of iterations I and scaling decay parameter 7,. In this paper, q(x) = 0.5 sgg((x). R-CCDE will output the context vector X as result. The composite polynomial p²(x) (pX PK-1
dx
pp (x) has learnable parameters X = (a1,,1,".. (K,
{an, , cra,) and
3k, 1 S k S K satisfy Pk (x) 3x Σ a; (x)) We apply LHS initialize sub-populations of each a# and Bg. The population size of a sub-populations is equal to 10 x |d 11/2, where Bg 20. We set 0x
and not learnable. Given iteration and uub-population index we apply DE to solve arg min & L.t,g((e (**) where Lpd, is the & distance between (xx) and q(x). on A means use the current context vector X but only search for the corresponding Org. The solution o evolved by DE is used update the context vector X (a Bf. ... 0x ... ax 3xk) Similarly, we also evolve 3g. After obtaining X3, we can scale ag by 3x and obtain the coefficients of the composite polynomial in terms of the first kind of Chebyshev basis.
E COMPARISON OF SEARCH ALGORITHMS
To solve the digh-dimensional search problem minD (f D), Boot(D)), we propose MoCoEv by using cooperative co-evolution to decompose high-dimensional optimization problem to cow-dimensional sub- boob-proolms... Because we adopt con-oomnnttdd sorting and crowding distance from NSGA-II Deb et al. (2002) to obtain Pareto-effective solutions. NSGA-II is a fair comparison to demonstrate the efficacy of MoCoEv. We conduct the search experiments of ResNet-20 and ResNet-32 plaintext CIFAR-10. When we use NSGA-II, we set the same dyper-parameten except for increasing the population size by the number of ReLUs. However, we cannot control the number of polynomials being evaluated, the number of evaluations on the minival dataset, and the number of fine- fine-tuning on the training dataset. So, we use the wall-clock search time to make computation comparable, shown in Table
The upper row of Figure & shows the Pareto fonts of NSGA-II and AutoFHE. terms of the trade-off of the Top-1 validation accuracy (> 80%) versus the number of bootstrapping operations, NSGA-II
16

---

Under review as a conference paper at ICLR 2023
ResNet-20
ResNet-32
90
88
84
NSGA-II II
82
Antol HE
18
Reformo:
14
TaTT
Figure 8: Comparison between AutoFHE with Co-evolution and NSGA-II.
Backhone
NSGA Deb
Network
Topl
HV
Time
Wiler
araly
#Eval
#Tume
HV
Time
Olter
4Puly
HEival
#Tune
ResNet-20
91.86
55.13
2 days 17 hrs
12
219K
9k
8k
72.98
2 days hrs
20
24k
18k
18k
ResNet-32
92.28
74.92
6 days 14 hrs
15
713k
14k
14k
92.89
6 days hrs
36k
30k
30k
Table 4: The ablation experiment of scarch algorithms plaintext CIFAR-10.
inferior to AutoFHE. It proves the effectiveness of co-evolution. Hypervolume (HV)Fonseca (2006) is used compare NSGA-II and AutoFHEEuuntiiativvell Hypervolume denotes the volume dominated by the Pareto front. The bigger HV, the better the Pareto Front. The bottom row of Figure
Fonseca et al.
& shows the trade-off between the Top-1 validation error and the number of bootstrapping. We compute the HV with respect to the reference points, (18.00, 18.56) for ResNet-20 and (30.00, 16.06) for ResNet-32, respectively. Table 4 shows AutoFHE has better HV values than NSGA-II. These ablation experiments prove that co-evolution facilitates the high-dimensional multi-objective search.
F EVALUATION OF LAYERWISE RELU APPROXIMATION
To demonstrate the efficacy of layerwise approximation of EvoReLUs, compare AutoFHE with the uniformly approximated networks. We adopt the Minimax composite polynomials Lee et al. (202 from precision 4 to 14 and them replace ReLUs uniformly. However, the Minimax polynomials require a re-design of homomorphic evaluation architecture for all composite polynomials with different precision. For example, FHE-MP-CNY the suitable homomorphic evaluation architecture. To fairly compare the layerwise EvoReLUand the uniformly distributed Minimax polynomial, we use the number of depths consumed by polynomials rather than the number of bootstrapping
the polynomial with precision 13 and designs
the criterion. We report the Top-1 validation accuracy on CIFAR-10 as the estimated performance under the RNS-CKKS. Hence, we used the search objective min (1- Acc,at (f ([w""); A* (D), D), Depth(D) DD.. where Depth(.) is the total number of depth the other hand, this ablation, we do NOT use PAT fine-tune networks to make the comparison fair.
consumed by polynomials.
The upper row of shour Pareto fronts of Minimax and AutoFHE terms of Top-1 validation accuracy and the number of depth. From the bottom row of Figure 9 we compute the hypervolume values with respect to the reference point (285, 90) for ResNet-20 and the reference point (372, 90) for ResNet-32, respectively. AutoFHE has HV 1.58 x 10 better than Minimax HV 1.06 1 on ResNet-20, while AutoFHE HV 1.84 x 10t compared with Minimax HV 1.00 x 104, These experimental results prove: the layerwise approximation is better than uniform approximation; 2)
17

---

Under review as a conference paper at ICLR 2023
ResNet-21
ResNet-32
60
10
Vall
Backbone
Minimax
AntoFIEE
Rehocure
60
Vall
20
Figure Evaluation of AutoFHE and layerwise Minimax.
35
EroRelll
12
15
24
Figure Depth consumption distribution of EvoReI.Us Us ResNet-56. Upper: depth consumption distributions layerwise EvoReLUs of different bootstrapping consumption. Bottom: the distribution of scaling parameters (B) layerwise EvoReLUs. The green dashed lines show the depth consumption or B of AppReLUs of FHE-MP-CNN.
the approximation of AutoFHE is also precise and AutoFHE's performance simply because of fine-tuning.
G EVALUATE AUTOFHE ON PLAINTEXT IMAGENET
It is not practical to evaluate higo-resolution images under the RNS-CKKS scheme due to the extremely high memory footprint and computational complexity constraints. realize the goal of practically processing high-resolution images in the encrypted domains, need advancements in
18

---

Under review as a conference paper at ICLR 2023
Val Top-1 (%)
70
60
50
40
30
20
10
20
45
70
95
120
Depth
Figure 11: Evaluate AutoFHE over ResNet-18 on plaintext ImageNct.
RNS-CKKS primitives, custom hardware for FHE, more efficient packing algorithms, etc. This is the reason why all current works use CIFAR to benchmark performance. We evaluate AutoFHE on plaintext ImageNe Russakovsky et al. (2015) to demonstrate its efficacy on the large-scale high- resolution dataset. We use the ResNet-18 model provided by Pytorch. MaxPooling. We replace the non-arithmetic MaxPooling by the arithmetic AvgPooling and train from scratch for 90 epochs. Its Top- accuracy is 69.62% slightly lower than its MaxPooling version, 69.76%. We set the number of generations to 10, the size of the minival dataset 2,560, and the population size to 30. Other hyper-paramen parameters are as same as CIFAR experiments. We turn off fine-tuning during the search and fine-tune the final result for epoch. The search experiment took 18 hours. We estimate accuracy on the plaintext validation dataset and use depth consumption as the inference cost under the RNS-CKKS, We adopt the Minimax polynomials with precision from 4 to Lee et al. (2021c) as our baseline and set B = 100. Figure [1 shows Pareto fronts of AutoFHE and Minimax. AutoFHE has 69.26% accuracy with depth consumption of 91, while Minimax consumes 126 depth to have the same accuracy. AutoFHE can reduce 28% depth consumption. When depth consumption is equal to 99, Minimax has an accuracy 14.71 %. AutoFHE reports accuracy 65.56% with the same depth consumption. This experiment demonstrates that AutoFHE can effectively trade off the accuracy and the depth consumption on large-scale high-resolution datasets.
has ReLUS and
H EVORELUS OF RESNET-56
Figure shows distributions of depth consumption of EvoReLUs Pareto-effective solutions with varying numbers of bootstrapping operations. From the upper panel of Figure T0, MoCoEv exploits the layerwise variable approximation sensitivity and assigns different depths to each EvoReLU, So. AutoFHE can reduce depth consumption, further accelerate inference. From the bottom panel of Figure 10 it shows different distributions smaller values and lower-degree polynomials have the same precision, namely B' 2 B 2 where B' B and a' < a. The pre-activations of residual EvoReLU are not normalized, so its B values are bigger than chain EvoReLU, So, residual EvoReLUs prefer higher-degree polynomial approximation with more depth consumption maintain approximation precision.
the number of bootstrapping operations and
of pre-activations. It proves
Figure and Figure show EvoReLUs of different layers of ResNet-56. We include Pareto-effective solutions with the number of bootstrapping operations from 26 to 52. From Figure 12 and Figure T3 high-pu precisreeision solutions consume more depth and approximate ReLUs precisely. Low-precision solutions use low-degree polynomials to reduce depth consumption. From EvoReLU approximation, we learn how AuE can trade off accuracy and inference speed.
19

---

Under review as a conference paper at ICLR 2023
Bootstrapping
25
29
32
34
36
39
40
41
42
44
45
47
EvoRaLLI Layer Index
20
Figure 12: EvoReLUs ResNet-56 from layer 0 to 26.
20

---

Under review as a conference paper at ICLR 2023
Bootstrapping
25
29
32
34
36
39
40
41
42
44
45
47
23
23
35
EV Layer Index
52
53
Figure 13: EvoReLUs of ResNet-56 from layer 27 54.
21


Reviews:
[{"review_id": "S5bR5mbmbF", "reviewer": "Reviewer_Lx4T", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a novel and comprehensive framework for convolutional neural network inference over a fully homomorphic encryption environment. Based on previous work FHE-MP-CNN, they made significant improvements by\n1) using a new approximation for the non-linear activation function ReLU\n2) an automatic procedure that helps choose your approximation function which simultaneously maximizes the accuracy and minimizes the computation cost. \n3) a new training procedure that better suits the proposed inference framework.", "summary_of_the_review": "I think it's a great paper that matches this conference. Shall definitely be accepted.", "strength_and_weaknesses": "Strength: this paper provides a framework for secure CNN inference that you could solely rely on it. The proposed techniques are novel and sound. And the experiments and evaluations are complete. This paper is also clearly written and provides all the necessary details.\n\nMy one question is about the choice of approximation functions. AFAIK Chebyshev approximations are quite generic. Is there any room for improvement given that we are particularly interested in the sign function? (Similar problem is considered here https://ia.cr/2021/572 but for sine function). Or maybe it will bring more complexity in designing the later search algorithm.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "No-v0PimtY", "reviewer": "Reviewer_b7YQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an automatic search based approach to design latency efficient CNN models for FHE. In particular, the paper presents a three stage approach of the search and fine tune: i) a multi-objective co-evolutionary (MOCoEv) search algorithm to maximize validation accuracy and minimize the number of bootstrapping operations, ii) a gradient-free search algorithm, R-CCDE, to optimize EvoReLU\ncoefficients, and iii) polynomial-aware training (PAT) to fine-tune polynomial-only CNNs for one epoch to adapt trainable weights to EvoReLUs. Demonstration on CIFAR-10 and CIFAR-100 shows the efficacy of the proposed method.", "summary_of_the_review": "The paper targets to solve the latency bottleneck issue of bootstrap and ReLU units forFHE based private inference. The problem is well motivated. However, the paper lacks ease of flow and clarity in writing. Details of error analysis for approx EvoReLU, latency evaluations, additional results, reason behind choice of search optimization are missing. Thus, despite good promise, the paper falls significantly below acceptance threshold.", "strength_and_weaknesses": "### Strengths\n\n1. In the current era of data and model IP protection, the problem statement of minimizing latency for secure and private inference is gullible and the paper is decently written.\n2. The issue with FHE-MP-CNN is well identified, particularly, the point of same high order approx. for all ReLUs.\n3. The multi objective problem formulation is well inspired.\n\n### Weakness\n\n1. Abstract introduced too much technicality as compared to its size with many technical terms. This definitely raises more question as opposed to providing a short overview of the paper. Some terms are not even clear, e.g. what's the full form of RNS-CKSS (in context of abstract).\n\n2. There has been few research in the domain of ReLU reduction in the context of private inference, including selective network linearization (SNL) [1], DeepReDuce [2] etc. These line of research definitely aligns with the current problem statement, hence, it would be interesting to see how efficient approximation of ReLU and removal of ReLUs go hand in hand in the context of FHE.\n\n3. If EvoReLU does not help in reducing latency, then is it replaced (from AppReLU) to improve accuracy? Or there is something I am missing? Does EvoReLU introduces polynomial error based on layer sensitivity? Please clarify, as the authors had mentione dApprox ReLU uses similar approx error for all ReLU layers.\n\n4. If you replace the EvoReLU with ReLU during backward pass, wont it introduce significant error? How that error is compensated in the framework? Why EvoReLU introduce exploding gradient issue, and why it can't be solved by traditional mean of solving exploding gradients? STE was introduced to primarily deal with non differentiable functions, not to handle exploding gradients. So, the citation of STE in this context is confusing!\n\n5. MoCoEv and Sec. 3.3 are written in a hurried way without properly mentioning the inspiration of the proposed solution. I find no discussion on possible alternatives and why we should buy this \"REGULARIZED COOPERATIVE DIFFERENTIABLE CO-EVOLUTION\" as the best potential solution.\n\n6. There is no pareto frontier of the search space, either for bootstrap or the EvoReLU polynomial choices. There is no latency vs accuracy plot either. \n\n7. Details of latency improvement computation is missing (the one mentioned as 17% and 22%). \n\n8. Additional results on higher resolution datasets are missing. Both CIFAR-10 and 100 are of size 32x32x3.\n\n9. The authors should also compare with more advanced search methods, instead of only comparing with NSGA II, which is not necessarily the state-of-the-art.\n\n### Other small issues\n\nPlease clarify (in the preliminaries) why bootstrapping operation is costly in a bit more details.\n\n\n[1] selective network linearization, ICML 2022.\n\n[1]  DeepReDuce, ICML 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MAIUEXrq2EZ", "reviewer": "Reviewer_Btk1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose Automated adaption of CNNs for evaluation over fully homomorphic encryption (FHE) called AutoFHE to accelerate CNNs on FHE and automatically design a homomorphic evaluation architecture. AutoFHE claims to exploit the varying sensitivity of approximate activations across different layers in a network and jointly evolves polynomial activations (EvoReLUs) and searches for placement of bootstrapping operations for evaluation under RNS-CKKS.", "summary_of_the_review": "1) It might be better to provide a motivation case study to show the shortcomings of the design choices of the state-of-the-art approach FHE-MP-CNN in section 1. This would motivate the readers to understand the importance of the proposed mechanism.\n2) In section 3, it is mentioned, \"We directly optimize the end-to-end objective to facilitate finding the optimal combination of layerwise polynomials.\" However, from the text it is not evident how the design choices were made nor how layer wise polynomials were optimised. Please specify.\n3) In section 3, please specify what each variables such as x, p, d, y means such that readers are able to understand the concept without domain expertise on the particular topic. This is to improve readability.\n4) Please briefly specify why CIFAR datasets were only utilised for evaluation in section 4. Why not other datasets? How will the proposed mechanism perform with other datasets (if such an evaluation is done or at least discuss the limitations of the proposed).\n5) Experimental section (section 4) lacks comparative study with state-of-the-art methods to show the efficacy of the proposed. Please provide such comparative studies or discuss the evaluations.", "strength_and_weaknesses": "Strengths::\nThe paper proposes an interesting concept.\n\nWeaknesses::\nThe paper can be improved based on the following points.\n1) It might be better to provide a motivation case study to show the shortcomings of the design choices of the state-of-the-art approach FHE-MP-CNN in section 1. This would motivate the readers to understand the importance of the proposed mechanism.\n2) In section 3, it is mentioned, \"We directly optimize the end-to-end objective to facilitate finding the optimal combination of layerwise polynomials.\" However, from the text it is not evident how the design choices were made nor how layer wise polynomials were optimised. Please specify.\n3) In section 3, please specify what each variables such as x, p, d, y means such that readers are able to understand the concept without domain expertise on the particular topic. This is to improve readability.\n4) Please briefly specify why CIFAR datasets were only utilised for evaluation in section 4. Why not other datasets? How will the proposed mechanism perform with other datasets (if such an evaluation is done or at least discuss the limitations of the proposed).\n5) Experimental section (section 4) lacks comparative study with state-of-the-art methods to show the efficacy of the proposed. Please provide such comparative studies or discuss the evaluations.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject