On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
Authors: Sitan Chen
Xiaoxiao Li
Zhao Song
Danyang Zhuo
Venue: ICLR 2021 Poster (2021)
Keywords: Distributed learning
InstaHide
phase retrieval
matrix factorization

Abstract: In this work, we examine the security of InstaHide, a scheme recently proposed by \cite{hsla20} for preserving the security of private datasets in the context of distributed learning. To generate a synthetic training example to be shared among the distributed learners, InstaHide takes a convex combination of private feature vectors and randomly flips the sign of each entry of the resulting vector with probability 1/2. A salient question is whether this scheme is secure in any provable sense, perhaps under a plausible complexity-theoretic assumption. 

The answer to this turns out to be quite subtle and closely related to the average-case complexity of a multi-task, missing-data version of the classic problem of phase retrieval that is interesting in its own right. Motivated by this connection, under the standard distributional assumption that the public/private feature vectors are isotropic Gaussian, we design an algorithm that can actually recover a private vector using only the public vectors and a sequence of synthetic vectors generated by InstaHide.

Published as a conference paper at ICLR 2021
ON INSTAHIDE, PHASE RETRIEVAL, AND SPARSE MA- TRIX FACTORIZATION
Sitan Chen
Xiaoxiao Li Princeton Universtiy
MIT
sitancémit.edu.
xiacxi ao. 110 wwwalaaaaa.... yale edd
Zhao Song
Danyang Zhuo
Columbia University, Princeton University / IAS magic. linuxkde@gmanl com.
Duke University
danyangecs duke. edu.
ABSTRACT
In this work, we examine the security of InstaHide, scheme recently proposed by Huang et al. (2020b) for preserving the security of private datasets in the context of distributed learning. To generate a synthetic training example be shared among the distributed learners, InstaHide takes a convex combination of private feature vectors and randomly flips the sign of each entry of the resulting vector with probability 1/2. A salient question is whether this scheme is secure in any provable sense, perhaps under a plausible complexity-theoretic assumption.
The answer to this turns out be quite subtle and closely related to the average- case complexity of a multi-task, missing-daid data version of the classic problem phase retrieval that is interesting in its own right. Motivated by this connection, under the standard distributional assumption that the public/private feature vectors are isotropic Gaussian, we design an algorithm that can actually recover private vector using only the public vectors and sequence of synthetic vectors generated by InstaHide.
INTRODUCTION
In distributed learning, where decentralized parties each possess some private local data and work together to train global model, a central challenge is to ensure that the security of any individ- ual party's local data is not compromised. Huang et al. (2020b) recently proposed an interesting approach called InstaHide for this problem. At high level, InstaHide is method for aggregating local data into synthetic data that can hopefully preserve the privacy of the local datasets and be used train good models.
Informally, given a collection of public feature vectors (e.g. a publicly available dataset like Ima- geNet Deng al. (2009)) and a collection of private feature vectors (e.g. the union of all of the private datasets among learners), InstaHide produces a synthetic feature vector as follows. Let inte- gers kpub. kpriv be sparsity parameters.
1. Form random convex combination of lipub public and kpriv private vectors.
2. Multiply every coordinate of the resulting vector by an independent random sign in {+11. and define this to be the synthetic feature vector.
The hope is that by removing any sign information from the vector obtained in Step Step makes it difficult to discern which public and private vectors were selected in Step 1. Strikingly, Huang al. (2020b) demonstrated on real-world datasets that if one trains a ResNet-18
NASNet on
"This work was supported in part by NSF CAREER Award CCF-114326,, NSF Large CCF-1565235 and Ankur Moitra's ONR Young Investigator Award.

---

Published as a conference paper at ICLR 2021
dataset consisting of synthetic vectors generated in this fashion, one can still get good test accuracy on the underlying private dataset for modest sparsity parameters (e.g. kppb = Kpriv = 2).
The two outstanding theoretical challenges that InstaHide poses understanding:
Utility:
What property, either of neural networks or of real-world distributions, lets one tolerate this kind of covariate shift between the synthetic and original datasets?
Security: Can one rigorously formulate a refutable security claim for InstaHide, under a plausible average-case complexity-theorce -thooretic assumption?
In this paper we consider the latter question. One informal security claim implicit in Huang et al. (2020b) that given a synthetic dataset of a certain size, no efficient algorithm can recover a private image within certain level of accuracy (see Problem 1 for formal statement of this recovery question). On the one hand, is a worthwhile topic of debate whether this a satisfactory guarantee from security standpoint. On the other, even this kind of claim is quite delicate pin down formally, in part because it seems impossible for such a claim to hold for arbitrary private datasets.
Known Attacks and the Importance of Distributional Assumptions If the private and public datasets consisted of natural images, for example, then attacks are known Jagielski (2020); Carlini et al. (2020). At a high level, the attack of Jagielski (2020) crucially leverages local Lipschitz- ness properties of natural images and shows that when Apriv + kpub = 2, even a single synthetic image can reveal significant information. The very recent attack of Carlini et al. (2020), which was independent of the present work and appeared a month after this submission appeared online, is more sophisticated and bears interesting similarities to the algorithms we consider. We defer a detailed discussion of these similarities to Appendix in the supplement.
While the original InstaHide paper Huang et al. (2020b) focused on image data, their general ap- proach has the potential to be applicable to other forms of real-valued data, and it is an interesting mathematical question whether the above attacks remain viable. For instance, for distributions over private vectors where individual features are nearly independent, one cannot hope to leverage the kinds of local Lipschitz-ness properties that the attack of Jagielski (2020) exploits. Additionally, if the individual features are identically distributed, then it is information theoretically impossible to discern anything from just single synthetic vector. For instance, if a synthetic vector it is given by the entrywise absolute value of 2 21 + 2 for private vectors U1 U2, then an equally plausible pair of private vectors generating would be v1 v/ given by swapping the i-th entry of 01 with that of 02 for any collection of indices E [d]. In other words, there are 2d pairs of private vectors which are equally likely under the Gaussian measure and give rise to the exact same synthetic vector.
Gaussian Images, and Our Results A natural candidate for probing whether such properties can make the problem of recovering private vectors more challenging is the case where the public and private vectors are sampled from the standard Gaussian distribution over Rd. While this distribution does not capture datasets in the real world, it avoids some properties of distributions over natural images that might make InstaHide more vulnerable to attack and is thus a clean testbed for stress- testing candidate security claims for InstaHide. Furthermore, in light of known hardness results for certain learning problems over Gaussian space Diakonikolas et al. (2017); Bruna et al. (2020); Diakonikolas et al. (2020b); Goel et al. (2020a); Diakonikolas et al. (2020a); Klivans & Kothari (2014); Goel et al. (2020b); Bubeck et al. (2019); Regev & Vijayaraghavan (2017), one might hope that when the vectors are Gaussian, one could rigorously establish some lower bounds, e.g. on the and/or the runtime of the attacker (computa-
size of the synthetic dataset (information-theonl tional), perhaps under average-case assumption, or in some restricted computational model like SQ.
Orthogonally, we note that the recovery task the attacker must solve appears to be an interesting in- verse problem in its own right, namely a multi-task, missing-entry version of phase retrieval with an intriguing connection to sparse matrix factorization (see Section 2.2 and Section 3). The assumption of Gaussianity is natural starting point for understanding the average-case complexity of this prob- lem, and in this learning- -thoorettc context it is desirable to give algorithms with provable guarantees.
We did not descrihe how the labels for the synthetic vectors assigned, but this part of InstaHide will not he important for our theoretical results and defer discussion of lahels to Section 4.
2

---

Published as a conference paper at ICLR 2021
Gaussianity is often standard starting point for developing guarantees for such inverse problems Moitra & Valiant (2010); Netrapalli et al. (2013); Candes et al. (2015); Hardt & Price (2015); Zhong et al. (2017b;a): Li & Yuan (2017); Ge et al. (2018); Li & Liang (2018); Zhong et al. (2019); Chen et al. (2020); Kong et al. (2020); Diakonikolas et al. (2020b).
Our main result is to show that when the private and public data is Gaussian, we the synthetic and public vectors to recover a subset of the private vectors.
Theorem 1.1 (Informal, see Theorem B.1), If there are ppriv private vectors and pupb public vec- tors, each of which is i..dd draw from No0,, Ida), then as long as d +2(poly (kpub; kipriu) log(Npub + -priv), there is some m = o(n Kair) vectors independently generated as above, one can exactly recover kpriv + 2 private vectors in time O(d(m² + (ubb)) + poly (Tbbb) with probability 9/10 over the randomness of the private and public vectors and the randomness of the selection vectors.
priv such that, given a sample of m. random synthetic
We emphasize that we can take m = o priv ). meaning we can achieve recovery even with access to a vanishing fraction of all possible combinations of private vectors among the synthetic vectors generated. For instance, when hipriv = 2, we show that m = ( 4/3, suffices (see Theorem B.
See Remark B.2 for additional discussion.
Additionally, to ensure we not working in uninteresting setting where InstaHide has zero utility, we empirically verify that in the setting of Theorem 1.1, one can train on the synthetic vectors and get reasonable test accuracy on the original Gaussian dataset (see Section 4).
Qualitatively, the main takeaway of Theorem 1.1 is that to prove meaningful security guarantees for InstaHide, we must be careful about the properties we posit about the underlying distribution generating the public and private data, even in challenging settings where this data does not possess the nice properties of natural images that have made other attacks possible.
1.1 CONNECTIONS AND EXTENSIONS TO PHASE RETRIEVAL
Our algorithm is based on connections and extensions to the classic problem of phase retrieval. At a high level, this can be thought of as the problem of linear regression where the signs of the linear responses are hidden. More formally, this is a setting where we get pairs (I1, y1 (1),,,., (IN,, yN) E C" x R for which there exists a vector E C satisfying Kw, aw,,,)) = y/ for all = 1, ...,, N, and the goal is to recover w. Without distributional assumptions on how T1. EN are generated, this problem is NP-hard Yi et al. (2014), and in the last decade, there has been huge body of work, much of it coming from the machine learning community, on giving algorithms for recovering w under the assumption that F1, ..., .N i.i.d. Gaussian, see e.g. Candes et al. (2013; 2015); Conca et al. (2015); Netrapalli et al. (2013).
To the connection between InstaHide and phase retrieval, first imagine that InstaHide only works with public vectors (in the notation of Theorem 1.1, Ppriv = Aipriv = 0). Now, consider a synthetic vector y E IRd generated by InstaHide, and let the vector w E noue be the one specifying the convex combination of public vectors that generated y. The basic observation is that for any feature E [d]. if E IR Rps is the vector consisting of i-th coordinates of all the public vectors, then Kw, æx)1 = yi-
In other words, if InstaHide only works with public vectors, then the problem of recovering which public vectors generated a given synthetic vector is formally equivalent to phase retrieval. In par- ticular, if the public dataset is Gaussian, then we can leverage the existing algorithms for Gaussian phase retrieval. Huang et al. (2020b) already noted this connection but argued that if InstaHide also uses private vectors, the existing algorithms for phase retrieval fail. Indeed, consider the extreme case where InstaHide only works with private vectors (i.e. Pub 0), so that the only information we have access to is the synthetic vector (V1,..,yyd generated by InstaHide. As noted above in the discussion about private distributions where the features are identically distributed, it is clearly information-theoretiaall theoretically impossible to recover anything about w or the private dataset.
As will see, the key workaround is to exploit the fact that InstaHide ultimately generates multiple synthetic vectors, each of which is defined by a random sparse convex combination of public/private
See Problem and Remark 2.7 for what exact recovery precisely means in this context.
3

---

Published as a conference paper at ICLR 2021
vectors. And will make formal in Section 2.2, the right algorithmic question to study in this context can be thought of as a multi-tase missing-data version of phase retrieval (see Problem 2) that we believe to be of independent interest.
Lastly, we remark that in spite this conceptual connection to phase retrieval, and apart from component of our algorithm (see Section B.1) which draws upon existing techniques for phase retrieval, the most involved parts our algorithm and its analysis utilize techniques that are quite different from the existing ones in the phase retrieval literature. We elaborate upon these techniques in Section 3.
2 TECHNICAL PRELIMINARIES
Miscellaneous Notation Given a subset T, let Cf denote the set of all subsets of of size exactly
k. Given a vector E IR and a subset S S [n)] let [v]s E TR|ST denote the restriction of v to the coordinates indexed by S.
Definition 2.1. Given Gaussian distribution (00 Σ), let / (0, Σ) denote the folded Gaussian distribution defined as follows: to sample from A ffolld(() (0, Σ), sample g ~ NO0 Σ) and output [g).
2.1 THE GENERATIVE MODEL.
Definition 2.2 (Image matrix notation). Let image matrix X E Rd be matrix whose columns consist of vectors T1,-.., In corresponding to n images each with pixels taking values F.3 will also be convenient to refer the rows of X p1, Pd IR
Definition 2.3 (Public/private notation). Let S C [1....,n} n} be some subset. We will refer to S and 5 {I,..., S as the set of public and private images respectively, and given vector w E IR" we will refer to supp(w) n and supp(w) n as the public and private coordinates of respectively.
Definition 2.4 (Synthetic images). Given sparsity levels kipub S 18), Kpriv S 15% image matrix X and selection vector E R for which [w]s and [w]s= kipb and -prive respectively, the corresponding synthetic image is the vector
X.
Xwi,
where |-| denotes entrywise absolute value. We say that X and sequence of selection vectors WI, Wm E Rn give rise to a synthetic dataset consisting of the images (uy ...., y,.,,,",,,,,..... Wm
Note that instead of the entrywise absolute value of Xw, InstaHide in Huang al. (2020b) ran- domly flips the sign of every entry of Xw, but these two operations are interchangeable in terms of information; will be slightly more convenient work with the former.
We will work with the following distributional assumption on the entries of X:
Definition 2.5 (Gaussian images). We say that X is a random Gaussian image matrix if its entries sampled i.i.d. from (00, 1).
We will also work with the following simple notion of "random convex combination" as our model for how the selection vectors wi...., Wm are generated:
Definition 2.6 (Distribution over selection vectors). Let 'D be the distribution over selection vectors defined as follows. To sample once from D, draw random subset Ti C S.T. S S size kipb and kpriv and output the unit vector whose i-th entry VRpu otherwise.*
if
Ti, Vkyw
if E T2, and zero
The main algorithmic question we study is the following:
We will often refer public/privatcesynteete feature vectors images, and their coordinates as pixels, in keeping with the original applications of InstaHide image datasets in Huang al. (2020h)
"Note that any such vector does not specify a convex combination. but this choice of normalization is just to make some of the analysis later somewhat cleaner, and our results would still hold if we chose the vectors the support of have entries summing
4

---

Published as a conference paper at ICLR 2021
Problem 1 (Private (exact) image recovery). Let X
Rddx be Gaussian image matrix,
Given access to the public images {r.) and the synthetic dataset (yx,w, ,...... y xm where Wi,... Wm D are unknown selection vectors, output vector R for which there exists private image 2, (where s 5*) satisfying | = (z,))l for all E [d].
Remark 2.7. Note that is information -etemmatiioo-heootiicllllll impossible to guarantee that 2; (r.): This because the distribution over X and the distribution over matrices given by sampling X and multiplying every private image by 11 are both Gaussian. And if the selection vectors wi,... Wm generated the synthetic images in the former case, then the selection vectors wi..., w where w/ is obtained by multiplying the private coordinates of wy by -1, would generate the exact same synthetic images.
2.2 MULTI- MUSKI-TASK PHASE RETRIEVAL WITH MISSING DATA
In this section make formal the discussion in Section 1.1 and situate it in the notation ahove. First consider synthetic dataset consisting of a single image _ yx.", where w is arbitrary and X a random Gaussian image. From Eq. (1) we know that
(w,, py) = y5 v E [d].
S == = {1,..,, n. then the problem of recovering selection vector w from synthetic dataset {リ} is merely that of recovering w from pairs (Pjs y5). and this exactly the problem of phase retrieval over Gaussians. More precisely, because w is assumed to be sparse, this is the problem of sparse phase retrieval over Gaussians.
If S {1,..., n.,, then it's clearly impossible to recover the private coordinates of w from yx. alone. But may still be possible to recover the public coordinates: formally, we can hope to recover [w]s given pairs ([pyls: V/), where the py This can be thought of as a missing-dalt dataa version of sparse phase retrieval where some known subset of the coordinates of the inputs, those indexed by S unobserved.
sampled independently from N(0 Id,.)
But recall our ultimate goal is to say something about the private images. It turns out that because we actually observe multiple synthetic images, corresponding multiple vectors w, becomes possible to recover I, for some s E S (even in the extreme case where $ = @!). This corresponds to the following inverse problem which is formally equivalent to Problem but phrased in self-contained way which may be of independent interest.
Problem (Multi-task phase retrieval with missing data). Let S [n] and [m]] Let X E Rdxn be a matrix whose entries are i.i.d. draws from NO0 1), with rows denoted by Pl. ... Pa and columns denoted by I1, ...; Fn. Let Wi,.... ......,,, Wm ~ D.
For every [d]. we get tuple (Ip)ls. v/ "/....?"") m/)) satisfying
ViE [m]]. [d]. (w p))l y (
Using just these, output r E IRd such that for some E S |æ,] (xx.); for all i E [d].
PROOF OVERVIEW
At a high level, our algorithm has three components:
1. Learn the public coordinates of all the selection vectors wi,..., Wm used to generate the synthetic dataset.
2. Recover the x rescaled Gram matrix M whose jit entry is ks (wi, Wz)-
3. Use M and the synthetic dataset to recover private image.
Step 1 draws upon techniques in Gaussian phase retrieval, while Step follows by leveraging the correspondence between the covariance matrix of Gaussian and the covariance matrix of its cor- responding folded Gaussian (see Definition 2.1). Step 3 the trickiest part and calls for leveraging delicate properties of the distribution D over selection vectors.
5

---

Published as a conference paper at ICLR 2021
Learning the Public Coordinates of Any Selection Vector We begin by describing how to carry out Step above. First consider the case where S = {l..... n). that is, where every image is public. Recall from the discussion in Section 1.1 and 2.2 that in this case, the question of recovering w from synthetic image yx is equivalent to Gaussian phase retrieval. One way to get a reasonable approximation
to consider the n matrix
N
Ely² (pp Id]], P:y
p (N, and y k(r,))
It is standard calculation (see Lemma B.3) show that N is rank-one matrix proportional to www T. And every one of pi..... .......... Pa is an independent sample from (0, Id), and y/₂ X,, satisfies (w, p.) = yi X, for every pixel E [d], one can approximate N with the matrix
d
v ) 2 (piP. - Id).
Ñ
This is the basis for the spectral initialization procedure that is present in many works on Gaussian phase retrieval, see e-g. Candes et al. (2015); Netrapalli al. (2013). N will not be sufficiently good spectral approximation to N when < n, so instead we use a standard post-processing step based on the canonical SDP for sparse PCA (see (2)). Instead of taking the top eigenvector of N, we can take the top eigenvector of the SDP solution and argue that long d (1(pll (Apub) log n),, this will be sufficiently close to w that we can exactly recover supp(w).
Now what happens when S S {L....,7) nn?? Interestingly, if one simply modifies the definition of N be Ep.yly². (ppss (p]s(p]] Id)] and defines the corresponding empirical analogue IÑ formed from the pairs {[pi)s s, V/ xx") hie(d one can still argue (see Lemma B.3) that the is a rank-1 |S] x [S] matrix proportional to [w]s|ut [ and that the top cigenvector of the solution to suitable SDP formed from Ñ will be close (see Lemma B.4).
Recovering the Gram Matrix via Folded Gaussians As we noted earlier, it is information- theoretically impossible to recover [w:]s= for any [m]] given only y yx,u; and [w,]s. but we now show it's possible to recover the inner products [[wiss,, [wy]s=)) for any i.j E [m]. For the remainder of the overview, we will work in the extreme case where 5 (1.... n). though it is not hard (see Section B.7) to combine the algorithms we are about to discuss with the algorithm for recovering the public coordinates to handle the case of general S. For brevity, let k A kipriv
First note that the m x d matrix whose rows consist of y y.x. ..... ...,yXX.m can be written as
Kp1 wiYl : Kpa, wm)i
Kpa, wi)l
Y
Kpa, w..il
Observe that without absolute values, each column would be an independent draw from the m- variate Gaussian (0, M), where M is the Gram matrix defined above. Instead, with the absolute values, each column of Y actually an independent draw from the folded Gaussian Affl (0, M) (Definition 2.1). The key point is that the covariance of (0, can be directly related to M (see Corollary B.6), so by estimating the covariance of the folded Gaussian fffold (0, M) using the columns of Y, entry of M that the rounded matrix exactly equals M. Furthermore, we only need to entrywise approximate the covariance of Afold M) for all this to work, which is why it suffices for d to grow logarithmically m.
obtain good enough approximation M to M that we can simply round every
Discerning Structure From the Gram Matrix By this point, we have access to the Gram matrix M. Equivalently, we now know for any i,j E [m] whether supp(w), n supp(w,) of 0. that is, for any pair of synthetic images, we can tell whether the set of private images generating one of them overlaps with the set generating the other. Note that M = k WW where W is the matrix whose i-th row is w;, so if we could factorize M in this way, would be able to recover which private vectors generated each synthetic vector. Of course, this kind of factorization problem, even if we constrain the factors be row-sparse like W, has multiple solutions. One reason is that any

