figuret

# Learning from Aggregate responses: Instance Level versus Bag Level Loss
Functions

Adel Javanmard111Data Sciences and Operations Department, University of
Southern California 222Google Research , Lin Chen††footnotemark: , Vahab
Mirrokni††footnotemark: , Ashwinkumar Badanidiyuru††footnotemark: , Gang
Fu††footnotemark:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Due to the rise of privacy concerns, in many practical applications the
training data is aggregated before being shared with the learner, in order to
protect 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: bag-level loss and the instance-level loss.
In the former, the model is learnt by minimizing a loss between 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 lets us compare the two approaches with
respect to bias and variance of the resulting estimators, and introduce a
novel interpolating estimator which 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 features dimension. Our analysis allows us to
theoretically understand the effect of different factors, such as bag size on
the model prediction risk. In addition, we propose a mechanism for
differentially private learning from aggregate responses and derive the
optimal bag size in terms of prediction risk-privacy trade-off. We also carry
out thorough experiments to corroborate our theory and show the efficacy of
the interpolating estimator.

##  1 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 that are
assigned to groups of data points rather than individual data points (Criteo
Privacy Preserving ML Competition, 2021). Since even the pre-machine learning
age, aggregate labels have been commonly used in group testing, a method of
testing 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 as 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 to 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 Developer Documentation, 2023). SKAdNetwork provides
advertisers with insights into the effectiveness of their ad campaigns without
compromising the privacy of their users. This is achieved by using aggregate
labels to represent groups of users who have interacted with an ad. For
example, an advertiser might see a report that tells them 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-
label pairs from users, but it protects their privacy by providing apps and
services with bags of instances that are labeled in an aggregated way. The
aggregate label can be further perturbed to ensure differential privacy, which
is a mathematical guarantee that the data cannot be used to identify or re-
identify individuals.

To formally describe the setup, consider a dataset consisting of $n$ samples
$({\bm{x}}_{i},y_{i})$, for $i\in[n]$, with ${\bm{x}}_{i}\in{\mathbb{R}}^{d}$
the features vector and $y\in{\mathbb{R}}$ the response variable. Motivated by
applications where the response variables $y_{i}$ carry private information,
instead of sharing individual responses with the learner, only aggregate
responses are shared in the following way. A set of $m$ non-overlapping bags
$B_{a}\subseteq[n]$, for $a\in[m]$, are formed, each of size $k$ and for each
bag the average response $\bar{y}_{a}=(\sum_{i\in B_{a}}y_{i})/k$, along with
the individual features vectors ${\bm{x}}_{i}$ are shared with the learner.

There are two common choices for learning from aggregated data:

  * •

Bag-level loss: The model is learnt by minimizing a loss function which
measures the distance between aggregate responses and the aggregate model
predictions. Namely,
$\widehat{\bm{\theta}}=\arg\min_{\bm{\theta}}\mathcal{L}_{\textnormal{bag}}(\bm{\theta})$
with

