HD-cos Networks: Efficient Neural Architechtures for Secure Multi-Party Computation
Authors: Wittawat Jitkrittum
Michal Lukasik
Ananda Theertha Suresh
Felix Yu
Gang Wang
Venue: ICLR 2022 Submitted (2022)
Keywords: multi-party computation
privacy
cryptography
privacy-preserving machine learning

Abstract: Multi-party computation (MPC) is a branch of cryptography where multiple non-colluding  parties execute a well designed protocol to securely compute a function. With the non-colluding party assumption, MPC has a cryptographic guarantee that the parties will not learn sensitive information from the computation process, making it an appealing framework for applications that involve privacy-sensitive user data.
In this paper, we study  training and inference of neural networks under the MPC setup. This is challenging because the elementary operations of neural networks such as the ReLU activation function and matrix-vector multiplications are very expensive to compute due to the added multi-party communication overhead. 
To address this, we propose the HD-cos network that uses 1) cosine as activation function, 2) the Hadamard-Diagonal transformation to replace the unstructured linear transformations. We show that both of the approaches enjoy strong theoretical motivations and efficient computation under the MPC setup. We demonstrate on multiple public datasets that HD-cos matches the quality of the more expensive baselines. 

Under review as a conference paper at ICLR 2022
HD-cOs NETWORKS: EFFICIENT NEURAL AR- CHITECHTURES FOR SECURE MULTI-PARTY COMPU- TATION
Anonymous authors Paper under double-bling review
ABSTRACT
Multi-party computation (MPC) is a branch of cryptography where multiple non- colluding parties execute a well designed protocol to securely compute a function. With the non-colluding party assumption, MPC has cryptographic guarantee that the parties will not learn sensitive information from the computation process, mak- ing it an appealing framework for applications that involve privacy-senss -sessivvve user data. In this paper, we study training and inference of neural networks under the MPC setup. This is challenging because the elementary operations of neural net- works such as the ReLU activation function and matrix-vecte multiplications are very expensive to compute due the added multi-party communication overhead. To address this, we propose the HD-cos network that uses 1) cosine as activation function, 2) the Hadamard- Diaggonnl transformation linear transformations. We show that both of the approaches enjoy strong theoret- ical motivations and efficient computation under the MPC setup. We demonstrate multiple public datasets that HD-cos matches the quality of the more expensive baselines.
replace the unstructured
INTRODUCTION
Machine learning models are often trained with user data that may contain private information. For example, healtheare patients diagnostics contain sensitive information and in financial sectors, user data contains potentially private information such as salaries and taxes. In these applications, storing the user data in plain text format at a centralized server can be privacy invasive. There have been several efforts to design secure and private ways of learning and inferring machine learning models. In this work, we focus on secure multi- multi-party computation (MPC), a branch of cryptography that allows parties to collaboratively perform computations on data sets without revealing the data they possess to each other (Evans et al.) 2017). Recently, there are several research papers that proposed to train and infer machine learning models in secure fashion via MPC (Gilad Bachhach ctt al., 2016; Graepel et al.] 20122] Obla et al. 2020). Loosely speaking, in the MPC setup, a piece of sensitive data is split into multiple shards called secret shares, and each secret share is stored with a different party. These parties are further chosen such that their fundamental interests are to protect sensitive data and hence can be viewed as non-colluding. The cryptography guarantee states that unless all the parties (or at least k out of all parties, depending on the cryptographic algorithm design) collude, sensitive data cannot be reconstructed and revealed anyone/anything.
Training in the MPC setup is challenging due to several reasons. Firstly, only limited data types (e.g. integer) and/or operations (e.g. integer addition and multiplication) are natively supported in most MPC algorithms. This increases the complexity to support non-trivial operations over MPC. Secondly, since data is encrypted into multiple secret shares and stored multiple parties, one share per party, directly training machine learning model on this data can be expensive, both terms of communication between the servers and computation at the individual servers. More concretely if simple operations like addition and multiplications take orders of nanoseconds in the normal computation scenarios, in the MPC setup they can take milliseconds or more, if the operation requires the parties in the MPC setup communicate with each other. Furthermore, one of the key bottlenecks of secret sharing mechanisms is that most non-linear operations e.g., ReLU(x)) = max(0,x)) .r), cannot be efficiently computed.

---