---

Published as a conference paper at ICLR 2021
permutation of the columns of W would also be a viable solution, but this is not really an issue because the ordering of the private images is not identifiable to begin with.
A more serious issue is that if m is too small, there might be row-se factorizations of M which appear to be valid, but which we could definitively rule out upon sampling more synthetic vectors. For instance, suppose the first ++11 selections vectors all satisfied |supp(u) ) (isupp( (yy)) k 1. Ignoring the fact that this is highly unlikely, in such a scenario it is impossible to distinguish between the case where the corresponding synthetic images all have the same k-1 private images in common, and the case where there is a group T S [n|] of k + private images such that each of these synthetic images is comprised of a subset of T of size k. But if we then sampled a new selection vector Wk+2 for which |supp( (wy) n supp [24+2) = 1 for all j E [k + 1], we could rule out the latter.
This is indicative of a more general issue, namely that one cannot always recover the identity of a collection of subsets (even up to relabeling) if one only knows the sizes of their pairwise intersec- tions!
This leads to the following natural combinatorial question. What families of sets are uniquely identi- fied (up to trivial ambiguities) by the sizes of the pairwise intersections? One answer to this question, as we show, is the family of all subsets of {1, {1,.... k + 2} of size k (see Lemma B.11). This leads us to the following definition:
Definition 3.1 (Floral Submatrices). A (k+2) x (k++) matrix H is floral if the following holds. Fix some lexicographic ordering on Ck [k+22 and index H according to this ordering. There is some
permutation matrix II for which the matrix H' A II HII satisfies that for every pair of S, E Ck 2++2]- H'ss SS n S'). See Example 1.18 in the supplement.
The upshot is that if we can identify a floral submatrix of M. then we know for certain that the subsets of private images picked by those selection vectors comprise all size-k subsets of some subset of [n] of size ls + 2. In summary, using the pairwise intersection size information provided by the Gram matrix M, we can pinpoint collections of selection vectors which share nontrivial amount of common structure.
Learning Private Image With a Floral Submatrix What can we do with this common structure in a floral submatrix? Let t 2 Given that the selection vectors Wiy ... wi, corresponding to the rows of the floral submatrix only involve & + 2 different private images altogether, and there
X,",, for any pixel & E [4]. we can hope that for each pixel, we can uniquely recover the k + 2 private images from solving this system of equalities, where the unknowns are the values of the k + 2 private images at that particular pixel. A priori, the fact that the number of constraints in this system exceeds the number of unknowns does not immediately guarantee that this system has a unique solution up to multiplying the solution uniformly by -1. Here we exploit the fact that X is Gaussian show however that this is the case almost surely (Lemma B0).). Finally, note that this system can be solved in time exp(O by simply enumerating over 2 sign patterns. We conclude that if we could find floral submatrix, then we would find not just one, but in fact k + private images!
are t > k + 2 constraints of the form KWw,, (W)) = Ve
Existence of Floral Submatrix, and How to Find It It remains to understand how big m has to be before we can guarantee the existence of floral submatrix inside the Gram matrix M with high probability. Obviously if m were big enough that with high probability we see every possible synthetic image that could arise from a selection vector w in the support of D, then M will contain many floral submatrices. One surprising part of our result is that we can ensure the existence of a floral submatrix when m much smaller. Our proof of this is quite technical, but high level is based on the second moment method (see Lemma B.12).
The final question is: provided floral submatrix of M exists, how do we find it? Note that naively, we could always brute-force over all (o(ke)) S ri O(k2) principal submatrices with exactly (kt3) rows/columns, and for each such principal submatrix we can check in cxp(((k:) time whether it is floral.
Surprisingly, we give an algorithm that can identify a floral submatrix of M in time dominated by the time it takes to write down the entries of the Gram matrix M. Note that off-the-shelf algorithm for
7

---

Published as a conference paper at ICLR 2021
subgraph isomorphism would not suffice the size of the submatrix in question is O(k2). and fur- thermore such an algorithm would need to work for weighted graphs. Instead, our approach is to use the constructive nature of the proof in Lemma B.1 that the family of all subsets of {L...., k + 2] of size k is uniquely identified by the sizes of the pairwise intersections. By algorithmizing this proof, give efficient procedure for finding floral submatrix, see Algorithm 3 and Lemma 1.17. An important fact we use is that if we restrict our attention to the entries of M equal to k - or k - 2, this corresponds graph over the selection vectors which is sparse with high probability.
We defer the formal specification and analysis of our algorithm to the supplement.
4 EXPERIMENTS
We describe an experiment demonstrating the utility of InstaHide for Gaussian images and com- paring to the utility of another data augmentation scheme, MixUp Zhang et al. (2018). We also informally report on our implementation of LEARNPUBLIC and its empirical efficacy.
4.1 CHOICE OF ARCHITECTURE AND PARAMETERS
As our empirical results are purely for proof-of-concep,, we work with fairly basic neural network architecture. We use 4-layer neural network as a binary classifier,
y = arg max(softmax (Wa (W + b1)) + 82) + b3) + b4)),
where x E 1210 Wi E R100x10 W2 E 10000x100 W3 E 1100x100 Wa E 1g2x100 : I E R1000 by E R2000 by R2000 by 1R000 We initialize the entries of each W, and by to be i..d. draws from N(u, 1), where uj is sampled from (O. a) at the outset. We train the neural network for 100 epochs with cross-entropy loss and SGD optimizer with a learning rate of 0.01. We do not need to distinguish between public and private images in our experiments, so let kpriv 0 and kpub = for l E { 1, 2, 3, 6). and for each choice of k we use random k-sparse selection vectors whose nonzero entries equal 1/k. In all of our experiments, data (before generating synthetic data) into two categories: 80% training data and 20% test data. We train synthetic images generated by MixUp or InstaHide using the training data, and measure the "test accuracy" " on the training data and the test data separately. We provide more choices of l in Appendix C.
separate our original image
4.2 GAUSSIAN DATA
Settings We considered binary classification Gaussian data. We generated random images Ti..... 1000 E RR from Id) and a random vector v E 0000 -O, Id). We then ranked all the Gaussian images based on Σ; |æ,,%,| and labeled the largest half as '1' and the rest as '0', The point of choosing this labeling function is that it would assign the same label to any x, x' which agree entrywise in magnitudes. Given synthetic image generated via MixUp or InstaHide using selection vector w, we assigned it the label which is the convex combination of the one-hot encodings of the labels of the original images indexed by w.
Results We compare training and test loss over epochs when training on a synthetic dataset gen- erated by either MixUp Instahide, shown in Figure 1. We use the convention in this paper of defining synthetic images under InstaHide to have all nonnegative entries (rather than imposing ran- dom sign flips). though we explore the supplement how random sign flips can affect learnability. Compared to training on MixUp, InstaHide results on lower model performance (accuracy). As we expected, when we increase the k. both MixUp and InstaHide suffer from accuracy loss. Instahide dropped by ~ 10% accuracy when k = 6 compared to classical training k 1, while MixUp dropped by ~ 5%.
4.3 IMPLEMENTATION OF LEARNPUBLIC
We implemented LEARNPUBLIC for Kpriv = 2 and n {2000, (2000,5000, 7500, 10000). For kipub
2, 4, 6, we respectively chose = 1000, 1800, 2400. In particular, our choice of meant to work essentially for any choice of (modulo the logarithmic dependence which does not noticeably
8

---

Published as a conference paper at ICLR 2021
1.0
1.0
0.0
0.0
0.
0.9
Ena
0.7
2.7
0.6
0.5
100
20
150
20
130
103
soomh
epoch
epoch
eacchh
(a) ls
(b) k =
(c) k 3
(d) 1: 6
Figure I: Comparing MixUp and Instahide training on Gaussian dataset with different k.
manifest in this regime). One heuristic modification that we made to LEARNPUBLIC was use diagonal thresholding approach from Cai et al. (2016) in place of solving the SDP in (2): namely for every j [n] we computed the quantity 1/2 Σ y {. zeroed out all but the principal submatrix of M indexed by the top 25 such j. and computed the top eigenvector of the resulting matrix. For each parameter setting we found that, as expected, we were able to recover an average of at least 90% of the support. As this experiment was primarily to demonstrate that d can be much less than n, we did not explore further optimizations to the algorithm.
REFERENCES
Joan Bruna, Oded Regev, Min Jac Song, and Yi Tang. arxiv:2005.0955 2020.
Continuous Iwe. arXiv preprint
Sébastien Bubeck, Yin Tat Lee, Eric Price, and llya Razenshteyn. Adversarial examples from com- putational constraints. In International Conference Machine Learning (ICML), pp. 831-840, 2019.
Tony Cai, Xiaodong Li, and Zongming Ma. Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow. The Annals of Statistics, 44(5):2221-225) 2016.
Emmanuel Candes, Thomas Strohmer, and Vladislav Voroninski. Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming, Communications on Pure and 2013.
Applied Mathematics, 66(8):
Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions Information Theory, (985):195-2000) 2015.
Nicholas Carlini, Samuel Deng, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mah- moody, Shuang Song, Abhradeep Thakurta, and Florian Tramer. An attack on instahide: Is private learning possible with instance encoding? arXiv preprint arXiv:2011.053135 2020.
Sitan Chen, Jerry Li, and Zhao Song. Learning mixtures of linear regressions suhexponential time via fourier moments. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 587-600, 2020.
Aldo Conca, Dan Edidin, Milena Hering, and Cynthia Vinzant. An algebraic characterization of injectivity in phase retrieval. Applied and Computational Harmonic Analysis, 38(2):346-356, 2015.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition (CVPR), pp. 248-255, 2009.
Ilias Diakonikolas. Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73-84, 2017.
Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Process- ing Systems (NeurIPS), 2020a.