$\displaystyle\mathcal{L}_{\textnormal{bag}}(\bm{\theta})=\frac{1}{m}\sum_{a=1}^{m}\ell\Big{(}\bar{y}_{a},\frac{1}{k}\sum_{i\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}\,,$ (1)

where $\ell(\cdot,\cdot):{\mathbb{R}}\times{\mathbb{R}}\to{\mathbb{R}}_{\geq
0}$, and $f_{\bm{\theta}}$ is a family of models parameterized by
$\bm{\theta}$.

  * •

Instance-level loss: The model is learnt by minimizing the loss between the
aggregate responses and individual model predictions. Namely,
$\widehat{\bm{\theta}}=\arg\min_{\bm{\theta}}\mathcal{L}_{\textnormal{ins}}$
with

$\displaystyle\mathcal{L}_{\textnormal{ins}}(\bm{\theta}):=\frac{1}{mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}\ell(\bar{y}_{a},f_{\bm{\theta}}({\bm{x}}_{i}))\,.$ (2)

An 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 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 on the performance of models learnt by each
approach, as measured in terms of model generalization error. One of our
contributions in this paper is to establish a connection between the two
losses and shed light on when one outperforms the other in terms of model
generalization. We build a strong intuitive understanding through precise
quantitative statements. The key observation is that employing a bag-level
loss leads to models with reduced bias but increased variance, as opposed 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 the bias.

###  1.1 Summary of contributions and organization of the paper

Our contributions are summarized as follows:

  1. $(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 features dimension ($d$). Depending on
the interplay between the bias and the variance, one loss may outweigh the
other and result in a model with better generalization. Motivated by this
observation, we propose a new estimator which includes a tuning parameter
$\rho\in[0,1]$ to control the strength of the regularization, and hence the
bias-variance trade-off. The case of $\rho=0$ corresponds to the bag-level
loss, and the case of $\rho=1$ corresponds to the instance-level loss.
However, by optimally tuning $\rho$, we can get models which outperform both
of these cases.

  2. $(ii)$

We next focus on the so-called ‘proportional regime’ where the sample size
$(n)$ and the features dimension $(d)$ are of the same order, i.e.,
$n/d\to\psi$, for some arbitrary bounded constant $\psi\in(0,\infty)$, as
$n\to\infty$. This asymptotic regime has attracted a significant interest in
recent years due to its relevance in practice, where the classical population
regime ($n/d\to\infty$) fails in capturing the behavior of overparametrized
machine learning models (see e.g Hastie et al. (2022); Javanmard et al.
(2020); Hassani & Javanmard (2022); Mei & Montanari (2022)). In Section 2.2,
we 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 quantities of interest, such
as bags size $k$, overparametrization, signal-to-noise ratio of the data, and
the regularization parameter $\rho$ 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 $\rho$, described in
the previous item.

  3. $(iii)$

In Section 4 we propose a 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 $\varepsilon$-(label) differential
privacy. For a given privacy loss $\varepsilon$, our theory in Section 2.2
allows us to derive the optimal size of the bags which results in the best
model generalization. Interestingly, the singleton bags is not always the
optimal choice, which implies that applying Laplace mechanism to aggregate
data gives a better privacy-model generalization trade-off, compared to
directly applying the Laplace mechanism to individual responses.

###  1.2 Related work

There is a 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, 2016; Chen et al., 2017; Lu et al., 2019; Chen et
al., 2023). In what follows, we categorize previous work into bag-level,
instance-level and other methods.

Bag-level methods. Rueping (2010) proposed a large-margin support vector
regression (SVR) method for learning with label proportions (LLP). The
proposed approach models the mean of each bag as a “super-instance” with a
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 bag-level loss function. Yu et al. (2014) also derived a VC-
dimension-based uniform convergence bound for the gap between the empirical
and population bag-level loss functions. Ardehaly & Culotta (2017) applied the
aggregated cross-entropy loss to deep learning and classification problems.

Instance-level methods. Yu et al. (2013) 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. Dulac-Arnold 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 a 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 an example are
conditionally independent 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 foundational
questions about the computational complexity of LLP and its relationship to
PAC learning. Scott & Zhang (2020) solves the LLP problem through reduction to
mutual contamination models (MCMs). Saket (2021) investigated the learnability
of linear threshold functions (LTFs) from label proportions. Saket et al.
(2022) proposed a method for combining bag distributions to improve learning
from label proportions.

##  2 Main results

###  2.1 Intuition: instance-level loss acts as a regularized bag-level loss

In this work we establish a connection between bag-level and instance-level
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 an
extension to general convex losses.

######  Lemma 2.1.

Consider the quadratic loss $\ell(x,y)=(x-y)^{2}$. For the bag-level loss (1)
and the instance-level loss (2) we have

$\mathcal{L}_{\textnormal{ins}}(\bm{\theta})=\mathcal{L}_{\textnormal{bag}}(\bm{\theta})+{\mathcal{R}}(\bm{\theta})\,,$

where the regularization term ${\mathcal{R}}(\bm{\theta})$ is given by

$\displaystyle{\mathcal{R}}(\bm{\theta}):=\frac{1}{k}\sum_{a=1}^{m}\sum_{i,j\in
B_{a}}(f_{\bm{\theta}}({\bm{x}}_{i})-f_{\bm{\theta}}({\bm{x}}_{j}))^{2}\,.$
(3)

Note that the regularization term ${\mathcal{R}}(\bm{\theta})$ 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 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 (Shivaswamy & Jebara, 2010; Zhao et al., 2019; Mou et al.,
2018). In addition, ${\mathcal{R}}(\bm{\theta})$ 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
${\mathcal{R}}(\bm{\theta})$. 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 $\mathcal{L}_{{\rm
int}}(\bm{\theta})$ which keeps the same form of the regularization but
includes a tuning parameter to control the strength of the regularization,
namely

$\displaystyle\mathcal{L}_{{\rm
int}}(\bm{\theta}):=\mathcal{L}_{\textnormal{bag}}(\bm{\theta})+\rho{\mathcal{R}}(\bm{\theta}),\quad\rho\in[0,1]\,.$
(4)

In practice, the optimal value of $\rho$ can be set via cross-validation to
obtain the best model performance. In the next section, we provide a theory
for linear models which also allows us to analytically derive the optimal
choice of $\rho$.

We conclude this section by extending lemma 2.1 to other loss functions.

######  Lemma 2.2.

Consider the loss function
$\ell:{\mathbb{R}}\times{\mathbb{R}}\to{\mathbb{R}}_{\geq 0}$ with continuous
second derivative in the second argument. Also suppose that
$|\frac{\partial^{2}}{\partial b^{2}}\ell(a,b)|\leq C$ for a constant $C$. We
then have the following relation between the bag-level loss (1) and instance-
level loss (2):

$\displaystyle\mathcal{L}_{\textnormal{ins}}(\bm{\theta})\leq\mathcal{L}_{\textnormal{bag}}(\bm{\theta})+C{\mathcal{R}}(\bm{\theta}),$
(5)

where the regularization ${\mathcal{R}}(\bm{\theta})$ is given by (3). In
addition, if $\ell(\cdot,\cdot)$ is convex in the second argument we have
$\mathcal{L}_{\textnormal{bag}}(\bm{\theta})\leq\mathcal{L}_{\textnormal{ins}}(\bm{\theta})$
for any model $\bm{\theta}$.

We refer to the supplementary for the proof of Lemmas 2.1 and 2.2.

###  2.2 Linear models: A precise theory

Consider a dataset of $n$ i.i.d pairs $({\bm{x}}_{i},y_{i})$, for $i\in[n]$,
with ${\bm{x}}_{i}\in{\mathbb{R}}^{d}$ a feature vector and
$y_{i}\in{\mathbb{R}}$ a response variable. We assume the following linear
model for the responses:

$y_{i}={\bm{x}}_{i}^{T}\bm{\theta}_{0}+w_{i},$

where $w_{i}$ are i.i.d noise with $\mathbb{E}(w_{i})=0$ and
$\mathrm{Var}(w_{i})=\sigma^{2}$. We collect the responses into a vector
${\bm{y}}\in{\mathbb{R}}^{n}$ and the features in a matrix
${\bm{X}}\in{\mathbb{R}}^{n\times d}$ (with rows
${\bm{x}}_{i}\in{\mathbb{R}}^{d}$).

We consider a setting where the features are i.i.d Gaussian vectors
${\bm{x}}_{i}\sim N(0,{\bm{I}}_{d})$. Consider a model $\bm{\theta}$, trained
on the data ${\bm{X}},{\bm{y}}$ and a test point ${\bm{x}}_{\rm test}\sim
N(0,{\bm{I}}_{d})$, independent of the training data ${\bm{X}},{\bm{y}}$. The
prediction risk of $\bm{\theta}$ is defined by

${\sf{Risk}}_{{\bm{X}}}(\bm{\theta})=\mathbb{E}[({\bm{x}}_{\rm
test}^{T}\bm{\theta}-{\bm{x}}_{\rm
test}^{T}\bm{\theta}_{0})^{2}|{\bm{X}}]=\mathbb{E}[\|\bm{\theta}-\bm{\theta}_{0}\|^{2}|{\bm{X}}]\,.$

Note that our definition of the risk is conditional on ${\bm{X}}$ and is made
explicit in our notation ${\sf{Risk}}_{{\bm{X}}}$. In addition, the bias-
variance decomposition of the risk is given by

$\displaystyle{\sf{Risk}}_{{\bm{X}}}(\bm{\theta})$
$\displaystyle=\operatorname{Bias}(\bm{\theta})+\operatorname{Var}(\bm{\theta}),$
(6) $\displaystyle\operatorname{Bias}(\bm{\theta})$
$\displaystyle=\|\bm{\theta}_{0}-\mathbb{E}[\bm{\theta}|{\bm{X}}]\|^{2},\quad\operatorname{Var}(\bm{\theta})=\operatorname{tr}({\rm
Cov}(\bm{\theta}|X))\,.$

Recall our interpolating loss given by (4). Specializing to linear model
$f_{\bm{\theta}}({\bm{x}})={\bm{x}}^{T}\bm{\theta}$ and quadratic loss, we
arrive at

$\displaystyle\mathcal{L}_{{\rm int}}(\bm{\theta})$
$\displaystyle=\mathcal{L}_{\textnormal{bag}}(\bm{\theta})+\rho{\mathcal{R}}(\bm{\theta})$
$\displaystyle=\mathcal{L}_{\textnormal{bag}}(\bm{\theta})+\rho(\mathcal{L}_{\textnormal{ins}}(\bm{\theta})-\mathcal{L}_{\textnormal{bag}}(\bm{\theta}))$
$\displaystyle=\frac{1}{2mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}\left((1-\rho)(\bar{y}_{a}-{\bm{x}}_{a}^{T}\bm{\theta})^{2}+\rho(\bar{y}_{a}-{\bm{x}}_{i}^{T}\bm{\theta})^{2}\right)\,,$
(7)

with $y_{a}$ and ${\bm{x}}_{a}$ respectively denoting the average response and
average of feature vectors in bag $a$. We also define
$\widehat{\bm{\theta}}_{{\rm int}}:=\arg\min_{\bm{\theta}}\mathcal{L}_{{\rm
int}}(\bm{\theta})$.

In this section, we derive a precise characterization of the bias and variance
of $\widehat{\bm{\theta}}_{{\rm int}}$. Our theory provides a precise
understanding on the role of different factors, such as bags size $k$,
overparametrization, and signal-to-noise ratio of the data. It also allows us
to theoretically derive optimal regularization parameter $\rho$.

We next describe the the asymptotic regime of interest and our assumptions.

######  Assumption 2.3.

(Asymptotic Setting) We focus on the so-called ‘proportional’ regime where the
sample size $n$ and the features dimension $d$ grow in proportion as
$d\to\infty$. Formally for an arbitrary but fixed constant
$\psi\in(1,\infty)$, we have $n/d\to\psi$. We further assume that the size of
bags $(k)$ remains fixed as $d\to\infty$, and the model norm
$\|\bm{\theta}_{0}\|$ converges. For the sake of normalization and without
loss of generality, we assume $\lim_{d\to\infty}\|\bm{\theta}_{0}\|=1$.

We next state our assumption on the bagging structure.

######  Assumption 2.4.

We assume that the bagging configuration is independent from the training data
$({\bm{X}},{\bm{y}})$. 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
described in Assumption 2.3. Also suppose that the bags are of size $k$ and
are non-overlapping as described in Assumption 2.4. The bias and variance of
$\widehat{\bm{\theta}}_{{\rm int}}$ are characterized below:

  * •

Bias: For $k>1$ and $\rho>0$, let $\alpha_{*}$ be the nonnegative fixed point
of the following equation:

$\rho+\frac{\psi}{k(1-\alpha_{*})}-1=\frac{\psi}{k\alpha_{*}}\rho(k-1)\,.$

The bias of $\widehat{\bm{\theta}}_{{\rm int}}$ converges in probability to

$\displaystyle\operatorname{Bias}(\widehat{\bm{\theta}}_{{\rm
int}})\stackrel{{\scriptstyle(p)}}{{\to}}\alpha_{*}^{2}+\frac{\alpha_{*}^{2}}{\frac{(k-1)\psi}{k^{2}(1-\alpha_{*})^{2}}-(\frac{\alpha_{*}}{1-\alpha_{*}})^{2}\frac{1}{k}-\frac{k-1}{k}}\,.$
(8)

If $k=1$ or $\rho=0$, then $\widehat{\bm{\theta}}_{{\rm int}}$ is unbiased.

  * •

Variance: Let $(v_{*},u_{*})$ be the solution of the following system of
equations:

$\left\\{\begin{aligned}
&\frac{\psi}{1+u}+\frac{\rho\psi(k-1)}{\rho+u}=k\,,\\\
&\frac{\psi(1+v)}{(1+u)^{2}}+\frac{\rho^{2}\psi(k-1)}{(\rho+u)^{2}}=k\,.\end{aligned}\right.$

We then have

$\displaystyle\mathrm{Var}(\widehat{\bm{\theta}}_{{\rm
int}})\stackrel{{\scriptstyle(p)}}{{\to}}\frac{\sigma^{2}}{v_{*}}\,.$ (9)

##  3 Discussion

###  3.1 Comparison between bag-level and instance-level estimators

We next specialize the result of Theorem 2.5 to $\rho=0$ (corresponding to the
bag-level loss) and $\rho=1$ (corresponding to the instance-level loss). Note
that the bag-level loss is the ordinary least square estimator with $m=n/k$
samples and $d$ parameters and therefore is well-defined only for $n\geq kd$.
In the asymptotic regime of Assumption 2.3, this implies that
$\psi=\lim_{d\to\infty}n/d\geq 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 $\psi\geq k$. For the bag-level estimator
$\widehat{\bm{\theta}}_{{\rm
bag}}:=\arg\min_{\bm{\theta}}\mathcal{L}_{\textnormal{bag}}(\bm{\theta})$, we
have

$\displaystyle\operatorname{Bias}(\widehat{\bm{\theta}}_{{\rm
bag}})\stackrel{{\scriptstyle(p)}}{{\to}}0,\quad\mathrm{Var}(\widehat{\bm{\theta}}_{{\rm
bag}})\stackrel{{\scriptstyle(p)}}{{\to}}\frac{\sigma^{2}}{\frac{\psi}{k}-1}.$

  * •

Instance-level loss: For the instance-level estimator
$\widehat{\bm{\theta}}_{{\rm
ins}}:=\arg\min_{\bm{\theta}}\mathcal{L}_{\textnormal{ins}}(\bm{\theta})$, we
have

$\displaystyle\operatorname{Bias}(\widehat{\bm{\theta}}_{{\rm
ins}})\stackrel{{\scriptstyle(p)}}{{\to}}\Big{(}1-\frac{1}{k}\Big{)}\Big{(}1+\frac{2-\psi}{k(\psi-1)}\Big{)},\quad\operatorname{Var}(\widehat{\bm{\theta}}_{{\rm
ins}})\stackrel{{\scriptstyle(p)}}{{\to}}\frac{\sigma^{2}}{k(\psi-1)}.$

As we 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 a threshold on the model signal-to-noise ratio
(SNR), defined as ${\rm SNR}=\|\bm{\theta}_{0}\|^{2}/\sigma^{2}$, under which
the bag-level estimator has the smaller risk and above it the instance-level
loss has the smaller risk.

######  Lemma 3.2.

Suppose $\psi\geq k>1$. Then, $\operatorname{Risk}(\widehat{\bm{\theta}}_{{\rm
ins}})\leq\operatorname{Risk}(\widehat{\bm{\theta}}_{{\rm bag}})$ if and only
if

$\displaystyle{\rm
SNR}:=\frac{\|\bm{\theta}_{0}\|^{2}}{\sigma^{2}}\leq\frac{(k+1)\psi-k}{(\psi-k)(\psi(1-\frac{1}{k})-1+\frac{2}{k})}.$

For $k=1$, we have $\widehat{\bm{\theta}}_{{\rm
ins}}=\widehat{\bm{\theta}}_{{\rm bag}}$ and so 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 a
lower prediction risk than the bag-level estimator.

###  3.2 Role of different factors on model risk

Our theory allows to precisely characterize the effect of different factors,
namely the bag size, SNR, overparametrization and the regularization parameter
on the bias, variance and risk of the estimator. In Figure 1 we plot the
theoretical curves derived in Theorem 2.5 versus $\rho$. As we see by
increasing $\rho$ (stronger regularization), the bias increases and the
variance decreases. The curves for the risk (rightmost panel) exhibits an
optimal $\rho$ 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 $k$
induces more bias. For small $\rho$, larger $k$ increases the variance, but at
large $\rho$, increasing $k$ reduces the variance. The last row of figures
shows the effect of $\psi=n/d$. Larger $\psi$ decreases bias, variance and the
risk since it corresponds to more samples relative to the number of parameters
to be estimated.

Figure 1: Effect of SNR, bag size ($k$) and overparametrization $(1/\psi=d/n)$
on the bias, variance and the risk of the model. The curves are the
theoretical curves given by Theorem 2.5.

##  4 Differentially private aggregate learning

As we discussed aggregate learning framework provides some layer of privacy
protections by obfuscating 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 $k$, replacing individual responses
with the aggregate ones offers $k$-anonymity, a privacy notion, stating that
any record is indistinguishable from at least $k-1$ other records, in terms of
response. One can also argue about the information leakage in aggregate
learning through the notion of mutual information between individual and
aggregate responses, conditional on the features vectors.

Another widely used privacy notion is differential privacy (DP), put forward
by Dwork et al. (2006b, a). Informally speaking, a mechanism (data processing
algorithm) is called DP, if its output 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 Chaudhuri & Hsu
(2011), in which the changes only happen on the ‘response’ of a 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 responses (medical test results). We recall the formal definition of
label DP from (Chaudhuri & Hsu, 2011).

######  Definition 4.1.

(Label Differential Privacy) Consider a randomized mechanism
$\mathcal{M}:D\to\mathcal{O}$ that takes as input a dataset $D$ and outputs
into $\mathcal{O}$. A mechanism $\mathcal{M}$ is called $\varepsilon$\- label
DP, if for any two datasets ($D$, $D^{\prime}$ ) that differ in the label of a
single example and any subset $O\subseteq\mathcal{O}$ we have

${\mathbb{P}}[\mathcal{M}(D)\in O]\leq
e^{\varepsilon}{\mathbb{P}}[\mathcal{M}(D^{\prime})\in O]\,,$

where $\varepsilon$ 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 aggregate (truncated) responses to
ensure label DP guarantee. The procedure is outlined in Algorithm 1. The
truncation level is of order $\sqrt{\log 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 to bound the sensitivity of aggregate responses and
decide on the noise variance needed to ensure DP.

Algorithm 1 Label differentially private learning from aggregate data

Input: individual responses $y_{1},\dotsc,y_{n}$, bags $B_{1},\dotsc,B_{m}$
eahc of size $k$, truncation level $C$.

Output: Privatized aggregate responses $\tilde{y}_{1},\dotsc,\tilde{y}_{m}$

 _// Clip the responses_

for $i=1,2,\dotsc,n$ do

$y_{i}^{c}\leftarrow\max(\min(y_{i},C\sqrt{\log n}),-C\sqrt{\log n})$

end for

for $a=1,2,\dotsc,m$ do

$\bar{y}_{a}\leftarrow\frac{1}{k}\sum_{i\in B_{a}}y_{i}$

$\tilde{y}_{a}\leftarrow\bar{y}_{a}+z_{a}$ where $z_{a}\sim{\rm
Laplace}\Big{(}\frac{C\sqrt{\log n}}{k\varepsilon}\Big{)}.$

end for

Figure 2: Optimal bag size $k$ as a function of $\log(\rho)$, for label DP
learning from aggregate data. We observe a phase transition, where for some
$\rho_{*}$ if $\rho<\rho_{*}$, $k=1$ is the best choice while for
$\rho>\rho_{*}$ the largest $k$ is optimal.

######  Lemma 4.2.

The mechanism described in Algorithm 1 is $\varepsilon$-label DP.

With slight abuse of notation, we let $\widehat{\bm{\theta}}_{{\rm int}}$ be
the minimizer of the interpolating loss, when the learner uses the privatized
aggregate responses $\tilde{y}_{a}$, $a\in[m]$ provided by Algorithm 1. By
Lemma 4.2 and the post-processing property of differential privacy,
$\widehat{\bm{\theta}}_{{\rm int}}$ is also $\varepsilon$-label DP. In the
next theorem, we use our theoretical result from Section 2.2 to characterize
the risk of $\widehat{\bm{\theta}}_{{\rm int}}$ in terms of privacy loss
$\varepsilon$ and the bags size $k$, among other factors.

######  Theorem 4.3.

Let $\widehat{\bm{\theta}}_{{\rm
int}}\in\arg\min_{\bm{\theta}}\mathcal{L}_{{\rm int}}(\bm{\theta})$ using the
privatized aggregate responses from Algorithm 1, with $C^{2}>2(1+\sigma^{2})$.
Let $(v_{*},u_{*})$ be the solution of the following system of equations:

$\left\\{\begin{aligned}
&\frac{\psi}{1+u}+\frac{\rho\psi(k-1)}{\rho+u}=k\,,\\\
&\frac{\psi(1+v)}{(1+u)^{2}}+\frac{\rho^{2}\psi(k-1)}{(\rho+u)^{2}}=k\,.\end{aligned}\right.$

We then have

$\displaystyle\frac{1}{\log n}\operatorname{Risk}(\widehat{\bm{\theta}}_{{\rm
int}})\stackrel{{\scriptstyle(p)}}{{\to}}\frac{2C^{2}}{k\varepsilon^{2}}\frac{1}{v_{*}}\,.$
(10)

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 $\widehat{\bm{\theta}}_{{\rm
int}}$. On the one side, large bag sizes allow the aggregate responses to be
less sensitive to each individual response, which means smaller noise is
needed to ensure $\varepsilon$-DP. On the other hand, at small $\rho$, larger
$k$ can cause larger instability because it amounts to fewer bags and hence
fewer (aggregate) labels. As $\rho$ increases, the regularization becomes
stronger and brings more stability. In Figure 2 we plot optimal $k^{*}$ (from
the bounded set $\\{1,\dotsc,5\\}$) versus $\rho$. Interestingly, we observe a
phase transition in the sense that for some $\rho_{*}$, if $\rho<\rho_{*}$
then $k^{*}=1$, due to the instability effect explained above, while for
$\rho>\rho_{*}$ 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 $\rho_{*}$ increases as $\psi$ decreases.
Recall that $\psi=n/d$, and so the instability due to sample size is stronger
at smaller $\psi$. Hence, a larger regularization is needed to control it.
Also note that if we optimize jointly over $(k,\rho)$, the risk is minimized
at $\rho=1$ and $k=5$, i.e., the instance-level loss with the largest possible
value of $k$ in the predetermined range.

Figure 3: Solid curves correspond are the theoretical curves (Theorem 2.5) and
the dots (symbols) correspond to simulations. Here $d=100$, and we already see
a perfect match between the (asymptotic) theory and the simulations.

##  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 $d=100$ and generate $\bm{\theta}_{0}$ to have
i.i.d normal entries and then scale it to be unit norm. The sample size is set
as $n=\psi d$ and the noise standard deviation is set as
$\sigma=\|\bm{\theta}_{0}\|/{\rm SNR}=1/{\rm SNR}$. The solid curves in Figure
3 are the theoretical curves and the dots correspond to the simulation.
Although the derived theory is in an asymptotic regime, we already see a
perfect match for $d=100$.

Figure 4: Test loss versus the regularization parameter $\rho$ for different
bag sizes, on the Boston Housing dataset. The values on the lines represent
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 $\rho$ that
achieves the minimum test loss.

Boston Housing dataset. To investigate the optimal value of the regularization
parameter $\rho$ in the interpolating loss, for different bag sizes, we
conduct numerical experiments on the Boston Housing dataset. Recall that
$\rho=0$ corresponds to the bag-level loss and $\rho=1$ corresponds to the
instance-level loss. The Boston Housing dataset is a regression dataset that
predicts the median value of owner-occupied homes in Boston, Massachusetts, in
the mid-1970s (Harrison Jr & Rubinfeld, 1978). The dataset contains 13
features, including the crime rate, per capita income, and the number of rooms
per dwelling. We use a 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 $\rho$. For each value
of $\rho$ in $[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 $\rho$ that achieves the minimum test loss.

From Figure 4, we have the following observations: First, for a fixed bag
size, smaller $\rho$ values (which means that the loss is closer to the bag-
level loss) yield larger variance, while larger $\rho$ 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 a
regularization effect (as shown in Lemma 2.1). Second, as the bag size
increases, the optimal $\rho$ value increases. For example, when the bag size
is 80, the optimal $\rho$ value is 0, while when the bag size is 240, the
optimal $\rho$ value is 1. For bag sizes between 80 and 240, the optimal
$\rho$ value is achieved in $(0,1)$. In other words, larger bag sizes require
stronger regularization (larger $\rho$) to achieve the minimum test loss.

##  6 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 a novel interpolating estimator. We also
provided a theoretical analysis of the interpolating estimator for linear
regression tasks and proposed a mechanism for differentially private learning
from aggregate responses. Finally, we conducted experiments to corroborate our
theory and show the efficacy of the interpolating estimator.

## Acknowledgement

Adel Javanmard is supported in part by the NSF CAREER Award DMS-1844481 and
the NSF Award DMS-2311024.

## References

  * Al-Rubaie & Chang (2019) Mohammad Al-Rubaie and J Morris Chang.  Privacy-preserving machine learning: Threats and solutions.  _IEEE Security & Privacy_, 17(2):49–58, 2019\.
  * Apple Developer Documentation (2023) Apple Developer Documentation.  Apple storekit ad network.  https://developer.apple.com/documentation/storekit/skadnetwork/, 2023.
  * Ardehaly & Culotta (2017) 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.
  * Busa-Fekete et al. (2023) Robert Istvan Busa-Fekete, Heejin Choi, Travis Dick, Claudio Gentile, et al.  Easy learning from label proportions.  _arXiv preprint arXiv:2302.03115_ , 2023.
  * Chaudhuri & Hsu (2011) Kamalika Chaudhuri and Daniel Hsu.  Sample complexity bounds for differentially private learning.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pp. 155–186. JMLR Workshop and Conference Proceedings, 2011.
  * Chen et al. (2023) Lin Chen, Thomas Fu, Amin Karbasi, and Vahab Mirrokni.  Learning from aggregated data: Curated bags versus random bags.  _arXiv preprint arXiv:2305.09557_ , 2023.
  * Chen et al. (2017) Zhensong Chen, Zhiquan Qi, Bo Wang, Limeng Cui, Fan Meng, and Yong Shi.  Learning with label proportions based on nonparallel support vector machines.  _Knowledge-Based Systems_ , 119:126–141, 2017.
  * Criteo Privacy Preserving ML Competition (2021) Criteo Privacy Preserving ML Competition.  Criteo privacy preserving ML competition at AdKDD 2021.  http://go.criteo.net/criteo-ppml-challenge-adkdd21-dataset.zip, 2021\.
  * Cui et al. (2017) Limeng Cui, Jiawei Zhang, Zhensong Chen, Yong Shi, and S Yu Philip.  Inverse extreme learning machine for learning with label proportions.  In _2017 IEEE International Conference on Big Data (Big Data)_ , pp. 576–585. IEEE, 2017.
  * De Cristofaro (2020) Emiliano De Cristofaro.  An overview of privacy in machine learning.  _arXiv preprint arXiv:2005.08679_ , 2020.
  * Dulac-Arnold et al. (2019) Gabriel Dulac-Arnold, Neil Zeghidour, Marco Cuturi, Lucas Beyer, and Jean-Philippe Vert.  Deep multi-class learning from label proportions.  _arXiv preprint arXiv:1905.12909_ , 2019.
  * Dwork et al. (2006a) 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.
  * Dwork et al. (2006b) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pp. 265–284. Springer, 2006b.
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Fish & Reyzin (2017) Benjamin Fish and Lev Reyzin.  On the complexity of learning from label proportions.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , pp. 1675–1681, 2017.
  * Gordon (1988) Yehoram Gordon.  On milman’s inequality and random subspaces which escape through a mesh in $\mathbb{R}^{n}$.  In _Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1986–87_ , pp. 84–106. Springer, 1988.
  * Harrison Jr & Rubinfeld (1978) David Harrison Jr and Daniel L Rubinfeld.  Hedonic housing prices and the demand for clean air.  _Journal of environmental economics and management_ , 5(1):81–102, 1978.
  * Hassani & Javanmard (2022) Hamed Hassani and Adel Javanmard.  The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression.  _arXiv preprint arXiv:2201.05149_ , 2022.
  * Hastie et al. (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.
  * Javanmard et al. (2020) 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\.
  * Li & Wang (2018) Yue Li and Bo Wang.  A study on customer churn of commercial banks based on learning from label proportions.  In _2018 IEEE International Conference on Data Mining Workshops (ICDMW)_ , pp. 1241–1247. IEEE, 2018.
  * Lu et al. (2019) 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.
  * Mei & Montanari (2022) Song Mei and Andrea Montanari.  The generalization error of random features regression: Precise asymptotics and the double descent curve.  _Communications on Pure and Applied Mathematics_ , 75(4):667–766, 2022.
  * Mou et al. (2018) Wenlong Mou, Yuchen Zhou, Jun Gao, and Liwei Wang.  Dropout training, data-dependent regularization, and generalization bounds.  In _International conference on machine learning_ , pp. 3645–3653. PMLR, 2018.
  * Musicant et al. (2007) 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.
  * Papernot et al. (2016) Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael Wellman.  Towards the science of security and privacy in machine learning.  _arXiv preprint arXiv:1611.03814_ , 2016.
  * Patrini et al. (2014) Giorgio Patrini, Richard Nock, Paul Rivera, and Tiberio Caetano.  (almost) no label no cry.  _Advances in Neural Information Processing Systems_ , 27, 2014.
  * Qi et al. (2016) Zhiquan Qi, Bo Wang, Fan Meng, and Lingfeng Niu.  Learning with label proportions via npsvm.  _IEEE transactions on cybernetics_ , 47(10):3293–3305, 2016.
  * Qi et al. (2017) Zhiquan Qi, Fan Meng, Yingjie Tian, Lingfeng Niu, Yong Shi, and Peng Zhang.  Adaboost-llp: a boosting method for learning with label proportions.  _IEEE transactions on neural networks and learning systems_ , 29(8):3548–3559, 2017.
  * Quadrianto et al. (2008) Novi Quadrianto, Alex J Smola, Tiberio S Caetano, and Quoc V Le.  Estimating labels from label proportions.  In _Proceedings of the 25th international conference on Machine learning_ , pp. 776–783, 2008.
  * Rueping (2010) Stefan Rueping.  Svm classifier estimation from group probabilities.  In _Proceedings of the 27th international conference on machine learning (ICML-10)_ , pp. 911–918, 2010.
  * Saket (2021) Rishi Saket.  Learnability of linear thresholds from label proportions.  _Advances in Neural Information Processing Systems_ , 34:6555–6566, 2021.
  * Saket et al. (2022) Rishi Saket, Aravindan Raghuveer, and Balaraman Ravindran.  On combining bags to better learn from label proportions.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 5913–5927. PMLR, 2022.
  * Scott & Zhang (2020) Clayton Scott and Jianxin Zhang.  Learning from label proportions: A mutual contamination framework.  _Advances in neural information processing systems_ , 33:22256–22267, 2020.
  * Shi et al. (2018) Yong Shi, Jiabin Liu, Zhiquan Qi, and Bo Wang.  Learning from label proportions on high-dimensional data.  _Neural Networks_ , 103:9–18, 2018.
  * Shi et al. (2019) Yong Shi, Limeng Cui, Zhensong Chen, and Zhiquan Qi.  Learning from label proportions with pinball loss.  _International Journal of Machine Learning and Cybernetics_ , 10(1):187–205, 2019.
  * Shivaswamy & Jebara (2010) Pannagadatta K Shivaswamy and Tony Jebara.  Maximum relative margin and data-dependent regularization.  _Journal of Machine Learning Research_ , 11(2), 2010.
  * Sunjaya & Sunjaya (2020) Angela Felicia Sunjaya and Anthony Paulo Sunjaya.  Pooled testing for expanding covid-19 mass surveillance.  _Disaster Medicine and Public Health Preparedness_ , 14(3):e42–e43, 2020.
  * Thrampoulidis et al. (2015) 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\.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wein & Zenios (1996) Lawrence M Wein and Stefanos A Zenios.  Pooled testing for hiv screening: capturing the dilution effect.  _Operations Research_ , 44(4):543–569, 1996.
  * Xiao et al. (2020) Yanshan Xiao, HuaiPei Wang, and Bo Liu.  A new transfer learning-based method for label proportions problem.  _Information Sciences_ , 541:391–408, 2020.
  * Yu et al. (2013) Felix Yu, Dong Liu, Sanjiv Kumar, Jebara Tony, and Shih-Fu Chang.  $\propto$SVM for learning with label proportions.  In _International conference on machine learning_ , pp. 504–512. PMLR, 2013.
  * Yu et al. (2014) Felix X Yu, Krzysztof Choromanski, Sanjiv Kumar, Tony Jebara, and Shih-Fu Chang.  On learning from label proportions.  _arXiv preprint arXiv:1402.5902_ , 2014.
  * Zhang et al. (2020) Yivan Zhang, Nontawat Charoenphakdee, Zhenguo Wu, and Masashi Sugiyama.  Learning from aggregate observations.  _Advances in Neural Information Processing Systems_ , 33:7993–8005, 2020.
  * Zhao et al. (2019) Han Zhao, Yao-Hung Hubert Tsai, Russ R Salakhutdinov, and Geoffrey J Gordon.  Learning neural networks with adaptive regularization.  _Advances in Neural Information Processing Systems_ , 32, 2019.

##  Appendix A Proof of theorems and technical lemmas

###  A.1 Proof of Lemma 2.1

Recall the shorthand $\bar{y}_{a}=(\sum_{i\in B_{a}}y_{i})/k$, for $a\in[m]$.
We have,

$\displaystyle\mathcal{L}_{\textnormal{ins}}(\bm{\theta})$
$\displaystyle=\frac{1}{mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}(\bar{y}_{a}-f_{\bm{\theta}}({\bm{x}}_{i}))^{2}$
$\displaystyle=\frac{1}{mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}\Big{(}\bar{y}_{a}-\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})+\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}^{2}$
$\displaystyle=\frac{1}{mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}\Big{(}\bar{y}_{a}-\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})\Big{)}^{2}+\frac{1}{mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}\Big{(}\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}^{2}$
$\displaystyle\quad+\frac{2}{mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}\Big{(}\bar{y}_{a}-\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})\Big{)}\Big{(}\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}$

