summaries: The paper analyzes the possibility of recovering the weight of a teacher network using a student network which is as dense as the original one. The authors prove that with enough samples drawn from the teacher network, the recovery can be done on one-hidden-layer neural networks with linear convergence speed. The authors also discuss the correlation between the needed samples and the sparsity of the teacher network.  To sum up, the well-designed structure makes the workﬂow clear and easy to follow, but the further analysis and discussion are expected to clarify some contributions in the techniques as well as in the evaluation section.

summaries: This paper presents a theoretical analysis of the advantages of learning pruned neural networks . This analysis considers a teacher-student setup with a finite number of training samples. The theoretical results presented in the paper show that pruned networks can have multiple advantages, such as faster training convergence, a lower number of samples required for successful convergence and an enlarged convex region.

summaries: This work takes a theoretical view of LTH, leveraging the geometric structure of the objective function to analyze the generalization error of a pruned network trained in a teacher-student fashion. In particular, they prove that, as a model is pruned, the desirable (convex) region with high-guaranteed generalization performance enlarges, providing explanation for improved performance of winning tickets. Then, the sample complexity of training the pruned network to achieve zero generalization error is analyzed, finding that the number of samples required is proportional to the number of un-pruned weights. Interestingly, the work finds that pruned models enjoy faster convergence to high performance, providing another possible explanation of why winning tickets outperform dense networks.

summaries: The paper gives theoretical explanation for improved generalization error of winning tickets for which only empirical results are known. Their results are based on teacher-student setting in which training samples are assumed to be generated from an unknown teacher network and student network is supposed to learn only from those samples. They give an accelerated gradient descent method for learning the pruned  network and convergence and sample complexity analysis for this algorithm. The empirical risk function is shown to have an enlarged convex region for a pruned network, which justifies the importance of the winning ticket. Learning on pruned network with the AGD algorithm gives a model closer to the teacher network with the same number of iterations, which implies better generalization of the trained pruned network. These findings are validated with experiments on synthetic and real datasets (MNIST, CIFAR-10).

abstractText: The lottery ticket hypothesis (LTH) [20] states that learning on a properly pruned network (the winning ticket) improves test accuracy over the original unpruned network. Although LTH has been justified empirically in a broad range of deep neural network (DNN) involved applications like computer vision and natural language processing, the theoretical validation of the improved generalization of a winning ticket remains elusive. To the best of our knowledge, our work, for the first time, characterizes the performance of training a pruned neural network by analyzing the geometric structure of the objective function and the sample complexity to achieve zero generalization error. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned, indicating the structural importance of a winning ticket. Moreover, when the algorithm for training a pruned neural network is specified as an (accelerated) stochastic gradient descent algorithm, we theoretically show that the number of samples required for achieving zero generalization error is proportional to the number of the non-pruned weights in the hidden layer. With a fixed number of samples, training a pruned neural network enjoys a faster convergence rate to the desired model than training the original unpruned one, providing a formal justification of the improved generalization of the winning ticket. Our theoretical results are acquired from learning a pruned neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.

authors:
Z. Allen-Zhu
Y. Li
Z. Song

title: A convergence theory for deep learning via overparameterization

venue: International Conference on Machine Learning, pages 242–252. PMLR,

authors:
S. Arora
R. Ge
B. Neyshabur
Y. Zhang

title: Stronger generalization bounds for deep nets via a compression approach

venue: J. Dy and A. Krause, editors, Proceedings of the 35th International 10 Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 254–263, Stockholmsmässan, Stockholm Sweden, 10–15 Jul

authors:
C. Baykal
L. Liebenwein
I. Gilitschenski
D. Feldman
D. Rus

title: Data-dependent coresets for compressing neural networks with applications to generalization bounds

venue: International Conference on Learning Representations,

title: Sipping neural networks: Sensitivity-informed provable pruning of neural networks

venue: arXiv preprint arXiv:1910.05422,

authors:
M. Ben
M. Osadchy
V. Braverman
S. Zhou
D. Feldman

title: Data-independent neural pruning via coresets

venue: International Conference on Learning Representations (ICLR),

authors:
M.L. Bermingham
R. Pong-Wong
A. Spiliopoulou
C. Hayward
I. Rudan
H. Campbell
A.F. Wright
J.F. Wilson
F. Agakov
P. Navarro

title: Application of high-dimensional feature selection: evaluation for genomic prediction in man

venue: Scientific reports,

title: Matrix analysis, volume 169

venue: Springer Science & Business Media,

authors:
A. Brutzkus
A. Globerson

title: Globally optimal gradient descent for a convnet with gaussian inputs

venue: Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 605–614. JMLR. org,

authors:
R.T. Chen
Y. Rubanova
J. Bettencourt
D. Duvenaud

title: Neural ordinary differential equations

venue: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6572–6583,

authors:
T. Chen
J. Frankle
S. Chang
S. Liu
Y. Zhang
M. Carbin
Z. Wang

title: The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models

venue: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16306–16316,

authors:
T. Chen
J. Frankle
S. Chang
S. Liu
Y. Zhang
Z. Wang
M. Carbin

title: The lottery ticket hypothesis for pre-trained bert networks

venue: arXiv preprint arXiv:2007.12223,

authors:
L. Chizat
F. Bach

title: On the global convergence of gradient descent for over-parameterized models using optimal transport

venue: Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 3040–3050,

authors:
M. Denil
B. Shakibi
L. Dinh
M. Ranzato
N. de Freitas

title: Predicting parameters in deep learning

venue: In Proceedings of the 26th International Conference on Neural Information Processing Systems-Volume

authors:
V.C. Dinh
L.S. Ho

title: Consistent feature selection for analytic deep neural networks

venue: H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2420–2431. Curran Associates, Inc.,

authors:
X. Dong
S. Chen
S. Pan

title: Learning to prune deep neural networks via layer-wise optimal brain surgeon

venue: Advances in Neural Information Processing Systems, pages 4857–4867,

authors:
S.S. Du
J.D. Lee
Y. Tian
A. Singh
B. Poczos

title: Gradient descent learns one-hiddenlayer cnn: Don’t be afraid of spurious local minima

venue: International Conference on Machine Learning, pages 1338–1347,

authors:
S.S. Du
X. Zhai
B. Poczos
A. Singh

title: Gradient descent provably optimizes overparameterized neural networks

authors:
B. Elesedy
V. Kanade
Y.W. Teh

title: Lottery tickets in linear models: An analysis of iterative magnitude pruning

venue: arXiv preprint arXiv:2007.08243,

authors:
U. Evci
T. Gale
J. Menick
P.S. Castro
E. Elsen

title: Rigging the lottery: Making all tickets winners

venue: International Conference on Machine Learning,

authors:
J. Frankle
M. Carbin

title: The lottery ticket hypothesis: Finding sparse, trainable neural networks

authors:
J. Frankle
G.K. Dziugaite
D. Roy
M. Carbin

title: Linear mode connectivity and the lottery ticket hypothesis

venue: International Conference on Machine Learning, pages 3259–3269. PMLR,

authors:
J. Frankle
G.K. Dziugaite
D.M. Roy
M. Carbin

title: Stabilizing the lottery ticket hypothesis

venue: arXiv preprint arXiv:1903.01611,

authors:
H. Fu
Y. Chi
Y. Liang

title: Guaranteed recovery of one-hidden-layer neural networks via cross entropy

venue: IEEE transactions on signal processing, 68:3225–3235,

authors:
I. Guyon
A. Elisseeff

title: An introduction to variable and feature selection

venue: Journal of machine learning research, 3(Mar):1157–1182,

authors:
S. Han
J. Pool
J. Tran
W. Dally

title: Learning both weights and connections for efficient neural network

venue: Advances in neural information processing systems, pages 1135–1143,

authors:
B. Hassibi
D.G. Stork

title: Second order derivatives for network pruning: Optimal brain surgeon

venue: Advances in neural information processing systems, pages 164–171,

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

venue: Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770– 778,

authors:
H. Hu
R. Peng
Y.-W. Tai
C.-K. Tang

title: Network trimming: A data-driven neuron pruning approach towards efficient deep architectures

venue: arXiv preprint arXiv:1607.03250,

authors:
S. Ioffe
C. Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: International Conference on Machine Learning, pages 448–456,

authors:
A. Jacot
F. Gabriel
C. Hongler

title: Neural tangent kernel: Convergence and generalization in neural networks

venue: Advances in neural information processing systems, pages 8571–8580,

authors:
V. Kuleshov
A. Chaganty
P. Liang

title: Tensor factorization via matrix factorization

venue: Artificial Intelligence and Statistics, pages 507–516,

authors:
Y. LeCun
B. Boser
J.S. Denker
D. Henderson
R.E. Howard
W. Hubbard
L.D. Jackel

title: Backpropagation applied to handwritten zip code recognition

venue: Neural computation, 1(4):541–551,

authors:
Y. LeCun
J.S. Denker
S.A. Solla

title: Optimal brain damage

venue: Advances in neural information processing systems, pages 598–605,

authors:
Y.A. LeCun
L. Bottou
G.B. Orr
K.-R. Müller

title: Efficient backprop

venue: Neural networks: Tricks of the trade, pages 9–48. Springer,

authors:
L. Liebenwein
C. Baykal
H. Lang
D. Feldman
D. Rus

title: Provable filter pruning for efficient neural networks

authors:
Z. Liu
M. Sun
T. Zhou
G. Huang
T. Darrell

title: Rethinking the value of network pruning

authors:
R. Livni
S. Shalev-Shwartz
O. Shamir

title: On the computational efficiency of training neural networks

venue: Advances in neural information processing systems, pages 855–863,

authors:
Y. Lu
C. Ma
Y. Lu
J. Lu
L. Ying

title: A mean field analysis of deep resnet and beyond: Towards provably optimization via overparameterization from depth

venue: International Conference on Machine Learning, pages 6426–6436. PMLR,

authors:
E. Malach
G. Yehudai
S. Shalev-Schwartz
O. Shamir

title: Proving the lottery ticket hypothesis: Pruning is all you need

venue: International Conference on Machine Learning, pages 6682–6691. PMLR,

authors:
S. Mei
A. Montanari
P.-M. Nguyen

title: A mean field view of the landscape of two-layer neural networks

venue: Proceedings of the National Academy of Sciences, 115(33):E7665–E7671,

authors:
D. Molchanov
A. Ashukha
D. Vetrov

title: Variational dropout sparsifies deep neural networks

venue: International Conference on Machine Learning, pages 2498–2507,

title: Towards learning convolutions from scratch

venue: Advances in Neural Information Processing Systems, 33,

authors:
L. Orseau
M. Hutter
O. Rivasplata

title: Logarithmic pruning is all you need

authors:
S. Oymak
M. Soltanolkotabi

title: Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks

venue: IEEE Journal on Selected Areas in Information Theory, 1(1),

authors:
V. Ramanujan
M. Wortsman
A. Kembhavi
A. Farhadi
M. Rastegari

title: What’s hidden in a randomly weighted neural network

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

authors:
A. Renda
J. Frankle
M. Carbin

title: Comparing rewinding and fine-tuning in neural network pruning