Under review as a conference paper at ICLR 2022
In this paper, address these questions by proposing a general network construct that can be implemented in MPC setup efficiently. Our proposal consists of two parts: 1) use the cosine function as the activation function, and 2) use structured weight matrix based on the Hadamard transform in place of the standard fully connected layer. We provide an algorithm to compute cosine under two- party computation (2PC) setup. Unlike ReLUU which involves multiple rounds of communication, our proposed algorithm for cosine requires only two online rounds of communication between the two computation servers. The use of the proposed Hadamard transform for weight matrices means that the number of parameters in each dense layer scales linearly with the input dimenion, opposed the standard dense layer which scales quadratically. We demonstrate on number of challenging datasets that the combination of these two constructs leads to model that is as accurate as the commonly used ReL.U-based model with fully connected layers.
The rest of the paper is organized as follows. We first overview multiparty computation in Sec- tion 2 and then overview related works in Section 3 We present the cosine activation function and structured matrix transformation with theoretical motivations and analysis of their computational ef- ficiency in Section 4 and Section We then provide extensive experimental evaluations on several datasets in Section 6
2 MULTI-PARTY COMPUTATION
Secure multi-party computation (MPC) is branch of cryptography that allows two more parties to collaboratively perform computations on data sets without revealing the data they possess to each other (Evans al., 2017). Following earlier works (Liu et al. 2017 Mohassel & Zhang 2017 Kelkar et al. 2022 ID. we focus on the two party computation (2PC) setup. Our results can be extended to multi-party setup by existing mechanisms. If the two parties are non-colluding, then 2PC setup guarantees that the two parties will not learn anything from the computation process and hence there
no data leak.
During training in the 2PC setup, each party receives features and labels of the training dataset in the form of secret shares. They compute and temporarily store all intermediate results in the form of secret shares. Thus during training, both the servers collaboratively learn a machine learning model, which again is split between two parties. Upon completion of the training process, the final result, i.c. the ML model itself, composed of trained parameters, are in secret shares to be held by each party in the 2PC setup. At prediction time, each party receives features in secret shares, and performs the prediction where all intermediate results are in secret shares. The MPC cluster sends the prediction results in secret share back to the caller who provided the features for prediction. The caller can combine all shares of the secret prediction result into its plaintext representation. In this entire training/prediction process, the MPC cluster does not learn any sensitive data.
While MPC may provide security/privacy guarantee and is Turing complete, it might be significantly slower than equivalent plaintext operation. The overall performance of MPC is determined by the computation and communication cost. The computation cost in MPC is typically higher than the cost of equivalent operations in cleartext. The bigger bottleneck is the communication cost among the parties in the MPC setup. The communication cost has three components.
Number of rounds: the number of times that parties in the MPC setup need to com- municate/synchronize with each other to complete the MPC crypto protocol. For 2PC, this is often equivalent to the number of Remote Procedure Calls (or RPCs) that the two parties need per the crypto protocol design. Many MPC algorithms differentiate offline rounds vs. online rounds, where the former is input-independent and can be performed asynchronously in advance, and the latter is input-dependent, is on the critical path for the computation and must be performed synchronously. For example, addition of additive secret shares requires no online rounds, whereas multiplication of additive secret shares requires one online round.
Network bandwidth: the number of bytes that parties in the MPC setup need to send to each other to complete the MPC crypto protocol. For 2PC, each RPC between the two parties has a request and response. The bandwidth cost is the sum of all the bytes to be transmitted in the request and response per the crypto protocol.
2

---

Under review as a conference paper at ICLR 2022
Network latency: the network latency is property of the network connecting all parties in the MPC setup. It depends on the network technology (e.g. 10 Gigabit Ethernet or 10GE), network topology, well applicable network Quality of Service (QoS) settings and the network load.
In this work, we propose neural networks which can be implemented with few online rounds of communication and little network bandwidth. Following earlier works, We consider neural network architectures where the majority of the parameters are on the fully connected layers.
We propose and systematically study using cosine as the activation and demonstrate that achieves comparable performance to existing activation and can be efficiently implemented with two online rounds.
We show that dense matrices in neural networks can be replaced by structured matrices, which have comparable performance to existing neural network architectures and can be efficiently implemented in MPC setup by reducing the bandwidth. We show that by using structured matrices, we can reduce the number of per-layer secure multiplications from (dP) to (d), where is the layer width, thus reducing the memory bandwidth.
RELATED WORKS
Neural network inference under MPCnBarni et al. (2006) considered inference of neural networks in the MPC setup, where the linear computations are done the servers in the encrypted field and the non-linear activations are computed at the clients directly in plaintext. The main caveat this approach is that, to compute L layer neural network, L rounds of communication is required between server and clients which can be prohibitive and furthermore intermediate results are leaked to the clients, which may not be desired. To overcome the information leakage, Orlandi et al.) (2007) proposed methods to hide the results of the intermediate data from the clients; the method still requires multiple rounds of communication. [Liu et al. (2017) proposed algorithms that allows for evaluating arbitrary neural networks; the intermediate computations (e.g., sign(x)) are much more expensive than summations and multiplications.
Efficient activation functions. Since inferring arbitrary neural networks can be inefficient, several papers have proposed different activation functions which are easy compute. Gilad-Bachrachi et al. (2016) proposed to use the simple square activation function. They also proposed to use mean-pooling instead of max-pooling. [Chabanne et al. (2017) also noticed the limited accuracy guarantees of the square function and proposed to approximate ReLU with low degree polynomial and added a batch normalization layer to improve accuracy. Wu et al. (2018) proposed to train polynomial activation to improve the performance. Obla et al. (2020) proposed different algorithm for approximating activation methods and showed that it achieves superior performance on several image recognition datasets. Recently Knott et al. (2021) released library for training and inference of machine learning models in the multi-party setup.
Cosine as activation function. Related using cosine as the activation function, Yu et al. (2015) proposed the Compact Nonlinear Maps method which is equivalent of using cosine as the activation function for neural networks with one hidden layer. Parascaandloo et al. (2016) studied using the sine function as activation. Xie et al. (2019) used cosine activation in deep kernel learning. [Nel et al. (2021) proposed variant of the cosine function called Growing Cosine Unit cos(x) and shows that it can speed up training and reduce parameters in convolutions neural networks. All the above works are not under the MPC setup.
Training machine learning models under MPC. Graepel et al. (2012) proposed to use training algorithms that can be expressed as low degree polynomials, so that the training phase can be done over encrypted data. Aslett et al. (2015) proposed algorithms train models such as random forests over training data. [Mhhassel & Zhang (2017) proposed 2PC setup for training and inference various types of models including neural networks where data is distributed to two non-colluding servers. Kelkar et al. (2021) proposed an efficient algorithm for Poisson regression by adding a secure exponentiation primitive.
Combining with differential privacy, We note that while the focus of this work is multi- com- putation, it can be combined with other privacy preserving techniques such differential privacy
3

---

Under review as a conference paper at ICLR 2022
Cocine No aciivoaann
Activation
Online rounds
None
0
p--1 Squaee
Gilad-Bachrach et al. 2016)
1
Kelkar al. (0021)
ReLU Polyht(3) (Obla et al. 2020
2
Cosine |this work]
2
Table 1: Activation functions and their communication costs. Since ReLU cannot be implemented efficiently in the MPC setup, we have omitted it.
Figure I: A comparison of different ac- tivation functions.
Dwork et al. 2014). There are some recent works which combine MPC with differential privacy Jayaraman Wang 2018). Systematically evaluating performances with the combination of our proposed technique and that of differential privacy remains an interesting future direction.
4 COSINE AS ACTIVATION
The most widely used activation function in the non-MPC setup is the Rectified Linear Unit (ReLU) function: ReLU(x)= = max (0,x). Unfortunately, it is not efficient to compute ReLU under the MPC setup. To this end, Wu et al. (018)) and Obla et al. (2020) proposed to approximate ReLU with low-degree polynomials. This still incurs large communication cost as it requires d - online online rounds of communications to compute d-degree polynomial approximation. Another simple alternative is the square function (Gilad- Bachach et al. (016). In this case, the trained neural network often has a subpar quality as noted by Wu et al. (018)).
cosine the activation function. We show that it has good theoretical properties (Section[4.) I. and can be implemented efficiently under the 2PC setup (Section (4.)). We compare different activation functions in Figure [ and give the corresponding computation costs in Table 4
In this work, we propose
4.1 THEORETICAL MOTIVATION OF COSINE
When using cosine the activation function, the output of neural network layer becomes cos(Wx + b), where E IRd is the input, W E kx is the weight matrix, and E R is bias vector. This form coincides with the Random Fourier Feature method (Rahimi & Recht 2007). widely used in the kernel approximation literature. Kernel method is a type of powerful nonlinear machine learning models that is computationally expensive scale to large-scale datasets. Kernel approximation methods aim at mapping the input into new feature space, such that the dot product that space approximate the value of the kernel. The benefit is that linear classifier trained in the mapped space approximate a kernel classifier.
Let (xx) = cos(Wxr v + b), the follow result Rahimi & Recht (007)) shows that d(x) d(y) approximates shift-invariant kernel with proper choice of the parameters in W and b. Note that since (Rahimi & Recht| (207)). there have been many improvements of Random Fourier Features such better rate of approximation (Sriperumbudur & Szabó 2015) and more efficient sampling YYang et al. 2014). Cosine is also shown to be able to approximate other kernel types such as the polynomial kernels unit sphere (Pennington al.) (015).
Lemma 1 (Cosine approximates a shift-invariant kernel Rahimi Recht 2007)). Let k: Rdd x Rd I. be positive definite kernel. Assume that i is iniff-iivarian:: there exists function K: IR such that for any I, E [Rd, K(x y) k(x,8) y). Let 6(x) 22/Di [cos(w; Ww + by).... cosí (WD x +bb), where Wi,..., WD are sampled i...d. from a distribution p(w) which is the Fourier transformation of K(2) i.e., K(z) J& e dw.. bi,...,by bp are sampled uniformly from [0, 2T.. Then d(x) (0y) is unbiased estimator of K(x v). and
h(x v)1 2 SC (AiammM))
2
P
sup
(6(x) Q(y)
c -D2
LENEM
where M is compact subset of R.d. diam(M) is the diameter of M, and C is constant.
4

---

Under review as a conference paper at ICLR 2022
Input: server, has [z]], and servery has [z|z such that [x]] + [al| = x.
Output: server, has [=]1, and server2 has [z]2 such that [z]1 [a|2 cos(
1. Local computation:
Both servers compute cos[ær] and sin[ar] locally.
2. Exchange:
From cos(2]1, server, constructs [cos(a)a] and [cos[2]112 using additive secret share
mechanisms |Evans et al., 2017); sends [cos[æ]]]2 to serverg.
From sin(2] server, constructs [sin[x]]]] and [s): sends [sin [in]z]]]2 to serverg-
From cos[3]], servery constructs [cos[æ]]2] and [cos[a] c2ss412222 sends [cos[Ir]2] server1.
From sin [z]2. serverz constructs [sin[æ]]]] and [sin[x]]]22: sends [sin[x]]] sends
to server
3. Multiplication:
[cos[æ]] cos[æ]2]1, [cos[æ]] cos[æ]2|2 Mult([[oos(z]1]] [cos[x]2]) ([cos[z]]]2, [cos] (z]2]2)). [sin[x]] sin (21]2]1 [sin [x]] sin [z12222 Mult(((sin(z]1)) (sin (x]]21)))) (oin(()]))) (sin(x]2]22)
4. Final computation:
server, computes [2] [cos [r) cos [r]]] [sin [2]] sin(x|2) [z|2]1-
server2 computes [2|2 [cos [ cos 2/22 [sin [2)1 sin [2|22222
Securely compute cosine activation in the 2PC setup. Mult() refers to the known secure multiplication protocol based on Beaver Triplets (Beaver 1991).
Algorithm 1:
The above lemma shows that, at random initialization, a linear classification model trained with the transformed features using cosine approximates kernel-baser classifier. In specific, if the weights {w,}?_1 are sampled from a Gaussian distribution, the model is approximating a Gaussian- kernel based classifier, already strong baseline initialization.
Besides the connection the kernel methods, cosine and its derivative are bounded functions. As shall be seen our experiments, having a Linerly-growwnn (e.g.. ReLU) or bounded activation (e.g., cos) means that the model can be trained without carefully fine-tuning the optimization method. That is, models with the cosine activation can trained with a wide range of learning rates, in contrast to, for instance, the square function which grows quickly enough that careful choice of learning rate is needed to prevent numerical overflow. Note that techniques like batchnorm that improves stability in neural network training hard to be applied under the MPC setup due to the expensive operation of division. Hence, having a numerically stable activation function is very important.
4.2 ALGORITHM TO COMPUTE COSINE ACTIVATION FUNCTION
In this section, provide algorithm to compute cosine activation function in the 2PC setup. The algorithm is given in Figure | We state the algorithm in the bracket notation, where [y] denote the shard of y located in server, Therefore [y] + [y/2] = y. The algorithm has two main parts: locally the algorithms first compute cos [z]; and (.] Then they use known 2PC protocols for addition, multiplication and secure exchange to compute [a]_ and [a]2 such that [2] + [2]2 2 and
2 = cos [x] cos(x2] sin[2]] sin [22]-
By the trignometric identity cos(a + cos(a) (a) cos(b) sin(a) sin(b).
cos([=)( [x]²) cos(x).
Theorem 1. Cosine can be computed in the 2PC setup with two online rounds of communication.
Proof. Observe that in Algorithm I the overall computation only requires known 2PC protocols for addition, secure exchange, and multiplication. Addition does not require any online rounds. It is known that multiplication online round. Finally secure exchange requires one online round of communication. Hence the total number of online rounds of communication is two.
be implemented using Beaver Triplets Beaver (1991) in one
5

---

Under review as a conference paper at ICLR 2022
5 FAST LINEAR TRANSFORMATION USING THE HADAMARD-DIAGONAL MATRICES
One elementary computation in neural network is linear transformation: y Wæ, where Rd W E R E R&* This operation is expensive due to the ((dk) multiplications involved. In the MPC setup, both W and æ are enerypted and thus computing their product requires bandwidth proportional to (ddk), which can be prohibitive.
In this paper we propose impose specific types of structure on the W matrix. For simplicity, let us assume &o <ا We propose using W = HD, where D E Rd is a diagonal matrices with matrix of order d with the following
learnable weights, and H the normalized recursive definition:
1 v2
[
-
H2
Hgt-1
111 = H2
H2t 2
H2t
- Hzs
5.1 THEORETICAL MOTIVATIONS
Speeding up linear transformations y = Wr has been an extensively studied topic under different applications. For example, in dimensionality reduction < d), when the element of W are sampled iid from a Gaussian distribution, the well-known distance of the original space is approximately preserved in the new space. Here W can be replaced by structured matrices such as the fast Johnson-Lindenstraus transformation (a sparse matrix, Hadam-- matrix, and a random binary matrix) (Ailon Chazelle [006), sparse matrices (Matoušck] 2008) and circulant matrices (Hinrichs & Vybíral 2011). Such matrices give faster computation with similar error bound. Another example is binary embedding y = sign(Wx), x). When elements of W are sampled iid from the standard Gaussian distribution, the Hamming distance of the new space approximates the angle of the original space. Similarly, this operation can be made faster with structured matrices such circulant (Yu al. 2018) and bilinear matrices (Gong al., 2013). Several types of structures have also been applied in speeding up the fully connected layers neural networks. Examples circulant (Cheng et 2015), fastfood (Yang al. 2015) low- displacement rank (Thomas et al. 2018) matrices.
lemma states that the 12
The reason why we chose use the Hadamard-Diagonn structure goes back the literature of kernel approximation. It was shown that by using such a structure, the mapping y cos Wx) provides even lower approximation error of shift-invariant kernel (Yu al. (016) in comparison with the random unstructured matrices. Notice that other types of structures such as "fastfood" (Le) cet al. 2013) and circulant do not have such good properties. By pairing cosine with the Hadamard- Diagonal structure, even at initialization, the feature space already well mimic that of kernel. Furthermore, by optimizing the weights of the diagonal matrices, we are implicitly learning good shift invariant kernel for the task. In Section 6 we show that this structure almost does not hurt the quality of the model while reducing the computational cost. We also show in the appendix that cosine is indeed performing better than circulate and fastfood.
5.2 CoST COMPUTING THE HADAMARD-DIAGONAN TRANSFORMATION
There are two operations in computing the Hadamard Diagonnal transformation.
Multiplication with a variable diagonal matrix. This involves O(d) secure multiplications. 2. Multiplication with fixed Hadamard matrix. Since the Hadamard matrix is linear trans- formation that is fixed and publicly known, multiplying vector with Hadamard matrix requires (d log d) sums and subtractions on each server locally and does not require any communication between the servers.
Thus computing Dr for vector I. requires Od d) sums and subtractions locally and Odd bits of communication. This is significantly smaller than the traditional matrix vector multiplication, which requires ((d) bits of communication between the two servers. Note that one can simply
I d can be handled with picking the first à elements of the output. can be padded with Os such that d a power of 2.

---

Under review as a conference paper at ICLR 2022
improve the model capacity by using multiple HD blocks such as y HDgHD,HD12 We empirically observe that more blocks only provides marginal quality improvements, yet much high computational cost. So in this work, advocate using single HD block.
6 EXPERIMENTS
In this section, we study how modeling choices affect the model prediction accuracy. These choices include the optimization method, activation function, number of layers, and structure of weight matrices. For all the experiments, use SGD the optimizer it is known that implementing optimizers which compute moments such as Adam incurs significantly more overhead MPC setup. For all the datasets, sweep learning rates in the set {le-5, le-4, 1e-3, 0.01, 0.1, 0.5). and show the best averaged result over five trials. We note that our goal here is not to produce the state-of-the- art results datasets consider. In fact under the MPC setup, it is not practical to use many more advanced architectures (e.g. attention), optimizes (e.g. Adam) and techniques (e.g. batchnorm), Rather, we aim investigate the predictive performance of simple models that are suitable for the MPC setup. More specifically, we provide empirical evidence for the following important findings:
1. Cosine activation performs better than other existing activation functions in the 2PC setup. Furthermore, the performance significantly superior the network has many layers.
2. Replacing dense matrices with Hadamard-diagonal matrices incurs only small perfor- mance degradation.
We report additional results in the appendix. There, we show that cosine activation is more stable to train compared to square activation and hence is preferred in the MPC setup. While the use of an adaptive optimization procedure like Adam (Kingma & Bal 2014) is limited the MPC setting, for completeness, we report our results with Adam in the appendix, where we show that cosine still performs better than other existing activation functions. In the main text, we will focus on SGD as our optimization method of choice. For all experimental results reported, the standard deviation computed across trials in the order of 0.1 or smaller i.e., the only factor of variability is the initialization. We omit the standard deviation for brevity.
6.1 DATASETS AND MODELS
Datasets We consider four classification datasets: MNIST, Fashion-MNIST, Higgs, and Criteo. These data cover challenging problems from computer vision, physics and online advertising do- mains, respectively. Briefly the MNIST and Fashion-MNIST datasets are 10-class classification problems where each example is an image of size 28 28 pixels. The Higgs datasef represents a problem of detecting the signatures of Higgs Boson from background noise (Baldi et al. 2014). This is binary classification problem where each record consists of 28 floating-point features rep- resenting kinematic properties. We randomly subsample 7.7M records (70%) from the available 11M examples, and use them for training. The remaining 3.3M records are used for testing. The Criteo dataset is a challenging ad click-through rate prediction problem, and was used as part of public Kaggle competition] There are 36 million records in total with 25.6% labeled as clicked. We preprocess the Criteo data following the setup of Wang et al. (2017). More technical details regarding these datasets and propcessing steps can found Section A in the appendix.
Models For MNIST and Fashion-MNIST" we use LeNet-5 (LeCun et al. 1998) as the model, where the activation functions in the last two hidden layers are replaced. For Higgs data, we use Multi- Layer Perceptron (MLP) model with four hidden layers, each with 16 units. A discussion number of layers and more results are presented in the appendix to show training stability different activation functions. For Criteo, we follow Wang et al. (2017) and use an MLP with four hidden layers, with 1024 hidden units in each. In all cases, we consider three variants for each dense layer in the model: 1) the standard dense (fully connected) layer, 2) the fast Hadamard Hadamard-Diagonia layer as
the
2 Higgs dataset is available at wttpttttp///mm /www. www.wrffrrro..oo ow www.oo//ttt.tte/aaaaaaateteeeeee 'The Criteo dataset was used as prediction problem as part of the Display Advertis- ing Challenge in 2014 (a Kaggle competition) by Criteo (https: //o/:///www.. kagg com/ c/ criteo-di www.dispay---....... ad- chal lenge).
og/ht ggs
7

---

Under review as a conference paper at ICLR 2022
Activation
MNIST
Fashion-MNIITT
Higgs
Critco
Cosine 6" -
99.1
88.0
74.4
57.8
98.0
86.6
50.0
57.1
None
92.2
83.6
63.5
57.0
ReLU Polyfit(3)
99.0
87.4
64.8
57.5
Square
80.9
61.8
50.0
59.0
ReLU (non MPC baseline)
99.1
90.0
74.2
59.5
Summary of results all the datasets using the standard unstructured dense layer. We report test accuracy except Criteo where we report AUC-PR due to its skewed label distribution. Even though ReI.U cannot be computed in the MPC setup, we state its performance for reference.
Table 2:
proposed in Section 5 and dense layer where the weight matrix has rank most i.e., the weight matrix W 1/2 where both matrices Vi and 1/2 have two rows.
6.2 ACTIVATION FUNCTIONS
Table summarizes our results for different activa- tion functions. Recall that for each activation func- tion, we report the best trial-averaged performance across number of learning rate candidates (trained with SGD). Here we use the standard dense layer, as opposed structured weight matrix. We report the test accuracy for all datasets, except for Criteo where instead report AUC-PR which is more appropri- ate for its skewed label distribution. We observe that our proposed cosine activation function performs as well as the standard activation function like ReLU, while being more computationally tractable for the 2PC setup. To understand other activation functions, consider the example Higgs dataset. In this dataset, using activation function yields accuracy of 63.5%, whereas ex - and Square only performance the chance level since theses models struggle train without numerical issue. Specifically, closer inspection reveals that these activation functions grow fast, and require a careful choice of the optimization method, and learning rate to prevent numerical overflow. By contrast, cosine is bounded and is more robust to sub-optimal choice of the optimization algorithm (more on this point in the appendix).
COS
None
ReLU Polyfiti3)
e*
ReLU
Square
accuracy
0.65
0.60
0.55
0.50
0
Number hidden layers function of the number of hidden layers in the Higgs problem. We use the proposed Hadamard- Diagonal layer with each activation function listed.
Figure 2: Test accuracy
We also investigated the performance of these activations as a function of number of layers for the Higgs dataset. The results are given in Figure where the proposed Hadamard structure is used for all activation functions. While most activation functions perform well with fewer hidden layers, only cosine and ReLU performs well as the number of layers increases. This is because these functions grow at most linearly as their derivatives are bounded by one, and do not require a careful tuning of the learning rate prevent numerical overflow. We note that the same observation holds true when we use the standard dense layer, and a low rank weight matrix. We omit these results for brevity. More discussion on this aspect can be found in Section B.2 in the appendix.
6.3 STRUCTURED MATRICES
Next we investigate the effect of using a structured weight matrix in each dense layer. To this end, we consider the cosine activation function for all datasets, and consider replacing each dense layer with one of the three variants described in Section 6.1] 1) the standard dense layer (Dense), 2) the proposed Hadamard- -iagonnal layer (Hadamard) as described in Section [ and 3) dense layer with weight matrix of at most rank two (Low rank). We present test accuracy and AUC-PR in Table can be seen that using the Hadamard weight matrix incurs a minor loss of performance across different datasets, compared the standard dense layer. Recall that the number of parameters in
8