Note that the first term can be written as

$\frac{1}{mk}\sum_{a=1}^{m}\sum_{i\in
B_{a}}\Big{(}\bar{y}_{a}-\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})\Big{)}^{2}=\frac{1}{k}\sum_{a=1}^{m}\Big{(}\bar{y}_{a}-\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})\Big{)}^{2}=\mathcal{L}_{\textnormal{bag}}(\bm{\theta})\,.$

For the second term, we have

$\displaystyle\sum_{i\in B_{a}}\Big{(}\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}^{2}$
$\displaystyle=\frac{1}{k}\sum_{i,j\in
B_{a}}(f_{\bm{\theta}}({\bm{x}}_{i})-f_{\bm{\theta}}({\bm{x}}_{j}))^{2}={\mathcal{R}}(\bm{\theta})\,,$

where we used the following identity for $a_{1},\dotsc,a_{k}$ and
$\bar{a}=(\sum_{i=1}^{k}a_{i})/k$:

$\displaystyle\sum_{i=1}^{k}(a_{i}-\bar{a})^{2}=\frac{1}{k}\sum_{i,j=1}^{k}(a_{i}-a_{j})^{2}\,.$
(11)

Finally, the third term works out at zero because

$\displaystyle\sum_{a=1}^{m}\sum_{i\in
B_{a}}\Big{(}\bar{y}_{a}-\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})\Big{)}\Big{(}\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}$
$\displaystyle=\sum_{a=1}^{m}\Big{(}\bar{y}_{a}-\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})\Big{)}\bigg{[}\sum_{i\in
B_{a}}\Big{(}\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}\bigg{]}=0,$

