Learning from Aggregate responses: Instance Level versus Bag Level Loss Functions
Authors: Adel Javanmard
Lin Chen
Vahab Mirrokni
Ashwinkumar Badanidiyuru
Gang Fu
Venue: ICLR 2024 poster (2024)
Keywords: aggregate learning
asymptotic analysis
bias
variance
privacy
regularization
Primary area: learning theory
TL;DR: A precise comparison between the bag-level loss and the event-level loss functions for aggregate learning in terms of bias, variance and risk

Abstract: Due to the rise of privacy concerns, in many practical applications, the training data is aggregated before being shared with the learner to protect the privacy of users' sensitive responses. In an aggregate learning framework, the dataset is grouped into bags of samples, where each bag is available only with an aggregate response, providing a summary of individuals' responses in that bag. In this paper, we study two natural loss functions for learning from aggregate responses: the bag-level loss and the instance-level loss. In the former, the model is learned by minimizing a loss between the aggregate responses and aggregate model predictions, while in the latter, the model aims to fit individual predictions to the aggregate responses. In this work, we show that the instance-level loss can be perceived as a regularized form of the bag-level loss. This observation allows us to compare the two approaches with respect to the bias and variance of the resulting estimators and to introduce a novel interpolating estimator that combines the two approaches. For linear regression tasks, we provide a precise characterization of the risk of the interpolating estimator in an asymptotic regime where the size of the training set grows in proportion to the feature dimension. Our analysis enables us to theoretically understand the effect of different factors, such as bag size, on the model's prediction risk. Additionally, we propose a mechanism for differentially private learning from aggregate responses and derive the optimal bag size in terms of the prediction risk-privacy trade-off. We also carry out thorough experiments to corroborate our theory and show the efficacy of the interpolating estimator.

Published as a conference paper at ICLR 2024
LEARNING FROM AGGREGATE RESPONSES: INSTANCE LEVEL VERSUS BAG LEVEL LOSS FUNCTIONS
Adel Javanmard Lin Chen', Vahab Mirrokni', Ashwinkumar Badanidiyuru', Gang Fu' 'Google Research, Unniversity of Southern Califormia (adel javanaa rd, 1 Linche, mi rrokni, www.waakwwwaaaaaaa thomasfu fu egg.oallffuooogge..c.oo
ABSTRACT
Due to the rise of privacy concerns, in many practical applications, the training data is aggregated before heing shared with the learner protect the privacy of users' sensitive responses. In an aggregate learning framework, the dataset is grouped into bags of samples, where each bag is available only with an aggregate response, providing a summary of individuals' responses in that bag. In this pa- per, we study two natural loss functions for learning from aggregate responses: the bag-level loss and the instance- loss. In the former, the model is learned by minimizing a loss between the aggregate responses and aggregate model pre- dictions, while in the latter, the model aims to fit individual predictions to the aggregate responses. In this work, we show that the instance-level loss can per- ceived regularized form of the bag-level loss. This observation allows us compare the two approaches with respect to the bias and variance of the resulting estimators and to introduce novel interpolating estimator that combines the two approaches. For linear regression tasks, we provide a precise characterization the risk of the interpolating estimator in an asymptotic regime where the size of the training set grows in proportion to the feature dimension. Our analysis enables us to theoretically understand the effect of different factors, such as bag size, on the model's prediction risk. Additionally, we propose mechanism for differentially private learning from aggregate responses and derive the optimal bag size terms of the prediction risk-privacy trade-off. We also carry out thorough experiments to corroborate our theory and show the efficacy of the interpolating estimator.
INTRODUCTION
Machine learning has revolutionized many industries and aspects of our lives, but its widespread use has also raised concerns about privacy. One way to address these concerns is to use aggregate
labels, which are labels assigned to groups of data points rather than to individual data points (Criteo) Privacy Preserving MI. Competition] 202T). Since even before the machine learning era, aggregate labels have been commonly used in group testing, a method that combines samples from various individuals or objects to maximize the use of limited resources (Wein & Zenios 1996] (Sunjaya & Sunjaya 2020). For example, group testing is used to screen for HIV in donated blood products and to identify viral epidemics, such COVID-19. In recent years, there has been growing interest in using aggregate labels to train machine learning models (Papernot et al., 2016]] Al-Rubaie & Chang. 2019 De Cristofaro 2020). This approach has the potential preserve privacy while still allowing for the development of accurate and effective models. The SKAdNetwork API from Apple is an example of how aggregate labels can be used to preserve privacy in machine learning (Apple Devel- opeer Documentation 2023). SKAdNetwork provides advertisers with insights into the effectiveness of their ad campaigns without compromising the privacy of users. This is achieved by using aggre- gate labels to represent groups of users who have interacted with an ad. For example, an advertiser might receive a report indicating that 10% of users who saw their ad installed their app. However, the advertiser would not be able to see the specific identities of those users. Another example is the Private Aggregation API of Chrome Privacy Sandbox. This API collects instance-labe label pairs from users, but it protects their privacy by providing apps and services with bags of instances that labeled in an aggregated way. The aggregate label can be further perturbed to ensure differential privacy, which is mathematical guarantee that the data cannot be used to identify individuals.

---

Published as a conference paper at ICLR 2024
To formally describe the setup, consider dataset consisting of samples (æ,, Mt), for i [n], with 2; E R being the features vector and E RR being the response variable. Motivated by applications where the response variables Y4 carry private information, instead of sharing individual responses with the learner, only aggregate responses are shared as follows: set m non-overlapping bags B. [n). for E [m]) formed, each of size k. For each bag, the average response Ya B. W.)/k is shared with the learner, along with the individual features vectors Z;.
(ZiE
There are two common choices for learning from aggregated data:
Bag-level loss: The model is learned by minimizing loss function that measures the distance be- tween aggregate responses and the aggregate model predictions. Namely, 0 arg ming Prag (0)
with
bbgg (0)
Ya. K
Σ fo(z.)), I.
Σ
(1)
where ((:-)) Rzo. and fo a family of models parameterized by 0.
Instance-level loss: The model learned by minimizing the loss between the aggregate responses and individual model predictions. Namely, arg ming Lins with
Lins (0.
mk Σ
1
Σ
(TTa, fo(x:))
advantage of bag-level loss is that since it involves aggregate model predictions, it provides a layer of protection for the features, in addition to responses. For example, in the case of linear models, the learner can still minimize the bag-level loss, given only access to the aggregate responses and the aggregate features.
Despite the common use of bag-level loss and instance-level loss, we still lack a clear understanding of the performance of models learned by each approach, measured in terms of model general- ization error. One of our contributions this paper is to establish a connection between the two losses and shed light when outperforms the other in terms of model generalization. We build strong intuitive understanding through precise quantitative statements. The key observation that employing bag-level loss leads models with reduced bias but increased variance, as op- posed to models trained with instance-level loss. Therefore, in scenarios with diverse responses, instance-level loss is more effective. Conversely, for use cases with more homogeneous responses, the bag-level loss is preferable, as it proves more effective in reducing bias.
1.1 SUMMARY OF CONTRIBUTIONS AND ORGANIZATION OF THE PAPER
Our contributions are summarized as follows:
(i) We show that the instance-level loss can be perceived as the bag-level loss with an additive regularization term. While the regularization penalty introduces bias into the estimator, it also serves to reduce variance when the sample size (n) is comparable to the feature dimension (d). Depending on the interplay between bias and variance, one loss may outweigh the other, resulting in model with better generalization. Motivated by this observation, we propose a new estimator that includes a tuning parameter P [0. 1] to control the strength of the regularization and, hence, the bias-variance trade-off. The case of = 0 corresponds to the bag-level loss, and the case of p = corresponds to the instance-level loss. However, by optimally tuning p. we can obtain models that outperform both of these cases.
(i)) We next focus on the so-called proportional regime where the sample size (n) and the feature dimension (d) are of the same order, i.e., n/d > tb, for some arbitrary bounded constant t e (0, Do), as n - oo. This asymptotic regime has attracted significant interest in recent years due to its relevance in practice, where the classical population regime (n/d - oc) fails to capture the behavior of overparametrized machine learning models (see e.g., Hastie et al. (2022): Javanmard et al. (020);; Hassami & JavaJaaannna Javanmard (2022) ; Mei & Montanari (2022)). In Section 2.2 focus on linear models and derive a precise characterization of model generalization error for both the bag-level and the instance-level losses. Our precise theory captures the effect of different
2