---

Under review as a conference paper at ICLR 2022
the proposed quadratic as in the standard dense layer. Interestingly the performance of the low-rank weight matrix lower than that of the Hadamard weight matrix, even though it has four times many learnable parameters. This hints that having an orthogonal weight matrix helps increase expressiveness of the model, presumably because it forms basis in the latent feature space of the network.
Diagonal layer is only linear in the number of inputs, as opposed to being
Structure
# secure mult.
MNIST Rishion-MNIST
Higgs
Criteo
Dense
d²
99.1
88.0
74.4
57.8
Low rank
4d
94.4
84.9
67.9
25.6
Hadamard
98.5
88.9
70.3
58.0
Table 3: Test accuracy on the four problems with cosine activation function. For Criteo where the label distribution is skewed, we report AUC-PR.
In fact, we observe that the superiority of the Hadamard- Diagoonal layer to the low-rank weight matrix is not specific to cosine. We provide evidence in Table 4 where report performance Fashion-MNIST and Criteo for each combination activation function and type of weight structure. Note that for Criteo, since the two classes skewed with roughly 25% of the data belonging to the positive class, we report AUC-PR instead of the test accuracy. We observe that in most cases our proposed Hadamard structure yields models with higher performance than the low rank approach does for all activation functions, while being competitive to the standard dense layer (which has an order of magnitude more parameters). We include comparisons
baselines in Table 2 in the
Appendix: PHD (Yng et al., 2015) and Circulant matrix (Cheng et al. 2015). Hadamard tranform to the best performing approach.
There too we find
Rashion-MNISS Low rank
Criteo Low rank
Activation
Dense
Hadamard
Dense
Hadamard
Cosine
88.0
84.9
88.9
57.8
25.6
58.0
ex
86.6
54.2
85.9
57.1
57.4
57.4
None
83.6
73.8
83.6
57.0
56.8
48.5
ReLU Polyfit(3)
87.4
83.8
88.7
57.5
25.6
52.7
Square
61.8
35.0
35.7
59.0
25.6
25.6
ReLU (non MPC baseline)
90.0
86.3
89.2
59.5
57.7
46.6
Table Test accuracy of the LeNet-5 model (LeCun et al. 1998) on Fashion-MNIST for each com- bination of activation function and type of the weight matrix. For Criteo, we use standard feed- forward MLP with four hidden layers, each containing 1024 hidden units. Our proposed Hadamard structure works better than the low rank approach in most cases, for all activation functions, while being competitive to the standard dense layer (where no structure is imposed).
7 DISCUSSION AND FUTURE WORK
The HD-cos approach offers a generic, computationally efficient building block for training and inference of neural network in the multi-party computation setup. The efficiency gain is result of two novel ideas: 1) use a fast Hadamard transform in place of the standard dense layer to reduce the number of parameters from d2 to d parameters where d is the input dimension; use cosine the activation function. As we demonstrated, the smoothness and boundedness of its derivative helps ensure robust training even when the learning rate is not precisely chosen. Both of these properties are of obvious value; yet a natural question remains: can we reduce the computational cost even further? A potential idea is combine HD-cos with Johnson-LLndeensrraus random projection, which reduces the input dimensionality (without learnable parameters) while preserving distances. Investigating this would be interesting topic for future research.

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
For all experiments, unless stated otherwise, the hyperparameters are set to the default values as provided by Tensorflow. Instructions to download datasets used in this work and processing steps necessary to reproduce our results are described in Section 6.] The proposed HD-cos approach consists of known building blocks (i.e., cosine, and the fast Hadamard transform) and are thus easy to apply. Our contributions are from showing their utility in the Multi-Party Computation (MPC) setup. To our knowledge, no previous work has attempted to study cosine and the fast Hadamard transform in the context of MPC.
REFERENCES
Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast transform. In Proceedings of the ehirty-eighth annual ACM symposium on Theory of computing, pp. 557-563, 2006.
Louis JM Aslett, Pedro M Esperança, and Chris C Holmes. review homomorphic encryption and software tools for encrypted statistical machine learning. arXiv preprint arXiv: 100.5508777777 2015.
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with Deep Learning. Nature Communications, 5:4308, 2014. doi: 10. 10.0//ccmmms5308..
Mauro Barni, Claudio Orlandi, and Alessandro Piva. privacy- preeccypressrvvng protocol for neural- network-based computation. In Proceedings of the 8th workshop on Multimedia and security, pp- 146-151, 2006.
Donald Beaver. Efficient multiparty protocols using circuit randomization. In Annual International Cryptology Conference, pp. 420-432. Springer, 1991.
Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel, and Emmanuel Prouff. privacypreseervng classification on deep neural network. International Association for Crypto- logic Research. ePrint Archive., 2017:35, 2017.
Yu Cheng, Felix X. Yu, Rogerio S Feris, Sanjiv Kumar, Alok Choudhary, and Shih-Fu Chang. An exploration of parameter redundancy in deep networks with circulant projections. In Proceedings of the IEEE international conference computer vision, pp. 2857-2865, 2015.
Kacper P Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations probability measures. Advances in Neural Information Processing Systems, 28:1981 19519111-99,, 2015.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4::21 (1:4)22114000 1-707, 2014.
David Evans, Vladimir Kolesnikov, and Mike Rosulek. A pragmatic introduction to secure multi- party computation. Foundations and Trends in Privacy and Security, 2(2-3), 2017.
Ran Gilad-Bachrach Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Werns- ing. Cryptonets: Applying neural networks encrypted data with high throughput and accuracy. In International conference on machine learning. pp. 201-210. PMLR, 2016.
Yunchao Gong, Sanjiv Kumar, Henry A Rowley, and Svetlana Lazebnik. Learning binary codes for high-dimensional data using bilinear projections. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 484 2013.
Thore Graepel, Kristin Lauter, and Michael Nachrig. ML confidential: Machine learning on en- crypted data. In International Conference Information Security and Cryptology, pp. 1-21. Springer, 2012.
Aicke Hinrichs and Jan Vybíral. Johnson-Lindensen lemma for circulant matrices. Random Structures & Algorithmss, 39(3):391-399, 2011.
10