since

$\sum_{i\in B_{a}}\Big{(}\frac{1}{k}\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}=\sum_{j\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{j})-\sum_{i\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{i})=0\,.$

Combining the three terms together we arrive at
$\mathcal{L}_{\textnormal{ins}}(\bm{\theta})=\mathcal{L}_{\textnormal{bag}}(\bm{\theta})+{\mathcal{R}}(\bm{\theta})$.

###  A.2 Proof of Lemma 2.2

We use the shorthand $\bar{f}_{a}=(\sum_{i\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{i}))/k$, for $a\in[m]$. By Taylor’s expansion
of the loss $\ell$ on its second argument we have

$\ell(\bar{y}_{a},f_{\bm{\theta}}({\bm{x}}_{i}))=\ell(\bar{y}_{a},\bar{f}_{a})+\frac{\partial}{\partial
b}\ell(\bar{y}_{a},\bar{f}_{a})(f_{\bm{\theta}}({\bm{x}}_{i})-\bar{f}_{a})+\frac{1}{2}\frac{\partial^{2}}{\partial
b^{2}}\ell(\bar{y}_{a},f)(f_{\bm{\theta}}({\bm{x}}_{i})-\bar{f}_{a})^{2}\,,$

for some $f$ between $\bar{f}_{a}$ and $f_{\bm{\theta}}({\bm{x}}_{i})$ and
$\partial/\partial_{b}$, $\partial^{2}/\partial_{b}^{2}$ indicate the first
and second derivative of $\ell(a,b)$ with respect to the second input $b$.

Summing both sides of the above equation over $i\in B_{a}$, the second term
works out at zero since $\sum_{i\in
B_{a}}(f_{\bm{\theta}}({\bm{x}}_{i})-\bar{f}_{a})=0$. Using the bound on the
second derivative we arrive at

$\sum_{i\in B_{a}}\ell(\bar{y}_{a},f_{\bm{\theta}}({\bm{x}}_{i}))\leq
k\ell(\bar{y}_{a},\bar{f}_{a})+\sum_{i\in
B_{a}}C(f_{\bm{\theta}}({\bm{x}}_{i})-\bar{f}_{a})^{2}\,.$

Next, summing both sides of the above equation over bags $a\in[m]$, and
dividing by $mk$, we get

$\mathcal{L}_{\textnormal{ins}}(\bm{\theta})\leq\mathcal{L}_{\textnormal{bag}}(\bm{\theta})+\frac{1}{k}\sum_{a=1}^{m}\sum_{i\in
B_{a}}C(f_{\bm{\theta}}({\bm{x}}_{i})-\bar{f}_{a})^{2}\,.$

By invoking identity (11) in the above we arrive at (5).

We are now ready to prove the second part of the statement. If the loss
$\ell(\cdot,\cdot)$ is convex in the second input, by the Jensen’s inequality
we have

$\displaystyle\frac{1}{k}\sum_{i\in
B_{a}}\ell(\bar{y}_{a},f_{\bm{\theta}}({\bm{x}}_{i}))\geq\ell\Big{(}\bar{y}_{a},\frac{1}{k}\sum_{i\in
B_{a}}f_{\bm{\theta}}({\bm{x}}_{i})\Big{)}$

Taking the average of both side over the bags $a\in[m]$, we obtain that
$\mathcal{L}_{\textnormal{ins}}(\bm{\theta})\geq\mathcal{L}_{\textnormal{bag}}(\bm{\theta})$,
which completes the proof of lemma.

##  Appendix B Proof of Theorem 2.5

Recall $m$ as the number of bags, and $n$ as the number of samples. Since the
bags are non-overlapping and each of size $k$, we have $m=n/k$. Define
${\bm{S}}\in\mathbb{R}^{m\times n}$, as a matrix the encodes the bagging
structure, with $S_{ia}=1/\sqrt{k}\bm{1}_{\\{{j\in B_{a}}\\}}$ where $B_{a}$
indicates $a$-th bag, for $a\in[m]$.

We next write the bag-level loss function and the instance-level loss function
in terms of ${\bm{S}}$ as follows:

$\begin{split}\mathcal{L}_{\textnormal{bag}}(\bm{\theta})&=\frac{1}{km}\|{\bm{S}}({\bm{y}}-{\bm{X}}{\bm{\theta}})\|_{2}^{2}\,,\\\
\mathcal{L}_{\textnormal{ins}}(\bm{\theta})&=\frac{1}{km}\|{\bm{S}}^{\top}{\bm{S}}{\bm{y}}-{\bm{X}}\bm{\theta}\|_{2}^{2}\,.\end{split}$

The interpolating loss function (2.2) then reads as

$\mathcal{L}_{{\rm
int}}({\bm{\theta}})=\frac{1}{mk}\left((1-\rho)\|{\bm{S}}{\bm{X}}{\bm{\theta}}-{\bm{S}}{\bm{y}}\|_{2}^{2}+\rho\left\|{\bm{X}}\bm{\theta}-{\bm{S}}^{\top}{\bm{S}}{\bm{y}}\right\|_{2}^{2}\right)\,.$

This can equivalently be written as