---

Published as a conference paper at ICLR 2021
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. In Conference on Learning Theory (COLT), pp. 1539,, 2020b.
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. In ICLR, 2018.
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolyno- mial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning (ICML), 2020a.
Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems (NeurIPS). 2020b.
Moritz Hardt and Eric Price. Tight bounds for learning a mixture of two gaussians. In Proceedings of the seventh ammual ACM symposium on Theory of computing (STOC), pp. 753-760, 2015.
Yangsibo Huang, Zhao Song, Danqi Chen, Kai Li, and Sanjeev Arora. Texthide: Tackling data privacy in language understanding tasks. In The Conference on Empirical Methods in Natural Language Processing (Findings of EMNLP), 2020a.
Yangsibo Huang, Zhao Song, Kai Li, and Sanjeev Arora. Instahide: aetaacee-idiing schemes for private distributed learning. In International Conference on Machine Learning (ICML), 2020b.
Matthew Jagielski.
2020. https::/cooab. research google. e. com dri vive
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. FOCS, 2020.
Raymond Kan and Cesare Robotti. On moments of folded and truncated multivariate normal distri- butions. Journal of Computational and Graphical Statistics, 26(4):930 934, 2017.
Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaussian space. In Ap- proximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (AP- PROX/RNNDOM 2014). Schloss Dagsuuhl-LebmiizzZeerurm fuer Informatik, 2014.
Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In ICMI., 2020.
Yuanzhi Li and Yingyu Liang. Learning mixtures of linear regressions with nearly optimal com- plexity. In Conference on Learning Theory (COLT), 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU activa- tion. In Advances in neural information processing systems (NIPS), pp. 597-607, 2017.
Ankur Moitra and Gregory Valiant. Settling the polynomial Icarnability of mixtures of gaussians. In 2010 IEEE 5 Annual Symposium on Foundations of Computer Science (FOCS), pp. 93-102. IEEE, 2010.
Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi. Phase retrieval using alternating minimiza- tion. In Advances Neural Information Processing Systems (NeurIPS), pp. 2796-2804, 2013.
Matey Neykov, Zhaoran Wang, and Han Liu. Agnostic estimation for misspecified phase retrieval models. In Advances in Neural Information Processing Systems (NeurIPS), pp. 4089-4097, 2016.
Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well-separated gaussians. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 85-96, 2017.
Xinyang Yi, Constantine Caramanis, and Sujay Sanghavi. Altematinn minimization for mixed linear regression. In International Conference on Machine Learning (ICML), pp. 613-621, 2014. Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations (ICLR), 2018.
10

