Anonymous Learning via Look-Alike Clustering: A Precise Analysis of Model Generalization
Authors: Adel Javanmard
Vahab Mirrokni
Venue: NeurIPS 2023 poster (2023)
Keywords: high-dimensional regression
generalization error
asymptotic analysis
Convex Gaussian Minimax Theorem
regularization
TL;DR: A precise characterization of the effect of look-alike clustering on the generalization property of the model

Abstract: While personalized recommendations systems have become increasingly popular, ensuring user data protection remains a top concern in the development of these learning systems. A common approach to enhancing privacy involves training models using anonymous data rather than individual data. In this paper, we explore a natural technique called "look-alike clustering", which involves replacing sensitive features of individuals with the cluster's average values. We provide a precise analysis of how training models using anonymous cluster centers affects their generalization capabilities. We focus on an asymptotic regime where the size of the training set grows in proportion to the features dimension. Our analysis is based on the  Convex Gaussian Minimax Theorem (CGMT) and allows us to theoretically understand the role of different model components on the generalization error. In addition, we demonstrate that in certain high-dimensional regimes, training over anonymous cluster centers acts as a regularization and improves generalization error of the trained models. Finally, we corroborate our asymptotic theory with finite-sample numerical experiments where we observe a perfect match when the sample size is only of order of a few hundreds.

Anonymous Learning via Look-Alike Clustering: A Precise Analysis of Model Generalization
Adel Javanmard
Vahab Mirrokni Google Research
University of Southern California, Google Research ajavanmaQusc.edi
mirrokni@google... com
Abstract
While personalized recommendations systems have become increasingly popular, ensuring user data protection remains a top concern in the development of these learning systems. A common approach to enhancing privacy involves training models using anonymous data rather than individual data. In this paper, we explore natural technique called look-alike clustering, which involves replacing sensitive features of individuals with the cluster's average values. We provide a precise analysis of how training models using anonymous cluster centers affects their generalization capabilities. We focus on an asymptotic regime where the size of the training set grows proportion to the features dimension. Our analysis is based on the Convex Gaussian Minimax Theorem (CGMT) and allows us to theoretically understand the role of different model components on the generalization error. addition, we demonstrate that in certain nigh-dimensional regimes, training over anonymous cluster centers acts as regularization and improves generalization error of the trained models. Finally, we corroborate our asymptotic theory with finite-sample numerical experiments where we observe a perfect match when the sample size is only of order of few hundreds.
Introduction
Look-alike modeling in machine learning encompasses range of techniques that focus identifying users who possess similar characteristics, behaviors, or preferences to a specific target individual. This approach primarily relies the principle that individuals with shared attributes exhibit comparable interests and behaviors. By analyzing the behavior of these look-alike users, look-alike modeling enables accurate predictions for the target user. This technique has been widely used various domains, including targeted marketing and personalized recommendations, where plays a crucial role in enhancing user experiences and driving tailored outcomes [26, 19, 18. 21].
likely to
In this paper, we use look-alike clustering for a different purpose, namely to anonymize sensitive information of users. Consider supervised regression setup where the training set contains pairs (x;, y:), for i [n], with y: é R denoting the response and 2; e Rd representing a nigh-dimensional vector of features. We consider personal information about users and should be protected from the leaner, and the non-sensitive features. We assume that that the learner has access clustering structure users, which is non-private information (e.g. based on non-sensitive features or other non-sensitive data set on users).
groups of features: sensitive features, which contain some
We propose a look-alike clustering approach, where we anonymize the individuals' sensitive features by replacing them with the cluster's average values. Only the anonymized dataset will shared with the learner who then uses it train model. We refer to Figure 1 for illustration of this approach. Note that the learner never gets access to the individuals' sensitive features and so this approach is safe from re-ide ideniificaaiinn attacks where the learner is given access the pool of individuals' sensitive information (up to permutation) and may use the non-sensitive features to re-identify the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

semuttive
non Ee featurcs
look-aibe reprssercations
non-samativv Teatures
features
Joem1
P1
duster
usors
duster 2
duster
u
14g
Figure 1: Schematic illustration of look-alike clustering on features data, Within each cluster, the sensitive features of users are replaced by a common look-alike representation (center of the cluster). In this example, μl, p22. Aaa represent the average of the sensitive features vectors for users in cluster 1, 3.
users. Also note that since a common representation (average sensitive features) is used for all the users in a cluster, this approach offers m-aanonymty provided that each cluster is of size at least m (minimum size clustering).
Minimum size clustering has received an increased attention mainly tool for anonymization and when privacy considerations are in place [7, 2, 3]. A particular application is for providing anonymity for user targeting in online advertising with the goal of replacing the use of third-party cookies with more privacy-respectinn entity [10]. There are a variety of approximation algorithms for clustering with minimum size constraint [23, 9, 1, 24], as well as parallel and dynamic implementation [10].
In this paper. we focus on linear regression and derive a precise characterization of model gener- alization using the look-alike clustering approach, in the so-called proportional regime where the size of training set grows in proportion to the number of parameters (which for the linear regression is equal to the number of features). The proportional regime has attracted significant attention as overparametrized models have become greatly prevalent. allows to understand the effect un- derroveerprammettizztion in feature-rich models, providing insights to several intriguing phenomena, including double-descent behavior in the generalization error [22, 8, 14].
Our precise asymptotic theory allows us to demystify the effect of different factors on the model generalization under look-alike clustering. such as the role of cluster size, number of clusters, signal- to-noise ratio of the model as well as the strength of sensitive and non-sensitive features. A key tool in our analysis a powerful extension of Gordon's is Gaussian process inequality [13] known as the Convex Gaussian Minimax Theorem (CGMT), which was developed in [30] and has been used for studying different learning problems; see e.g. [29, 8, 15, 14, 16].
Initially, it might be presumed that look-alike clustering would hinder model generalization by suppressing sensitive features of individuals, suggesting possible tradeoff between anonymity (privacy) and model performance. However, our analysis uncovers scenarios in which look-alike clustering actually enhances model generalization! We will develop further insights on these results by arguing that the proposed look-alike clustering can serve as a form of regularization, mitigating model overfitting and consequently improving the model generalization.
Before summarizing our key contributions in this paper, we conclude this section by discussing some of the recent work the tradeoff between privacy and model generalization large. An approach to study such potential tradeoff is via the lens of memorization. Modern deep neural networks, with remarkable generalization property, operate in the overparametrized regime where there are more tunable parameters than the number of training samples. Such overparametrized models tend to interpolate the training data and known to fit well even random labels [34, 33). Similar phenomenon has been observed in other models, such as random forest [4], Adaboost [25, 32], and kernel methods [5, 17]. Beyond label memorization, [6] studies setting where learning algorithms with near-optimal generalization must encode most of the information about the entire high-dimensee (and high-entropy) covariates of the training examples. Clearly, memorization of training data imposes significant privacy risks when this data contains sensitive personal information, and therefore these results hint potential trade-off between privacy protection and model generalization [27, 12, 20]. Lastly, [11] I] studies settings where data is sampled from mixture of subpopulations, and shows that label memorization is necessary for achieving near-optimal generalization error, whenever the
the ability of the model generalize to new, unseen data from the same distribution the training data

---