$\mathcal{L}_{{\rm
int}}(\bm{\theta})=\frac{1}{mk}\left\|\begin{pmatrix}\sqrt{\rho}{\bm{I}}\\\
\sqrt{1-\rho}{\bm{S}}\end{pmatrix}{\bm{X}}{\bm{\theta}}-\begin{pmatrix}\sqrt{\rho}{\bm{S}}^{\top}{\bm{S}}{\bm{y}}\\\
\sqrt{1-\rho}{\bm{S}}{\bm{y}}\end{pmatrix}\right\|_{2}^{2}\,.$

The minimizer of the above loss admits a closed-from solution given by
$\widehat{\bm{\theta}}_{{\rm int}}={\bm{B}}{\bm{y}}$, with

${\bm{B}}=\left({\bm{X}}^{\top}\left(\rho{\bm{I}}+(1-\rho){\bm{S}}^{\top}{\bm{S}}\right){\bm{X}}\right)^{-1}{\bm{X}}^{\top}{\bm{S}}^{\top}{\bm{S}}\,.$

We define the shorthand
${\bm{E}}:=\rho{\bm{I}}+(1-\rho){\bm{S}}^{\top}{\bm{S}}\in\mathbb{R}^{n\times
n}$, which is non-singular for $\rho>0$, and
${\bm{M}}=({\bm{X}}^{\top}{\bm{E}}{\bm{X}})^{-1}{\bm{X}}^{\top}\in\mathbb{R}^{d\times
n}$. We then have ${\bm{B}}={\bm{M}}{\bm{S}}^{\top}{\bm{S}}$.

We next recall the bias-variance decomposition (6), where the bias and
variance are given by

$\displaystyle\operatorname{Bias}(\widehat{\bm{\theta}}_{{\rm int}})$
$\displaystyle=\|({\bm{B}}{\bm{X}}-{\bm{I}})\bm{\theta}_{0}\|_{2}^{2}$
$\displaystyle=\|({\bm{M}}{\bm{S}}^{\top}{\bm{S}}{\bm{X}}-{\bm{M}}{\bm{E}}{\bm{X}})\bm{\theta}_{0}\|_{2}^{2}$
$\displaystyle=\|{\bm{M}}({\bm{S}}^{\top}{\bm{S}}-{\bm{E}}){\bm{X}}\bm{\theta}_{0}\|_{2}^{2}\,,$
(12) $\displaystyle\mathrm{Var}(\widehat{\bm{\theta}}_{{\rm int}})$
$\displaystyle=\sigma^{2}\|{\bm{M}}{\bm{S}}^{\top}{\bm{S}}\|_{F}^{2}\,,$ (13)

with $\|\cdot\|_{F}$ indicating the matrix Frobenius norm.

We continue by treating the bias and the variance separately.

###  B.1 Calculating the bias

Since the distribution of the features matrix ${\bm{X}}$ is invariant under
rotation, we can assume that
$\bm{\theta}_{0}=\|\bm{\theta}_{0}\|{\bm{e}}_{i}$, where
${\bm{e}}_{i}\in{\mathbb{R}}^{d}$ is the vector with one at $i$-th entry and
zero everywhere else. By taking average on $i\in[d]$ we obtain

$\begin{split}\operatorname{Bias}(\widehat{\bm{\theta}}_{{\rm
int}})&\stackrel{{\scriptstyle(d)}}{{=}}\frac{\|{\bm{\theta}}_{0}\|_{2}^{2}}{d}\sum_{i\in[d]}\|{\bm{M}}({\bm{S}}^{\top}{\bm{S}}-{\bm{E}}){\bm{X}}{\bm{e}}_{i}\|_{2}^{2}\\\
&=\frac{\|{\bm{\theta}}_{0}\|_{2}^{2}}{d}\operatorname{tr}\Big{(}{\bm{M}}({\bm{S}}^{\top}{\bm{S}}-{\bm{E}}){\bm{X}}\Big{(}\sum_{i\in[p]}{\bm{e}}_{i}{\bm{e}}_{i}^{\top}\Big{)}{\bm{X}}^{\top}({\bm{S}}^{\top}{\bm{S}}-{\bm{E}}){\bm{M}}^{\top}\Big{)}\\\
&=\frac{\|{\bm{\theta}}_{0}\|_{2}^{2}}{d}\left\|{\bm{M}}({\bm{S}}^{\top}{\bm{S}}-{\bm{E}}){\bm{X}}\right\|_{F}^{2}\,.\end{split}$

Let us define ${\bm{\Lambda}}\in{\mathbb{R}}^{n\times n}$ as follows:

$\displaystyle{\bm{\Lambda}}$
$\displaystyle:=-({\bm{S}}^{\top}{\bm{S}}-{\bm{E}})$
$\displaystyle=-({\bm{S}}^{\top}{\bm{S}}-(\rho{\bm{I}}+(1-\rho){\bm{S}}^{\top}{\bm{S}}))$
$\displaystyle=\rho({\bm{I}}-{\bm{S}}^{\top}{\bm{S}})\,.$ (14)

The bias can then be written in terms of ${\bm{\Lambda}}$ as
$\operatorname{Bias}(\bm{\theta})=\frac{1}{d}\|{\bm{M}}{\bm{\Lambda}}{\bm{X}}\|_{F}^{2}$.
In our next lemma, we characterize the asymptotic behavior of the bias.

######  Lemma B.1.

Under the asymptotic regime of Assumption 2.3, we have

$\frac{1}{d}\|{\bm{M}}{\bm{\Lambda}}{\bm{X}}\|_{F}^{2}\stackrel{{\scriptstyle(p)}}{{\to}}\alpha_{*}^{2}+\frac{\alpha_{*}^{2}}{\frac{(k-1)\psi}{k^{2}(1-\alpha_{*})^{2}}-(\frac{\alpha_{*}}{1-\alpha_{*}})^{2}\frac{1}{k}-\frac{k-1}{k}}\,,$

where $\alpha_{*}$ is the nonnegative fixed point of the following equation:

$\rho+\frac{\psi}{k(1-\alpha_{*})}-1=\frac{\psi}{k\alpha_{*}}\rho(k-1)\,.$

Since $\|\bm{\theta}_{0}\|\to 1$, the result (8) follows from Lemma B.1.

We refer to the supplementary D.1 for the proof of Lemma B.1.

###  B.2 Calculating the variance

Since the bags are non-overlapping we have
${\bm{S}}{\bm{S}}^{\top}={\bm{I}}_{m}$. Therefore ${\bm{S}}^{\top}{\bm{S}}$ is
a projection matrix and can be written as
${\bm{S}}^{\top}{\bm{S}}={\bm{U}}{\bm{U}}^{\top}$, with
${\bm{U}}\in{\mathbb{R}}^{n\times m}$ an orthogonal matrix. Recall that the
variance is given by $\mathrm{Var}(\widehat{\bm{\theta}}_{{\rm
int}})=\sigma^{2}\|{\bm{M}}{\bm{S}}^{\top}{\bm{S}}\|_{F}^{2}$. We use the next
lemma to characterize the asymptotic behavior of the variance.

######  Lemma B.2.

Under the asymptotic regime of Assumption 2.3, for any vector
${\bm{a}}\in{\mathbb{R}}^{m}$ we have

$\frac{n}{\|{\bm{a}}\|^{2}}\|{\bm{M}}{\bm{U}}{\bm{a}}\|_{2}^{2}\stackrel{{\scriptstyle(p)}}{{\to}}\frac{k}{v_{*}}\,,$

where $v_{*}$ is given as the fixed point of the following system of equations
in $(v,u)$:

$\displaystyle\begin{cases}\frac{\psi}{1+u}+\frac{\rho\psi(k-1)}{\rho+u}&=k,\\\
\frac{\psi(1+v)}{(1+u)^{2}}+\frac{\rho^{2}\psi(k-1)}{(\rho+u)^{2}}&=k\,.\end{cases}$

Proof of Lemma B.2 is given in the supplementary D.2.

We next use the above lemma for each row of ${\bm{U}}$ separately (as the
vector ${\bm{a}}$) and add them together. Using the fact that
$\|{\bm{U}}\|_{F}^{2}=m$ and $m/n=k$, we get that
$\|{\bm{M}}{\bm{U}}{\bm{U}}^{\top}\|_{F}^{2}\stackrel{{\scriptstyle(p)}}{{\to}}1/v_{*}$,
which completes the variance calculation.

###  B.3 Proof of Lemma 4.2

We use the idea of (Dwork et al., 2014, Theorem 3.6) to prove this lemma.
Given a database $D=(y_{1},y_{2},\dots,y_{n})$, Algorithm 1 (we denote this
mapping by ${\mathcal{A}}:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$) outputs $m$
real numbers $(\tilde{y}_{1},\tilde{y}_{2},\dots,\tilde{y}_{m})$. Given the
database $D$, we define the map $f:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$ by
$D\mapsto(\bar{y}_{1},\bar{y}_{2},\dots,\bar{y}_{m})$, which computes the mean
of labels in each bag. Fix any pair of neighboring databases $D,D^{\prime}$
that differ in the label of a single example. We have
$\|f(D)-f(D^{\prime})\|_{1}:=\sum_{a\in[m]}|f(D)_{a}-f(D^{\prime})_{a}|\leq\Delta
f:=\frac{C\sqrt{\log n}}{k}$. In this argument, we used 2.4 that assumes non-
overlapping bags, and therefore, changing a certain $y_{i}$ in $D$ leads to a
change in only one of $\bar{y}_{a}$ by at most $\Delta f$. Let
$p_{{\mathcal{A}}(D)}(z)$ and $p_{{\mathcal{A}}(D^{\prime})}(z)$ denote the
probability density function of ${\mathcal{A}}(D)$ and
${\mathcal{A}}(D^{\prime})$. We have

$\displaystyle\frac{p_{{\mathcal{A}}(D)}(z)}{p_{{\mathcal{A}}(D^{\prime})}(z)}={}$
$\displaystyle\prod_{a\in[m]}\frac{\exp\left(-\frac{\varepsilon|f(D)_{a}-z_{a}|}{\Delta
f}\right)}{\exp\left(-\frac{\varepsilon|f(D^{\prime})_{a}-z_{a}|}{\Delta
f}\right)}$ $\displaystyle={}$
$\displaystyle\prod_{a\in[m]}\exp\left(\frac{\varepsilon\left(|f(D^{\prime})_{a}-z_{a}|-|f(D)_{a}-z_{a}|\right)}{\Delta
f}\right)$ $\displaystyle\leq{}$
$\displaystyle\prod_{a\in[m]}\exp\left(\frac{\varepsilon|f(D^{\prime})_{a}-f(D)_{a}|}{\Delta
f}\right)$ $\displaystyle={}$
$\displaystyle\exp\left(\frac{\varepsilon\|f(D)-f(D^{\prime})\|_{1}}{\Delta
f}\right)$ $\displaystyle\leq{}$ $\displaystyle e^{\varepsilon}\,,$

which completes the proof.

##  Appendix C Proof of Theorem 4.3

Recall that in Algorithm 1, the individual responses are first truncated by
$C\sqrt{\log n}$ and then after the aggregate responses are computed, a
Laplace noise is added to them to ensure label DP. We define $\mathcal{E}$ is
the event that no truncation happens, namely:

$\displaystyle\mathcal{E}:=\bm{1}_{\\{{|y_{i}|\leq C\sqrt{\log n},\;\forall
i\in[n]}\\}}\,.$ (15)

Since $y_{i}\sim N(0,\|\bm{\theta}_{0}\|^{2}+\sigma^{2})$,
$\|\bm{\theta}_{0}\|=1$, by using Gaussian tail bound along with union
bounding we arrive at

