Thank you for taking the time to read and review our paper!

Response to 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.

We would like to clarify that we did provide detailed proofs for all the theorems in the supplementary material. Specifically, the proof of Theorem 2.5 can be found in Appendix B. Due to space constraints for the main manuscript, the proofs are deferred to the supplementary. It is already available to the reviewers.

In particular, (please let me know if I'm wrong), equation (8) simplifies to $2\alpha_*-1$ when $k=1$ which is not always 0 based on the fixed point assumption.

Note that equation (8) is under the assumption $k>1$ and $\rho>0$. (So you cannot set $k=1$ in it and get a valid result). We have been specific about this: The first bullet reads: “Bias: For $k>1$ and $\rho> 0$ ….”. And then we add a sentence stating that under $k=1$ or $\rho=0$, the bias is zero. In other words, these two statements are the complement of each other and you should not expect to get the second as a special case of (8).

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.

The case of $d = o(n)$ is the classical setting in statistics, while nowadays with the ability of collecting rich granular information on individuals, we are well into the proportional regime. For the practical applications discussed in the paper, there is often abundant information about users, many of which are categorical and would add even more dimension once converted into numerical features. Indeed there is a very active and broad area, called high-dimensional statistics, developed in the past three decades to discuss scenarios where $d$ exceeds sample size $n$. We refer to (Donoho 2000) for a discussion of the relevance of the high-dimensional regime.

Regarding the comment on $k$, we would like to recall that the setting of the paper is motivated by applications where the responses/labels contain private information, but the features vectors are not private. That’s why the aggregation is only done on the responses. That said, k-anonymity does not have anything to do with features dimension ($d$). It simply means that for each user, its aggregate response is shared with at least $k-1$ other users (since the bags are of size $k$). If you have further questions or if additional clarification is needed, please let us know and we will be happy to address.

*Donoho (2000), High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality

Response to Question:

Please see our response to weaknesses. The proofs are already given in the supplementary which is available to the reviewers. In particular, the proof of Theorem 2.5 can be found in Appendix B.

Thank you for taking the time to read our paper and for your thoughtful comments.

Response to 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.

While it's true that our theoretical analyses primarily focus on linear models, by providing a precise theory for this case we develop non-trivial insights, which as we see in the experiment carry over to more complex nonlinear setups.

In particular, we acknowledge that real-world data often exhibits complex patterns that may be better captured by non-linear models such as gradient boosting machines or multi-layer perceptrons (MLPs). To bridge the gap between theory and practice, we conducted experiments on the Boston housing dataset using an MLP, deviating from the linear models typically analyzed in the theoretical context.

Interestingly, our experimental results with the MLP align with the predictions of our theoretical framework. Specifically, our theory suggests that the choice between bag-level and instance-level loss depends on the signal-to-noise ratio (SNR), and our experiment on the Boston housing dataset validates this insight. When the SNR is high (indicating smaller bags with higher SNR), bag-level loss outperforms; conversely, when the SNR is low, instance-level loss is more effective. In the intermediate phase, our results reveal a sweet spot, confirming the practical relevance of our theoretical findings.

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.

In the setup discussed in the paper, the aggregate labels are generated by averaging the individual labels of all examples within a bag. It's worth noting that this method of label aggregation through averaging is a well-established and widely used practice. This technique finds application in various domains, from traditional group testing methodologies to contemporary privacy-preserving frameworks, such as the Private Aggregation API of Chrome Privacy Sandbox and the SKAdNetwork API from Apple.

If there's a specific concern or aspect of label generation that we may not have adequately addressed in our work, we would greatly appreciate additional details or clarification. It's possible that there might be a misunderstanding, and we are keen to ensure that we address your question comprehensively.

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.

While we acknowledge that there are various ways to aggregate information, such as using max, median, or rank, in the literature the aggregation often refers to the average or a weighted average. This method of label aggregation through averaging is a widely adopted practice, evident in traditional group testing methodologies, as well as in contemporary privacy-preserving frameworks like the Private Aggregation API of Chrome Privacy Sandbox and the SKAdNetwork API from Apple.

Response to Questions

Why non-overlapping?

The significance of employing non-overlapping bags is beyond considerations for our analysis; it is also crucial for maintaining privacy protection. Allowing overlapping bags, where a data example can be included in multiple bags, introduces the risk of inferring individual labels. To illustrate this potential privacy breach, consider an extreme scenario where there are more bags than the number of data examples. In such cases, an adversary could exploit the overlap to infer individual labels by solving a linear equation. Therefore, the choice of non-overlapping bags is not only for our analytical considerations but is also a deliberate measure to safeguard against potential privacy vulnerabilities. We appreciate your attention to this aspect of our methodology.

"The bag-level loss does not have a unique minimizer": is this proven?

To illustrate this point, let's consider a simple example. Suppose we have a bag consisting of two examples and the aggregate response for this bag is 0.5. In this case, we can select any one of the two examples and predict its response y, and the other as 1-y. As a result, the bag-level loss on this bag becomes zero, achieving the minimum. Therefore, it does not admit a unique minimizer. We hope this example clarifies the observation that the bag-level loss does not admit a unique minimizer in general.

Thank you for taking the time to read our paper and for your thoughtful comments.

Response to 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.

Following your comment, we plan to add this explanation early on in the paper to better describe the contributions. “Note that bag-level and instance-level are approaches for training models using aggregated responses and once the bag configurations are given to the learner, she can try either loss to train her model. The high-level intuition we establish in this paper (through rigorous quantitative statements) is that using bag-level loss results in models with lower bias but higher variance compared to models that are trained by minimizing the instance-level loss. So in cases where there is a lot of heterogeneity in the responses, instance-level would work better. In contrast, for use cases with more homogenous responses, the bag-level would be better because lowering the bias becomes more effective (the variance is low).”

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.

Note that $u$ is a dummy variable and the first equation is a quadratic equation in $u$, which has one positive solution. Once it is solved in $u$, it can be plugged into the second equation which is linear in $v$, to solve for $v$. As we see from the result $v$ is the variable that shows up in variance formula (equation 9). We could have just written $v$ explicitly by solving for $u$ and $v$ in closed form, but thought that writing it this way would be cleaner.

Response to Question:

Can you explain a bit more on the fixed point and the solution of the equation systems in Theorem 2.5?

Please see our response to the weaknesses as w answer this question there. If you have any other question or any further clarification is needed we are more than happy to respond.

Thank you very much for addressing the concerns. It would be nice to incorporate the discussion in the revision. I would like to raise the score to 6.

Thank you for taking the time to read our paper and for your thoughtful comments.

Response to Weaknesses

I think the motivation behind the definition of instance-level and bag-level losses is not clear.

Indeed having a clear understanding of these concepts is essential for comprehending our work. Note that in our setup, the learner has access to individual features vectors $x_i$, while is only given access to the aggregate responses. The instance-level and bag-level losses are two approaches often used in this area to assess the loss of a model. In the instance-level you treat the average response in a bag as a proxy for the ungiven individual responses in that bag and measure the loss between your model predictions $f(x_i)$ and the average response. Therefore, for each instance $x_i$ you still have a term in the loss function. In the bag-level loss, for each bag you measure how well your average predictions align with the given average responses. So for each bag you get a term in the loss function, but not for each instance.
We hope that this explanation has been helpful. Please let us know if you have any further questions.

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?

To clarify, we do compare our results with the label DP procedure. Note that the pure label DP procedure corresponds to the choice of $k=1$, which results in clusters of size one and essentially no aggregation. In particular, in Figure 2, we discuss that if $\rho$ is small (recall that $\rho=0$ corresponds to the bag-level loss), then $k=1$ is optimal, which means that pure label DP yields better model risk under a fixed privacy budget than aggregation + DP. On the other hand, for large values of $\rho$ (recall that $\rho=1$ corresponds to the instance-level loss), larger $k$ is better, so adding noise to the aggregated responses is better than just label DP. Hence, in summary, in our experiments, we compare with pure label DP ($k=1$) and also different choices of $\rho$ (which cover both the bag-level and instance-level loss as well as any combination of them).

Response to 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.

Note that bag-level and instance-level are approaches for training models using aggregated responses and once the bag configurations are given to the learner, she can try either loss to train her model. In our response to the weaknesses (above), we provided further intuition about the definition of these losses. The high-level intuition we establish in this paper (through rigorous quantitative statements) is that using bag-level loss results in models with lower bias but higher variance compared to models that are trained by minimizing the instance-level loss. So in cases where there is a lot of heterogeneity in the responses, instance-level would work better. In contrast, for use cases with more homogenous responses, the bag-level would be better because lowering the bias becomes more effective (the variance is low). For the case of linear regression, we explicitly characterize regimes where one approach is better than the other (see Lemma 3.2). In Figure 3, we also plot the risk (derived from our precise theoretical characterization). Note that the leftmost point ($\rho=0$) corresponds to the bag-level loss and the rightmost point ($\rho =1$) corresponds to the instance-level loss. As we see depending on the values of signal-to-noise ratio (SNR), cluster size (k) and overparameterization ($\psi$), one approach can outweigh the other.

2- What is the significance of non-overlapping bags? Is it because of the analysis?

The significance of employing non-overlapping bags is beyond considerations for our analysis; it is also crucial for maintaining privacy protection. Allowing overlapping bags, where a data example can be included in multiple bags, introduces the risk of inferring individual labels. To illustrate this potential privacy breach, consider an extreme scenario where there are more bags than the number of data examples. In such cases, an adversary could exploit the overlap to infer individual labels by solving a linear equation. Therefore, the choice of non-overlapping bags is not only for our analytical considerations but is also a deliberate measure to safeguard against potential privacy vulnerabilities. We appreciate your attention to this aspect of our methodology.

Thank you for taking the time to read our paper and for your thoughtful comments.

Response to Weaknesses:

1.This is a minor comment on terminology: regularizers in the ML context ....

Yes, we agree that regularization is often used to refer to techniques that only depend on model parameters. However, there is indeed a growing body of work on data-dependent regularization. Following your comments, we will add the following clarification to the paper: "In addition to traditional regularization techniques that only depend on model parameters, there is also a growing body of 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." We will also add references to the following papers, which provide examples of data-dependent regularization techniques:

• Shivaswamy, P. K., & Jebara, T. (2010). Maximum Relative Margin and Data-Dependent Regularization. Journal of Machine Learning Research, 11(2).
• Zhao, H., Tsai, Y. H. H., Salakhutdinov, R. R., & Gordon, G. J. (2019). Learning neural networks with adaptive regularization. Advances in Neural Information Processing Systems, 32.
• Mou, W., Zhou, Y., Gao, J., & Wang, L. (2018, July). Dropout training, data-dependent regularization, and generalization bounds. In International conference on machine learning (pp. 3645-3653). PMLR. We hope that these additions will clarify the distinction between traditional regularization and data-dependent regularization.

2.The theoretical results are proved under the following a. Random Bags b. Equal Sized Bags c. Non-Overlapping Bags. The 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 ....

Thank you for your insightful comment. The Google Privacy Sandbox and Apple APIs are discussed in the introduction mainly to motivate the general problem of learning from aggregated data, why it is of interest in practice and the privacy protections benefits of it. We acknowledge that the configurability of aggregation keys introduces a level of specificity that may not align perfectly with our assumption of random aggregations. However, we contend that even in scenarios where bags are specified based on certain criteria (e.g., location, content, time of day), there remains an element of randomness in the aggregation process, especially when multiple users meet the specified conditions. In this sense, our theoretical framework, while idealized, can still serve as a valuable baseline for practical considerations.

Furthermore, note that constructing bags by aggregating records with specific attributes in general outperforms random bags (see Chen et al. (2023)). Therefore, our study of random bags provides a conservative estimate of performance in practical settings, acting as a benchmark for the worst-case scenario. Additionally, it's noteworthy that random bags are commonly employed in the literature on learning from aggregate labels, further emphasizing their relevance in theoretical analyses (e.g., Busa-Fekete et al. (2023), Yu et al. (2013), Quadrianto et al. (2008)).

Response to Questions

Are there explicit connections/insights to be gleaned from the results in the paper and the Google/Apple approaches for aggregated-feedback?

Our paper aims to shed light on the trade-offs between instance-level and bag-level losses in aggregated feedback settings. While we understand that the specifics of the Google Privacy Sandbox and Apple SKAd APIs may not align directly with our theoretical framework, our findings suggest a broader principle — the potential regularization effect of instance-level loss leading to improved generalization performance. This principle may inform the design of algorithms for APIs with configurable aggregation keys, guiding the search for an optimal balance between instance-level and bag-level losses.

In conclusion, we value your input and recognize the need for future work that bridges the gap between theoretical models and real-world applications. Our ongoing research will focus on extending our theoretical framework to incorporate more realistic assumptions, specifically addressing the nuances of APIs like the Google Privacy Sandbox and Apple SKAd. We are committed to exploring how our theoretical insights can be practically applied in these settings and welcome further discussion on this important intersection of theory and application.