distribution of subpopulation frequencies is long tailedd Intuitively, this corresponds to datasets with many small distinct subpopulations. In order to predict more accurately on a subpopulation from which only very few examples are observed, the algorithm needs to memorize their labels.
1.1 Summary of contributions
We consider linear regression setting for response variable y given feature æ, and posit a Gaussian Mixture Model on the features to model the clustering structure on the samples. We focus on the high-dimensional asymptotic regime where the number of training samples n, the dimension of sensitive features (p), and the dimension of non-sensitive features (d-p) p) grow in proportion (v/n + up and d/n + Vd, for some constants < < á 4aa). Asymptotic analysis in this particular regime, characterized by fixed sample size to feature size ratio, has recently garnered significant attention due to its relevance the regime where modern neural networks operate. This analysis allows for the study of various intriguing phenomena related to both statistical properties (such as double-descent) and the tractability of optimizing the learning process in such networks [22, 8, 14], where the population analysis n/d oo fails to capture. Let T { (x) e [n]] denote the (unanonymized) training set and T/," be the set obtained after replacing the sensitive features with the look-alike representations of clusters. We denote by 0 and 02 the min-norm estimators fit to T and Tt" respectively. Under this asymptotic setting:
We provide a precise characterization of the generalization error of 0 and or. Despite the random- ness in data generating model, we show that in the high-dimensional asymptotic, the generalization errors of these estimators converge in probability to deterministic limits for which we provide explicit expressions.
Our characterizations reveal several interesting facts about the generalization of the estimators:
(i) For the min-norm estimator @ we observe significantly different behavior in the under- parametrized regime (Na S 1) than in the overparametrized regime (th > 1). Note that in the underparametrized regime, the min-norm estimator coincides with the standard least squares estimator. For the look-alike estimator 0g our analysis identifies the underparametrized regime as tha u & and the overparametrized regime as tha 1/p >
(Hi) In the underparametrized regime, analysis shows that, somewhat surprisingly, the general- ization error (for both estimators) does not depend on the number or size of the clusters, nor the scaling of the cluster centers.
(iit In the overparametrized regime, our analysis provides a precise understanding of the role of different factors, including the number of clusters, energy of cluster centers, and the alignment of the model with the constellation of cluster centers, on the generalization error.
Using our characterizations, we discuss settings where the look-alike estimator 0, has better generalization than its non-private counterpart 0. A relevant quantity that shows up in our analysis is the ratio of the norm of the model component on the sensitive features over the noise in the response, which we refer to as signal-to-noise ratio (SNR). Using our theory, we show that if SNR is below a certain threshold, then look-alike estimator 0 has lower generalization eтror than Ø. This demonstrates scenarios where anonymizing sensitive features via look-alike clustering does 'not' hinder model generalization. We give an interpretation for this result, after Theorem 5.1, by arguing that at low-SNR, look-alike clustering acts as a regularization and mitigates overfitting, which consequently improves model generalization.
In our analysis in the previous parts, we assume that the learner has access to the exact underlying clustering structure on the users, disentangle the clustering estimation error from look-alike modeling. However, in practice the learner needs to estimate the clustering structure from data. In Section 3.2, we combine our analysis with a perturbation analysis extend our results to the case of imperfect clustering estimation.
Due to space constraint, we refer the supplementary material for an overview of our proof techniques well as proof of theorems and technical lemmas.
3

---

2 Model
We consider linear regression setting, where we are given n i.idd pairs (2,,, Bi), where the response y/ is given by
V/ (a:; 0o) + Bi, ; ~ N(0,o").
(2.1)
We assumee that there is clustering structure on features x,, i [m1], independent from the responses. We model this structure via
model.
Gaussian-Mixture Model (GMM) on features. Each example æ belong to cluster é [4:] with probability тe. We let [T, . Te& e R with 0 and 1 π 1. The cluster conditional distribution of an example æ in cluster follows an isotropic Gaussian with mean My E R4, namely
x Mg 2, 2 N(0,7²I).
(2.2)
By scaling the model (2.1), without loss of generality we assume T Writing in the matrix form, we let
X = [22] [..]
y = (v Vn)) R", M [4.|ug)... [ux] Rd*k (2.3)
It is also convenient to encode the cluster membership as one-hot encoded vectors A é R², where A one at entry (with l being the cluster of example x;) and zero everywhere else. The GMM can then be written as
X = MA + Z,
(2.4)
with Z E Rdvn is Gaussian matrix with i.d N(O, 1) entries, and A E Rkxn is the matrix obtained by stacking vectors X; as its column.
Sensitive and non-sensitive features. We assume that some of the features are sensitive for which we have some reservation to share with the learner and some non-sensitive features. Without loss of generality, we write as æ uns), where ag IRP representing the sensitive features and Tas E Rdd-P representing the non-sensitive features. We also decompose the model Ou (2.1) as 0g = (0o,s, fo,ns) with 0o.- IR and Oo.ns Rd-P__ Likewise, the cluster mean vector l is decomposed as f (11,) Mns). The idea of look-alike clustering to replace the sensitive features of an example æ, with the center of its cluster g... This way, if each cluster is of size at least m, then look-alike clustering offers m-anonymity.
Our goal in this paper is to precisely characterize the effect of look-alike clustering on model generalization. We focus on the high-dimensional asymptotic regime, where the number of training data n, and features sizes d, grow in proportion.
We formalize the high- digenssiinii asymptotic setting in the assumption below:
Assumption We assume that the number of clusters l fixed and focus on the asymptotic regime where d, at a fixe ratio d/n + vha and p/ n 10p-
To study the generalization of model 0 (performance on unseen data) via the out-of-sample prediction risk defined as Risk(O) == E - x O))3. where (y, x) is generated according to (2.1). Our next lemma characterizes the risk when the feature is drawn from GMM.
Under the linear response model (2.1) and a GMM for features x, the out-of oa-ple prediction risk of a model 0 is given by
Lemma 2.1
Risk(0) () = o² 110, 01., ()) ( ( M -0)
The proof of Lemma 2.1 is deferred to the supplementary.
3 Main results
Consider the minimum & norm (min-norm) least squares regression estimator of y on X defined by
① = (XxT ) Xyy
(3.1)

---

where (XXT)* denotes the Moore-Penross pseudoinverse of XXX.. This estimator can also be formulated as
i == arg min (101ls, minimizes y- x10 82
We also define the "look-alike estimator" denoted by 0z,, where the sensitive features are first anonymized via look-like modeling, and then the min-norm estimator computed based the resulting features. Specifically the sensitive feature I, of each sample is replaced by the center of its cluster. In our notation, writing X [X] x we define X [(M,A)' X the features
matrix obtained after look-alike modeling on the sensitive features. The look-alike estimator is then given by
Ø = (X XLy.
(3.2)
Our main result is to provide a precise characterization of the risk of look-alike estimator 0 as well as 0 (non-look-alike) in the asymptotic regime, described in Assumption 1. We then discuss regimes where look-alike clustering offers better generalization.
As our analysis shows there are two majorly different setting in the behavior of the look-alike estimator: (i) thd - 1/p á 1, i.e., the sample size n is asymptotically larger than d p. the number of non-sensitive features (referred to as underparametrized asymptotics); (ii) tha up 2 1, which is referred to as overparametrized asymptotics.
Our first theorem is on the risk of look-alike estimator in the underparametrized setting. To present our result, we consider the following singular value decomposition for Ms. the matrix of cluster centers restricted to sensitive features:
Mg = UUEVVVV Ug E RPKE,
EE REK,,E RTXT, Vg E Rixrr with r rank( M.) S k.
Theorem 3.1 (Look-alike estimator, underparametrizee regime) Consider the linear response model (2.1). where the features are coming from the GMM (2.4). Also assume that 10o..l тs and IU_ 0o pprs. for all n.p. Under Assumption I with v'a - th S 1, the out-of-sample prediction risk of look-alike estimator Or,, defined by (3.2), converges in probability,
Risk (0z) P 0² 02+r"
pr
(V'a vp)
There are several intriguing observations about this result. In the underparametrized regime:
1. The risk depends on 0o.- (model component on the sensitive features), only through the norms |00,,sl T, and
/pr.. Note that |U, 0o.s measures the alignment of the model with the left singular vectors of the cluster centers.
0o.s = |
2. The cluster structure the non-sensitive features plays no role in the risk, nor does 0,,us the model component corresponding to the non-sensitive features.
The cluster prior probabilities π does not impact the risk.
We next proceed the overparametrized setting. For technical convenience, we make some simplify- ing assumption, however, we believe a similar derivation can be obtained for the general case, albeit with a more involved analysis.
Suppose that there is no cluster structure on the non-sensitive features ( (Mss 0). Also, assume orthogonal, equal energy centers for the clusters on the sensitive features (M, nUU, with U.U.- U.=
Assumption
Our next theorem characterizes the risk of look-alike estimator in the underparametrized regime.
Theorem 3.2 (Look-alike estimator, overparametrized regime) Consider the linear response model (2.1), where the features are coming from the GMM (2.4). Also assume that 10u..l Ter 100.ss| and [ pr for all n. d. Under Assumption I with vha 1hp 2 1, and Assumption the sumple prediction risk of look-alike estimator o2, defined by (3.2), converges in probability.
Risk(0,) 0,) - p)r 70 +a TT(I+ 1el (ddiag(T))
(3.3)
5

---

where π (T1....., Th) encodes the cluster priors and "o and a R are given by the following relations:
I (ddia((T)
)
U 0..
a
Vd 1/p
(0² r 1²aa (t)g(())x))))))))))))))))))))( + (1 0d 1
2 7O
y2
As discussed in the introduction, one the focal interest in this work to understand cases where look-alike modeling improves generalization. In Section 5 discuss this by comparing the look- alike estimator O2 with the min-norm estimator 0, given by (3.1) which utilizes the full information on the sensitive features. In order to do that, we next derive precise characterization of the risk of ! in the asymptotic setting.
Theorem 3.3 (min-norm estimator with look-alike clustering) Consider the linear response model (2.1), where the features are coming from the GMM (2.4). Under Assumption 1, the fol- lowings hold for the min-norm estimator given by (3.1):
(a) (underpurumettrized setting) If tha $ 1, we have
p o²
Risk (0)
1- v'd
(b) (overparumetrized setting) If vha 2 1, under Assumption 2, the prediction risk o converges in probability
Risk 0 o² + à T y diag(T)))
(3.4)
where To and ε are given by the following relations:
I + 1² diag((T)
ā I
U. 00,3.
1/-
1
(02 a àT(TT (2+ diag( + (1- wol ((1 (11 p)r?+ +ra)).
w
= TK = 1/k), the risk characterization (3.3) depends only through |alle, (and likewise, the risk (3.4) depends & only through its norm). This significantly simplifies these characterizations.
Example 3.1 (Balanced clusters) In the case of equal cluster prior (x) :..=
3.2 Extension imperfect clustering estimation
In our previous results, we assumed that the underlying cluster memberships of users are known to the learner, so we could concentrate our analysis on the impact training using anonymous cluster centers. However, in practice, clusters should be estimated from the features and thus includes an estimation error. In our next result, we combine our previous result with a perturbation analysis to bound the risk of the look-alike estimator based on estimated clusters.
Recall matrix M Raxk from (2.3), whose columns are the cluster centers. Also, recall the matrix A Rixn whose columns are the one-hot encoding of the cluster memberships. We let M and Ā indicate the estimated matrices, with the cluster estimation error rate 8, := Vn M,A M.A 2 where | la indicates spectral norm. Note that only the cluster estimation error with respect to the sensitive features matters because in the look-alike modeling only those features anononymized (replaced by the cluster centers).
Let T [(M,A)T XT]] be the feature matrix after replacing the sensitive features with the estimated cluster centers of users. We also o, i,, X133 be the look- alike estimator based on ,, Note that 0g is the counterpart of 0 given by (3.2). Define the cluster estimation error rate 8,, == M, M 2. and suppose that either of the following conditions hold:
Proposition 3.4

---

Ru 6
V4
(a) Risk of 02 (a 1, Pos
2)
(b) Risk of (a 1, Pos 2)
(c) Risk of 02 (a= rs
( 1000
19 9p
(d) Risk of L, r 1ur==
(c) Risk 02 (ra 1, Tus 2)
(f) Risk of 0 (r, 1, Tas = 2)
Figure 2: Validation of theoretical characterizations of the risks, Curves correspond to (asymp- totic) analytical predictions, and dots numerical simulations (averaged 20 realizations). all the plots, 500, p 200, μ 5, 3. 0.3. Left panel corresponds to risk O,, and right panel corresponds the risk of 0.
(i) via - thp 0.5 and 8 /1 (V'd Up) / Upp.
(ti) vha 1pp 2 and 5 / 1/p -1
Then,
Risk (l)) s Risk O1.) C5,
for some constant C depending on the problem parameters.
Numerical experiments
In this section, we validate our theory with numerical experiments. We consider GMM with & clusters, where the centers of clusters are given by puue, for & [A:], where e IR are of unit f--norm. Also vectors u, are non-zero only on the first p entries, and their restriction to these entries form
U with
random orthogonal constellation. Therefore, defining U [[,..... Uk]. we have U =
U.U.= = Ig. In this setting there is no cluster structure on the non-sensitive features and the cluster centers on the sensitive features are orthogonal and of same norm.
Recall the decomposition of the model 0n (0o.s: Oo.ns,, with On the true underlying model (2.1) and 0o.s. O,.ns the components corresponding to sensitive and non-sensitive features. We generate Oo.ns IRd-p to have i..d standard normal entries and then normalize it to have ||0o, to.s. we generate Z1, Zz N(O,, Ip), independently and let
Tus- For
Pu, + +
(I (I-Pu,)22
0p.- TaVp iPu,21
I(I Pu. (I.)).)=
where Pu. U is the projection onto column space of U.. Therefore, 10,, rs and |UT T0 Vrr.. Note that P quantifies the alignment of the model with the cluster centers, confined the sensitive features.)
We will vary the values of rs and Tus in our experiments. We also consider the case of balanced clusters, the cluster prior probabilities are all equal, n. 1/k, for f [k]. We set the number of

---

cluster kt 3. dimension of sensitive features 200 and the dimension of entire features vector 500. We also set μr 5 and p = 0.3. In our experiments, we vary the sample size n and plot the risk of 0r and 0 versus V/d 1 (d - pp)/n. We consider different settings, where we vary 7s+ Ius and a (noise variance in model (2.1)). In Figure 2, we report the results. Curves correspond to our asymptotic theory and dots to the numerical simulations. (Each dot is obtained by averaging over 20 realizations of that configuration)) As we observe, in all scenarios our theoretical predictions are perfect match to the empirical performance.
When does look-alike clustering improve generalization?
In Section 3, we provided precise characterization of the risk of look-alike estimator 0, and its counterpart, the min-norm estimator 0 which utilizes the full information the sensitive features. By virtue of these characterizations, we would like to understand regimes where the look-alike clustering helps with the model generalization, and the role of different problem parameters in achieving this improvement. Notably, since the look-alike estimator offers m-anonymity on the sensitive features (with m the minimum size of clusters), our discussion here points out instances where data anonymization and model generalization are not in-conflict.
We define the gain of bokke estimator as A == Risk 0) Riskk 0L) to indicate the gain obtained in generalization via look-alike clustering. For ease in presentation, focus the case of balanced clusters (equal priors π =... Ty = 1/k), and consider three cases:
Case 1 (1ba $ 1): this case, both 02 and 0 are the underparametrrzed regime and Theorems 3.1 and 3.3 (a) provide simple closed-form characterization of the risks of 02 and 0, by which we obtain
---
P (1+r2/o²) va wp) prr//02
Define the signal-to-noise ratio SNR rs/a. Since p S 1, is easy to see that is decreasing in the SNR. In particular, as SNR- O, we have A (1 tha tip) vha) > 1, which means the look-alike estimator 0, achieves lower risk compared 0. In Figure 3a we plot log(A) versus SNR, for several values of v/p- Here we set diu = 0.9 and p= = 0.3. As we observe in low SNR, the look-alike estimator has lower risk. Specifically, for each curve there a threshold for the SNR, below which log( () Furthermore, this threshold increases with d.p, covering larger range of SNR where 0, has better generalization.
2
-03
- 0.1
=05
1.5
0.7
p=
(0)(A)
=09
p= 0.9
lng(A)
0.5
0-
-0.5
-1.5
2
0
2
3
4
5
SNR = 1./a
SNR
r2/o
p 0.3
(b) F 0.5
Figure 3: Behavior of gain A in the generalization of the look-alike estimator 0r over nor-norm estimator as we vary SNR = ra/a. Here, eha = 0.9, a 1, and we are in the underparametrized regime both 0r and 0.
In Figure 3b we report similar curves, where this time v = 0.5 and we consider several values of p. As we observe, at fixed SNR the gain A increasing in p. This expected since p measures the alignment of the underlying model Op with the (left eigenvectors of) cluster centers and so higher p is to advantage of the look-alike estimator which uses the cluster centers instead of individuals' sensitive features.

---

Case 2 (2/2 2 1, t 4/ S 1): In this case, the look-alike estimator 0g is in the underparametrized regime, while the min-norm 0 is in the overparametrized regime. The following theorem the characterizations in Theorem 3.1 and and 3.3 (b), and shows that in the low SNR= rs/ a, the look-alike estimator 0, has a positive gain. It further shows the monotonicity of the gain with respect to different problem parameters.
Suppose that tha 2 1 and Va - Up S 1, and consider the case of equal cluster priors. The gain A is increasing in Ina and ps and is decreasing in p²1k. Furthermore, under the following condition
Theorem 5.1
vu 2/)) SNR² := -"-- 1+ (0' (+a--11) (
(5.1)
(1- Vis + 12p 2/2 -1
we have A 2 for all values of other parameters (p,, k. Prnn).
An interpretation based on regularization: We next provide an argument to build further insight on the result of Theorem 5. Recall the data model (2.1), where substituting from (2.2) and decomposing over sensitive and non-sensitive features we arrive at
y (Igg 0z) + nns 0us)+ +
(Mg. 0z) (z 0z) (mas 0us) +
Note that (zs, 0.) ~ N(O. [|0, At low SNR, this term is of order of the noise term E ~ N(0, o²). Recall that the look-alike clustering approach replaces the sensitive feature 2. by the cluster center Hg. and therefore drops the term (zg, 0z) from the model during the training process. In other words, look-alike clustering acts form of regularization which prevents overfitting the noisy component (zg, 0z), and this will help with the model generalization, together with anonymizing the sensitive features.
In Figure 4a we plot log(A) versus μ for several values of Tns- Here, tha = 2, Up = 1.7, a = 1, r. 0.5 and condition (5.1) holds. As observe log( (A) is positive, decreasing in μ and also at any fixed ju, it is increasing in Tus, all of which are consistent with the Theorem 5.1. In Figure 4b, we plot similar curves where this time Tas = 0.2 and try several values of p. As see the look-alike estimator has larger gain A at larger values of p.
0.28
0.32
0.2
Tw
0.3
-06
fu
0.0
ho 0.4
0.28
(gg(A)
(oc(()
0.26
0.24
0.22
0.22
0.2
0.2
0
6
8
10
0
2
6
6
10
14
(a) p= 0.3
(b) Pus 0.2
Figure 4: Behavior of gain A in the generalization of the look-alike estimator 02 over min-norm estimator as we vary μ energy of cluster centers.
Case 3 (wha - v// 2 1): In this case, both 0r and ① are in the overparametrized regime. Let us first. focus on Tus- the energy of the model on the non-sensitive features. Invoking the equations (3.3) and (3.4) and hiding the terms that do not depend on Tna constants C₁ C2 we arrive at
C +
th )r
C₂ + (1- wターUカ )r
Therefore, lim, A -1- (11-5))1(11- (V'- -0)
) > indicating gain for the look-alike
estimator over 0. In Figure 5a, we plot log( A) versus Tus for several values of vip. As we observe, when Tus is large enough we always have gain, which is increasing in dpp-

---

0.4
0.5
=2
lng log(A)
log(A)
-0.2
0.1
0.5
-0.4
1.5
00.6
-0.1
-0.8
-0.2
2
0
4 SNR = Tu/a
8
10
Piss
(a) r. 0.5
(b) ris 2
Figure 5: Behavior of gain A versus and SNR==../o for several values of 1.p Here, thes 4. σ = 0.1, p= 0.3, f 5, l = 5. Here, we are in the overparametrized regime for both O and O.
0.1
0.3
0.5
log (A)
-0.5
0
0.5
1.5
SNR=r./o
Figure Behavior gain versus SNR the nonlinear model described Section small SNR, observe positive gain (lower risk of look-alike estimator 0, compared to 0).
We next consider the effect of SNR = rs/a. Figure 5b we log(A) versus SNR, for several values of dhp- Similar the underparametrized regime, observe that in low SNR, the look-alike estimator has better generalization (log( A) 0).
Beyond linear models
In previous section, we used our theory for linear models to show that at low SNR, look-alike modeling improves model generalization. We also provided insight for this phenomenon by arguing that look-alike modeling acts as form of regularization and avoids over-fitting low SNR regime. In this section show empirically that this phenomenon also extends to non-linear models. Consider the following data generative model:
y Binomial(N,2) N.Pw),
1 + 0n) +
where e N(O, o²). We construct the model O. (0o,s: 0o,ss) similar to the setup in Section We set n 200, d = 180, k= = 3, μ 5, a = 1, = 0.3, Tis 2 and N = 1000 (number of trials in Binomial distribution). We vary SNR by changing rs in the set (0.1, and or are obtained by fitting GLM with logit link function and binomial distribution. We compute the risks of and 02 by averaging over a test set of size 50K. In Figure 6, we plot the gain log( A) versus F3 where each data point by averaging over 50 different realizations data. As we observe low SNR, log(A) () > 0 indicating that the look-alike estimator 02 obtains a lower risk than the min-norm estimator.
1.9). The estimators
10

---

Acknowledgement
This work is supported in part by the NSF CAREER Award DMS-1844481 and the NSF Award DMS-2311024.
References
[1] F. Abu-Khzam, C. Bazgan, K. Casel, and H. Fernau. Building clusters with lower-bounded sizes. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Schloss Dagsuhh-LeibnizZZeetrrm fuer Informatik, 2016.
[2] G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. Approximation algorithms for k-anonymity. Journal of Privacy Technology, 2005112001:400, 2005.
[3] G. Aggarwal, R. Panigrahy, T. Feder, D. Thomas, K. Kenthapadi, Khuller, and A. Zhu. Achieving anonymity via clustering. ACM Transactions on Algorithms (TALG), 6(3):1-19, 2010.
[4] Bartlett, Y. Freund, W. S. Lee, and R. E. Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, (6(5):15111168) 1998.
[5] M. Belkin, Ma, and Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541-549. PMLR, 2018.
[6] G. Brown, M. Bun, V. Feldman, A. Smith, and K. Talwar. When is memorization of irrelevant training data necessary for high-accuracy learning? In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 123-132, 2021.
[7] J.-W. Byun, A. Kamra, E. Bertino, and N. Li. Efficient k-anonymization using clustering techniques. In Advances in Databases: Concepts, Systems and Applications: 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand. April 9-12, 2007. Proceedings 12, pages 188-200. Springer, 2007.
[8] Z. Deng, A. Kammoun, and C. Thrampoulidis. A model of double descent for high-dimensional binary linear classification. Information and Inference: Journal of the IMA, 11(2):435-495, 2022.
[9] H. Ding, L. Hu, L. Huang, and J. Li. Capacitated center problems with two-sided bounds and outliers. In Algorithms and Data Structures: 15th International Symposium, WADS 2017, St. John's 's NI, Canada, July 31 31-August 2, 2017, Proceedings 15, pages 325-336. Springer, 2017.
[10] A. Epasto, M. Mahdian, V. Mirrokni, and Zhong. Massively parallel and dynamic algorithms for minimum size clustering. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithmms (SODA), pages 1613-1660. SIAM, 2022.
[11] V. Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954-959 9549999,,45 2020.
[12] V. Feldman and Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881 -2911, 2020.
[13] Y. Gordon. On milman's inequality and random subspaces which escape through mesh in r". In Geometric aspects of functional analysis, pages 84-106. Springer, 1988.
[14] H. Hassani and A. Javanmard. The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression. arXiv preprint arXiv:2201.05142 2022.
[15] A. Javanmard and M. Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. The Annals of Statistics, 50(4):2127-2156, 2022.

---

[16] A. Javanmard, M. Soltanolkotabi, and H. Hassani. Precise tradeoff's in adversarial training for linear regression. In Conference on Learning Theory, pages 2034-2078. PMLR, 2020.
[17] Liang and A. Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329-1344 2020.
[18] Q. Ma, E. Wagh, J. Wen, Z. Xia, R. Ormandi, and D. Chen. Score look-alike audiences. In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), pages 647-654. IEEE, 2016.
[19] Q. Ma, M. Wen, Z. Xia, and D. Chen. A sub-linear, massive-scale look-alike audience extension system a massive-scale look-alike audience extension. In Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, pages 51-67. PMLR, 2016.
[20] M. Malekzadeh, A. Borovykh, and D. Gündüz.. Honest-but-curious nets: Sensitive attributes of private inputs can be secretly coded into the classifiers' outputs. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pages 825-844, 2021.
[21] A. Mangalampalli, A. Ratnaparkhi, A. O. Hatch, A. Bagherjeiran, R. Parckh, and V. Pudi. A feature- pair-based based associative classification approach to look-alike modeling for conversion- oriented usrr-targe in tail campaigns. In Proceedings of the 20th international conference companion on World wide web, pages 85-86, 2011.
[22] S. Mei and A. Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
[23] H. Park and K. Shim. Approximate algorithms for k-anonymity. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pages 67-78, 2007.
[24] A. Sarker, W.-K. Sung, and M. Rahman. A linear time algorithm for the r-gathering problem on the line. Theoretical Computer Science, 866:96-106, 2021.
[25] R. E. Schapire. Explaining adaboost. In Empirical inference, pages 37-52. Springer, 2013.
[26] Shen, S. C. Geyik, and A. Dasdan. Effective audience extension in online advertising. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2099-2108, 2015.
[27] C. Song and V. Shmatikov. Overleamiig reveals sensitive attributes. arXiv: 1905. 1742, 2019.
arXiv preprint
[28] G. W. Stewart. On the perturbation of pseudo-inverses, projections and linear least squares problems. SIAM review, 19(4):634-66) 662, 1977.
[29] C. Thrampoulidis, E. Abbasi, and B. Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions Information Theoory 566858592-5628, 2018.
[30] C. Thrampoulidis, Oymak, and Hassibi. Regularized linear regression: precise analysis of the estimation error. In Conference on Learning Theory, pages 1683-1709, 2015.
[31] S. Tu. On the smallest singular value of non-centered gaussian designs, 2020.
[32] A. J. Wyner, M. Olson, J. Bleich, and D. Mease. Explaining the success of adaboost and random forests as interpolating classifiers. The Journal of Machine Learning Reseurch, 18(1): 15588 1590, 2017.
[33] C. Zhang, S. Bengio, M. Hardt, M. C. Mozer, and Y. Singer. Identity crisis: Memorization and generalization under extreme overparameterizztton.. In International Conference on Learning Representations, 2020.
[34] C. Zhang, S. Bengio, M. Hardt, Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 6473):107-115, 2021.
12

---

Supplementary Material
In this supplementary, first provide overview of our proof techniques in Appendix A and then in Appendix B provide the proofs of theorems and technical lemmas stated in the main paper.
A Overview of proof techniques
Our analysis of the generalization error is based extension of Gordon's Gaussian process inequality [13], called -aauss-Ga Minimax Theorem (CGMT) [30]. Here, we outline the general steps of this framework and refer to the supplementary for complete details and derivations.
Consider the following two Gaussian processes:
X X := u Go (u, v): Yu, == |/ull gov v lole, h"u vu,
where e Raxd, g R" and h e Rd, all have i.d standard normal entries. Further, th: Rd R" a continuous function, which is convex in the first argument and concave in the second argument.
Given the above two processes, consider the following min-max optimization problems, which are respectively referred to as the Primary Optimization (PO) and the Auxiliary Optimization (AO) problems:
PC) = min max X X Se v55
(A.1)
min max Y S vs.,
(A.2)
The main result of CGMT is to connect the above two random optimization problems. As shown [3h]orh 3), if Sa and S. are compact and convex then, for any e and 0,
P (()Po x|> 2P (1 t)
An immediate corollary of this result (by choosing X AO problem concentrates in probability, then the optimal cost of the corresponding PO problem also concentrates, in probability, around the same value. In addition, shown in part (iii) of [he]reh 3), concentration of the optimal solution of the AO problem implies concentration of the optimal solution of the PO around the same value. Therefore, the two optimization intimately connected and by analyzing the AO problem, which is substantially simpler, one can derive corresponding properties of the PO problem.
(g. h)]l is that if the optimal cost of
The CGMT framework has been used to infer statistical properties of estimators in certain high- dimensional asymptotic regime. The intermediate steps in the CGMT framework can be summarized as follows: First form an PO problem the form of (A.1) and construct the corresponding AO problem. Second, derive the point-wise limit of the AO objective in terms of convex-concave optimization problem, over only few sealar variables. This step is called "scalarization', Next, is possible establish uniform convergence of the scalarized AO to the (deterministic) min-max optimization problem using convexity conditions. Finally, by analyzing the latter deterministic problem,
derive the desired asymptotic characterizations.
Of course implementing the above steps involved problem-specific intricate calculations, Our proofs of Theorems 3.1, 3.2, 3.3 in the supplementary follow this general strategy.
13