$\displaystyle{\mathbb{P}}(\mathcal{E})\geq
1-n\exp\Big{(}-\frac{C^{2}}{2(1+\sigma^{2})}\log n\Big{)}=1-n^{-c}\,,$ (16)

with $c=\frac{C^{2}}{2(1+\sigma^{2})}-1>0$.

We next bound the risk of estimator $\widehat{\bm{\theta}}_{{\rm int}}$ as
follows:

$\displaystyle\operatorname{Risk}(\widehat{\bm{\theta}}_{{\rm
int}})=\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}}\\}}|{\bm{X}}]+\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}^{c}}\\}}|{\bm{X}}]\,.$ (17)

For the first term, note that on the instance $\mathcal{E}$ (no truncation),
the privatized aggregate responses are just the aggregate responses with an
additive zero mean noise with variance $2C^{2}\log n/(k\varepsilon)^{2}$. So
we can use the analysis in the proof of Theorem 2.5 with the inflated noise
variance. Let $\widehat{\bm{\theta}}_{{\rm int}}^{{\rm nt}}$ be the estimator
using untruncated responses in Algorithm 1. We then have This gives us

$\displaystyle\frac{1}{\log n}\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}}\\}}|{\bm{X}}]$
$\displaystyle=\frac{1}{\log n}\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}^{{\rm nt}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}}\\}}|{\bm{X}}]$
$\displaystyle=\frac{1}{\log n}\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}^{{\rm nt}}-\bm{\theta}_{0}\|^{2}|{\bm{X}}]-\frac{1}{\log
n}\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm int}}^{{\rm
nt}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}^{c}}\\}}|{\bm{X}}]$
$\displaystyle=\frac{1}{\log n}\operatorname{Bias}(\widehat{\bm{\theta}}_{{\rm
int}}^{{\rm nt}})+\frac{1}{\log n}\mathrm{Var}(\widehat{\bm{\theta}}_{{\rm
int}}^{{\rm nt}})-\frac{1}{\log n}\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}^{{\rm
nt}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}^{c}}\\}}|{\bm{X}}]\,,$ (18)

where the bias is given by (8) and variance is given by (9), where
$\sigma^{2}/k$ is replaced with the inflated variance $\sigma^{2}/k+2C^{2}\log
n/(k\varepsilon)^{2}$. Since $\operatorname{Bias}(\widehat{\bm{\theta}}_{{\rm
int}}^{{\rm nt}})$ has a finite limit, the first term above vanishes as
$n\to\infty$. For the second term we have

$\frac{1}{\log n}\mathrm{Var}(\widehat{\bm{\theta}}_{{\rm int}}^{{\rm
nt}})\stackrel{{\scriptstyle(p)}}{{\to}}\frac{2C^{2}}{k\varepsilon^{2}}\frac{1}{v_{*}}\,.$

since $\sigma^{2}/\log n\to 0$. For the third term, by Cauchy–Schwarz
inequality we have

$\displaystyle\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm int}}^{{\rm
nt}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}^{c}}\\}}|{\bm{X}}]\leq\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}^{{\rm
nt}}-\bm{\theta}_{0}\|^{4}|{\bm{X}}]^{1/2}\;{\mathbb{P}}(\mathcal{E}^{c})\,.$
(19)

Using the high probability bound on the minimum singular value of the Gaussian
matrix ${\bm{X}}$ (Vershynin, 2018, Theorem 4.6.1), we can show that
$\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm int}}^{{\rm
nt}}-\bm{\theta}_{0}\|^{4}|{\bm{X}}]$ is bounded in probability and since
${\mathbb{P}}(\mathcal{E}^{c})\leq n^{-c}$, we conclude that the third term in
(18) also vanishes as $n\to\infty$, in probability. Combining these together
we arrive at

$\displaystyle\frac{1}{\log n}\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}}\\}}|{\bm{X}}]\stackrel{{\scriptstyle(p)}}{{\to}}\frac{2C^{2}}{k\varepsilon^{2}}\frac{1}{v_{*}}\,.$
(20)

Similar to (19) we can also show that

$\frac{1}{\log n}\mathbb{E}[\|\widehat{\bm{\theta}}_{{\rm
int}}-\bm{\theta}_{0}\|^{2}\bm{1}_{\\{{\mathcal{E}^{c}}\\}}|{\bm{X}}]\stackrel{{\scriptstyle(p)}}{{\to}}0\,,$

which along with (20) and (17) implies that

$\frac{1}{\log n}\operatorname{Risk}(\widehat{\bm{\theta}}_{{\rm
int}})\stackrel{{\scriptstyle(p)}}{{\to}}\frac{2C^{2}}{k\varepsilon^{2}}\frac{1}{v_{*}}\,,$

completing the proof.

##  Appendix D Proof of Intermediate Lemmas

###  D.1 Proof of Lemma B.1

Write ${\bm{X}}=[{\bm{x}}_{1},\dotsc,{\bm{x}}_{d}]$ with ${\bm{x}}_{i}$
representing the $i$-th column. We then have
$\|{\bm{M}}{\bm{\Lambda}}{\bm{X}}\|^{2}=\sum_{i=1}^{d}\|{\bm{M}}{\bm{\Lambda}}{\bm{x}}_{i}\|^{2}$.
We compute the asymptotic behavior of each of the summand separately. Indeed,
by symmetry of the distributions of ${\bm{x}}_{i}$, we will see that all
summands converge to the same limit.

Recall that ${\bm{M}}=({\bm{X}}^{\top}{\bm{E}}{\bm{X}})^{-1}{\bm{X}}^{\top}$.
Consider the following optimization problem:

$\displaystyle{\bm{\alpha}}_{i}=\operatorname{arg\,min}_{{\bm{\alpha}}\in\mathbb{R}^{d}}\frac{1}{d}\|{\bm{E}}^{1/2}{\bm{X}}{\bm{\alpha}}-{\bm{E}}^{-1/2}{\bm{\Lambda}}{\bm{x}}_{i}\|_{2}^{2}\,.$
(21)

It is easy to see that by the KKT condition,
${\bm{\alpha}}_{i}=({\bm{X}}^{\top}{\bm{E}}{\bm{X}})^{-1}{\bm{X}}^{\top}{\bm{\Lambda}}{\bm{x}}_{i}={\bm{M}}{\bm{\Lambda}}{\bm{x}}_{i}$.
Therefore, we are interested in characterizing $\|{\bm{\alpha}}_{i}\|$ in the
asymptotic regime, described in Assumption 2.3.

We write ${\bm{\alpha}}$ as $(\alpha_{i},{\bm{\alpha}}_{\sim i})$ to separate
its $i$-th entry form the rest. Likewise we write
${\bm{X}}=[{\bm{x}}_{i}{\bm{X}}_{\sim i}]$ to separate the $i$-th columns from
the rest. We then have

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\frac{1}{d}\|{\bm{E}}^{1/2}{\bm{X}}{\bm{\alpha}}-{\bm{E}}^{-1/2}{\bm{\Lambda}}{\bm{x}}_{i}\|_{2}^{2}$
$\displaystyle={}$
$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{p}}\frac{1}{d}\|{\bm{E}}^{1/2}{\bm{x}}_{i}\alpha_{i}+{\bm{E}}^{1/2}{\bm{X}}_{\sim
i}{\bm{\alpha}}_{\sim i}-{\bm{E}}^{-1/2}{\bm{\Lambda}}{\bm{x}}_{i}\|_{2}^{2}$
$\displaystyle={}$
$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\frac{1}{d}\|{\bm{E}}^{1/2}{\bm{X}}_{\sim
i}{\bm{\alpha}}_{\sim
i}+(\alpha_{i}{\bm{E}}^{1/2}-{\bm{E}}^{-1/2}{\bm{\Lambda}}){\bm{x}}_{i}\|_{2}^{2}$
$\displaystyle={}$
$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{{\bm{v}}\in\mathbb{R}^{n}}\frac{2}{d}\left({\bm{v}}^{\top}(\alpha_{i}{\bm{E}}^{1/2}-{\bm{E}}^{-1/2}{\bm{\Lambda}}){\bm{x}}_{i}+{\bm{v}}^{\top}{\bm{E}}^{1/2}{\bm{X}}_{\sim
i}{\bm{\alpha}}_{\sim i}-\frac{1}{2}\|{\bm{v}}\|_{2}^{2}\right)\,,$ (22)

where in the last step we used the identity
$\max_{{\bm{v}}}({\bm{v}}^{\top}{\bm{x}}-\|{\bm{v}}\|^{2}/2)=\|{\bm{x}}\|^{2}/2$
for any vector ${\bm{x}}$.

We next note that ${\bm{S}}{\bm{S}}^{\top}={\bm{I}}$ since the bags are non-
overlapping. Therefore we can write
${\bm{S}}^{\top}{\bm{S}}={\bm{U}}{\bm{U}}^{\top}$ for an orthogonal matrix
${\bm{U}}\in{\mathbb{R}}^{n\times m}$. We then have

${\bm{E}}:=\rho{\bm{I}}+(1-\rho){\bm{S}}^{\top}{\bm{S}}={\bm{U}}{\bm{U}}^{\top}+\rho{\bm{U}}_{\perp}{\bm{U}}_{\perp}^{\top}\,,\quad{\bm{\Lambda}}=\rho({\bm{I}}-{\bm{S}}^{\top}{\bm{S}})=\rho{\bm{U}}_{\perp}{\bm{U}}_{\perp}^{\top}.$

where ${\bm{U}}_{\perp}$ is an orthogonal matrix representing the orthogonal
space to the column space of ${\bm{U}}$. We next decompose the vector
${\bm{v}}$ in the above optimization as
${\bm{v}}={\bm{U}}{\bm{v}}_{1}+{\bm{U}}_{\perp}{\bm{v}}_{2}$ and therefore
$\|{\bm{v}}\|^{2}=\|{\bm{v}}_{1}\|^{2}+\|{\bm{v}}_{2}\|^{2}$.

We introduce the change of variable $\tilde{{\bm{v}}}={\bm{E}}^{1/2}{\bm{v}}$
in optimization (22). Note that
$\tilde{{\bm{v}}}={\bm{U}}{\bm{v}}_{1}+\sqrt{\rho}{\bm{U}}_{\perp}{\bm{v}}_{2}$.
Continuing with (22) in terms of $\tilde{{\bm{v}}}$ we have

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{\tilde{{\bm{v}}}\in\mathbb{R}^{n}}\frac{2}{d}\left(\tilde{{\bm{v}}}^{\top}(\alpha_{i}{\bm{I}}-{\bm{E}}^{-1}{\bm{\Lambda}}){\bm{x}}_{i}+\tilde{{\bm{v}}}^{\top}{\bm{X}}_{\sim
i}{\bm{\alpha}}_{\sim
i}-\frac{1}{2}\|{\bm{E}}^{-1/2}\tilde{{\bm{v}}}\|_{2}^{2}\right)\,.$ (23)

To analyze the asymptotic behavior of the solution to the above minimax
optimization, we use the Convex-Gaussian-Minimax-Theorem (CGMT) (Thrampoulidis
et al., 2015, Theorem 3), which is a power extension of the classical Gordon’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:

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{\tilde{{\bm{v}}}\in\mathbb{R}^{n}}\frac{2}{d}\left(\tilde{{\bm{v}}}^{\top}(\alpha_{i}{\bm{I}}-{\bm{E}}^{-1}{\bm{\Lambda}}){\bm{x}}_{i}+\|{\bm{\alpha}}_{\sim
i}\|\tilde{{\bm{v}}}^{\top}{\bm{g}}+\|\tilde{{\bm{v}}}\|{\bm{h}}^{\top}{\bm{\alpha}}_{\sim
i}-\frac{1}{2}\|{\bm{E}}^{-1/2}\tilde{{\bm{v}}}\|_{2}^{2}\right)\,,$ (24)