---

Published as a conference paper at ICLR 2021
Kai Zhong, Zhao Song, and Inderjit S Dhillon. Learning non-overlapping convolutional neural networks with multiple kernels. In arXiv preprint, 2017a.
Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hiddenl neural networks. In International Conference on Machine Learning (ICML), 2017b.
Kai Zhong. Zhao Song, Prateek Jain, and Inderjit S Dhillon. Provable non-linear inductive matrix completion. In Advances Neural Information Processing Systems (NeurIPS), pp. 11439-11444 11449, 2019.

---

Published as a conference paper at ICLR 2021
A DISCUSSION OF OTHER ATTACKS
Attack of Jagielski (2020) It has been pointed out Jagielski (2020) that for lipriv = 2, kipub 0, given a single synthetie image one discern large regions of the constituent private images simply by taking the entrywise absolute value the synthetic image. The reason is the pixel values of a natural image are mostly continuous, i.e. nearby pixels typically have similar values, so the entrywise absolute value of the InstaHide image should be similarly continuous. That said, natural images have enough discontinuities that this breaks down if one mixes more than just two images, and as discussed above, this attack is not applicable when the individual private features are i.i.d. like in our setting.
Attack of Carlini et al. (2020) month after this submission, Carlini et al. Carlini et al. (2020) independently gave an attack breaking the InstaHide challenge originally released by the authors of Huang et al. (2020b). In that challenge, the public dataset was ImageNet, the private dataset consisted of Plrriv 100 natural images, and Kipii = 2, kipub = 4, m 5000. They were able to produce a visually similar copy of each private image.
Most of their work goes towards recovering which private images contributed to each synthetic image. Their first step is to train a neural network on the public dataset to compute a similarity matrix with rows and columns indexed by the synthetic dataset, such that the (i.j) j'th entry approximates the indicator for whether the pair of private images that are part of synthetic image overlaps with the pair that is part of synthetic image j. Ignoring the rare event that two private images contribute two distinct synthetic images, and ignoring the fact that the accuracy of the neural network for estimating similarity is not perfect, this similarity matrix is precisely our Gram matrix in the Apriv 2 case.
The bulk of Carlini et al.'s work Carlini et al. (2020) is focused on giving heuristic for factorizing this Gram matrix. They do so essentially by greedily decomposing the graph with adjacency matrix given by the Gram matrix into plrly cliques (plus some k-means post-processing) and regarding each clique as consisting of synthetic images which share a private image in common. They then construct an m x Plrivv bipartite graph as follows: for every synthetic image index and every private image index j. connect to j if for four randomly chosen elements i1,,.. ig E [m]] of the j-th clique, the (i, 3-th entries of the Gram matrix are nonzero. Finally, they compute min-cost max-flow on this instance to assign every synthetic image to exactly Aipriv = private images.
It then remains to handle the contribution from the public images. Their approach is quite different from our sparse PCA-based scheme. At high level, they simply pretend the contribution from the public images is mean-zero noise and set up nonconvex least-squares problem to solve for the values of the constituent private images.
Comparison to Our Generative Model Before we compare our algorithmic approach to that of Carlini et al. (2020), mention an important difference between the setting of the InstaHide chal- lenge and the one studied in this work, namely the way in which the random subset of public/private images that get combined into synthetic image is sampled. In case, for each synthetic image, the subset is chosen independently and uniformly at random from the collection of all subsets con- sisting of kpriv private images and kpub public images. For the InstaHide challenge, batches of nprivv synthetic images get sampled one at a time via the following process: for a given batch, sample two random permutations T1, T2 on ppriv elements and let the t-th synthetic image in this batch be given by combining the private images indexed by Ti (t) and (t).). Note that this process ensures that every private image appears exactly 2m/ 2m/Tpriv Upriv times, barring the rare event that क (t) = (t( for some l in some batch. It remains to be seen to what extent the attack of Carlini et al. (2020) degrades the absence of this sort of regularity property in our setting.
Comparison to Our Attack The main commonality between our approach and that of Carlini et al. (2020) is to identify the question of extracting private information from the Gram matrix the central algorithmic challenge.
How compute this Gram matrix differs. We use the relationship between covariance of folded Gaussian and covariance of a Gaussian, while Carlini et al. (2020) use the public dataset to train a neural network on public data to approximate the Gram matrix.
12

---

Published as a conference paper at ICLR 2021
How this matrix also differs significantly. We do not produce candidate factorization but instead pinpoint a collection of synthetic images such that we can provably ascertain that each one comprises kpriv private images from the same set of kpriv + 2 private images. This allows us to set up an appropriate piecewise linear system of size (Kprri) with a provably unique solution and solve for the Kpriv + 2 private images.
An exciting future direction is to understand how well the heuristic in Carlini et al. (2020) scales with Kiriie. Independent of the connection to InstaHide, it would be very interesting from a theoret- ical standpoint if one could show that their heuristic provably solves the multi-task phase retrieval problem defined in Problem in time scaling only polynomially with Kpriv (i.e. the sparsity of the vectors W1, Wm in the notation of Problem 2).
B RECOVERING PRIVATE IMAGES FROM A GAUSSIAN DATASET
In this section we prove our main algorithmic result:
Theorem B.1 (Main). Let S S [n], and let npub |S| and Reriv 1.5% Let k kipbb + Kpriv- Apii Kpott (oool((ash))) then with
If d 2 ((poly(Kpub Kpriv) log + +ppriv) and 2 Q
''riv
high probability over X and the sequence of randomly chosen selection vectors w1; Wm D, there is algorithm which takes input the synthetic dataset (y) " lig[m) and the columns of X indexed by S, and oulputs kipii + 2 distinct images
Tkpw++ for which there exist Kpriv + 2 distinct private images Fip ....... Fixpo satisfying [ī:]] = |rii for all [kiriv + 2]. Furthermore,
the algorithm runs time
Odm² dn pub + n 2w+1).
pub
where w == 2.373 is the exponent of matrix multiplication. Remark B.2. Here we give some interpretation to the quantitative guarantees of Theorem B.1:
The number of pixels d only needs to depend logarithmically on the number of pub- lic/private images and polynomially in the sparsity kppb. Aprii. which will be some small positive integer (e.g. kupb + Kpriv 4 or 8 in Huang et al. (2020a), kpub + kpriv = 4 or 6 in Huang et al. (2020b) and kppb + Aipriv = 2 in the implementation of MixUp in Zhang et al. (2018)), so the regime in which Theorem B.1 applies is quite realistic.
Aipte Note that we can achieve recovery even when m = o(
). The reason this is significant
is that as soon as m = (m Anw), ). all possible combinations of k private images are used. While it is still not immediately clear how to recover private images once this has happened, we regard the fact that we can do well before this point to be one of the most interesting aspects of our result. Finally, we remark that the runtime is largely dominated by the O(²) term coming from forming an m X m matrix whose equal (w, wy) for all j E [m]. In fact, naive implementations of the most sophisticated part of our algorithm (see Sections B.3, B.4, B.5, and B 6) require time w( (m² and getting these parts of the algorithm to run in O(m)) time turns out to be quite subtle.
entry turns out to
B.1 LEARNING THE PUBLIC COORDINATES VIA GAUSSIAN PHASE RETRIEVAL
In this section we give a procedure which, given any synthetic image y yxX.,, recovers the entire support of [w]s. The algorithm is inspired by existing algorithms for sparse phase retrieval, with the catch that we need to handle the fact that we only get to observe the public subset of coordinates of any of the vectors pj. Our algorithm, LEARNPUBLIC is given in Algorithm below.
We first show that the population version of the matrix M formed in Step 1 is rank-1 projector whose top eigenvector is in the direction of [urss-
Lemma B.3. Let w be unit vector. Let M E R be defined as
M 2
1
Σ
1 1) (lryls lpsls ld)
13

---

Published as a conference paper at ICLR 2021
Algorithm 1: LEARNPUBLIC s, VU ())))(())))
Input: Samples ([pi]s: 3/1 ...,, (pals Ma)
Output: supp([w]s) with probability at least 6, provided d 2
log(n/6)
Form the matrix M _ à Eー=100 (v} 1) (pyls [py]s - ld).
Solve the semidefinite program (SDP) (this step takes p'pub
2w++1
via Jiang et al. (2020))
max Z, M) subject to Tr(Z) 2=0
Zi.gl I
kpub
(2)
Compute the top eigenvector w of Z.
return coordinates of the k entries of i with the largest magnitudes.
Then E M
[ [[w]s[w]s
Proof. First, is obvious that the expectation of M can be written as
E
[(w,,p)) p)² 1) (pspg Id)]
p-N (0.1a)
For any vector v E IR" with ||l||2 = 1, we can compute e. E
e EMMp = o E(((w,p)) 1) (NSP3 - Id)]
E(((w,p)2 - -1) ((w)s, p)² 1)] B(((w,p)) 1) (1 (1tl0//sllllllll.. 1)]
p)(( 1) [IlbdsslB((lsss/lllsllllll |[[0|s113)
+ ()(((w,))* - 1) (1]|)s|13 1)]
A A2
where the second step follows from |0113 = 1. For the first term in the above equation, we have
A E[((w, p)² - 1) (IIcs=/B((clss//llllllll.. - [|[v|s|13
||v]s|l2 2 E ((((w - 1 ((bls// [|[}s{113]
21[(v] E (ltp:)))))((((l3llcllllll/...//
22[[v] 1 (w. [v]s/| (v))s2)
2(w, [u]s]²
where the third step follows from the fact that w and [u]s/[[[u]s]] are unit vectors, Φ2 denotes the normalized degree-2 Hermite polynomial Φ2(2) & 1
/ (s² 1), and the last step follows from the standard fact that Eg~N((, (0:((9 (1)) w2)) (0, v2) if j and otherwise. For the second term, we have
A B[((w, - 1)- [[]s 1)] = (I[[)ss13 1) El(w, p)² - 1] 0.
Thus, we have
A1 Ao 2(w, [o]s)².
the above quantity is [|[[w]s [wwsl3. 12 while for v L [w]ss the above quantity is O. Thus complete the proof.
In particular, for e =
14

---

Published as a conference paper at ICLR 2021
Finally, complete the proof of correctness of LEARNPUBLIC. Here we leverage the fact that we are running an SDP (the canonical SDP for sparse PCA) to show that as long as d is at least polynomially large in Kpub and logarithmicalty large in with high probability we recover supp([e) [w]s)-
Lemma B.4 (Learning the public coordinates). For any ō > if poly(kipub) log(n/5), then with probability at least - 6 over the randomness of X, we have that the coordinates oulput by LEARNPUBLIC( Uj)) jejd for yj - Kp,, w) are exactly equal to supp([w)ss.
Proof. Let be the solution to the SDP in (2), and define w. - [w]s/|[w]s|| Because w, is feasible solution for the SDP, by optimality of Z we get that
(Z w. M)
(Z W.W, w. B + (Z w. W. M E(M)
|| Z w. w. W4 (Z w M E
where in the last step we used Lemma B.3.
Because |/ I Tr(2) = 1 = | ||. we may upper bound ① by - ut_ 11 For ② note that because the entrywise L, norm of Z and N. are both upper bounded by k. by Holder's can upper bound 2 by pkipub || E E max- Standard concentration (see c.g. Neykov et al. (2016)) implies that long d 2 log(n/8 / then |M -E max S 77. We conclude from (3) that
[w]s 2|
1 w. w.w. IP. 2kipub?7,
so 2 - w. 11 < //pubn//l[u]ss > 8nk where in the last step we used that if w has at least one public coordinate, then ||[w]||| 2 1/kipub- By Davis-Kahan, this implies that the top eigenvector w of Z satisfies || by taking = ((1/k_2 we ensure that || w..l.o S || - w. ll < 1/2 Ripub. so the largest entries of w in magnitude will be in the same coordinates as the nonzero entries of w..
w. 2|2 < Snp As the nonzero entries of w, at least 1/ kppbb
B.2 RECOVERING THE GRAM MATRIX VIA FOLDED GAUSSIANS
We now turn to the second step of our overall recovery algorithm: matrix whose j-th entry is aupp(w;) O supp(w;). ). For this section and the next four sections, will assume that S 0, i.c. that all images are private. For brevity, let A å kpriv- This turns out to be without loss of generality. Given that the case where S & 0 we can recover the public coordinates of any selection vector using LEARNPUBLIC,, passing the case of general S will be simple matter of subtracting the contribution of the public coordinates from the entries of the Gram matrix obtained by GRAMEXTRACT reduce the case of S 0. We will elaborate on this in the final proof of Theorem B.
recovering the m X Gram
Given selection vectors Wiy... Wm. define the matrix W E Rmxd x to have rows consisting of these vectors, so that the Gram matrix we are after is simply given by WWT. Recall that the m x matrix whose rows consist of y X_,, y X. can be written as
Ke wi\l
Kpa, wiYl
Y A
(P1s wm)
Kpa wn))
and each entry of X is an independent standard Gaussian, the columns of Y R can be regarded as independent draws from fold (0, WW where W defined above. Let fold denote the covariance of this folded Gaussian distribution. It is known that about the covariance W of the original Gaussian distribution from the covariance folld of its folded counterpart:
recover information
15

---

Published as a conference paper at ICLR 2021
Lemma B,5 (Page 7 in Kan & Robotti (2017)). Given Gaussian (0, Σ), the covariance ffold Rmx. of the corresponding folded Gaussian distribution A (0, Σ) is given by Efold Σ and, for # J.
Ei 0: (1,) -) + 1 "j 12,)) (; - is 25
2 2/1 22/2 2/2
where Pr.j
E (E 2
We can apply Lemma B.5 in our specific setting to obtain the following relationship between WWT and the covariance of Aool (0, WW
Corollary B.6. I = WWT E Im for some matrix W E m where the rows of W are unit vectors, then the covariance ffold E mm of the corresponding folded Gaussian distribution AfTold (0, E) is given by
{1,
i ji if
(ww,, Wy)),
where (=)) A (2 arcsin(2) + v1 11-22- -1) 1).
Proof. Because the rows of W are unit vectors, we have that Σ,, Pt.j = (w,, wy) for all i.j [m]. To compute the off-diagonal entries of fold note that by definition of CDF and PDF,
aresin (w;, wzy)
(0 0; (wi, wy)) = 2T v (mi, myy2 (2 0; (wi, wy)) = 4 +
2x
The claim follows.
Algorithm 2: GRAMEXTRACT X,ws
hi((m):)) (y)t))
Input:
InstaHide dataset (ux, he((m)) ). accuracy parameter 7)
Output:
Matrix M equal the Gram matrix k- WWT, scaled have integer entries (see
Lemma B.7)
17" + -1)2). Let 21,... .... E I. be the vectors given by
(zz); = X.w,
for all i E [m],j E [d]. Form the empirical estimates
1
Σ
Σ
(z M2 22)
and define E' to be the matrix obtained by applying the function clip,-- entrywise to Σ. Let Σ be the matrix obtained by applying - entrywise to Σ.
Let E' denote the matrix obtained by entrywise rounding every entry of Σ to the nearest multiple of 1/k. return k Σ"
We now show that provided the number of pixels is moderately large, can recover the matrix ex- actly, regardless of the choice of selection vectors Wi...., Wm E R". The full algorithm, GRAMEX- TRACT, is given in Algorithm 2 above.
Lemma B.7 (Extract Gram matrix). Suppose d 2(log(m/0)/n') For random Gaussian image matrix X and arbitrary wi..., Wm E $22 ler Σ be the matrix computed in Step of GRAMEX- TRACT K.y [xe(m] 1)). and let E be the output. Then with probability 1-8 over the randomness X, we have that EE,y (w,, wy)] for all i, [m]. In particular, if 1j = 1/2k, the condi- tioned on this happening, E" k. WWT.
16

---

Published as a conference paper at ICLR 2021
To prove this, will need the following helper lemma about vr Lemma B.8. There is an absolute constant e >> 0 such that for any 0 < < and ž, 2 1)
M (2) v (z)]
-2-
Proof. Noting that (2) = 2 2arcsin())/T, we get that the derivative of v at is given by
(=) 2 arresin (V- One verify numerically that for 0 S 1, =² (xx) 1.2s so in particular /=z/ 1.2 < V (=) VTTz. The derivative of Q at is therefore upper bounded by O11 aresin( / m2/11221) S (...) In particular, for = 2 1/. this at most 0(1/ vT). In other words, over 7 S = $1 1- is 1 -ippsshhtiz as claimed.
Up this point we have used the randomness of the process generating the selection vectors w1,-,, Wm- Note that without leveraging this, there exist choices of W for which is information- theoretically impossible to discern anything. Indeed, consider a situation where wi,..., Wm E $ have pairwise disjoint supports. In this case all we know is that the columns of are independent standard Gaussian vectors, as WW ld. We now proceed to the most involved component of our proof, where we exploit the randomness of the selection vectors.
B.3 SOLVING A LARGE SYSTEM OF EQUATIONS
In this section we show that if we can pinpoint a collection of selection vectors corresponding to all size-k subsets of some set of k + 2 private images, then we can solve certain system of equations to uniquely (up sign) recover those private images. We will need the following basic notion corresponding to the fact that this system has only one unique solution, up to sign.
Definition B.9 (Generic solution of system of equations). For any m and any vector v = (US)sEcH
E <R
we say that v is generic if there are at most two solutions to the system
a
us
AS
Cim)
in the variables {ar Note that there are exactly two solutions {a}} and {af'} to this system and only if a = a. for all i [m] and a + O for some
[m]]
We now show that for Gaussian images, the abovementioned system of equations almost surely has a unique solution up to sign.
Lemma B.10 (Vector of Gaussian subset sums is generie). Let 91 .... Im be independent draws from k 2, the vector v (es)sect given by Us & Eies Pi is
1). For any satisfying generic almost surely (with respect to the randomness of 91...., Imn).
Proof. First note that the entries of are all nonzero almost surely. For v not be generic, there must exist another vector v' whose entrywise absolute value satisfies |e| = jer but for which v' of v. - and for which there exists h1 hi,.., hm satisfying Eves h = v'ss for all S E Cfmy. This would imply there exist indices S, T for which v's = ug and v/y Ur.
By the assumption that m 2 k + 2 (and recalling that & > 1 in our setup), we have that (7) > m. In particular, the set of vectors w (ws)secH_ for which there exist numbers {g/} such that
proper subspace of (T)). Let fI,..., la be a basis for the set of vectors l satisfying (e, w) = 0 for all E U. Note that there least one nonzero generic vector in U, for instance, the vector w' given by w = 1 i E S] (here we again use the fact that m 2 k+
uss Eies of for all
Letting D E ( (T) denote the diagonal matrix whose S-th diagonal entry is equal to v. /v'g, note that the existence of h1...., hm above implies that additionally satisfies (De, v) 0 for all i E [a). But there must be some i for which DE, does not lie in the span E,, la or else we would conclude that for any U, the vector w whose S-th entry is ws us ss/v's would also lie
17

---

Published as a conference paper at ICLR 2021
in U. Because of the existence of indices S, T for which v's ui and 1/7 -y, know that w * ww'-w', so we would erroneously conclude that w is not generic for any w E U, contradicting the fact that the vector w" defined above is generic.
We conclude that there is some for which De, lies outside the span of l,....,fa La But then the fact that (Dl,, r) 0 for this particular i implies that the variables 9: satisfy some nontrivial linear relation. This almost surely cannot be the case because 9I. Im are independent draws from ().
B.4 LOCATING A SET OF USEFUL SELECTION VECTORS
In the previous section we showed that we just need to find a set of selection vectors from among the rows of W that correspond to size-k subsets of some of + 2 private images. Here we show that such a collection of selection vectors is uniquely identified, up to trivial ambiguities, by their pairwise inner products.
Lemma B.11 (Uniquely identifying family of subsets). Let J (Ts)sect be collection of subsets of [m] for which [T' n T'r = n S for all S, E C CK+2] Then there is some subset U S [m] of size k 2 for which (Ts) Ct as (unordered) sets.
4
4
5
6
4
1
4
6
2
4
2
4
6
1
2
3
2
4
2
3
6
2
4
6
3
6
4
6
2
3
5
6
2
4
6
2
6
Table I: Illustration of the sequence of subsets constructed in the proof of Lemma B.11 for k = 4. Red and blue denote So and Si, purple denotes Sa. for a [1,2], {k + 1, + 2}, green denotes the 4k 8 sets S", and gold denotes the (k-2) = set S
Proof. For the reader's 's convenience, we illustrate the sequence of subsets constructed in the follow- ing proof in Table
Suppose without loss of generality that contains the sets S1.2 - {1...., k} and 1,42 A {3, .... t + 2} (the indexing will become clear momentarily). We will show that {T's] Ck for U- 2].
Let 5* A Son St. For any S" E Ck++2 satisfying |So nS nsl = 1-1, observe that S" contain S* and element from each of So)SS, (1,2) and S (Sn (k + 1, k 2}, so there are four such choices of 5", call them [Subhaet1.,,.0et4H... them.
and J must contain all of
Now consider any subset S" C [k 2] for which, for some * b' E t + 2}, we have that IS" n S1.2| = SS" n S1 | = SS n S2,1
1, and S" Sk+1A42| 2. Observe that must be that s= - there are 2 (k=2) 2k- 4 such choices of S", and JF must contain all of them. We can similarly consider 5" for which, for some + a' (1, have that 1S" S IS" S
S S
IS" n.S I --2.
and that S" contains {1,2]. so
18

---

Published as a conference paper at ICLR 2021
S S. = 1S" n S s 2k 4, for which there again 2k: 4 choices of 5", and FF must contain all of them.
|S S.S.,t22l = k and |S" n S1,21 SS n
Alternatively, if F contained k 2 subsets S" satisfying |S" n S1.22 = 1s" n Sb,4+1l = Is" n S6,4+2| = k - 1 for some b E {1, (), then it would have to be that any such S" contains the k elements of (b.3..... k). and therefore the intersection between any pair of such S" must be equal to k The same reasoning applies to rule out the case where contains k - 2 subsets s" satistying |S" SS = |5" n S1,11 = |S" S2,11 k- 1 for some b { + 1, +).
violating the constraint that [Ts n Tsl |S S"| for all S,5' E C(++2)-
Finally, consider the set of all subsets S distinct from the ones exhibited thus far, and for which 1S n Sol = =S" n S 1S n Sa,al = k 2 for all a {1.2}.b {kr + 1, k + 2) and 1S" n.s" for at least one of the 4k - 8 subsets constructed two paragraphs above. Observe that any exhibited thus far which satisfies the first constraint must either contain S* and two elements outside of {L...., k + 4}, or must satisfy 1S n S* k - 4 and contain 21,2, 1, 2). In the former case, such S would violate the second constraint. As for the latter case, there are (b-2) such choices of S"" and must therefore contain all of them. We have now produced 4h: + (k=3) (k++ unique subsets, all belonging to C (k+2p
S distinct from the
and JF is of size
( concluding the proof.
B.5 EXISTENCE OF A FLORAL SUBMATRIX
Recall the notion of a floral submatrix from Definition 3.1. In this section we show that with high probability M contains floral principal submatrix. In the language of sets, this means that with high probability over a sufficiently long sequence of randomly chosen size-k subsets of [m]. there a collection of (k+2) subsets in the sequence which together comprise all size-k subsets of some U S [n] of size lo + 2. Quantitatively, we have the following:
Lemma B.12 (Existence of a floral submatrix). Let m 2 M(KOW)) If sets Ti,... Tm are independent draws from the uniform distribution over C% then with probability at least 9/ 10, there is some U + for which every element of Ct is present among Ti, Ti...., Tm.
Proof. Let L = (1x2)
(k+ + 1). Define
Σ
[TT...... Ti,} = ct for some U E cltt
i E
By linearity of expectation, E[Z] is equal to (").) times the probability that (Ti, ..., Tz} Cj.y for
some U [lj] The latter probability is equal to (442)
L!
(M)
so we conclude that -L
m
T.
E
L!
L
k + 2)
k
x22
L! (k!)
2 m
nL
L4 (k + 2)k+2
2 Q (m 'n k+2 bb)
2 2 9(1),
where in the penultimate step we used that
2 2 (k+2)++ is nonnegative and increasing over 2 2,
and in the last step we used that 2 Ω
..., R²))) Without loss of generality, we may assume these are (1, L) and (s+1, L) for some 0 < S L. In order for (Ti,.., Tr} Cj and (Tz-st1, T2t--41} = Cb., for some U, U E C it must be that (T.. Ty.. = ch Note that if IU n U'| = & + 2, then U = U and therefore s
We now upper bound E E Consider pair of distinct summands (f1,..., iz) and (ii
must be 0. So if 0, it must be that IU n n (k, k + +1.
19

---

Published as a conference paper at ICLR 2021
In either case, the probability that (Ti,..,TT Tu-o11) Cy Coner and (Tz-s+1, ... Tr} Conu is
Ct Cinni {TI+1, T2c-st13
-2L+s
(L s)}? s!
S L!? (k/n)))2.
TV n nnI = k, then must be 1, and there are
2 2
n
S n 4+4
k
2
choices for (U,U". If IU n = k + 1 then must be k: + and there are and there are
k 1+11 (n k - 1) (n k - 2) s n k+
choices for (U.U').
Finally, note that there are (7) pairs of summands (i1, it); (f/,... ['y) for which 8 = 0 (namely the ones for which in = 12 for j), m (7-1) (2=1) S O(m)2i. 21 L!² pairs for which s 1, and ( (4+1) ((====)- (,m==1)) S ((m)22-2 k-1 L!a for which k + 1. Putting everything together, we conclude that
E[Z²]= = E + (mm)2t-1 L.t +4 +4, (t/n)22k-- + (mm)2 L1 ++3 (k:/n) 2kk
s E (1 O(1mm) L!d 222L +011/ L!a 2262 (26b-b(k11) 222-1)
s (1.01 (1,01E|2))?
where in the last step we used that S 12t and that n =1 - /m h+1 By Paley-Zygmund, we conclude that
because m 2 k0(h")) ;
E 2
PIZ > 0.01 E| 2 0.99²
2 9/10,
as desired, upon picking constant factors appropriately.
Lemma B.12 implies that with probability at least 9/10 over the randomness of the mixup vectors w....., Wm. if m 2 2(<0(k2)) k- wfr), then there is subset of [m] for which the corresponding principal submatrix of WWT is floral. By Lemma B.7, with high probability M = k. &.W. so this is also the case for the output of GRAMEXTRACT.
B.6 FINDING FLORAL SUBMATRIX
As mentioned in Section 3, to find a floral principal submatrix of M, one option is to enumerate over all subsets of size (k+2) of [ma]. which would take n o(k") time. We now give much more efficient procedure for identifying floral principal submatrix of M, whose runtime is dominated by the time it takes to write down the entries of M. At high level, the reason we can obtain such dramatic savings is that the underlying graph defined by the large entries of WWT is quite sparse, ie. vertices of the graph typically have degree independent of k.
We will need the following basic notion:
Definition B.13. Given i E [m] and integer 0 s l, Net & {j (w,, wy) = t/k}. For any j e NY, refer to i and t-neighbors (this relation is obviously commutative).
We will also need the following helper lemmas establishing certain deterministic regularity condi- tions that WWT will satisfy with high probability.
then with probability at least 1 2md over the randomness of W1, ... Wms have that for every E [m], there are at most O(m +++1 n 1 -k) of j.
Lemma B.14 (Hypergraph sparsity). For any 8 > 0, if m 2 n n
) (I: - (te-1)-neighhee neiihhoss of j. and at most O(m k+2 n² 2-k) (Ie ((e-2)-nnete -eenihoos
20

---

Published as a conference paper at ICLR 2021
54
Illustration of house (i: Ji: j2, J3. j1) where the solid lines indicate entry of in M, while the dotted lines indicate an entry of 2.
Figure 2:
Proof. We will union bound over j E [m]] so without loss of generality fix j in the argument below. Let Xy (resp. Yy.) denote the indicator for the event that and j' are (k 1) -eeighooss (resp. (k: 10-22 -eighbbgb..s). As wiy is sampled independently of W1, conditioned on w1 we know that Xy is
Bernoulli random variable with expectation E[Xp'] k(n-k)
n g++1, where the factor of
(2)
k(n k) comes from the number of ways to pick supp( (u))) (upp(un))(supp(pe))) (sspp(wy))) and (appp(()))\supppl Similarly, Y is Bernoulli random variable with expectation E|Y,-] (²)(² S 2 k4+2
(2)
By Chernoff, we conclude that Σド'2 X, > 2n kk A with probability at most
exp (-m- D(Ber(2n !-k * Ber(n" k ))) - exp(-0(mm' . k*+l))
s exp( exp(((((m--t))
from which the first claim follows. Similarly by Chernoff, Σ3> Y3 2n k with proba- bility at most
exp (-m- D(Ber(2n2~+ | x v exp( exp(-9(mm22+) . k*t2)
S exp( exp(-9((mn2-b))
from which the second claim follows.
Definition B.15. Given symmetric matrix M E mmxm and distinct indices J....... j4 E [m]] for which < J4, say that (i:ji..... (4] is house (see Figure 2) if for all < b S 4, Mj..i = k - (a, b) E (11,2 2), (2, (2, (3, 4), (1,4)) and Mj.sh = k - 2 otherwise, and furthermore M. = for all E [4).
Lemma B.16 (Upper bounding the number of houses). If m 2 2(n then with probability at least 9/10 over the randonness of Wi,..., Wm. there are at most O m n -k422 houses in M.
Proof. Define
2
Σ
[(isi,.... ... .4) is house].
$J.....f distinct,fi
By linearity of expectation, E|Z] equal to m- mm-1) S m times the probability that 2,; house. Note that the only way for (1; 2, 5) to be house is if there disjoint subsets
S.S 2. C [n] of size 2, 2, and 2 respectively such that wi supported on U T and each of W2, ...; Wa is supported {8i, 82) U T where 81 St, 82 Sz. There
21

---

Published as a conference paper at ICLR 2021
(4_2)) (2) I n 2+ such choices of S2, T), and for each is an O((x) - chance that the supports of w1,.... Wy correspond to a given (S1, T),, so we conclude that
(%) k:
-5
E|Z| = O m A-2
S 0(h5k m n 4k+)).
We now upper bound E E[ Consider a pair of distinct summands (i; (i:j...... (4] and
Hi....... (d. Recall that they correspond to some (S1, T) and (51,5% T') respectively. Note that if these tuples overlap in any index (e.g. (1;2,3,4, 4, and (6; 1, 8, 9)), then [(S] U US2 UT) (S) U. T 2 k. There are at most
n
h
2 2
) (1 (
n - k 2
k (++))
k (
n1 ("T*)
n -- ("
k n )) S 5((
k
2
pairs of sets U, U' C
[T]] of size k. + 2 with intersection of size at least k, and given a set U of size (k+2) S poly(k) ways of partitioning U into three disjoint sets of size 2, 2,
+ 2. there are O and k - respectively, We conclude that any pair distinct summands in the expansion of E[2
altogether contributes most poly(k)- O(n++)) (2) -b I k10kk n-nnnnn-0000 (6-1)k+4 where 6 S b < 10 is the number of distinct indices within the tuples (i; (i;J1,.... ja) and (i'; H....... ..). For any 6, there are (5) (5--)) I m2 such pairs of tuples.
In the special case where b = 6, we will use slightly sharper bound by noting that then, it must be that S₁ U S2 UT and S U S T are identical, in which case we can improve the above bound of (n++++) for the number of pairs U, U" to O(n
We conclude that
10
E[Z²] < E + k 10k 6.
5k42
Σ m² n (b- 1)-1) ~O(k mm 10 8K -K+4)) b=7
where in the last step we used the fact that m 2 O(n2k/3) and h: 2 2 to bound the summands
corresponding to b 6 and b 7. Finally, by our bounds on E[Z] and E E| we conclude by
Chebyshev's 's that with probability at least 9/10, there are most E I O m² 4k + houses in M.
Lemma B.17 (Finding a floral submatrix). Suppose m R(n ((n). With probability at least 3/4, SANDFLORALSUBMATIIN
runs in time O(n2k- -.T exp(ppol((k)) and outputs (k+t2) (k+2)- sized subset I S. [m] indexing principal submatrix of M which is floral, together with a function F:I Ch 2k+ such that M (F() n F(j')) for all j,j E EI.
Proof. The proof of correctness essentially follows immediately from the proof of Lemma B. while the runtime analysis will depend crucially on the sparsity of the underlying weighted graph defined by M, as guaranteed by Lemmas B. 3.14 and B.1 Henceforth, condition the events of those lemmas holding, which will happen with probability at least 3/4.
First note that if one reaches as far Step 20 in FINDFLORA SETTTLRRRASUMMAARRI then by the proof of Lemma 11 the I produced in Step 22 indexes a principal submatrix of M which is floral. The recursive call in Step 24 is applied to submatrix of M whose size is independent of n, and it is evident that the time expended past that point is no worse than some exp(poly (k)), and inductively we know that the resulting F' produced in Step 25 when the recursion is complete correctly maps indices j E [m] to subsets in Cj [k++2] such that M, [F()) n F(j')l for all j.J E I.
To carry out the rest of the runtime analysis, it suffices to bound the time expended leading up to the recursive call. Consider any house (fo;j1, fa, j4) encountered in Step 5. First note that one can compute Nu=I-Whh1 with a basic hash table, so because the first part of Lemma B.14 tells us that with high probability, ja | < 0(m kk+1 -=²=)) for all [4], Step only requires
O(m kk-1 -n" - time. Similarly, for each of the O(1) possibilities in the loop in Step 14, takes O(m kk-1 - time enumerate over (k neighhoss of iz, fay ig in Step 15 and, by
22

---

Published as a conference paper at ICLR 2021
the second part of Lemma B.14, ( k*+2 >n²=k) time to enumerate (k: neighhors of 81-2, by, 86, and takes pkly(k) to check that the resulting indices are not all (k - 1) neighboss of each other. And once more, in Step 20 it takes O(m kk+2 n =²²=k) time to enumerate over all indices which are (k
neighbors of io, and of every i" I
We conclude that for every house (4o: J2: J3. FINDFLORALS SUBMATRIX expends at most
O k =)==)) time checking whether the house be expanded into set of indices corre- sponding to floral principal submatrix of M. Note that for any (in; f1, j2, j3. j4) encountered in Step 4 which is not a house, the algorithm expends O(1) time. As W 14*-11
| S O n n--k k
with high probability for any io. there are most Om . m² .n 1k 1 < ( nn 2 p k. such tuples which are not houses.
And because Lemma B.16 tells us that with high probability there are O m 4k 22) houses in M, WANDFLORALSUBMATE
outputs None with low probability. In particular, given that any single house (&o: J1 J2, Ja. 54) expends (( 10mm-k--2 1. n time from Step 9 all the way potentially to Step 24, we conclude that the houses contribute a total of most O mm n -4442 m mn-k-*4 k n² O( n 4- 5k 2
2) the runtime.
Putting everything together, we conclude that FINDFLLORA. runs in time
O (m3 .
b.++4 4 + m .n 4-55k 1.k+2) O - 2O(K))
Lastly, note that +
10 141 S E+T whenever 2 2, completing the proof.
B.7 PUTTING EVERYTHING TOGETHER
We are now ready to conclude the proof correctness of our main algorithm, LEARNPRIVATEIM-
AGE.
Proof. By Lemma B.4, the subsets S; computed in Step correctly index the public coordinates of wy By Lemma B.7, with high probability over the randomness of X, the matrix M formed from GRAMEXTRACT in Step of
is exactly equal to the Gram matrix WWT, so after Step 5 and Step M is equal the Gram matrix of the vectors [wi]s,,... [wm]s-. sr. i.c. the restrictions of the selection vectors to the private coordinates. We are now in position to apply the results of Sections B.3, B.4, B.5, and B.6.
By Lemma B.17, with high probability the output I, F of FINDFLORALSUBMATII satisfies that 1) the principal submatrix of M indexed by I, set of indices of size (Ruii++2) is floral, and 2) the function
in Step
kpp
Chaci C satisfies that [F()) n F()1 = M., for all i, I. By Lemma B.11, because the principal submatrix indexed by I is floral, there exists some subset U C [n] of size kpriv + 2 for which the supports of the mixup vectors wy for j I are all the subsets of U of size kiriv- Finally, by Lemma B. and the fact that the entries of X are independent
[d], the solution {a!() to the system in Step satisfies that there is some column æ of the original private image matrix X such that for every E [kpriv + 2},
Gaussians. for every pixel index
1 is, up to signs, equal to the L-th pixel of æ.
Note that the runtime of LEARYPRIVATHIMAGE is dominated by the operations of forming the matrix M and running FINDFL.ORAL.SURMATRIX which take time O(m²) by Lemma B.17. Ll
B.S EXAMPLE OF FLORAL SUBMATRIX
Example B.18. For & = 2, the following 6 x 6 matrix, after dividing every entry by k is floral:
[1,3}
{2,
4]
{1,4)
{1,2]
{3, 4}
{2.3)
(1.3)
2
0
[2.4]
0
[1.4]
1
1
2
0
112)
1
1
(3.4)
1
1
{2,3}
1
1
0
2
23

---

Published as a conference paper at ICLR 2021
Algorithm 3: PINDFLLOR.LSSUMMTIIIN,,, K, r)
Input: Query access to matrix M E RRM sparsity level k-
Output: (*++)) x ) subset I _ [M], function F I - Ck [K++2] (Lemma B.17)
Nhouses f O.
for in E [M] do
F(io) fl,..,,)] k:].
for ji,...-.Je .J4 in N for which ji < j4 do
if (fo: J1, fo, J4) is house then
Nhouses f- Nnouses + 1. if Noouses S2(k M 4k+2) then return None.
8
I' J3.
if = - + 0 then
Let i be the (unique) element of N N, "
I" + 0.
F(ii) + k......k-22) 2}.
for = E (0. and distinct a, 3,,,7,8 E [4] for which a < B and in (resp. is) is a (k - ----eigghb i ia (resp. ig), and for which in a, 3 are (k -e-nighoorrs and i, ô are (k- -)-neighboors do if exactly k- k- choices of which are (k -eiiihhorr of ig las ig and (k: - -2i-neighbors by ig, and which are not all (I- -einiihhs of each other then Add to I" all such t".
if I 4k - 8 then
If = 0, set F(ia) +- (1,3, ..... k, k, 1).
F(ig) + (..3....,k k + F(i,)) + f1.3....,k,k 2}, and
F(is) + (2.3....k,k+ 2].
If 1, set F(a,) - (1,3....,k k, + 1}.
F(ig) (1, 3, k k +
F(ix) (2,3, ...,...,,,,, k. 1) and
F(is) < .......,.++2
if exactly (1=3) choices of i" which are (k- 2) neighbors of in, in ia.
ig. by. and igg and which also (k- -e-neghsorrs of at least one
8" E I" then
Let I" denote the of such i"!
I {du, UT' U UI"
Let Maub denote the (x=3) x (#2 submatrix of M given by restricting to the rows and columns indexed by I" and subtracting
4 from every entry.
24
sub, 2). For every i" E I set F(i")) <- G(i") U (1,2, k + 1, + 2}.
26
return I, F.
24

---

Published as a conference paper at ICLR 2021
Algorithm 4: LEARNPRIVATEIMMGGEC X,; X hxe(m)
Input: InstaHide dataset { hiefm]
Output: Vectors T1,..., 3x+2 I equal to k + images (up signs) from the original
private dataset
M -GRAMEXTRACT(Y J. t
Apii
for i E (m] do
L S, LELARNUULLIC(((pssss b5)))(4))))))))
for i,j [m]] do
Mi, + Mij Kpab
1 [8 SyJ--
M Kpriv M.
I, F -FINDFLORALSSBMMARRXXY.
For every pixel index E [d]. solve the system of equations Eiero) x
Ve X,ns
in the
variables ! + for all j E I.
For every image index i E pKri 2], let 3. Rd denote the image whose f-th pixel is equal to
((()
10 return 21 +2
C ADDITIONAL EXPERIMENTAL RESULTS
0.9
0.8
0.
0.0
0.8
Son
mikap Irain
MEMU Eun
mikap
mius
DESE
0.0
0.6
Tota
0.6
D.C.
0.3
#cot
spoch
#poch
e2cch
(a) l:
(b) k =
(c) k
k=
0.9
0.9
0.9
6.9
0.8
Con
mikup trai
20.
train
maaup tran
mixap
manup de
0.6
Ituis..
0.
0.6-
Iratunide
TotaMAlL
0.5
45oth
epoch
esoch
eacch
(e) ls 5
(l) k 6
(g) A:
7
(h) h:
Figure 3: Comparing Vanilla, Mixup and Instahide training on Gaussian magnitude dataset with different k.
25

---

Published as a conference paper at ICLR 2021
0.6
Inttanide
Inerah
0.8
08
mane
0.5
instlili trals
nota Jain
Jest
nota 2est
0.5
0.5
20
130
0.5
102
(a)
(b) 1: 2
(c) k
(d) l:
1.0
1.0
instakie__rah
Instahide,
0.8
20.
0.6
0.
0.
20
05
60
300
0.5
102
(e)
(f) k
(g) l:
(h) l:
Figure 4: Comparing Vanilla, Mixup and Instahide training on Gaussian dataset with different k.
26


Reviews:
[{"review_id": "kiDCuvXdBwO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper examines the security of a recently proposed privacy scheme, InstaHide Huang et al. 2020, that can be used to generate synthetic training data. Under a standard Gaussian distributional assumption on the data, the authors propose an algorithm that can extract private information from the synthetic vectors generated by InstaHide.\n\nComments:\n\nInstaHide is a recently proposed technique Huang et al. 2020, that aggregates local data into synthetic data that can both preserve the privacy of the local datasets and be used to train good models. InstaHide assumes presence of both public feature vectors (e.g. a publicly available dataset like ImageNet) and a collection of private feature vectors (which we want to hide). This scheme is based on an interesting looking idea, and also seems to achieve good empirical performance (in that by training a network like ResNet on the generated synthetic data one can achieve good test accuracy on the real data). This paper investigates the security properties of the InstaHide scheme. The main result shows that if the public and private data are both drawn from an i.i.d. Gaussian distribution then it is possible to reconstruct (some of) the private data if we have the access to output of the InstaHide on multiple queries and public data. The reconstruction is correct up to sign of the coordinates..\n\nThis is an interesting result, implying that a careful discussion of security for InstaHide should be sensitive to the properties of the distributions generating the private and public feature vectors.\n\nThe paper is well-presented, however, most of the interesting theoretical results are in the appendices. The idea behind the reconstruction can be broken into four steps: a) identify the public coordinates of the selection vector, b) construct the Gram matrix of the selection vectors, c) identify a particular submatrix of the Gram matrix, and d)  use this particular submatrix to identify private feature vectors.\n\nI have not verified all the technical details, but overall the reconstruction idea looks sound. The theoretical results are also backed by some simple proof-of-concept experiments. \n\nSome questions:\n1)\tWould have nice to see the formal statement of the primary theorem in the main paper. Also what is the overall probability of success in Theorem A.1?\n2)\tCan be the Gaussian assumption on the X matrix be relaxed to a subgaussian assumption. \n\nSide-remark: I thought the title of the paper is slightly misleading. The result is specific to InstaHide scheme and is not a general statement about private distributed learning.", "extra_scores": {}, "extra_text": {}}, {"review_id": "h6TwTBGr_2d", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the security of InstaHide, a recently proposed algorithm for scrambling a secret image data set so that it is still useful for learning but doesn't allow inferences about individual images in the data set. \n\nThe paper provides an algorithm that takes the output of InstaHide, and reconstructs the secret images (in a particular parameter regime of very high-dimensional data). The attack works by reduction to a new variant of the phase retrieval problem with hidden inputs.\n\nThe paper's results appear to be correct. I am not familiar enough with the phase retrieval literature to judge the technical novelty and interest of the new problem variant and algorithm. The authors claim that the new variant is of independent interest, but don't really spend time justifying that.  I remain neutral on that point. \n\nHowever, I disagree strongly with the authors' interpretation of their results for InstaHide's security, and do not think that they rise to the level of significance appropriate for ICLR.\n\nTo explain the setting a bit: InstaHide starts with two data sets of images (vectors in $\\mathbb{R}^d$)  called the public and private data sets, each of size $n$. Given parameters $M$ and $k$, it produces $M$ synthetic output images. For each output image, one does the following:\n1. select $k$ public images and $k$ private images (uniformly at random)\n2. let $y$ be the sum of the selected images\n3. Output a synthetic image $|y|$ consisting of the absolute values of the entries of $y$. \n\n(I've simplified the scheme a bit—the $n$'s and $k$'s can be different for the public and private data—but the simplifications don't change this discussion.) \n\nThe paper mentions $k=2$ as a reasonable value.\n\nThe attack recovers the synthetic data set roughly when $d$ is reasonably large (at least $poly(k)\\log(n)$) and when $M$, the number of synthetic data points, is very large (something like $n^k$). As mentioned above, the algorithm appears to be correct. \n\n**On InstaHide's security**\n\nI disagree with the authors' claims of their results' significance for security. I doubt that this paper would be acceptable at, say, a security or cryptography conference. \n\nThe main issue is that InstaHide looks broken to begin with, even when only 1 image is output. \n\nThe submission's main question is *\"Under what settings can we rigorously prove that InstaHide preserves security of the private datasets used to generate the synthetic vectors?\"*. Asking such a question requires first answering a seemingly much more basic question: *\"What **clear, refutable conjecture** could one make about InstaHide's security that is both (a) sufficient to suggest it is reasonable to use on sensitive data and (b) not obviously false?*\"\n\n\nUnfortunately, I'm not sure there is such a conjecture. For InstaHide to be a reasonable approach to image data privacy, it should be hold up to settings where an attacker knows quite a bit about the format of the input. Suppose, for example, that the images themselves are \"sparse\" in the following sense: each consists of small grayscale image, randomly placed on a much larger black background. Then the linear combination of a small number of them would also be sparse with high probability, and its absolute values would exactly reveal all of the component grayscale images. One would start getting attacks with $M=1$. For a more realistic but messy example, consider a setting in which the images are screenshots where most of each screen is text but  sensitive pictures may appear in different parts of the screen. Finally, Matthew Jagielski shared the following notebook with many people (including the authors of InstaHide) which works out a simple example with 2 images:\nhttps://colab.research.google.com/drive/1ONVjStz2m3BdKCE16axVHZ00hcwdivH2?usp=sharing\n(The images, one of a dog and the other of a bird, are easy to pick out from the absolute values of the combination.)\n\n**Implications for this submission**\n\nBecause of the known problems with InstaHide,  it's not clear to me what light the submission really sheds on InstaHide's security. The example attacks above shows that it isn't hard to find natural distributions and settings of $k$ for which InstaHide allows recovery of the inputs. (Aside: doesn't the requirement of $M\\approx n^k$ makes this attack unlikely to be practical, unless very small $k$ is necessary for utility?) The question in my mind is whether any reasonably robust security or privacy claim could be made. The last twenty years have seen major advances in how to formulate such claims, but those advances are not reflected in either the original paper or this follow-up.\n\nI would encourage the authors to rethink the framing for the question they address. Perhaps they can argue that the complexity of their setting is important for understanding InstaHide's security, or perhaps they can make a case that the new phase retrieval problem and algorithm are interesting in their own right (and rewrite the paper as a function of that)? Absent such a reframing of the paper, I don't think it should be accepted. \n\n**Minor Comments**\n\n* Page 2:  \"to ensure we are not working in an uninteresting setting where InstaHide has zero utility, we empirically verify that in the setting of Theorem 1.1, one can train on the synthetic vectors and get good test accuracy on the original Gaussian dataset\". It is fine to do experiments in the setting where InstaHide is useful, but ensuring high utility would seem to me to make attacks easier, not harder.\n\n* Page 3: \"consider the extreme case where InstaHide only works with private feature vectors[...], so that the only information we have access to is the synthetic vector generated by InstaHide. In this case, it is clearly information-theoretically impossible to recover anything about [which combinations were chosen] or the private dataset.\" I strongly disagree. I don't see why that's true in the Gaussian setting—isn't the mutual information between the synthetic data and the secret data infinite (since the coefficient vectors are discrete)? In any case, the \"sparse images\" setting above gives a simple illustration of how absolute values of linear combinations can leak tons of information.\n\n**Follow-up to author comments**\n\nI appreciate the authors' thoughtful response. While I agree on certain points, I am not convinced that the paper, as currently written, is ready for acceptance to a venue like ICLR. (That said, I also still believe the paper's core technical claims to be correct; my question is about significance.)\n\nThe paper's premise is that reconstruction attacks on InstaHide deserve extensive investigation. I'd like to see justification for that premise. To be absolutely clear: I strongly believe that techniques (like InstaHide) which attempt to provide security against moderately strong attackers deserve discussion and investigation. However, I also believe that the starting point for such work should be a careful attempt to formulate security goals. I don't see how the current paper advances the important parts of that discussion. The focus on reconstruction is narrow; my score reflects that.\n\nTo add just a little bit to my review: InstaHide is best viewed as a proposed lightweight alternative to multiparty computation (MPC). MPC protocols allow participants to compute on shared data in a way that reveals nothing but the final outcome of the computation (tools like FHE, to which InstaHide's authors compare it, can help achieve that goal but are not qualitatively different). \n\nMPC protocols (and InstaHide in particular) say nothing about how much is revealed about the data by the final trained model (the \"ideal functionality\", in the language of MPC). There is at this point a large literature showing that models themselves leak information in surprising ways (membership inference, to pick an example that received recent attention).\n\nEven if we focus on \"lightweight MPC\" as the end goal, the literature on data privacy suggests a wide range of more sophisticated measures of security than resistance/vulnerability to reconstruction. (That is, it's interesting and potentially important to relax the goal of full simulation that one normally aims for in MPC; but then one should spell out what the relaxed goal is, why it's sufficient for some settings, etc.) This submission reflects none of the past decades' lessons on that count. \n\nResponding to specific points: \n\n* I was not comparing to the paper of Carlini et al. I assume that this submission and the manuscript of Carlini et al are independent. \n\n* (Minor point) I'll stick by my complaint about Page 3: \"it is clearly information-theoretically impossible to recover anything about [...] the private dataset.\" I understand and agree with the math of the rebuttal, but not with the conclusion. To spell out my original objection: Let $V=(V_1,V_2)$ be the random variable consisting of the two private images, and let $W$ be their average. It is not true that the mutual information $I(V;W)$ is 0 (which is the natural meaning of \"no information about the data set\"). It is not even true that $I(V_1;W)$ is 0.  Concretely, learning $W$ makes certain pairs of images much more likely than they were a priori. Whether that's ok depends on the context, what else is likely to be  known about the images, etc. My point isn't that one released image will lead to a practical attack; it is that information leaks in lots of ways. If you want to claim that leaked information isn't useful for an attack, that requires a clear notion of \"useful for an attack\" (and possibly a proof, though that's less important than a clear claim).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RJC2SJSxGvC", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the security of private datasets is considered. Huang et al. (2020) proposed InstaHide for this problem. The InstaHide can be summarised as follows:\n\nFrom a random convex combination of k_pub public and k_private vectors,\nMultiply every coordinate of the resulting vector by an independent random sign in {+-1},and define this to be the synthetic feature vectors.\nIn the paper, the authors try to understand InstaHide by phase retrieval. The main result of this paper is to show when the private and public data is Gaussian, then they can recover the private feature vector form the given synthetic dataset and the public feature vectors\n\nI think the topic is good. Under many situations, we should focus on security of private information. But in practice, the public and private dataset can be any. The assumptions in this paper may be not correct. The problem of recovery of private vector can indeed be considered as a phase retrieval problem from public vector and the synthetic dataset generated from InstalHide. I think it is the affine phase retrieval or phase retrieval with background information.", "extra_scores": {}, "extra_text": {}}, {"review_id": "70atQUgGlZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The purpose of the paper seems clear: it proposes an attack to the recently proposed algorithm called Instahide (ICML 2020) which is a probabilistic algorithm for generating synthetic private data in the distributed setting. The attack proposed in this paper is considered for the case where the private data is i.i.d. Gaussian distributed, and Thm 1.1 says that one can recover k original feature vectors with O(k^2) + O(M^2) computational complexity, where M is the total number of original data elements.\n\nAlthough the original paper describing Instahide proposes few attacks and has some analysis for them, and revolves around the probabilistic notions of privacy, it lacks any rigorous privacy guarantees for the hiding algorithm (e.g. differential privacy (DP) guarantees) and the illustration of the performance of Instahide seems to be only heuristic. \n\nThis paper gives an attack which underlines the fact that theoretical guarantees of the kind given by DP are indeed very important. As there is an attack for the Gaussian case (as given here), the assumptions on the distributions of the original data have to be something different if theoretical guarantees for Instahide are desired.\n\nThe experiments with small dense neural networks are mainly to illustrate the that in the setting of the assumptions used is not useless in a sense that it is possible to train a neural network to perform classification with data satisfying the assumptions.\n\n I think the paper is very well written, and, although I didn't read in detail all the proofs given of Appendix, those I read seem to be correct and I have no reason to suspect there are errors.\n\nMy only slight concern is whether some more theoretically oriented venue would suit better for this paper than ICLR, however the topic is very relevant to ICLR.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers an attack of the recently proposed InstaHide algorithm mixing up public and private images by convex combination to achieve security of sensitive data. The paper formulates the problem as a multi-task phase retrieval problem with missing-data, and shows that under Gaussian data distribution setting, we can recover a small number of private data samples given sufficiently large dimensionality and number of synthetic samples output by InstaHide.

Theoretically, the Gaussian data distribution is quite restrictive in practice, but it could be a good start. The paper also uses some novel techniques in the analysis, which meets the technical standard of ICLR. The reviewer mainly concerns about the general motivation and formulation of "security" studied in the paper, since attacks can be trivial in practical scenarios where data is non-Gaussian, which reveals a possible weakness on practical value of this work.


Although the work is probably better suited for a theoretical-oriented conference, I nevertheless feel it should be also acceptable for ICLR because it specifically addresses a recent distributed learning problem and the results are non-trivial and improving our understanding of the InstaHide's security.
Decision: Accept (Poster)