authors:
I. Safran
O. Shamir

title: Spurious local minima are common in two-layer relu neural networks

venue: International Conference on Machine Learning, pages 4430–4438,

title: Distribution-specific hardness of learning neural networks

venue: The Journal of Machine Learning Research, 19(1):1135–1163,

authors:
S. Singh
A. Majumdar

title: Deep sparse coding for non–intrusive load monitoring

authors:
M. Soltanolkotabi
A. Javanmard
J.D. Lee

title: Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

venue: IEEE Transactions on Information Theory, 65(2):742–769,

authors:
S. Srinivas
R.V. Babu

title: Data-free parameter pruning for deep neural networks

venue: arXiv preprint arXiv:1507.06149,

title: An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis

venue: Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3404–3413. JMLR. org,

title: User-friendly tail bounds for sums of random matrices

venue: Foundations of computational mathematics, 12(4):389–434,

title: Introduction to the non-asymptotic analysis of random matrices

venue: arXiv preprint arXiv:1011.3027,

authors:
C. Wang
G. Zhang
R. Grosse

title: Picking winning tickets before training by preserving gradient flow

authors:
F. Wang
K. Li
C. Liu
Z. Mi
M. Shafie-Khah
J.P.S. Catalão

title: Synchronous pattern matching principle-based residential demand response baseline estimation: Mechanism analysis and approach description

venue: IEEE Transactions on Smart Grid, 9(6):6972–6985,

authors:
W. Wen
C. Wu
Y. Wang
Y. Chen
H. Li

title: Learning structured sparsity in deep neural networks

venue: Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2082–2090,

authors:
T.-J. Yang
Y.-H. Chen
V. Sze

title: Designing energy-efficient convolutional neural networks using energy-aware pruning

venue: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5687–5695,

authors:
M. Ye
C. Gong
L. Nie
D. Zhou
A. Klivans
Q. Liu

title: Good subnetworks provably exist: Pruning via greedy forward selection

venue: International Conference on Machine Learning, pages 10820–10830. PMLR,

authors:
M. Ye
Y. Sun

title: Variable selection via penalized neural network: a drop-out-one loss approach

venue: International Conference on Machine Learning, pages 5620–5629. PMLR,

authors:
M. Ye
L. Wu
Q. Liu

title: Greedy optimization provably wins the lottery: Logarithmic number of winning tickets is enough

authors:
G. Yehudai
O. Shamir

title: On the power and limitations of random features for understanding neural networks

venue: Advances in Neural Information Processing Systems, pages 6594–6604,

authors:
H. You
C. Li
P. Xu
Y. Fu
Y. Wang
X. Chen
R.G. Baraniuk
Z. Wang
Y. Lin

title: Drawing early-bird tickets: Toward more efficient training of deep networks

authors:
C. Zhang
S. Bengio
M. Hardt
B. Recht
O. Vinyals

title: Understanding deep learning requires rethinking generalization

venue: arXiv preprint arXiv:1611.03530,

authors:
S. Zhang
M. Wang
S. Liu
P.-Y. Chen
J. Xiong

title: Fast learning of graph neural networks with guaranteed generalizability:one-hidden-layer case

venue: 2020 International Conference on Machine Learning (ICML),

title: Guaranteed convergence of training convolutional neural networks via accelerated gradient descent

venue: 2020 54th Annual Conference on Information Sciences and Systems (CISS),

authors:
S. Zhang
M. Wang
J. Xiong
S. Liu
P.-Y. Chen

title: Improved linear convergence of training cnns with generalizability guarantees: A one-hidden-layer case

venue: IEEE Transactions on Neural Networks and Learning Systems, 32(6):2622–2635,

authors:
L. Zhao
Q. Hu
W. Wang

title: Heterogeneous feature selection with multi-modal deep neural networks and sparse group lasso

venue: IEEE Transactions on Multimedia, 17(11):1936–1948,

authors:
K. Zhong
Z. Song
P. Jain
P.L. Bartlett
I.S. Dhillon

title: Recovery guarantees for onehidden-layer neural networks

venue: Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 4140–4149. JMLR. org, https://arxiv.org/abs/1706.03175,

authors:
H. Zhou
J. Lan
R. Liu
J. Yosinski

title: Deconstructing lottery tickets: Zeros, signs, and the supermask

venue: Advances in Neural Information Processing Systems 32, pages 3597–3607.

authors:
W. Zhou
V. Veitch
M. Austern
R.P. Adams
P. Orbanz

title: Non-vacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach

authors:
D. Zou
Y. Cao
D. Zhou
Q. Gu

title: Gradient descent optimizes over-parameterized deep relu networks

venue: Machine Learning, 109(3):467–492,

authors:
D. Zou
Q. Gu

title: An improved analysis of training over-parameterized deep neural networks

venue: Advances in Neural Information Processing Systems, pages 2055–2064,

heading: 1 Introduction

text:
Neural network pruning can reduce the computational cost of model training and inference significantly and potentially lessen the chance of overfitting [33, 26, 15, 25, 28, 51, 58, 41]. The recent Lottery Ticket Hypothesis (LTH) [20] claims that a randomly initialized dense neural network al-
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
ways contains a so-called “winning ticket,” which is a sub-network bundled with the corresponding initialization, such that when trained in isolation, this winning ticket can achieve at least the same testing accuracy as that of the original network by running at most the same amount of training time. This so-called “improved generalization of winning tickets” is verified empirically in [20]. LTH has attracted a significant amount of recent research interests [45, 70, 39]. Despite the empirical success [19, 63, 55, 11], the theoretical justification of winning tickets remains elusive except for a few recent works. [39] provides the first theoretical evidence that within a randomly initialized neural network, there exists a good sub-network that can achieve the same test performance as the original network. Meanwhile, recent work [42] trains neural network by adding the `1 regularization term to obtain a relatively sparse neural network, which has a better performance numerically.
However, the theoretical foundation of network pruning is limited. The existing theoretical works usually focus on finding a sub-network that achieves a tolerable loss in either expressive power or training accuracy, compared with the original dense network [2, 71, 61, 43, 4, 3, 35, 5, 59]. To the best of our knowledge, there exists no theoretical support for the improved generalization achieved by winning tickets, i.e., pruned networks with faster convergence and better test accuracy.
Contributions: This paper provides the first systematic analysis of learning pruned neural networks with a finite number of training samples in the oracle-learner setup, where the training data are generated by a unknown neural network, the oracle, and another network, the learner, is trained on the dataset. Our analytical results also provide a justification of the LTH from the perspective of the sample complexity. In particular, we provide the first theoretical justification of the improved generalization of winning tickets. Specific contributions include:
1. Pruned neural network learning via accelerated gradient descent (AGD): We propose an AGD algorithm with tensor initialization to learn the pruned model from training samples. Our algorithm converges to the oracle model linearly, which has guaranteed generalization.
2. First sample complexity analysis for pruned networks: We characterize the required number of samples for successful convergence, termed as the sample complexity. Our sample complexity bound depends linearly on the number of the non-pruned weights and is a significant reduction from directly applying conventional complexity bounds in [69, 66, 67].
3. Characterization of the benign optimization landscape of pruned networks: We show analytically that the empirical risk function has an enlarged convex region for a pruned network, justifying the importance of a good sub-network (i.e., the winning ticket).
4. Characterization of the improved generalization of winning tickets: We show that gradientdescent methods converge faster to the oracle model when the neural network is properly pruned, or equivalently, learning on a pruned network returns a model closer to the oracle model with the same number of iterations, indicating the improved generalization of winning tickets.
Notations. Vectors are bold lowercase, matrices and tensors are bold uppercase. Scalars are in normal font, and sets are in calligraphy and blackboard bold font. I denote the identity matrix. N and R denote the sets of nature number and real number, respectively. ‖z‖ denotes the `2-norm of a vector z, and ‖Z‖2, ‖Z‖F and ‖Z‖∞ denote the spectral norm, Frobenius norm and the maximum value of matrix Z, respectively. [Z] stands for the set of {1, 2, · · · , Z} for any number Z ∈ N. In addition, f(r) = O(g(r)) ( or f(r) = Ω(g(r)) ) if f ≤ C · g ( or f ≥ C · g ) for some constant C > 0 when r is large enough. f(r) = Θ(g(r)) if both f(r) = O(g(r)) and f(r) = Ω(g(r)) holds, where c · g ≤ f ≤ C · g for some constant 0 ≤ c ≤ C when r is large enough.

heading: 1.1 Related Work