with ${\bm{g}}\sim N(0,{\bm{I}}_{n})$ and ${\bm{h}}\sim N(0,{\bm{I}}_{d-1})$
independent Gaussian vectors. We next write the above optimization in terms of
the components ${\bm{v}}_{1}$ and ${\bm{v}}_{2}$, noting that
${\bm{E}}^{-1}{\bm{\Lambda}}={\bm{U}}_{\perp}{\bm{U}}_{\perp}^{\top}$, as
follows:

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{{\bm{v}}_{1},{\bm{v}}_{2}\in\mathbb{R}^{n}}\frac{2}{d}\Big{(}$
$\displaystyle\alpha_{i}{\bm{v}}_{1}^{\top}{\bm{U}}^{\top}{\bm{x}}_{i}+\sqrt{\rho}{\bm{v}}_{2}^{\top}{\bm{U}}_{\perp}^{\top}(\alpha_{i}{\bm{I}}-{\bm{U}}_{\perp}{\bm{U}}_{\perp}^{\top}){\bm{x}}_{i}+\|{\bm{\alpha}}_{\sim
i}\|({\bm{v}}_{1}^{\top}{\bm{U}}^{\top}{\bm{g}}+\sqrt{\rho}{\bm{v}}_{2}^{\top}{\bm{U}}_{\perp}^{\top}{\bm{g}})$
$\displaystyle+\sqrt{\|{\bm{v}}_{1}\|^{2}+\rho\|{\bm{v}}_{2}\|^{2}}{\bm{h}}^{\top}{\bm{\alpha}}_{\sim
i}-\frac{1}{2}\|{\bm{v}}_{1}\|^{2}-\frac{1}{2}\|{\bm{v}}_{2}\|^{2}\Big{)}\,.$
(25)

Define the shorthand

$\displaystyle{\bm{x}}_{1}$ $\displaystyle:={\bm{U}}^{\top}{\bm{x}}_{i}\sim
N(0,{\bm{I}}_{m}),$ $\displaystyle{\bm{x}}_{2}$
$\displaystyle:={\bm{U}}_{\perp}^{\top}{\bm{x}}_{i}\sim N(0,{\bm{I}}_{n-m}),$
$\displaystyle{\bm{g}}_{1}$ $\displaystyle:={\bm{U}}^{\top}{\bm{g}}\sim
N(0,{\bm{I}}_{m}),$ $\displaystyle{\bm{g}}_{2}$
$\displaystyle:={\bm{U}}_{\perp}^{\top}{\bm{g}}\sim N(0,{\bm{I}}_{n-m}).$

Then optimization (25) can be rewritten as

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{{\bm{v}}_{1},{\bm{v}}_{2}\in\mathbb{R}^{n}}\frac{2}{d}\Big{(}$
$\displaystyle\alpha_{i}{\bm{v}}_{1}^{\top}{\bm{x}}_{1}+\sqrt{\rho}(\alpha_{i}-1){\bm{v}}_{2}^{\top}{\bm{x}}_{2}+\|{\bm{\alpha}}_{\sim
i}\|({\bm{v}}_{1}^{\top}{\bm{g}}_{1}+\sqrt{\rho}{\bm{v}}_{2}^{\top}{\bm{g}}_{2})$
$\displaystyle+\sqrt{\|{\bm{v}}_{1}\|^{2}+\rho\|{\bm{v}}_{2}\|^{2}}{\bm{h}}^{\top}{\bm{\alpha}}_{\sim
i}-\frac{1}{2}\|{\bm{v}}_{1}\|^{2}-\frac{1}{2}\|{\bm{v}}_{2}\|^{2}\Big{)}\,.$
(26)

We fix $\|{\bm{v}}_{1}\|=\beta_{1}$ and $\|{\bm{v}}_{2}\|=\beta_{2}$ and first
optimize over the directions of ${\bm{v}}_{1}$, ${\bm{v}}_{2}$ and then over
the norms $\beta_{1}$ and $\beta_{2}$. This brings us to

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{\beta_{1},\beta_{2}\geq
0}\frac{2}{d}\Big{(}$
$\displaystyle\beta_{1}\|\alpha_{i}{\bm{x}}_{1}+\|{\bm{\alpha}}_{\sim
i}\|{\bm{g}}_{1}\|+\beta_{2}\|\sqrt{\rho}(\alpha_{i}-1){\bm{x}}_{2}+\|{\bm{\alpha}}_{\sim
i}\|\sqrt{\rho}{\bm{g}}_{2}\|$
$\displaystyle+\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}{\bm{h}}^{\top}{\bm{\alpha}}_{\sim
i}-\frac{1}{2}\beta_{1}^{2}-\frac{1}{2}\beta_{2}^{2}\Big{)}\,.$ (27)

In order to optimize over ${\bm{\alpha}}_{\sim i}$, we first fix its norm to
$\eta:=\|{\bm{\alpha}}_{\sim i}\|$ and optimize over its direction, and then
optimize over $\eta$, which results in:

$\displaystyle\min_{\eta\geq 0,\alpha_{i}}\max_{\beta_{1},\beta_{2}\geq
0}\frac{2}{d}\Big{(}$
$\displaystyle\beta_{1}\|\alpha_{i}{\bm{x}}_{1}+\eta{\bm{g}}_{1}\|+\beta_{2}\|\sqrt{\rho}(\alpha_{i}-1){\bm{x}}_{2}+\eta\sqrt{\rho}{\bm{g}}_{2}\|$
$\displaystyle+\eta\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}\|{\bm{h}}\|-\frac{1}{2}\beta_{1}^{2}-\frac{1}{2}\beta_{2}^{2}\Big{)}\,.$
(28)

The next step in the CGMT framework is to compute the pointwise limit of the
objective functions. Using the concentration of Lipschitz functions of
Gaussian vectors we have

$\displaystyle\frac{1}{\sqrt{d}}\|\alpha_{i}{\bm{x}}_{1}+\eta{\bm{g}}_{1}\|$
$\displaystyle\stackrel{{\scriptstyle(p)}}{{\to}}\sqrt{(\alpha_{i}^{2}+\eta^{2})\frac{\psi}{k}}\,,$
$\displaystyle\frac{1}{\sqrt{d}}\|\sqrt{\rho}(\alpha_{i}-1){\bm{x}}_{2}+\eta\sqrt{\rho}{\bm{g}}_{2}\|$
$\displaystyle\stackrel{{\scriptstyle(p)}}{{\to}}\sqrt{(\rho(\alpha_{i}-1)^{2}+\rho\eta^{2})\psi\Big{(}1-\frac{1}{k}\Big{)}}\,,$

where we used Assumption 2.3, by which $n/d\to\psi$ and $m=n/k$.

We also have
$\frac{1}{\sqrt{d}}\|{\bm{h}}\|\stackrel{{\scriptstyle(p)}}{{\to}}1$.

We therefore arrive at the following deterministic optimization problem

$\displaystyle\min_{\eta\geq 0,\alpha_{i}}\max_{\beta_{1},\beta_{2}\geq
0}\Big{(}$
$\displaystyle\beta_{1}\sqrt{(\alpha_{i}^{2}+\eta^{2})\frac{\psi}{k}}+\beta_{2}\sqrt{(\rho(\alpha_{i}-1)^{2}+\rho\eta^{2})\psi\Big{(}1-\frac{1}{k}\Big{)}}$
$\displaystyle+\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}-\frac{1}{2}\beta_{1}^{2}-\frac{1}{2}\beta_{2}^{2}\Big{)}\,,$
(29)

where we made the change of variables $2\beta_{1}/\sqrt{d}\to\beta_{1}$ and
$2\beta_{2}/\sqrt{d}\to\beta_{2}$.

By writing the stationary conditions for the above optimization, and
simplifying the resulting system of equations by solving for $\beta_{1}$,
$\beta_{2}$, and substituting for them in the other two equations, we arrive
at the following two equations for $\alpha_{i}$ and $\eta$:

$\displaystyle\begin{cases}\rho+\frac{\psi}{k(1-\alpha_{*})}-1=\frac{\psi}{k\alpha_{*}}\rho(k-1)\\\
\eta_{*}^{2}+\frac{k\alpha_{*}^{2}}{k-1}+\frac{\eta_{*}^{2}\alpha_{*}^{2}}{(1-\alpha_{*})^{2}(k-1)}=\frac{\psi}{k}\frac{\eta_{*}^{2}}{(1-\alpha_{*})^{2}}\,.\end{cases}$

As the final step, recall that by definition $\eta:=\|{\bm{\alpha}}_{\sim
i}\|$ and therefore,
$\|{\bm{\alpha}}_{i}\|^{2}\stackrel{{\scriptstyle(p)}}{{\to}}\alpha_{*}^{2}+\eta_{*}^{2}$.
As we see it is independent of the index $i$ and therefore,

$\frac{1}{d}\|{\bm{M}}{\bm{\Lambda}}{\bm{X}}\|^{2}=\frac{1}{d}\sum_{i=1}^{d}\|{\bm{M}}{\bm{\Lambda}}{\bm{x}}_{i}\|^{2}=\frac{1}{d}\sum_{i=1}^{d}\alpha_{i}^{2}\stackrel{{\scriptstyle(p)}}{{\to}}\alpha_{*}^{2}+\eta_{*}^{2}\,.$

This completes the proof.

###  D.2 Proof of Lemma B.2

Recall that ${\bm{M}}=({\bm{X}}^{\top}{\bm{E}}{\bm{X}})^{-1}{\bm{X}}^{\top}$.
Consider the following optimization problem:

$\displaystyle{\bm{\alpha}}=\operatorname{arg\,min}_{{\bm{\alpha}}\in\mathbb{R}^{d}}\frac{1}{d}\|{\bm{E}}^{1/2}{\bm{X}}{\bm{\alpha}}-{\bm{E}}^{-1/2}{\bm{U}}{\bm{a}}\|_{2}^{2}\,.$
(30)

The solution to the above optimization problem has a closed-form solution
given by
${\bm{\alpha}}=({\bm{X}}^{\top}{\bm{E}}{\bm{X}})^{-1}{\bm{X}}^{\top}{\bm{U}}{\bm{a}}={\bm{M}}{\bm{U}}{\bm{a}}$.
So we are interested in characterizing the norm of the optimal solution to the
above optimization problem.

Similar to the proof of Lemma B.1, we use the framework of CGMT to
characterize $\|{\bm{\alpha}}\|$ in the asymptotic regime described in
Assumption 2.3.

Using the identity
$\|{\bm{x}}\|/2=\max_{{\bm{v}}}({\bm{v}}^{\top}{\bm{x}}-\|{\bm{v}}\|^{2}/2)$,
we rewrite the above optimization as:

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\frac{1}{d}\|{\bm{E}}^{1/2}{\bm{X}}{\bm{\alpha}}-{\bm{E}}^{-1/2}{\bm{U}}{\bm{a}}\|_{2}^{2}$
$\displaystyle={}\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{{\bm{v}}\in\mathbb{R}^{n}}\frac{2}{d}\left({\bm{v}}^{\top}{\bm{E}}^{1/2}{\bm{X}}{\bm{\alpha}}-{\bm{v}}^{\top}{\bm{E}}^{-1/2}{\bm{U}}{\bm{a}}-\frac{1}{2}\|{\bm{v}}\|_{2}^{2}\right)\,,$
(31)