---

Under review as a conference paper at ICLR 2022
Bargav Jayaraman and Lingxiao Wang. Distributed learning without distress: Privacy-pree preserving empirical risk minimization. Advances in Neural Information Processing Systems, 2018.
Mahimna Kelkar, Phi Hung Le, Mariana Raykova, and Karn Seth. Secure Poisson regression. In-
lernational Association for Cryptologic Researc. ePrint Archive., 2021:208, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1eXiv:1412.6966 2014.
Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. Crypten: Secure multi-party computation meets machine learning. arXiv preprint arXiv:2109.00900 2021.
Quoe Le, Tamás Sarlós, Alex Smola, al. Fastfood: approximating kernel expansions in loglinear time. In Proceedings of the international conference on machine learning, volume 85, 2013.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322, 1998.
Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [On- line]. Available: http://yann.lecm wttp://ww......o/////mmeem 2, 2010.
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J Sutherland. Learn- ing deep kernels for non-parametric two-sample tests. In International Conference on Machine Learning, pp. 6316-6326. PMLR, 2020.
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.
Jiří Matoušck. On variants of the Lindesstsnnd lemma. Random Structures & Algorithms, 33(2):142-156, 2008.
Payman Mohassel and Yupeng Zhang. Secureml: system for scalable learning. In 2017 IEEE symposium security and privacy (SP), pp. 19-38. IEEE, 2017.
machine
Mathew Mithra Noel, Advait Trivedi, Praneet Dutta, al. Growing cosine unit: novel oscilla- tory activation function that can speedup training and reduce parameters in convolutional neural networks. arXiv preprint arXiv:2 108. /2943, 2021.
Srinath Obla, Xinghan Gong, Asma Aloufi, Peizhao Hu, and Daniel Takabi. Effective activation functions for homomorphic evaluation of deep neural networks. IEEE Access, 8:153998-153112 2020.
Claudio Orlandi, Alessandro Piva, and Mauro Barni. Oblivious neural network computing via ho- momorphic encryption. EURASIP Journal on Information Security, 2007:1-11, 2007.
Giambattista Parascandolo, Heikki Huttunen, and Tuomas Virtanen. Taming the waves: sine as activation function in deep neural networks. Unpublished, available on openreview.net, 2016.
Jeffrey Pennington, Felix X. Yu, and Sanjiv Kumar. Spherical random features for polynomial kernels. Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume Volume 2, pp. 1846-1854, 2015.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 2007.
Bharath Sriperumbudur and Zoltán Szab6. Optimal rates for random Fourier features. In Advances in Neural Information Processing Systems, 2015.
Anna T Thomas, Albert Gu, Tri Dao, Atri Rudra, and Christopher Ré. Learning compressed trans- forms with low displacement rank. Advances Neural Information Processing Systems, 2018: 9052, 2018.
11