---

Published as a conference paper at ICLR 2024
quantities of interest, such as bag size k, overparametrrizatoo, signal-to- tignal-tonooiee ratio of the data, and the regularization parameter on the model performance. It also allows us to compare the two approaches in terms of bias and variance and theoretically find the optimal regularization parameter as described in the previous item.
(iii)
In Section 4 we propose differentially private mechanism for learning from aggregate data. It is based on the Laplace mechanism, which adds Laplace noise to the aggregate responses to ensure e-(label) differential privacy. For given privacy loss E, our theory in Section 2.2 allows us to derive the optimal size of the bags that results in the best model generalization. Interestingly, the singleton bags are not always the optimal choice, which implies that applying the Laplace mechanism to aggregate data gives better privacy-model generalization trade-off compared to directly applying the Laplace mechanism to individual responses.
1.2 RELATED WORK
There is rich body of prior work on learning with label proportions (LLP) (Shi et al. 2018
2019
Cui et al., 2017 Xiao et al. 2020; Li & Wang 2018 Quadrianto et al. 2008 Patrini et al.
2014
Musicant et al.) 2007| Zhang et al.
2020:
Qi et al. 2017 Chen et al., 2017 Lu et al.
2019
2024 In what follows, we categorize previous work into bag- Chen et al. [023 Javanmard et al.
level, instance-level and other methods.
Bag-level methods. [Rueping (2010) proposed large-margin support vector regression (SVR) method for learning with label proportions (L.PP). The proposed approach models the mean of each bag "super-instance with soft label equal to the label proportion of the bag. Yu et al. (2014) introduced the Empirical Proportion Risk Minimization (EPRM) framework, which minimizes the uniform convergence bound for the gap between the empirical and population bag-level loss functions. |Ardeaaly & Cu-) lotta (017) applied the aggregated cross-entropy loss to deep learning and classification problems.
bag-level loss function. Yu et al. (2014) also derived a VC-dimension-baase
Instance-level methods. Yu al. (2033 proposed a method that also uses the idea of support vector regression (SVR), but models the probability of each instance rather than each bag, in contrast to Rueping (2010). The proposed loss function has two components: (1) the sum of the hinge losses between the unknown individual label and the predicted label of each instance, and (2) the sum of the losses between the label proportion of the unknown individual labels of each bag and the true label proportion of that bag. "bulac-Amold et al. (2019) uses a similar idea to (Rueping 2010) and considers relaxation to make the optimization problem more tractable. For classification problems, Busa-Fekete et al.) (2023) derived an unbiased estimator of the individual labels of the data examples.
This estimator is function of the label proportion of the bag to which the example belongs and the probability distribution of all labels in the population. By using this estimator of the individual labels, one can apply the usual supervised learning methods.
Other related works. Quadrianto et al. (2008) proposed a kernelized conditional exponential model for inferring the individual labels of unseen examples based on training examples grouped in bags and the label proportion of the bags. The method is based on maximizing the log-likelihood of the model. A key assumption of the model is that the features of example
conditionally indepen- dent of the bag to which it belongs, given the example's ' label. Fish & Reyzin (2017) formally defines the class of functions that can be learned from label proportions (LLP Learnable) and resolves foun- dational questions about the computational complexity of I.IP and its relationship to PAC learning. Scott& & Zhang (2020) solves the LLP problem through reduction mutual contamination models (MCMs), Saket (202T) investigated the learnability of linear threshold functions (LTFs) from la- bel proportions. Saket al. (2022) proposed method for combining bag distributions to improve learning from label proportions. While in this work we focus on random bagging, other bagging schemes based on features are proposed recently by Chen et al. (2023) and Javanmard et al. (024))
MAIN RESULTS
2.1 INTUITION: INSTANCE-LEVEL LOSS ACTS AS A REGULARIZED BAG-LEVEL LOSS
In this work establish connection between level and instance- losses, showing that the latter can be perceived as a regularized version of the former. We first show this claim for quadratic loss and then discuss extension general convex losses.
3

---

Published as a conference paper at ICLR 2024
Lemma 2.1. Consider the quadratic loss E(x, y) (Ir y)? For the bag-level loss and the instance-lewe loss ( we have
Lins Crag (0) +R)))
where the regularization term R(0) given by
1 Σ Σ (fo(æ;) - fo(x,)))² k:
R(0)) =
a-li.j..
Note that the regularization term R(0) does not depend on the responses, but it does depend on the feature vectors. While traditional regularization techniques only depend on model parameters, there is also a growing body work on data-dependent regularization. This type of regularization explicitly takes into account the training data during the regularization process, which can lead to improved generalization performance in certain settings (Shivaswamy & Jebara 2010) (Zhao et al.) 2019 Mou al. 2018). In addition, R(0) captures the within cluster variations of the model predictions, While the additive regularization induces bias to the estimator minimizing the instance- level loss, it can reduce the variance when the sample size and features dimension are comparable.
Also note that when the bag-level loss does not have a unique minimizer, the regularization term promotes solutions with smaller (0). Therefore, if the true model also has small penalty value, this will help to impose this structure on the estimator.
Motivated by Lemma 2.1
we introduce an interpolating loss Line which keeps the same form of the regularization but includes a tuning parameter to control the strength of the regularization, namely
Lint (0) == Lany (0) (0)++ ()(()), P E 10.
In practice, the optimal value of can be set via cross- validatoiiotionn to obtain the best model perfor- mance. In the next section, we provide a theory for linear models which also allows us to analytically derive the optimal choice of p.
We conclude this section by extending lemma to other loss functions.
Lemma 2.2. Consider the loss function 8 R x R R22 with continuous second derivative in the second argument. Also suppose that
8 E(a, b) S C for a constant C. We then have the following 362 relation between the bag- bag-level loss 77) and instance-level loss (
Lins(0) S Coag( (0) - CR(()).
(5)
where the regularization R(0) is given by 3 In addition, if ((---) ) is convex in the second argument have Laag ( < Lims (f) for any model O.
We refer to the supplementary for the proof of Lemmas 2. and 2.2.
2.2 LINEAR MODELS: A PRECISE THEORY
Consider dataset of i..dd pairs (.), for E [nn]. with æ; RR a feature vector and y/ E RR response variable. We assume the following linear model for the responses:
= x 0o + wi,
where w; are i.i.d noise with E(w;) = and Var(w,) = a². We collect the responses into a vector R" and the features in matrix X Raxd (with rows 2; Rd).
We consider a setting where the features are i.i.d Gaussian vectors x; ~ (O, Ia). Consider a model 0. trained on the data X, y and test point Frest (0, Ia), independent of the training data X, y- The prediction risk of 0 is defined by
Risk x (0) [B[ test 0- x 0000 X | - 0
Note that our definition of the risk is conditional on X and is made explicit our notation Riskx. In addition, the vtaiinnieeee decomposition of the risk is given by
Risk x (0) Biasx (0) + Varx
(6)
Bias (0) ||0, E 111
Varx (0) tr(Cov(8)x)))
4

---

Published as a conference paper at ICLR 2024
Recall our interpolating loss given by 4h. Specializing to linear model fo(æ) =x"0 and quadratic loss, we arrive at
Lint (0) = Lbag(0) pR(() pR(())
Lbag (0) pl Lim (0) Lbag(0))
Σ Σ
(11- x²² + ply, x 0)))
2mk
a= 1e1.., Ba
with Ya and Ra respectively denoting the average response and average of feature vectors in bag a. We also define mt == arg ming Lint (0).
In this section, we derive a precise characterization of the bias and variance of m Our theory pro- vides precise understanding the role of different factors, such as bags size k, overparametriza- tion, and signal-to-noise ratio of the data. It also allows us to theoretically derive optimal regular- ization parameter p.
We next describe the the asymptotic regime of interest and our assumptions.
Assumption 2.3. (Asymptotic Setting) We focus the so-called 'proportional" regime where the sample size n and the features dimension d grow in proportion as d - oc. Formally for an arbitrary but fixed constant v (1, 00), have n - th. We further assume that the size of bags (k) remains fixed as + oc, and the model norm ||0||| converges. For the sake of normalization and without loss of generality, we assume lim oo 10.l
We next state our assumption on the bagging structure.
Assumption 2.4. We assume that the bagging configuration is independent from the training data (X, 3). In addition, we assume that the bags are non-overlapping, so that each sample appears in exactly one bag.
Theorem 2.5. Consider data generated according to linear model in an asymptotic regime de- scribed in Assumption 2.3 Also suppose that the bugs are of size k and are non-overlapping as described in Assumption 2.4 The bias and variance of Out are characterized below:
Bias: For k > 1 and p > 0, let a. be the nonnegative fixed point of the following equation:
w p(k kk 1).
p+
k a.)
ka.
The bias of mmm converges in probability to
a
Biasx (0mt)
(8)
11
)2
(1-0.
kf or p= O, then Oun unbiased.
Variance: Let (ve, u.) be the solution of the following system of equations:
pvb(k - -1)
p+ =
1
(1++v) +
p² -
(0 + u)²
=
We then have
Var (0mmt (p) 0²)
U+
DISCUSSION
3.1 COMPARISON BETWEEN BAG-LEVEL AND INSTANCE-LEVEL ESTIMATORS
We next specialize the result of Theorem 2.3 to = (corresponding to the bag-level loss) and p (corresponding the instance-level loss). Note that the bag-level loss is the ordinary least
5

---

Published as a conference paper at ICLR 2024
square estimator with n/k samples and d parameters and therefore is well-defined only for n 2 kd. In the asymptotic regime of Assumption 2.3 this implies that v = lim n/d 2 k.)
The following corollary characterizes the bias and variance of the bag-level and the instance-level estimators.
Corollary 3.1. The followings hold:
Bag-level loss: Suppose vb 2 k. For the bag-level estimator 0 == arg ming Lbag(O), we have
0²
Bias (0
I 0,
Varx (Gbag)
Instance-level loss: For the instance-level estimator Oms arg ming (0), we have
Biasx (0ins)
(P) (1 (1-T) Te)
k(1 1)) Var (0mss)
2 2
(p)
o²
k( 1))
As see from the above characterization, while the bag-level loss is unbiased, it has higher variance compared to the instance-level loss. The dominance of one estimator over the other in terms of prediction risk (6) depends on the relative magnitudes of bias and variance.
In the next lemma, we provide threshold on the model signal-to-noise ratio (SNR), defined as SNR 10/l1//a2 under which the bag-level estimator the smaller risk and above the instance-level loss has the smaller risk.
Lemma 3.2. Suppose &o 2 k >
Then, Riskx (0ms) I Riskx (Gvag) if and only if
1 r²
(k: 1)1-
SNR
(vb (v
1
For k == 1, we have :un 0 bag and they have the same risk.
Intuitively, when the SNR is low it means that the variance of the samples is large relative to the model strength. In this case, the instance-level loss which aims to decrease the variance, at the cost of increasing bias, obtains lower prediction risk than the bag-level estimator.
3.2 ROLE DIFFERENT FACTORS ON MODEL RISK
Our theory allows to precisely characterize the effect of different factors, namely the bag size, SNR, overparametrizztioon and the regularization parameter on the bias, variance and risk of the estimator. In Figure] I we plot the theoretical curves derived in Theorem 2.5 versus p. As we see by increasing p (stronger regularization), the bias increases and the variance decreases. The curves for the risk (rightmost panel) exhibits an optimal that balances the trade-off between bias and variance. The first row of plots shows the effect of SNR on the curves. As expected, higher SNR reduces the model variance, but has no effect on the bias, and so reduces the risk. The second row of plots shows the effect of bag size k. Larger induces more bias. For small p. larger increases the variance, but large p, increasing i reduces the variance. The last row of figures shows the effect of s n/ d. Larger vi decreases bias, variance and the risk since it corresponds to more samples relative to the number of parameters to be estimated.
4 DIFFERENTIALLY PRIVATE AGGREGATE LEARNING
As we discussed aggregate learning framework provides some layer of privacy protections by ob- fuscating the individual responses and only revealing aggregate responses in each bag. In particular, when the bags are non-overlapping and each are of size at least ki replacing individual responses with the aggregate ones offers e-anonymity, a privacy notion, stating that any record is indistinguish- able from at least & other records, in terms of response. One also argue about the information leakage in aggregate learning through the notion of mutual information between individual and ag- gregate responses, conditional the features vectors.

---

Published as a conference paper at ICLR 2024
Variune,,
0.5
1.5
144
0.4
ShR
ShR
0.5
0.6
0.1
0.2
Baax, S o 10
Varisnse, SNF--2 5f 10
Ridk, SNR--0 e
12
3.5
0.5
0.4
0.2
0.2
0.2
0.2
0.4
0.8
0.8
0.2
0.4
0.5
0.8
0.2
0.4
0.6
0.8
Bias, 5NB Ai-
Vicisues, SNR km
Risk, SNR-2
0.5
0.5
0.5
0.0
0.3
0.4
0.1
0.2
0.4
3.5
0.8
0.2
0.4
0.0
0.8
0.2
0.4
0.6
0.8
Figure 1: Effect of SNR, bag size (k) and overparametrrizaioon (1/b- = d/n) on the bias, variance and the risk of the model. The curves are the theoretical curves given by Theorem 2.5
Another widely used privacy notion is differential privacy (DP), put forward by Dwork et al. (2006b)a). a). Informally speaking, a mechanism (data processing algorithm) is called DP, if its out- put distribution does not change significantly if a single record is changed in the input dataset. We focus on the notion of label differential privacy, introduced by CCaudhuri & Hsu (20TT), in which the changes only happen on the 'response" of single record. Label DP is also widely used for applications where only the privacy of the responses are concerned, in opposite to all features. For example, in a medical test, the demographic features of patients may be far less private than the re- sponses (medical test results). We recall the formal definition of label DP from (Chaudhuri & Hsu 2011).
Definition 4.1. (Label Differential Privacy) Consider randomized mechanism M : D - O that takes as input dataset D and outputs into O. mechanism M is called E- label DP, if for any two datasets (D, D') ) that differ in the label of a single example and any subset O C O we have
PP(M(D) 0 s <P(MM(D) e),
where E is the privacy budget.
It is easy to observe that the framework of learning from aggregate data, alone does not provide (label) differential privacy. In this section we propose a mechanism which adds noise to the aggre- gate (truncated) responses ensure label DP guarantee. The procedure is outlined in Algorithm T The truncation level is of order Vlog n., so that with high probability it does not happen. But this truncation step provides us an upper bound on the responses which we use bound the sensitivity of aggregate responses and decide on the noise variance needed to ensure DP.
Lemma 4.2. The mechanism described in Algorithm is e-label DP.
With slight abuse of notation, we let Tmt be the minimizer of the interpolating loss, when the learner uses the privatized aggregate responses Ga, a E [ml provided by Algorithm [ By Lemma 4.2 and the post-pree pros-processing property of differential privacy, 0,n is also e-label DP. In the next theorem, we use our theoretical result from Section 2.2 to characterize the risk of ine in terms of privacy loss e and the bags size kt among other factors.
7

---

Published as a conference paper at ICLR 2024
I Label differentially private learning from ag- gregate data
Algorithm
Optimal
Input: individual responses {yr { bags (Bela each of size truncation level C.
Output: Privatized aggregate responses Ù1 Fm
// Clip the responses
2: for = 1,2,.... .... do
3: yf f- max(min(()) Cvlog n), -Cllogn)
kag(o)
4: end for
Figure 2: Optimal bag size k as a func- tion of log(p), for label DP learning from aggregate data. We observe phase transition, where for some p. P P., = 1 is the best choice while for > Pa the largest is optimal.
5: for a = 1, 1........ do
6: Da
B. Vi
7: Da s Ya + za where za ~ Laplace
Cvlogn ke
8: end for
Theorem 4.3. Let Int arg ming (ine using the privatized aggregate responses from Algo- rithm ! with C > 2(1 o²). Let (v., U.) be the solution of the following system of equations:
v
palk - -1)
p+u =
1
+11+
p2yp(k 11
k.
(1+
(p +o+ u)²
We then have
1 log 7
(p) 20 1
Risk x (0mnt)
(10)
he U.
A virtue of Theorem 4.3 is that it allows to decide on the optimal bag size k which minimizes the risk of the estimator O On the side, large bag sizes allow the aggregate responses to be less sensitive to each individual response, which means smaller noise is needed to ensure s-DP. On the other hand, small p. larger i can cause larger instability because it amounts to fewer bags and hence fewer (aggregate) labels. As increases, the regularization becomes stronger and brings more stability. In Figure we plot optimal k. (from the bounded set {1...., 5)) versus p. Interestingly, we observe a phase transition in the sense that for some p.. if < p. then k = 1, due to the instability effect explained above, while for p P. the regularization mitigates the stability issue and the first effect (DP noise) outweighs, making k- = 5 the optimal choice. We also see that the phase transition threshold p. increases as & decreases. Recall that n/d, and the instability due to sample size is stronger at smaller vp. Hence, larger regularization is needed to control it. Also note that we optimize jointly over (k:, p). the risk minimized at p = 1 and i 5, i.e., the leseelc-leevel loss with the largest possible value of k in the predetermined range.
5 NUMERICAL EXPERIMENTS
Numerical verification of the theory In our first set of experiments, we corroborate our theory derived in Section 2.2 with simulations. We set 100 and generate 0g have i.id normal entries and then scale it to be unit norm. The sample size is set as n vld and the noise standard deviation set as a I/SNR
1/SNR. The solid curves Figure B are the theoretical curves and the dots correspond to the simulation. Although the derived theory in asymptotic regime, already see a perfect match for d == 100.
Boston Housing dataset. To investigate the optimal value of the regularization parameter p in the interpolating loss, for different bag sizes, we conduct numerical experiments on the Boston Housing dataset. Recall that p O corresponds to the bagelevel loss and م 1 corresponds to the instance-leved loss. The Boston Housing dataset is a regression dataset that predicts the median value of owner-occupied homes in Boston, Massachusetts, in the 197-s (Harrison Jr & Rubinfeld
8

---

Published as a conference paper at ICLR 2024
1
SNR 21,) X1-
SNR 2, 2
Figure 3: Solid curves correspond are the theoretical curves (Theo- rem 2.5) and the dots (symbols) cor- respond to simulations. Here d = 100, and we already see a perfect match between the (asymptotic) the- ory and the simulations.
1.5
0.8
0.8
0.7
0.7
Risk
Rlok
Rigk
0.5
0.5
0.4
0.4
0.3
SNR
0.2
0.2
0.5
0.5
P
Figure 4: Test loss versus the regu- larization parameter p for different bag sizes, the Boston Housing dataset. The values on the lines rep- resent the mean of the test loss and the error bars represent the standard deviation of the test loss. The red dots denote the optimal value of that achieves the minimum test loss.
150
Min loss (p:0
Min loss (ge0-26)
80
Bog 2:20 100
eag sizo
120
100
150
Nin 1==0.00)
100
50
40
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Nin lods (2-0.84)
300
Min loss (p-0.581 Blg
Min loss (p=0.58)
150
200
sizu 180
Test
200
200
1000
100
1.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Min loss 1ammm An)
Min lons (pmnn 7R1
250
Min lnos (gm1 ..00)
locs
200
Bag dize 200
Bog 2:20 220
200
Bag dize 240
200
150
100
100
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
P
1978). The dataset contains 13 features, including the crime rate, per capita income, and the number of rooms per dwelling. We use feed-forward neural network to learn the housing prices in this dataset. The network has four hidden layers, each with 64 neurons. The activation function for all hidden layers is ReLU. The output layer has one neuron which outputs the predicted housing price.
We experiment with bag sizes ranging from 80 to 240. For each bag size, we plot the test loss against the regularization parameter p. For each value of i [0, 1], we train 20 models and compute the mean and the standard deviation of their test loss. The results are shown in Figure 4 where the values on the lines represent the mean of the test loss and the error bars represent the standard deviation of the test loss. We also use red dots to denote the optimal value of p that achieves the minimum test loss.
From Figure 4 we have the following observations: First, for a fixed bag size, smaller values (which means that the loss is closer to the bag-level loss) yield larger variance, while larger / values (which means that the loss is closer to the instance-level loss) yield smaller variance. This confirms our theory that the instance-level loss actually has regularization effect (as shown in Lemma (.1) Second, as the bag size increases, the optimal value increases. For example, when the bag size 80, the optimal p value is while when the bag size is 240, the optimal p value is For bag sizes between 80 and 240, the optimal value is achieved in (0, 1). In other words, larger bag sizes require stronger regularization (larger p) to achieve the minimum test loss.
CONCLUSION
In this paper, we studied the problem of learning from aggregate responses, a privacy-preserving machine learning technique. We compared two loss functions for aggregate learning and proposed novel interpolating estimator. We also provided a theoretical analysis of the interpolating estimator for linear regression tasks and proposed mechanism for differentially private learning from aggre- gate responses. Finally, we conducted experiments to corroborate our theory and show the efficacy of the interpolating estimator.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
Adel Javanmard is supported in part by the NSF CAREER Award and the NSF Award DMS-2311024.
REFERENCES
Mohammad Al-Rubaie and J Morris Chang. Privacy-preserving machine learning: Threats and solutions. IEEE Security & Privacy, 17(2) 2019.
Apple Developer Documentation. Apple storekit ad network. lattps://develope::: apple. 2023.
com/ http///uetttteoo///ooeee////aaaa
Ehsan Mohammady Ardehaly and Aron Culotta. Co-training for demographic classification using deep learning from label proportions. In 2017 IEEE International Conference on Data Mining Workshops (ICDMW), pp. 1017-1024. IEEE, 2017.
Robert Istvan Busa-Fekete, Heejin Choi, Travis Dick, Claudio Gentile, et al. Easy learning from label proportions. arXiv preprint arXiv:2302.03/ 2023.
Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learn- ing. In Proceedings of the 24th Anmual Conference on Learning Theory, pp. 155-186. JMLR
Workshop and Conference Proceedings, 2011.
Lin Chen, Thomas Fu, Amin Karbasi, and Vahab Mirrokni. Learning from aggregated data: Curated bags versus random bags. arXiv preprint SxXiv:2305005557 2023.
Zhensong Chen, Zhiquan Qi, Bo Wang, Limeng Cui, Fan Meng. and Yong Shi. Learning with label proportions based on nonparallel support vector machines. Knowledge-Bar Based Systems, 119: 126-141, 2017.
Criteo Privacy Preserving ML Competition. Criteo preserving ML competition AdKDD 2021. http:://Dee..........eeeeeaeaacd
Zip 2021.
Limeng Cui, Jiawei Zhang, Zhensong Chen, Yong Shi, and S Yu Philip. Inverse extreme learning machine for learning with label proportions. In 20/7 IEEE International Conference on Big Data (Big Data), pp. 576-585. IEEE, 2017.
Emiliano De Cristofaro. arXiv:2005.0867, 2020.
An overview of privacy in machine learning.
arXiv preprint
Gabriel Dulac-Arood, Neil Zeghidour, Marco Cuturi, Lueas Beyer, and Phinlppi Vert. Deep multi-class learning from label proportions. arXiv preprint arXiv:1905, 12909, 2019.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual international conference on the theory and applications of cryptographic techniques, pp. 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006b.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):21 1-407, 2014.
Benjamin Fish and Lev Reyzin. On the complexity of learning from label proportions. In Proceed- ings of the 26th International Joint Conference on Artificial Intelligence, pp. 1675-1681, 2017.
Ychoram Gordon. On milman's 's incquality and random subspaces which escape through mesh in R". In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1986-87, pp. 84-106. Springer, 1988.
David Harrison Jr and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. Journal of environmental economics and management, 511):11100, 1978.
10

---

Published as a conference paper at ICLR 2024
Hamed Hassani and Adel Javanmard. The curse of overparametrizzatoon in adversarial train- ing: Precise analysis of robust generalization for random features regression. arXiv preprint arXiv:2201.05119, 2022.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pp. 2034-2078, PMLR, 2020.
Adel Javanmard, Matthew Fahrbach, and Vahab Mirrokni. Priorboost: An adaptive algorithm for learning from aggregate responses. arXiv preprint 0et::2242.04987,, 2024.
Yue Li and Bo Wang. A study on customer churn of commercial banks based on learning from label proportions. In 2018 IEEE International Conference Data Mining Workshops (ICDMW), pp- 1241-1247. IEEE, 2018.
Nan Lu, Gang Niu, Aditya Krishna Menon, and Masashi Sugiyama. On the minimal supervision for training any binary classifier from only unlabeled data. In International Conference on Learning Representations, 2019.
Song Mei and Andrea Montanari. The generalization error random features regression: Precise asymptotics and the double descent curve. Communications Pure and Applied Mathematics, 75(4):667-766, 2022.
Wenlong Mou, Yuchen Zhou, Jun Gao, and Liwei Wang. Dropout training, data-dependent reg- ularization, and generalization bounds. In International conference machine learning, pp- 3645-3653. PMLR, 2018.
David R Musicant, Janara M Christensen, and Jamie F Olson. Supervised learning by training on aggregate outputs. In Seventh IEEE International Conference on Data Mining (ICDM 2007), pp- 252-261. IEEE, 2007.
Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael Wellman. Towards the science of security and privacy machine learning. arXiv preprint 1xXiv:161.0038/1 2016.
Giorgio Patrini, Richard Nock, Paul Rivera, and Tiberio Caetano. (almost) label cry. Advances in Neural Information Processing Systems, 27, 2014.
Zhiquan Qi, Bo Wang, Fan Meng, and Lingfeng Niu. Learning with label proportions via npsvm. IEEE transactions on cybernetics, 47(10):223-33006 2016.
Zhiquan Qi, Fan Meng, Yingjie Tian, Lingfeng Niu, Yong Shi, and Peng Zhang. Adaboost-llp: boosting method for learning with label proportions. IEEE transactions on neural networks and learning systems, 29)))335883355) 2017.
Novi Quadrianto, Alex J Smola, Tiberio S Caetano, and Quoe V Le. Estimating labels from label proportions. In Proceedings of the 25th international conference on Machine learning, pp. 776- 783, 2008
Stefan Rueping. Svm classifier estimation from group probabilities. In Proceedings of the 27th international conference on machine learning (ICMI-10), pp. 911-918, 2010.
Rishi Saket. Learnability of linear thresholds from label proportions. Advances in Neural Informa- fion Processing Systems, 34:6555-6566, 2021.
Rishi Saket, Aravindan Raghuveer, and Balaraman Ravindran. On combining bags better learn from label proportions. In International Conference on Artificial Intelligence and Statistics, pp- 5913-5927. PMLR, 2022.
Clayton Scott and Jianxin Zhang. Learning from label proportions: A mutual contamination frame- work. Advances in neural information processing systems, 33:22256-2223 2020.
Yong Shi, Jiabin Liu, Zhiquan Qi, and Bo Wang. Learning from label proportions on high- dimensional data. Neural Networks, 103:9-18, 2018.

---

Published as a conference paper at ICLR 2024
Yong Shi, Limeng Cui, Zhensong Chen, and Zhiquan Qi. Learning from label proportions with pinball loss. Interaational Journal of Machine Learning and Cybernetics, 10(1):187-205, 2019.
Pannagadatta K Shivaswamy and Tony Jebara. Maximum relative margin and data-dependent regu- larization. Journal of Machine Learning Research, 11(2), 2010.
Angela Felicia Sunjaya and Anthony Paulo Sunjaya. Pooled testing for expanding covid- mass surveillance. Disaster Medicine and Public Health Preparedness, 14(3):e42-ed) 2020.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pp. 1683-1709. PMLR, 2015.
Roman Vershynin. #ligh-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Lawrence M Wein and Stefanos A Zenios. Pooled testing for hiv screening: capturing the dilution effect. Operations Research, 44(4):543-500 1996.
Yanshan Xiao, HuaiPei Wang, and Bo Liu. A new transfer learning-basee method for label propor- tions problem. Information Sciences, 541:391 1-80, 2020.
Felix Yu, Dong Liu, Sanjiv Kumar, Jebara Tony, and Shih-Fu Chang. xSVM for learning with label proportions. In International conference on machine learning, pp. 504-512. PMLR, 2013.
Felix X Yu, Krzysztof Choromanski, Sanjiv Kumar, Tony Jebara, and Shih-Fu Chang. On learning from label proportions. arXiv preprint arXiv:1402.5902, 2014.
Yivan Zhang, Nontawat Charoenphakdee, Zhenguo Wu, and Masashi Sugiyama. Learning from aggregate observations. Advances in Neural Information Processing Systems, 33:7993-8005, 2020.
Han Zhao, Yao-Hung Hubert Tsai, Russ R Salakhutdinov, and Geoffrey Gordon. Learning neural networks with adaptive regularization. Advances in Neural Information Processing Systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2024
A PROOF OF THEOREMS AND TECHNICAL LEMMAS
A.1 PROOF OF LEMMA 2.1
Recall the shorthand Ya = (EiEB, Vi)/k, for a E [m]. We have,
1
Lins( mi
(ja- fo(21))2
a=1 Ba
1
Σ
Da
1
Σ fo(az))
+
1
Σ
fo(æ;) - ff((z)) 2
mk
k
K
a=1
je
m
m
Σ fo(wx))
Σ fo(w)) fo(
mk
Da
k
mk
K
jEB.
jEB.
2 m
fo(z))
( Σ fo(xz) - fo(
+
Yu - k
mk
JeB
jEB
Note that the first term can be written
1 T
Σ )
Σ
m
1 Σ l frae(
ya
Vo
K
JEB.
jEB.
For the second term, we have
Σ E
E
folæ,) - fo(az)) = K
Σ (folæ.)) - fo(xx))² R(O),
ie B.
JEB,
ijEB.
where we used the following identity for a1...., Ok and ā (E a;)/k=
k (a. a)²
k
Σ
Σ
(a:
0z)²
(II)
k
i,
Finally, the third term works out at zero because
m
Jo
Σ
fo(æz))
Σ fo( sf((a)))
B
JEB
jEB.
m
1
Σ So(2,))
Σ So(mr)) so(m.)) =0,
Ua
K
jEB.
JEB.
since
Σ E
Σ
so(æ;) So(2:)
Σ So(æ;) Σ So(wx: = 0.
B.
JEB,
JEB.
iEB.
Combining the three terms together we arrive at Lins (0) Loag (0) + R(O).
A.2 PROOF OF LEMMA 2.2
for We use the shorthand fo (EieB, fo(w,))/k, for E [m]. By Taylor's expansion of the loss é on its second argument we have
i ((Ta, fo(x:)) (Voo + ab (( [a)(f((;)) - Fa)
0² 0b ((v., ())(()))) faa²
for some f between F.. and fo,);) and 0/0 a² /a indicate the first and second derivative of É(a, b) with respect to the second input b.
13

---

Published as a conference paper at ICLR 2024
Summing both sides of the above equation i Ba, the second term works out at zero since EiEB, (fo(x;) fa) = 0. Using the bound on the second derivative we arrive at
Σ
(Waa, Jo(x:)) S ke fa) + Σ C(Jo(a,) - fa)².
B.B.
SEB.
Next, summing both sides of the above equation over bags a E [m]] and dividing by mk, we get
Lins (0) S Lbag ( + Σ Σ
C(fo(x,) fa)².
GEliEB,
By invoking identity in the above we arrive at (5)
We now ready prove the second part of the statement. If the loss E(:,)) is convex in the second input, by the Jensen's inequality we have
1
Σ (īua, So(x:)) 2 (Ta Da. k iEB.
1 Σ so fo(
h VEB
Taking the average of both side over the bags a E [m]] we obtain that (ins 2 Lrag(0), which completes the proof of lemma.
B PROOF OF THEOREM 2.5
Recall m as the number of bags. and n as the number of samples. Since the bags non-overlapping and each of size k, we have m n/k. Define S E Tkmx,, as matrix the encodes the bagging structure, with Sia (ikk((jBB))) where B, indicates a-th bag, for E [m]]
We next write the bag-level loss function and the instance-level loss function in terms of S as follows:
Lhag (0) ||S x
km
Lins (0)
||S Sy x012
km
The interpolating loss function 7 then reads as
Lint (0) mk (1 Sxe S + + S SSyyl syl
This can equivalently be written as
Cine (0) 1
ypI mkk psp
(
(VPTT Sy
x0
SSy
The minimizer of the above loss admits a closed-froe -roeddffrmm solution given by 0.n By, with
B (X (pl + (c1-p)sTss 5) x) X STS
We define the shorthand := pI (1-p)S p)S S Rxxn which is non-singular for p > and M = (X EE) E _dx= We then have B = MS S.
We next recall the bias-variance decomposition
6 where the bias and variance are given by
Biasx (0mt) |I(BX 1)0.11
= |[MS SX MEX
= |M S - E) 1 Var (0m.) = IS 51 with || indicating the matrix Frobenius norm.
(12)
(13)
We continue by treating the bias and the variance separately.
14

---

Published as a conference paper at ICLR 2024
B.1 CALCULATING THE BIAS
Since the distribution of the features matrix X is invariant under rotation, we can assume that 0g ||Ou]le, where e, E R is the vector with one at i-th entry and zero everywhere else. By taking average on i E [d] we obtain
1
Bias (0mtt)
|MS
Ee.ll
iEI
1 MMS S -
Σ iE(p]
c,e, )
X ( -- )
| | S- --)s
E)
Let us define A E R as follows:
A = - -SS 5 - E)
-S" s (pI + -1 p)- S))
p([ - S).
(14)
The bias can then be written in terms of A as Bias (0) | In our next lemma, we characterize the asymptotic behavior of the bias.
M
Lemma B.1. Under the asymptotic regime of Assumption 2.3
have
MAXX
(p) 0
(K- (k-1)
(i- )2
E a.
where is the nonnegative fixed point of the following equation:
p 1 a0)
p(k 1).
ko,
Since ||Oul| + 1, the result (8) follows from Lemma B.1
We refer the supplementary D. for the proof of Lemma B.1
B.2 CALCULATING THE VARIANCE
Since the bags are non-overlapping we have SST Im- Therefore T S is projection matrix and can be written as S' S = UUT, with U E TR= an orthogonal matrix. Recall that the variance
is given by Var (6mm)) o² MS SI We use the next lemma characterize the asymptotic behavior of the variance.
Lemma B.2. Under the asymptotic regime of Asssupptin 2.3 for any vector R we have
MM
(p)
k
||||
Ux
where vs is given as the fixed point of the following system of equations (v, u):
1+a + pv(k-1) atn + p'o(k-1)
k, k.
((1+))
[I+u]=
(ptu)s
Proof of Lemma B.2 is given in the supplementary D.2
We next use the above lemma for each row of U separately (as the vector a) and add them together.
Using the fact that |U = m and m/ k, we get that |MUU [|3 (p) 1/v., which completes the variance calculation.
15

---

Published as a conference paper at ICLR 2024
B.3 PROOF OF LEMMA 4.2
We use the idea of (Dwork et al. 2014, Theorem 3.6) to prove this lemma. Given database D
(y), 12,...,, Vn), Algorithm| (we denote this mapping by A R Rm)) outputs m real numbers
(91, U2....... Dm) Given the database D, we define the map f : R - Rm by D + (ÿ1: V2.--- Mm ) which computes the mean of labels in each bag. Fix any pair of neighboring databases D, D' that differ in the label of single example. We have f (D') == Eaelmi If(D), f(D)al s
Af Cylog In this argument, we used Assumption 2.4 that assumes non-overlapping bags, and therefore, changing a certain Yi in D leads to a change in only one of Ya by at most Af. Let (2)()((2) and (2) denote the probability density function of A(D) and A(D'). We have
El5(D) Af
PA(D) PA(D))22
exp
II mE(m]
elf(D"), Ai
exp
(If(DD)) -Zal
If(D)a =al))
II exp aE/ma
Af
e)J(D"), - I(D)al
II exp
Af
aE/m]
<IIf(D) - 5(D'IlI)
exp
Af
< e
which completes the proof.
C PROOF OF THEOREM 4.3
Recall that in Algorithm | the individual responses are first truncated by C'Vlog n and then after the aggregate responses computed, Laplace noise is added them ensure label DP. We define is the event that no truncation happens, namely:
[lu15O viE(n))
(15)
Since ya ~ N(, ||0 + 0²), |10||| = 1, by using Gaussian tail bound along with union bounding we arrive at
P(E) 2 1 n exp (- 2(1 02)
C
logn) - n
(16)
with c 2(1004) > 0.
We next bound the risk of estimator O.n follows:
Riskx (0mm) @l Oul 0 [ + E|| 0011 X
(17)
For the first term, note that on the instance & (no truncation), the privatized aggregate responses are just the aggregate responses with an additive zero mean noise with variance 2C log n (ke)². So we can use the analysis the proof of Theorem 2.5 with the inflated noise variance. Let 0ut be the estimator using untruncated responses Algorithm We then have This gives us
1
E|[ Ome 001l21 XX]
EE Ont int
0oll [1)11
log
log
1
[|]
Out
00
0ll 0bll ((s)( X
log
log
1
Bias (t))) +
Var x (0
Ell 1. - 0 2 XX,
log n
log n
log n
(18)
16

---

Published as a conference paper at ICLR 2024
where the bias is given by (8 and variance is given by (9). where o² /k is replaced with the inflated variance o² //-++220 20 log / (ke)?. Since Biasx (fit) has finite limit, the first term above vanishes as n + cc. For the second term we have
20
Var x (0
log n
ke
since o²/ /log n + 0. For the third term, by Seuchy-Schwarn incquality we have
El| 0oll 001l21 10 X &
m intt El|
0oll | P(E").
(19)
Using the high probability bound on the minimum singular value of the Gaussian matrix X (Ver- shynin 2018 Theorem 4.6.1). we can show that Ell 0oll*|XX] is bounded in probability and
since P ((") I n " we conclude that the third term in 18) also vanishes as + oc, probability.
Combining these together we arrive at
Ell 0 001121 (8)
X]
(P)
2C
(20)
logn
ke Ux
Similar to (9) we can also show that
E Oin
00ll ((0) [X] (
log
which along with (20) and 17 implies that
1 Riskx (Oint)
(p) 20 1 ke V.
log
completing the proof.
D PROOF OF INTERMEDIATE LEMMAS
D.1 PROOF OF LEMMA B.1
Write X = [x1,...,,.. øa) with x; representing the i-th column. We then have |MAX|| =
Ed ||M We compute the asymptotic behavior of each of the summand separately. In- deed, by symmetry of the distributions of 2;, we will see that summands converge to the same limit.
Recall that M (X EX)-1 -1
1x
Consider the following optimization problem:
a arg min 7 1/2 1 Xa E-1/2 Ax
(21)
It is easy to that by the KKT condition, a; (X are interested in characterizing ||as|| in the asymptotic regime, described in Assumption 2.3
Az; MA Therefore,
We write a (a;, a... to separate its i-th entry form the rest. Likewise write X [x: to separate the i-th columns from the rest. We then have
min acRd
11/2 E Az2
min aER*
E 1/ + 122 X-s - BOowi-E--1. E-112Ax
min acRd d
E 1/2 1212X Xnn + (1, -V-1-E//A
1
min max aCR DER" d
EE-1- - + T E1/2 T ans -5111111
X
(22)
where in the last step used the identity max, (v - 12211//2) || 1| for any vector
17

---

Published as a conference paper at ICLR 2024
We next note that SS I since the bags are non-overlapping. Therefore write STS UU for an orthogonal matrix U E IR" 1g We then have
E = pl + -1- p)s = s UU + U A -=)
where U1 is an orthogonal matrix representing the orthogonal space to the column space of U.
We next decompose the vector vr the above optimization as e Uv U1tt t2 and therefore || = 1 11 ||
We introduce the change of variable û = / in optimization 22 Note that i = Uvi + 1pU. Continuing with (22) in terms of we have
min max acEd BER
2 (
E + 6J X
1 E 1/2011
(23)
2
To analyze the asymptotic behavior of the solution to the above minimax optimization, we use (CGMT) (Thrampoulidis et al., 2015 Theorem 3). which
the is power extension of the classical Gordon's s Gaussian min-max theorem Gordon (1988), under additional convexity assumptions. According to CGMT, the above optimization is equivalent to the following auxiliary optimization problem:
2 (a; ----E-AA A-a,)a, | 0 g + || ant 1IEE-122) 1/20
min max agRd BER" d
(24)
with g ((0, In) and (0, 1 independent Gaussian vectors. We next write the above optimization in terms of the components en and 22, noting that E A = U. follows:
2 U x + you - Jz, + ||amil U g you, llg)
min max
aeRd DIR" d
10
02 h ani // |10111
1
||
(25)
Define the shorthand
31 U 0; Im),
82 U_ 0 N(O, In-m);
91 = U 9 ~ N NO, Im),
92 U g NN, (0,In-m))
Then optimization 25 can be rewritten as
ag ERR d ( x1 + vplas 1)02 22 + a [1u 91 + ypo, 92)
min
max
||l| 12 12 Ta
a..
| 2
|12112)
(26)
We fix ||l || 31 and [22ll = Bg and first optimize over the directions of U1, V2 and then over the
norms Bn and 32. This brings us to
min max aeRd A1.2200 d
B1 (aala + ||awilll111 321l
1)x2 + |l VPgall
V B p3gh a.i
1
7
(27)
2
In order to optimize over ami we first fix its norm to 17 := ||ww|| || and optimize over its direction, and then optimize over 7, which results in:
min max 2200m $1.220
(11lar21 + ng1 B2llvp(aas - 1)22 + /Vpgall
1 83)
87 + m
(28)
18

---

Published as a conference paper at ICLR 2024
The next step in the CGMT framework is to compute the pointwise limit of the objective functions. Using the concentration Lipschitz functions
Gaussian vectors we have
1b
0
(af + (²)
(P) V (pla: 1)2 + pn²) :
IVpla; 1)22 7/ A92
Vd
where we used Assumption 2.3 by which n/d and m n/k.
3 1.
We also have
va |/|
We therefore arrive at the following deterministic optimization problem
max (9) (a + 11²) k
(olas - 1)2 pm () (1- 1
min
+ B2
020,0 B .220
1
1
89 + pB3
(29)
2
where we made the change of variables 23,
2 - B1 and 232/ Vd 82.
By writing the stationary conditions for the above optimization, and simplifying the resulting system of equations by solving for B1, $2, and substituting for them in the other two equations, arrive the following two equations for a and ry:
p R(l [1-aa)
ko.
p(k: 1)
+
ko R-1 (((--1
10
R (1-cc)2
As the final step, recall that by definition 7) = |lawill and therefore, ||a:||2 (2) a? + nZ. As it is independent of the index and therefore,
|MAX
M Max 1==
Σ
a a 17
This completes the proof.
D.2 PROOF LEMMA B.2
Recall that M (X EX TT. Consider the following optimization problem:
a arg aen d | Xa 1-1/2
(30)
The solution the above optimization problem has closed-form solution given by MUa. So we are interested in characterizing the norm of the optimal
(X EX)-1x Ua solution to the above optimization problem.
= UUa
Similar to the proof of Lemma B.1 we use the framework of CGMT to characterize ||a]]] in the asymptotic regime described in Assumption 2.3
Using the identity || = max,(uT x //2)2/2), we rewrite the above optimization as:
min a d
1 Xa -
CC--E-1/214 E-1/2Ual
min max DE
oo 1 xa x TTTE-1/U 1111
(31)
agRd
By using Convex-Gand Miniiian---ii-x----- Theorem (Thrampoulidis et al. 2015 optimization is equivalent to the following auxiliary optimization problem:
Mhnorex-Theorem
Theorem 3), the above
oER d [|az]|0] E
min max
2
u/ a v T E E--1/2aa 2
1 1|0111
(32)
19

---

Published as a conference paper at ICLR 2024
with g (V, I.) and h [N,0,)) independent Gaussian vectors.
We also recall that T S UU and so
E = pl + (1- p)s = UU + PULLI
with U1 Rax(n-m) denotes the orthogonal matrix, whose column space is orthogonal to the column space of U. We decompose v to its component in the column space of U and U1 as
v = UVV + v2,
||l| = |1 + +
Therefore, / Uvi + VPU1vp U2 and so the above optimization 32 can be written as
UIg + vl 12 a [|al|e]] UT g V
min max oER U2ER
1 1 2
|1221(3)
(33)
We next introduce the following change of variables:
g1 = U g ~ [0, Im),
= U ~ N(0, I I-
Rewriting the optimization in terms of 91 and g2 we get
2 d [|acell] + Vplla 1 92 + v //11 12 - 2
min aEE ER
max
|00211
(34)
We next do the maximization on ii and v2 by first fixing the norms to 31 := =|[=1| and B3 == |/02|
and maximize over the directions and then maximize over 31, B2. This gives
BP 32
min max (ailllaa g1 - all + 82vP|alllg: + / B + p33n T a QeR $2. d
(35)
For minimization over a, we first fix its norm to r7: = ||cx| and optimize over its direction, and then
min max 2 720 3 9o 20 d (illln all + 32 /2vllll - -n 37 + p83 ||||||
87 + 32
(36)
2
The next step in the CGMT framework is compute the pointwise limit of the objective function. By concentration of Lipschitz functions of Gaussian vectors we have
(p)
a
2 +
tb
19
all
172
k
||
(p)
1b
2
Vd
1
(p)
1.
where we used Assumption 2.3 by which n//d vh and Assumption 2.4 by which m n/k. Using these limits in (36). we arrive at the following deterministic optimization problem:
aa
1/2 +
+ B2VDn 16 1) k TL B +
87 + 8
min max B1
(37)
120 8.0
d
where we applied the change of variables 28,
/d + 3, and 2/2/ + 32.
In order to find the optimal solution solve the stationary conditions. By setting derivative with respect to to zero we obtain
F
(1-111 m pe p 11-11-11 1) V + +83 =
(38)
2
2
20

---

Published as a conference paper at ICLR 2024
In addition by setting the derivative with respect 31 and B2 zero, obtain
2
15
+
1p
+ 11,,
k
B1
+ p33
(39)
pb
pm
+ 1 1132..
K
B1 + p33
By substituting for 31 and 32 from
39
into 38
we get
pmp 1 1
0,
(40)
7) +
pn + c
where c= VBF + p.3.
Also by substituting for 31 and Bg from
39
into the definition == vBJ + p3g. we have
||a
p - 12)
(41)
(1) c)²
(pn c)²
We next make the change of variable: yu, and rewriting equations 440 and 41 as follows:
pib(k-1) p+u
k
T+u
klla 12
(20(-11)
k
(1+u)a
(pta)²
Defining
k||a]]
get the system of equations given in the lemma statement.
wdy
As the final step, recall that discussed at the beginning of the proof, a. MUa. Therefore,
n
MUa
n
(p)
72
a
Ia
|
which completes the proof.
21


Reviews:
[{"review_id": "0olFxvOqoK", "reviewer": "Reviewer_Z7mk", "summary": "This paper addresses the problem of learning a model from a dataset partitioned into non-overlapping 'bags' of equal size, given the average value of the response variable in each bag. The difference with respect to usual regression analysis is that the individual responses are not provided, and so we cannot calculate the usual loss function. This calls for the definition of a modified loss function that depends only on the aggregate response in each bag.\n\nThe present paper analyses two such modified loss functions : L_bag, which measures the distance between the aggregate responses and the aggregates of model predictions ; and L_ins, which measures the distance between the aggregate responses and the individual model predictions.\n\nWhile L_bag gives rise to an unbiased estimator, the estimator corresponding to L_ins has a lower variance, at the cost of introducing a bias. The author(s) interpret the difference L_ins - L_bag as a sort of regularization term.\n\nThe paper also studies a loss function L_int, depending on a parameter rho, that interpolates linearly between L_bag and L_ins. (This corresponds to tuning the strength of the regularization.) The choice of rho involves a trade-off between the bias and variance of the resulting estimator, and one can make this choice in order to minimize the 'prediction risk' of the estimator.\n\nThe paper illustrates the above ideas in the case of linear models, with a quadratic loss function. In a rather specific asymptotic regime, with the training data drawn from standard normal distributions and then assigned uniformly at random to the bags, the paper computes several quantities of interest, such as the bias and variance of the estimator corresponding to L_int (and, by specialization, of that corresponding to L_bag and L_int). The results support the qualitative conclusions mentioned above.\n\nThe paper also contains certain numerical experiments, verifying the theoretical results in the asymptotic regime mentioned above, and exploring in the case of the Boston Housing dataset the optimal value of rho as a function of bag size.\n\nFinally, the paper also shows that truncating and adding a Laplace noise to the original aggregate responses makes the dataset epsilon-label Differentially Private. The resulting estimator is also Differentially Private, and the paper studies the optimal bag size (in the aforementioned asymptotic regime) as a function of the optimal regularization parameter rho.", "questions": "1. Are there explicit connections/insights to be gleaned from the results in the paper and the Google/Apple approaches for aggregated-feedback?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "A. Clarity\n     1. The content is well organized. The introduction succinctly motivates the problems and summarizes the results.\n     2. The intuitions are made explicit and are transparently described. This made the review process painless.\n     3. The main text is clutter free and the proofs of all the technical claims are included in the supplementary material. The submission, is as a result, largely self contained and has no technical gaps.\n     4. The literature review is thorough and the authors have gone the extra mile organizing the ideas and summarizing the current state of a rapidly evolving niche in ML research.\n\nB. Significance, Quality\n     1. The subject is topical since Privacy preserving ML is a burning issue and an active area of current research.\n     2. The results shed new light on the interplay between instance-level and bag-level loss. It is interesting to see that the interpolate improves generalization in a real world dataset. \n     3. The qualitative conclusions derived in the asymptotic regime are clarifying and may be useful in more \"hairy\" real world datasets.\n\nC. Originality\n     1. Mixed loss function: The idea of interpolating between the loss functions is interesting and the idea that this could result in better generalization for aggregates-based learning appears to be novel.\n     2. The authors go beyond showing empirical results and derive closed form expressions and provide compelling interpretations for them.", "weaknesses": "1. This is a minor comment on terminology: regularizers in the ML context, to the best of this reviewer's knowledge, only depend on model parameters and not on the data (which includes the feature vectors). Shrinkage and variance-reduction are related but not identical, and regularization in ML refers to the former. If indeed this term is used more broadly it may be helpful to include a few clarifying sentences and/or references. \n\n2. The theoretical results are proved under the following\n      a. Random Bags\n      b. Equal Sized Bags\n      c. Non-Overlapping Bags\n\nThe introduction cites the Google(Privacy Sandbox) and Apple(SKAd) APIs as motivations for the problem but the assumptions (a),(b),(c) do not hold in this regimes. In fact, a critical feature of both (a) Google's Private Aggregation API and (b) Apple's SKAd Network is that the aggregation keys are configurable (eg. aggregate behavior of traffic from California, visiting sports content at a certain time of day) ie the bags are specified by the consumer of the API, not by random aggregations. This enables ML algorithms to effectively use these aggregates for prediction.\n\nThis is an essential part of the problem. For example, here is a quasi-technical [report published by Google](https://github.com/google/ads-privacy/blob/master/Combining%20the%20Event%20and%20Aggregate%20Summary%20Reports%20from%20the%20Privacy%20Sandbox%20Attribution%20Reporting%20API.pdf)\n\nIf there is indeed a connection/insight in the paper that this reviewer has missed, please respond to the question below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GQtFxAHgma", "reviewer": "Reviewer_LbHA", "summary": "This paper investigates the challenge of learning with restricted access to labels. Specifically, the authors explore two categories: Instance Level and Bag Level Losses. The proposed algorithm begins by partitioning data points into k non-overlapping bags, each containing m examples. Subsequently, the authors introduce two sets of loss functions: bag-level (as seen in Eq. 1) and instance-level (as seen in Eq. 2).\n\nThe primary contributions of this paper are as follows:\n\n1- Demonstrating that for a wide range of loss functions, a regularized bag-level loss can effectively serve as a surrogate for instance-level losses.\n\n2- In the context of well-specified linear regression, providing a precise characterization of the tradeoff between bias and variance.\n\n3- Introducing a label-DP variant of their algorithm tailored to bag-level losses.", "questions": "1- What are the use-cases of instance-level loss and bag-level loss? To me, instance-level seems more intuitive and I want to know about the scenarios in which it is preferable to use bag-level loss.\n\n2- What is the significance of non-overlapping bags? Is it because of the analysis?\n\n3- For DP variants, the authors propose first forming the bag-level loss and then applying Laplace mechanism to the aggregated labels. Is that the best approach? What is the comparison of this method with the prior work on label-DP?\n\n4- Randomness in placing the samples in bags may help in privacy amplification.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think the paper is well-written and the theoretical results are presented with lots of intuitions. I think the main strength of the paper is the exact characterization of the bias and variance tradeoff. This characterization let them compare two family of losses.", "weaknesses": "I think the motivation behind the definition of instance-level and bag-level losses is not clear. Another weakness is that the authors do not compare their results with the prior results on label DP. In this paper the authors use bag-level loss and then consider the noisy labels. Is that the best approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FnS1yyFCwz", "reviewer": "Reviewer_wg1T", "summary": "This paper studies learning from aggregated responses with loss functions from both an instance level and a bag level with motivation from keeping individual privacy. It investigated the tradeoff between risk and privacy by inserting a multiplicative parameter for the regularization term $\\rho$ such that the instance-level loss and bag-level loss are well balanced. It also investigated different parameters such as signal-to-noise ratio, bag size, and overparameterization, and their effects on the convergence of the bias and variance of the model, and derived the optimal choice of parameter $\\rho$ with evidence from numerical experiments.", "questions": "Can you explain a bit more on the fixed point and the solution of the equation systems in Theorem 2.5?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper investigates the trade-off between bias and variance by taking into account various factors that might influence the model performance, which is considered thorough.", "weaknesses": "The presentation can be improved. For example, some high-level ideas on the tradeoff could be included earlier in the paper (in more detail) instead of introducing them in the latter parts of the paper which makes it hard to grasp the contribution at the beginning. More explanation on Theorem 2.5 should be discussed. For example, the intuition of the actual meaning of the fixed point or the solution of the equation systems; what quantities the bias and the variance are converging to.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aEiPbinRoL", "reviewer": "Reviewer_D7UY", "summary": "This paper studied the problem of learning from average response.\nThe author compared two loss functions (error of average output, average as instance label) theoretically and analyzed the bias and variance for linear models.\nThen, the author proposed a method for differential privacy based on the theoretical result.", "questions": "- Why non-overlapping?\n- \"The bag-level loss does not have a unique minimizer\": is this proven?\n- Why should we reduce the variance? It seems that the regularization could lead to an over-smoothed solution.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper is well-written and easy to follow. The mathematical notation is clear.\n- The author did a good job discussing real-world examples and related works.\n- The analyses are sound and reasonable.\n- The private aggregate learning method is a solid contribution.", "weaknesses": "- Most analyses are restricted to linear models. Thus, the range of applications may be limited. Even for tabular data, gradient boosting machines may perform better than linear models. There's a gap between theory and practice: for the Boston housing dataset, the author used an MLP instead.\n- The experiment is limited to one dataset. The labels generated in this way may not be a good proxy of real-world aggregate label problems.\n- A minor issue: the title \"learning from aggregate responses\" may be imprecise since here, the author only considered the average. There are other types of aggregate information, such as max, median, and rank.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "29aC1vNKhm", "reviewer": "Reviewer_2uPt", "summary": "The paper studies the relationship between instance-loss and bag-loss in the setting of aggregate label. In practice, the latter would provide stronger privacy protection in the model training process. The authors showed that instance loss can be viewed as having an extra regularization term similar to the within-cluster square loss from k-means. Based on this, a interpolative loss is proposed between these two as well as the bias-variance tradeoff on this factor.", "questions": "As aforementioned, I would like the authors to provide the derivation of the theoretical results in the supplementary, and address the generalizability of the results if one or few assumptions do not hold in the paper.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is clearly written and provides a very intuitive view on the connection between the bag-loss and individual-loss.\n- The authors derived theoretical results on the SNR which has practical implications on selecting optimal bag size.", "weaknesses": "- The authors did not include the proof of the theorems, which I think is essential given the paper is largely centered around Theorem 2.5. In particular, (please let me know if I'm wrong), equation (8) simplifies to $2\\alpha_{\\ast}-1$ when k=1 which is not always 0 based on the fixed point assumption.\n- There is a little incoherence between the assumption and application. The authors focused on very practical applications with DP and aggregate learning, but it's rare in those cases for the proportional regime to hold which appears to be essential to the analysis. More commonly we see d = o(n), and I also assume k could not be fixed as d grows to satisfy k-anon.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)