By using Convex-Gaussian-Minimax-Theorem (Thrampoulidis et al., 2015, Theorem
3), the above optimization is equivalent to the following auxiliary
optimization problem:

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{{\bm{v}}\in\mathbb{R}^{n}}\frac{2}{d}\left(\|{\bm{\alpha}}\|{\bm{v}}^{\top}{\bm{E}}^{1/2}{\bm{g}}+\|{\bm{E}}^{1/2}{\bm{v}}\|{\bm{h}}^{\top}{\bm{\alpha}}-{\bm{v}}^{\top}{\bm{E}}^{-1/2}{\bm{U}}{\bm{a}}-\frac{1}{2}\|{\bm{v}}\|_{2}^{2}\right)\,,$
(32)

with ${\bm{g}}\sim N(0,{\bm{I}}_{n})$ and ${\bm{h}}\sim N(0,{\bm{I}}_{d})$
independent Gaussian vectors.

We also recall that ${\bm{S}}^{\top}{\bm{S}}={\bm{U}}{\bm{U}}^{\top}$ and so

${\bm{E}}:=\rho{\bm{I}}+(1-\rho){\bm{S}}^{\top}{\bm{S}}={\bm{U}}{\bm{U}}^{\top}+\rho{\bm{U}}_{\perp}{\bm{U}}_{\perp}^{\top}\,,$

with ${\bm{U}}_{\perp}\in{\mathbb{R}}^{n\times(n-m)}$ denotes the orthogonal
matrix, whose column space is orthogonal to the column space of ${\bm{U}}$. We
decompose ${\bm{v}}$ to its component in the column space of ${\bm{U}}$ and
${\bm{U}}_{\perp}$ as

${\bm{v}}={\bm{U}}{\bm{v}}_{1}+{\bm{U}}_{\perp}{\bm{v}}_{2},\quad\|{\bm{v}}\|^{2}=\|{\bm{v}}_{1}\|^{2}+\|{\bm{v}}_{2}\|^{2}\,.$

Therefore,
${\bm{E}}^{1/2}{\bm{v}}={\bm{U}}{\bm{v}}_{1}+\sqrt{\rho}{\bm{U}}_{\perp}{\bm{v}}_{2}$
and so the above optimization (32) can be written as

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{{\bm{v}}_{1},{\bm{v}}_{2}\in\mathbb{R}^{n}}\frac{2}{d}\Big{(}$
$\displaystyle\|{\bm{\alpha}}\|{\bm{v}}_{1}^{\top}{\bm{U}}^{\top}{\bm{g}}+\sqrt{\rho}\|{\bm{\alpha}}\|{\bm{v}}_{2}^{\top}{\bm{U}}_{\perp}^{\top}{\bm{g}}+\sqrt{\|{\bm{v}}_{1}\|^{2}+\rho\|{\bm{v}}_{2}\|^{2}}{\bm{h}}^{\top}{\bm{\alpha}}$
$\displaystyle-{\bm{v}}_{1}^{\top}{\bm{a}}-\frac{1}{2}\|{\bm{v}}_{1}\|^{2}-\frac{1}{2}\|{\bm{v}}_{2}\|^{2}\Big{)}\,.$
(33)

We next introduce the following change of variables:

$\displaystyle{\bm{g}}_{1}$ $\displaystyle:={\bm{U}}^{\top}{\bm{g}}\sim
N(0,{\bm{I}}_{m}),$ $\displaystyle{\bm{g}}_{2}$
$\displaystyle:={\bm{U}}_{\perp}^{\top}{\bm{g}}\sim N(0,{\bm{I}}_{n-m}).$

Rewriting the optimization in terms of ${\bm{g}}_{1}$ and ${\bm{g}}_{2}$ we
get

$\displaystyle\min_{{\bm{\alpha}}\in\mathbb{R}^{d}}\max_{{\bm{v}}_{1},{\bm{v}}_{2}\in\mathbb{R}^{n}}\frac{2}{d}\Big{(}$
$\displaystyle\|{\bm{\alpha}}\|{\bm{v}}_{1}^{\top}{\bm{g}}_{1}+\sqrt{\rho}\|{\bm{\alpha}}\|{\bm{v}}_{2}^{\top}{\bm{g}}_{2}+\sqrt{\|{\bm{v}}_{1}\|^{2}+\rho\|{\bm{v}}_{2}\|^{2}}{\bm{h}}^{\top}{\bm{\alpha}}$
$\displaystyle-{\bm{v}}_{1}^{\top}{\bm{a}}-\frac{1}{2}\|{\bm{v}}_{1}\|^{2}-\frac{1}{2}\|{\bm{v}}_{2}\|^{2}\Big{)}\,.$
(34)

We next do the maximization on ${\bm{v}}_{1}$ and ${\bm{v}}_{2}$ by first
fixing the norms to $\beta_{1}:=\|{\bm{v}}_{1}\|$ and
$\beta_{2}:=\|{\bm{v}}_{2}\|$ and maximize over the directions and then
maximize over $\beta_{1}$, $\beta_{2}$. This gives us

$\displaystyle\min_{{\bm{\alpha}}\in{\mathbb{R}}^{d}}\max_{\beta_{1},\beta_{2}\geq
0}\frac{2}{d}\Big{(}$
$\displaystyle\beta_{1}\|\|{\bm{\alpha}}\|{\bm{g}}_{1}-{\bm{a}}\|+\beta_{2}\sqrt{\rho}\|{\bm{\alpha}}\|\|{\bm{g}}_{2}\|+\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}{\bm{h}}^{\top}{\bm{\alpha}}-\frac{\beta_{1}^{2}+\beta_{2}^{2}}{2}\Big{)}\,.$
(35)

For minimization over ${\bm{\alpha}}$, we first fix its norm to
$\eta:=\|{\bm{\alpha}}\|$ and optimize over its direction, and then over
$\eta$:

$\displaystyle\min_{\eta\geq 0}\max_{\beta_{1},\beta_{2}\geq
0}\frac{2}{d}\Big{(}$
$\displaystyle\beta_{1}\|\eta{\bm{g}}_{1}-{\bm{a}}\|+\beta_{2}\sqrt{\rho}\eta\|{\bm{g}}_{2}\|-\eta\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}\;\|{\bm{h}}\|-\frac{\beta_{1}^{2}+\beta_{2}^{2}}{2}\Big{)}\,.$
(36)

The next step in the CGMT framework is to compute the pointwise limit of the
objective function. By concentration of Lipschitz functions of Gaussian
vectors we have

$\displaystyle\frac{1}{\sqrt{d}}\|\eta{\bm{g}}_{1}-{\bm{a}}\|$
$\displaystyle\stackrel{{\scriptstyle(p)}}{{\to}}\sqrt{\frac{\|{\bm{a}}\|^{2}}{d}+\eta^{2}\frac{\psi}{k}}\,,$
$\displaystyle\frac{1}{\sqrt{d}}\|{\bm{g}}_{2}\|$
$\displaystyle\stackrel{{\scriptstyle(p)}}{{\to}}\sqrt{\psi\Big{(}1-\frac{1}{k}\Big{)}},$
$\displaystyle\frac{1}{\sqrt{d}}\|{\bm{h}}\|$
$\displaystyle\stackrel{{\scriptstyle(p)}}{{\to}}1\,,$

where we used Assumption 2.3 by which $n/d\to\psi$, and Assumption 2.4 by
which $m=n/k$. Using these limits in (36), we arrive at the following
deterministic optimization problem:

$\displaystyle\min_{\eta\geq 0}\max_{\beta_{1},\beta_{2}\geq
0}\beta_{1}\sqrt{\frac{\|{\bm{a}}\|^{2}}{d}+\eta^{2}\frac{\psi}{k}}+\beta_{2}\sqrt{\rho}\eta\sqrt{\psi\Big{(}1-\frac{1}{k}\Big{)}}-\eta\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}\;-\frac{\beta_{1}^{2}+\beta_{2}^{2}}{2}\,,$
(37)

where we applied the change of variables $2\beta_{1}/\sqrt{d}\to\beta_{1}$ and
$2\beta_{2}/\sqrt{d}\to\beta_{2}$.

In order to find the optimal solution we solve the stationary conditions. By
setting derivative with respect to $\eta$ to zero we obtain

$\displaystyle\frac{\beta_{1}\eta\frac{\psi}{k}}{\sqrt{\frac{\|{\bm{a}}\|^{2}}{d}+\eta^{2}\frac{\psi}{k}}}+\eta\sqrt{\rho\psi\Big{(}1-\frac{1}{k}\Big{)}}-\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}=0\,.$
(38)

In addition by setting the derivative with respect to $\beta_{1}$ and
$\beta_{2}$ to zero, we obtain

$\displaystyle\begin{split}\sqrt{\frac{\|{\bm{a}}\|^{2}}{d}+\eta^{2}\frac{\psi}{k}}&=\Big{(}\frac{\eta}{\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}}+1\Big{)}\beta_{1}\,,\\\
\eta\sqrt{\rho\psi\Big{(}1-\frac{1}{k}\Big{)}}&=\Big{(}\frac{\rho\eta}{\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}}+1\Big{)}\beta_{2}\,.\end{split}$
(39)

By substituting for $\beta_{1}$ and $\beta_{2}$ from (39) into (38) we get

$\displaystyle\frac{\eta\frac{\psi}{k}}{\eta+c}-1+\frac{\rho\eta\psi(1-\frac{1}{k})}{\rho\eta+c}=0\,,$
(40)

where $c=\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}$.

Also by substituting for $\beta_{1}$ and $\beta_{2}$ from (39) into the
definition $c=\sqrt{\beta_{1}^{2}+\rho\beta_{2}^{2}}$, we have

$\displaystyle\frac{\frac{\|{\bm{a}}\|^{2}}{d}+\eta^{2}\frac{\psi}{k}}{(\eta+c)^{2}}+\frac{\rho^{2}\eta^{2}\psi(1-\frac{1}{k})}{(\rho\eta+c)^{2}}=1\,.$
(41)

We next make the change of variable: $c=\eta u$, and rewriting equations (40
and 41) as follows:

$\displaystyle\begin{cases}\frac{\psi}{1+u}+\frac{\rho\psi(k-1)}{\rho+u}&=k\,,\\\
\frac{\frac{k\|{\bm{a}}\|^{2}}{d\eta^{2}}+\psi}{(1+u)^{2}}+\frac{\rho^{2}\psi(k-1)}{(\rho+u)^{2}}&=k\,.\end{cases}$

Defining $v:=\frac{k\|{\bm{a}}\|^{2}}{\psi d\eta^{2}}$ we get the system of
equations given in the lemma statement.

As the final step, recall that as we discussed at the beginning of the proof,
${\bm{\alpha}}_{*}={\bm{M}}{\bm{U}}{\bm{a}}$. Therefore,

$\frac{n}{\|{\bm{a}}\|^{2}}\|{\bm{M}}{\bm{U}}{\bm{a}}\|_{2}^{2}=\frac{n}{\|{\bm{a}}\|^{2}}\|{\bm{\alpha}}_{*}\|_{2}^{2}\stackrel{{\scriptstyle(p)}}{{\to}}\frac{n}{\|{\bm{a}}\|^{2}}\eta_{*}^{2}=\frac{k}{v_{*}}\,,$

which completes the proof.