---

Under review as a conference paper at ICLR 2022
Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. Deep and cross network for ad click predic- tions. In Proceedings of the ADKDD' 17, New York, NY, USA, 2017. Association for Computing Machinery. doi: 10.1 (0.1145/124449.312444
Wei Wu, Jian Liu, Huimei Wang, Fengyi Tang, and Ming Xian. Ppolynets: Achieving high pre- diction accuracy and efficiency with parametric polynomial activations. JEEE Access, 6:72814- 72823, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for bench- marking machine learning algorithms. CoRR, abs/1708.07747,, 2017. URL htttp://axxi>
org/abs/1708 07747
Jiaxuan Xie, Fanghui Liu, Kaijie Wang, and Xiaolin Huang. Deep kernel learning via random Fourier features. arXiv preprint arXiv:1910.02660, 2019.
Jiyan Yang, Vikas Sindhwani, Haim Avron, and Michael Mahoney, Quasi-Monte Carlo feature maps for shift-invariant kernels. In Proceedings of International Conference on Machine Learning, 2014.
Zichao Yang, Marcin Moczulski, Misha Denil, Nando De Freitas, Alex Smola, Le Song, and Ziyu Wang. Deep fried convnets. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1476-1483, 2015.
Felix X. Yu, Sanjiv Kumar, Henry Rowley, and Shih-Fu Chang. Compact nonlinear maps and circulant extensions. arXiv preprint 1531v31503.0388. 2015.
Felix X. Yu, Ananda Theertha Suresh, Krzysztof M Choromanski, Daniel N Holtmann-Rice and Sanjiv Kumar. Orthogonal random features. Advances in neural information processing systems, 29:1975-1983, 2016.
Felix X. Yu, Aditya Bhaskara, Sanjiv Kumar, Yunchao Gong, and Shih-Fu Chang. On binary em- bedding using circulant matrices. Journal of Machine Learning Research, 18(150):1-30, 2018.
12

---

Under review as a conference paper at ICLR 2022
HD-cos NETWORKS: EFFICIENT NEURAL ARCHITECHTURES FOR SECURE MULTI-PARTY COMPUTATION
Supplementary Material
A DATASETS AND PREPROCESSING
This section contains technical details of all datasets and preprocessing we use in experiments in the main text.
MNIST and Fashion-MNIST The MNIST datahase contains 60,000 training and 10,000 test images of handwritten digits (LeCun et al. 2010). Each image is of size 28 28 pixels and represents one of the digits (0 to 9). The Fashion- -NNIS dataset (Xiao et al. 2017) is a drop-in replacement for MNIST with the same image size and dataset size. Here each example is an image of one of the ten selected fashion products e.g.. T-shirt, shirt, bag. For these two datasets, models are trained for 200 epochs with a batch size of 128.
Higgs The Higgs dataset represents a problem of detecting the signatures of Higgs Boson from background noise (Baldi et al., 2014). This binary classification problem where each record consists of 28 floating- ppint features, of which 21 features representing kinematic properties, and additional seven features are derived from the 21 features by physicists to help distinguish the two classes. The dataset is regarded as challenging multivariate problem for benchmarking nonpara- metric two-sample tests i.e., statistical tests to detect the difference of between the distributions of the two classes (Chwialkowski et al. 2015; Liu et al.) 2020). Out of the available IM records, randomly subsample 7.7M records (70%) and use them for training. No feature normalization or standardization is performed. The remaining 3.3M records are used for testing. We train models Higgs data for 40 epochs with a batch size of 256.
Criteo The Criteo dataset challenging ad dick-througlh rate prediction problem, and was used as part of a public Kaggle competition Here, the label is binary (clicked or not clicked), and the feature vector encodes user information and the page being viewed. Each feature vec- tor consists of 39 features, of which 13 are integer and 26 are categorical. There are 36 million records in total with 25.6% labeled as clicked. Following WWang et al. (017)), we split the data into 80%/10%//00 for training, evaluation and testing, respectively. For each categorical feature, each value its range is mapped to a trainable token embedding vector whose length is given by 6 x (cardinality of the feature))/1. Fach integer feature x E N is mapped to log(1 + x)). Concate- nating all the preprocessed features gives dense vector of length 1023, from which we feed to standard multi-layer perceptron. All the models are trained for 150k update steps with a batch size of 512.
'The Criteo dataset was used as prediction problem as part of the Display Advertis- ing Challenge in 2014 (a Kaggle competition) by Criteo (ttpps: / /wwww kagg le com/ c/ criteo-disg sioo-displly-aooe ad- chal lenge).
13