text:
Network pruning. Network pruning methods seek a compressed model while maintaining the expressive power. Numerical experiments have shown that over 90% of the parameters can be pruned without a significant performance loss [10]. Examples of pruning methods include irregular weight pruning [25], structured weight pruning [57], neuron-based pruning [28], and projecting the weights to a low-rank subspace [13].
Winning tickets. [20] employs an Iterative Magnitude Pruning (IMP) algorithm to obtain the proper sub-network and initialization. IMP and its variations [22, 46] succeed in deeper networks like Residual Networks (Resnet)-50 and Bidirectional Encoder Representations from Transformers (BERT) network [11]. [21] shows that IMP succeeds in finding the “winning ticket” if the ticket is
stable to stochastic gradient descent noise. In parallel, [36] shows numerically that the “winning ticket” initialization does not improve over a random initialization once the correct sub-networks are found, suggesting that the benefit of “winning ticket” mainly comes from the sub-network structures. [18] analyzes the sample complexity of IMP from the perspective of recovering a sparse vector in a linear model rather than learning neural networks.
Feature sparsity. High-dimensional data often contains redundant features, and only a subset of the features is used in training [6, 14, 27, 60, 68]. Conventional approaches like wrapper and filter methods score the importance of each feature in a certain way and select the ones with highest scores [24]. Optimization-based methods add variants of the `0 norm as a regularization to promote feature sparsity [68]. Different from network pruning where the feature dimension still remains high during training, the feature dimension is significantly reduced in training when promoting feature sparsity.
Over-parameterized model. When the number of weights in a neural network is much larger than the number of training samples, the landscape of the objective function of the learning problem has no spurious local minima, and first-order algorithms converge to one of the global optima [37, 44, 64, 50, 9, 49, 38]. However, the global optima is not guaranteed to generalize well on testing data [62, 64].
Generalization analyses. The existing generalization analyses mostly fall within three categories. One line of research employs the Mean Field approach to model the training process by a differential equation assuming infinite network width and infinitesimal training step size [12, 40, 56]. Another approach is the neural tangent kernel (NTK) [30], which requires strong and probably unpractical over-parameterization such that the nonlinear neural network model behaves as its linearization around the initialization [1, 17, 72, 73]. The third line of works follow the oracle-learner setup, where the data are generated by an unknown oracle model, and the learning objective is to estimate the oracle model, which has a generalization guarantee on testing data. However, the objective function has intractably many spurious local minima even for one-hidden-layer neural networks [48, 47, 64]. Assuming an infinite number of training samples, [8, 16, 52] develop learning methods to estimate the oracle model. [23, 69, 66, 67] extend to the practical case of a finite number of samples and characterize the sample complexity for recovering the oracle model. Because the analysis complexity explodes when the number of hidden layers increases, all the analytical results about estimating the oracle model are limited to one-hidden-layer neural networks, and the input distribution is often assumed to be the standard Gaussian distribution.

heading: 2 Problem Formulation

text:
In an oracle-learner model, given any input x ∈ Rd, the corresponding output y is generated by a pruned one-hidden-layer neural network, called oracle, as shown in Figure 1. The oracle network is equipped with K neurons where the j-th neuron is connected to any arbitrary r∗j (r ∗ j ≤ d) input features. LetW ∗ = [w∗1, · · · ,w∗K ] ∈ Rd×K denotes all the weights (pruned ones are represented by zero). The number of non-zero entries in w∗j is at most r ∗ j . The oracle network is not unique because permuting neurons together with the corresponding weights does not change the output. Therefore, the output label y obtained by the oracle network satisfies 1
y = 1
K K∑ j=1 φ(w∗Tj x) + ξ := g(x;W ∗) + ξ = g(x;W ∗P ) + ξ, (1)
where ξ is arbitrary unknown additive noise bounded by some constant |ξ|, φ is the rectified linear unit (ReLU) activation function with φ(z) = max{z, 0}, and P ∈ {0, 1}K×K is any permutation matrix. M∗ is a mask matrix for the oracle network, such that M∗j,i equals to 1 if the weight w∗j,i is not pruned, and 0 otherwise. Then,M∗ is an indicator matrix for the non-zero entries ofW ∗ with M∗ W ∗ = W ∗, where is entry-wise multiplication. Based on N pairs of training samples D = {xn, yn}Nn=1 generated by the oracle, we train on a learner network equipped with the same number of neurons in the oracle network. However, the j-th neuron in the learner network is connected to rj input features rather than r∗j . Let rmin, rmax, and rave denote the minimum, maximum, and average value of {rj}Kj=1, respectively. LetM denote the
1It is extendable to binary classification, and the output is generated by Prob ( yn = 1|xn ) = g(xn;W ∗).
mask matrix with respect to the learner network, and wj is the j-th column ofW . The empirical risk function is defined as
f̂D(W ) = 1
2N N∑ n=1 ( 1 K K∑ j=1 φ(wTj xn)− yn )2 . (2)
When the maskM is given, the learning objective is to estimate a proper weight matrixW for the learner network from the training samples D via solving
minW∈Rd×K f̂D(W ) s.t. M W = W . (3)
M is called an accurate mask if the support ofM covers the support of a permutation ofM∗, i.e., there exists a permutation matrix P such that (M∗P ) M = M∗. When M is accurate, and ξ = 0, there exists a permutation matrix P such that W ∗P is a global optimizer to (3). Hence, if W ∗P can be estimated by solving (3), one can learn the oracle network accurately, which has guaranteed generalization performance on the testing data.
We assume xn is independent and identically distributed from the standard Gaussian distribution N (0, Id×d). The Gaussian assumption is motivated by the data whitening [34] and batch normalization techniques [29] that are commonly used in practice to improve learning performance. Moreover, training one-hidden-layer neural network with multiple neurons has intractable many fake minima [47] without any input distribution assumption. In addition, the theoretical results in Section 3 assume an accurate mask, and inaccurate mask is evaluated empirically in Section 4.
The questions that this paper addresses include: 1. what algorithm to solve (3)? 2. what is the sample complexity for the accurate estimate of the weights in the oracle network? 3. what is the impact of the network pruning on the difficulty of the learning problem and the performance of the learned model?

heading: 3 Algorithm and Theoretical Results

text: Section 3.1 studies the geometric structure of (3), and the main results are in Section 3.2. Section 3.3 briefly introduces the proof sketch and technical novelty, and the limitations are in Section 3.4.

heading: 3.1 Local Geometric Structure

text:
Theorem 1 characterizes the local convexity of f̂D in (3). It has two important implications.
1. Strictly locally convex near ground truth: f̂D is strictly convex nearW ∗P for some permutation matrix P , and the radius of the convex ball is negatively correlated with √ r̃, where r̃ is in the order of rave. Thus, the convex ball enlarges as any rj decreases.
2. Importance of the winning ticket architecture: Compared with training on the dense network directly, training on a properly pruned sub-network has a larger local convex region near W ∗P , which may lead to easier estimation of W ∗P . To some extent, this result can be viewed as a theoretical validation of the importance of the winning architecture (a good sub-network) in [20]. Formally, we have
Theorem 1 (Local Convexity). Assume the mask M of the learner network is accurate. Suppose constants ε0, ε1 ∈ (0, 1) and the number of samples satisfies
N = Ω ( ε−21 K 4r̃ log q ) , (4)
for some large constant q > 0, where
r̃ = 1
8K4
(∑K k=1 ∑K j=1(1 + δj,k)(rj + rk) 1 2 )2 , (5)
δj,k is 1 if the indices of non-pruned weights in the j-th and k-th neurons overlap and 0 otherwise. Then, there exists a permutation matrix P such that for anyW that satisfies
‖W −W ∗P ‖F = O ( ε0 K2 ) , andM W = W , (6)
its Hessian of f̂D, with probability at least 1−K · q−rmin , is bounded as:
Θ (1− ε0 − ε1
K2
) I ∇2f̂D(W ) Θ ( 1 K ) I. (7)
Remark 1.1 (Parameter r̃): Clearly r̃ is a monotonically increasing function of any rj from (5). Moreover, one can check that 18rave ≤ r̃ ≤ rave. Hence, r̃ is in the order of rave. Remark 1.2 (Local landscape): Theorem 1 shows that with enough samples as shown in (4), in a local region ofW ∗P as shown in (6), all the eigenvalues of the Hessian matrix of the empirical risk function are lower and upper bounded by two positive constants. This property is useful in designing efficient algorithms to recoverW ∗P , as shown in Section 3.2.
Remark 1.3 (Size of the convex region): When the number of samples N is fixed and r changes, ε1 can be Θ( √ r̃/N) while (4) is still met. ε0 in (7) can be arbitrarily close to but smaller than 1− ε1 so that the Hessian matrix is still positive definite. Then from (6), the radius of the convex ball is Θ(1) − Θ( √ r̃/N), indicating an enlarged region when r̃ decreases. The enlarged convex region serves as an important component in proving the faster convergence rate, summarized in Theorem 2. Besides this, as Figure 1 shown in [20], the authors claim that the learning is stable if the linear interpolation of the learned models with SGD noises still remain similar in performance, which is summarized as the concept “linearly connected region.” Intuitively, we conjecture that the winning ticket shows a better performance in the stability analysis because it has a larger convex region. In the other words, a larger convex region indicates that the learning is more likely to be stable in the linearly connected region.

heading: 3.2 Convergence Analysis with Accelerated Gradient Descent

text:
We propose to solve the non-convex problem (3) via the accelerated gradient descent (AGD) algorithm, summarized in Algorithm 1. Compared with the vanilla gradient descent (GD) algorithm, AGD has an additional momentum term, denoted by β(W (t) −W (t−1)), in each iteration. AGD enjoys a faster convergence rate than vanilla GD in solving optimization problems, including learning neural networks [65]. Vanilla GD can be viewed as a special case of AGD by letting β = 0. The initial point W (0) can be obtained through a tensor method, and the details are provided in Appendix B.
Algorithm 1 Accelerated Gradient Descent (AGD) Algorithm 1: Input: training data D = {(xn, yn)}Nn=1, gradient step size η, momentum parameter β, and an
initializationW (0) by the tensor initialization method; 2: Partition D into T = log(1/ε) disjoint subsets, denoted as {Dt}Tt=1; 3: for t = 1, 2, · · · , T do 4: W (t+1) = W (t) − η ·M ∇f̂Dt(W
(t)) + β(W (t) −W (t−1)) 5: end for 6: Return: W (T )
The theoretical analyses of our algorithm are summarized in Theorem 2 (convergence) and Lemma 1 (Initialization). The significance of these results can be interpreted from the following aspects.
1. Linear convergence to the oracle model: Theorem 2 implies that if initialized in the local convex region, the iterates generated by AGD converge linearly toW ∗P for some P when noiseless. When there is noise, they converge to a pointW (T ). The distance betweenW (T ) andW ∗P is proportional to the noise level and scales in terms of O( √ r̃/N). Moreover, when N is fixed, the convergence rate
of AGD is Θ( √ r̃/K). Recall that Algorithm 1 reduces to the vanilla GD by setting β = 0. The rate for the vanilla GD algorithm here is Θ( √ r̃/K) by setting β = 0 by Theorem 2, indicating a slower convergence than AGD. Lemma 1 shows the tensor initialization method indeed returns an initial point in the convex region.
2. Sample complexity for accurate estimation: We show that the required number of samples for successful estimation of the oracle model is Θ ( r̃ log q log(1/ε) ) for some large constant q and estimation accuracy ε. Our sample complexity is much less than the conventional bound of Θ(d log q log(1/ε)) for one-hidden-layer networks [69, 66, 67]. This is the first theoretical characterization of learning a pruned network from the perspective of sample complexity.
3. Improved generalization of winning tickets: We prove that with a fixed number of training samples, training on a properly pruned sub-network converges faster toW ∗P than training on the original dense network. Our theoretical analysis justifies that training on the winning ticket can meet or exceed the same test accuracy within the same number of iterations. To the best of our knowledge, our result here provides the first theoretical justification for this intriguing empirical finding of “improved generalization of winning tickets” by [20]. Theorem 2 (Convergence). Assume the maskM of the learner network is accurate. SupposeW (0) satisfies (6) and the number of samples satisfies
N = Ω ( ε−20 K 6r̃ log q log(1/ε) )
(8)
for some ε0 ∈ (0, 1/2). Let η = K/14 in Algorithm 1. Then, the iterates {W (t)}Tt=1 returned by Algorithm 1 converges linearly toW ∗ up to the noise level with probability at least 1−K2T · q−rmin
‖W (t) −W ∗P ‖F ≤ν(β)t‖W (0) −W ∗P ‖F +O (∑
j
√ rj log q
N
) · |ξ|, (9)
and ‖W (T ) −W ∗P ‖F ≤ε‖W ∗‖F +O (∑
j
√ rj log q
N
) · |ξ|, (10)
for a fixed permutation matrix P , where ν(β) is the rate of convergence that depends on β with ν(β∗) = 1−Θ ( 1−ε0√ K ) for some non-zero β∗ and ν(0) = 1−Θ ( 1−ε0 K ) . Lemma 1 (Initialization). Assume the noise |ξ| ≤ ‖W ∗‖2 and the number of samples N = Ω ( ε−20 K 5rmax log q )
for ε0 > 0 and large constant q, the tensor initialization method outputs W (0) such that (6) holds, i.e., ‖W (0) −W ∗‖F = O ( ε0σK K2 ) with probability at least 1− q−rmax .
Remark 2.1 (Faster convergence on pruned network): With a fixed number of samples, when r̃ decreases, ε0 can increase as Θ( √ r̃) while (8) is still met. Then ν(0) = Θ( √ r̃/K) and ν(β∗) =
Θ( √ r̃/K). Therefore, when r̃ decreases, both the stochastic and accelerated gradient descent
converge faster. Note that as long asW (0) is initialized in the local convex region, not necessarily by the tensor method, Theorem 2 guarantees the accurate recovery. [66, 67] analyze AGD on convolutional neural networks, while this paper focuses on network pruning.
Remark 2.2 (Sample complexity of initialization): From Lemma 1, the required number of samples for a proper initialization is Ω ( ε−20 K 5rmax log q ) . Because rmax ≤ Krave and r̃ = Ω(rave), this number is no greater than the sample complexity in (8). Thus, provided that (8) is met, Algorithm 1 can estimate the oracle network model accurately.
Remark 2.3 (Inaccurate mask): The above analyses are based on the assumption that the mask of the learner network is accurate. In practice, a mask can be obtained by an iterative pruning method such as [20] or a one-shot pruning method such as [55]. In Appendix E, we prove that the magnitude pruning method can obtain an accurate mask with enough training samples. Moreover, empirical experiments in Section 4.2 and 4.3 suggest that even if the mask is not accurate, the three properties (linear convergence, sample complexity with respect to the network size, and improved generalization of winning tickets) can still hold. Therefore, our theoretical results provide some insight into the empirical success of network pruning.

heading: 3.3 The Sketch of Proofs and Technical Novelty

text:
Our proof outline is inspired by [69] on fully connected neural networks, however, major technical changes are made in this paper to generalize the analysis to an arbitrarily pruned network. To characterize the local convex region of f̂D (Theorem 1), the idea is to bound the Hessian matrix of the population risk function, which is the expectation of the empirical risk function, locally and then characterize the distance between the empirical and population risk functions through the concentration bounds. Then, the convergence of AGD (Theorem 2) is established based on the desired local curvature, which in turn determines the sample complexity. Finally, to initialize in the local convex region (Lemma 1), we construct tensors that contain the weights information and apply a decomposition method to estimate the weights.
Our technical novelties are as follows. First, a direct application of the results in [69] leads to a sample complexity bound that is linear in the feature dimension d. We develop new techniques to tighten the sample complexity bound to be linear in r̃, which can be significantly smaller than d for a sufficiently pruned network. Specifically, we develop new concentration bounds (Lemmas 4 and 5 in Appendix) to bound the distance between the population and empirical risk functions rather than using the bound in [69]. Second, instead of restricting the acitivation to be smooth for convergence analysis, we study the case of ReLU function which is non-smooth. Third, new tensors are constructed for pruned networks (see (21)-(23) in Appendix) in computing the initialization, and our new concentration bounds are employed to reduce the required number of samples for a proper initialization. Last, Algorithm 1 employs AGD and is proved to converge faster than the GD algorithm in [69].

heading: 3.4 Limitations

text: Like most theoretical works based on the oracle-learner setup, limitations of this work include (1) one hidden layer only; and (2) the input follows the Gaussian distribution. Extension to multi-layer might be possible if the following technical challenges are addressed. First, when characterizing the local convex region, one needs to show that the Hessian matrix is positive definite. In multi-layer networks, the Hessian matrix is more complicated to compute. Second, new concentration bounds need to be developed because the input feature distributions to the second and third layers depend on the weights in previous layers. Third, the initialization approach needs to be revised. The team is also investigating the other input distributions such as Gaussian mixture models.

heading: 4 Numerical Experiments

text:
The theoretical results are first verified on synthetic data, and we then analyze the pruning performance on both synthetic and real datasets. In Section 4.1, Algorithm 1 is implemented with minor modification, such that, the initial point is randomly selected as ‖W (0) −W ∗‖F /‖W ∗‖F < λ for some λ > 0 to reduce the computation. Algorithm 1 terminates when ‖W (t+1)−W (t)‖F /‖W (t)‖F is smaller than 10−8 or reaching 10000 iterations. In Sections 4.2 and 4.3, the Gradient Signal Preservation (GraSP) algorithm [55] and IMP algorithm [10, 20]2 are implemented to prune the neural networks. As many works like [11, 10, 20] have already verified the faster convergence and better generalization accuracy of the winning tickets empirically, we only include the results of some representative experiments, such as training MNIST and CIFAR-10 on Lenet-5 [32] and Resnet-50 [27] networks, to verify our theoretical findings.
The synthetic data are generated using a oracle model in Figure 1. The input xn’s are randomly generated from Gaussian distribution N (0, Id×d) independently, and indices of non-pruned weights of the j-th neuron are obtained by randomly selecting rj numbers without replacement from [d]. For the convenience of generating specific r̃, the indices of non-pruned weights are almost overlapped ( ∑ j ∑ k δjδk > 0.95K
2) except for Figure 5. In Figures 2 and 4, rj is selected uniformly from [0.9r̃, 1.1r̃] for a given r̃, and rj are the same in value for all j in other figures. Each non-zero entry ofW ∗ is randomly selected from [−0.5, 0.5] independently. The noise ξn’s are i.i.d. from N (0, σ2), and the noise level is measured by σ/Ey , where Ey is the root mean square of the noiseless outputs.
2The source codes used are downloaded from https://github.com/VITA-Group/CV_LTH_Pre-training.

heading: 4.1 Evaluation of theoretical findings on synthetic data

text:
Local convexity near W ∗. We set the number of neurons K = 10, the dimension of the data d = 500 and the sample size N = 5000. Figure 2 illustrates the success rate of Algorithm 1 when r̃ changes. The y-axis is the relative distance of the initializationW (0) to the ground-truth. For each pair of r̃ and the initial distance, 100 trails are constructed with the network weights, training data and the initializationW (0) are all generated independently in each trail. Each trail is called successful if the relative error of the solutionW returned by Algorithm 1, measured by ‖W −W ∗‖F /‖W ∗‖F , is less than 10−4. A black block means Algorithm 1 fails in estimatingW ∗ in all trails while a white block indicates all success. As Algorithm 1 succeeds ifW (0) is in the local convex region nearW ∗, we can see that the radius of convex region is indeed linear in −r̃ 12 , as predicted by Theorem 1. Convergence rate. Figure 3 shows the convergence rate of Algorithm 1 when r̃ changes. N = 5000, d = 300, K = 10, η = 0.5, and β = 0.2. Figure 3(a) shows that the relative error decreases exponentially as the number of iterations increases, indicating the linear convergence of Algorithm 1. As shown in Figure 3(b), the results are averaged over 20 trials with different initial points, and the areas in low transparency represent the standard deviation errors. We can see that the convergence rate is almost linear in √ r̃, as predicted by Theorem 2. We also compare with GD by setting β as 0. One can see that AGD has a smaller convergence rate than GD, indicating faster convergence.
10 12 14 16 18 20 2 6
10 14 18 22 26 30 34 38
Figure 2: The radius of the local convex region against r̃ 1 2
Sample complexity. Figures 4 and 5 show the success rate of Algorithm 1 when varying N and r̃. d is fixed as 100. In Figure 4, we construct 100 independent trails for each pair of N and r̃, where the ground-truth model and training data are generated independently in each trail. One can see that the required number of samples for successful estimation is linear in r̃, as predicted by (8). In Figure 5, rj is fixed as 20 for all neurons, but different network architectures after pruning are considered. One can see that although the number of remaining weights is the same, r̃ can be different in different architectures, and the sample complexity increases as r̃ increases, as predicted by (8).
r̃
r̃ 1 2 at different noise level
Performance in noisy case. Figure 6 shows the relative error of the learned model by Algorithm 1 from noisy measurements when r̃ changes. N = 1000, K = 10, and d = 300. The results are averaged over 100 independent trials, and standard deviation is around 2% to 8% of the corresponding relative errors. The relative error is linear in r̃ 1 2 , as predicted by (9). Moreover, the relative error is proportional to the noise level |ξ|.

heading: 4.2 Performance with inaccurate mask on synthetic data

text:
The performance of Algorithm 1 is evaluated when the maskM of the learner network is inaccurate. The number of neurons K is 5. The dimension of inputs d is 100. r∗j of the oracle model is 20 for
all j ∈ [K]. GraSP algorithm [55] is employed to find masks based only on early-trained weights in 20 iterations of AGD. The mask accuracy is measured by ‖M∗ M‖0/‖M∗‖0, whereM∗ is the mask of the oracle model. The pruning ratio is defined as (1− rave/d)× 100%. The number of training samples N is 200. The model returned by Algorithm 1 is evaluated on Ntest = 105 samples, and the test error is measured by √∑ n |yn − ŷn|2/Ntest, where ŷn is the output of the learned model with the input xn, and (xn, yn) is the n-th testing sample generated by the oracle network.
Improved generalization by GraSP. Figure 7 shows the test error with different pruning ratios. For each pruning ratio, we randomly generate 1000 independent trials. Because the mask of the learner network in each trail is generated independently, we compute the average test error of the learned models in all the trails with same mask accuracy. If there are less than 10 trails for certain mask accuracy, the result of that mask accuracy is not reported as it is statistically meaningless. The test error decreases as the mask accuracy increases. More importantly, at fixed mask accuracy, the test error decreases as the pruning ratio increases. That means the generalization performance improves when r̃ deceases, even if the mask is not accurate.
Linear convergence. Figure 8 shows the convergence rate of Algorithm 1 with different pruning ratios. We show the smallest number of iterations required to achieve a certain test error of the learned model, and the results are averaged over the independent trials with mask accuracy between 0.85 and 0.90. Even with inaccurate mask, the test error converges linearly. Moreover, as the pruning ratio increases, Algorithm 1 converges faster.
Sample complexity with respect to the pruning ratio. Figure 9 shows the test error when the number of training samples N changes. All the other parameters except N remain the same. The results are averaged over the trials with mask accuracy between 0.85 and 0.90. We can see the test error decreases when N increases. More importantly, as the pruning ratio increases, the required number of samples to achieve the same test error (no less than 10−3) decreases dramatically. That means the sample complexity decreases as r̃ decreases even if the mask is inaccurate.

heading: 4.3 Performance of IMP on synthetic, MNIST and CIFAR-10 datasets

text:
We implement the IMP algorithm to obtain pruned networks on synthetic, MNIST and CIFAR-10 datasets. Figure 10 shows the test performance of a pruned network on synthetic data with different sample sizes. Here in the oracle network model, K = 5, d = 100, and r∗j = 20 for all j ∈ [K]. The noise level σ/Ey = 10−3. One observation is that for a fixed sample size N greater than 100, the test error decreases as the pruning ratio increases. This verifies that the IMP algorithm indeed prunes the network properly. It also shows that the learned model improves as the pruning progresses, verifying our theoretical result in Theorem 2 that the difference of the learned model from the oracle model decreases as rj decreases. The second observation is that the test error decreases as N increases for any fixed pruning ratio. This verifies our result in Theorem 2 that the difference of the learned model from the oracle model decreases as the number of training samples increases. When the pruning ratio is too large (greater than 80%), the pruned network cannot explain the data properly, and thus the test error is large for all N . When the number of samples is too small, like N = 100, the test error is always large, because it does not meet the sample complexity requirement for estimating the oracle model even though the network is properly pruned.
Figures 11 and 12 show the test performance of learned models by implementing the IMP algorithm on MNIST and CIFAR-10 using Lenet-5 [32] and Resnet-50 [27] architecture, respectively. The
experiments follow the standard setup in [10] except for the size of the training sets. To demonstrate the effect of sample complexity, we randomly selected N samples from the original training set without replacement. As we can see, a properly pruned network (i.e., winning ticket) helps reduce the sample complexity required to reach the test accuracy of the original dense model. For example, training on a pruned network returns a model (e.g., P1 and P3 in Figures 11 and 12) that has better testing performance than a dense model (e.g., P2 and P4 in Figures 11 and 12) trained on a larger data set. Given the number of samples, we consistently find the characteristic behavior of winning tickets: That is, the test accuracy could increase when the pruning ratio increases, indicating the effectiveness of pruning. The test accuracy then drops when the network is overly pruned. The results show that our theoretical characterization of sample complexity is well aligned with the empirical performance of pruned neural networks and explains the improved generalization observed in LTH.

heading: 5 Conclusions

text:
This paper provides the first theoretical analysis of learning one-hidden-layer pruned neural networks, which offers formal justification of the improved generalization of winning ticket observed from empirical findings in LTH. We characterize analytically the impact of the number of remaining weights in a pruned network on the required number of samples for training, the convergence rate of the learning algorithm, and the accuracy of the learned model. We also provide extensive numerical validations of our theoretical findings.
Broader impacts
We see no ethical or immediate societal consequence of our work. This paper contributes to the theoretical foundation of both network pruning and generalization guarantee. The former encourages the development of learning method to reduce the computational cost. The latter increases the public trust in incorporating AI technology in critical domains.

heading: Acknowledgement

text: This work was supported by AFOSR FA9550-20-1-0122, ARO W911NF-21-1-0255, NSF 1932196 and the Rensselaer-IBM AI Research Collaboration (http://airc.rpi.edu), part of the IBM AI Horizons Network (http://ibm.biz/AIHorizons). We thank Tianlong Chen at University of Texas at Austin, Haolin Xiong at Rensselaer Polytechnic Institute and Yihua Zhang at Michigan State University for the help in formulating numerical experiments. We thank all anonymous reviewers for their constructive comments.

title: Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks


summaries: The paper has two main contributions:  1) It proposes a unifying framework called "Adaptive Measurements" that covers many differentially private synthetic data generation algorithms and show how these algorithms can be derived by modifying the loss function and distributional family.  2) Based on the above framework, two specific synthetic data generation algorithms called Private Entropy Projection (PEP) and Generative networks with Exponential Mechanism (GEM) have been proposed. Since PEP attempts to explicitly model the data distribution, it does not scale well to higher dimensions. GEM uses the well-known generative neural networks to overcome the above problem and can also effectively use public data for good initialization.

summaries: The authors unify several algorithms for DP synthetic data generation for query release. Using this framework they create two algorithms, private entropy projection (PEP) and generative networks with the exponential mechanism (GEM). Then they empirically evaluate their algorithms in publicly available datasets and show that their algorithms (mostly) outperform existing ones. They also show how GEM can use public data to improve its accuracy.

summaries: This paper tackles the problem of synthetic data generation for query release. First, it presents a general algorithmic framework (Adaptive measurements) for the task, and interprets a long line of prior work under this lense. At a high level, these works solve the min max problem in Equation 1.   Given this formulation, the paper proposes two algorithms, PEP and GEM. PEP selects a maximum entropy distribution to minimize the error for a given query set by solving the dual of the constrained optimization problem. They offer an iterative algorithm for this.  To avoid the exponential runtime of approaches like PEP (because they maintain a distribution over entire data domains), the paper also proposes GEM, which uses a generator network to represent this high dimensional space.  GEM can easily incorporate public data (with various missingness) by using it for pretraining.   Empirically, GEM outperforms prior work in accuracy to privacy tradeoffs on ACS and the adult datasets, and is more robust to domain shift in the public data than PMW or PEP. This gain is most pronounced when the data is high dimensional.

summaries: # Summary of contributions  The paper studies the problem of synthesizing differentially private (DP) data for query release. Here we are given a sensitive dataset $P$ together with a set $\mathcal{Q}$ of queries of interest. The goal is to generate a DP synthetic dataset $D$ so that answering the queries using $D$ gives similar answers to those of $P$; more formally, we want to minimize the maximum error across the queries, i.e. $\max_{q \in \mathcal{Q}} |q(P) - q(D)|$. Several works have proposed algorithms for this problem, including MWEM [Hardt et al., NeurIPS'12] and FEM [Vietri et al., ICML'20].  The first contribution of the paper is in observing that essentially the previously proposed algorithms all fit into a single framework which they call "Adaptive Measurements". Specifically, the algorithm proceeds in iterations and, in each iteration, it uses the exponential mechanism to select one or more queries, asks for noisy values of those queries and it then updates the current synthetic dataset $D$ by minimizing some objective (which involves the answers to the queries so far and the current guess dataset).  With the above in mind, the authors then decide a new algorithm which fits into this framework called Private Entropy Projection (PEP) algorithm. At each step, PEP tries to find the distribution $D$ with maximum entropy among those whose max error w.r.t. the noisy measurements is at most $\gamma$ for some parameter $\gamma$. The authors note that PEP also gives exponentially weighted distributions, similar to MWEM, but the weights are more elaborated. Empirically, the authors show that PEP performs better than MWEM when $\epsilon$ is sufficiently large (and performs similarly for small $\epsilon$) on reduced versions of ADULT and ACS datasets for 3-way marginal queries.  The reason a reduced version of those datasets are used is because the original datasets have high-dimension, which is infeasible for MWEM or PEP since they have to keep the entire distribution explicitly. To overcome this, the authors propose a different algorithm called GEM which instead assume that the distribution is generated to some network $G_\theta$ with parameter $\theta$ (assuming that the inputs to the network is i.i.d. Gaussian). This can help reduce the computational cost dramatically since now only the network parameters $\theta$ is needed to be maintained. Here, GEM still works in the "Adaptive Measurements" framework and the authors use gradient descent to minimize the $\ell_1$ loss w.r.t. the noisy measurements so far. Note that this might not be easily differentiable for generic queries; fortunately, for k-way marginal queries, the authors point out that they are just product of the network's outputs and as a result the gradient can be easily found.  Finally, the authors consider the setting where there is some public data which one hopes to use to improve the quality of the synthetic dataset. Previous state-of-the-art called PMW$^{Pub}$ [Liu et al., 2021] simply uses limits the distribution to only those on the _support_ of the public data and runs MWEM. This has several limitations, such as when the support of the public data is not sufficient to express the sensitive data, or when some features are missing in the public dataset. The authors show that a modified version of GEM (called GEM$^{Pub}$) is more amenable for these cases: just use the public data to find an initial generator network, and then proceed with the GEM algorithm as usual. They demonstrate that this approach indeed works well in practice: although the performances of GEM$^{Pub}$ and PMW$^{Pub}$ are similar for large & similarly-distributed public data, GEM$^{Pub}$ significantly outperforms PMW$^{Pub}$ when public data is incomplete or its support not closely resembling the sensitive data.

abstractText: We study private synthetic data generation for query release, where the goal is to construct a sanitized version of a sensitive dataset, subject to differential privacy, that approximately preserves the answers to a large collection of statistical queries. We first present an algorithmic framework that unifies a long line of iterative algorithms in the literature. Under this framework, we propose two new methods. Our first method, generative networks with the exponential mechanism (GEM), circumvents computational bottlenecks in algorithms such as MWEM by optimizing over generative models parameterized by neural networks, which capture a rich family of distributions while enabling fast gradient-based optimization. The second method, private entropy projection (PEP), can be viewed as an advanced variant of MWEM that adaptively reuses past query measurements to boost accuracy. We demonstrate that GEM and PEP empirically outperform existing algorithms. Furthermore, we show that GEM nicely incorporates prior information from public data while overcoming limitations of PMWPub, the existing state-of-the-art method that also leverages public data.

title: The U.S. census bureau adopts differential privacy

venue: In ACM International Conference on Knowledge Discovery & Data Mining,

authors:
Noga Alon
Raef Bassily
Shay Moran

title: Limits of private learning with access to public data

venue: Advances in Neural Information Processing Systems,

authors:
Sergul Aydore
William Brown
Michael Kearns
Krishnaram Kenthapadi
Luca Melis
Aaron Roth
Ankit Siva

title: Differentially private query release through adaptive projection

venue: arXiv preprint arXiv:2103.06641,

authors:
Raef Bassily
Albert Cheu
Shay Moran
Aleksandar Nikolov
Jonathan R. Ullman
Zhiwei Steven Wu

title: Private query release assisted by public data

venue: In Proceedings of the 37th International Conference on Machine Learning,

authors:
Raef Bassily
Shay Moran
Anupama Nandi

title: Learning from mixtures of private and public populations

venue: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems

authors:
Brett K Beaulieu-Jones
Zhiwei Steven Wu
Chris Williams
Ran Lee
Sanjeev P Bhavnani
James Brian Byrd
Casey S Greene

title: Privacy-preserving generative deep neural networks support clinical data sharing. Circulation: Cardiovascular Quality and Outcomes

authors:
Avrim Blum
Katrina Ligett
Aaron Roth

title: A learning theory approach to non-interactive database privacy

venue: Proceedings of the 40th Annual ACM Symposium on Theory of Computing,

authors:
Mark Bun
Thomas Steinke

title: Concentrated differential privacy: Simplifications, extensions, and lower bounds

venue: In Proceedings of the 14th Conference on Theory of Cryptography, TCC ’16-B,

authors:
Mark Bun
Jonathan Ullman
Salil Vadhan

title: Fingerprinting codes and the price of approximate differential privacy

venue: SIAM Journal on Computing,

authors:
Mark Cesar
Ryan Rogers

title: Unifying privacy loss composition for data analytics

venue: arXiv preprint arXiv:2004.07223,

authors:
Dheeru Dua
Casey Graff

title: UCI machine learning repository, 2017

venue: URL http://archive. ics.uci.edu/ml

authors:
Cynthia Dwork
Guy N. Rothblum

title: Concentrated differential privacy, 2016

authors:
Cynthia Dwork
Frank McSherry
Kobbi Nissim
Adam Smith

title: Calibrating noise to sensitivity in private data analysis

venue: In Proceedings of the 3rd Conference on Theory of Cryptography,

authors:
Cynthia Dwork
Moni Naor
Omer Reingold
Guy N. Rothblum
Salil Vadhan

title: On the complexity of differentially private data release: Efficient algorithms and hardness results

venue: In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing,

authors:
Alexander Edmonds
Aleksandar Nikolov
Jonathan Ullman

title: The power of factorization mechanisms in local and central differential privacy

venue: In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing,

authors:
Ferdinando Fioretto
Cuong Tran
Pascal Van Hentenryck

title: Decision making with differential privacy under a fairness lens

venue: arXiv preprint arXiv:2105.07513,

authors:
Marco Gaboardi
Emilio Jesús Gallego Arias
Justin Hsu
Aaron Roth
Zhiwei Steven Wu

title: Dual query: Practical private query release for high dimensional data

venue: In International Conference on Machine Learning,

authors:
Anupam Gupta
Aaron Roth
Jonathan Ullman

title: Iterative constructions and private data release

venue: In Proceedings of the 9th International Conference on Theory of Cryptography, TCC’12,

authors:
Moritz Hardt
Guy N Rothblum

title: A multiplicative weights mechanism for privacy-preserving data analysis

venue: IEEE 51st Annual Symposium on Foundations of Computer Science,

authors:
Moritz Hardt
Katrina Ligett
Frank Mcsherry

title: A simple and practical algorithm for differentially private data release

title: Census bureau continues to boost data safeguards

venue: U.S. Census: Random Samplings Blog. URL https://www.census.gov/newsroom/blogs/random-samplings/2019/07/ boost-safeguards.html

title: Consistency with external knowledge: The topdown algorithm, 2019

authors:
Chao Li
Gerome Miklau
Michael Hay
Andrew Mcgregor
Vibhor Rastogi

title: The matrix mechanism: Optimizing linear counting queries under differential privacy

venue: The VLDB Journal,

authors:
Terrance Liu
Giuseppe Vietri
Thomas Steinke
Jonathan Ullman
Zhiwei Steven Wu

title: Leveraging public data for practical private query release

venue: arXiv preprint arXiv:2102.08598,

authors:
Andre Martins
Ramon Astudillo

title: From softmax to sparsemax: A sparse model of attention and multi-label classification

venue: In International conference on machine learning,

authors:
Ryan McKenna
Gerome Miklau
Michael Hay
Ashwin Machanavajjhala

title: Optimizing error of high-dimensional statistical queries under differential privacy

venue: Proc. VLDB Endow.,

authors:
Ryan McKenna
Daniel Sheldon
Gerome Miklau

title: Graphical-model based estimation and inference for differential privacy

authors:
Marcel Neunhoeffer
Steven Wu
Cynthia Dwork

title: Private post-{gan} boosting

venue: In International Conference on Learning Representations,

authors:
Aleksandar Nikolov
Kunal Talwar
Li Zhang

title: The geometry of differential privacy: The sparse and approximate cases

venue: In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing,

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga
Alban Desmaison
Andreas Kopf
Edward Yang
Zachary DeVito
Martin Raison
Alykhan Tejani
Sasank Chilamkurthy
Benoit Steiner
Lu Fang
Junjie Bai
Soumith Chintala

title: Pytorch: An imperative style, highperformance deep learning library

venue: Advances in Neural Information Processing Systems

authors:
Aaron Roth
Tim Roughgarden

title: Interactive privacy via the median mechanism

venue: Proceedings of the 42nd ACM Symposium on Theory of Computing,

title: Ipums usa: Version 10.0

title: Answering n2+o(1) counting queries with differential privacy is hard

title: Private multiplicative weights beyond linear queries

venue: In Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems,

authors:
Jonathan Ullman
Salil Vadhan

title: Pcps and the hardness of generating private synthetic data

venue: In Theory of Cryptography Conference,

venue: In Yuval Ishai, editor, Theory of Cryptography,

authors:
Giuseppe Vietri
Grace Tian
Mark Bun
Thomas Steinke
Steven Wu

title: New oracle-efficient algorithms for private synthetic data release

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine learning,

authors:
Liyang Xie
Kaixiang Lin
Shu Wang
Fei Wang
Jiayu Zhou

title: Differentially private generative adversarial network

authors:
Yasin Yazıcı
Chuan-Sheng Foo
Stefan Winkler
Kim-Hui Yap
Georgios Piliouras
Vijay Chandrasekhar

title: The unusual effectiveness of averaging in gan training

venue: arXiv preprint arXiv:1806.04498,

authors:
Jinsung Yoon
James Jordon
Mihaela van der Schaar

title: PATE-GAN: Generating synthetic data with differential privacy guarantees

heading: 1 Introduction

text:
As the collection and analyses of sensitive data become more prevalent, there is an increasing need to protect individuals’ private information. Differential privacy [15] is a rigorous and meaningful criterion for privacy preservation that enables quantifiable trade-offs between privacy and accuracy. In recent years, there has been a wave of practical deployments of differential privacy across organizations such as Google, Apple, and most notably, the U.S. Census Bureau [3].
In this paper, we study the problem of differentially private query release: given a large collection of statistical queries, the goal is to release approximate answers subject to the constraint of differential privacy. Query release has been one of the most fundamental and practically relevant problems in differential privacy. For example, the release of summary data from the 2020 U.S. Decennial Census can be framed as a query release problem. We focus on the approach of synthetic data generation—that is, generate a privacy-preserving "fake" dataset, or more generally a representation of a probability distribution, that approximates all statistical queries of interest. Compared to simple Gaussian or Laplace mechanisms that perturb the answers directly, synthetic data methods can provably answer an exponentially larger collection of queries with non-trivial accuracy. However, their statistical advantage also comes with a computational cost. Prior work has shown that achieving better accuracy than simple Gaussian perturbation is intractable in the worst case even for the simple query class of 2-way marginals that release the marginal distributions for all pairs of attributes [38].
∗First two authors contributed equally.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Despite its worst-case intractability, there has been a recent surge of work on practical algorithms for generating private synthetic data. Even though they differ substantially in details, these algorithms share the same iterative form that maintains and improves a probability distribution over the data domain: identifying a small collection of high-error queries each round and updating the distribution to reduce these errors. Inspired by this observation, we present a unifying algorithmic framework that captures these methods. Furthermore, we develop two new algorithms, GEM and PEP, and extend the former to the setting in which public data is available. We summarize our contributions below:
Unifying algorithmic framework. We provide a framework that captures existing iterative algorithms and their variations. At a high level, algorithms under this framework maintain a probability distribution over the data domain and improve it over rounds by optimizing a given loss function. We therefore argue that under this framework, the optimization procedures of each method can be reduced to what loss function is minimized and how its distributional family is parameterized. For example, we can recover existing methods by specifying choices of loss functions—we rederive MWEM [21] using an entropy-regularized linear loss, FEM [40] using a linear loss with a linear perturbation, and DualQuery [19] with a simple linear loss. Lastly, our framework lends itself naturally to a softmax variant of RAP [5], which we show outperforms RAP itself.2
Generative networks with the exponential mechanism (GEM). GEM is inspired by MWEM, which attains worst-case theoretical guarantees that are nearly information-theoretically optimal [11]. However, MWEM maintains a joint distribution over the data domain, resulting in a runtime that is exponential in the dimension of the data. GEM avoids this fundamental issue by optimizing the absolute loss over a set of generative models parameterized by neural networks. We empirically demonstrate that in the high-dimensional regime, GEM outperforms all competing methods.
Private Entropy Projection (PEP). The second algorithm we propose is PEP, which can be viewed as a more advanced version of MWEM with an adaptive and optimized learning rate. We show that PEP minimizes a regularized exponential loss function that can be efficiently optimized using an iterative procedure. Moreover, we show that PEP monotonically decreases the error over rounds and empirically find that it achieves higher accuracy and faster convergence than MWEM.
Incorporating public data. Finally, we consider extensions of our methods that incorporate prior information in publicly available datasets (e.g., previous data releases from the American Community Survey (ACS) prior to their differential privacy deployment). While Liu et al. [26] has established PMWPub as a state-of-the-art method for incorporating public data into private query release, we discuss how limitations of their algorithm prevent PMWPub from effectively using certain public datasets. We then demonstrate empirically that GEM circumvents such issues via simple pretraining, achieving max errors on 2018 ACS data for Pennsylvania (at ε = 1) 9.23x lower than PMWPub when using 2018 ACS data for California as the public dataset.

heading: 1.1 Related work

text:
Beginning with the seminal work of Blum et al. [9], a long line of theoretical work has studied private synthetic data for query release [33, 21, 22, 20]. While this body of work establishes optimal statistical rates for this problem, their proposed algorithms, including MWEM [22], typically have running time exponential in the dimension of the data. While the worst-case exponential running time is necessary (given known lower bounds [16, 36, 39]), a recent line of work on practical algorithms leverage optimization heuristics to tackle such computational bottlenecks [19, 40, 5]. In particular, DualQuery [19] and FEM [40] leverage integer program solvers to solve their NP-hard subroutines, and RAP [5] uses gradient-based methods to solve its projection step. In Section 3, we demonstrate how these algorithms can be viewed as special cases of our algorithmic framework. Our work also relates to a growing line of work that use public data for private data analyses [6, 4, 7]. For query release, our algorithm, GEM, improves upon the state-of-the-art method, PMWPub [26], which is more limited in the range of public datasets it can utilize. Finally, our method GEM is related to a line
2We note that Aydore et al. [5] have since updated the original version (https://arxiv.org/pdf/2103. 06641v1.pdf) of their work to include a modified version of RAP that leverages SparseMax [27], similar to way in which the softmax function is applied in our proposed baseline, RAPsoftmax.
of work on differentially private GANs [8, 44, 30, 42]. However, these methods focus on generating synthetic data for simple downstream machine learning tasks rather than for query release.
Beyond synthetic data, a line of work on query release studies "data-independent" mechanisms (a term formulated in Edmonds et al. [17]) that perturb the query answers with noise drawn from a data-independent distribution (that may depend on the query class). This class of algorithms includes the matrix mechanism [25], the high-dimensional matrix mechanism (HDMM) [28], the projection mechanism [31], and more generally the class of factorization mechanisms [17]. In addition, McKenna et al. [29] provide an algorithm that can further reduce query error by learning a probabilistic graphical model based on the noisy query answers released by privacy mechanisms.

heading: 2 Preliminaries

text:
Let X denote a finite d-dimensional data domain (e.g., X = {0, 1}d). Lete U be the uniform distribution over the domain X . Throughout this work, we assume a private dataset P that contains the data of n individuals. For any x ∈ X , we represent P (x) as the normalized frequency of x in dataset P such that ∑ x∈X P (x) = 1. One can think of a dataset P either as a multi-set of items from X or as a distribution over X . We consider the problem of accurately answering an extensive collection of linear statistical queries (also known as counting queries) about a dataset. Given a finite set of queries Q, our goal is to find a synthetic dataset D such that the maximum error over all queries in Q, defined as maxq∈Q |q(P )− q(D)|, is as small as possible. For example, one may query a dataset by asking the following: how many people in a dataset have brown eyes? More formally, a statistical linear query qφ is defined by a predicate function φ : X → {0, 1}, as qφ(D) = ∑ x∈X φ(x)D(x) for any normalized dataset D. Below, we define an important, and general class of linear statistical queries called k-way marginals. Definition 1 (k-way marginal). Let the data universe with d categorical attributes be X = (X1 × . . .×Xd), where each Xi is the discrete domain of the ith attribute Ai. A k-way marginal query is defined by a subset S ⊆ [d] of k features (i.e., |S| = k) plus a target value y ∈ ∏ i∈S Xi for each feature in S. Then the marginal query φS,y(x) is given by:
φS,y(x) = ∏ i∈S 1 (xi = yi)
where xi ∈ Xi means the i-th attribute of record x ∈ X . Each marginal has a total of ∏k i=1 |Xi| queries, and we define a workload as a set of marginal queries.
We consider algorithms that input a dataset P and produce randomized outputs that depend on the data. The output of a randomized mechanismM : X ∗ → R is a privacy preserving computation if it satisfies differential privacy (DP) [15]. We say that two datasets are neighboring if they differ in at most the data of one individual. Definition 2 (Differential privacy [15]). A randomized mechanism M : Xn → R is (ε, δ)differentially privacy, if for all neighboring datasets P, P ′ (i.e., differing on a single person), and all measurable subsets S ⊆ R we have:
Pr [M(P ) ∈ S] ≤ eεPr [M(P ′) ∈ S] + δ
Finally, a related notion of privacy is called concentrated differential privacy (zCDP) [14, 10], which enables cleaner composition analyses for privacy. Definition 3 (Concentrated DP, Dwork and Rothblum [14], Bun and Steinke [10]). A randomized mechanismM : Xn → R is 12 ε̃
2-CDP, if for all neighboring datasets P, P ′ (i.e., differing on a single person), and for all α ∈ (1,∞),
Rα (M(P ) ‖ M(P ′)) ≤ 1
2 ε̃2α
where Rα (M(P ) ‖ M(P ′)) is the Rényi divergence between the distributionsM(P ) andM(P ′).

heading: 3 A Unifying Framework for Private Query Release

text:
In this work, we consider the problem of finding a distribution in some family of distributions D that achieves low error on all queries. More formally, given a private dataset P and a query set Q, we
solve an optimization problem of the form:
min D∈D max q∈Q |q(P )− q(D)| (1)
In Algorithm 1, we introduce Adaptive Measurements, which serves as a general framework for solving (1). At each round t, the framework uses a private selection mechanism to choose k queries Q̃t = {q̃t,1, . . . , q̃t,k} with higher error from the set Q. It then obtains noisy measurements for the queries, which we denote by Ãt = {ãt,1, . . . , ãt,k}, where ãt,i = q̃t,i + zt,i and zt,i is random Laplace or Gaussian noise. Finally, it updates its approximating distribution Dt, subject to a loss function L that depends on Q̃1:t = ⋃t i=1 Q̃i and Ã1:t = ⋃t i=1 Ãi. We note that L serves as a surrogate problem to (1) in the sense that the solution of minD∈D L(D) is an approximate solution for (1). We list below the corresponding loss functions for various algorithms in the literature of differentially private synthetic data. (We defer the derivation of these loss functions to the appendix.)
MWEM from Hardt et al. [22] MWEM solves an entropy regularized minimization problem:
LMWEM(D, Q̃1:t, Ã1:t) = t∑ i=1 ∑ x∈X D(x)q̃i(x) (ãi − q̃i(Di−1)) + ∑ x∈X D(x) logD(x)
We note that PMWPub [26] optimizes the same problem but restrictsD to distributions over the public data domain while initializing D0 to be the public data distribution.
DualQuery from Gaboardi et al. [19] At each round t, DualQuery samples s queries (Q̃t = {q̃t,1, . . . q̃t,s}) from Qt and outputs Dt that minimizes the the following loss function:
LDualQuery(D, Q̃t) = s∑ i=1 q̃t,i(D)
FEM from Vietri et al. [40] The algorithm FEM employs a follow the perturbed leader strategy, where on round t, FEM chooses the next distribution by solving:
LFEM(D, Q̃1:t) = t∑ i=1 q̃t(D) + Ex∼D,η∼Exp(σ)d (〈x, η〉)
RAPsoftmax adapted from Aydore et al. [5] We note that RAP follows the basic structure of Adaptive Measurements, where at iteration t, RAP solves the following optimization problem:
LRAP(D, Q̃1:t, Ã1:t) = ∑ i,j (q̃i,j(D)− ãi,j)2
However, rather than outputting a dataset that can be expressed as some distribution over X , RAP projects the noisy measurements onto a continuous relaxation of the binarized feature space of X , outputting D ∈ [−1, 1]n′×d (where n′ is an additional parameter). Therefore to adapt RAP to Adaptive Measurements, we propose a new baseline algorithm that applies the softmax function instead of clipping each dimension of D to be between −1 and 1. For more details, refer to Section 4 and Appendix B, where describe how softmax is applied in GEM in the same way. With this slight modification, this algorithm, which we denote as RAPsoftmax, fits nicely into the
Adaptive Measurements framework in which we output a synthetic dataset drawn from some probabilistic family of distributions D = { σ(M)|M ∈ Rn′×d } .
Algorithm 1: Adaptive Measurements Input: Private dataset P with n records, set of linear queries Q, distributional family D, loss
functions L, number of iterations T Initialize distribution D0 ∈ D for t = 1, . . . , T do
Sample: For i ∈ [k], choose q̃t,i using a differentially private selection mechanism. Measure: For i ∈ [k], let ãt,i = q̃t,i(P ) + zt,i where z is Gaussian or Laplace noise Update: Let Q̃t = {q̃t,1, . . . , q̃t,k} and Ãt = {ãt,1, . . . , ãt,k}. Update distribution D:
Dt ← arg minD∈D L ( Dt−1, Q̃1:t, Ã1:t ) where Q̃1:t = ⋃t i=1 Q̃i and Ã1:t = ⋃t i=1 Ãi.
end Output H ( {Dt}Tt=0 ) where H is some function over all distributions Dt (such as the average)
Finally, we note that in addition to the loss function L, a key component that differentiates algorithms under this framework is the distributional family D that the output of each algorithm belongs to. We refer readers to Appendix A.2, where we describe in more detail how existing algorithms fit into our general framework under different choices of L and D.

heading: 3.1 Privacy analysis

text: We present the privacy analysis of the Adaptive Measurements framework while assuming that the exponential and Gaussian mechanism are used for the private sample and noisy measure steps respectively. More specifically, suppose that we (1) sample k queries using the exponential mechanism with the score function:

heading: Pr [q̃t,i = q] ∝ exp (αε0n|q(P )− q(Dt−1)|)

text:
and (2) measure the answer to each query by adding Gaussian noise
zt,i ∼ N ( 0, ( 1
n(1− α)ε0
)2) .
Letting ε0 = √
2ρ
T(α2+(1−α)2) and α ∈ (0, 1) be a privacy allocation hyperparameter (higher values
of α allocate more privacy budget to the exponential mechanism), we present the following theorem: Theorem 1. When run with privacy parameter ρ, Adaptive Measurements satisfies ρ-zCDP. Moreover for all δ > 0, Adaptive Measurements satisfies(ε(δ), δ)-differential privacy, where ε(δ) ≤ ρ+ 2 √ ρ log(1/δ).
Proof sketch. Fix T ≥ 1 and α ∈ (0, 1). (i) At each iteration t ∈ [T ], Adaptive Measurements runs the exponential mechanism k times with parameter 2αε0, which satisfies k8 (2αε0) 2 = k2 (αε0)
2- zCDP [12], and the Gaussian mechanism k times with parameter (1 − α)ε0, which satisfies k 2 [(1− α)ε0]
2-zCDP [10]. (ii) using the composition theorem for concentrated differential privacy [10], Adaptive Measurements satisfies kT2 [ α2 + (1− α)2 ] ε20-zCDP after T iterations. (iii) Set-
ting ε0 = √
2ρ
kT(α2+(1−α)2) , we conclude that Adaptive Measurements satisfies ρ-zCDP, which in turn implies ( ρ+ 2 √ ρ log(1/δ), δ ) -differential privacy for all δ > 0 [10].

heading: 4 Overcoming Computational Intractability with Generative Networks

text:
We introduce GEM (Generative Networks with the Exponential Mechanism), which optimizes over past queries to improve accuracy by training a generator network Gθ to implicitly learn a distribution
of the data domain, where Gθ can be any neural network parametrized by weights θ. As a result, our method GEM can compactly represent a distribution for any data domain while enabling fast, gradient-based optimization via auto-differentiation frameworks [32, 2].
Concretely, Gθ takes random Gaussian noise vectors z as input and outputs a representation Gθ(z) of a product distribution over the data domain. Specifically, this product distribution representation takes the form of a d′-dimensional probability vector Gθ(z) ∈ [0, 1]d ′ , where d′ is the dimension of the data in one-hot encoding and each coordinate Gθ(z)j corresponds to the marginal probability of a categorical variable taking on a specific value. To obtain this probability vector, we choose softmax as the activation function for the output layer in Gθ. Therefore, for any fixed weights θ, Gθ defines a distribution over X through the generative process that draws a random z ∼ N (0, σ2I) and then outputs random x drawn from the product distribution Gθ(z). We will denote this distribution as Pθ.
To define the loss function for GEM, we require that it be differentiable so that we can use gradientbased methods to optimize Gθ. Therefore, we need to obtain a differentiable variant of q. Recall first that a query is defined by some predicate function φ : X → {0, 1} over the data domain X that evaluates over a single row x ∈ X . We observe then that one can extend any statistical query q to be a function that maps a distribution Pθ over X to a value in [0, 1]:
q(Pθ) = Ex∼Pθ [φ(x)] = ∑ x∈X φ(x)Pθ(x) (2)
Note that any statistical query q is then differentiable w.r.t. θ:
∇θ [q(Pθ)] = ∑ x∈X ∇θPθ(x)φ(x) = Ez∼N(0,Ik) ∑ x∈X φ(x)∇θ 1 k k∑ i d′∏ j=1 (Gθ(zi)j) xj  and we can compute stochastic gradients of q w.r.t. θ with random noise samples z. This also allows us to derive a differentiable loss function in the Adaptive Measurements framework. In each round t, given a set of selected queries Q̃1:t and their noisy measurements Ã1:t, GEM minimizes the following `1-loss:
LGEM ( θ, Q̃1:t, Ã1:t ) = t∑ i=1 |q̃i(Pθ)− ãi| . (3)
where q̃i ∈ Q̃1:t and ãi ∈ Ã1:t.
In general, we can optimize LGEM by running stochastic (sub)-gradient descent. However, we remark that gradient computation can be expensive since obtaining a low-variance gradient estimate often requires calculating∇θPθ(x) for a large number of x. In Appendix B, we include the stochastic gradient derivation for GEM and briefly discuss how an alternative approach from reinforcement learning.
For many query classes, however, there exists some closed-form, differentiable function surrogate to (3) that evaluates q(Gθ(z)) directly without operating over all x ∈ X . Concretely, we say that for certain query classes, there exists some representation fq : ∆(X )→ [0, 1] for q that operates in the probability space of X and is also differentiable. In this work, we implement GEM to answer k-way marginal queries, which have been one of the most important query classes for the query release literature [22, 40, 19, 26] and provides a differentiable form when extended to be a function over distributions. In particular, we show that k-way marginals can be rewritten as product queries (which are differentiable). Definition 4 (Product query). Let p ∈ Rd′ be a representation of a dataset (in the one-hot encoded space), and let S ⊆ [d′] be some subset of dimensions of p. Then we define a product query fS as
fS(p) = ∏ j∈S pj (4)
A k-way marginal query φ can then be rewritten as (4), where p = Gθ(z) and S is the subset of dimensions corresponding to the attributes A and target values y that are specified by φ (Definition 1). Thus, we can write any marginal query as ∏ j∈S Gθ(z)j , which is differentiable w.r.t. Gθ (and therefore differentiable w.r.t weights θ by chain rule). Gradient-based optimization techniques can then be used to solve (3); the exact details of our implementation can be found in Appendix B.

