summaries: The paper focuses on the topic of differentially private deep learning. Specifically, based on the deep residual learning, they first see it as an ODE. Then, to reduce the reversibility of the ODE, they modify the model as an SDE. By discretizing the SDE, they get a perturbed version of residual learning and use this to design DP-algorithms. The first strategy is directly followed the SDE while the second strategy is with an addition multiplicative noise of the additive noise. Finally, they show that their methods to defend membership inference attack both theoretically and practically.

summaries: The paper presents a method for training ResNets with differential privacy. Rather than the usual methods based on noisy gradient descent, the authors propose adding noise at each layer of the network during both training and testing. The authors prove differential privacy guarantees for two strategies of this type (one with additive and one with multiplicative noise). They also show some evidence that the noise can help generalization, by showing that the Rademacher complexity of a continuous linearized version of the model is lower when noise is added.

summaries: This paper studies an important problem and proposes the novel residual perturbation to protect privacy while maintaining the ResNet models’ utility.  Two SDE models are provided to inject noises with abundant theoretical proof are provided. Experimental results demonstrate the performance of privacy protection and classification accuracy on benchmark datasets. My major concern is about the utility enhancement and the DP guarantee (see cons below). Hope the authors can address my concern in the rebuttal period.

abstractText: Protecting data privacy in deep learning (DL) is at its urgency. Several celebrated privacy notions have been established and used for privacy-preserving DL. However, many of the existing mechanisms achieve data privacy at the cost of significant utility degradation. In this paper, we propose a stochastic differential equation principled residual perturbation for privacy-preserving DL, which injects Gaussian noise into each residual mapping of ResNets. Theoretically, we prove that residual perturbation guarantees differential privacy (DP) and reduces the generalization gap for DL. Empirically, we show that residual perturbation outperforms the stateof-the-art DP stochastic gradient descent (DPSGD) in both membership privacy protection and maintaining the DL models’ utility. For instance, in the process of training ResNet8 for the IDC dataset classification, residual perturbation obtains an accuracy of 85.7% and protects the perfect membership privacy; in contrast, DPSGD achieves an accuracy of 82.8% and protects worse membership privacy.

authors:
Martin Abadi
Andy Chu
Ian Goodfellow
H. McMahan
Ilya Mironov
Kunal Talwar
Li Zhang

title: Deep Learning with Differential Privacy

venue: In 23rd ACM Conference on Computer and Communications Security (CCS 2016),

authors:
Martin Abadi
Andy Chu
Ian Goodfellow
H Brendan McMahan
Ilya Mironov
Kunal Talwar
Li Zhang

title: Deep learning with differential privacy

venue: In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,

authors:
Mohammad Al-Rubaie
J Morris Chang

title: Reconstruction attacks against mobile-based continuous authentication systems in the cloud

venue: IEEE Transactions on Information Forensics and Security,

authors:
Ho Bae
Dahuin Jung
Sungroh Yoon

title: Anomigan: Generative adversarial networks for anonymizing private medical data

venue: arXiv preprint arXiv:1901.11313,

authors:
Eugene Bagdasaryan
Omid Poursaeed
Vitaly Shmatikov

title: Differential privacy has disparate impact on model accuracy

venue: In Advances in Neural Information Processing Systems,

authors:
Peter L Barlett
Sahar Mendelson

title: Rademacher and gaussian complexities: Risk bounds and structural results

venue: Jounal of Machine Learning Research,

authors:
Marco Barreno
Blaine Nelson
Russell Sears
Anthony D Joseph
J Doug Tygar

title: Can machine learning be secure

venue: In Proceedings of the 2006 ACM Symposium on Information, computer and communications security,

authors:
Raef Bassily
Adam Smith
Abhradeep Thakurta

title: Private empirical risk minimization: Efficient algorithms and tight error bounds

venue: In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science,

authors:
Kamalika Chaudhuri
Claire Monteleoni
Anand D Sarwate

title: Differentially private empirical risk minimization

authors:
Jinshuo Dong
Aaron Roth
Weijie J Su

title: Gaussian differential privacy

venue: arXiv preprint arXiv:1905.02383,

authors:
Cynthia Dwork
Frank McSherry
Kobbi Nissim
Adam Smith

title: Calibrating noise to sensitivity in private data analysis

venue: In Theory of cryptography conference,

authors:
Khaled El Emam
Fida Kamal Dankar

title: Protecting privacy using k-anonymity

venue: Journal of the American Medical Informatics Association,

authors:
Wei Feng
Zheng Yan
Hengrun Zhang
Kai Zeng
Yu Xiao
Y. Hou

title: A Survey on Security, Privacy and Trust in Mobile Crowdsourcing

venue: IEEE Internet of Things Journal,

authors:
Matt Fredrikson
Somesh Jha
Thomas Ristenpart

title: Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures

venue: In 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS 2015),

title: Model inversion attacks that exploit confidence information and basic countermeasures

venue: In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security,

authors:
Matthew Fredrikson
Eric Lantz
Somesh Jha
Simon Lin
David Page
Thomas Ristenpart

title: Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing

venue: In 23rd {USENIX} Security Symposium ({USENIX} Security

authors:
Neil Zhenqiang Gong
Bin Liu

title: You are who you know and how you behave: Attribute inference attacks via users’ social friends and behaviors

venue: In 25th {USENIX} Security Symposium ({USENIX} Security

title: Attribute inference attacks in online social networks

venue: ACM Transactions on Privacy and Security (TOPS),

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Ehsan Hesamifard
Hassan Takabi
Mehdi Ghasemi
Rebecca N Wright

title: Privacy-preserving machine learning as a service

venue: Proceedings on Privacy Enhancing Technologies,

title: An algorithmic introduction to numerical simulation of stochastic differential equations

venue: SIAM review,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

title: Introduction to stochastic calculus with applications

authors:
Jakub Konečnỳ
H Brendan McMahan
Felix X Yu
Peter Richtárik
Ananda Theertha Suresh
Dave Bacon

title: Federated learning: Strategies for improving communication efficiency

venue: arXiv preprint arXiv:1610.05492,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Bai Li
Changyou Chen
Hao Liu
Lawrence Carin

title: On connecting stochastic gradient mcmc and differential privacy

venue: In The 22nd International Conference on Artificial Intelligence and Statistics,

authors:
Zhicong Liang
Bao Wang
Quanquan Gu
Stanely Osher
Yuan Yao

title: Exploring private federated learning with laplacian smoothing

venue: arXiv preprint arXiv:2005.00218,

authors:
Yehuda Lindell
Benny Pinkas

title: Privacy preserving data mining

venue: In Annual International Cryptology Conference,

authors:
Xuanqing Liu
Tesi Xiao
SiSi
Qin Cao
Sanjiv Kumar
Cho-Jui Hsieh

title: Neural sde: Stabilizing neural ode networks with stochastic noise

authors:
Yun Liu
Krishna Gadepalli
Mohammad Norouzi
George E. Dahl
Martin C. Stumpe

title: Detecting Cancer Metastases on Gigapixel

venue: Pathology Images

authors:
Ledoux M
Talagrand

title: Probability in Banach spaces: Isoperimetry and processes

authors:
H Brendan McMahan
Eider Moore
Daniel Ramage
Seth Hampson

title: Communication-efficient learning of deep networks from decentralized data

venue: arXiv preprint arXiv:1602.05629,

authors:
H Brendan McMahan
Galen Andrew
Ulfar Erlingsson
Steve Chien
Ilya Mironov
Nicolas Papernot
Peter Kairouz

title: A general approach to adding differential privacy to iterative training procedures

venue: arXiv preprint arXiv:1812.06210,

title: Rényi differential privacy

venue: IEEE 30th Computer Security Foundations Symposium (CSF),

authors:
Nicolas Papernot
Martı́n Abadi
Lfar Erlingsson
Ian Goodfellow
Kunal Talwar

title: Semisupervised Knowledge Transfer for Deep Learning from Private Training Data

venue: In 5th International Conference on Learning Representation (ICLR

authors:
Nicolas Papernot
Shuang Song
Ilya Mironov
Ananth Raghunathan
Lfar Erlingsson

title: Scalable Private Learning with PATE

venue: In International Conference on Learning Representations (ICLR

authors:
Adnan Siraj Rakin
Zhezhi He
Deliang Fan

title: Parametric noise injection: Trainable randomness to improve deep neural network robustness against adversarial attack

venue: arXiv preprint arXiv:1811.09310,

authors:
Alexandre Sablayrolles
Matthijs Douze
Cordelia Schmid
Hervé Jégou

title: D\’ej\a vu: an empirical evaluation of the memorization properties of convnets

venue: arXiv preprint arXiv:1809.06396,

authors:
Ahmed Salem
Yang Zhang
Mathias Humbert
Pascal Berrang
Mario Fritz
Michael Backes

title: Ml-leaks: Model and data independent membership inference attacks and defenses on machine learning models

venue: arXiv preprint arXiv:1806.01246,

authors:
Reza Shokri
Vitaly Shmatikov

title: Privacy-Preserving Deep Learning

authors:
Reza Shokri
Marco Stronati
Congzheng Song
Vitaly Shmatikov

title: Membership inference attacks against machine learning models

venue: IEEE Symposium on Security and Privacy (SP),

title: k-anonymity: A model for protecting privacy

venue: International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems,

authors:
Florian Tramèr
Fan Zhang
Ari Juels
Michael K Reiter
Thomas Ristenpart

title: Stealing machine learning models via prediction apis

authors:
Bao Wang
Quanquan Gu
March Boedihardjo
Farzin Barekat
Stanley J Osher

title: Dp-lssgd: A stochastic optimization method to lift the utility in privacy-preserving erm

venue: arXiv preprint arXiv:1906.12056,

authors:
Bao Wang
Zuoqiang Shi
Stanley Osher

title: Resnets ensemble via the feynman-kac formalism to improve natural and robust accuracies

authors:
Yu-Xiang Wang
Stephen Fienberg
Alex Smola

title: Privacy for free: Posterior sampling and stochastic gradient monte carlo

venue: In International Conference on Machine Learning,

authors:
Zhibo Wang
Mengkai Song
Zhifei Zhang
Yang Song
Qian Wang
Hairong Qi

title: Beyond inferring class representatives: User-level privacy leakage from federated learning

venue: In IEEE INFOCOM 2019-IEEE Conference on Computer Communications,

authors:
Bingzhe Wu
Chaochao Chen
Shiwan Zhao
Cen Chen
Yuan Yao
Guangyu Sun
Li Wang
Xiaolu Zhang
Jun Zhou

title: Characterizing membership privacy in stochastic gradient langevin dynamics

venue: arXiv preprint arXiv:1910.02249,

authors:
Bingzhe Wu
Shiwan Zhao
Guangyu Sun
Xiaolu Zhang
Zhong Su
Caihong Zeng
Zhihong Liu

title: P3sgd: Patient privacy preserving sgd for regularizing deep cnns in pathological image classification

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Samuel Yeom
Irene Giacomelli
Matt Fredrikson
Somesh Jha

title: Privacy risk in machine learning: Analyzing the connection to overfitting

venue: IEEE 31st Computer Security Foundations Symposium (CSF),

authors: Yuen Man-Ching King Irwin Leung Kwong-Sak

title: A Survey of Crowdsourcing Systems

venue: In Proceedings of the IEEE international conference on social computing (Socialcom

authors:
Xu Zheng
Zhipeng Cai
Yingshu Li

title: Data linkage in smart internet of things systems: A consideration from a privacy perspective

venue: IEEE Communications Magazine,

authors:
Ligeng Zhu
Zhijian Liu
Song Han

title: Deep leakage from gradients

heading: 1 INTRODUCTION

text:
Many high-capacity deep nets (DNs) are trained with private data, including medical images and financial transaction data (Yuen et al., 2011; Feng et al., 2017; Liu et al., 2017). DNs usually overfit and can memorize the private training data, which makes training DNs exposed to data privacy leakage (Fredrikson et al., 2015a; Shokri et al., 2017; Salem et al., 2018; Yeom et al., 2018; Sablayrolles et al., 2018). Given a pre-trained DN, the membership inference attack can determine if an instance is in the training set based on DN’s response (Fredrikson et al., 2014; Shokri et al., 2017; Salem et al., 2018); the model extraction attack can learn a surrogate model that matches the target model, given the adversary only black-box access to the target model (Tramèr et al., 2016; Gong & Liu, 2018); the model inversion attack can infer certain features of a given input from the output of a target model (Fredrikson et al., 2015b; Al-Rubaie & Chang, 2016); the attribute inference attack can deanonymize the anonymized training data (Gong & Liu, 2016; Zheng et al., 2018).
Machine learning (ML) with data privacy is crucial in many applications (Lindell & Pinkas, 2000; Barreno et al., 2006; Hesamifard et al., 2018; Bae et al., 2019). Several algorithms have been developed to reduce privacy leakage include differential privacy (DP) (Dwork et al., 2006), federated learning (FL) (McMahan et al., 2016; Konečnỳ et al., 2016), and k-anonymity (Sweeney, 2002; El Emam & Dankar, 2008). Objective, output, and gradient perturbations are among the most used approaches for ML with DP guarantees at the cost of significant utility degradation (Chaudhuri et al., 2011; Bassily et al., 2014; Shokri & Shmatikov, 2015; Abadi et al., 2016b; Bagdasaryan et al., 2019). FL trains centralized ML models, through gradient exchange, with the training data being distributed at the edge devices. However, the gradient exchange can still leak the privacy (Zhu et al., 2019; Wang et al., 2019c). Most of the existing privacy is achieved at a tremendous sacrifice of utility. Moreover, training ML models using the state-of-the-art DP stochastic gradient descent (DPSGD) leads to tremendous computational cost due to the requirement of computing and clipping the per-sample gradient (Abadi et al., 2016a). It remains a great interest to develop new privacy-preserving ML algorithms without excessive computational overhead or degrading the utility of the ML models.

heading: 1.1 OUR CONTRIBUTION

text:
In this paper, we propose residual perturbation for privacy-preserving deep learning (DL) with DP guarantees. At the core of residual perturbation is injecting Gaussian noise to each residual mapping
of ResNet (He et al., 2016), and the residual perturbation is theoretically principled by the stochastic differential equation (SDE) theory. The major advantages of residual perturbation are threefold: • It can protect the membership privacy of the training data almost perfectly and often without
sacrificing ResNets’ utility. Furthermore, it can even improve ResNets’ classification accuracy. • It has fewer hyperparameters to tune than the benchmark DPSGD. Also, it is more computationally
efficient than DPSGD, which requires to compute the per-sample gradient. • It can be easily implemented by a few lines of code in modern DL libraries.

heading: 1.2 RELATED WORK

text:
Improving the utility of ML models with DP guarantees is an important task. PATE (Papernot et al., 2017; 2018) uses semi-supervised learning together with model transfer between the “student” and “teacher” models to enhance utility. Several variants of the DP notions have also been proposed to improve the privacy budget and some times can also improve the resulting model’s utility at a given DP budget (Abadi et al., 2016b; Mironov, 2017; Wang et al., 2018; Dong et al., 2019). Some post-processing techniques have also been developed to improve the utility of ML models with negligible computational overhead (Wang et al., 2019a; Liang et al., 2020). From the SDE viewpoint, (Li et al., 2019; Wang et al., 2015) showed that several stochastic gradient Monte Carlo samplers could reach state-of-the-art performance in terms of both privacy and utility in Bayesian learning.
Gaussian noise injection in residual learning has been used to improve the robustness of ResNets (Rakin et al., 2018; Wang et al., 2019b; Liu et al., 2019). In this paper, we inject Gaussian noise to each residual mapping to achieve data privacy instead of adversarial robustness.

heading: 1.3 ORGANIZATION

text: We organize this paper as follows: In Section 2, we introduce the residual perturbation for privacypreserving DL. In Section 3, we present the generalization and DP guarantees for residual perturbation. In Section 4, we numerically verify the efficiency of the residual perturbation in protecting data privacy without degrading the underlying models’ utility. We end with some concluding remarks. Technical proofs and some more experimental details and results are provided in the appendix.

heading: 1.4 NOTATIONS

text: We denote scalars by lower or upper case letters; vectors/ matrices by lower/upper case bold face letters. For a vector x = (x1, · · · , xd) ∈ Rd, we use ‖x‖2 = ( ∑d i=1 |xi|2)1/2 to denote its `2 norm. For a matrix A, we use ‖A‖2 to denote its induced norm by the vector `2 norm. We denote the standard Gaussian in Rd as N (0, I) with I ∈ Rd×d being the identity matrix. The set of (positive) real numbers is denoted as (R+) R. We use B(0, R) to denote the ball centered at 0 with radius R.

heading: 2 ALGORITHMS

heading: 2.1 DEEP RESIDUAL LEARNING AND ITS CONTINUOUS ANALOGUE

text:
Given the training set SN := {xi, yi}Ni=1, with {xi, yi} ⊂ Rd × R being a data-label pair. For a given xi the forward propagation of a ResNet with M residual mappings can be written as
xl+1 = xl + F̂ (xl,Wl), for l = 0, 1, · · · ,M − 1, with x0 = xi; ŷi = f(xM ), (1)
where F̂ (·,Wl) is the nonlinear mapping of the lth residual mapping parameterized by Wl; f is the output activation function, and ŷi is the predicted label for xi. The heuristic continuum limit of (1) is
dx(t) = F (x(t),W(t))dt, x(0) = x̂, where t is the time variable. (2)
The ordinary differential equation (ODE) (2) can be revertible, and thus the ResNet counterpart might be exposed to data privacy leakage. For instance, we use the ICLR logo (Fig. 1 (a)) as the initial data x̂ in (2). Then we simulate the forward propagation of ResNet by solving (2) from t = 0 to t = 1 using the forward Euler solver with a time step size ∆t = 0.01 and a given velocity field F (x(t),W(t)) (see Appendix E for the details of F (x(t),W(t))), which maps the original image to its features (Fig. 1 (b)). To recover the original image, we start from the feature and use the backward Euler iteration, i.e., x̃(t) = x̃(t+∆t)−∆tF (x̃(t+∆t), t+∆t), to evolve x̃(t) from t = 1 to t = 0 with x̃(1) = x(1) being the features obtained in the forward propagation. We plot the recovered image from features in Fig. 1 (c), and the original image can be almost perfectly recovered.

heading: 2.2 RESIDUAL PERTURBATION AND ITS SDE ANALOGUE

text:
In this part, we propose two SDE models to reduce the reversibility of (2), and the corresponding residual perturbations analogue can protect the data privacy in DL.
Strategy I. For the first strategy, we consider the following SDE model:
dx(t) = F (x(t),W(t))dt+ γdB(t), γ > 0, (3)
where B(t) is the standard Brownian motion. We simulate the forward propagation and reverseengineering the input from the output by solving the SDE model (3) with γ = 1 using the same F (x(t),W(t)) and initial data x̂. We use the following forward (4) and backward (5) EulerMaruyama discretizations (Higham, 2001) of (3),
x(t+ ∆t) = x(t) + ∆tF (x(t),W(t)) + γN (0, √ ∆t I), (4)
x̃(t) = x̃(t+ ∆t)−∆tF (x̃(t+ ∆t),W(t+ ∆t)) + γN (0, √ ∆t I), (5)
for the forward and backward propagation, respectively. Figure 1 (d) and (e) show the results of the forward and backward propagation by SDE, respectively, and these results show that it is much harder to reverse the features obtained by SDE evolution. The SDE model informs us to inject Gaussian noise, in both training and test phases, to each residual mapping of ResNet to protect data privacy, which results in
xi+1 = xi + F̂ (xi,Wi) + γni, where ni ∼ N (0, I)1. (6)
Strategy II. For the second strategy, we consider using the multiplicative noise instead of the additive noise used in (3) 2 and (6), and the corresponding SDE can be written as
dx(t) = F (x(t),W(t))dt+ γx(t) dB(t), γ > 0, (7)
where denotes the Hadamard product. Similarly, we can use the forward and backward EulerMaruyama discretizations of (7) to propagate the image in Fig. 1 (a), and we provide these results in Appendix D.1. The corresponding residual perturbation is
xi+1 = xi + F̂ (xi,Wi) + γxi ni, where ni ∼ N (0, I), (8)
again, the noise γxi ni is injected to each residual mapping in both training and test phases. We will provide theoretical guarantees for these two residual perturbation schemes, i.e., (6) and (8), in Section 3, and numerically verify their efficacy in Section 4.

heading: 2.3 UTILITY ENHANCEMENT VIA MODEL ENSEMBLE

text: Wang et al. (2019b) showed that an ensemble of noise injected ResNets can improve models’ utility. In this paper, we will also study the model ensemble for utility enhancement. We inherit notations from (Wang et al., 2019b), e.g., we denote an ensemble of two noise injected ResNet8 as En2ResNet8.

heading: 3 MAIN THEORY

text: In this section, we will provide theoretical guarantees for the above two residual perturbations. 1Liu et al. (2019); Wang et al. (2019b) used this noise injection to improve robustness of ResNets. 2Liu et al. (2019) injected multiplicative noise to neural networks to improve their robustness.

heading: 3.1 DIFFERENTIAL PRIVACY GUARANTEE FOR STRATEGY I

text:
We consider the following function class for ResNets with residual perturbation:
F1 := {f(x) = wTxM |xi+1 = xi + φ ( Uixi ) + γni, i = 0, · · · ,M − 1, (9)
x0 = input data + πn,n and ni ∼ N (0, I),w ∈ Rd,Ui ∈ Rd×d},
where x0 ∈ Rd is the noisy input 3, Ui is the weight matrix in the ith residual mapping and w ∈ Rd is the weights of the last layer. γ, π > 0 are hyperparameters. φ = BN(ψ) with BN being the batch normalization and ψ being a L-Lipschitz and monotonically increasing activation function (e.g., ReLU). We first recap on the definition of differential privacy below. Definition 1 (( , δ)-DP). (Dwork et al., 2006)A randomized mechanism M : SN → R satisfies ( , δ)-DP if for any two datasets S, S′ ∈ SN that differ by one element, and any output subset O ⊆ R, it holds that P[M(S) ∈ O] ≤ e · P[M(S′) ∈ O] + δ,where δ ∈ (0, 1) and > 0.
We have the following DP guarantee for Strategy I, and we provide its proof in Appendix A. Theorem 1. Assume the input to ResNet lies in B(0, R) and the output of every residual mapping is normal distributed and bounded by G, in `2 norm, in expectation. Given the total number of iterations T used for training ResNet. For any > 0 and δ, λ ∈ (0, 1), the parameters Ui and w in the ResNet with residual perturbation satisfies ((λ/i+ (1− λ)) , δ)-DP and ((λ/M + (1− λ)) , δ)DP, respectively, provided that π > R √ (2Tbα)/(Nλ ) and γ > G √ (2Tbα)/(Nλ ), where α = log(1/δ)/ ((1− λ) ) + 1, M,N and b are the number of residual mappings, training data, and batch size, respectively. In particular, when γ > G √ (2Tbα)/(NMλ ) the whole model obtained by injecting noise according to strategy I satisfies ( , δ)-DP.

heading: 3.2 THEORETICAL GUARANTEES FOR STRATEGY II

text:
Privacy. To analyze the residual perturbation (8), we consider the following function class:
F2 := {f (x) = wTxM + πxMn| xi+1 = xi + φ ( Uixi ) + γx̃i ni), (10)
i = 0, · · · ,M − 1,ni ∼ N (0, I), ‖w‖2 ≤ a}
where a > 0 is a constant; we denote the entry of xi that has the largest absolute value as ximax, and x̃i is defined as (sgn(xij) max(|xij |, η))dj=1. Due to batch normalization, we assume φ can be bounded by a positive constant B. The other notations are defined similar to that in (9).
Consider training F2 by using two different datasets S and S′, and we denote the resulting models as: f (x|S) := wT1 xM + πxMnM ; xi+1 = xi + φ ( Ui1x i )
+ γx̃i ni, i = 0, · · · ,M − 1. (11) f ( x|S ′ )
:= wT2 x M + πxMnM ; xi+1 = xi + φ ( Ui2x i ) + γx̃i ni, i = 0, · · · ,M − 1. (12)
Theorem 2. For f(x|S) and f(x|S′) that are defined in (11) and (12), respectively. Let λ ∈ (0, 1), δ ∈ (0, 1), and > 0, if γ > (B/η) √ (2αM)/(λ ) and π > a √ (2αM) /λ , where α = log(1/δ)/ ((1− λ) ) + 1, then P[f(x|S) ∈ O] ≤ e · P[f(x|S′ ] ∈ O] + δ for any input x and any subset O in the output space.
We provide the proof of Theorem 2 in Appendix B. Theorem 2 guarantees the privacy of the training data given only black-box access to the model, i.e., the model will output the prediction for any input without granting adversaries access to the model itself. In particular, we cannot infer whether the model is trained on S or S′ no matter how we query the model in a black-box fashion. We leave the theoretical DP-guarantee for for Strategy II as a future work.
Generalization Gap. Many works have shown that overfitting in training ML models leads to privacy leakage (Salem et al., 2018), and reducing overfitting can mitigate data privacy leakage (Shokri et al., 2017; Yeom et al., 2018; Sablayrolles et al., 2018; Salem et al., 2018; Wu et al., 2019b). In this part, we will show that the residual perturbation (8) can reduce overfitting via computing the Rademacher complexity. For simplicity, we consider binary classification problems. Suppose SN ={xi, yi}Ni=1 is drawn from X × Y ⊂ Rd×{−1,+1} with X and Y being the input data and label
3We add noise to the input for DP guarantee
spaces, respectively. Assume D is the underlying distribution of X × Y , which is unknown. Let H ⊂ V be the hypothesis class of the ML model. We first recap on the definition of Rademacher complexity. Definition 2. (Barlett & Mendelson, 2002) Let H : X → R be the space of real-valued functions on the space X . For a given sample S = {x1,x2, · · · ,xN} of size N , the empirical Rademacher complexity ofH is defined as
RS(H) := 1
N Eσ[sup
h∈H N∑ i=1 σih(xi)],
where σ1, σ2, · · · , σN are i.i.d. Rademacher random variables with P(σi = 1) = P(σi = −1) = 12 .
Rademacher complexity is a tool to bound the generalization gap (Barlett & Mendelson, 2002). The smaller the generalization gap is, the less overfitting the model is. For ∀xi ∈ Rd and constant c ≥ 0, we consider the following two function classes:
F := {f(x,w) = wxp(T )|dx(t) = Ux(t)dt,x(0) = xi; w ∈ R1×d,U ∈ Rd×d} with ‖w‖2, ‖U‖2 ≤ c},
G := {f(x,w) = E (wxp(T )) |dx(t) = Ux(t)dt+ γx(t) dB(t),x(0) = xi; w ∈ R1×d, with U ∈ Rd×d, ‖w‖2, ‖U‖2 ≤ c},
where 0 < p < 1 takes the value such that xp is well defined on the whole Rd. γ > 0 is a hyperparameter and U is a circulant matrix that corresponding to the convolution layer in DNs. B(t) being the 1D Brownian motion. The function class F represents the continuous analogue of ResNet without inner nonlinear activation functions, and G denotes F with the residual perturbation (8). Theorem 3. Given the training set SN = {xi, yi}Ni=1. We have RSN (G) < RSN (F).
We provide the proof of Theorem 3 in Appendix C, where we will also provide quantitative lower and upper bounds of the above Rademacher complexities. Theorem 3 shows that residual perturbation (8) can reduce the generalization error. We will numerically verify this generalization error reduction for ResNet with residual perturbation in Section 4.

heading: 4 EXPERIMENTS

text: In this section, we will numerically verify that 1) can residual perturbation protect data privacy; in particular, membership privacy? 2) can the ensemble of ResNets with residual perturbation improve the classification accuracy? 3) are skip connections crucial in residual perturbation for DL with data privacy? 4) what is the advantage of the residual perturbation over the DPSGD? We focus on Strategy I in this section, and we provide the results of Strategy II in Appendix D.

heading: 4.1 PRELIMINARIES

text:
Datasets. We consider both CIFAR10/CIFAR100 (Krizhevsky et al., 2009) and the Invasive Ductal Carcinoma (IDC) datasets. Both CIFAR10 and CIFAR100 contain 60K 32× 32 color images with 50K and 10K of them used for training and test, respectively. The IDC dataset is a breast cancerrelated benchmark dataset, which contains 277,524 patches of the size 50× 50 with 198,738 labeled negative (0) and 78,786 labeled positive (1). Figure 2 depicts a few patches from the IDC dataset. For the IDC dataset, we follow Wu et al. (2019a) and split the whole dataset into training, validation, and test set. The training set consists of 10,788 positive patches and 29,164 negative patches, and the test set contains 11,595 positive patches and 31,825 negative patches. The remaining patches are used as the validation set. For each dataset, we split its training set into Dshadow and Dtarget with the same size. Furthermore, we split Dshadow into two halves with the same size and denote them as Dtrainshadow and Doutshadow, and split Dtarget by half into D train target and D out target. The purpose of this splitting of the training set is for the membership inference attack, which will be discussed below.
Membership inference attack. To verify the efficiency of residual perturbation for protecting data privacy, we consider the membership inference attack (Salem et al., 2018) in all the experiments below. The membership attack proceeds as follows: 1) train the shadow model by using Dtrainshadow; 2) apply the trained shadow model to predict all data points in Dshadow and obtain the corresponding
classification probabilities of belonging to each class. Then we take the top three classification probabilities (or two in the case of binary classification) to form the feature vector for each data point. A feature vector is tagged as 1 if the corresponding data point is in Dtrainshadow, and 0 otherwise. Then we train the attack model by leveraging all the labeled feature vectors; 3) train the target model by using Dtraintarget and obtain feature vector for each point in Dtarget. Finally, we leverage the attack model to decide whether a data point is in Dtraintarget.
Experimental settings. We consider En5ResNet8 (ensemble of 5 ResNet8 with residual perturbation) and the standard ResNet8 as the target and shadow models. We use a multilayer perceptron with a hidden layer of 64 nodes, followed by a softmax output function as the attack model, which is adapted from (Salem et al., 2018). We apply the same settings as that used in (He et al., 2016) to train the target and shadow models on the CIFAR10 and CIFAR100. For training models on the IDC dataset, we run 100 epochs of SGD with the same setting as before except that we decay the learning rate by 4 at the 20th, 40th, 60th, and 80th epoch, respectively. Moreover, we run 50 epochs of Adam (Kingma & Ba, 2014) with a learning rate of 0.1 to train the attack model. For both IDC and CIFAR datasets, we set π as half of γ in Strategy I, which simplifies hyperparameters calibration, and based on our experiment it gives a good trade-off between privacy and accuracy.
Performance evaluations. We consider both classification accuracy and capability for protecting membership privacy. The attack model is a binary classifier, which is to decide if a data point is in the training set of the target model. For any x ∈ Dtarget, we apply the attack model to predict its probability (p) of belonging to the training set of the target model. Given any fixed threshold t if p ≥ t, we classify x as a member of the training set (positive sample), and if p < t, we conclude that x is not in the training set (negative sample); so we can obtain different attack results with different thresholds. Furthermore, we can plot the ROC curve(see details in subsection 4.5) of the attack model and use the area under the ROC curve (AUC) as an evaluation of the membership inference attack. The target model protects perfect membership privacy if the AUC is 0.5 (attack model performs random guess), and the higher AUC is, the less private the target model is. Moreover, we use the precision (the fraction of records inferred as members are indeed members of the training set) and recall (the fraction of training set that is correctly inferred as members of the training set by the attack model) to measure ResNets’ capability for protecting membership privacy.

heading: 4.2 EXPERIMENTS ON THE IDC DATASET

text:
In this subsection, we numerically verify that the residual perturbation in protecting data privacy while retaining the classification accuracy on the IDC dataset. We select the En5ResNet8 as a benchmark architecture, which has ResNet8 as its baseline architecture (the details of the neural architectures are provided in Appendix F). As shown in Figure 3, we set four different thresholds to obtain different attack results with three different noise coefficients (γ) when γ = 0 means the standard ResNet8 without residual perturbation. We also depict the ROC curve for this experiment in Figure 7 (c).
En5ResNet is remarkably better in protecting the membership privacy, and as γ increases the model becomes more resistant to the membership attack. Also, as the noise coefficient increases, the gap between training and test accuracies becomes smaller, which resonates with Theorem 3. For instance, when γ = 0.2 the AUC for the attack model is 0.495 and 0.563, respectively, for En5ResNet8 and ResNet8; the classification accuracy of En5ResNet8 and ResNet8 are 0.867 and 0.847, respectively.

heading: 4.2.1 RESIDUAL PERTURBATION VS. DPSGD

text: In this part, we compare the residual perturbation with the benchmark Tensorflow DPSGD module (McMahan et al., 2018), and we calibrate the hyperparameters, including the initial learning rate (0.1) which decays by a factor of 4 after every 20 epochs, noise multiplier (1.1), clipping threshold (1.0), micro-batches (128), and epochs (100) 4 such that the resulting model gives the optimal trade-off between membership privacy and classification accuracy. DPSGD is significantly more expensive due to the requirement of computing the per-sample gradient. We compare the standard ResNet8 trained by DPSGD with En1ResNet8 and En5ResNet8 with residual perturbation (γ = 0.3). Table 1 lists the AUC of the attack model and training and test accuracies of the target model; we see that residual perturbation can improve accuracy and protect better membership privacy.

heading: 4.3 EXPERIMENTS ON THE CIFAR10/CIFAR100 DATASETS

text:
We further test the residual perturbation for ResNet8 and En5ResNet8 on the CIFAR10/CIFAR100 dataset. Figure 4 plots the performance of En5ResNet8 on the CIFAR10 dataset under the above four different measures. Again, the ensemble of ResNets with residual perturbation is remarkably less vulnerable to the membership inference attack; for instance, the AUC of the attack model for ResNet8 and En5ResNet8 (γ = 0.75) is 0.757 and 0.573, respectively. Also, the classification accuracy of En5ResNet8 (67.5%) is higher than that of ResNet8 (66.9%) for CIFAR10 classification. Figure 5 depicts the results of En5ResNet8 for CIFAR100 classification. These results confirm again that residual perturbation can protect membership privacy and improve classification accuracy.
4https://github.com/tensorflow/privacy/tree/master/tutorials

heading: 4.3.1 EFFECTS OF THE NUMBER OF MODELS IN THE ENSEMBLE

text: In this part, we consider the effects of the number of residual perturbed ResNets in the ensemble. Figure 6 illustrates the performance of EnResNet8 for CIFAR10 classification measured in the AUC, and training and test accuracy. These results show that tuning the noise coefficient and the number of models in the ensemble is crucial to optimize the trade-off between accuracy and privacy.

heading: 4.4 ON THE IMPORTANCE OF SKIP CONNECTIONS

text: Residual perturbations theoretically relies on the irreversibility of the SDEs (3) and (7), and this ansatz lies in the skip connections in the ResNet. We test both standard ResNet and the modified ResNet without skip connections. For CIFAR10 classification, under the same noise coefficient (γ = 0.75), the test accuracy is 0.675 for the En5ResNet8 (with skip connection); while the test accuracy is 0.653 for the En5ResNet8 (without skip connection). Skip connections makes EnResNet more resistant to noise injection which is indeed crucial for the success of residual perturbation for protecting data privacy.

heading: 4.5 ROC CURVES FOR EXPERIMENTS ON DIFFERENT DATASETS

text: The receiver operating characteristic (ROC) curve can be used to illustrate the classification ability of a binary classifier. ROC curve is obtained by plotting the true positive rate against the false positive rate at different thresholds. The true positive rate, also known as recall, is the fraction of the positive set (all the positive samples) that is correctly inferred as a positive sample by the binary classifier. The false positive rate can be calculated by 1-specificity, where specificity is the fraction of the negative set (all the negative samples) that is correctly inferred as a negative sample by the binary classifier. In our case, the attack model is a binary classifier. Data points in the training set of the target model are tagged as positive samples, and data points out of the training set of the target model are tagged as negative samples. Then we plot ROC curves for different datasets (as shown in Figure 7). These ROC curves show that if γ is sufficiently large, the attack model’s prediction will be nearly a random guess.

heading: 4.6 REMARK ON THE PRIVACY BUDGET

text:
In the experiments above, we set the constantsG andR to 30 for Strategy I. For classifying IDC with ResNet8, the DP budget for Strategy I is ( = 1.1e5, δ = 1e− 5) and the DP-budget for DPSGD is ( = 15.79, δ = 1e − 5). For classifying CIFAR10 with ResNet8, the DP budget for Strategy I is ( = 3e5, δ = 1e − 5) and the DP-budget for DPSGD is ( = 22.33, δ = 1e − 5). Note that theorem 1 offers a quite loose DP budget compared to DPSGD. There are several difficulties we need to overcome to get tight DP bounds for Strategy I. Compared to DPSGD, it is significantly harder. In particular, 1) the loss function of the nose injected ResNets is highly nonlinear and very complex with respect to the weights, also the noise term appears in the loss function due to the noise injected in each residual mapping. These together make the tight estimate very difficult. 2) In our proof, we leveraged the framework of subsampled Rényi-DP (Wang et al., 2018) to find a feasible range of
noise variance parameter, and then convert to DP to get the value of γ for a given DP budget. This procedure will significantly reduce the accuracy of the estimated γ. We leave the tight DP guarantee as future work. In particular, how to reduce the accuracy of estimating due to the conversion between Rényi-DP and DP.

heading: 5 CONCLUDING REMARKS

text: In this paper, we proposed residual perturbations, whose theoretical foundation lies in the theory of stochastic differential equations, to protect data privacy for deep learning. Theoretically, we prove that the residual perturbation can reduce the generalization gap with differential privacy guarantees. Numerically, we have shown that residual perturbations are effective for protecting membership privacy on some benchmark datasets. In particular, on the IDC benchmark, residual perturbations protect better membership privacy than state-of-the-art differentially private stochastic gradient descent and achieve remarkably better classification accuracy.

heading: A Proof of Theorem 1 13

text: A.1 Rényi Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 A.2 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

heading: B Proof of Theorem 2 15

heading: C Proof of Theorem 3 15

text: C.1 Some Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 C.2 The proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

heading: D Experiments on Strategy II 18

text: D.1 Forward and Backward Propagation Using (7) . . . . . . . . . . . . . . . . . . 18 D.2 Experiments on the IDC Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . 18 D.3 Experiments on the CIFAR10/CIFAR100 Datasets . . . . . . . . . . . . . . . . 18 D.4 ROC Curves for the Experiments on Different Datasets . . . . . . . . . . . . . . 19

heading: E More Experimental Details 19

heading: F Architectures of the Used DNs 20

heading: A PROOF OF THEOREM 1

text:
A.1 RÉNYI DIFFERENTIAL PRIVACY
We will use the notion of Rényi differential privacy (RDP) to prove the differential privacy (DP) guarantees for the proposed residual perturbations. First, let’s review the definition and several results of the Rényi differential privacy (Mironov, 2017). Definition 3. (Mironov, 2017) (Rényi divergence) For any two probability distributions P and Q defined over the distribution D, the Rényi divergence of order α > 1 is
Dα(P ||Q) = 1
α− 1 logEx∼Q(P/Q)α.
Definition 4. (Mironov, 2017) ((α, )-RDP) A randomized mechanismM : D → R is said to have -Rényi differential privacy of order α or (α, )-RDP for short, if for any adjacent S,S ′ ∈ D that differ by only one entry, it holds that
Dα(M(S)||M(S ′ ) ≤ ε.
Lemma 1. (Mironov, 2017) Let f : D → R1 be (α, 1)-RDP and g : R1 ×D → R be (α, )-RDP, then the mechanism defined as (X,Y ), where X ∼ f(D) and Y ∼ g(X,D), satisfies (α, 1 + 2)- RDP. Lemma 2. (Mironov, 2017) (From RDP to ( , δ)-DP) If f is an (α, )-RDP mechanism, then it also satisfies ( − (log δ)/(α− 1), δ)-differential privacy for any 0 < δ < 1.
Lemma 3. (Mironov, 2017) (Post-processing lemma) LetM : D → R be a randomized algorithm that is (α, )-RDP, and let f : R → R′ be an arbitrary randomized mapping. Then f(M(·)) : D → R′ is (α, )-RDP
A.2 PROOF OF THEOREM 1
In this subsection, we will give a proof of Theorem 1, i.e., DP-guarantee for the Strategy I.
Proof. We will prove Theorem 1 by mathematical induction. Consider two adjacent datasets S = {x1, · · · ,xN−1,xN},S ′ = {x1, · · · ,xN−1, x̂N} that differ by one entry. For the first residual mapping, it is easy to check that when γ ≥ R √ 2α/ p we have Dα(x1N ||x̂1N ) = α‖xN − x̂N‖2/(2γ2) < εp. For the remaining residual mappings, we denote the response of the ith residual mapping, for any two input data xN and x̂N , as xiN , x̂ i N , respectively. Based on our assumpution, we have
xiN + φ(U ixiN ) ∼ N (µN,i, σ2N,i)
x̂iN + φ(U ix̂iN ) ∼ N (µ̂N,i, σ2N,i),
where µN,i and µ̂N,i are both bounded by the constant G. If Dα(xiN ||x̂iN ) ≤ p/i, according the post-processing lemma (Lemma 3), we have
Dα(x i N + φ(U ixiN )||x̂iN + φ(Uix̂iN )) = α‖µN,i − µ
′ N,i‖2
2σ2N,i ≤ p/i,
so when γ > √ 2αG2/ p, we further have
Dα(x i N + φ(U ixiN ) + γn||x̂iN + φ(Uix̂iN ) + γn) = α‖µN,i − µ
′ N,i‖2
2(σ2N,i + γ 2)
≤ p i+ 1 ,
which implies that Dα(xi+1N ||x̂ i+1 N ) < p i+1 . On the other hand, note that ∇Ui+1`|xi+1N = l ′ ( xi+1N + φ ( Ui+1xi+1N )) φ ′ (Ui+1xi+1N )(x i+1 N ) T
∇Ui+1`|x̂i+1N = l ′ ( x̂i+1N + φ ( Ui+1x̂i+1N )) φ ′ (Ui+1x̂i+1N )(x̂ i+1 N ) T .
Leveraging the post-processing lemma (Lemma 3) again, we get
Dα(∇Ui+1`|xi+1N ||∇Ui+1`|x̂i+1N ) < p i+ 1 .
Let Bt be the index set with |Bt| = b, and we update Ui as following:
Ui+1t+1|S = Uit − α 1
b ∑ j∈Bt ∇Ui+1t `(x i+1 j ,U i+1 t )
Ui+1t+1|S ′ = Uit − α 1
b ∑ j∈Bt ∇Ui+1t `(x i+1 j ,U i+1 t ),
where Ui+1t is the weights updated after the tth training iterations. When N /∈ Bt, it’s obviously that Dα(Ui+1t+1|S||U i+1 t+1|S ′) = 0; when N ∈ Bt, the equations which we use to update Ui can be rewritten as
Ui+1t+1|S = Uit − α(1/b) ∑
j∈Bt−{N}
∇Ui+1t `(x i+1 j ,U i+1 t )− α(1/b)∇Ui+1t `(x i+1 N ,U i+1 t )
Ui+1t+1|S ′ = Uit − α(1/b) ∑
j∈Bt−{N}
∇Ui+1t `(x i+1 j ,U i+1 t )− α(1/b)∇Ui+1t `(x̂ i+1 N ,U i+1 t ).
According to the post-processing lemma (Lemma 3), we have Dα(Ui+1t+1|S||U i+1 t+1|S ′) ≤ p/(i+ 1). Because there are only (Tb)/N steps where we use the information of xN and x̂N . Replace p by (Tb p)/N and use composition theorem we can get after T steps the output Ui+1T satisfies (α, p/(i + 1))-RDP and w satisfies (α, p/M)-RDP. By Lemma 2, we can easily establish the DP-guarantee for Strategy I, as stated in Theorem 1.

heading: B PROOF OF THEOREM 2

text:
In this section, we will provide a proof for Theorem 2.
Proof. Let φ = BN(ψ), where BN is batch normalization operation and ψ is an activation function. Because of the property of batch normalization, we assume that φ can be bounded by a positive constant B. To show that the model (9) guarantees training data privacy given only black-box access to the model. Consider training the model (9) with two different datasets S and S′, and we denote the resulting model as f(·|S) and f(·|S′), respectively. In the following, we prove that with appropriate choices of γ and π, Dα(f(x|S)||f(x|S ′ )) < p for any input x.
First, we consider the convolution layers, and let Conv(x)i be the ith entry of the vectorized Conv(x). Then we have Conv(x)i = xi+φ(Ux)i+γx̃ini. For any two different training datasets, we denote
Conv(x)i|S = xi + φ(U1x)i + γx̃ini ∼ N (xi + φ(U1x)i, γ2x̃2i ),
and Conv(x)i|S ′ = xi + φ(U2x)i + γx̃ini ∼ N (xi + φ(U2x)i, γ2x̃2i ).
Therefore, if γ > (B/η) √ (2αM)/( p), we have
Dα ( N ( xi + φ (U1x)i , γ 2x̃2i ) ||N ( xi + φ (U2x)i , γ 2x̃2i ))
≤ α(φ(U1x)i − φ(U2x)i) 2 2γ2η2 ≤ 4αL 2B2‖x‖22 2γ2x̃2i ≤ 2αB 2
γ2η2 ≤ p/M.
Furthermore, γ > (b/η) √
(2αM)/( p) guarantees (α, p/M)-RDP for every convolution layer. For the last fully connected layer, if π > a √ (2αM) / p, we have
Dα ( N ( wT1 x, π 2x̃2i ) ||N ( wT2 x, π 2x̃2i ))
= α ( wT1 x−wT2 x )2 2π2‖x‖2 ≤ 4αa 2‖x‖22 2π2‖x‖2
≤ 2αa 2
π2 ≤ p/M,
i.e., π > a √
(2αM) / p guarantees that the fully connected layer to be (α, p/M)-RDP. According to Lemma 1, we have (α, p)-RDP guarantee for the ResNet of M residual mappings if γ > (Lb/η) √ (2αdM)/( p) and π > a √ (2αM) / p. Let λ ∈ (0, 1), for any given ( p, δ) pair, if
p ≤ λ and −(log δ)/(α − 1), δ) ≤ (1 − λ) , then we have get the ( , δ)-DP guarantee for the ResNet with M residual mapping using the residual perturbation Strategy II.

heading: C PROOF OF THEOREM 3

text:
In this section, we will proof that the residual perturbation (8) can reduce the generalization error via computing the Rademacher complexity. Let us first recap on some related lemmas on the stochastic differential equation and the Rademacher complexity.
C.1 SOME LEMMAS
Let ` : V × Y → [0, B] be the loss function. Here we assume ` is bounded and B is a positive constant. In addition, we denote the function class `H = {(x, y) → `(h(x), y) : h ∈ H, (x, y) ∈ X × Y }. The goal of the learning problem is to find h ∈ H such that the population risk R(h) = E(x,y)∈D[`(h(x), y)] is minimized. The gap between population risk and empirical risk RSN (h) = (1/N) ∑N i=1 `(h(xi), yi) is known as the generalization error. We have the following lemma and theorem to connect the population and empirical risks via Rademacher complexity.
Lemma 4. (Ledoux-Talagrand inequality) (M & Talagrand, 2002)LetH be a bounded real valued function space and let φ : R→ R be a Lipschitz with constant L and φ(0) = 0. Then we have
1 n Eσ [ sup h∈H n∑ i=1 σiφ (h (xi)) ] ≤ L n Eσ [ sup h∈H n∑ i=1 σih (xi) ] .
Lemma 5. (Barlett & Mendelson, 2002)Let SN = {(x1, y1) , · · · , (xN , yN )} be samples chosen i.i.d. according to the distribution D. If the loss function ` is bounded by B > 0. Then for any δ ∈ (0, 1), with probability at least 1− δ, the following holds for all h ∈ H,
R (h) ≤ RSN (h) + 2BRSN (`H) + 3B √ (log(2/δ)/(2N).
In addition, according to the Ledoux-Talagrand inequality and assume loss function is L-lipschitz, we have
RSN (`H) ≤ LRSN (H) .
So the population risk can be bounded by the empirical risk and Rademacher complexity of the function class H. Because we can’t minimize the population risk directly, we can minimize it indirectly by minimizing the empirical risk and Rademacher complexity of the function class H. Next, we will further discuss Rademacher complexity of the function class H. We first introduce several lemmas below.
Lemma 6. (Klebaner, 2005) For any given matrix U, the solution to the equation{ dx(t) = Ux(t)dt
x(0) = x̂
has the following expression x(t) = exp(Ut)x̂,
Also, we can write the solution to the following equation{ dy(t) = Uy(t)dt+ γy(t)dB(t)
y(0) = x̂
as
y(t) = exp(Ut− 1 2 γ2tI + γB(t)I)x̂.
Obviously, we have E[y(t)] = x(t). Lemma 7. A matrix C ∈ Rd×d is circulant, if there exists real number a1, · · · , ad such that
C =  a1 a2 . . . ad ad a1 . . . . . . . . . . . . . . . a2
a2 . . . ad a1
 .
For any circulant matrix, we have the following eigen-decomposition
ΨHCΨ = diag(λ1, . . . , λd),
where
√ dΨ =  1 1 . . . 1 1 m1 . . . md−1 . . . . . . . . . . . .
1 md−11 . . . m d−1 d−1  , and mis are the roots of unity and λi = a1 + a2mi + · · ·+ admd−1i .
C.2 THE PROOF OF THEOREM 3
Proof. By the definition of Rademacher complexity (Def. 2), we have
RSN (F) = (1/N)Eσ [ sup f∈F N∑ i=1 σiwx p i (T ) ] = (c/N)Eσ [ sup ‖U‖2≤c ‖ N∑ i=1 σix p i (T ) ‖2 ] .
Let ui = Ψx p i and denote the jth element of ui as ui,j . Then by lemma 7, we have
RSN (F) = (c/N)Eσ sup ‖U‖2≤c ∑ i,j σiσj〈xpi (T ),x p j (T )〉 1/2
= (c/N)Eσ sup |λi|≤c (‖ΨH N∑ i=1 σi ( ui,1 exp(λ1Tp), · · · , ui,d exp(λdTp))T ‖2 ) = (c/N)Eσ sup
|λi|≤c { d∑ j=1 [ N∑ i=1 σiui,j exp (λjTp) ]2 }1/2 = (c/N) exp(cTp)Eσ{ d∑ j=1 [ N∑ i=1 σiui,j ]2 }1/2
= (c/N) exp (cTp)Eσ‖ N∑ i=1 σiui‖2 = (c/N) exp (cTp)Eσ‖Ψ N∑ i=1 σix p i ‖2
= (c/N) exp (cTp)Eσ‖ N∑ i=1 σix p i ‖2
Note that E (wxpi (T )) = wE (x p i (T )) and according to Lemma 6, similar to proof for the function class F we have
RSN (G) = (c/N)Eσ sup ‖U‖2≤c ∑ i,j σiσj〈Expi (T ),Ex p j (T )〉 1/2
= (c/N)Eσ sup |λi|≤c (‖ΨH N∑ i=1 σi(ui,1 exp(λ1Tp− p(1− p)γ2T/2),
· · · , ui,d exp(λdTp− p(1− p)γ2T/2))T ‖2)
= (c/N)Eσ sup |λi|≤c { d∑ j=1 [ N∑ i=1 σiui,j exp ( λjTp− p(1− p)γ2T/2 )]2 }1/2 = (c/N) exp(cTp− p(1− p)γ2T/2)Eσ{ d∑ j=1 [ N∑ i=1 σiui,j ]2 }1/2 = (c/N) exp ( cTp− p(1− p)γ2T/2 ) Eσ‖
N∑ i=1 σiui‖2
= (c/N) exp ( cTp− p(1− p)γ2T/2 ) Eσ‖Ψ N∑ i=1 σix p i ‖2 = (c/N) exp ( cTp− p(1− p)γ2T/2 ) Eσ‖
N∑ i=1 σix p i ‖2 < RSN (F)
Therefore, we have completed the proof for the fact that the ensemble of Gaussian noise injected ResNets can reduce generalization error compared to the standard ResNet.

heading: D EXPERIMENTS ON STRATEGY II

text:
D.1 FORWARD AND BACKWARD PROPAGATION USING (7)
Figure 8 plots the forward and backward propagation of the ICLR logo using the SDE model (7). Again, we cannot simply use the backward Euler-Maruyama discretization to reverse the features generated by the propagating through the forward Euler-Maruyama discretization.
D.2 EXPERIMENTS ON THE IDC DATASET
In this subsection, we consider the performance of the second residual perturbation in protecting membership privacy while retaining the classification accuracy on the IDC dataset. We use the same ResNet models as that used for the first residual perturbation. We list the results in Fig. 9, these results confirm that the residual perturbation (8) can effectively protect data privacy and maintain or even improve the classification accuracy. In addition, we depict the ROC curve for this experiment in Figure 12 (c). We note that, as the noise coefficient increases, the gap between training and testing accuracies narrows, which is consistent with Theorem 3.
D.2.1 RESIDUAL PERTURBATION VS. DIFFERENTIALLY PRIVATE STOCHASTIC GRADIENT DESCENT
We have shown that the first residual perturbation (6) outperforms the DPSGD in protecting membership privacy and improving classification accuracy. In this part, we further show that the second residual perturbation (8) also outperforms the benchmark DPSGD with the above settings. Table 2 lists the AUC of the attack model and training & test accuracy of the target model; we see that the second residual perturbation can also improve the classification accuracy and protecting better membership privacy.
D.3 EXPERIMENTS ON THE CIFAR10/CIFAR100 DATASETS
In this subsection, we will test the second residual perturbation (8) on the CIFAR10/CIFAR100 datasets with the same model using the same settings as before. Figure 10 plots the performance of En5ResNet8 on the CIFAR10 dataset. These results show that the ensemble of ResNets with residual
perturbation (8) is significantly more robust to the membership inference attack. For instance, the AUC of the attack model for ResNet8 and En5ResNet8 (γ = 2.0) is 0.757 and 0.526, respectively. Also, the classification accuracy of En5ResNet8 (γ = 2.0) is higher than that of ResNet8, and their accuracy is 71.2% and 66.9% for CIFAR10 classification. Figure 11 shows the results of En5ResNet8 for CIFAR100 classification. These results confirm that residual perturbation (8) can protect membership privacy and improve classification accuracy once more.
D.4 ROC CURVES FOR THE EXPERIMENTS ON DIFFERENT DATASETS
Figure 12 plots the ROC curves for the experiments on the different datasets with different models using the second residual perturbation strategy. These ROC curves again show that if γ is sufficiently large, the attack model’s prediction will be nearly a random guess.

heading: E MORE EXPERIMENTAL DETAILS

text:
We give the detailed construction of the velocity field F (x(t),W(t)) in (3) and (7) that used to generate Figs. 1 and 8 in Algorithm 1.
Algorithm 1 The expression of F (x(t),W(t)) Input: image=x(t); rows, cols, channels = image.shape. Output: F (x(t),W(t))=dirtyimage. for k in range(channels) do
for i in range(rows): do for j in range(cols): do
offset(j) =int([j + 50.0cos(2πi/180)]%cols); offset(i) =int([i+ 50.0sin(2πi/180)]%row); dirtyimage[i, j, k] = image[(i+ offset(j))%rows, (j + offset(i))%cols, k];
return dirtyimage

heading: F ARCHITECTURES OF THE USED DNS

text: Figure 13 shows the architectures of ResNets used in this paper, and we plot basic blocks in Fig. 14.


summaries: The paper proposed the Length-Adaptive Transformer. The model can be trained once and directly applied to different inference scenarios. To achieve this goal, the author proposed the LengthDrop method, which randomly samples the length at each layer. In addition, the author used the sandwich rule to train the model. At each step, the sandwich rule will train the largest model, the smallest model, and another bunch of randomly sampled models. In the inference phase, the paper proposed to search for the best length configuration that balances the accuracy and latency tradeoff via evolutionary search. Moreover, to generalize the model to token annotation tasks, the author proposed the Drop-and-Restore process, in which the tokens that have been dropped are used again in the final layer. Experiments show that Length-Adaptive Transformer is able to outperfom the baseline models when evaluated at the same latency level.

summaries: This work introduces a method, called LengthDrop, to train a Length-Adaptive Transformer that supports adaptive model architecture based on different latency constraints. In order to make the model robust to variable input lengths, the method stochastically reduces the length of a sequence at each layer during training. Once the model is trained, the method uses an evolutionary search to find subnetworks that maximize model accuracy under a latency budget.

summaries: The work targets an interesting direction of improving the efficiency of Transformers by reducing the sequence length. The main contributions of the work are (1) proposing LengthDrop as the way to achieve length reduction; (2) utilizing techniques developed in NAS, namely one-shot NAS, to enable proper training and allow adaptive drop ratio search after training. All these ideas are very reasonable and interesting. Empirically, the authors show that the proposed method is able to match or even outperform BERT-base model with 1/3 - 1/2 FLOPs during inference (not training).

abstractText: Although transformers have achieved impressive accuracies in various tasks in natural language processing, they often come with a prohibitive computational cost, that prevents their use in scenarios with limited computational resources for inference. This need for computational efficiency in inference has been addressed by for instance PoWER-BERT (Goyal et al., 2020) which gradually decreases the length of a sequence as it is passed through layers. These approaches however often assume that the target computational complexity is known in advance at the time of training. This implies that a separate model must be trained for each inference scenario with its distinct computational budget. In this paper, we extend PoWER-BERT to address this issue of inefficiency and redundancy. The proposed extension enables us to train a large-scale transformer, called Length-Adaptive Transformer, once and uses it for various inference scenarios without re-training it. To do so, we train a transformer with LengthDrop, a structural variant of dropout, which stochastically determines the length of a sequence at each layer. We then use a multi-objective evolutionary search to find a length configuration that maximizes the accuracy and minimizes the computational complexity under any given computational budget. Additionally, we significantly extend the applicability of PoWER-BERT beyond sequence-level classification into token-level classification such as span-based question-answering, by introducing the idea of Drop-and-Restore. With Drop-and-Restore, word-vectors are dropped temporarily in intermediate layers and restored at the last layer if necessary. We empirically verify the utility of the proposed approach by demonstrating the superior accuracyefficiency trade-off under various setups, including SQuAD 1.1, MNLI-m, and SST-2. Upon publication, the code to reproduce our work will be open-sourced.

authors:
Tom B Brown
Benjamin Mann
Nick Ryder
Melanie Subbiah
Jared Kaplan
Prafulla Dhariwal
Arvind Neelakantan
Pranav Shyam
Girish Sastry
Amanda Askell

title: Language models are few-shot learners

authors:
Han Cai
Chuang Gan
Song Han

title: Once for all: Train one network and specialize it for efficient deployment

authors:
Ting-Wu Chin
Ruizhou Ding
Cha Zhang
Diana Marculescu

title: Towards efficient model compression via learned global ranking

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Zihang Dai
Guokun Lai
Yiming Yang
Quoc V Le

title: Funnel-transformer: Filtering out sequential redundancy for efficient language processing

venue: arXiv preprint arXiv:2006.03236,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Maha Elbayad
Jiatao Gu
Edouard Grave
Michael Auli

title: Depth-adaptive transformer

venue: arXiv preprint arXiv:1910.10073,

authors:
Angela Fan
Edouard Grave
Armand Joulin

title: Reducing transformer depth on demand with structured dropout

venue: arXiv preprint arXiv:1909.11556,

authors:
Saurabh Goyal
Anamitra Roy Choudhary
Venkatesan Chakaravarthy
Saurabh ManishRaje
Yogish Sabharwal
Ashish Verma

title: Power-bert: Accelerating bert inference for classification

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149,

authors:
Peter Henderson
Jieru Hu
Joshua Romoff
Emma Brunskill
Dan Jurafsky
Joelle Pineau

title: Towards the systematic reporting of the energy and carbon footprints of machine learning

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Lu Hou
Lifeng Shang
Xin Jiang
Qun Liu

title: Dynabert: Dynamic bert with adaptive width and depth

venue: arXiv preprint arXiv:2004.04037,

authors:
Gao Huang
Yu Sun
Zhuang Liu
Daniel Sedra
Kilian Q Weinberger

title: Deep networks with stochastic depth

venue: In European conference on computer vision,

authors:
Gao Huang
Danlu Chen
Tianhong Li
Felix Wu
Laurens van der Maaten
Kilian Q Weinberger

title: Multi-scale dense networks for resource efficient image classification

venue: arXiv preprint arXiv:1703.09844,

authors:
Jared Kaplan
Sam McCandlish
Tom Henighan
Tom B Brown
Benjamin Chess
Rewon Child
Scott Gray
Alec Radford
Jeffrey Wu
Dario Amodei

title: Scaling laws for neural language models

authors:
Zhuohan Li
Eric Wallace
Sheng Shen
Kevin Lin
Kurt Keutzer
Dan Klein
Joseph E Gonzalez

title: Train large, then compress: Rethinking model size for efficient training and inference of transformers

venue: arXiv preprint arXiv:2002.11794,

authors:
Weijie Liu
Peng Zhou
Zhe Zhao
Zhiruo Wang
Haotang Deng
Qi Ju

title: Fastbert: a self-distilling bert with adaptive inference time

venue: arXiv preprint arXiv:2004.02178,

authors:
Paul Michel
Omer Levy
Graham Neubig

title: Are sixteen heads really better than one

venue: In Advances in Neural Information Processing Systems,

authors:
Matthew E Peters
Mark Neumann
Mohit Iyyer
Matt Gardner
Christopher Clark
Kenton Lee
Luke Zettlemoyer

title: Deep contextualized word representations

venue: arXiv preprint arXiv:1802.05365,

authors:
Alec Radford
Jeffrey Wu
Rewon Child
David Luan
Dario Amodei
Ilya Sutskever

title: Language models are unsupervised multitask learners

venue: OpenAI Blog,

authors:
Colin Raffel
Noam Shazeer
Adam Roberts
Katherine Lee
Sharan Narang
Michael Matena
Yanqi Zhou
Wei Li
Peter J Liu

title: Exploring the limits of transfer learning with a unified text-to-text transformer

venue: arXiv preprint arXiv:1910.10683,

authors:
Pranav Rajpurkar
Jian Zhang
Konstantin Lopyrev
Percy Liang

title: Squad: 100,000+ questions for machine comprehension of text

venue: arXiv preprint arXiv:1606.05250,

authors:
Esteban Real
Alok Aggarwal
Yanping Huang
Quoc V Le

title: Regularized evolution for image classifier architecture search

venue: In Proceedings of the aaai conference on artificial intelligence,

authors:
Oren Rippel
Michael Gelbart
Ryan Adams

title: Learning ordered representations with nested dropout

authors:
Victor Sanh
Lysandre Debut
Julien Chaumond
Thomas Wolf

title: Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter

authors:
Roy Schwartz
Gabi Stanovsky
Swabha Swayamdipta
Jesse Dodge
Noah A Smith

title: The right tool for the job: Matching model and instance complexities

venue: arXiv preprint arXiv:2004.07453,

authors:
Abigail See
Minh-Thang Luong
Christopher D Manning

title: Compression of neural machine translation models via pruning

venue: arXiv preprint arXiv:1606.09274,

authors:
Mohammad Shoeybi
Mostofa Patwary
Raul Puri
Patrick LeGresley
Jared Casper
Bryan Catanzaro

title: Megatron-lm: Training multi-billion parameter language models using gpu model parallelism

authors:
Nitish Srivastava
Geoffrey Hinton
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning

authors:
Emma Strubell
Ananya Ganesh
Andrew McCallum

title: Energy and policy considerations for deep learning in nlp

venue: arXiv preprint arXiv:1906.02243,

authors:
Sandeep Subramanian
Ronan Collobert
Marc’Aurelio Ranzato
Y-Lan Boureau

title: Multi-scale transformer language models

venue: arXiv preprint arXiv:2005.00581,

authors:
Siqi Sun
Yu Cheng
Zhe Gan
Jingjing Liu

title: Patient knowledge distillation for bert model compression

venue: arXiv preprint arXiv:1908.09355,

authors:
Raphael Tang
Ashutosh Adhikari
Jimmy Lin

title: Flops as a direct optimization objective for learning sparse neural networks

venue: arXiv preprint arXiv:1811.03060,

authors:
Surat Teerapittayanon
Bradley McDanel
Hsiang-Tsung Kung

title: Branchynet: Fast inference via early exiting from deep neural networks

venue: In 2016 23rd International Conference on Pattern Recognition (ICPR),

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In Advances in neural information processing systems,

authors:
Alex Wang
Amanpreet Singh
Julian Michael
Felix Hill
Omer Levy
Samuel R Bowman

title: Glue: A multi-task benchmark and analysis platform for natural language understanding

venue: arXiv preprint arXiv:1804.07461,

authors:
Hanrui Wang
Zhanghao Wu
Zhijian Liu
Han Cai
Ligeng Zhu
Chuang Gan
Song Han

title: Hat: Hardware-aware transformers for efficient natural language processing

venue: arXiv preprint arXiv:2005.14187,

authors:
Thomas Wolf
Lysandre Debut
Victor Sanh
Julien Chaumond
Clement Delangue
Anthony Moi
Pierric Cistac
Tim Rault
Rémi Louf
Morgan Funtowicz

title: Transformers: State-of-the-art natural language processing

authors:
Ji Xin
Raphael Tang
Jaejun Lee
Yaoliang Yu
Jimmy Lin

title: Deebert: Dynamic early exiting for accelerating bert inference

venue: arXiv preprint arXiv:2004.12993,

authors:
Zhilin Yang
Zihang Dai
Yiming Yang
Jaime Carbonell
Russ R Salakhutdinov
Quoc V Le

title: Xlnet: Generalized autoregressive pretraining for language understanding

authors:
Jiahui Yu
Thomas S Huang

title: Universally slimmable networks and improved training techniques

venue: In Proceedings of the IEEE International Conference on Computer Vision,

heading: 1 INTRODUCTION

text:
Pretrained language models (Peters et al., 2018; Devlin et al., 2018; Radford et al., 2019; Yang et al., 2019) have achieved notable improvements in various natural language processing (NLP) tasks. Most of them rely on transformers (Vaswani et al., 2017), and the number of model parameters ranges from hundreds of millions to billions (Shoeybi et al., 2019; Raffel et al., 2019; Kaplan et al., 2020; Brown et al., 2020). Despite this high accuracy, excessive computational overhead during inference, both in terms of time and memory, has hindered its use in real applications. This level of excessive computation has further raised the concern over energy consumption as well (Schwartz et al., 2019; Strubell et al., 2019).
Recent studies have attempted at addressing these concerns regarding large-scale transformers’ computational and energy efficiency (see §6 for a more extensive discussion.) Among these, we focus on PoWER-BERT (Goyal et al., 2020) which progressively reduces sequence length by eliminating word-vectors based on the attention values as passing layers. PoWER-BERT establishes the superiority of accuracy-time trade-off over earlier approaches (Sanh et al., 2019; Sun et al., 2019; Michel et al., 2019). It however requires us to train a separate model for each efficiency constraint. In this paper, we thus develop a framework based on PoWER-BERT such that we can train a single model that can be adapted in the inference time to meet any given efficiency target.
In order to train a transformer to cope with a diverse set of computational budgets in the inference time, we propose to train one while reducing the sequence length with a random proportion at each
layer. We refer to this procedure as LengthDrop which was motivated by the nested dropout (Rippel et al., 2014). We can extract sub-models of shared weights with any length configuration without requiring extra post-processing nor additional finetuning.
Once a transformer is trained with the proposed LengthDrop, we search for the length configuration that maximizes the accuracy given a computational budget. Because this search is combinatorial and has multiple objectives (accuracy and efficiency), we use an evolutionary search algorithm, which further allows us to obtain a full Pareto frontier of accuracy-efficiency trade-off of each model.
It is not trivial to find an optimal length configuration given the inference-time computational budget, although it is extremely important in order to deploy these large-scale transformers in practice. In this work, we propose to use evolutionary search to find a length configuration that maximizes the accuracy within a given computational budget. We can further compute the Pareto frontier of accuracy-efficiency trade-off to obtain a sequence of length configurations with varying efficiency profiles.
PoWER-BERT, which forms the foundation of the proposed two-stage procedure, is only applicable to sequence-level classification, because by design it eliminates some of the word vectors at each layer. In other words, it cannot be used for token-level tasks such as span-based question answering (Rajpurkar et al., 2016), because these tasks require hidden representations of the entire input sequence at the final layer. We thus propose to extend PoWER-BERT with a novel Drop-and-Restore process (§3.3), which eliminates this inherent limitation. Word vectors are dropped and set aside, rather than eliminated, in intermediate layers to maintain the saving of computational cost, as was with the original PoWER-BERT. These set-aside vectors are then restored at the final hidden layer and provided as an input to a subsequent task-specific layer, which is unlike the original PoWER-BERT.
The main contributions of this work are two-fold. First, we introduce LengthDrop, a structured variant of dropout for training a single Length-Adaptive Transformer model that allows us to automatically derive multiple sub-models with different length configurations in the inference time using evolutionary search, without requiring any re-training. Second, we design Drop-and-Restore process that makes PoWER-BERT applicable beyond classification, which enables PoWER-BERT to be applicable to a wider range of NLP tasks such as span-based question answering. We empirically verify Length-Adaptive Transformer works quite well using the variants of BERT on a diverse set of NLP tasks, including SQuAD 1.1 (Rajpurkar et al., 2016) and two sequence-level classification tasks in GLUE benchmark (Wang et al., 2018). Our experiments reveal that the proposed approach grants us a fine-grained control of computational efficiency and a superior accuracy-efficiency trade-off in the inference time, compared to existing approaches.

heading: 2 BACKGROUND: TRANSFORMERS AND POWER-BERT

text: Before we describe our main approach, we review some of the building blocks in this section. In particular, we review transformers, which are a standard backbone used in natural language processing these days, and PoWER-BERT, which was recently proposed as an effective way to train a large-scale, but highly efficient transformer for sequence-level classification.

heading: 2.1 TRANSFORMERS AND BERT

text:
A transformer is a particular neural network that has been designed to work with a variable-length sequence input and is implemented as a stack of self-attention and fully-connected layers (Vaswani et al., 2017). Here, we give a brief overview of the transformer which is the basic building block of the proposed approach.
Each token xt in a sequence of tokens x = (x1, . . . , xN ), representing input text, is first turned into a continuous vector h0t ∈ RH which is the sum of the token and position embedding vectors. This sequence is fed into the first transformer layer which returns another sequence of the same length h1 ∈ RN×H . We repeat this procedure L times, for a transformer with L layers, to obtain hL = (hL1 , . . . , h L N ). We refer to each vector in the hidden sequence at each layer as a word vector to emphasize that there exists a correspondence between each such vector and one of the input words.
Although the transformer was first introduced for the problem of machine translation, Devlin et al. (2018) demonstrated that the transformer can be trained and used as a masked language model.
More specifically, Devlin et al. (2018) showed that the transformer-based masked language model, called BERT, learns a universally useful parameter set that can be finetuned for any downstream task including sequence-level and token-level classification.
In the case of sequence-level classification, a softmax classifier is attached to the word vector hL1 associated with the special token [CLS], and the entire network, including the softmax classifier and BERT, is finetuned. For token-level classification, we use each hLt as the final hidden reprsentation of the associated t-th word in the input sequence. This strategy of pretraining followed by finetuning, often referred to as transfer learning, has recently become a dominant approach to classification in natural language processing.

heading: 2.2 POWER-BERT

text:
PoWER-BERT keeps only the topmost lj word vectors at each layer j by eliminating redundant ones based on the significance score, which is the total amount of attention imposed by a word on the other words (Goyal et al., 2020). lj is the hyper-parameter determines how many vectors to keep at layer j. PoWER-BERT has the same model parameters with BERT, but the extraction layers are interspersed after the self-attention layer in every transformer blocks (Vaswani et al., 2017).
PoWER-BERT reduces inference time successfully, achieving better accuracy-time trade-off than DistilBERT (Sanh et al., 2019), BERT-PKD (Sun et al., 2019), and Head-Prune (Michel et al., 2019). Despite the original intention of maximizing the inference efficiency with the minimal loss in accuracy, it is possible to set up PoWER-BERT to be both more efficient and more accurate compared to the original BERT, which was observed but largely overlooked by Goyal et al. (2020).
Training a PoWER-BERT model consists of three steps: (1) finetuning, (2) length configuration search, and (3) re-training. The finetuning step is just like the standard finetuning step of BERT given a target task. A length configuration is a sequence of retention parameters (l1, · · · lL), each of which corresponds to the number of word vectors that are kept at each layer. These retention parameters are learned along with all the other parameters to minimize the original task loss together with an extra term that approximately measures the number of retained word vectors across layers. In the re-training step, PoWER-BERT is finetuned with the length configuration fixed to its learned one.
For each computational budget, we must train a separate model going through all three steps described above. Moreover, the length configuration search step above is only approximate, as it relies on relaxation of retention parameters which are inherently discrete. This leads to the lack of guaranteed correlation between the success of this stage and true run-time. Even worse, it is a delicate act to tune the length configuration given a target computational budget, because trade-off is implicitly made via a regularization coefficient. Furthermore, PoWER-BERT has an inherent limitation in that it only applies to sequence-level classification because it eliminates word vectors in intermediate layers.

heading: 3 LENGTH-ADAPTIVE TRANSFORMER

text:
In this section, we explain our proposed framework which results in a transformer that reduces the length of a sequence at each layer with an arbitrary rate. We call such a resulting transformer a Length-Adaptive Transformer. We train Length-Adaptive Transformer with LengthDrop which randomly samples the number of hidden vectors to be dropped at each layer with the goal of making the final model robust to such drop in the inference time. Once the model is trained, we search for the optimal trade-off between accuracy and efficiency using multi-objective evolutionary search, which allows us to use the model for any given computational budget without finetuning nor re-training. At the end of this section, we describe Drop-and-Restore process as a way to greatly increase the applicability of PoWER-BERT which forms a building block of the proposed framework.
In short, we train a Length-Adaptive Transformer once with LengthDrop and Drop-and-Restore, and use it with an automatically determined length configuration for inference with any target computational budget, on both sequence-level and token-level tasks.

heading: 3.1 LENGTHDROP

text:
Earlier approaches to efficient inference with transformers have focused on a scenario where the target computational budget for inference is known in advance Sanh et al. (2019); Goyal et al. (2020). This greatly increases the cost of deploying transformers, as it requires us to train a separate transformer for each scenario. Instead, we propose to train one model that could be used for a diverse set of target computational budgets without retraining.
LengthDrop randomly generates a length configuration by sequentially sampling a sequence length li+1 at the (i+ 1)-th layer based on the previous layer’s sequence length li, following the uniform distribution U(d(1 − p)lie, li), where l0 is set to the length of the input sequence, and p is the LengthDrop probability. This sequential sampling results in a length configuration (l1, · · · , lL). Length-Adaptive Transformer can be thought of as consisting of a full model and many sub-models corresponding to different length configuration, similarly to a neural network trained with dropout (Srivastava et al., 2014).
LayerDrop From the perspective of each word vector, the proposed LengthDrop could be thought of as skipping the layers between when it was set aside and the final layer where it was restored. The word vector however does not have any information based on which it can determine whether it would be dropped at any particular layer. In our preliminary experiments, we found that this greatly hinders optimization. We address this issue by using LayerDrop (Fan et al., 2019) which skips each layer of a transformer uniformly at random. The LayerDrop encourages each word vector to be agnostic to skipping any number of layers between when it is dropped and when it is restored, just like dropout (Srivastava et al., 2014) prevents hidden neurons from co-adapting with each other by randomly dropping them.
Sandwich Rule and Inplace Distillation We observed that standard supervised training with LengthDrop does not work well in the preliminary experiments. We instead borrow a pair of training techniques developed by Yu & Huang (2019) which are sandwich rule and inplace distillation, for better optimization as well as final generalization. At each update, we update the full model without LengthDrop as usual to minimize the supervised loss function. We simultaneously update ns randomly-sampled sub-models (which are called sandwiches) and the smallest-possible submodel, which corresponds to keeping only d(1− p)lie word vectors at each layer i, using knowledge distillation (Hinton et al., 2015) from the full model. Here, sub-models mean models with length reduction. They are trained to their prediction close to the full model’s prediction (inplace distillation).

heading: 3.2 EVOLUTIONARY SEARCH OF LENGTH CONFIGURATIONS

text:
After training a Length-Adaptive Transformer with LengthDrop, we search for appropriate length configurations for possible target computational budgets that will be given at inference time. The length configuration determines the model performance in terms of both accuracy and efficiency. In order to search for the optimal length configuration, we propose to use evolutionary search, similarly to Cai et al. (2019) and Wang et al. (2020). This procedure is efficient, as it only requires a single pass through the relatively small validation set for each length configuration, unlike re-training for a new computational budget which requires multiple passes through a significantly larger training set for each budget.
We initialize the population with constant-ratio configurations. Each configuration is created by li+1 = d(1 − r)lie for each layer i with r so that the amount of computation within the initial population is uniformly distributed between those of the smallest and full models. At each iteration, we evolve the population to consist only of configurations lie on a newly updated efficiencyaccuracy Pareto frontier by mutation and cross-over. Mutation alters an original length configuration (l1, · · · , lL) to (l′1, · · · , l′L) by sampling l′i from the uniform distribution U(l′i−1, li+1) with the probability pm or keeping the original length l′i = li, sweeping the layers from i = 1 to i = L. Crossover takes two length configurations and averages the lengths at each layer. Both of these operations are performed while ensuring the monotonicity of the lengths over the layers. We repeat this iteration G times, while maintaining nm mutated configurations and nc crossover’d configurations. Repeating this procedure pushes the Pareto frontier further to identify the best trade-off between two objectives, efficiency and accuracy, without requiring any continuous relaxation of length configurations nor using a proxy objective function.

heading: 3.3 DROP-AND-RESTORE PROCESS

text: The applicability of the PoWER-BERT, based on which our main contribution above was made, is limited to sequence-level classification, because it eliminates word vectors at each layer. In addition to our main contribution above, we thus propose to extend the PoWER-BERT so that it is applicable to token-level classification, such as span-based question-answering. Our proposal, to which we refer as Drop-and-Restore, does not eliminate word vectors at each layer according to the length configuration but instead sets them aside until the final hidden layer. At the final hidden layer, these word vectors are brought back to form the full hidden sequence, as illustrated graphically in Fig. 1.

heading: 4 EXPERIMENT SETUP

text:
Datasets We test the proposed approach on both sequence-level and token-level tasks, the latter of which could not have been done with the original PoWER-BERT unless for the proposed Dropand-Restore. We use MNLI-m and SST-2 from GLUE benchmark (Wang et al., 2018), as was done to test PoWER-BERT earlier, for sequence-level classification. We choose them because consistent accuracy scores from standard training on them due to their sufficiently large training set imply that they are reliable to verify our approach. We use SQuAD 1.1 (Rajpurkar et al., 2016) for token-level classification.
Evaluation metrics We use the number of floating operations (FLOPs) as a main metric to measure the inference efficiency given any length configuration, as it is agnostic to the choice of underlying hardware, unlike other alternatives such as hardware-aware latency (Wang et al., 2020) or energy consumption (Henderson et al., 2020). We later demonstrate that FLOPs and wall-clock time on GPU and CPU correlate well with the proposed approach, which is not necessarily the case for other approaches, such as unstructured weight pruning (Han et al., 2015; See et al., 2016).
Pretrained transformers Since BERT was introduced by Devlin et al. (2018), it has become a standard practice to start from a pretrained (masked) language model and finetune it for each downstream task. We follow the same strategy in this paper and test two pretrained transformerbased language models; BERTBASE (Devlin et al., 2018) and DistilBERT (Sanh et al., 2019), which allows us to demonstrate that the usefulness and applicability of our approach are not tied to any specific architectural choice, such as the number of layers and the maximum length of input sequence. Although we focus on BERT-based masked language models here, the proposed approach is readily applicable to any transformer-based models.
Learning We train a Length-Adaptive Transformer with LengthDrop probability and LayerDrop probability both set to 0.2. We use ns = 2 randomly sampled intermediate sub-models in addition to the full model and smallest model for applying the sandwich learning rule.
We start finetuning the pretrained transformer without Drop-and-Restore first, just as Goyal et al. (2020) did with PoWER-BERT. We then continue finetuning it for another five epochs with Drop-andRestore. This is unlike the recommended three epochs by Devlin et al. (2018), as learning progresses
FLOPs (G)
La te
nc y
(m s/
in st
an ce
)
0
5
10
15
20
10 15 20 25 30 35
GPU (1) GPU (4) GPU (16) GPU (64)
(a) GPU
FLOPs (G)
La te
nc y
(m s/
in st
an ce
)
0
250
500
750
1000
1250
10 15 20 25 30 35
CPU (1) CPU (4) CPU (16) CPU (64)
(b) CPU
Figure 3: Correlation between FLOPs and latency with different length configurations.
slower due to a higher level of stochasticity introduced by LengthDrop and LayerDrop. We use the batch size of 32, the learning rate of 5e− 5 for SQuAD v1.1 and 2e− 5 for MNLI-m and SST, and the maximum sequence length of 384 for SQuAD v1.1 and 128 for MNLI-m and SST.
Search We run up to G = 30 iterations of evolutionary search, using nm = 30 mutated configurations with mutation probability pm = 0.5 and nc = 30 crossover’d configurations, to find the Pareto frontier of accuracy and efficiency.

heading: 5 RESULTS AND ANALYSIS

text:
Efficiency-accuracy trade-off We use SQuAD 1.1 to examine the effect of the proposed approach on the efficiency-accuracy trade-off. When the underlying classifier was not trained with LengthDrop, as proposed in this paper, the accuracy drops even more dramatically as more word vectors are dropped at each layer. The difference between standard transformer and Length-Adaptive Transformer is stark in Fig. 2. This verifies the importance of training a transformer in a way that makes it malleable for inference-time re-configuration.
When the model was trained with the proposed LengthDrop, we notice the efficacy of the proposed approach of using evolutionary search to find the optimal trade-off between inference efficiency and accuracy. The trade-off curve from the proposed search strategy has a larger area-under-curve (AUC) than when constant-rate length reduction was used to meet a target computational budget. It demonstrates the importance of using both LengthDrop and evolutionary search.
We make a minor observation that the proposed approach ends up with a significantly higher accuracy than DistillBERT when enough computational budget is allowed for inference (log FLOPs > 10). This makes our approach desirable in a wide array of scenarios, as it does not require any additional pretraining stage, as does DistilBERT. With a severe constraint on the computational budget, the proposed approach could be used on DistilBERT to significantly improve the efficiency without compromising the accuracy.
Maximizing inference efficiency We consider all three tasks, SQuAD 1.1, MNLI-m and SST-2, and investigate how much efficiency can be gained by the proposed approach with minimal sacrifice of
Model SQuAD 1.1 MNLI-m SST-2 Pretrained
Transformer Method F1 FLOPs Acc FLOPs Acc FLOPs
BERTBase Standard 88.5 1.00x 84.4 1.00x 92.8 1.00x
Length-Adaptive? 89.6 0.89x 85.0 0.58x 93.1 0.36x Length-Adaptive† 88.7 0.45x 84.4 0.35x 92.8 0.35x
DistilBERT Standard 85.8 1.00x 80.9 1.00x 90.6 1.00x
Length-Adaptive? 86.3 0.81x 81.5 0.56x 92.0 0.55x Length-Adaptive† 85.9 0.59x 81.3 0.54x 91.7 0.54x
Table 1: Comparison results of standard Transformer and LengthAdaptive Transformer. Among length configurations on the Pareto frontier of Length-Adaptive Transformer, we pick two representative points: Length-Adaptive? and Length-Adaptive† as the most efficient one while having the highest accuracy and the accuracy higher than (or equal to) standard Transformer, respectively.
accuracy. First, we look at how much efficiency could be gained without losing on the accuracy. That is, we use the length configuration that maximizes the inference efficiency (i.e., minimize the FLOPs) while ensuring that the accuracy is above or same as the accuracy of the standard approach without any drop of word vectors. The results are presented in the rows marked with Length-Adaptive† from Table 1. For example, in the case of BERTBase, the proposed approach reduce FLOPs by more than half across all three tasks.
From Fig. 2, we have observed that the proposed Length-Adaptive Transformer generalize better than the standard, base model in some cases. We thus try to maximize both the inference efficiency and accuracy, in order to see whether it is possible for the proposed algorithm to find a length configuration that both maximizes inference efficiency and improves accuracy. We present the results in the rows marked with Length-Adaptive? from Table 1. For all cases, Length-Adaptive Transformer achieves higher accuracy than a standard transformer does while reducing FLOPs significantly. Although it is not apparent from the table, tor MNLI-m and SST-2, the accuracy of the smallest sub-model is already greater than or equal to that of a standard transformer.
FLOPs vs. Latency As has been discussed in recent literature (see, e.g., (Li et al., 2020; Chin et al., 2020)), FLOPs is not a perfect indicator of the real latency measured in wall-clock time, as the latter is affected by the combination of hardware choice and network architecture. To understand the real-world impact of the proposed approach, we study the relationship between FLOPs, obtained by the proposed procedure, and wall-clock time measured on both CPU and GPU by measuring them while varying length configurations. As shown in Fig. 3, FLOPs and latency exhibit near-linear correlation on GPU, when the minibatch size is ≥ 16, and regardless of the minibatch size, on CPU. In other words, the reduction in FLOPs with the proposed approach directly implies the reduction in wall-clock time.
Convergence of search Although the proposed approach is efficient in that it requires only one round of training, it needs a separate search stage for each target budget. It is important for evolutionary search to converge quickly in the number of forward sweeps of a validation set. As exemplified in Fig. 4, evolutionary search converges after about fifteen iterations.

heading: 6 RELATED WORK

text:
The main purpose of the proposed algorithm is to improve the inference efficiency of a large-scale transformer. This goal has been pursued from various directions, and in this section, we provide a brief overview of these earlier, and some concurrent, attempts in the context of the proposed approach.
Weight pruning Weight pruning (Han et al., 2015) focuses on reducing the number of parameters which directly reflects the memory footprint of a model and indirectly correlates with inference speed. However, their actual speed-up in runtime is usually not significant, especially while executing a model with parallel computation using GPU devices (Tang et al., 2018; Li et al., 2020).
Adaptive architecture There are three major axes along which computation can be reduced in a neural network; (1) input size/length, (2) network depth and (3) network width. The proposed approach, based on PoWER-BERT, adaptively reduces the input length as the input sequence is processed by the transformer layers. In our knowledge, Goyal et al. (2020) is the first work in this direction for transformers. More recently, Funnel-Transformer (Dai et al., 2020) and multi-scale transformer language models (Subramanian et al., 2020) also successfully reduce sequence length in the middle and rescale to full length for the final computation. However, their inference complexity is fixed unlike PoWER-BERT because they are not designed for the control of efficiency.
LayerDrop (Fan et al., 2019) drops random layers during the training to be robust to pruning inspired by Huang et al. (2016). Word-level adaptive depth in Elbayad et al. (2019) might seemingly resemble with length reduction, but word vectors reached the maximal layer are used for self-attention computation without updating themselves. Escaping a network early (Teerapittayanon et al., 2016; Huang et al., 2017) based on the confidence of the prediction (Xin et al., 2020; Schwartz et al., 2020; Liu et al., 2020) also offers a control over accuracy-efficiency trade-off, but it is difficult to tune a threshold for a desired computational budget because of the example-wise adaptive computation.
DynaBERT (Hou et al., 2020) can run at adaptive width (the number of attention heads and intermediate hidden dimension) and depth. Hardware-aware Transformers (Wang et al., 2020) construct a design space with arbitrary encoder-decoder attention and heterogeneous layers in terms of different numbers of layers, attention heads, hidden dimension, and embedding dimension.
Structured dropout A major innovation we introduce over the existing PoWER-BERT is the use of stochastic, structured regularization to make a transformer robust to the choice of length configuration in the inference time. Rippel et al. (2014) proposes a nested dropout to learn ordered representations. Similar to LengthDrop, it samples an index form a prior distribution and drops all units having a larger index than sampled one.
Search There have been a series of attempts at finding the optimal network configuration by solving a combinatorial optimization problem. In computer vision, Once-for-All (Cai et al., 2019) use an evolutionary search (Real et al., 2019) to find a better configuration in dimensions of depth, width, kernel size, and resolution given computational budget. Similarly but differently, our evolutionary search is mutli-objective to find length configurations on the Pareto accuracy-efficiency frontier to cope with any possible computational budgets. Moreover, we only change the sequence length of hidden vectors instead of architectural model size like dimensions.

heading: 7 CONCLUSION AND FUTURE WORK

text:
In this work, we propose a new framework for training a transformer once and using it for efficient inference under any computational budget. With the help of training with LengthDrop and Drop-andRestore process followed by the evolutionary search, our proposed Length-Adaptive Transformer allows any given transformer models to be used with any inference-time computational budget for both sequence-level and token-level classification tasks. Our experiments, on SQuAD 1.1, MNLI-m and SST-2, have revealed that the proposed algorithmic framework significantly pushes a better Pareto frontier on the trade-off between inference efficiency and accuracy. Furthermore, we have observed that the proposed Length-Adaptive Transformer could achieve up to 3x speed-up over the standard transformer without sacrificing accuracy, both in terms of FLOPs and wallclock time.
Although our approach finds an optimal length configuration of a trained classifier per computational budget, it leaves open a question whether the proposed approach could be further extended to support per-instance length configuration by for instance training a small, auxiliary neural network for each computational budget. Yet another aspect we have not investigated in this paper is the applicability of the proposed approach to sequence generation, such as machine translation. We leave both of these research directions for the future.
Our approach is effective, as we have shown in this paper, and also quite simple to implement on top of existing language models. We will release our implementation, which is based on HuggingFace’s Transformers library (Wolf et al., 2019), publicly and plan to adapt it for a broader set of transformerbased models and downstream tasks.

title: LENGTH-ADAPTIVE TRANSFORMER: TRAIN ONCE