---

B Proof of theorems and technical lemmas
B.1 Proof of Lemma 2.1
By substituting for y from (2.1) in the definition of risk we obtain
Risk(O) [[ =0)
[00= 0)) E[{²]
Σ m [ + =)((0=))))))))))))0)))) 0))) [[[="]
te]k]
Σ गe El! (0. -0)) Σ [<[A]
म 10 Bolle, +
[=[A]
(0 (0-0u) T M M 0) + 00 - -01le + t
where (a) follows from the Gaussian- Mixture model (2.2) and (b) holds since Σe((H] we 1.
B.2 Proof of Theorem 3.1 and Theorem 3.2
Recall that the look-alike estimator is defined as the min-norm estimator over the feature matrix X where the look-alike representations are used instead of individual sensitive features; see (3.2).
To analyze risk of 0r we consider the ridge regression estimator given by
1 1/ x,,01 + 2
x arg min 2n
The minimum-nome norm estimator is given by 0, lim 0x. We follow the CGMT framework explained in Section A. Recall that
M,A
X
M
Zns
and therefore by substituting for y, X, and X,, we get
x
1
|| c
T x
2n y
2n
1
E A (0..
(0o.. 0a) Z 00.s (A (AM, Z00 -0
2n
We define the primary optimization loss as follows:
Lro 6m.)
1
s+ A A 0.) 2., Oo.. (A (A M, (00,) 11, 10
2n
We continue by deriving the auxiliary optimization (AO) problem. By duality, we have
T (0o. oT 2 Po.. o "A M (Bu,) -Ous) /11123
Lro 6ms)
v E t
Note that the above is jointly convex in (0,, m.s) and concave in v, and the Gaussian matrix Z is independent of everything else. Therefore, the AO problem reads:
Lo Qms) max
1 A A. (Bu.- O.)
+ 1o.slla le, 9. u |ulle h 0o.s
O0.us Onale Ine v ||ule, OIs(O0,us Ons)
|00/3 E2
+ v A M (0o.ne Ons)
X 100111, + +
2
14

---

where Is. Ins é IR and hg E RP, hns é Rd-P are independent Gaussian random vectors with i.i.d N(O, 1) entries.
We next fix norm of Iioll, = 33 and maximize over its direction to obtain
(0s: 0ns) 820 n
max
B [B|E++ A A M,,,, (0u,: 02)
110u,=ll,, Is -10u.us Buslle, Jus A MM ( 0ms)llg
+ +Bh 0o.s + S (0u.ns 0us) 8² + +1110.1e, +1/ Quslle
max 1
(s)
A A ( (0o,s 0.) A A (0 0us) /100,s l + 110 0ulll:g
920
8² A 11110.12,
00. + 3 (0o.ns 0ns)
where we used that 9s. Ins R" have independent Gaussian entries. Here, RD has i.i.d entries from N(O, 1). Next, note that the above optimization over 3 has a closed form. Using the identity max (3x (2) = 22, with = max 0), we get
La, Oms) _ -||= + (Oo.s 0.) A M (00.ns Ons) 00. 100.ns Ons l
2n
h! 0o.s + Musa00. 0ms)) ) > 111.,1,, + 10msslie
(B.1)
Scalarization of the auxiliary optimization (AO) problem. We next proceed to scalarize the AO problem. Consider the singular value decomposition
M,=
with U, E RRerr, Σ, E |REX,, V, Rkoor, where rank(M,) s k. Decompose q, := Ou.- O. in its projections onto the space spanned by the columns u1,:....; Ups of U,, and the orthogonal component:
=
a aog
where l au O, and U. q Using the shorthand a (a1,...., a,), we write
A T M. (0o 0.) AVV.EU q. AVE,
In addition,
| 2,
00,s (0o.s - 0
00. l. || 2(00. (6)
00.. 1. |1qalle, 2(00.., U,a:) 200 00. 9
00.. 12 l/ -2(U, 0,,,, a) 200 0, 4-)
10. lú (aî |ail',)) -2 0u.s; ax) 200 (Ou.. gt)
(B.2)
Similarly, we define que Oo Ons and consider the singular value decomposition
M = Un Ens ns
with Un.. E (dddp)xt Ens Rxtt VnS e Rext where t = rank (mx) $ k. Decomposing qus in its projections the orthogonal columns ui.ns.... U, of U uss and the orthogonal component write
Ins Σ 7 ms 70
with lig Ie, 1, 2 0, and T d O. Define > = (n...., 7t). In this notation, we have ns
A M (0, 0ns) A A Ens UT Ans A T Ens
15

---

Also, 00 Gns 1,2 = Ams le, = V18 + 17llér- In addition,
ns (00.us Ons) n Ins Σ
rch Mi + Yo Ius
im1
Using the above identities in (B.1), we have
2/1 A A Vus 7 000,lle, - I7
1
(A, Pns)
2n
Pich Mi,ni + To 1o Ins ?
h 0o. + Σ
1=1
+ Oo -aaa +alll; 22(U, 0o,s, Q+) 2Aa0 g3)
+ 12 X(10 1ml(,) -NA 7) 22 22 (0 ( (B.3)
By the above characterization, minimization over 0g and Ons reduces to minimization 7, To and I Further, these variables are free from each other and can be optimized over separately, For gs there is only one term involving this variable and therefore, minimization over it reduces
oo, 7o. ax
min -(0,,s: g min 19.1%
(U,) 00,s, gt) IUU 00.elle2 (U.t))o.slle.
For ams we note that there are two terms involving this variable, namely (5/m qus) and ((UH)) Ins) Since llgallle = 1, it is easy to see that the optimal qns should be in the span of hs and (U ns)
( To,us. In addition,
(
(p) 0,
by the of large numbers. words, these two vectors are asymptotically orthogonal. Hence, we can consider the following decomposition of the optimal qus:
h
U (UL) Too.as
qus
E2
1
((U 00.uslle,
where & 2 and h denotes the projection of has onto the (left) null space of Uns. This brings us to
min (os Ons)= 0.,
min a0-1020,a.y
1
s AVV. A V Ens
V100,.ll2, +7ō + |7 g
+ 2
h 0o.s
hT ui - 706
| 2
Σ 7/8
Vn
vn
vn
==1
0
+ N(a + |a (2:) -0AU2 (0,,T0,,s,o0 a) 2Aco (U:)) To.eale,
2
+ 0
lg X(10 ( -2 ns Gu..s, >) - 11--22211-- 1
(UL) To
(B.4)
Note that at this stage, the AO problem is reduced to optimization + t scalar variables (oo, No 2 0, s & s and a RR"," RR)..
Convergence of the auxiliary optimization problem. We next continue derive the point-wise in-probability limit of the AO problem.
First observe that since and g independent with i.i.d N(O. 1) entries, we have
11000112 1 + + 1rle, g
(d) V02 +2 01 12, + 20 1r12,) 9.
where ğ IR" has i.i.d N(O, 1) entries.
Second, by construction AAT diag(M1,...., mx) IR where ny denotes the number of examples from cluster f. Hence,
A AVVE A A D 12 (V,E,a+ Vns Dns T
diag(") 2 ..... De (V,,VE Vns Ens
(p) (V.E,a+ Vn Y) ddii)()))VVVVVVA..... Vna (m.
16

---

Next, by using concentration of Lipschitz functions of Gaussian vectors, we obtain
vn e A A'V.I, A Vns E y+ V100,al,, + t |1>l|le, 9
(V 7 (V,Ega + Vus
o² (1100,s +10 + 1r((,
Also, since 10,,lle, bounded and |
1, we get
hg
Oo.s
h Us (p)
0.
Vn
Vn
In addition, | l|ا concentrates around vd p-t and (d p t)/n Vi 1/p. because t
remains bounded as n diverges, and so
1 (p)
V
Via
vpp
Vn
Using the above limits, the objective in (B.4) converges in in-probability to D(oo; 70,5. =
(V(VE,, >n) Tdiag( (V, Vin + 0² +0 2 +
(xl1e) 705 1/a 1/11)
+ +1110ollz *(aa %0 |all lmll)))
22 (IV 00 a) ao (U:) 00 + +0001 --2 T
0o.nelle,) (B.5)
are now ready to prove the theorems.
B.2.1 Proof of Theorem 3.1
Using Lemma 2.1, we have
Risk( 0² 00g 100-01 013, + (0. 0) M (0o (0p-0)
0² 19 + ||ma llz q. M,diag( a M qs + q daag πt M Ins
0² (ag v + || l2. + lTTl1;))
a V. (diag())V.E.c E di Vns Ensy
(B.6)
Since tha 16 S 1, we are in the over- determined (a.k.a underparametrized) regime. As - 0*, the terms involving À become negligible compared the first term in (B.5) except those that include og. as is not present in the first term Since (r)² is increasing, and
(V,E.a Vn Emm>) T (ilag())(V,.)))
+ V Ens>) + 17/2, 20,
the minimum over a and y is achieved for = 0 R" and 7 O Rf. The optimization (B.5) then reduces to
min ap. 20,,000, 2
(V022 02 (100,112,, 7/)) 7o0- wn) + Xag 2A00 (U,
On.- & (B.7)
The optimal g is given by & 1. Also, setting derivative with respect to og to zero we obtain the optimal Okg = (U.) 00.s Next, by setting derivative with respect to ?o we arrive at
Vi Up
v0= = (o² 10..1 I (Nla vp))
Using the optimal variables in (B.6) we obtain the risk of minimum- norm estimator as L) 1/p
Risk(Or) 0² + + To + (o² 100.x1?2)) 1 (via wp)
= = =aa²+ 1100,-113) (wia - -wp) U.. 0o.s
Recall that by assumption, =100, and U. 0owlles = /prs, which completes the proof.
17

---

B.2.2 Proof of Theorem 3.2
We continue from (B.5). In the case of d4 1/p 1, it is easy to see that the derivative of the first term of (B.5), the active region is decreasing "t- With the consideration À 0*, minimizing over will push us into the non-active region. Therefore the optimization problem (B.5) reduces to
minimize
1 aa 20 Iall 11712 2 ( O0. a) [l,,)) Oo.sll, +U 7) 10o0i-e2 00..sllee))
subject to
(V,E,a+ Ens diag( (T Vus En 7) + (110,,alée, + +70 Ir]le,) 705 2 up))
(B.8)
By Assumption 2, Σ. H.x, V Lxck and E = 0, Uns = 0 (no cluster structure on non-sensitive features and an orthogonal, equal energy cluster centers on the sensitive features). Therefore, by fixing y = lrylez the optimization problem (B.8) becomes:
ag + To |lale +2 2 2 Go.. a) + ao (oo To.a + +700 @ lee,)
minimize
subject to
2 T diag( a o² 00 70 + 72 s 5005 ( 1p))
(B.9)
Since ag does not appear the constraint, is easy to see that its optimal value given by og ( To.ssle, Also, note that by decreasing y the objective value decreases and also by constraint on the other variables become more relaxed. Consequently, the optimal value of y is 7 = 0.
Removing ag from the objective function, are left with
minimize vo + lall, 2 (U oo. a) To vo 1 00.uslles)
1
subject to u²aa diag(r)) + o² + 10,,= + + s 70 1bp)
(B.
Optimal choice of & results in the constraint to become equality. Solving for &, the optimization reduces
aa diag(d π a o² 10 le +
(T)
minimize
20 +all, - B0 +
oo
1 10
Va Vp
Setting derivative with respect to To to zero, we obtain
p²a diag(d)) o² Bo.e + T0
10.malle.
(B.11)
Via upp
Setting derivative with respect to zero and using the previous stationary equation, we get
Q = I n diag(T))
U.o....
(B.12)
Vi 1/
We next square both sides of (B.12) and rearrange the terms to get
1 Va 1i (a² + 100.=1?,, 2² diag(())))
(
1 10
whs
Up
1
Vd 10,, (o² + + + 2 diag(T))))
22
vha thp
which are the same expressions for a and no given in the theorem statement.
The final step is to write the risk of estimator in terms of T0- Invoke equation (B.6), and recall that the current case, Σns 0, Σ, JI. Also, as we showed in our derivation, ? ||
oo =| (U. by which we arrive at
Risk 01) 4 a diag( π (T) o² + (((+ To.eel. T + + lal))
= + (1 - p)r + + a (I 2 d'diag(T)) a.
(B.13)
This concludes the proof.
18

---

B.3 Proof of Theorem 3.3
We follow the proof strategy used for Theorem 3.1-3.2. Here, we would like characterize the risk of min-norm estimator 0. The features matrix has a clustering structure, but the learner using that (no look-alike clustering) and is just compute the min-norm estimator for fitting the responses to individual features. Therefore, one can think of this setting special case of our previous analysis when there is no sensitive features (so U/ 0).
(a) By setting , 0 and Fs = in the result of Theorem 3.1, we get that when t/a S 1,
Risk (
1 L
(b) In this case, we specialize the proof of Theorem 3.2 to the case that v O. Continuing from (B.8), and removing the terms corresponding to sensitive features, we arrive at
minimize
o0 Irlles
2 (UU 0 7) + 7o V ( ( (0.
subject to
(V in diag( πT (V Ens + 0² + v0 17 s 2 (B.14)
We drop the index 'ns' it is not relevant in this case. Also by Assumption 2, Ens pla. Vns Id. Therefore, the above optimization can written as
minimize
T 1712, ((UT Go 7) 70 20v1 E² (U Tou TT p diag(()) (T)) o² nh 2
subject
(B.15)
Optimal & makes the constraint equality. Solving for the above optimization can be written as so we have
minimize
- 1r -2 -2(( 7) V r
71 (2d=)=/dda(())))))) + o²
n
(I44)
Setting the derivative with respect to to zero, we get
TT(I+ + (( o² + = (1- Va
1
(B.16)
Vi
Setting derivative with respect to y to zero and using the above equation, we obtain
I + 1 (idia())))))
I
UT
(B.17)
We next square both sides of equation (B.16), and rearrange the terms to get:
0 Vi (0² + (I diag(())))) t.
(1-=)
Under the simplifying Assumption 2, there is no cluster structure on the non-sensitive features and so Un. 0. Therefore,
||u =|UU, 00. =Vrss
( 1 l2. -TTTo = -1 (1-p)r? 2
We next proceed to compute the risk of estimator in terms of 7, "/o- We use equation (B.6), which for the min-norm estimator with look-alike clustering, reduces to
Risk 0 o + n 7 + eIIII("+aaaaaap "ddag(T))
(B.
This concludes the proof. Note that in the theorem statement we made the change of variables 7o 70 and 7 ā. for easier comparison with the risk of look-alike estimator.)
19

---

B.4 Proof of Proposition 3.4
Consider singular value decompositions X UEV' and X UEVT. We then can write the estimators 0r and 0r follows:
0 ---U-VV y, i,=ū
We first bound |001 0.ll We write
|0, 0.1 -
(B.19)
We have
| | + T
M 0g + zz 0u e|
Note that Z 0. +
(d)
V100l 10 02 where ~ N(0, 4n). In addition.
A M 00l2 0 M.AAA
0g
Mdiag d1
H 0, = 0 (M... MTM MM 0o
Therefore by using concentration Lipschitz functions Gaussian vectors, we get
1
bl 2 V (dia((()) |00 o2.
This shows that
y + Cs ( + + O
(B.20)
We next use the result of [28, Theorem 3.3], by which obtain
V5
- -UEVI. (B.21)
max
2
Tmin (2)²* Jmin ($)²
Note that
UEV -USVVI -EVT-UΣVVIO Xr X M
(B.22)
by the assumption of the theorem statement. We next lower bound m ()) a x)). Recall that X (MA)* [Onxp: Zax(d-p)), with Z having i.idd N(O, entries.
Next suppose that Condition (i) holds true, namely ó < V1 (w' - 4p) /Va Up with t/a - Up 0.5. Using the result of [31, Theorem 2.1]. we have with probability at least 1- - n
log n
min (X.) 2 /n Vid 1p -
Furthermore,
Jmin (X1) omin (X,.) - ||,, -x,1
2 2 n
n v1 - (iis - (/p)) - -Vba 1/
c' Tr (V1 (w' vpp) Vi 1/pp)
using the assumption on the estimation error rate 6. Therefore, using the above bound along with (B.22) in (B.21) we get
1 1+
8.
2 V / (wa 1/pp) / vp
20

---

Combining the above bound with (B.20), we get
1 v5
-0.11
(B.23)
2
(VI- - bp) Vd vp
We next note that by triangle inequality, the above bound implies that
1 8ul 00 0o 100 02 0
Therefore, by invoking Lemma 2.1, we obtain the desired result on Risk (l).
Next suppose that Condition (di) holds, namely 8 V pp - 1 with vha up > 2. Using the result of [31, Theorem 2.1] for X we have with probability at least 1 1-n²
min (x) Vn Ve'' Up 11-1-
2 log
V
n
By following a similar argument we prove the claim under Condition (ii)
B.5 Proof of Theorem 5.1
We use Theorem 3.3 (b) to characterize Risk( 0 the regime tha 2 1. Specializing to the case of balanced cluster priors, the risk depends o only through its norm á := | and is given by
11
Risk 0
o² %
+
+
à²
k
vh
0² +
112
+
à
(1-
1 tha
1 1 ((1 p)r r2a)
v -
with
2²a
+
ā
1
k
Vprs.
In addition, by Theorem 3.1 we have
Risk θ2)
P
g2+r3 1- v/a
0²
pr
1/
Note that Risk (0l) in this regime does not depend on /²2ks Also, is easy to verify that Risk 0 is decreasing in y²² /k. Therefore the gain A is decreasing in j/²/k.
Also observe that Risk(O () is increasing in Thss while (isk(O,) does not depend on Tus- Therefore, the gain A is increasing in Tis-
To understand the dependence of A on P, we write
Risk( 0
A 1
Risk (2)
62 +
( 22
+ 1) (1
///1+1 -2
pr?) pr²)+(1 (1-+))(11 pp)? +
((1 (1-)+(11))(
Py-1 1
R
Wy-1
Va
o²+r3
pr?
1-b4tt1
a
2 +
( [ +
12/++1
We-1
-2
pr + (1
1 Vel
( 2
1-va+t
a²rr
+
pr V'
pr?
I-
As we see the numerator increasing in & and denominator is decreasing in p. which implies that the gain A is increasing
21

---

We next show that A 2 if condition (5.1) holds. Since A is decreasing in p²/k and increasing in
suffices to show the claim assuming j²/k + oo and p In this case we have ( + 1) ā² and so
n
A
Vu
o or+22
1-
o
1-
Wy
SNR.
04-
2 1,
I+SNR2
1-
where the last step follows from condition (5.1).
22


Reviews:
[{"review_id": "m02wictswM", "reviewer": "Reviewer_EnfZ", "summary": "The paper studies linear regression where some coordinates of the covariate x are not revealed directly to the learner, and only a cluster-wise average is revealed for those coordinates. This change in the covariates x is called look-alike clustering and it has been used for protecting sensitive attributes in prior work. While it seems that with look-alike clustering, less information is provided to the learner, the paper shows that in certain regimes the performance of linear regression improves after look-alike clustering. As the authors explain, the reason behind this surprising phenomenon is that look-alike clustering can reduce overfitting.\n\nMore concretely, this paper assumes that the data points (x_i, y_i) are generated iid from a linear model y_i = < x_i, theta > + eps_i with mean-zero Gaussian noise eps_i. The distribution of the covariate x is a mixture of k Gaussian distributions each with its covariance matrix being the identity matrix. Look-alike clustering then corresponds to replacing a subset of the coordinates of each x_i by the coordinates of the mean of the Gaussian distribution that generates x_i. Those coordinates are called sensitive features.\n\nFor d dimensional x with p sensitive features, the authors study the asymptotic performance of linear regression with n data points as d, p, n all tending to infinity and the ratios d/n, p/n tending to constants. The number of clusters, k, is fixed, and performance is measured using the (population) mean squared error. The learner estimates the parameter theta in the linear model by solving least squares on the data points. When there are multiple solutions (e.g. when n < d) the learner chooses the one with the minimum l_2 norm $\\\\|\\theta\\\\|_2$.\n\nThe authors show closed-form formulas for the asymptotic performance with and without look-alike clustering. This allows the authors to identify regimes when look-alike clustering improves the performance. They also included experimental results verifying the formulas. While the formulas are only shown to hold asymptotically, even when d, p, n are only a few hundreds the experimental results already closely match the formulas. The authors also extend the formulas to the case where we do not know the means of the k Gaussians when performing look-alike clustering and we instead use estimates for these means.", "questions": "1. The explanation at Line 297 seems to be presented only for Case 2, but I don't see why this should be the case.\n2. It seems that the assumed upper bound on delta at Line 237 could be negative, in which case the assumption cannot be satisfied. I would appreciate some comments on this.\n3. It would be great if the authors can provide their feedback on the weaknesses session of the review.\n\nTypos:\n\n- Line 29: leaner -> learner\n\n- Line 30: that that -> that\n\n- Line 133: belong -> belongs", "limitations": "The authors adequately stated all the assumptions needed for obtaining their results. In terms of negative social impact, perhaps one question is whether look-alike clustering may lead to stereotyping each cluster (e.g. when the clusters are demographic groups). It would be great if the authors could discuss this.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors chose an interesting problem to study: the effect of look-alike clustering on generalization. The exact formulas on the performance of linear regression established in this paper are technically challenging to obtain, for which the authors use tools such as the Convex Gaussian Minimax Theorem. The paper is well written. The proofs in the supplementary are easy to follow and they look correct and complete.", "weaknesses": "1. Unless I am missing some parts of the paper, the authors do not provide any (empirical) examples beyond linear regression where look-alike clustering is helpful for performance. It would be great to have such examples as they may suggest that the analysis in this paper could explain a general phenomenon appearing not just in linear regression. Currently, the impact of the paper is somewhat limited to the linear regression setting.\n\n2. In proposition 3.4 where look-alike clustering uses estimated means of the Gaussians, a requirement seems to be that we can accurately estimate the Gaussian mean of every data point. When we do not know which cluster each point comes from, this seems quite challenging especially when the Gaussians are not well separated. It is important for the authors to provide a clear explanation on how to obtain such accurate estimates (perhaps using prior results on learning Gaussian mixtures).\n\n3. Starting at Line 297, the authors provide an explanation for the improved generalization from look-alike clustering. Indeed, with the main results being presented using math formulas, a high-level explanation is much needed. However, I am not able to fully understand the authors' explanations at Line 297. The authors wrote that look-alike clustering drops the <z_s, theta_s> term, but my understanding is that the y in look-alike clustering is generated using the original x and thus still contains the <z_s, theta_s> term, which means that the authors' description is inaccurate. It is also unclear how the authors' explanation is related to regularization.\n\n    Here is my own understanding of why look-alike clustering can improve generalization. The authors can comment on whether this makes sense. After look-alike clustering, each x_i, when restricted to the sensitive features, can only be chosen from k possible vectors, and thus the learned parameter theta, when restricted to the sensitive features, must be in the space spanned by the k vectors (since the learner picks the minimum norm theta). This low-dimension restriction is a form of regularization and can reduce overfitting. This does not explain why lower SNR leads to larger performance gain, which I feel is not explained well in the authors' explanation either.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper!\n\n## General comments on weaknesses:\n1) We expect that the virtue of look-alike modeling on generalization to apply in a broad range of settings. The high-level intuition is that the look-alike modeling acts as a regularizer and can improve the generalization by reducing the variance, an observation that is not limited to linear regression. To support it empirically, in our **global response** we provide additional experiments for a nonlinear model where we observe similar phenomena. \n\n\n2) We would like to emphasize that Proposition 3.4 **does not make such an assumption**. Note that the proposition statement involves two matrices $M$ and $\\widetilde{M}$. The matrix $M$ corresponds to the matrix with true cluster means as it is columns, and $\\widetilde{M}$ is the estimated cluster means. Similarly, $\\Lambda$ is the matrix which encodes true cluster memberships, while  $\\widetilde{\\Lambda}$ is the estimated one. Our proposition allows both estimation $\\widetilde{M}$ and $\\widetilde{\\Lambda}$ be different from the true ones.\n\n3) Let us make a clarification here. There are two components of the problem setting: (i) data generative model (linear regression and Gaussian Mixture model on the features), and (ii) trained model (Look-alike). The latter is how the learner fits a model to predict $y$ from the features. The response $y$ of course is based on individual features as you said, but the look-alike fits a model by regressing the response $y$ against ($\\mu_s$,$x_{{\\rm ns}}$) as opposed to ($x_s$, $x_{{\\rm ns}}$) (which is done in the vanilla regression). This is what we mean by “look-alike clustering drops the $\\langle z_s, \\theta_s\\rangle$ term”. In other words, it drops this term form the model it uses to regress against the response $y$. At low SNR, this corresponds to removing a `noise’ component from the model ($\\langle z_s,\\theta_s\\rangle$ is of order of the noise $\\varepsilon$) and avoids overfitting to this component. We will rewrite this part in the revision to ensure clarity and also include your explanation as well. \n\n\n## Response to questions:\n1) The explanation applies to other cases as well (e.g., in case 1, Fig3 we also see higher gain at lower SNR). We initially thought to put the explanation right after the theorem statement, but now we understand the confusion it made and will move it to the beginning of the section.    \n\n2) Line 237: The upperbound on the perturbation is non-negative only if $\\psi_d-\\psi_p \\le 0.5$. Recall that $\\psi_d - \\psi_p = (d-p)/n$ is the ratio of non-sensitive features on the sample size. For $\\psi_d-\\psi_p\\ge 0.5$ the statement is vacuous  as the assumption is not satisfied. However, note that in this regime (or its extreme where n<< d-p) it is hopeless to have a reasonable estimate of the clusters  as we have substantially smaller sample size than the problem dimension. \nThat said, please note that this proposition only makes an assumption on the perturbation norm, and NOT any specific estimator of the clusters (so perturbations can be added in an adversarial way as far as it satisfies the norm constraint).  In other words, the result holds against strong adversarial perturbation. If one instead focuses on specific estimator of the clusters, then the bound on $\\delta$ can probably be made more relaxed.\n\n3) Please see our responses to the weaknesses.\n\nThanks for pointing out the typos. We will fix them. \n"}, {"review_id": "J84ii5ct0S", "reviewer": "Reviewer_gwNk", "summary": "This paper extends look-alike clustering to anonymize sensitive features of data points by replacing them with cluster means. It provides a theoretical analysis of the generalization error of models (linear regression estimator) trained using the anonymized sensitive features in the asymptotic regime. The paper also shows that anonymizing sensitive features through look-alike clustering can improve model generalization by acting as a regularization and mitigating overfitting when the signal-to-noise ratio (ratio of the energy of the model on sensitive features to the response noise) is below a certain threshold under different parametrization regimes.\n", "questions": "1. Please refer to the comments in the weaknesses section.\n\n2. Besides the generalization bounds, do the authors have any insights about the DP guarantees of their proposed look-alike anonymization approach?\n\nMinor recommendations:\n\n1.  The authors should specify that proposition 3.4 holds true for the look-alike estimator in the under-parametrized regime.\n\nReference for k-anonymity :\n\n1.  Sweeney, Latanya. \"k-anonymity: A model for protecting privacy.\" International journal of uncertainty, fuzziness and knowledge-based systems 10.05 (2002): 557-570.\n\t\nRelated works covering memorization of sensitive information in neural networks and can provide valuable insights into the problem motivation:\n1. Song, Congzheng, and Vitaly Shmatikov. \"Overlearning reveals sensitive attributes.\" arXiv preprint arXiv:1905.11742 (2019).\n\n2. Feldman, Vitaly, and Chiyuan Zhang. \"What neural networks memorize and why: Discovering the long tail via influence estimation.\" Advances in Neural Information Processing Systems 33 (2020): 2881-2891.\n\n3. Stephenson, Cory, et al. \"On the geometry of generalization and memorization in deep neural networks.\" arXiv preprint arXiv:2105.14602 (2021).\n\n4. Malekzadeh, Mohammad, Anastasia Borovykh, and Deniz Gündüz. \"Honest-but-curious nets: Sensitive attributes of private inputs can be secretly coded into the classifiers' outputs.\" Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021.\n\t\n", "limitations": "I could not find a section addressing the limitations and negative societal impact of this work.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies an interesting area of anonymizing private/sensitive user information, drawing on recent research that examines the memorization of training data samples.\n\n2. The theoretical analysis presented in the paper is intriguing as it explores scenarios where learning from look-alike clustering-based anonymized data can potentially improve model generalization.\n\n3. The paper is well-written with the majority of sections being clear and coherent.\n", "weaknesses": "1. The current draft lacks coverage of related works on other data anonymization methods. It would be helpful for the readers if the authors included a literature survey in either the main paper or the appendix.\n\n2. The paper lacks comprehensive empirical experiments on real-world datasets (of any scale).\n\n3. Limitations of the theoretical analysis presented in the paper are also missing.\n\n4. Perturbation analysis about the upper bound of the look-alike estimator's risk (Proposition 3.4) is not covered in the over-parametrized regime.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper!\n\n## General comments on weaknesses:\n1) We will add related work on other data anonymization methods, including differential privacy, k-anonymity and aggregate learning.\n\n2) Since the focus has been developing on “precise characterization” of the effect of look-alike modeling on generalization, we devoted our numerical sections on thorough synthetic simulations to corroborate our theory in various data regimes. We will be happy to add a real-data experiment to show the high-level idea that look-alike modeling can improve generalization.\n\n3) A limitation of the presented analysis is that it is focused on linear regression. Despite its simplicity though, it is rich enough to show the surprising phenomenon that look-alike clustering can reduce overfitting. Also as you see deriving a precise characterization of generalization, in the regime that sample size and features dimension grow in proportion is already challenging. That said, we expect the same phenomenon carries over to a broader problem setting.\n \n4) The upper bound on the perturbation becomes vacuous unless $\\psi_d-\\psi_p \\ge 0.5$. Recall that $\\psi_d-\\psi_p = (d-p)/n$. Still we can have $\\psi_p = p/n$ and $\\psi_d = d/n$ both be higher than one, but it needs the number of non-sensitive features $(d-p)$ be smaller than $n$. The assumption arises in the analysis as we need to compare the spectrum of the look-alike features and the spectrum of the raw individual features and the randomness of the non-sensitive features can lead to large deviations in the eigenvalues. However, please note that this proposition only makes an assumption on the perturbation norm, and NOT any specific estimation of clusters (so perturbations can be added in an adversarial way as far as it satisfies the norm constraint). \n\n## Response to questions:\n1) Please see our responses to weaknesses.\n\n2) It is a very interesting question. In the current form the look-alike modeling is not DP, unless some sort of randomization (noise) is applied to the look-alike features. In ongoing work we are investigating the right way of doing it. The idea is to split the privacy budget,  part of it to learn clusters privately and part of it to randomize the look-alike features. The intuition is that if the cluster sizes are large enough, then this approach leads to a better privacy/generalization tradeoff compared to making the individual features DP from the onset. But it is an ongoing work and out of the scope of the current one.\nMinor comments: Many thanks for the pointers. We will add/discuss them in the revised version.\n"}, {"review_id": "RRS8Cue053", "reviewer": "Reviewer_KLzk", "summary": "This work presents a generalization analysis for look-alike clustering. In this type of clustering, the features in a model are divided into two groups: sensitive and non-sensitive, and the values of the sensitive features are replaced by the mean of the cluster to ensure K-anonymity (if the size of the cluster is K). They provide an analysis of generalization in the under-parameterized and over-parametrized regimes.\n", "questions": "Clarify what happens if number of features are not equal to number of samples?\n\nHow do number of sensitive features affect generalization? ", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper brings in generalization analysis for look-alike clustering, i.e., clustering under the assumptions of some features being held fixed at their mean. They provide some simulations as well, showing the under-parametrized and over-parametrized regimes.", "weaknesses": "It would be good to provide more intuitive insights on how different factors affect the generalization, e.g., the number of sensitive and nonsensitive features. My intuition is that as the number of sensitive features increases, the generalization should get worse until it fails as they approach the total number of features?\n\nI do not understand this assumption: \"We focus on an asymptotic regime where the size of the training set grows in proportion to the features dimension.\" For a complete picture, it is best to keep them as separate variables, and if required, consider a substitution at the end in a corollary or something. This assumption takes away important insights related to the relationship between number of features and size of training set.\n\nExperiments are mostly on synthetic data but it may be okay since the focus is mostly theoretical.\n\nClustering assumptions are based on linear models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper!\n## General comments on weaknesses:\n1) The effect of the number of sensitive features on the generalization is indeed more complicated. For example, in the underparamterized regime as shown in Theorem 3.1, if we fix $n,d$ and increase $p$ (so $\\psi_d = d/n$ is fixed and $\\psi_p = p/n$ increases) the denominator in the risk increases, so does $r_s$ in the numerator (recall that $r_s = ||\\theta_{0,s}||$ represents the norm of model component restricted to sensitive features). In addition, $\\rho$ can also change as it measures the correlation between $\\theta_{0,s}$ (the model component over sensitive features) and the cluster centers. The overall effect on the risk depends on the interplay between these factors. The virtue of our precise theory is to shed light on such intriguing effects. The reason that your intuition does not give the complete picture is at core due to a bias-variance tradeoff.  As we argue after Theorem 5.1, look-alike modeling acts as a regularizer. As we increase the number of sensitive features, the impact of such regularization becomes stronger. It induces bias but also decreases the variance of the estimators. Depending on the interplay between them, we can have a positive or negative impact on the generalization.  \n\n2) You have a mis-understanding about the proportion regime. It says that the sample size and the features dimension are “proportional”, i.e. they are of the same “order” as the sample size grows to infinity (mathematically $d/n \\to \\psi_d$ and $p/n \\to\\psi_p$ as $n\\to\\infty$ for arbitrary bounded constants $\\psi_d$ and $\\psi_p$).Therefore, $n$, $d$, $p$ are separate variables (e.g., d = 1000n or p = 100 n, and these constants can be arbitrary).\nThis is in contrast to the “population regime” where the sample size is “orderwise” larger than the features dimension (i., n/d \\to \\infty). The population regime is of course much easier to analyze, however it does not capture many of the interesting phenomena happening in the proportional regime. Moreover, as discussed in the paper, with rise of overparamterized regime, the proportional regime is more relevant in practice.\n\n3) Since our goal have been on deriving a precise characterization of generalization performance of look-alike modling, we devoted our numerical experiments to synthetic data to corroborate our theory and show the perfect match between simulations and the proposed theory.\n\n4) Regarding the linear model and the limitations, please see our **global response** to all reviewers where we supplement an experiment with a non-linear data model and empirically show that a similar phenomena (better generalization of the look-alike modeling at low SNR) applies to this setting as well.\n\n## Response to questions:\n\n1) Please see our response above to it. We do not make such assumption. The proportional regime assumes that the number of features and the number of samples are at the same scale (their ratio can be any arbitrary bounded constant.)\n\n2) Please see our response above (item #1 in weaknesses).\n"}, {"review_id": "0IHOAckdCB", "reviewer": "Reviewer_PpUR", "summary": "In this paper the authors propose a look-alike clustering technique that replaces sensitive feature of individuals with the cluster’s average value – the cluster in which that individual belongs to. The authors provide precise analysis of how replacing sensitive features with cluster center value affect the generalization of the linear regression model by comparing under-parameterized and over-parameterized regimes in the asymptotic setting. Numerical experiments are provided that matches the asymptotic theory.", "questions": "1.\tSee weakness.", "limitations": "Limitations are not clearly mentioned. To establish concrete expression of the risk, Assumption 2 is very simplistic or the isotropic Gaussians in the GMM is very simplistic. It may be a good idea to add a specific section/subsection mentioning the limitations.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1.\tPrecise analysis of how replacing sensitive features with cluster center value affect the generalization of the linear regression model.\n2.\tExpression of risk in the under-parameterized and over-parameterized regimes and analysis of scenarios when the proposed method improves generalization by achieving lower risk while ensuring privacy.\n", "weaknesses": "1.\tWhile the introduction suggests that the developed theory clearly demonstrates the role of cluster size and number of clusters in controlling generalization error none of the theory statements presented in the main paper explicitly shows that dependence. While looking at the supplementary material, it is clear that after simple algebraic manipulation such effect can be seen (e.g., in part (b) of Theorem 3.3) it may be a better idea to reorganize the theory statement where such dependence is clearly visible.\n2.\tIn theorem 3.1 what is $\\rho$? While later at somewhere else it is mentioned that it captures the alignment of the model with the left singular vectors of the cluster centers can it be interpreted as $U^T_s\\theta_{0,s}=\\sqrt{\\rho}\\theta_{0,s}$ which yields $|| U^T_s\\theta_{0,s}||=\\sqrt{\\rho}r_s$?\n3.\tFor case 1 in section 5, $\\psi_d=0.9$. If we look at figure 3(a), among various values of $\\psi_p$, $\\psi_p=0.9$ tolerates largest SNR while still ensuring $\\Delta>1 (\\log (\\Delta) >0)$. However, since $\\psi_d=0.9, \\psi_p=0.9$ means all the features are sensitive and yet it tolerates the largest SNR and improves generalization. Does that mean, irrespective of sensitiveness, it is always a good strategy to replace all features by their cluster centers to achieve better generalization?\n4.\tIf we compare Figure 3(a) and 3(b) and look at what SNR values the red curve hits zero for $\\rho=0.3$ and $\\psi_p=0.5$, we get very different values. On Fig 3(a), this SNR value is a little less than 2 while on Fig 3(b), this SNR value is close to 2.5. Since both axes in Fig 3(a), 3(b) are identical, why is this discrepancy?\n5.\tIn figure 2, the six graphs are organized in a 2x3 window without clear “left” and “right” panels as mentioned in the figure caption. Reorganizing them in 2x3 window will have two panels and will match the figure caption.\n6.\tFew typos in the statement of Proposition 3.\n       a.\t $\\tilde{X}^T$ should be $\\tilde{X}^T_L$\n       b.\t  It seems $\\delta_n$ and $\\delta$ represent same thing (cluster estimation error rate). This needs to be fixed.\n7.\tIn line 200, “underparameterized” should be “overparameterized”.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper!\n## General comments on weaknesses:\n1) We respectfully disagree with your comment. Our theory indeed captures the effect of cluster size and the number of clusters as well as other factors precisely in the studied asymptotic regime. However, an intriguing corollary of our theory is that in the so-called underparamterized regime, those two factors (number of size of clusters) do not impact the generalization (cf. Theorem 3.1), while in the overparamterized regime they do (cf Theorem 3.2 and 3.3). Maybe that is the source of your confusion. We have highlighted this point in lines 106-111 and 191-192.\n\n2) Definition of $\\rho$ is just stated in the theorem itself (see line 185). Please recheck.\n\n3) Not necessarily. Recall that $r_s := ||\\theta_{0,s}||$ is the norm of model components restricted to sensitive features. So if you continue converting nonsensitive features to the sensitive ones, $r_s$ and so the SNR goes up. In other words, when it gets to comparing gain, you will be comparing different curves at different SNRs.\n\n4) It seems that you are comparing wrong curves. Note that $\\rho = 0.3$, $\\psi = 0.5$ corresponds to the **green** curve in Fig 3(a) and to the **red** curve in Fig 3(b). \n\n5) Thanks for raising it. It happened as we were dealing with the space constraint. We will fix the arrangement of panels.\n\n6,7)  Thanks! We will fix these typos.\n"}, {"review_id": "ZMqeg5fmzb", "reviewer": "Reviewer_Kp2o", "summary": "This work considers linear regression on data $(x_i, y_i)_{i=1}^n$ where each $x_i \\in \\mathbb{R}^d$ is sampled from one of $k$ Gaussian clusters, each with probability $\\pi_k$, and $y_i = x_i ^T \\theta_0 + \\varepsilon_i$ with $\\varepsilon_i \\sim N(0, \\sigma^2)$ representing noise. The goal of this paper is to characterize and compare the out-of-sample expected squared error of the minimum 2-norm regression predicter with that of the so called ``look-alike\" predicter. The look-alike predicter is the minimum 2-norm predicter after one replaces the first $p$ features of each point with the first $p$ features of their respective cluster average: to motivate this consider the first $p$ features as sensitive in some manner, aggregation therefore provides a degree of anonymization for each data point. The min-norm and look-alike predicter are then analyzed in the asymptotic regime $d,p,n \\rightarrow \\infty$ with $d/n \\rightarrow \\varphi_d$ and $p/n \\rightarrow \\varphi_p$. The min-norm and look-alike estimators are said to be in the underparameterized regime if $\\varphi_d\\leq 1$ and $\\varphi_d - \\varphi_p \\leq 1$ respectively, and are otherwise considered overparameterized. In addition, if $\\theta_s$ denotes the first $p$ (sensitive) entries of $\\theta_0$, then the Signal to Noise Ratio SNR is defined as $||\\theta_s || / \\sigma$. This work identifies a number of scenarios in which the look-alike predicter outperforms the min-norm predicter, in particular when the SNR is low then the underparmaterized look-alike predicter outperforms the min-norm predicter.", "questions": "1. Can you comment as to the potential avenues and barriers to relaxing your results from asymptotic to big-O?\n\n2. Can you comment as to the potential for your results to be extended to more general data distributions?\n\n3. In Figure 3a) when $\\varphi_p=0.9$ then $p=d=0.9n$ and all features are sensitive. If in addition the SNR is $0$, then unless I am mistaken this implies $\\theta_0 = 0 $ and therefore $y_i = \\varepsilon_i$, i.e., the target is independent of the input features and is random noise. It seems curious then that one classifier has a better generalization than another in this setting, could you comment?\n\n3. Have you observed the conclusions of your results to actually hold on any real-world data? In particular have you identified any real world data problems where you actually see the look-alike estimator out-perform the min-norm estimator?\n\n4. I wonder if the proportional regime is the most appropriate to consider here for actual applications versus say fixed $d$ and $p$, for instance when considering financial or health records in a country. Could you comment on the how your results might change in this setting?", "limitations": "A section discussing limitations of the work is lacking. I cannot foresee any negative societal outcomes from this work. Although it seems only fairly basic numerics are presented a link to the code used to generate the plots is lacking and should probably be included.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper illustrates, albeit in a specific setting, that anonymization by aggregating sensitive features does not necessarily lead to a drop in the performance of the predictor, and can in certain settings actually lead to improvements. The results appear technically sound and are based on a nice use of the Convex-Gaussian Minimax Theorem. I did not go through all of the appendix or re-derive any of the results line-by-line. Synthetic data is used to support and validate the results numerically. The paper is also well written and structured. I am not an expert in this space so cannot comment really on the novelty of the work.", "weaknesses": "The biggest weaknesses to my mind is perhaps the specificity of the data model, both in terms of the data model. Little discussion as to the feasibility of extending the takeaways to more general settings is provided. As a small note I also think greater care is perhaps required when discussing the informal notion of user privacy used here versus more formal notions, e.g., differential privacy, which actually provide privacy guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper!\n\n## General comments on weaknesses:\n\n1) **Limitations of the model**: We expect that the virtue of look-alike modeling on generalization to apply in a broad range of settings. The high-level intuition is that the look-alike modeling acts as a regularizer and can improve the generalization by reducing the variance, an observation that is not limited to linear regression. To support it empirically, in our **global response** we provide additional experiments for a nonlinear data model and empirically observe a similar phenomena (i.e., look-alike modeling achieves better generalization over the vanilla estimator at lower SNR). In terms of theory, a similar approach based on CGMT can be used to handle other loss functions, albeit leading to a much more complicated formula for the generalization, which is less transparent in showing the message. A limitation in our analysis is though the distribution of features, as the CGMT strongly relies on gaussianity of the features. \n\n\n2) **Privacy measures**: We will add a discussion on other privacy measures, including differential privacy, aggregate learning and k-anonymity. Note that in our setting if the minimum size cluster is k, then after look-alike modeling we have k-anonymity in the sense that for any individual there are at least k-1 other users with the same sensitive features.\n\n## Response to questions:\n\n1) The proportional regime (where n,d, p are of the same order) studied in the paper is indeed much more challenging than the population regime where the sample size $n\\gg d,p$. In the population regime, the variance of the estimator goes to zero and we are essentially left with a deterministic estimator. However, as we mentioned in the paper, the population regime is not relevant to practical situations as many ML systems (in particular neural nets) have a humongous number of parameters, on the order of number of training samples.\n\n2) Please see our response above (#1 in weakness)\n\n3) Yes, the target in this case is just random noise, but note that the two estimators are using different features to fit to this noise vector (one uses individual features and one uses cluster centers), so you will naturally have different estimators and so different risks.\n\n4) We have indeed observed this phenomena on a click-through-rate dataset of users on a pool of ads. However, due to privacy of users we are not permitted to share that data.   \n\n5) Although our theory is for an asymptotic regime, as we show in the simulations, when $n,d,p$ are only a few hundreds we already see a great match between theory and simulations. \n"}]

Author rebuttal:
We would like to sincerely thank all the reviewers for taking time to review our paper and for the valuable feedbacks. A common comment raised by some of the reviewers was on the limitation of the work and whether the message of our paper goes beyond linear regression. 

We expect the virtue of look-alike modeling on generalization to apply in a broad range of settings. The high-level intuition is that the look-alike modeling acts as a regularizer and can improve the generalization by reducing the variance, an observation that is not limited just to linear regression. To support it empirically, here we provide additional experiments for a nonlinear data model. We consider the setting where the response is generated as $y = \exp(X\theta_0 + \varepsilon)$, with $\varepsilon$ Gaussian noise, and the estimators are obtained by fitting a generalized linear model with logarithm link function and poisson distribution. As the plot in the attached pdf shows, at smaller SNR we observe a gain in the generalization of the look-alike estimator over the vanilla estimator which uses individual sensitive features (similar behavior to Fig 3a in the paper). 

In terms of theory, a similar approach based on CGMT can be used to handle other loss functions, albeit leading to a much more complicated formula for the generalization, which is less transparent in showing the message. Nonetheless, a limitation of our analysis is the distribution of features, as the CGMT strongly relies on the gaussianity of the features. 


Meta-review: The paper studies linear regression where some coordinates of the covariate x are not revealed directly to the learner, and only a cluster-wise average is revealed for those coordinates. This change in the covariates x is called look-alike clustering and it has been used for protecting sensitive attributes in prior work.  The authors show closed-form formulas for the asymptotic performance with and without look-alike clustering. This allows the authors to identify regimes when look-alike clustering improves the performance. They also included experimental results verifying the formulas.
Decision: Accept (poster)