---

Under review as a conference paper at ICLR 2022
B ADAPTIVE OPTIMIZATION AND TRAINING STABILITY
In the main text, we omit the results for all learning rates and choose present only the best perfor- mance across learning rates for each activation and type of weight structure, for the sake of brevity. In this section, we report results for all learning rates, study the interplay between the network depth and the choice of the activation function, as well as investigate the use of an adaptive optimization method like Adam (Kingma & Ba. 2014).
Note again that for all experimental results reported in this paper, the standard deviation computed across trials the order of 0 or smaller i.e., the only factor of variability the initialization. We omit the standard deviation for brevity.
B. OPTIMIZATION ALGORITHMS
We show that the optimization method used affects the performance of each activation function differently. To demonstrate, consider the MNIST dataset and use the LeNet-5 (LeCun et al. 1998) model; this is a convolutional neural network with two convolution layers interleaved with average pooling layers, followed by dense layers. Each of the convolution and dense layers has an activation function. Activation function candidates are cosine (proposed), exponential, none (no activation function), ReLU, ReLU Poly(3), and square. The ReLU Poly(3) degree-3 polynomial approximation of ReLU investigated in (Obla et al.] 2020). Unlike ReLU which is expensive to implement the MPC setup (i.e., requires scalar comparison). polynomial only relies on multi- plication and addition, and is more suitable for MPC. We consider f(x) ex - instead of e* so that f(0) = property common to many activation functions. Table 5 shows the test accuracy for different optimization methods: Stochastic Gradient Descent (SGD) vs Adam (Kingma & Ba 2014), learning rates, and activation functions.
Learning rate Activation
1e 15
1e
1e-3
1e
0.01
0.1
0.5
Optimizer
Cosine
.96
.99
.92
.98
.54
.10
e
.97
.98
.99
.10
.10
.10
Adam
None
.91
.92
.92
.91
.91
.91
ReLU
.97
.99
.98
.98
.45
.10
ReLU Poly(3)
.90
.98
.98
.86
.10
.10
Square
.96
.99
.69
.81
.10
.10
Cosine
.69
.95
.97
.98
.92
.10
e" -1
.93
.63
.39
.10
.10
.10
SGD
None
.88
.91
.91
.92
.91
.10
ReLU
.52
.96
.97
.98
.98
.10
ReLU Poly(3)
.13
.94
.86
.98
.69
.10
Square
.27
.10
.40
.16
.10
.10
Table 5: Test accuracy of the LeNet-5 model (LeCun et al. 1998) on MNIST for different optimiza- tion methods, learning rates, and activation functions. The optimization method used affects the performance of each activation function differently. The cosine activation offers generic, robust construct that can be trained without the need of precisely choosing the learning rate.
When no activation function used, the model achieves roughly the same performance for both optimization algorithms across different learning rates. On the other hand, the performance of other nonlinear activations changes with different optimization methods. In particular, for activation function that grow fast (i.e., e" 1. square), it is crucial to use an optimization method equipped with an adaptive learning rate like Adam to ensure stable training. By contrast, for standard choice such as the linearly growing ReLU function, and a bounded function such as cosine, the model can learn with either optimizer without precise tuning of the learning rate.
Several important observations can be made from Table 5
14

---

Under review as a conference paper at ICLR 2022
B.2 TRAINING STABILITY AS FUNCTION OF NETWORK DEPTH
In this section, we expand results presented in Figure the main text by including the performance on Higgs for every learning rate tried. Our conclusion remains the same as discussed in Section 66.2 which is that activation functions with bounded derivatives (e.g., cos, ReLU) can be trained with a wide range learning rates, and different optimizers. By contrast, models relying on activation functions with high growth rate (e.g., exponential, square) can only be trained with careful choice of the learning rate. This training instability more pronounced when the number layers is larger (deeper network).
Learning rate Activation
1e-5
le
1e
0.01
0.1
0.5
Optimizer
Number of layers
.62
.63
.64
.64
.64
.64
.57
.65
.68
.69
.69
.58
Cosine
.55
.65
.69
.70
.70
.56
.54
.63
.70
.71
.71
.57
.52
.60
.70
.69
.71
.57
.62
.63
.64
.58
.66
.68
.69
.61
ReLU
.56
.66
.70
.70
.70
.63
SGD
.55
.65
.70
.70
.70
.56
.54
.64
.70
.71
.71
.56
.62
.63
.64
.64
.64
.64
.59
.65
.66
.66
.66
.55
Square
.66
.65
.68
.56
.50
.50
.54
.61
.52
.50
.50
.50
.62
.63
.64
.64
.64
.64
.60
.65
.67
.52
.50
.51
.50
.50
.50
.50
.50
.50
.50
.50
.50
.50
.50
.62
.64
.64
.64
.64
.63
.65
.68
.69
.69
.65
.50
Cosine
.66
.70
.71
.71
.60
.50
.66
.71
.72
.72
.60
.50
.66
.71
.72
.60
.60
.50
.63
.64
.64
.64
.63
.65
.68
.69
.70
.67
.50
ReLU
.66
.69
.71
.71
.69
.50
Adam
.66
.71
.72
.72
.64
.50
.66
.72
.50
0
.63
.64
.64
.64
.64
.63
.64
.66
.67
.67
.67
.66
Square
.65
.69
.57
.68
.70
.70
.64
.59
.62
.64
.64
.64
.64
.63
.64
.67
.68
.57
.50
2
.53
.50
.50
.54
.50
.50
.50
.50
.50
.50
.50
.50
Table 6: Experimental results on Higgs. Vary the numbers of hidden layers.
15

---

Under review as a conference paper at ICLR 2022
C STRUCTURED WEIGHT MATRICES
Here we expand results in Section 6.3 and present more results showing the influence of structured weight matrices the model performance. Table 7 and Table & give results the same setting as in Table 2 presented in the main text, except that each dense layer is replaced with the proposed Hadamard layer (Table and dense layer with low-rank weight matrix (Table 2
Activation
MNIST
Mishion-MNIST
Higgs
Criteo
Cosine
98.5
88.9
70.3
58.0
e" -
94.0
85.9
50.0
57.4
None
92.2
83.6
63.5
48.5
ReLU
98.4
89.2
69.8
46.6
ReLU Polyfit(3)
98.5
88.7
62.4
52.7
square
45.4
35.7
54.4
25.6
Table Test accuracy on all the datasets using the proposed Hadamard layer. We report accu- racy except Criteo where we report AUC-PR due to its skewed label distribution.
Activation
MNIST
Fashion-MNIST
Higgs
Criteo
Cosine
94.4
84.9
67.9
25.6
e" -1
86.2
54.2
50.0
57.4
None
68.4
73.8
63.5
56.8
ReLU
94.8
86.3
67.9
57.7
ReLU Polyfit(3)
94.5
83.8
56.7
25.6
Square
60.6
35.0
50.0
25.6
Table 8: Test accuracy on all the datasets using low-rank dense layers. We report test accuracy except Criteo where we report AUC-PR due its skewed label distribution.
For completeness, we also compare to other types of weight matrices: 1) PHD (Yang et al. 2015). 5). 2) circulant matrix (Yu et al. 2018). The PHD approach is similar our proposed proposed Hadamard layer. The weight matrix is given by W = PHD where P is a sparse matrix with non-zero entries drawn from Gaussian distribution, H the Hadamard matrix, and D the diagonal weight matrix. The PHD has the same number of parameters as our Hadamdard-Diagee -iagoonal (HD) approach. The main difference is the presence of the sparse matrix P. The circulant matrix approach of Yu et al.) (2018) also only requires d weights parameters. The weight matrix is formed by forming circulant matrix from these weights. We present a comparison these three related approaches on Fashion-MNIST in Table
We observe that our proposed Hadamard layer performs better than the PHD approach. This suggests that the presence of the sparse random matrix P hurts the expressiveness of the model. It can be seen that the circulant weight matrix generally does not performance as well as the other two variants.
Activation
Hadamard
PHD
Yang et al. 2015)
Circulant Cheng et al. 2015
Cosine c² -1
88.6
88.1
80.3
80.2
59,7
10.0
None
83.7
83.5
83.6
ReLU
89.3
89.0
89.4
ReLU Polyfit(3)
88.5
87.6
87.8
Square 36.0
36.0
87.6
Table Comparison Hadamard transform against other structures imposed on the weight matrix. Notice how Hadamard works better across most activation functions.
16


Reviews:
[{"review_id": "oa5WGIx8pO9", "reviewer": "Reviewer_g4Ma", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "While the ideas are interesting, the MPC aspects are insufficient:\n- The paper does not name a secret sharing domain. Usually, numbers are shared modulo an integer in order to achieve security via uniform distribution of shares. This modular operation would hinder the summand-wise cosine and sine computations in Algorithm 1.\n- It is common to use quantization with MPC because full floating-point computation is much more expensive. The authors don't specify how they have obtained their accuracy results. It would be insufficient to use floating-point computation because it is known that quantization reduces the accuracy [1].\n\nThe authors say that it is not efficient to implement ReLU accurately. However, there are implementations that do that, for example [2].\n\nMinor:\n- p4: (The) Kernel method is a type of powerful nonlinear\n- p6: is a diagonal matrices (matrix)\n- p6: Another example is (the) binary embedding\n\n[1] https://arxiv.org/abs/1502.02551\n[2] https://arxiv.org/abs/2104.10949\n\n", "summary_of_the_paper": "The paper proposes changes to improve the performance of neural network training with multi-party computation, that is an activation function based on cosine and a linear functionality that reduces the number of weights to be trained.\n", "summary_of_the_review": "The MPC aspects need more work.\n", "strength_and_weaknesses": "", "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": {}}, {"review_id": "PQgSM78Bf47", "reviewer": "Reviewer_7c3H", "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": "Strengths- The paper demonstrates the utility of cosine activation function and Hadamard transform in the privacy-preserving machine learning paradigm. The experimental results demonstrate the improvement on the prediction performance over benchmarks is promising. \n\nWeaknesses-\n1- The proposed approach combines well-known building blocks (e.g., cosine activation) that have been studied in the context of ML. Similarly, the secure computing component uses well-known cryptographic primitives such as Beaver's multiplication triplets. \n\n2 - The proposed setup is for a (non-colluding) two-server model, where the two parties do not cooperate with each other. The two server model is restrictive in practical settings\n\n3- The experiments do not include runtime comparisons between the baselines, or comparing the communication and computation costs, to demonstrate efficiency. \n\n4- The baselines do not provide an extensive comparison with the former two-party MPC approaches (for instance SecureML [Mohassel-Zhang] also discussed in the related works section). Thus, it would be good to clarify the motivation on the choice of baselines. \n\n\n", "summary_of_the_paper": "The paper proposes using a cosine activation function and Hadamard-Diagonal transformation as a means to improve the efficiency of MPC for machine learning. The paper considers a two-server model, where the training computation are carried out by two non-colluding parties. Experiments are provided to demonstrate the improvement on the test accuracy of the proposed approach over other baselines that use different activation functions.  ", "summary_of_the_review": "Improving the efficiency and predictive performance of MPC-based techniques for machine learning is an important problem. It would be good to include experiments that demonstrate the efficiency over the benchmarks. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OdpVp0fCXNh", "reviewer": "Reviewer_pKsC", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "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": "It seems to me that there is a fundamental flaw in how secret sharing is used: computing trigonometric functions on arithmetic secret shares makes no sense, as the shares are over a finite ring. I don't see a way to fix this problem.", "summary_of_the_paper": "This paper proposes using a 2-party MPC protocol for evaluating neural networks on private data by replacing activation functions with a cosine function, and another technique of replacing fully connected layers with a specially structured matrix.", "summary_of_the_review": "Unfortunately, it seems to me that this paper has a fundamental mistake and cannot be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NNDg8h34IAU", "reviewer": "Reviewer_w59J", "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": "Pros:\n1. Compare to ReLU in MPC with multiple rounds of communication, proposed cosine function in 2PC setup only involves two rounds of communication. Since communication overhead is a big deal in MPC among parties, cosine approach decreases the cost.\n2. Structure matrices used in the work can reduce bandwidth and save memory.\n3. Theoretical explanation for both methods is provided to convince reader in some way. \n\nCons:\n1. Since this work focuses on MPC approach, it is necessary to state what type of adversary model (semi-honest or malicious) is trying to deal with. More security analysis is expected if possible.\n2. Although communication cost is analyzed in words, fail to provide table or charts to show efficiency compared with existing methods, since “efficient” is in the title. With tables or charts would convince more.", "summary_of_the_paper": "MPC is a cryptographic technique to allow multiple party to jointly compute a protocol without leaking sensitive data, but building blocks in the neural network converted to MPC setup usually suffer from heavy communication overhead among parties, and jointly training ML models is also computationally expensive. So, in this work, authors propose an efficient MPC-based neural network. The network consists of cosine function as activation function under 2PC setup and linear transformations by Hadamard-Diagonal method.", "summary_of_the_review": "To be honest, this paper is below acceptance standard because of innovation and lack of security analysis, although the writing of manuscript looks great. So, currently, I think I would not accept this paper and looking forward to see other reviewers’ comments to make final decision.", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: There appears to be to be a fundamental error in the paper, w.r.t. the application of the proposed approach to finite fields. As a result, the paper cannot be accepted in its current form.
Decision: Reject