heading: 5 Maximum-Entropy Projection Algorithm

text:
Next, we propose PEP (Private Entropy Projection) under the framework Adaptive Measurements. Similar to MWEM, PEP employs the maximum entropy principle, which also recovers a synthetic data distribution in the exponential family. However, since PEP adaptively assigns weights to past queries and measurements, it has faster convergence and better accuracy than MWEM. PEP’s loss function in Adaptive Measurements can be derived through a constrained maximum entropy optimization problem. At each round t, given a set of selected queries Q̃1:t and their noisy measurements Ã1:t, the constrained optimization requires that the synthetic data Dt satisfies γ-accuracy with respect to the noisy measurements for all the selected queries in Q̃1:t. Then among the set of feasible distributions that satisfy accuracy constraints, PEP selects the distribution with maximum entropy, leading to the following regularized constraint optimization problem:
minimize: ∑ x∈X D(x) log (D(x)) (5)
subject to: ∀i∈[t] |ãi − q̃i(D)| ≤ γ, ∑ x∈X D(x) = 1
We can ignore the constraint that ∀x∈XD(x) ≥ 0, because it will be satisfied automatically. The solution of (5) is an exponentially weighted distribution parameterized by the dual variables λ1, . . . , λt corresponding to the t constraints. Therefore, if we solve the dual problem of (5) in terms of the dual variables λ1, . . . , λt, then the distribution that minimizes (5) is given by Dt(x) ∝ exp (∑t i=1 λiq̃i(x) ) . (Note that MWEM simply sets λi = ãi− q̃i(Dt−1) without any optimization.) Given that the set of distributions is parameterized by the variables λ1, . . . , λt, the constrained optimization is then equivalent to minimizing the following exponential loss function:
LPEP ( λ, Q̃1:t, Ã1:t ) = log (∑ x∈X exp ( t∑ i=1 λi (q̃i(x)− ãi) )) + γ‖λ‖1
Since PEP requires solving this constrained optimization problem on each round, we give an efficient iterative algorithm for solving (5). We defer the details of the algorithm to the Appendix C.
6 Extending to the public-data-assisted setting
Incorporating prior information from public data has shown to be a promising avenue for private query release [6, 26]. Therefore, we extend GEM to the problem of public-data-assisted private (PAP) query release [6] in which differentially private algorithms have access to public data. Concretely, we adapt GEM to utilize public data by initializing D0 to a distribution over the public dataset. However, because in GEM, we implicitly model any given distribution using a generator G, we must first train without privacy (i.e., without using the exponential and Gaussian mechanisms) a generator Gpub, to minimize the `1-error over some set of queries Q̂. Note that in most cases, we can simply let Q̂ = Q where Q is the collection of statistical queries we wish to answer privately. GEMPub then initializes G0 to Gpub and proceeds with the rest of the GEM algorithm.
6.1 Overcoming limitations of PMWPub.
We describe the limitations of PMWPub by providing two example categories of public data that it fails to use effectively. We then describe how GEMPub overcomes such limitations in both scenarios.
Public data with insufficient support. We first discuss the case in which the public dataset has an insufficient support, which in this context means the support has high best-mixture-error [26]. Given some support S ⊆ X , the best-mixture-error can be defined as
min µ∈∆(S) max q∈Q ∣∣∣∣∣q (D)−∑ x∈S µxq(x) ∣∣∣∣∣
where µ ∈ ∆(S) is a distribution over the set S with µ(x) ≥ 0 for all x ∈ S and ∑ x∈S µ(x) = 1.
In other words, the best-mixture-error approximates the lowest possible max error that can be achieved by reweighting some support, which in this case means PMWPub cannot achieve max errors lower that this value. While Liu et al. [26] offer a solution for filtering out poor public datasets ahead of time using a small portion of the privacy budget, PMWPub cannot be run effectively if no other suitable public datasets exist. GEMPub however avoids this issue altogether because unlike MWEM (and therefore PMWPub), which cannot be run without restricting the size of D, GEMPub can utilize public data without restricting the distributional family it can represent (since both GEM and GEMPub compactly parametrize any distribution using a neural network).
Public data with incomplete data domains. Next we consider the case in which the public dataset only has data for a subset of the attributes found in the private dataset. We note that as presented in Liu et al. [26], PMWPub cannot handle this scenario. One possible solution is to augment the public data distribution by assuming a uniform distribution over all remaining attributes missing in the public dataset. However, while this option may work in cases where only a few attributes are missing, the missing support grows exponentially in the dimension of the missing attributes. In contrast, GEMPub can still make use of such public data. In particular, we can pretrain a generator G on queries over just the attributes found in the public dataset. Again, GEMPub avoids the computational intractability of PMWPub in this setting since it parametrizes its output distribution with G.

heading: 7 Empirical Evaluation

text:
In this section, we empirically evaluate GEM and PEP against baseline methods on the ACS [34] and ADULT [13] datasets in both the standard3 and public-data-assisted settings.
Data. To evaluate our methods, we construct public and private datasets from the ACS and ADULT datasets by following the preprocessing steps outlined in Liu et al. [26]. For the ACS, we use 2018 data for the state of Pennsylvania (PA-18) as the private dataset. For the public dataset, we select 2010 data for Pennsylvania (PA-10) and 2018 data for California (CA-18). In our experiments on the ADULT dataset, private and public datasets are sampled from the complete dataset (using a 90-10 split). In addition, we construct low-dimensional versions of both datasets, which we denote as ACS (reduced) and ADULT (reduced), in order to evaluate PEP and MWEM.
Baselines. We compare our algorithms to the strongest performing baselines in both low and highdimensional settings, presenting results for MWEM, DualQuery, and RAPsoftmax in the standard setting45 and PMWPub in the public-data-assisted setting.
Experimental details. To present a fair comparison, we implement all algorithms using the privacy mechanisms and zCDP composition described in Section 3.1. To implement GEM for k-way marginals, we select a simple multilayer perceptron for Gθ. Our implementations of MWEM and PMWPub output the last iterate Dt instead of the average and apply the multiplicative weights update rule using past queries according to the pseudocode described in Liu et al. [26]. We report the best performing 5-run average across hyperparameter choices (see Tables 1, 2, 3, 4, and 5 in Appendix D.1) for each algorithm.

heading: 7.1 Results

text:
Standard setting. In Figure 1, we observe that in low-dimensional settings, PEP and GEM consistently achieve strong performance compared to the baseline methods. While MWEM and PEP are similar in nature, PEP outperforms MWEM on both datasets across all privacy budgets except
3We refer readers to Appendix D.7 where we include an empirical evaluation on versions of the ADULT and LOANS [13] datasets used in other related private query release works [28, 40, 5].
4Having consulted McKenna et al. [28], we concluded that running HDMM is infeasible for our experiments, since it generally cannot handle a data domain with size larger than 109. See Appendix D.5 for more details.
5Because RAP performs poorly relative to the other methods in our experiments, plotting its performance would make visually comparing the other methods difficult. Thus, we exclude it from Figure 1 and refer readers to Appendix D.3, where we present failure cases for RAP and compare it to RAPsoftmax.
ε ∈ {0.1, 0.15} on ACS (reduced), where the two algorithms perform similarly. In addition, both PEP and GEM outperform RAPsoftmax. Moving on to the more realistic setting in which the data dimension is high, we again observe that GEM outperforms RAPsoftmax on both datasets.
Public-data-assisted setting. To evaluate the query release algorithm in the public-data-assisted setting, we present the three following categories of public data:
Public data with sufficient support. To evaluate our methods when the public dataset for ACS PA-18 has low best-mixture-error, we consider the public dataset ACS PA-10. We observe in Figure 1 that GEMPub performs similarly to PMWPub, with both outperforming GEM (without public data).
Public data with insufficient support. In Figure 2a, we present CA-18 as an example of this failure case in which the best-mixture-error is over 10%, and so for any privacy budget, PMWPub cannot achieve max errors lower that this value. However, for the reasons described in Section 6.1, GEMPub is not restricted by best-mixture-error and significantly outperforms GEM (without public data) when using either public dataset.
Public data with incomplete data domains. To simulate this setting, we construct a reduced version of the public dataset in which we keep only 7 out of 13 attributes in ADULT. In this case, 6 attributes are missing, and so assuming a uniform distribution over the missing attributes would cause the dimension of the approximating distribution D to grow from≈ 4.4×103 to a≈ 3.2×109. PMWPub would be computationally infeasible to run in this case. To evaluate GEMPub, we pretrain the generator G using all 3-way marginals on both the complete and reduced versions of the public
dataset and then finetune on the private dataset (we denote these two finetuned networks as GEMPub and GEMPub (reduced) respectively). We present results in Figure 2b. Given that the public and private datasets are sampled from the same distribution, GEMPub unsurprisingly performs extremely well. However, despite only being pretrained on a small fraction of all 3-way marginal queries (≈ 20k out 334k), GEMPub (reduced) is still able to improve upon the performance of GEM and achieve lower max error for all privacy budgets.

heading: 8 Conclusion

text:
In this work, we present a framework that unifies a long line of iterative private query release algorithms by reducing each method to a choice of some distributional family D and loss function L. We then develop two new algorithms, PEP and GEM, that outperform existing query release algorithms. In particular, we empirically validate that GEM performs very strongly in high dimensional settings (both with and without public data). We note that we chose a rather simple neural network architecture for GEM, and so for future work, we hope to develop architectures more tailored to our problem. Furthermore, we hope to extend our algorithms to other query classes, including mixed query classes and convex minimization problems [37].
Limitations. While our empirical study is structured based on past work in the literature, real-world deployment of differential privacy may be more nuanced. For example, though GEM achieves strong performance on the ACS dataset in our experiments, we (and possibly the U.S. Census Bureau itself) do not know yet what the end goals of a differentially private ACS release should be. Given different constraints or evaluation metrics, it is possible for another technique to be more suitable.
Broader impacts. We note that a possible consequence of privacy preserving methods is their potential to bring about unfair outcomes. Fioretto et al. [18], for example, show that decisions based on DP analyses may disproportionately impact certain groups. Because the U.S. Census Bureau has plans to adopt differential privacy for ACS releases after 2025 [23], the ACS dataset serves as the main test bed for our algorithms. We believe it is important to ensure that fairness is preserved for downstream tasks that use DP synthetic dataset, since the ACS provides statistics that are critical to many important decision processes (e.g., Title I grant allocations [1]).

heading: Acknowledgments

text: ZSW is supported by NSF grant SCC-1952085, Carnegie Mellon CyLab’s Secure and Private IoT Initiative, and a Google Faculty Research Award.

title: Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods