SPriFed-OMP: A Differentially Private Federated Learning Algorithm for Sparse Basis Recovery
Authors: Ajinkya K Mulay
Xiaojun Lin
Venue: Accepted by TMLR ()

Abstract: Sparse basis recovery is a classical and important statistical learning problem when the number of model dimensions $p$ is much larger than the number of samples $n$. However, there has been little work that studies sparse basis recovery in the Federated Learning (FL) setting, where the client data's differential privacy (DP) must also be simultaneously protected. In particular, the performance guarantees of existing DP-FL algorithms (such as DP-SGD) will degrade significantly when $p \gg n$, and thus, they will fail to learn the true underlying sparse model accurately. In this work, we develop a new differentially private sparse basis recovery algorithm for the FL setting, called SPriFed-OMP. SPriFed-OMP converts OMP (Orthogonal Matching Pursuit) to the FL setting. Further, it combines SMPC (secure multi-party computation) and DP to ensure that only a small amount of noise needs to be added in order to achieve differential privacy. As a result, SPriFed-OMP can efficiently recover the true sparse basis for a linear model with only $n = \mathcal{O}(\sqrt{p})$ samples. We further present an enhanced version of our approach, SPriFed-OMP-GRAD, based on gradient privatization, that improves the performance of SPriFed-OMP. Our theoretical analysis and empirical results demonstrate that both SPriFed-OMP and SPriFed-OMP-GRAD terminate in a small number of steps, and they significantly outperform the previous state-of-the-art DP-FL solutions in terms of the accuracy-privacy trade-off.

Published in Transactions on Machine Learning Research (06/2024)
SPriFed-OMP: A Differentially Private Federated Learning Algorithm for Sparse Basis Recovery
Ajinkya K Mulay
mulaySpurdue.cc edu
Elmore Fomily School of Electrical and Computer Engineering Purdue Universily
Xiaojun Lin
Trun@eenn.purduee edu
Elmore Family School Electrical and Computer Engineering Purdue University
Reviewed on OpenReview: https: // openreview. net/ pett/formm?ee id= Dsaure6gii))
Abstract
Sparse basis recovery is classical and important statistical learning problem when the number of model dimensions is much larger than the number of samples n. However, there has been little work that studies sparse basis recovery in the Federated Learning (FL) setting, where the client data's differential privacy (DP) must also be simultaneously protected. In particular, the performance guarantees existing DP-FL algorithms (such as DP-SGD) will degrade significantly when p n, and thus, they will fail to learn the true underlying sparse model accurately. In this work, we develop new differentially private sparse basis recovery algorithm for the FL setting, called SPriFed OMP. SPriFed OMP converts OMP (Orthogonal Matching Pursuit) to the FL setting. Further, it combines SMPC (secure multi-party computation) and DP to ensure that only a small amount of noise needs to be added in order to achieve differential privacy. As a result, SPriFed- OMP can efficiently recover the true sparse basis for a linear model with only n = =(vF) samples. We further present an enhanced version of our approach, SPriFed OMP-GRAD based on gradient privatization, that improves the performance of SPriFed-OMP. Our theoretical analysis and empirical results demonstrate that both SPriFed-OMh OMP and SPriFed-OMP. OMP-GRAD terminate in a small number of steps, and they significantly outperform the previous state-of-the-arl DP-FL solutions in terms of the accuracy-privant trade-off.
GRAD
1 Introduction
For many statistical learning applications, such as genomics and economics (Liang & Kelemen 2008 Clarke
et al. 2008 Belloni et al. 2014 Fan et al.) 2011). it is essential to deal with situations where the number of
samples (n) is significantly lower than the number of model parameters (p). Without additional constraints, such problems are ell-determined as there will be many models that can fit the same set of training samples. To address this issue, a popular approach is to assume some sparsity conditions on the desired model. Along this line, there have been significant advances compressed sensing techniques, such as LASSO (Zhao & Yu! 2006), [Meinshausen] 2007) Orthogonal Matching Pursuit (OMP) (Tropp al. (007), (Noodell & Tropp 2009 Forward- -ackwad- Algorithm (FoBA) (Zhang 2011) and Least Angles Regression (LARS) 2004), which leverage sparsity assumptions on the data to extract the true sparse basis of the underlying model. Once the sparse basis is identified, the sparse model can be estimated using standard learning techniques, as the problem is no longer ill-determined.
Efron et al.
However, the above methods usually assume that the training datasets are already hosted on a server and thus neglect the privacy of the users who generate the training data. Recently, Federated Learning (FL)
* Part of this work was completed when the second author moved The Chinese University of Hong Kong.

---

Published in Transactions on Machine Learning Research (06/2024)
[McMahan et al. 2017 has been proposed as standard approach to protect user privacy, which keeps user data at the clients during training. Specifically, the clients update the models on their data and only upload the new gradients to the parameter server. The server updates the model parameters based on the aggregated global gradient and then sends the new model parameters back to the clients, furthering the training process. Such iterations are repeated until the global model converges, with no need to upload the user data to the server. However, note that FL is insufficient for privacy protection because the client. gradients transmitted to the server may still leak information (Huang et al. 2021), (Geiping et al. 2020 Therefore, in the literature, Differential Privacy (DP) (Dwork et al., 2014) has also been introduced into FL. DP privatizes FL by adding noise to client gradients before uploading them to the parameter server. By adding appropriate noises, individual client gradients are hidden from the server and any external adversary while still enabling the learning of the global model. A notable example is DP-SGD, which can be applied to any SGD-based training algorithms and arbitrary loss functions (e.g., regularized objective functions in LASSO).
Unfortunately, this DP-FL pipeline is poor fit. for training sparse models when the number of training samples (n) is significantly below the number of model parameters (p). For ease of discussion, in this paper, we assume that each elient contains single training sample. Therefore, in our analysis, the number of clients equals the number of samples. Note that, intuitively, the gradient uploaded by each client has p elements, one for each model parameter. For DP to achieve the desirable privacy guarantee, we usually need to add noise to the gradients with variance proportional to the model dimensions (woork et al.) 2014). Thus, when p > n, the noise required in the DP-FL setting can completely overwhelm the signal and thus prevent the recovery of the correct sparse basis. We refer to this problem the curse-of-dimensionne
for DP-FT.
In particular, for DP-SGD (Abadi et al. 2016), even when it is applied to Lipschitz loss functions, the empirical risk is of the order O(H) (Theorem 2.4 in Bassily et al. (2014)). When >> n, even though one can apply DP-SGD to a sparse-solution-seeknn objective, such as LASSO, it will not produce accurate answers. Other DP-FL algorithms, such as objective perturbation (Kifer et al. 2012 have similar issues. For example, the empirical loss of the objective perturbation mechanism in Kifer et al. (002) is of the order O(2") (sce Theorems 4.1-4.2 and 5 in Kifer et al. )2 which will also lail to produce accurate sparse models when p > n. Thus, developing DP-FL algorithms that can attain provable sparse recovery under high- nigh-dimensional settings remains an open question. We note that if we do not consider the FL setting, there are DP solutions in the literature for sparse recovery under high dimension (Thakurta & Smith 2013 Talwar et al. 2015 However, these algorithus assume full data access al the server and thus fail to work in the FL setting (where data are kept at the client for privacy).
In this work, we develop new sparsc-rocovery algorithm specifically for the DP-FL setting, which, under suitable conditions, can ensure DP for data al the clients and recover the true sparse basis even when p n. Specifically, our new algorithm called SPriFed OMP (Sparse Private Federated OMP), is based on Orthogonal Matching Pursuit (OMP) (Tropp et al.) 2007). At each iteration, OMP picks one basis with the highest correlation with the target, subtracts the contribution of this basis from the target, and continues to search for the next basis with the highest correlation with the residual until a given number s of sparse basis is identified. However, the standard OMP (Tropp et al.] (007) is not designed for the FL setting, nor does it ensure DP. We augment OMP with noisy SMPC (secure multi-party computation) algorithm (Bonawitz) et al. 2017 Kairouz et al. 2021) that only smaller amount of noise is added to the aggregate correlation, which ensures DP. In some steps, e.g., to compare the correlation with the target across all bases, this noise is still in order O(vP). However, we only need to perform such steps 8 times, which is usually much smaller than the number of iterations for DP-SGD to converge. As a result, the overall amount of noise will be much smaller. Our careful analysis shows that, as long as n O(v)), our algorithm will be able to recover the true sparse basis with high probability under the similar assumption of Restricted Isometry Property (RIP) as in standard OMP. While this general idea is quite intuitive, the detailed design of SPriFed-OMP also matters lot. Indeed, we present two versions of SPriFed- OMP. In the first version, we privatize the individual correlations (feature and feature-residual correlations) to compute the total feature-residual correlation in each step. This version introduces our first enhancement that specifically adds lower order noise to the selected basis elements. Lower order noise enables lower sample size requirement for sparse basis recovery
'Qur analysis can be easily extended to multiple samples per client by the group privacy notion discussed in Section 2
2

---

Published in Transactions on Machine Learning Research (06/2024)
while also incurring lower test error as we will see in Section Next, we identify simplified second version of (PriFed-OMP that introduces our second enhancement based on gradient privatization. We will see in the experimental section (Section 7 that adding noise to the gradient is much more advantageous under clipping than adding noise to correlations. Furthermore, for both methods, we can quantify the estimation
error (Theorem 9) and the empirical risk (Theorem 10: to be on the order of o(V s log(s) and O x llg(s))
respectively which are in the same order as the traditional non-private Ordinary Least Squares (OLS) estimate that already assumes knowledge of the correct sparse basis.
1.1 Related Work
In the literature, we have two major categories for private sparse learning: (1) The sparse learning methods that only work in the central DP setting (f.e., where the data can be sent to the server non-privately and only the server privatizes the output) and, (2) the learning methods that are either directly DP-FL compatible or can be adapted to be suitable for the DP-FL setting. We note that not all of these methods can provide basis recovery guarantecs (some of them only guarantees empirical risks). Below, we discuss the related work in each category.
Central DP compatible sparse learning methods: The recent sparse methods in Asi et al. 2021 1
Bassily et al. (2021) have empirical risk that holds for n O(VP) samples under the RSC constraint. However, both of these methods require centralized data access due to their unique sampling requirements and certain non-private mechanisms, and thus, they are not suitable for the DP-FI. domain.
DP-FL compatible sparse learning methods: As we discussed earlier, DP-SGD is not designed for the p> setting or exploiting sparsity. Amongst the DP-FL sparse learning methods, the work of Kifer et al. (2022) is most closely related to ours. Although the method proposed in Kifer et al. (2012) is not geared toward the DP-FL setting, the Samp-Agg algorithm can be adapted to the DP-FL setting. However, support recovery in Kifer el al. (2012) requires that each client's 's data matrix individually satisfies the Restricted Strong Convexity (RSC) [Zhang 2011) assumption. In contrast, the RIP assumption in our proposed solution is considerably weaker, as it only needs to hold over the entire training set across all clients. Thus, our solution can apply to a larger set of scenarios. There are two other related work that aim at the DP-FL and > n setting. Mangold et al. (2023) recently proposed a mechanism that has an empirical risk that holds for n = O(vp) samples under the RSC constraint. We note that Mangold et al. (023) is only studied for the contralized DP sctting. Still, the algorithm can be appropriately adjusted for the DP-FL setting with the Gaussian noise? 2 However, their analysis lacks a sparse basis recovery guarantee, and thus is unclear whether their methods can find the underlying true basis. Furthermore, their empirical risk values cannot avoid the polynomial dependency on p. WWng & Xul (2019) also considers the problem of estimating sparse models under the p >> n scenario and where noise is directly added to the client communication to the server to preserve DP. They provide two algorithmic results. The first result applies to the p >> n case, but it studies the privacy scenarios where only the response vector y must be private. The measurement matrix X has no privacy protection. When the matrix X must also be protected, their second result still requires n = O(p) (ignoring the logarithmic terms). Thus, our proposed algorithms provide better privacy guarantees with fewer samples. In a similar sense, the private hard-thresholding methods proposod in Wang & Gu (2019): Hu ct al. (2022) either do not recover the sparse models or require Opp) samples for convergence.
Noisy OMP: Finally, our analysis of the noisy version of OMP is also related to (Chen & Caramanis 2012), which studies how adding noise to the measurement matrix X will impact the accuracy of OMP. However, their analysis does not apply to the DP or the DP-FL cases as it does not privatize the response vector y. Furthermore, they directly add noise to the measurement matrix X. As a result, the noise level needed for ensuring DP for the matrix X would have had to be at least ypn, which is higher than our solution's. Specifically, our solution adds noise to the correlation between each basis and the target. Further, by employing Noisy-SMPC (Algorithm 1) the level of noise added is only of the order vps. Thus, new analysis is needed to study our improved DP and accuracy guarantees.
We provide a modiffel/enhancee DP-FL version of Algorithm in Mangold et 2023 for comparison in the form of Algorithm
3

---

Published in Transactions on Machine Learning Research (06/2024)
The rest of the paper is structured as follows. Section presents the system model and provides brief overview of differential privacy and the goal of compressed sensing. In Section 3 we provide the details of our proposed algorithm SPriFed-OMP and its other variant SPrIFed-OMP--RRAD Sections 4 and P provide a thorough utility-privacy analysis of our proposed implementation. Section the core result. Section 7 provides empirical results. Then, we conclude. Complete prools and supporting results are omitted due to the page limits.
6 provides an intuitive sketch of
2 System Model
We assume that the ground truth model y zQ+ E, where as E R2 is the underlying model parameter that we wish to recover, RP (a vector) and y E R are the input-output pair, and c < (O, of) R is an additive error. We assumee that this ground-truth model is sparse that ag has at most non-zero elements, Le., ||a=|lo & We now consider n inpul-ou(pat training pairs represented by (æa, D:), (1,..., ......,] where each pair belongs to a single distinct client. F We stack the row vectors vertically together to form an n X p matrix X. Similarly, we stack yi into an n x 1 vector y. We emphasize that the server does not have the entire data, so we need to study a federated learning setting (McMahan et al. 2017).
Any DP-FL algorithm iterates over n distributed clients over steps t I,... T. For each step t, the 7th client transmits message mi,t; computed
function of the client dataset and any information it receives from the server plus possibly additionall randomness. At the end of the T-th iteration, the server aims to recover Or, (likely with some error). Let us use M to denote such a distributed and randomized mechanism. We aim to ensure Differential Privacy (DP) for the clients, and hence we present the Differential Privacy (DP) definition for . below.
Definition 2.1. [Approzimate Distributed Differential Privacy] For any two neighboring distributed datasets X,X' e Raxp differing in one of their clients and the corresponding data-pairs (i.c., they only differ in the dala-poir for one client k E (l,...,n)) Let M(X) and M(X') be the oulpuls when M operates on X and X' respectively. We say that the randomized and distributed mechanism M is (c, differentially private if, for any set R
E P
Next, we introduce essential assumptions relevant to our system model. Recall that the goal of the server is to estimate the sparse model parameter as without access to the client data. Even without the DP requirement, recovering the true sparse model typically requires additional assumptions on the data matrix (Zhang) 2009) Candes & Tao 2005). Below, in assumption 1 we describe the Restricted Isometry Property (RIP), which is usually required for OMP (Candes & Tao 2005 which our proposed algorithm is based on.
Assumption 1. Restricted Isometry Property (RIP): A measurement matrir X E RRap is said to satisfy RIP of order-K if there exists a constant Ç [0, 1] such that,
(1 (1-6)leel < || & (1 +llbB
for all vectors v E R/P.///loo & K. Note that Ç is referred to as the isometric constant. Furthermore, the Restricted Isometry Constant (RIC) is defined as the infimam of all possible Ç values that satisfy RIP of order-K for given measurement matrix X E Raxp_ In other words, assuming that the RIP of order K is satisfied, the corresponding RIC is given by,
SK infe infe 111111 & X & (1+ 1
for all u RP, 1/00/0 < K]
Thhis assumption be casily relaxed to allow more than training pair per client performing the privacy analysis with group privacy. As long as the samples of each clicnt are cousidcrably lower than n, the group privacy cost will be small. If client holds a large number of samples, we could consider limiting the maximum number of samples per client in each iteration of algorithm upper bound our privacy costs.
4

---

Published in Transactions on Machine Learning Research (06/2024)
We acknowledge that RIP is more restrictive condition than other related conditions in the compressed- sensing literature, such as the Restricted Strong Convexity from Jalali et al. (2011) and Zhang 2009 or the Positive Cone Condition from Efron et al. (2004). However, even under this RIP assumption, no solution cxists in the literature to attain DP in an FL setting and achieve exact support recovery with the number of samples much smaller than the model dimension. Thus, our contribution under the RIP assumptior still represents a significant contribution. We will leave the study of other assumptions for future work.
We also make the following assumption, typical in the differential privacy literature (Dwork et al. 2014 Wang & Xu 2019)
Assumption 2. (Bounded data matrix and response] We assume that the elements in the measurement malriz X and its response y are bounded by scolars XM and yM respectively.
The boundedness of malrix or vector elements can be easily achieved by clipping the values to particular bounds. We can also easily maintain the original vector variance by re-scaling after clipping. Alternatively, if the underlying data distribution is light-tailed, we could leverage concentration bounds combined with the union bound to obtain realistic bound on the data values.
As discussed in section 1 the standard DP approaches of adding noise are highly ineffective for recovering sparse models when >> n. Thus, our paper aims to develop a mechanism that is both DP-FL and can recover the exact support with several samples much smaller than the total model dimension. Specifically, let & denote the estimated model parameter of our proposed DP-FL algorithm. Recall that a is the ground-truth model parameter with sparsity s. We wish to (1) Ensure that the support of & matches the true support with high probability, (2) Quantify the empirical risk AR n E (l=; y1)² (#;0ks site-vy)?? w²² and estimation error Aa + l|ā- such that both are small and do not blow up with large p.
3 The SPriFed-OMP Algorithm
Our primary goal in this work is to recover a sparse model given a high number of features and a few samples. Note that if we can guarantee exact sparse basis recovery, we only need to add noise to the output model with variance proportional to the model sparsity, which is a much easier goal to accomplish. Thus, below, we will first focus on the goal to identify the true sparse basis. The analysis for recovering ag with a small estimation error will then be presented later (see Theorems 9 and 10
Our proposed algorithu is based on OMP, a popular algorithu for exact sparse recovery without DP considerations. Below, we first describe the standard version of OMP. OMP iteratively selects a single new feature in each step. The feature with the absolute maximum correlation to the current residual is picked during each step. The residual is set to the model response y in the initial step. At cach subsequent step, the residual is updated by removing the newly picked feature's contribution from the response. OMP continues iterating until model of predetermined cinnension//parsitty s is selected.
Non-Private OMP:
Challenge to make OMP differentially private: Below, we explain the challenge to make OMP differentially private in the FL setting. First, when OMP computes the correlation of each basis with the residual and picks the basis with the highest correlation, it must be able to do so without direct access to the data on all clients. Second, when OMP subtracts the contribution of a new basis from the current residual, it needs the covariance of the existing basis. This must also be done without direct access to the data on all clients.
Both of these challenges can be overcome if we can differentially privately compute the correlation between two columns that spread across all clients. Further, the total number of such computations must be carefully controlled to limit the amount of noise added. This idea leads to our first version of SPriFed-OMP, which focuses on computing the correlations in a DP-FL manner. The server maintains the estimated model parameter à and is never released to the clients. (In contrast, the second version of SPriFed- OMP, which will be presented later, will release the privatized model parameter to the clients.)
Note that we do not specifically assume that the clients are homogeneous. Even if the clients heterogeneous, long as the RIP assumption ion holds, our analytical results in the paper will hold.
5

---

Published in Transactions on Machine Learning Research (06/2024)
Differentiall-PPrivtttt and Distributed Computation of Correlation Specifically, consider two columns of data =f and af spread across all clients E (1..... We now develop a mechanism so that the server can compute the sum _;-1 zf. For privacy, though, each client cannot disclose 2 directly. We can add noise directly to the client, which will lead to a noise level that is too high. In contrast, below, we use an approach that requires lower noise.
NoisySMPC: We use the NoisySMPC mechanism (Algorithm I that combines SMPC (Bonawitz et al, 2017] with much lower level of noise to ensure DP. This algorithm, which is distributed and satisfies DP, forms core component of our proposed SPriFed OMP algorithm. To achieve DDP (distributed and differentially private), NoisySMPC adds two levels of randomness. First, NoisySMPC modifies each client's 's contribution as f(0i, wi) f + 1 where 2i, Mi is the jth client's 's data-response pair and f computes a statistic such as the correlation between the client's data and response. The per-client noise 7 is added so that the total noise 7sum 2 7 at the server is sufficient to differentially privatize the sum of client. outputs. Second, NoisySMPC adds f(2f, 2²) across all clients through SMPC, which further protects the privacy of individual clients. This underlying SMPC mechanism allows the clients to sum their contributions f without disclosing any individual values. Examples of such SMPC mechanisms can be pair-wise client key sharing as described in (Bonawitz et al.) 2017) or the distributed discrete Gaussian (Kairouz et al. 2021 b. We refer the reader to the above literature for further details regarding SMPC and related mechanisms. NoisySMPC adds significantly lower variance noise to the sum (reduced by a factor of n), compared to privatizing each client's 's output individually, as shown in line 11 of the Algorithm D
We are now ready to present the complete SPriFed-OMii algorithm in the DP-FL setting. Algorithm contains the pseudocode. Recall that, for each step in OMP, we compute, for all features, the correlation of the feature column and the residual. For the first step, the residual is set to the model response, and thus, the computation can be denoted by X"y. The lines 4 - 6 perform this computation privately using the NoisySMPC Algorithm ! This noisy correlation selects the feature with the highest absolute correlation as part of the predicted basis (line 8). We then subtract the correlation contributed by the newly contributed feature 1* from the previous residual to obtain the new residual. Mathematically, we represent this correlation contribution as (B(( 7 = X (xxxx,)) " y where 31+ 1* X1*), 7 = X y. Note that this computation computes the correlation between the
Private OMP:
X 1,,,,,30,00 1 (x new column i* and other columns. These correlations can be computed via the NoisySMPC mechanism. We represent these combined computations on lines 10 18. Note that after a feature is choson, its associated correlation computation must only be done twice via NoisySMPC. We first privatize correlations over all un-selected features (order vp-7 where are the number of features already chosen). From amongst these correlations, choose the correlation with the highest value. Once the highest correlated feature is identified, we add noise to this correlation with a much lower noise value (of order I where s is the sparsity of the model). Thus, we can significantly reduce the noise impact by privatizing the highest correlation twice.
Remark: We notice that, to privatize the p-dimensional correlations (lines 5 and 11), we cannot reduce the variance of DP noise below O(p) (sce the Gaussian mechanism from Dwork et al. (2014)). Thus, each time we compute the p-dimensional correlations, we are required add noise of magnitude ((vp). However, we only need to do so finitely many times (f... times), thus requiring finite privacy budget. Further, thanks to NoisySMPC, we can get away with adding significantly smaller amount of noise (lines 14-17).
Further, we note that for our method, we need to compute a maximum of p(s + 1) + 2s² private correlations. In DP-SGD, we instcad need to compute pT private correlations, where the number of iterations T is significantly higher than a and often around the order of n. Furthermore, in our proposed algorithm, we require order-p variance noise only for recovering the basis while order-s variance noise is used to compute the model parameter on these bases. DP-SGD on the other hand requires order-p variance noise throughout for all T iterations. Thus, the noise required for our method is much lower in terms of the number of private correlation computations and the model parameter computation. Therefore, we expect to recover model with significantly higher accuracy.
Enhancement 1: Adding lower noise to selected features
While the above idea of privatize OMP may seem straightforward, there is a key step Line 14 which greatly enhances the performance of SPriled-OMP. Note that in lines 5 and 11 of Algorithm 3 we already
6

---

Published in Transactions on Machine Learning Research (06/2024)
privatize the p dimensional artifacts X"y and X X,= respectively with noise of variance poî. Although we could have directly use such privatized values in estimating a, the resulting error will be high. Instead, in line 14, we re-privatize the private model with much lower noise of variance saž. We have found that this re-privatization step can significantly enhance the performance of our proposed algorithm, ensuring its sparse basis recovery success. Please see the numerical results Section 7 for details. Intuitively, although we re-privatize the same features/ reaturrs/artifacts artifacts twice, since, we add lower noise the second time, the noise á estimate (refer line (15) in Algorithm 3 is of order only depending on s. In contrast, if we do not utilize this modification, then the order of noise in both B and á will be O(PP). Since these estimates will be used in later steps to identify the next basis, without re-privatization the higher noise will disrupt the correlation computation, leading to stricter requirements on the sample size.
3.1 The
Algorithm
We now present the second version of private OMP with our second enhancement in Algorithm g that further enhances the performance of Algorithm 3
Enhancement 2: Re-visiting SPriFed- OMP from the gradient perspective
In line 15 of Algorithm 3 we compute the private correlation (essentially the gradient) at the 1th step given by, %o - -9 (% + Thu - (Bt + ng)ā where (%)), , represent the true (uon-noisy correlations), Thyo M7 represent the corresponding noise values and a(= Ysu)) represents the privatized linear model. We notice that since we are already privatizing the correlations required in the computation of ā, we are naturally inclined also to privatize (77) and f similarly. Thus, in our first approach of Algorithm 3 all clients collaboratively compute correlations, and then the server computes the final private model and the private gradient. However, our second approach improves this correlation computation by first computing the L2 sensitivity (Definition A.2) of the gradient calculated using the private model (or mathematically, (- ))) and then adding the corresponding DP noise to the entire correlation rather than separately privatizing each correlation. In this second approach, given the model, each client computes the gradient on its own device. Collaboratively, all clients and the server then compute the aggregated gradient. However, the server still handles the model computation with the noisy correlation method. That way, the server can share the private model with individual clients without sacrificing privacy. Later in the next section and the experimental section, we will also discuss a clipping- based version of the new algorithm, SPriPed-OMP-GRAD (Algorithm that leverages clipping to provide better empirical performance.
We now present the second major enhancement our proposed method in Algorithm We note that the correlation computed in line 15 of Algorithm 3 is essentially the private gradient computed at the current. model value. In Algorithm 3 we first separately privatize correlation values and then combine them to obtain the private gradient. On the other hand, in Algorithm g we let the server pass the private model to the clients, and let the clients directly compute the residues and the local gradients (i.e., the gradient computed on line 4 in Algorithm [4). Then, we aggregate the local gradients in a private manner. We expect that Amgorithm | will see a significant performance benefit due to the effect of clipping. Note that clipping can control the sensitivity of individual data items, and thus has a directly impact on the magnitude of DP noise needed. Since, gradients typically reduce in magnitude as training proceeds, we can expect to clip the gradients more aggressively without affecting performance. In contrast, the correlations in Algorithm X will stay at large values during the entire training, which is not amenable to clipping. We report experimental effects of clipping on gradients and correlation in section 7 to visualize their varying impact.
4 Privacy Analysis
This section includes the details for the privacy cost incurred by running Algorithms 3 and 4
Since we need to account for the overall DP guarantee by composing multiple DP mechanisms, in this paper, we will use Gaussian Differential Privacy (GDP) Dong et al. 2019) (a variant of DP) for composition. In the later part of this section, we will discuss the reason behind choosing GDP over other composition mothods, e.g., those based on Renyi DP, in more detail. Before stating the Gaussian mechanism, we first formally define the Izzsennitivity of function.
7

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm NOISY-SMPC
Input Parameters: Vectors to be multiplied: Xk, (or y) E ER" Number of clients: Noise
Variance: o
2: Output: X Xj + Me: ~ (0)
3: procedure NOISY-SMPC(X, N,
4: Server broadcasts noise variance of to all clients
for client i [n] do
1/: VO, S
Compute gi - X 33. + +
8:
end for
9:
// Vanilla SMPC
10:
Compute Itotal - Ei=1 di using SMPC [Bonawitz et al. 2017)
11:
11 The resulting private sum satisfies the following - Qtotal -i XR,i, X + th = x +
1 = - + Ms: Th N n- o (= (V00,0)
12:
Server obtains and returns ltotal to all clients
13:
end procedure
Algorithm PRIVATE-OLS
1: Input Parameters: Data: X = (X1, X2,..., Xp) | R"xp, where X; is the 8th feature. Response Variable: y RR, Feature Set: SA, New Feature to be privatized: [*, Privacy Parameter: 02.
Truc Model Support Cardinality: s.
185 and Thi both have iid elements Output: Private Model: (X (SA + 118 ) 1
with distribution (0, oÿs).
procedure PRIVATE-OLSIX, y. SA,"", (2.88)
[s N-NOIS--SMPPCXXX (1,,, J,, n, /2v 1x Nole, that total privale correlation over all previous rounds is 7SA X This TTAA eRixl has sid elements from NO, (0,03s) */
for k == 0: do
6: [s, - NOISY-SMPCIX
7: end for 1 Note that, as BSA is symmetric, we have [k, = 3s k] and thus total private Rxx has iid elements from ((0,o3s) */
covariance is ASA XT SAXSA + Return (BsA) YSA
end procedure
Definition 4.1 (I2 sensitivity of a function). Given a deterministic function f, consider all possible pairs of neighboring datasets X and X' in the domain of that differ on a single row. Then, we denote lz-sensitivity
of f as
22f
max X.X Edom(()
f(x')112
Thus, Agf records the maximum possible change in due to change in single row. Often, each row belongs to different client, and thus, 42f will record the maximum change due to change in client due to the inclusion or removal of a client from the dataset. Below, we state the Gaussian mechanism from Dong et al. (2019) required to achieve the GDP guarantee.
Lemma 1. [GDP mechanism (Theorem 2.7 from Dong et al. (2019))) Let f Raxp - Rp be some function computed over the dotaset X E RRPp, Then, the randomized Gaussian mechanism M(X) f(X)+ +1 is μ GDP where 7~ NOO (Aa()' 1,) and Def is the L2- sensitivity of (Definition A.
Reasons behind choosing GDP for privacy analysis: We choose GDP because GDP gives the optimal privacy guarantees for compositions of Gaussian mechanisms. For example, GDP has been shown produce lower values when composed over finite (possibly small) number of Gaussian mechanism steps T Dong

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm 3 SPrifed-OMM: Private Orthogonal Matching Pursuit
Input Parameters: Data: X {X1, X Xp) Raxp, where X; is the 4th feature. Response
Variable: y I", Feature Set: Q (1,2,...Pp True Model Support Cardinality: s, GDP
Privacy Paramcters: Mp: (pp Na), Noise standard deviation: 01 Py 02 jby
Output: Predicted Support SA, Predicted sparse model over predicted support SA
Initialize: SA x,55 = 0,
for k 0 0: p- 1 do / Server and Clients privately compute data-response correlation */
[A) NOISY-SMPC(X 01
6: end for /* Note that the total privale corvelation overall k is %o XTy X + 1h: Thy Rpx1 has
tid elements from NN0 */
7: while [Al & do
8: - arg max J ((T))) )sl
/* Server privately extracts new highest-correlated feature *
SA - S
10: for 0=:0pp- do
/ Server and Clients privately compute data covariance for newly
extracted feature */
11:
B[k, [] NOISY-SMPCIAS XR. n,
12:
end for /* Note that, the total private covariance over all previous rounds is B XTX
X" XSA + 778 n7 RFx(I+1) has iid elements from ((, */
13:
// Server privately updates residual with newly chosen feature
14:
à - PRIVATE--LS SA," 02,3)
15:
71 % - -Bā
16:
1=1+1
17:
end while
18: Return SA. à (3sA) 7
YSA /* Server privately publishes sparse basis and model overall
extracted features */
Algorithm SPriFed-OMP-GGRDD Private Orthogonal Matching Pursuit
Input Parameters: Data: X {X1, X2,..., Xp) Raxp, where X; is the ith feature. Response
Variable: & R", Feature Set: Ω (1.2....PP, True Model Support Cardinality: 8, GDP
Privacy Parameters: Ppp (o(p > pa), Noise standard deviation: 01 14, 02 n, Privacy
[1(8))ss lbs.
Vitcorine) (refer Lemma and
Constants: XM = UM = 1, Bc = 1 + 2X + 2//x33/ 1-6.41 + I-6x+1
Section
for further details about setting Be in practice).
while S A < s do
for 0: do
4:
دb - NOISY-SMPC((X;;
end for
6:
1* < arg max en/s (())))
SA SAUP
8:
// Server privately updates model with newly chosen feature PRIVATF-OLS(X, SA, 82,88
10:
1=1
11: end while
et al. 2019h. This small-T regime is important for work because proposed algorithms aim to find the correct basis with only small number of iterations (proportional to the sparsity level s). Readers refer to Table 1 of Reference Liu et al. (2022) for an empirical comparison of various adaptive composition mechanisms where GDP performs the best. (i.e., produces the smallest. values across varying values of 6) compared to other composition mechanisms including Renyi DP, Advanced composition and naive DP. For related results on the non-adaptive composition of Gaussian mechanisms see Thcorem 8 Balle Wang (2018)). Finally, we note that single value can demonstrate GDP guarantees, and GDP can casily and optimally be composed over multiple iterations via. Corollary 3.3 in (Dong et. al. 2019 Furthermore,

---

Published in Transactions on Machine Learning Research (06/2024)
convert between μ GDP guarantee and the (e, ()-P) guarantee losslessly via Corollary 2.13 in Dong et al. 2019). However, only need to convert μ-GDP to DP for our purpose. Below, present both of these lemmas.
Lemma 2. /Conversion from μ-GDP to (e, (Corollary 2.13 in Dong et al. (2019)) ) A
mechanism (e. for all ε > 0 and
(
1 e
2)
#
2
if it is p-GDP. Here, denotes the standard normal CDF.
Further, multiple mechanisms with p-GDP into an overall GDP mechanism. Lemma 3. Composition of p-GDP (Corollary 3.3 in Dong et al. (2019)) The composition k-GDP mechanisms, each of which is PD-GDP i = l,...k k is v E 12- GDP.
In summary, leveraging GDP allows us to obtain better composition results, control the privacy leakage by a single parameter, and losslessly convert. between GDP and (s, 6)-P. For further details regarding GDP, we refer the reader to Dong ct al. 2019).
we notice that we only need differentially privatize the terms X7 y and X X2 and their combinations. Thus, we use Lemma 4 to identify their Lz-sensitivity (Definition A.2
For our proposed Algorithm
Lemma 4. Under Assumption the Logsensitivity (Definition A.2) of the terms X2 y and X" j for any SA defined in Algorithm are given by 2 =((P) and 2/PX3 O(vp) respectively. Here, X e Rexp and e R
Proof. The proof is available in the Appendix section
Lemma 5. Consider design matrix X E Raxp salisfying RIP of order + 1 and RIC S4+1- Now given the corvelation greeaation/gradient Cj (as computed in Line of algorithm 4 for any j E [p], we show that the upper bound on the L2 sensitivity of the expression is upper bounded by the following values,
A2(C,) +1+ 28 + 2 [((4))s) lbo
vI+ +1+Sttilee Sutilfee
Be
Sot1
1 1-C411 Got1
when Assumptions and hold. Here, as is the underlying ground truth model, N₂ / (ogg2(// and oe is the additive system error's standard deviation. We also need to assume that Sst1 < vs and
602 22ogg2/22ll 12(1-5a+11
The result holds with probubility 1 1 3pp where po is small positive probability
value.
Proof. The proof is provided in the Appendix Scction
Theorem Algorithmss 3 and salisfies GDGDP with P V 12 2s 12, where Pay Ms are privacy constants as inputs to Algorithm
Proof. The proof follows simply by Lemma 3 In our proposed algorithm, we use the GDP (lines 5 and 11 in Algorithm 3 and line 4 in Algorithm g mechanism a times and the GDPGDP mechanism 2s times (lines 4
and 6 in algorithm 2) Thus, the result. follows. Finally, using Lemma 2 we can obtain the corresponding DP guarantee of Algorithm 3
5 Accuracy of Private Orthogonal Matching Pursuit
This section will present our main result on the accuracy sparse basis recovery. Thcorem states that the proposed algorithm SPriFed- OMP (Algorithm 3) terminates in finite steps and can recover the true sparse basis and the corresponding model w.h.p. as oo and when ((vP).
10

---

Published in Transactions on Machine Learning Research (06/2024)
Before state our main results, define the relevant constants. Let Sa+1 denote the RIC of X of (s + ))-order. Let y be a small positive constant, close to 1, that satisfies the inequality T- & u(++1). Recall that de is
and fi = KM, KM,, (lM(P/og/p/)))) the standard deviation of the additive error the system model presented Section 2 Here, pb is small positive probability, eventually affecting the with-bighh-robabblity statement of Theorem 7 Further define the constant KM₃
Next, we define K, = V 2 log( (h)) Ai = KM, (ls.Vlog(s/p)))
KM2 = 1 1+ 11 11-1)
where the constant C (which depends on Ps) is chosen such that the following probability statement holds: For square matrix N with dimensions s 8, where the elements follow an i..d. distribution of NV 1), its largest eigenvalue is greater than C with probability pb, i.e.,
Pr (1 CIV&) & Ph
By these choices (which will be used in our proof in the technical report), each constant bound the corresponding random variable with probability 1- - ps- Finally, we denote the true basis of the underlying model by S..
Theorem 7. [Sparse recovery of SPriFed- OMMPPP Under the provided system model (Section ? and Assumptions 7 and suppose that the following conditions holds:
4v Alog(pp st/P = Omaxx "V ppogg 5/2
Sample size: n z max /pssi 1605/2k2; K2,
Apllas lla
Mally n.,
RIC of X of order-s + 1: Sst1 k[+Vo
minjes layl
9. Re Ke & 16 ((L+004))))
Then, the SPriFed-OMP algorithm will correctly recover the true basis with probability 1 - 40(s + 1) Pb-
Remark (Intuition behind the assumptions for successful recovery in Theorem 7 If we ignore the log term, condition only requires n = ((vP) for sparse recovery. To the best of our knowledge, this is the first result in the literature that both attains DP in an FL setting and attains sparse recovery when n is much smaller than p. We note that condition Ologr) is sufficient. We believe the main reason for this difference is that must simultaneously ensure DP in the FI. setting. As we discussed carlier when present Algorithm D even in the first step for computing the data-response correlation, O(vP) noise seems unavoidable (remark under Section 3 Thus, it seems difficult to suppress the noise when is smaller than vp.
stricter than typical OMP results in the non-private scttings, where
Condition is related to the strength of the RIP assumption. The smaller the RIC, the closer X is to unitary matrix, and thus, the corresponding condition becomes more demanding. Our condition provides simple upper bound for the RIC. As expected, we observe that, with the increasing value of 8, our RIC bound reduces, implying that sparse recovery gets more challenging the model cardinality increases. This intuition is in line with that in the non-private OMP literature.
The RIC is an important attribute of the RIP.
Condition 3 on the additive error in the training data is also intuitive. If the minimum true-model column norms are large enough (i.e., the signals due to true features are sufficiently strong), then we expect that the impact of the additive error in the system will be minuscule. This is reflected by the term minyes, |ayl in the numerator. We also expect that model recovery gets more complex with rising model cardinality (i.e., rising s). Thus, the impact of the error in the training data will rise as reflected by the v 1 term in the denominator. Similar to Theorem we can state the recovery guarantee of SPriFed-OMP-GLE
below. Theorem 8. [Sparse Recovery of SPriFed- OMP Grad) Under the provided system model (Section and Assumplions and suppose that the following conditions hold,
11

---

Published in Transactions on Machine Learning Research (06/2024)
([v++1)[++ /olna +1)) 2v (Vlog(p-91) sl/p
0 ( log
Sample Size: n 2 max
1999
Mpl ap
RIC of X of order + 1s41 vo+1
mingr&g layl
3. Ki <
6(1+0(++1)8/ VE+1+ Civenay I
Then the Oiteod-OMP-RAAA algorithm will correctly recover the true basis with probabilily 1 - 8(88 + 1)ps- Note that here, hi
V1tGu1i(yt4 illow))+ss) Rig /2 pe Kig 2 (2) and Be =1 Miee +
1-
(sa lle VitGuing and ps is small positive probability value similar Theorem 1-6e-1
2//5X31( I-6e41
Remark (The privicy-prioacy Irade-off) Although we do not. explicitly mention privacy requirements in the results here directly depend on the privacy parameters such as and Hy. Thus, we G to obtain the utility-privacy trade-off. Specifically, suppose that we wish to re-write the conditions stated in Theorems 7 and g in terms of (c, 3D- guarantees. We first pick μi, which can be easily converted (c DP guarantees according Lemma 2 Then, by assuming that Ps Pp may where my known constant factor, we obtain from Theorem that μ /py + m?). We can thus solve Up and ss as:
Theorems 7 andd 8
can combine them with Theorem
"p p/ s1+ m?)
Ms Up ma.
These values can then be directly plugged into Theorems and g obtain the accuracy guarantees.
Remark (Benefits of Algorithm 4 over Algorithm 3 Readers can see that the conditions of Theorem are on the same order as that of Theorem 7 However, this is because we assume the DP noise magnitudes are the same in both cases. In practice and as we discussed earlier, due to the decreasing magnitude of the gradients, A Algorithm 4 can benefit from more aggressive clipping and lower DP noise magnitude. We will present numerical results to demonstrate the benefits of these enhancement Section 7
Based on our main Theorems and g next, we provide results on the parameter estimation error and empirical risk. Both of these results are optimal they in the same order several previous results for both the parameter estimation error (Meinshausen & Yu 2009 Wasserman & Roeder 2009 and the empirical risk analysis [ifer et al.) 2012 Bassily et al.) [014)) even under the assumption that they have already known the correct basis before-hand. In particular, these error bounds depend on s but are independent of the dimension p since we have already identified the correct sparse basis as in Theorems and
Theorem 9. [Estimation Error of SPriFed-OMA OMP and SPriFed-OME Grad] Under the same system model and assumptions as Theorem 7 with high probability of 1 Pb, the eslimation error satisfies,
Aa || ass1l2
// log( 22) Pb
C.+ / 2s log o2
Vn
11 Co+1)
8 3/2 3// 2 log(
26
Pb
(1 (at1)llasu
Mn Co+1)2
V&y log( 22
+ / 1 Som1Bee
Hun
-0(man [axx { (slg((s)
33/2
Tog(s)
{V"
n
nfu
12

---

Published in Transactions on Machine Learning Research (06/2024)
where & is the predicted model from the SPriFed-OMP algorithm, asa is the true ground truth model, So+1 is the RIC conslont for the matrix X and Ps is as defined in Algorithm Our result holds with high probability of 1 4ps.
Proof:
The proof is omitted due to page limits.
Theorem 10. [Risk Analysis of SPriFed- OMP] Under the same system model and assumplions Theorem 7 with probability 1 4ps the risk AR from algorithm SPriFed OMP is bounded by.
AR R( X, y)
1 n
(z,à y:)² (2,as -()a-s w))²
n
(s+1)s 22ogg 22
2
Man(1 (o+1) 1)
(1 + Sa+1 /2 2ns log (28 pol)o X
+ 2
n(1 So+1)
3/2 RM 2 loog
2x ps
+ 2
(1 (a+1)
MaTi(1 (s+1)2
v 2 log
22 pa
v S041K, +
pnn
slog(s) s log(s) = -o(max max
n n2p22 2
where & is the predicted model from the SPriFel-OMP algorithm, OS is the true ground-trulh model, S++1 is the RIC constant for the matrir X and μs is as defined is defined in Algorithm S and the label veclor while n the vamber of clients.
X, y are the data matrir
Proof: The proof omitted due to page limits.
Remark (privacy parometers in Theorems and 10 Results in Theorems 9 and I0 only depend on the μa parameter and not Mp privacy parameter as the privatized model in these results are outputted based on the PRIVATE-OLS routine which only adds noise with privacy parameter of μs (as the predicted bases are alroady known).
6 Proof Sketch of Theorems 7 and 8
This section identifies the key steps required to prove Theorems 7 and g From Algorithms 3 and we notice that in the very first round, the server picks the feature with maximum absolute data-respouse correlation over the entire feature set. To ensure that we only pick features from the true feature set, we thus require expression I below to hold.
XJ y + Thg JES&
min
max XJ y + nhyl. J$S
(1)
In other words, for correct basis recovery to occur in the first round, the minimum absolute feature correlation over the true set should exceed the maximum absolute feature correlation over all the features not in this true set. The strategy for proving 1 is to bound the mandomness-induccin terms (i.e., noise terms) with high probability. This high-probability event will also dictate the relationship between the sample size, the restricted isometry constant, and the rest the system constants. Using the restricted isometry property over the datasot contributed by all clients, we can then show that the above incquality holds. The remaining rounds are handled similarly over the updated residuals. The complete proof is available in the Appendix sections P and F
13

---

Published in Transactions on Machine Learning Research (06/2024)
Remark: Here, re-iterate that both algorithms' analyses have subtle but critical differences. In Algorithm B the noise is added to column correlations (that are collaboratively computed by the clients), and then the private model and the aggregate correlation between columns and the residual (d.e. the gradient) are both computed by the server. In Algorithm 4 the clients first compute their individual gradients and then collaboratively find the average private gradient. The server computes the privale model similarly to in Algorithm
3 but then shares this model with the individual clients. Here, the clients then recompute their gradients for the next step. Algorithm adds the noise to the correlations of the gradient, which are then the bulk of the noise value is added outside of the correlations,
multiplied. On the other hand, in Algorithm 4 directly to the gradient.
Although our analysis idea is similar to several OMP proofs in the literature (such as Chen & Caramanis 22012), ) we have to redo the analysis because the way with which we add noise to the system (to ensure DP) is completely different. Notably, Chen & Caramanis (2012) adds noise to the measurement matrix X, which has several issues. First, does not even protect the privacy of the response y. Second, the noise variance is of the order-np, which is too high and likely leads to poor estimation accuracy. Indeed, the estimation
error bound (Corollary 8) in Chen & Caramanis (2012) given by ||a - &112 O (ax+t)))aa where ow is the standard deviation of the noise matrix WTW such that W is the additive noise added to the original matrix X. From their analysis, the term on + o = O(p²) when ow is set. to the DP-compliant noise value. The above error bound, therefore, will be huge when p n, negating its usefulness in the high-dimensional regime. The experimental results in Chen & Caramanis (2012) assume small values of Ow, not at the level of (p)) needed for achieving DP. Third, Chen & Caramanis (2012) does not provide a condition on the RIC. They assume that the matrix elements are subgaussian ii.d;; thus, their model implicitly determines the RIC constant in their results. In contrast, we allow an arbitrary design matrix X (irrespective of the matrix's data distribution) that satisfics an RIP condition. Thus, it important to quantify the condition of RIC to guarantee sparse recovery.
7 Empirical Results
In this section, we compare our proposed algorithm SPriFed-OMM with a version of the DP-SGD algorithm Abadi et al. 2016) that uses Li regularization (Zhao & Yu 2006). The first set of experiments is based on a synthetic data set so that we can freely vary the sample size n, the model dimension p, and the model sparsity s. Given p and n, we first generate X with é.í.d. elements, each of which is from Ao(0, 1). Given the model sparsity s, we then generate the non-zero coefficients of the model parameters Qx each of which is from the distribution (22 1). We then add additive error with mean zero and standard deviation a, 0.001 to generate the response y. We then clip (to 1 or -1) every element in X and y with magnitude greater than 1 and then re-scale the whole matrix/vecte vector appropriately to maintain their unit variance as required by the RIP condition
7.1 Warm-up Experiments: Intuition behind our proposed enhancements
Before moving on to the main experimental results, we revisit the enhancements noted in Section 3 that both experiments below use the synthetic data setup above.
Note
Importance of Enhancement Adding lower noise to selected features
Here, we test the sparse basis recovery capabilities of Algorithm Jo & synthetic loy dataset. We compare Algorithm 3 with another modified version, where Enhancement is removed, i.e. we directly use the artifacts privatized by the higher order noise in lines 5 and 11 to estimate the private model. Thus, the private model will now have noise of order O(vP) instead of O(7B). In Table I. we observe worse test MSE and poor sparse basis recovery performance when enhancement is removed. Thus, we conclude that we need to re-privatize, i.e., add lower-order noise to the correlations/graete obtain competitive sparse basis recovery in the DP-FL case.
computed on the chosen feature set to
Importance of Enhancement 2: Privatizing the gradient
14

---

Published in Transactions on Machine Learning Research (06/2024)
Tist MSE
Number of samples recovered
Sumples
SPMFEd-OMP (low boise)
SPoPaT-OMP [high noise)
SPAP---OMP (low hoise)
SPRFed-OMP (high noise)
a 2000
0.83
$35.81
4000
0.52
6.45
2.07
1,77
8000
0.35
0.77
7.07
5.67
Table 1: Enhancement Performance Improvement: Comparison of Test MSE and basis recovery performance for when Algorithm 3 runs with and without enhancement The experiments are run over randomized trials over the synthetic setup (above) with p 10000, 10, and privacy guarantee of (5.74, 10 10 DP.
In this experiment, we look closely at the two kinds of artifacts released by Algorithms 3 and i.e. the correlations and gradients respectively. We measure the change in the artifacts' value over iterations by measuring and plotting the total l2 norm values for each artifact. To do so, we run non-private version of Algorithm and plot the changing correlation norms and gradient l2 norms over multiple iterations. Here, in each iteration we use the correlation value with respect to the current newly chosen feature j (referred Figure I legend). We observe from Figure [ that the gradient norm values decrease over time while most of the correlation norms are constant. As expected from the way OMP is designed, only the value of the correlation norm | y/l decreases over iterations since the newly chosen features have lower correlation values than previous features. Thus, we conclude that we can employ more aggressive clipping in Algorithm ! than in A Algorithm 3 That is, for gradients, a lower clipping bound should work well, especially toward the final rounds, while such lower clipping bounds will significantly affect the correlations irrespective of the iteration.
2001
Narm of data artifact
[X3,X,
3000
lterations
Figure 1: Enhancement Performance Intuition: Change in size of artifacts (correlations and gradient)
measured by their norm multiple iterations.
7.2 Performance Comparison: Synthetic Data Sets
In the rest of the section, we will compare SPriFed-OMP with various baselines. We first discuss the experimental setup and the basclines. In "PriFed-OMP (Algorithm 3). we the parameter Pp be cither 0.4 (for 10) or 0.543 (for = 5) and set the parameter μ4 0.02. The cumulative privacy cost (e, 0) for all the experiments is set to most (5.34, 10-4) (for DP) equivalently 1.32 (GDP). Note that SPriFed OMP does not require hyperparameter tuning besides choosing the privacy parameters μ4, and μp. Since p 8, we can easily tolerate much smaller than Ap- Thus, the Up parameter will primarily dominate the privacy cost.
The first baseline DP-SGD implemented minimize the L-rrguularzeed mean square error. After the algorithm terminated, we pick the top-s elements and leverage those compute the final model and the test MSE. One requirement for DP-SGD is that also need to choose the hyper-parameters, which the
15

---

Published in Transactions on Machine Learning Research (06/2024)
SPriPdd
Sanda DM203
DP-5GD
DM-CCD
MSE
Test MSE
00
200
190
Sample Size (n)
Dimensions (p)
(a) fix
5, 2000, vary
(b) fix
5. 2500, vary Y
Figure 2: Test MSE is shown for both SPriFed- OMP and DP-SGD for privacy parameters (4.94, 10 +)
Figure (a) fixes the sample size and varies the model dimensions; Figure (b) fixes the model dimensions and varies the sample size. Measurements averaged over randomized simulation runs.
Number Basis Elements Recovered
oven
Number of Basis Elements Recovered
SINPNS--NP-GRAD
OP SGD
DP-560
an GzB
DI-GED
Sample Size (n)
Sample Size (n)
(a) fix 5.p 2500, vary n (Synthetic Data)
(b) fix 5. 10000, vary (Synthetic Data)
Figure 3: The number of basis correctly recovered by SPriFed-OMF OMP for privacy parameters (4.94, 10-4). We
choose 8 = 5. Figure (a) demonstrates basis recovery for model sparsity 2500 over varying sample sizes.
Figure (b) demonstrates basis recovery for model sparsity = 10000 over varying sample sizes. Measurements averaged over 3 randomized simulation runs.
coefficient for the I--regularization term and the learning rate. Although hyper-parameter tuning may incur an additional privacy cost for DP-SGD, hore, benefit DP-SGD, we perform the hyper-parameter tuning non-privately using the Optuna library (Akiba et al. 2019 To maintain standardized notion of privacy definition, also study the composed privacy cost of DP-SGD using GDP. In particular, for achieving GDP in DP-SGD, we set the privacy parameter PDP-SGD as cither 0.4 (when
10) or 0.543 (when = 5). #DP-SGD matches the Рe parameter from SPriFed-OMMP OMP, which is also being used to privatize p-dimensional vectors. DP-SGD stops training when the overall privacy budget matches that of SPriFel-OMPP
The second baseline DP-GCD is based on a modified DP-FL compatible version the algorithm presented
Mangold et al. 2023). Algorithm in Mangold al. (2023 primarily follows from the Gradient Coordinate Descent (GCD) algorithm. Like DP-SGD, although DP-GCD does not provide performance guarantees sparse basis recovery, it remains a natural algorithm when used along with 4y-reullarization objectives.
Although GDGD alone provides intuitive privacy definition, for completeness, also convert the final μ-GDP privacy parameter the approximate DP parameters using the AutoDP Python library (Wang) 2023
16

---

Published in Transactions on Machine Learning Research (06/2024)
Number of Daste thenetss Receees Rectverdd
Number of Bist $te- monto Recorroo
the dan Sori sE suiipod
Number of B121 Stc Berrono
(a) fix =010,p 2500, vary (Syn- thetic Data)
(b) fix 10. 10000, vary (Synthetic Data)
(c) fix 10, vary p and (Synthetic Data)
Figure 4: The number of basis correctly recovered by SPriFed-OMP for privacy parameters (5.34, 10- We choose s = 10, and figures (a) and (b) have an additive error with standard deviation d; 0.001. Figure (a) demonstrates basis recovery for model sparsity p 2500 over varying sample sizes. Figure (b) demonstrates basis recovery for model sparsity p 10000 over varying sample sizes. Figure (c) varies 40000 while increasing the system model's additive error's standard deviation to 0, = 0.1. Measurements averaged over 3 randomized simulation runs.
20000 and
However, DP-GCD in Mangold et al. (2023) considered DP only in the server setting but not the DP-FL setting as in this paper. Thus, we make an effort to compare with it by first converting to a DP-FL compatible version. We first present our converted DP-GCD algorithm (Algorithm 5]. Here, cach iteration, the maximum gradient is picked privately lines 5-8, and the model (akes a slep in only the direction of this chosen gradient element in lines 10-11. Such gradient-based optimization steps are repeated until the model converges the privacy budget is exhausted.
In our modified version presented in Algorithm 5
we also include two enhancements to the DP-GCD algorithm from Mangold et al. (2023). First, we convert DP-GCD to be DP-FL compatible by leveraging the NOISY-SMPC mechanism while identifying the feature with the maximum gradient (lines 5-8). We further ensure that much lower noise is added while following the gradient tradient-based approach in DP-GCD by separately re-privatizing (in line 10) the feature gradient chosen via the maximum gradient mechanism. Thus, in summary, proposed modification of DP-GCD (Algorithm 5) significantly enhances the private version in Mangold et al. (2023) by making it DP-FL compatible while also ensuring that it has traits suitable for sparse basis recovery. Similar to DP-SGD, we again perform apper-parameter tuning non-privately using the Optuna library (Akiba et al. 2019). For both DP-SGD and DP-GCD, we do not include the cost of tuning these hyperparamelers the privacy cost, and hence, the results we report below are more optimistic for these two algorithms. Below we discuss our empirical findings.
Fix n, Change p: In Fig. [(a), we fix 5 and 2000 and vary e (2500, 4000, 6000, 8000, 10000). With rising p, observe that the test MSE loss increases much more dramatically for DP-SGD (note the logarithmic y-axis) than SPriFed-OMM In fact, SPriFed-OMPP performance is almost constant as p varies since its empirical risk (Theorem 10 is mostly dependent on s. Further, although not shown in the figure, SPriFed-OMM extracts most the basis elements (> 3) even when p = 10000. Finally, even though the sample size can be quite small in comparison to the model dimension, we obtain highly accurate models for SPriFed-OMP with test MSE close to zero, which is in line with our theory (sce Theorems 0 and 10p. Similarly, even though DP-GCD performs better than DP-SGD in terms of test. MSE (thanks to the lower noise that our enhanced DP- GCD algorithm adds), its test MSE is still much worse than SPriFed-OMP, We will discuss this limitation of DP-SGD in the latter part of this section.
Fix P, Change nu In Fig. bb), we set 8 = 5 and 2500 and vary n E 8400,800, 1200, 1600, 2000). We observe that when p > n, the performance all algorithms is impacted. However, increasing the sample size improves performance more dramatically for SPriFed- OMP and SPriFed-OMPP OMP-GRAD (again, note the logarithmic scale on the y-axis). Notably, SPriFed-OMe OMP and SPriFed OMP GRAD significantly outperform DP-SGD and DP-GCD for all choices of n. We specifically note that the test loss for both versions of
17

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm Enhanced DP-GCD (DP-FL)
1: Input Parameters: Data: X = {X1,, X2,...,Xp E Rnxp where X; is the 8th feature, Response:
y E R", Learning Step Size: 7/ Total Steps: T, Privacy Paramcters: 01 H4," Initialize Model:
ā 0, Initialize Basis: S = Ø, Gradient Bound: C (true bound over all gradients or bound achieved
via gradient clipping).
Output: Predicted Sparse Model á, Predicted Sparse Basis 9
3: procedure DP-GCD(X, y, n,
4: for = 1 do do
5: for j = 0: do
6:
9 - NOISY-SMPC(X, - Xsq end for
7:
je arg max, 1951
S S u (5*}
10:
0j* - NOISY-SMPC(Xx: (
Xsyā,n,o1C)
11:
abi+ a[j*] 7965
12: end for
13: Return S
14: end procedure
SPriFed- OMP gets very close to zero (as n increases), which matches our theoretical results (Theorems 9 and 10
Fix 8, Change p and n: In Figs. and we report the number of non-zero basis in 0g that are correctly recovered by the proposed algorithms. We show two plots, Fig. for = 5 and Fig, 4 for 10. The sample sizes are varied over (500, 1000, 2000, 4000, 8000} and the model dimensions are varied over {2500, 100000) for both 8 = 5 and 8 = 10. Additionally, we also vary p over (20000, 400000) for the 8 = 10 case. First, we can see for correctly recovering majority of the sparse basis, the value of n increases much slower than p. Let us examine more closely the cases when we vary 8 as either or 10. We first look at the case when = 5. For p == 2500 by setting n 2000, we manage to recover 3+ out of basis elements with SPriFed- SEFFFedOMP--O OMP-Grad It turns out that even when p is increased to 10000, using n 2000 is still sufficient to recover 3 out of 5 basis. When s 10, we consider the number of samples required recover 7+ out of 10 basis elements. For 2000 sulfices. But when p is increased 4 times to 10000, we only need to be doubled to 4000.
p p= 2500, Finally, when p is either 20000 or 40000, we only need n = 8000 samples to recover the same number of basis clements. In summary, we find that, as the model dimension and the model sparsity increase, the sample size required for sparse recovery increases as well, which is consistent with our main results, Theorems 7 and More interestingly, the value of n increases much slower than that of p. This aligns with our theoretical result that n only needs to be order-yp.
Second, seen while comparing Figures a-bb with Figure 4 c). increasing the additive error variability affects SPriFed-OMP the most, while both the gradient-based methods SPriFed OMP- Grad and DP-GCD are minimally affected. Note that the results shown in Figures (abb) have system error standard deviation of 0.001. Here, we can see that the performance of SPriFed- OMP is quite comparable to both SPriFed- OMP-GRAD and DP-GCD. SPriFed-OMP even manages to outperform DP-GCD for the higher sample size range. However, Figure (c)) uses a standard deviation of 0.1. Here, the performance of SPriFed-OMP dips significantly in comparison to both SPriFed- OMP more than the other methods. These results are in line with our theory (refer Theorems 7 and that shows that OMrFeddMMMP has stricter system error requirements compared to SPriFed-
OMP-GRMDDDDDDDD- and DP-GCD. Thus, error variability affects
Let us now discuss the sparse basis recovery performance of the two baselines. Note that both DP-GCD and DGD converge to a private model by leveraging gradient- baased optimization. However, DP-GCD adds much lower noise than DP-SGD since, at each round, it only updates a single dimension rather than all dimensions as done by DP-SGD. This explains why we see a better performance for DP-GCD than DP-SGD. However, DP-GCD still adds significant. noise to the model compared to both SPriFed-OMP
18

---

Published in Transactions on Machine Learning Research (06/2024)
and SPriFed- CAMP-GRAD due to the following two reasons. First, due to its gradient-based optimization, DP-GCD may take more than one step to optimize any given direction fully. In contrast, for each new basis, SPriFed-OMP only collects new correlation values (or gradients) once. Thus, depending on the number of steps taken, the amount of noise added by DP-GCD per dimension is often much higher. For instance, if the same dimension is picked & times, then the noise added will be of L orders higher for DP-GCD than the PPriFed-OMP class of methods. The remark in this section covers further details. Second, unlike SPriFed-OMe OMP and SPriFed- SiiiFed-OMP-GII OMP-GRAD, DP-GCD does not compute the exact true value of the model (using the OLS formula) in each round rather than choosing to add noise to the previously predicted model continually and thus the noise added in previous rounds might affect the predicted model significantly. In contrast, private OMP estimates the model parameters a directly using the OLS formula (Algorithm 2 based on the re-privatized correlation values in Lines (14)) and (9) of Algorithmns 3 and respectively, which have much lower noise. Thus, this noise accumulation effect is greatly reduced.
Remark (Signéficant difference of Test MSE between DP-SGD, DP-GCD and both flavors of SPriFed- SPriFed-OMP): From Figures 2 a) and 2(b),, we observe that the test. MSE of SPriFed-OMP and DP-SGD are of different. orders (note the logarithmic scale on the y-axis). This difference is because, in SPriFed-OME we only introduce noise with a variance of order-s to the final model. In contrast, DP-SGD adds noise of order-p variance to all its model dimensions. Therefore, even though DP-SGD selects a subset of these dimensions for the final model, the considerable noise significantly impacts the resulting model coefficients. As a result, the test MSE for DP-SGD is much worse than the one we obtain from SPriFed-OMM that due to such high noise variance, DP-SGD cannot recover any of the true basis in our experiments. For the case of DP-GCD, the noise added to the model is of order as well. However, DP-GCD follows a gradient-based itcrative approach where noise is added to the gradicnt. Then, this noise is passed to the model based on the feature selected in that step, the learning rate, and the number of total steps taken. Unlike DP-GCD, the SPriFed- OMP flavors add noise to the exact value of the true model based on the currently selected features. Thus, overall, SPriFed-OMP only adds noise via the privacy mechanism. On the other hand, DP-GCD adds a similar noise via the privacy mechanism while also including a bias term based on the difference between the DP-GCD model and the optimal linear model for the chosen feature set.
Once more, we note
Remark (Run-time trends of algorithms): To understand the general trend of computational time required by each algorithm, we consider the sample case when = 2000, s = 20. p 20000. Here we provide the CPU time as measured by the time library in Python. We note that SPriFed-OMP takes 20.17 seconds, -PriFed-OMPP-Grd takes 26.38 seconds, DP-SGD takes 11.99 seconds, and DP-GCD takes 9.56 seconds. As expocted, the OMP algorithms take longer due to their separate computations for the sparse model in cach step. In particular, SPriFed-OMP-GGrr for each sample, sum them up in a DP-FL fashion (like DP-SGD and DP-SGD), and compute the sparse models separately. Finally, DP-SGD takes a bit longer than DP-GCD since, in each step, it operates over all possible features, while DP-GCD only runs the feature with the maximum gradient. Note that we expect when the number of clients is fewer, the gradient computations might be speedier. However, we will consider optimizing these algorithms and exploring a lengthier ablation study as part of future work.
takes the longest since it needs to compule the gradient separately
7.3 Performance Comparison: More Realistic Data Sets
In the second set of experiments, we test our proposed algorithms on the synthetic MADELON dataset from the NIPS 2003 challenge (Guyon et al. 2004), a popular dataset used in the sparse recovery literature. The original MADELON dataset has 20 true features, but only 5 of these are true raw features, and the remaining 15 are linear combinations of these raw features. Its total model dimension is p p= 500, with 2000 training samples. However, since we are only interested in the p n case, we randomly sub-sample 300 samples in each trial. We run 5 randomized trials and report the average results. Here, we set μp 0.45, μ4 0.09 for SPriFed- and PDP-SGD = 0.45 for DP-SGD. The corresponding DP guarantee is (8.38, 10-3), and the GDP guarantee is 1.72. For SPriFed-OMP, we clip the elements of X to 0.12 and elements of y to 0.36. We clip the gradient elements to 1. As expected, DP-SGD performs the worst with a high Test MSE of 105. 73. DP-GCD performs reasonably well with Test MSE of 1.23. Finally, SPriFed OMP has a Test MSE of 1.55 while SPriFed- SMadd-OP-CCo GRAD handily outperforms DP-GCD with a Test MSE of only 0.27. We attribute the relatively better performance of DP-GCD for this data set to two reasons, (1) proper hyperparameter
19

---

Published in Transactions on Machine Learning Research (06/2024)
tuning of DP-GCD; thus, we expect that the performance of DP-GCD would be worse if the privacy cost of hyperraaaaeterr tuning must also be accounted for; and (2) due to the synthetic nature of MADELON, DP-GCD might perform well even when it does not pick the exact best features (since MADELON has 15 features that are lincar combinations of the true 5 features).
In the third set of experiments, we show results on two real high-dimensional datasets from the repository presented in Drysdale (2022). Here, we consider the higl-dimensional datasets chop and gse The chop dataset contains 414 total samples with 3836 features, and gsc1992 contains 124 samples with 15537 features. Similar to MADELON, we sub-sample the dimensions of chop to be 2000 and that of gse1992 to be 500 in each trial. The rest of the privacy setup is identical to MADELON. We present the results for these datasets outperforms all other algorithuss
in Table 2 We note that both SPriFed- -MP and (Priied-OMP-CGA over both datasets with SPriFed OMP- GRAD providing the best utility. As previously noted in the remark above, we attribute the success of both versions of SPriFed- OMP to their ability to add significantly lower order noise to the true model value while leveraging the true value of the model using the ordinary least squares formula. Note that DP-GCD also adds lower-order noise to the model. However, unlike both flavors of SPriFed- OMP, DP-GCD does not add noise to the exact value of the true model, instead relying a gradient-basee based approach that iteratively adds noise to the gradient. The gradient-based noisc is then passed to the model value based on the feature selected and the learning rate.
Algorithm
chop
gse 1992
SPriFed-OND OMP
0.101
1.90
SPriFed GRAD
0.154
1.15
DP-GCD
18.79
525.60
DP-SGD
546.76
988.72
Table 2: Test MSE Performance: We observe that without model/basis selection, both DP-SGD and DP-GCD are required add substantial noise in the models, leading to much higher Test MSE than both SPriFed-OMM and SPrifed-OMP-GGLA However, both SPriFed-OMP and SPrifed-OMP-GRRA enjoy close to optimal test MSE.
7.4 Ablation study of privacy-utility trade-off
To understand the impact of the privacy parameters on the algorithm's performance, we next sludy the lest error and the number of bases recovered for both SPriFed-OMP and SPriFed-OMP- OMaddrad, as we vary the net epsilon value. We first consider the synthetic datascts of Section 7.2 for the case of n = 2000, s 5, and p 10000. Both algorithuss are run for random seeds. The value of Mp is varied over [0.1, 0.2, 0.3, 0.5, 0.8, 1], which in turn affects the final value. Note that Hs 0.09 constant since it does not greatly affect the net value. In Fig. 5(a) and (b), we plot both algorithms' test MSE and the basis recovery capabilities can observe that, and the number of correctly recovered bases increases). Both algorithms generally reach constant performance for any epsilon larger than 5 (which is around the value chosen in our results reported in Section 7.3
e. We increases, the performance of both algorithms improves (i.e., the test MSE decreases,
We then perform a similar study of privacy-utility trade-off on the realistic chop dataset. We consider the following setup where He is again varied over 0.2,, 0.3, 0.4, 0.5, 0.8, 1] to adjust the net privacy budget. We run both algorithms over 7 random sceds and set the clipping bound for elements of X, y be 0.5. u/x = 0.15. Since we do not know the underlying basis for the chop dataset, we simply report the Test MSE error in Fig. 5c We can that as increases, the error generally tends to lower. However, we observe that the error dips the most from e [6, 12]. Thus, we pick x 8, which gives a reasonable privacy-utility trade-off for a <<> 10.
Remark (Sub-sampling with DP-FL): We recognize that under a DP-FL setting, sub-sampling is beneficial in reducing per-round commuiicttin costs and amplifying privacy. However, the benefit of sub-sampling in the n < p regime that we focus on in this paper has not been thoroughly studied, which could be an interesting direction for future work.
20

---

Published in Transactions on Machine Learning Research (06/2024)
Number of basis clemens recovered
Shalaa out GIAD
SPr 000
010
10775
Frrox
0.08
02.0
(a) Basis Recovery-privacy trade-off (b) Error-privacy trade-off (Syuthetic Data)
(c) Error-privacy trade-off
(Chop
(Synthetic Data)
Dalaset Drysdale (2022))
Figure 5: Ablation study for finding privacy-utility trade-off. We look at the impact of choosing varying privacy parameters on the accuracy of the proposed algorithms. Figures (a) and (b) study the basis recovery, and Test MSE values varied over changing values of the overall privacy budget e, respectively, for the synthetic data with n 2000, s 5,p 10000. Figure (c) provides the Test MSE of the chop dataset again varied over the net privacy budget e. is implicitly modified by adjusting the privacy parameter Mdp
8 Conclusion
In this work, we propose two new private sparse basis recovery algorithms called SPriFed OMP and SPriFed- OMP-GRAD for the DP-FL setting basod on the Orthogonal Matching Pursuit (OMP) algorithm. Specifically, we prove analytically that both algorithms can recover the sparse basis in a finite number of steps. Further, we bound the privacy cost while leveraging the obtained low-dinensional model to obtain dimension-free model estimation error and empirical risk. Here, SPriFed-OME is our first attempt at leveraging OMP for sparse basis recovery in the DP-FL setting. In contrast, SPriFed OMP-GRAD improves upon SPriFed OMP (both analytically and empirically) by requiring a simpler DP-FL mechanism, fewer samples, and a less complicated analysis. To the best of our knowledge, these are the first DP-FL algorithms that successfully manage sparse recovery under the RIP assumption while only requiring n = O(vp) samples. Our experimental results on both synthetic and real datasets strongly corroborate our theoretical analysis. For future work, we will explore DP-FL algorithms that can perform sparse recovery without the RIP assumption.
9 Acknowledgement
This work has been partially supported by NSF grants CNS-2113893 and CNS-2225950.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference compuler and communications security, pp. 308 318, 2016.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next- generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp.
2019.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in 11 geometry. In International Conference Machine Learning, pp. 393 08--033. PMLR, 2021.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for diffcrential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pp. 394-403. PMLR, 2018.
21

---

Published in Transactions on Machine Learning Research (06/2024)
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and light error bounds. In 2014 IEEE 55th annaal symposium on foundalions of computer science, pp- 464 473. IEEE, 2014.
Raef Bassily, Cristóbal Guzmán, and Amupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pp. 474-499. PMLR, 2021.
Alexandre Belloni, Victor Chernozhukov, and Christian Hansen. High-dimensional methods and inference on structural and treatment effects. Journal of Economic Perspectives, 28(2):29-50, 2014.
Christopher M Bishop al. Neural networks for pattern recognation. Oxford university press, 1995.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for learning. In proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Securily, pp. 1175 1175-1191, 2017.
machine
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymptotic theory of independence. Oxford university press, 2013.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016.
Emmanuel J Candes and Terence Tao. Decoding by linear programmingg IEEE transactions on information
theory, 4121):22203 4215, 2005.
Yudong Chen and Constantine Caramanis. Orthogonal matching pursuit with noisy and missing data: Low and high dimensional results. arXie preprint arXiv:1206 200.0888, 2012.
Robert Clarke, Habtom W Ressom, Antai Wang, Jianhua Xuan, Minetta C Liu, Edmund A Gehan, and Yue Wang. The propertics of high-dimensional data spaces: implications for exploring gene and protein expression data. Nature reviews cancer, 8(1):37 49, 2008.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arxic: 02383, 2019.
Erik Drysdale. SurvSet: An open-source time-to-event dataset repository. arXie preprint or orXiv::203 03094, 2022.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Compul. Sci., (3344):211 2104477, 2014.
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression. 2004.
Jianqing Fan, Jinchi Lv, and Lei Qi. Sparse high-dimensional models in economics. Annu. Rev. Econ., 3(1): 291 317, 2011.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients-how easy is it to break privacy in federated learning? Advances in Neural Information Processing Systems, 33: 16937-16947, 2020.
Isabelle Guyon, Steve Gumn, Asa Ben-Hur, and Gideon Dror. Result analysis of the nips 2003 feature selection challenge. Advances in neural information processing systems, 17, 2004.
Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41st ACM SICMOD-SICCACT-SICAA Sympostum on Principles of Database Systems, pp. 227-236 2022.
Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, and Sanjoev Arora. Evaluating gradient inversion attacks and defenses in federated learning. Advonces Neural Information Processing Systems, 34:7232-7241, 2021.
22

---

Published in Transactions on Machine Learning Research (06/2024)
Ali Jalali, Christopher Johnson, and Pradeep Ravikumar. On learning discrete graphical models using greedy methods. Advances in Neural Information Processing Systems, 24, 2011.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. Tn International conference on machine learning, pp. 1376 1385. PMLR, 2015.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference Machine Learning, pp. 5201-5212. PMLR, 2021.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pp. 25 1. JMLR Workshop and Conference Proccodings, 2012.
Yulan Liang and Arpad Kelemen. Statistical advances and challenges for analyzing correlated high dimensional sup data in genomic study for complex diseases. 2008.
Yi Liu, Ke Sun, Bei Jiang, and Linglong Kong. Identification, amplification and measurement: A bridge to gaussian differential privacy. Advances in Neural Information Processing Systems, 35:11410-11422, 2022.
Paul Mangold, Aurélien Bellet, Joseph Salmon, and Mare Tommasi. High-dimensional private empirical risk minimization by greedy coordinate descent. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2023.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communicttion- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp- 1273 1282. PMLR, 2017.
Nicolai Meinshausen. Relaxed lasso. Computational Statistics & Data Analysis, 52(1):374 393, 2007.
Nicolai Meinshausen and Bin Yu. Lasso-type recovery of sparse representations for high-dimensional data. 2009.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275. TEEE, 2017.
Deanna Needell and Joel A Tropp. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and compulational harmoric analysis, 26(3):301 321, 2009.
Kaare Brandt Petersen, Michael Syskind Pedersen, et al. The matrix cookbook. Technical University of Denmark, 7(15):510, 2008
Mark Rudelson and Roman Vershynin. The dttlewood-offort problem and invertibility of random matrices. Advances in Mathematics, 218(2):6000 633, 2008.
Kunal Talwar, Abhradecp Guha Thakurta, and Li Zhang. Nearly optimal private lasso. Advances in Neural Information Processing Systems, 28, 2015.
Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Conference on Learning Theory, pp. 819 850. PMT.R, 2013.
Joel Tropp, Anna C Gilbert, et al. Signal recovery from partial information via orthogonal matching pursuit. IEEE Trans. Inform. Theory, 53(1))46655 4666, 2007.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv:1011.3027, 2010.
arXiv preprint
Roman Vershynin. High- high--immnssonal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
23

---

Published in Transactions on Machine Learning Research (06/2024)
Di Wang and Jinhui Xu. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, pp. 6628 6637. PMLR, 2019.
Lingxiao Wang and Quanquan Gu. Differentially private iterative gradient hard thresholding for sparse learning. In 28th International Joint Conference on Artificial Intelligence, 2019.
Yu-Xiang Wang. autodp: A flexible and easy-to-use package for differential privacy. https://githubb.com yuxi yuziangu/autodp 2023.
Larry Wasserman and Kathryn Roeder. High dimensional variable selection. Annals of stalisties, 37()A): 2178, 2009.
Tong Zhang. On the consistency of feature selection using greedy least squares regression. Journal of Machine Learning Research, 10(3), 2009.
Tong Zhang. Adaptive forward-backward backward greedy algorithm for learning sparse representations. IEEE transactions on information theory, 57(7):4689-4708 2011.
Peng Zhao and Bin Yu. On model selection consistency of lasso. The Journal of Machine Learning Research, 7:2541-2563, 2006.
A Differential Privacy
Differential privacy was introduced to privatize changes caused by individual clients (Dwork et al. 2014). For given function, differential privacy obscures the maximum possible change in the function's output due to the inclusion removal of a single client's data. Here, obscuring is allowed by introducing noise and, thus, a form of deniability in the function's 's output. Deniability allows an individual client to deny its presence in the dataset and disallows an adversary from linking the client or its data to non-privatized record. Differential privacy is significantly stronger than previous anonymization methods as il works even in the worst-case scenario when the entire dataset publicly released except for a single client's data. Here, we look at the precise mathematical definition differential privacy, simple techniques to introduce privacy, and its additional properties.
Definition A.1. [Approcimate Differential Privacy] For any two neighboring dalasets X,X' S differing over single sample, say that the randomized mechanism M S R is (c,8) differentially private if,
P.M(X) E e PH(M(X) E R. +
Definition A.2 (I2 sensitivity of a function). Given deterministic function f, consider all possible pairs of conformable neighboring datasets in the domain of f differing on single row. Then we denote f L2 sensilivily
D2f = max 11f(x) - fxx')ll2
x.xedomm [.1l
Thus, AgJ records the mazimumm possible change in f. due to a change a single row. Often each row belongs to a different client and thus, A2f will record the marimam change due to change in client or the inclusion or removal of cliend from the datasel.
We can achieve differential privacy by the Laplacian, Exponential, and Gaussian mechanisms [wwork et al. 2014). Here, we the Gaussian mechanism it performs better for multi-step (or composed) privacy algorithms. In particular, we leverage the Gaussian Differential Privacy (GDP) composition method for optimally tracking the privacy loss over multiple steps (Dong et al., 2019). Although, other composition methods such as advanced composition (Kairouz et al. 2015), Renyi DP (Mironov 2017). and concentrated
DP (Bun & Steinke, 2016) exist, we chose GDP for its superior composition performance for Gaussian mechanisms. For completeness, we state the connection between the Gaussian mechanism and the GDP privacy constant.
24

---

Published in Transactions on Machine Learning Research (06/2024)
Lemma 11. [GDP Gaussian mechanism (Theorem 2.7 from (Dong et al. 2019 Let statistic f(-) be computed over the dalaset X. Then, the randomized Gaussian mechanism M(X) f(X) + where 1/ N~N(0, 2af)) is p- GDP.
Lemma 12. [Restated Theorem 2.7 from Dong et al. 2019)] Let statistic f(-) be computed over the datoset X. Then, the randomized Gaussian mechanism M(X) = f(X) + where N(0,, Aaf)) is H
An important property of DP, known as post-processing maintains that no amount of processing on a differentially private system will cause the new output to leak any information than the unprocessed input. This is expressed clearly in Lemma 13
Lemma 13 (Differential Privacy Post- Post-Processing. Consider randomized mechanism M that is (e,5) differentially privale. Now, lel Moost be another randomized mechanism that can be applied to the oulpul of M. Then, we state that the output of the combination of Mpost(M(.) function group has at least differential privacy guarantee of (e,8) or higher.
B Compressed Sensing Theory
Let Q = (1.2...., be the overall feature index set and the support S S f2 of 3 be defined such that, $ [ili E 2 * 0j. By definition, [S] < (where 8 is the sparsity index of the dataset). For a vector v I2, let define Uw as the restriction of to the indices in W where W s Ω. Similarly, for matrix Q e _=* let us define the sub-matrix Qw Rnx[W] s.t. it only contains columns indexed by W(S I2). Our primary assumption for the data matrix follows the Restricted Isometry Property (RIP) detailed in Assumption
Intuitively, assumption for X, a matrix satisfying RIP of order K states that the eigenvalues for all K-dimensional (or smaller) sub-matrices derived from X, lie in a tight interval around Interestingly, the assumption holds for several popular sub-Gaussian random matrices. Construction of such random RIP matrices is detailed in Theorem 5.65 from Vershynin (2010). We note that although we use the random matrix construction a reference for our primary analysis, we only require matrix (even deterministic) normalized by vn that satisfies the RIP condition and and it should contain (probably) bounded values. Further details are omitted due to page limits.
Lemma 14. /Construction of Random Matrices satisfying RIP] (Theorem 5.65 from Vershymin (2010)) Let A E RRAP be a subgoussian random matrir with independent and isotropic rows. Then the normalized matria vn satisfies the following for every sporsity level & k & and every number 8e (0, 1),
Cklog( 22)
A
ifn
dk
8
8²
with a probability at least 2e 25 Here, C C Ck > O depend only on the subgaussian norm = max; ||Ail,, of the rows of A. Here, k the RIP order, and dz(-) the RIC. The exact construction is demonstrated below.
One instance of such a random matrix satisfying RIP, Raxp, can be constructed with the following steps,
For a given row X, independently sample the row's elements from a sub-Gaussian distribution s.t. each row is isotropic. v e IRP is an isotropic vector if E[ueT]] II.
The standard normal distribution satisfies the isotropic property. Therefore, assume X (O0 1), for all i e [m].j e [p]. We note that alternative distributions as detailed in Vershynin (201)) also satisfy the isotropy property.
Normalize X
Given an RIP satisfying matrix e Raxp satisfying RIP of order s with an RIC of constant Çes we note some useful properties (Lemmas 15 18 derived from the RIP condition ((Candes & Tao 2005
25

---

Published in Transactions on Machine Learning Research (06/2024)
Consider the set of vectors W (w R" w E W and by RIP and using |Xsws|le |x 2,
|| lo & s}. The support for vectors in W is S. For vector
(1 [
Ksswsl < (1 (.) 1
|| 2 & (1 + (
w" x Xw
(1 - (.)
< (1 (.)
(2)
w w
Thus, the following bound immediately follows,
(1 (1-63 Go) & min (X)s) max (X5 & (c)
Lemma 15. [Monotonocity of the Isometric Constant] If measurement matrix X R2xp satisfies RIP of orders K2 and K2 s.t. K1 & K2 then their corresponding RICs follow the same order i.c., SK, & (K. Lemma 16. [Direct RIP Consequences] Let S = Q be the support of the true model 8*. If 1;5= [S] then we can show that for the measurement matria X salisfying RIP with order and for any E RR,
(3) X & (1 (.)1lu[12
1+G ||lll2 < Xs) wwll & 1- ||w||2
Lemma 17. [RIP: Near Orthogonalityl Let S1, S2 S Ωs.t., S1 n S2 = Ø. If (1s1+1S) < and S1 u US = 5 then for the measurement matriz X satisfying RIP of order and for E RlSaa we have
| Ss ull2 & (isu+tss 1lull2
Lemma 18. Let S = Q be the support of 8 (our ground truth model parameter). If Ç. 1; = [S] then we show for the measurement matric X salisfying RTP with order and for any TR.
w & v1 Callw]12
C Useful Results for Privacy Analysis
Proof of Lemma 4 Consider two neighboring input-output pairs X, and X X', such that the pairs differ in single sample at row k. We approach this proof by first considering the sensitivity of the jth column (X;) and then computing the combined sensitivity of the columns.
A2(X)y,) max
[Ixx))
X3 vll2
k
max ke[n]
max X Xjk0y} & XMMM kE[n|
- A2(X 2PPXMrM O(vp)
Similarly, let us consider the sensitivity of XT xTXSs>
A2(X = max
||(X')TXX x X,ll2
ke[n]
< 2 max ke[r]]
[|| X Xxxlee))l1)
< 22
-AAXX"X & 2x v O
26

---

Published in Transactions on Machine Learning Research (06/2024)
D Useful Results for optimality of SPriFed-OMP
Lemma 19. Consider the term M = [1+ N where == Ti A.gA. , A ( (
v is any conformable vector and is the sample size. The remaining terms have been borrowed from Algorithm Note that each element in A has distribution of (0, p/1G)) We show that
|| & KMllu|l2:3
En Von
+
(o41)
Here, En chosen as per the lower bound of the smallest singular value of the random matrix XSA (by Theorem 1.2 from Rudelson & Vershynin (2008)), vpSkn from assumptions in Theorem 7 and so have that each in A.S. has the distribution [mivan,) NO0 1).
Proof:
||
[1[T NA
||0||2
Omin [I NA
||0||2
Omin [NA-1]
||0||2
+ min [N Miinl A-11
||0||2
+ 46n
[1/omaxx[44
nVa
||0|22
Here (1) follows from Lemma 30 and since mmax [K 1 mmm (2) is true since |] + K||2 k || where the identity matrix and K is some conformable matrix. Furthermore, with high probability, the minimum eigenvalue of the random Gaussian matrix is lower bounded by a positive value. This statement is true by Theorem 1.2 from Rudelson & Vershynin (2008) since here each row of 1 has the distribution S0, I.). Thus the random Gaussian matrix is positive definite w.h.p. Therefore, we have statement (3) since miin [AB] 2 amia [A] Tmin [ where A, B conformable Hermitian matrices. (4) holds subsequently from Theorem 1.2 from Rudelson & Vershynin (2008) by considering the random matrix n N with entries from the distribution sK,N((O I12). (5) is based on the bounds of the eigenvalues of a RIP matrix K with RIC Se+1 and order 5 + 1.
Lemma 20. Consider the term M2 = 1- I- -I+ -I=- We show that Mallz is upper bounded by KMs x XSA (as terms represented in Algorithm 3). Here, KM,
where N- T/'s AA and A
May 6,, (1+6++1)m
and KM, C2 19,
|elll KM, 11l112. Furthermore, ||Mil| [[ + -A--A/llll upper bounded by KM, Here,
nll 60117
Sy, C1 depend (polynomially) on the sub-Gaussion moment bounds of N/O, Rudelson & Vershynin 2008
Proof:
| 2 = ||I (I+ NA NI- 1
[| + NA N
2
KM IN 1|2
KM, E, SK
||-
27

---

Published in Transactions on Machine Learning Research (06/2024)
KM, En
1 n11 + Ss+1)
Here statement (1) follows by ||4 K|12 = k - |||] where I the identity matrix and K a conformable matrix. (2) is based on identifying a lower bound for M1 (below). (3) employs theorem 1.2 from Rudelson & Vershynin (2008) where the rows in n- NV have distribution of sK,N (4) uses the bound on the eigen-values of the RIP matrix A. To compute the lower bound for ||]]| we consider conformable vector
v,
| II(I -A-
Omin + NA-
(3)
||u||2
mmax (II + NA-1)
(3)
|/1//2
+ max (N A-1)
||0//2
1 + mmax (N) O ( (A-1))
||1||2
CryBen.
1 (m)(1-
(6)
||l||2
KM, 1u1|2
1
Ci 6A/P/a
xs1 4(1-5++1)
(1)-(4) follow from simple matrix manipulations, (5) is based on Theorem 2.4 from (Rudelson & Vershynin 2008) for matrix n N with values distributed as sK,NN(0,1) 1) and (6) is based on bounds on eigenvalues of matrix A
Lemma 21. We show that the terms 2-norm of the terms L1= XT (X 05 and L2
XE required in
our analysis are upper-bouss upper-bounded as expressed below. Essentially, L1 considers the value of y after multiplying it by the projection matria that removes cerlain columans of XSa (due to orthogonalily between these columns and the projection matrix).
|| & Cotillas, ll + /1 Satine
||2l|la & + (llass + + v1 SatiKe)
Proof: Consider the analysis for La.
XT S4
(Xsy ass +
|
ll2
n
X S
Xse a
XT e S5
Sx
1|2
n
(2)
(Go+1)laas lll v1 Sot1
(1) follows by the triangle inequality and the RIP definition for matrices XT./Vm, Xs. respectively. By the La inequality we further have ||æ||| & Vd||=l|o where x E Rdd. Clearly, with Lemma 36 we then have ||el| & / Vnn, w.h.p. where Kg /2e/2lop 2/Po where e, ~N(0, and pa is determined by our probability requirements. Now, for Le,
XT
Lg la =
28

---

Published in Transactions on Machine Learning Research (06/2024)
X (Xs, as +c]] 112
X Xs X3,1 e 1|2
n
(1 + Sa+1)llasula + v + Sot1
(1) follows since y Xs, asa as +
(2) follows by RIP definition and Lemma 18 for the first term and
Lemmas 36 18 for the error term.
D.1 Bounding the noise terms in SPriFed-OMP
Lemma 22. (Bound small inverse term] We show that for a small value 0 < <t<) <x1, I & 1 + ut if
B-B, where B, is an upper bound of t. Furthermore, v (1,2).
Proof: Suppose, we assume that - < + vt holds. Then, we can write the inequality simply,
(v 1)t vta
p-1
&
Setting, B, = " we obtain v == --B, We note, that for the second statement to hold, we require that
1x and for > 2 the statement holds trivially.
D.1.1 Note on the difference between the basis columns and the non-basis columns
We present the analysis for noise terms when only a single feature j is picked each time (Lermaas 23 However, we note that the same result holds when we pick the set 5 instead of j alone. This is true since the total cardinality of the first matrix (either for the noise signal matrix) is less than 1. Therefore, results from RIP and other singular value bounds apply to this case well. This is particularly important for true basis columns. However, for the non-basis columns, this is not useful as the total cardinality of the non-basis set and the SPriFed-OMP selected feature set will easily exceed (closer to p).
Lemma 23. The noise terms
|لlll| = || Xss
-I++ a (X3, -1-1 St
11 || X s. (X Xsa)=
- A (X3, Xsx) - St
(Theorem 7 are upper-bourded such that,
11 112 < 8 Sot1kKgg
2log( )1 + vCo+1) PMM
pb
(VI+ C 1ll 2ll Re)
82
1n/lla < s2150
2og
(1 + uCo+ )KM
pb
(V1 + Co+
I ||| + kie)
Here, terms are borrowed from Theorem 7 Lemma 19 and pa is base failure probability defined in Lemma 36
Proof: We provide the proof for the 11(7)) ||a term. However, proving the inequality for the ||,/|| is straightforward.
1167)112 falll=11xff
X (X
Xsa) 8 (X7 Xsa)
29

---

Published in Transactions on Machine Learning Research (06/2024)
(X5x Xsn) 11aa)_(a
X
X XSA
X5 XSay
=n|
n
n
ABS
X SA
XSA 1-1
[I
n
7A
X SA
XSA -1
X2
1|2
n
n
(1)
Sat1
A88 A 1|241
11
|2|1
(1
(o+1)
(2)
n6s+ill
1984.84
11a(1 (S++1) 3KM
(V 1 S0+1llas41 112 + ke)
(3)
<
52 Catiting
82 2log(
")(1 )1 + vCo+1) 2kMM
pb
Ke)
l12. The middle and last terms are handled by Lommas 20 and 21 respectively. In (2), we replace the bounds for the terms M, La using Lemmas 20 and 21 respectively. We replace the denominator by using the bound in Lemma 22 Finally, (3) follows from simply noticing that each element in Mis
Here, (1) follows from Lemma 17 for matrices and Xs and bounded eigenvalues for II(
X2 X5A)
SA A has distribution N(0, s²x)),
L2 Lio inquulity and lemma 36 The bound for the noise term holds with probability close to 1 of the
form pb- 1 - kie k2 = where h1, k2 are positive constants.
Lemma 24. The noise terms
Inaalla r2||
XT XSA
XI, JTAXSA
-1
1 [1-1-
78 A
SA
XT. XSA
1111
n
n
11
18
X7 S
XSA --1
1733
||25 S.
n
1
XT XSA
XT XSA -
11(2)1'l12 ri|l
I- [I+ AA
XT XSA -17-1
A
X S.
XSA )-1
MhsA 11255 $ S
n
is shown to be upper bounded such. that,
11(r51) 1'122 & swaaaaiig
2 2oog(
2s
(1 +
pb
2x (1 16 2
Ilrallla laaa SNa 2 logí
Ph
The terms follow the notation in Algorithm Theorem
Lemmas
20
pb is the base fasture probability
defined in Lemma 36
We first demonstrate the proof for the case when j$ St. The proof for the j E S case follows simply by replacing the first inequality involving the term X XSA-
Proof:
11 112 n/| XSA
XT
X
7 A.SA
1 -
30

---

Published in Transactions on Machine Learning Research (06/2024)
X7 SA
XSA
)-1
X
SA XSA )-1
|/2
71
n5++1
||
11
(1 (a+1)
n
n n(( 1KM2
7713 1/2
Sa+1)
n2
M8 st1s1 2 log
20
15+118M
(1 (o+1)
2s
1ka6a+1 2 logg ph
(1 +
Here, (1) follows from RIP properties in Lemmas 16:17 (since $ SA) and M2 is defined in Lemma 20
(2) follows from the bound in Lemma 20 (3) follows from Lemma 36 L2-Tep inequality and the Gaussian
Mechanism for differential privacy. Here, (Thh ) w(s,, And Kg is defined in Algorithm 3 direct application of Lemma 22
(4) is a
l112el22 2. (1(222) ( l|2 which both have the form nlll " X5 X5 Xoa
Lemma 25. The noise terms
[I+
"
X3 SAASAAy
) 1-1
A
X3_ Xs )-1)
x3 " 1l2 for sets j E S& and j & S respectively are both upper (VI+ Ca+ las lle + ka) (1 vSot1)). The notation is borrowed from ps is the base failure probubility defined in Lemma 30
bounded by / 2 log( Algorithm and Theorem
32
NNM Lemmas
Do
7
22
20
11
12 = n1|
785.8
XT S.A B
1
11-1111
11+
M8 A
1
xT.
SA
X S
-11-1
n
XT XSA XSA)-
XT
18SAA8A
SA
n
n
(1)
11,,9 A
n2
1|2
So+1
KMa (v1 + Satallass 112 Ke
18, l|2
n/
1 1 So+1
m||
18
||2kMMs
(V++ Gttlloas 112 Kie)
(1 + V(--1))
(4)
///
782.5A
11o0KMM (VI+ Sati Satillasalla kic)
(1 + v(=-1))
Vpskipp
2p 2 log
_
)KM, (VI+ Coti Gotillasll kie)
pb
(1 v(o-1)
Statement (1) follows by substituting for the middle and last term (from Lemmas 20
21 resp.), separating
the noise vector and bounding the singular values of x Xa -1 (2) follows by bounds in Lemmas 20
21
1
31

---

Published in Transactions on Machine Learning Research (06/2024)
(3) is direct application of inverting the denominator term with Lemma 22 (4) uses the L2 Lop incquality. The final statement uses Lemma 36 distribution of the noise matrix and bounds it for the appropriate set
and failure probability as shown in Lemma 36
Lemma 26. The noise terms
|| Massll2.11 (1(75s) ll2 over sets E Se and j $ S* respectively both have the form
78 nl
X
XSA
[I [I
X
Xs
11-1
72
n
n
M
X SA*
Xsa )-1
T7SA 1/2
71
n
n
are both upper bounded by 2KM, (1 + v(s+1)
(ogg( (2) log( (e). The notation follows from Algorithm
nm
and Theorem
7 Lemmas
22
20
ps is the base failure probabilily defined in Lemma 30
XT
XSA
X7 XSA
nl|
(-1(1-
-1p-1)
X
1775 1/2 XSA
S
n1
(1)
M2
185.8a
T/IA l12
||2||
6o+1
(2)
783
The
nnM, (1 + US 16
/s|l
/sl
1100
(3)
1p8
2p
28
KAAa (1 + v(s+1)
Kig x.p2
log(
log(
n
Pb
Pb
(4) 28M (1 vC++1)
log(
2p
log(
28
Kn
pb
pb
Statement (1) follows from bounding the eigenvalues of X3_ Xs n)_ substituting the value of the middle term as M2 (from Lemma 20 and separating the noise 2-norms. (2) leverages the L2 - Lox inequality for the noise 2-norms, bounds M2 with Lemma 20 and inverts the denominator with the simple Lemma 22 (3) follows from noting the variances of the noise matrices as being proportional to and s and using the maximum concentration bound (Lemma 36 to pick an appropriate value. K2 and Ki are picked by the privacy mechanism in Algorithm 3 Depending on the set we are maximizing over for j we can pick d s (basis columns) d p (non-basis columns). Ps is some appropriate base probability that is generally quite small. (4) follows by substituting vpSKn.
(n ) llz is upper bounded by
2 22 Map
1 Lemma 27. The noise term || l|2 Ps is some base probability that is quite small.
Given, jE T,d [T] and
Vakn
Proof:
(11 )a
vp Kap
2p
1 log( 2p
ps
)kp
&
log
Ph
Vakn
where the last incquality holds because of Lemma 36 and since (n=-); ~ NN kzP) where up picked by the privacy mechanism in Algorithm
E Proof of Main Theorem 7
We will use induction to prove our main result as noted in section Step 1:
We show that we pick the correct basis in step with high probability (w.h.p.). Here, the correct
basis implies that we choose the column index belonging to Sy. First step from Algorithm written
32

---

Published in Transactions on Machine Learning Research (06/2024)
argmax Our strategy is to find the maximum correlation's lower and upper bound under the assumptions j e Ss and j $ Ss. respoctively. Denote these correlations C' and C' respectively and let their lower bound and upper bound be C. and C₂ respectively. If If < C. then the correct basis (from S.) is chosen at each step. This statement is true since C+ < C+ implies that the upper bound of the maximum correlation of non-support columns is smaller than the lower bound of the maximum correlation support columns. Thus, we first atlempt to find the values C+: C s0 as to equate the inequality above.
Thus, the lower bound of the maximum correlation of support columns is given by,
C max ((5))) JeS$
max X3 y + 765))) JESs
| Sq y 1((55) ll2
(by L2, Loo ineq.)
V S4
X
vlle
max ((55g )ul (by reverse triangle inequality)
JeS
Suppose events F1, F2,.... F., each occur w.p. (1 Pa) Event Pkk, [s] indicates that M(55) Ba for some Ba > 0. This could be rewritten as Pr[ Pr[M )2 & Ba] = 1 - Pa- Invoking Lermaa 32 and
since MM777 )el ~ N(0 og) we can write Pa 2e 2 - B. = soy/ 2log( p.. v 2log( 2.
estep vP Ka v/
Mp
where Ka / 2log( Kp. To bound the maximum of the noise terms, we require that all events En, k [s] na Extep
hold simultancously. By the union bound (Lemma 33
Prfmaxces, M,5)) > Bal Pr[UKESe Egl & Pa- And w-p. Pa can say Σ Pr[F[]] Pa- Therefore, Prfmaxtes, (355)x ) Ba]
KES*
that,
|| C
5112
24
|| S4
Xs as
+X
V
(1)
XXT SM
X asslll
|XT, ell2
Vs kayp
X7 Xs
n
OSS
|| elle
Ka KavP
v
(1) follows by the roverso-triangle inequality. We know that by construction X/v/n has isotropic, sub- sub-gaussian, independent rows and thus satisfies RIP of order + 1 [1] Thus, by Lemma 16
C n(1 - (6t1)llass
vn
vn
K D
V
X3
v satisfies and RIP of order s ++1 we observe that, || v(1+ 6. |nlel lo- Combining these two results, we have,
From Lemma 18 and since
ell2 & VI+ Cstillell2 &
vin
C2 n0(1 Set1)llasala nV(11 + Set1)lle|la
RaVD
V8
Consider the events B1, Bg.... ..., B, s.t. Pr[B,] = Pr[je, < B&] (1 p.), [n] (for some probability
Pe [0, 1]. Comparing the expression with Lemma 32 and noting that No0, we observe that
33

---

Published in Transactions on Machine Learning Research (06/2024)
Be = Vev 2log( 2 = Re. We bound the probability event with the union bound s,t,, Pr[B] = Pr[maxxe[M] leal Be]. Therefore, Pr[Ba] Eiemm] Pr[B:] & n pa- Thus, Pr[B] 1 upc- Thus, w.p. npe event B occurs and thus,
C x n11 - Sct1)llass ll.
(11 (5t1)
nn.
Kay = Cs
v
Next, identify the expression for Cz For any j S. let us upper bound ((%)
C' = max
1(% )5
S*
max S+
X y + 7((5)) ),
X X S4 S.S + x3 e (15)))
max #$5$
||
Xs oS 1|2 11xx7el e/12
max jES
(((5))) )s
Xs
X
n/|
asall2 + vTl
elle
+ max (n(6)) )5l
vn
JES
(1) follows by the Lz-Loo inequality. Considering event B again, we have that Pr[B] Pr[max les & B.] and occurs w.p. 1 1- rtpe.
Further, consider events Ck, k & A.s.t.,rr(C. Pr[lnco )al Bdl (1
Pe).
To bound the maximum
of the noise terms, need all Ck, k [p 8] events to hold. By Lemma 33
Pr Pr[maxx#5 19676 la > B₂]
Pr[unes, Ci] & Σ Pr[C]]] (p- 8) Pc- Therefore, Pr[mmax4ss (666
B. 2 1 (p 8) Pe- By
KES#
Lemma 32
Bg VOV' 2log( 2) = 2log
Pe Extep vp = Kie vD.
2 Fp
Combined with the RIP Lemmas 16 18 for any $ S², get the upper bound,
c' < nn ll2 + ny 1 Cot1N, Keyp C'
Note that by the union bound (Lemma 33
events A, B, C hold w.p. at least spe -2mpe (p- s)pe. Let
Pa d
P
Pe
Pe [(p-a)-
Po
With probability 1 Po the bounds, C2, C, hold. Let us identify the conditions for Co C2.
no nllas,, ll2
1
n (12(1
Vs
1
+ mn/++ G441ke(1 + Vs
) + (Ki + kc)
Thus, put logether we obtain the following condition on the RIC, So+1.
Sot1 a|las, ||2 ny 1 1o (1+ V8) (Ki + K
n3 aal 12(vs+1)
n nllas [12 /2(1 + /S) - (Na (ic)
nlloss 11(2v++
where the last line follows from the fact that Cot1 < Suppose, we can bound V2(1 V8)ns,++++ ((a +ie+ & n|las 112
allas ll2 that would give us Sot1 < 2n| [[2(v=+1] = 2(V++1)' It remains to characterize the condition for
v2 + Vo)RKe + (Ka + ke) & allas, to hold. Thus, we only need,
2v2(1 + V8)nke
2(kr, KcD
n >
||as l|2
||as 122
34

---

Published in Transactions on Machine Learning Research (06/2024)
n(1 2v2(1 + /
2(Kaa + ko)
| 112
las 1l2
2(Ha + Ke)
Vp
aas 1/2 2222(1 + vo)
Note, Ke v 2log( ) Si. and so n 22( Vp plg((p) 1las ll ). We also require that 1|as,1l2-2220
2/2((1 + vS)ke
Eatep
which is generally applicable since Hi (dependent oe) is generally smaller comparable to 1.
Step (I+1): By induction, C, < C holds for all steps from 1 to We now prove the same for the (1+1)th step.
Case A: Analysis for when chosen column j Sa Let us determine a lower bound for the correlation for when the column chosen belongs to the true basis,
C max (75)sl ,68
max (1ō - -((3sa) 7 J68
max mmx|(X)] [X] + 11n5)s)
JESs
- -X] XSA + TT ) X Xsa + 188 )
(X ThSx)) )
We now separate the signal and noise terms in order to analyze them further. Consider the following ex expression to relate the true (i.e., non-private) signal- Strues the privatized version of the signal Spii for the jth and the various noise values (denoted by the terms) for the jth dimension where j E (1,...,..
Sprie
(X + ((-5)))
- (X3 XSA + 118,,8 )(5 XSΛ + +1
(X U 1TsA)
X5y - X. Ss (X SA
XsA + 185A ) -1x
Xs) XSA + TBS (11sa))
(nons, |x55 XSa + 1788
)1((3
Tis
- -no 1x55 XSx + ) (T(MS))
+ 7(75))
We apply the Woodbury Identity-Kailan Kailath Variant (Eqn 31 to each expression marked by an asterisk to obtain the following simplifications,
Spoley
# *x - X X9, (X Xs,) Xs,
-
X3 X (XA
M 185
XXfAXsal -1x
35

---

Published in Transactions on Machine Learning Research (06/2024)
1/11 = X3 Xs, (X Xs,) -
1/22 = 1 (X3,x (ssa)~Mal
1/33 * 3, (X5, Xsa) (issssaMa |M2ths
Here, M1 = [1 + s A and L2 = x3
(X Xsa 1 M2 = (u (1-
-L + s SA (X Xsx) 1
(x Xsx)
We look at the correlation values for the true support. columns and non-suppori columns.. Let us suppose the lower bound and upper bound for C,C' (defined below) are C2 and C₂ respectively. We wish to identify the expressions for C.. C₁ and compare their values C² < C2 so that we always pick the column from the true basis (steps follows similarly to Step 1). For j E S we have,
Cj = Sriuee + . + 1/2 T + T/2 + vasal
1
/ Struell2 l1 2l 1
vs
||aallox ||1s2|loe ||
Similarly, when j $ S,, we have,
C₁ (S + (nH) (md) + (mbsa'' (rize) + (r54)'1
< (1((rre))'1)
+ 11 + 11(/2)122 + 11 Vlla + 11((is2) + 11
where we leverage the To inequality, the triangle inequality, and the fact that each term Strues Vi v/2, ng is I-dimensional and thus their L2, Log norms are the same.
We now bound the signal values,
|| Struuell2
||x33 [I Pslull2
|| [I - (X 0S8 + e)ll
(1) ||xT 5/
(Xs5 0:55 + <)]l2
x
(X3
St
aggy +
n2|l
XT.
XSA
XT XSA -1
XT (X 1 ags + E)
5t
(2)
XT.
X 0.59
XT
|12 -
1/2
XT. XSA XT XSx
XSA -1 X [X
[5,(X52 0sgg + c] 112)
n
(3)
nco+1 [|Lll
n(1 -6st1)llass Ila-nn1++ Cot1le 1 - Sat1
4 n(1 (61-611)ll 1 Cot1ke
nl++1 [Sstillasg ||a + v1 + (+tike]
(1 (s+1)
n(1 - (ot1)llass I|2 v
VSo+1ke
n6s+1(1 15++ ll| + /I vc++1n.]
We observe (1) since the projection matrix mullifies the impact of the columns already picked by OMP. (2)
follows from the reverse triangle inequality and by definition of y. (3) follows from Lemma 18 and 36 for the
36

---

Published in Transactions on Machine Learning Research (06/2024)
first and second terms and Lemma 17 eigen-value bounds for the third term. (4) follows from Lemma 21
(5) follows by Lemma 22
Case B: Analysis for when chosen column j E St Let us determine an upper bound for the correlation when the column chosen does not belong to the true basis. These columns are also referred to as non-basis columns. For the non-basis columns, we consider a single column each time. By definition, the non-basis columns are separate and thus disjoint from the true basis set, and thus Xs; is independent of Xsy. Consider any j E S
| brue
| [ Ps](Xs, os
+6]112
(1)
X Xs aS5
X3e e
ml
||2 + r2|l
112
n
71
X7 XsA
X AS X
X5
+
m/|
12
n
11
n
n6s+1 l12 + ny 1 + Sot1Ke
n6--1 [setlllasg || + /1 Sot1Ke]
- Sot1
(8)
$ nestillasgl 2l2 + ny uSs+ike
+ n66+1111 (5411 || /I P5++1ke]
(1) follows from the triangle inequality and since 1-dimensional value a has ||al| xc ||a/|2. We have reduced columns in (1) for the measurement matrix due to the projection matrix 1- Ps. (2) follows steps identical to |Stuuellz except for the first term. The first term uses the approximate orthogonality property (Lemma 17
due the Restricted Isometry. By the union bound over all j $ Sg we can conclude that the ||St Ioo is upper bounded. (3) holds due to Lemma 22 We bound the remaining noise terms in the Appendix section D.1
We re-use common concentration bounds for bounding the values of maximal noise contributions across matrices and vectors. Since keeping track of such values is non-trivial we note that, the number of dimensions and the stopping point s of our algorithm are both finite. Thus, given that we have several highly probable bounds with the form e where both ki, &2 are positive numbers. Thus, the overall probability bound for our result will hold with a similar form well mainly because our iterations are finite and small (s)
A note about the probabilistic concentration bounds:
Combination of Case A and Case B: Therefore, now, we can begin combining the two bounds for this induction. Or more appropriately we compare the lower bound and upper bounds of the correlations for the columns picked from the true basis and the non-basis sets respectively. We have C² < C.. By combining the maximum values for any columns we can compare maxjes, C2 < maxjes, Cj and substituting these terms we obtain,
1
Vs Strueel2
2|S + (Irrilla + 11 lla)
(Inilll + 11(g))1l + (1lva 1102. D'1'/1111, (11))
(11v22la + 110g))) + (11ssslaa + I1Gds) (1a)
We simplify by substituting the noise bounds derived in previous Lemmas signal norms ||Strell22 and |ruelll
24
25
26 as well as the
37

---

Published in Transactions on Machine Learning Research (06/2024)
nl1a3,,1 112 > n(vs+ 1)6s+1lla3,lle
+ 11+1++1/+++ MSs+1Ne
+n(v++1))+ (1 ((s+1)llaas 112
+m(v=+ 1 + / )
+1 1(++1) (52(1 (v 1)
+ (1 + uSo+1) (1 + (v+ +0++1 ++)o++))
3/2 K31 (1 + V 1 + (v+ 1)(++1)
+ 2 pS (1 + MCs+ ) ||
+ /PSNS32 (1 + 1
+ 4 Vps²
133(1 + v(++1)
+ 2 vps K2
where,
2s²
K1 KgKMa
2 llog
pb
28 Ph
Kai KgAMM
2 log(
)
2(p
K32 Kap
log(
pb
8Hi
2s
2(p
K33
2oog( pb
log(
Knn
pb
2(p 5))
Kg Kap
2 log(
Pb
and ps is the failure probability used in the Lemma
36
To identify bounds the various terms in our system model, we allocate the left-hand side budget of nllaa, 212/2 appropriately. Therefore, we obtain, the bound on n,
2 2/pSHia2 +(++1) ) n/ nllaš,ll2 b 4/pSK32 (1 + 36o+1)312 =00D)
2
(3)
Similarly, we can obtain a bound on the RIC, Co+1, by allocating the budget of nllas, 1l2/4
n|lasa1l ll2
> n(vs+ + 1)6stallas,,1 llz
4
1
C6+1 4(V++1)
(4)
Now, the Ke terms can be combined such that,
22/ (1 + vC.+1) + n + 1)(1 + vC++1)
38

---

Published in Transactions on Machine Learning Research (06/2024)
+ n(Vs 1) + 1
+ 3/ (1 u (2 (v 1)(++1))
EKe
+ nn(s 1)(1 + v(++1)
2 WI++uo++
n11 + vSa+1)312
+ //22 (1 + uS++1) (1 +1+ (v + 1)G++1)
Here, these inequalities arise from the first two bounds on vp and the RIC C0+1 (Equs. 3 and dominating term should be n2 /5 1)(1 + v(s+1) long as,
4
Clearly, the
s Ki (1 + ((o+1) (1 + (v 1)(e+1) & n(v3+11 -
5/2 x1 (1 vC.+ 1) (v 1)(++1)
(5)
V +
Thus, the Kg bound can be obtained by assuming that,
1
4k.n(v²+ + 1)(1 v(++)) &
16 n ll2
11 112 -he < 16(Vs+ 1)(1 + v(++1)
(6)
From the remaining terms which are independent of both p and n, pick the dominant term to obtain another bound on n in terms of
n nlla3,lla
5/2 K2 + 1(++1) 5/ + (v 1)6++))lla ll2 $
-n > 3/2 K1 (1 +c++1)
(00-+1))(((1))) 5/2 (v 1){++1)
(7)
We see that the remaining terms extremely small and can be easily bounded by the remaining budget.
F Proof of Main Theorem 8
Before proving the convergence result in Theorem will include additional results required by analysis. First, calculate the upper bound on the l2 differential privacy sensitivity of the maximum absolute correlation in Lemina 28
Lemma 28. Consider design malrix X E Raxp salisfying RIP of order + 1 and with RIC Set1- Now given the correlation grailatioongrddentt Cj (as computed in Line of algorithm Z for any j [p], we show that the Toz sensitivity of Cj is upper bounded by the following values,
I1(x))s 100
v VI+ SatitiE) Be
A2(C,) 11 28 +2V5X2
Sot1
1 Sot1
where an is the underlying ground-truth model, Kig = / 2 and oe is the additive system error's standard deviation. We also need to assume that Est1 t/2 and
polo,
6s u.2Cxx2,0e x9 (2og(/2/pp)) Here, the result. a G..))²
holds with probability 3pp-
Proof. Consider arbitrary adjacent datasets X, X' R such that they differ in only their 1th record/row. At any iteration of Line 4 in Algorithm the set SA of basis identified until now has been fixed. Furthermore, note that the private model received from the server before the current iteration is also fixed. Denote this
39

---

Published in Transactions on Machine Learning Research (06/2024)
model by 7a where a is based on the currently predicted feature set SA and 7a denotes the privacy-related noise added to the model using the NOISY-SMPC algorithm (Algorit hm 1. Note, here we refer to the model as fixed due to the differential privacy post-processing wherein the model has already been privatized, and thus, future processing will not affect its privacy. In comparison with standardized private methods, we could consider this equivalent to using the same privale model while computing gradient sensitivity in DP-SGD under FL. constraints. Thus, the la sensitivity of the correlation of the jth column (denoted as C₃) can be computed as such,
A2(Cg) = max |x] v - (x 3 + x2 Xs, na) - (X' )3 X's (a + na)l2
km[ml
max KE[M]
[x]] (Xs + - Xs - ((x') (X's as + asyas))) + |
mmx|1(Xx xx) + 11x3 XSΛ (x Xx ((a))s) a)ll
kE[n]
+ |[(x) Xs2 - (X (x 1 83 (ao)s sx || |
2XMKK++ + (I3A4(as)) 89 || | - a]]l) + ||
Here, A = Xs, AA = = -Xyxss + X S AA = Xs a + X s a= (X (x X
and K2 (2logg2n/ppp)) where is a small positive probability, We also see that
|| = 1|x XxxXsssaDa
& XMr(IXXA + ||
< (I + |X
< <//XX
Similar results can be derived for other terms in the expression for the correlation bound. Thus, we simplify the correlation bound such that,
A2(C,) & 2XMMa + 2/ (l |alll I1(a))s a)ll
Now, suppose without loss of generalily, suppose a is developed on matrix X and feature set SA then we have,
X = (x3 (Ks, (a+)su + Xsx (0x()))) + +s) XT, (Xsg, (a0) +s)
(aa)ss + (X3, XSA)
G++ [1 -I/a - (a4)sall & 1 Cot1
v1+ Co+1Ke
1 Cst1
Here, the final set of inequalities follows from the inequalities (1)-(10) below.
Furthermore, consider the value of Na. which denotes the noise added to the model via the NOISY-SMPC mechanism using noisy correlations. We can compute this exact value using the Kailath (Woodbury Variant) (Equ. 31 and the value is defined as follows,
T/2
(X SA Xsa)
(MTSA 7832 (T+ (XF, XsA) n880
(1 (X XSA) - +Tea))
We now note the following l2 bounds,
(1)
max
A AAlla
& 2v
ke [m]
(2)
max ke[n]
X (X 3
& 2X
40

---

Published in Transactions on Machine Learning Research (06/2024)
X (3) S & V8XMUM
(4)
1 1 Sa+1
v 1I+ Sa+1
| = [1(X5A x 'x vl = |1 X (5,) (Xs, a2 +
&
|x4l
Rig
- Ss+1
1 --+1
Ka
X
84
Xsa
--|1
(5)
1
n
1 Cu+1
(0)
/28 (2///p))) YM
11
11
14a
(7)
sCIX3
(8)
[I + XSs) Xsa) (
)
$
XT XSA
(9)
||
$ + Cs+1
n
XfX4
(10)
Sa+1
Here, incqualities (1)-(3) follow from the boundedness requirement on clements of X. y. Incqualitics (4)-(5) follows from the RIP condition on X/vn matrix. Specifically, in (4), Kg /2g=/llg(22n /2 generated from
Lemma 36 Inequality (6) follows from Lemma 36 where elements in 7hs have distribution No, (2slog((e)p))) Pa
Inequality (7) follows by noting the inequality of largest. singular value inequality for random matrix inequality
from Rudelson & Vershynin 2008)) where the elements in 782 are from distribution NV0, y²). (8) follows
from Lemma 19
(9) follows from the RIP property of X/v Combining inequalities above, can find the
bound on ||
28 log( [2s/pD)XMUM XMMM 11 1 (s+1)
sC1X
28 log (2s/ (s/pb) XMUM VEXMUM
||
[1 Se+1)2
1//43
2s log (2rM
X
2 loogg(2:) (2sppp))))
+
n11a(1 - 1
nusa(1 Co+1)²
where this bound holds with probability 1 - 2ps, and is small positive probability. We quickly note that given the (sample size) in the denominator, then say that | < if
6s 6s"Cx / 22og(22//p))
13(1 (.+1)
We now continue finding the upper bound of A2(C,) using the incqualitics computed above,
A₂(C,) < 1+ 2X + 2 sx (1((a)))ss)))))))))))))))))))))) 100 + (s+1l(as)) ll2
/ Sat1
1 Co+1
1 Sot1
1 2XMSs + 2/5x2 [1 )ss lbo
V++ Cot1Mi
Ct+1
1 Cs+1
= 1 1+2XX MK: + 2/8X
* Be
where we assume that Co+1 < 1. and Nia l1 llke
iite
I-6et1 +
1-50+1
F.1 Performance of Algorithm
Here, similar main theorem we will demonstrate that Algorithm 4 can recover the correct basis w.h.p. Again, we will use induction to prove our result. We note from our proof sketch that the first. induction step
41

---

Published in Transactions on Machine Learning Research (06/2024)
for both the current theorem and main theorem 7 are the same (since the correlation and the gradient have the same value for linear regression model. Thus, we can immediately proceed to prove the induction step. Before proceeding, we restate the preliminary steps of the induction.
Step 1: Here, we show that in the first step of the algorithm involving picking the feature with the highest absolute correlation, we will pick the correct feature (í.e., the one from the true basis set). Similar to Theorem 7 we find a condition on the sample size such that the lower bound of the maximum absolute correlation of the true feature set is greater than the upper bound of the maximum absolute correlation of the wrong feature set w.h.p. Thus, we need to find the conditions that ensure C+ > Cg where C2 and C2 are lower and upper bounds of C and C' respectively. Here,
= max X y + 76)5)) >/1 JES&
C max jeS
X3 v 71:5 )sl
and the rest of the notation follows from Algorithms and 3 Note that the proof follows exactly as Theorem [ss step 1 and the sample size condition remains the same.
Step (I+1): By induction, C. > C22 holds for all steps from to I. We will now show that a similar result holds for the (1 + thth step for Algorithm
We first note the private correlation value is,
C = Cz=X, x Xsa (X5, XSS + 78 ) (X SA V/ + (hes) + +1,
X
= =xīy- - X7 XSy Xs,, - (X3, Xsa) 1 + 11 (X Xsa) 1 (x3, Xss (X y + mhsn)
+
- -XţU- X7. Xs Xx/xs Xs (X5, Xss) 11 X2 X7 Xs (X XSA) ) 1' "Ass + +11,
XsA)
Xx Xsa) (1
1 22 (x XSA) -1 118 (X5, Xsa) 2(3520) + +haa))
where nc, o20, oc vbBe Bc Vs 2X and TTSA NOO, o I,) and 18 Ay
N(O, & u3 I,). Note that the first term is the true correaaiton and can be re-written as Xi (I - p)X3, y where P X5A - is the projection matrix.
Case A: Analysis for when chosen column j S (true feature set except for features already chosen):
First, will find a lower bound for the maximum correlation/gradient when the features are chosen from the true set (except for the features already chosen).
1
ke >
|Cyll2
V3
(1)
[1XT (I (1-P))ll1- - |1 Xs, (xH,
Xs,) (es,)~mma Ms 1l2 -lmec, ll2
V
1133 Xsa (X (XI, X5x) (11
178 s. ss (XT, Xsa) Ksa)-1)118 )1)))~)))---- >>
31 (xT, Xsa) (X + the ll2))
-
(2) 1
1
|x3g (1 -
X Xss S (XT Xss) J 122 - 10-1,1,,11 11x
Vo
| Xsu (X3, Xsu) (1+ Tīi x v (X3,, Xsa) - (X3, - y + Tha, ll
n05 sn
88
n11 Ca+1) (441)11as511 ll2
1
1
E|12
1 XsA
(X S XsA) XT Su (Xsg asy + E)ll2
Vs
Vs
Sa+1 v8(1 (o+z)
VDBEKt
So+1
|1 12
Il (X5, + 1TS )|/2
Up
Vs(1
- (++1)2
42

---

Published in Transactions on Machine Learning Research (06/2024)
(4) n(1 Sa+1)llass ll
nL | 12
|x5gell ella
So+1 |X E|12
V8
vs(1 - -So+1)
Vs
vs(l - (--1)
So+1
VDBONp
So+1
112
I1MASAI (X y + Thi ll1
vo(1 So+1)
Hp
V8
(0+1)2
(5)
m11 Sa+1)llasss 1|2
l|2
1 -
nll 1
Co+1)NiG (1 1 S041
S071
V8
vs(1 (041)
v
2XM
vpBOKp
C0t1C15555
2XMUMN.
Mp MoV8(1 So+1)2 (1 + (at1)llass + his
1s(1 So+1)
14a
(6) n(1 (ot1)llaggll ll2
n
n(v1
Vs
vs(1 - S6+11 va(1- (4+1)
2X MXM
vDBcKp
C ((1 (s+1)llass + Aic +
2X 2X
1s(1 - So+1)
Pp
Ps S6+1)2
M4
(1) follows by reverse triangle inequality. (2) holds due to the 12-1æ inequality. (3)-(4) follow from the RIP
propertics of X/Vī as described in the incqualities in the proof of Lemma 28 alongside the Lemma 36
where K
2 log( 22) where ps is small positive failure probability. (5) follows from Lemma 36 where
Kg 2 log( 2x and Theorem 2.4 (upper bound on largest singular value of random matrix) from Rudelson Pa
& Vershymin (2008).
Case B: Analysis for when chosen column j S::
We now compute the upper bound on the correlations of the features not in the true set.,
|0,|| < 10lll XX] P)alla + |X] Xs] Xs (X3, Xs2)= TTs
'' 1l2 + || l22
Xx] Xss (X Xss) -1 + 185 S (X Xs,) -)M88A (XT,
X
S4 XsA) (X mns))lz))
W +
ypBoK
| (X asy asy + +)l12 + ||x X (X 1sa)-1X3 (Xsgasg +
Na(1 Co+1)
Pp
So+1 Ci Civ (1 (++1)lllsss 1l2 + Kic + 2XMUMMKi
Ms So+1)
ncstillass 1|2 + n CatiNe + Ps (ot1)
2VXMMMMNaGot VpBckp
So+1
Pp
G++Civan (1 (s+1)llas,, 1l2 + + + 2X
+ ps(11 - (o+1)
(1)-(2) follow the same inequalities as the one developed in case A.
Combining Case A and Case B: We compare the upper bound of Case B with the lower bound of Case A to find the conditions on the system parameters and mainly the sample size.
allasg lla 2 n66t1llasgl (la 11 - Co+1)
- + (V8+1)
n( I(V1+ Sati) +
26XMUMMsGott + ypBorg
1- So+1
1s(1 (1(1)
Pp
2XMUMAK
(1 (6+1) 12 KE
11,(1
63+1)3
14
We now compare specific terms to maintain the inequality above and set Ce+1 Js+1
43

---

Published in Transactions on Machine Learning Research (06/2024)
al|ass 1a,
(V&+ + DP.kpp
Up
allasy 112
No + v6o+1) 13/2 [n(v++1) + CIVaRaN / + S--1
Hg
a I+ + S441C1/95,
(v3 1)
Sst1
Ms(1 Sot1)
n nllass
2VSXMUMMS
2v5(v88 1)XMMMMNKofott
Ms So+1)
Ms(1 - Sa+1)
n allass l12
CIVSna
2X
(1+ Sati)llas
1s So+1)2
Mi
Sot1lV& + 1)C1v5K
2X 2XMUMK
(1 (at1)lasll
2
Ma
Simplifying these conditions, we obtain the following,
2(V8+ + 1DBBBe 2(v8+ 1)(vKK (XMUMM)NPP Mpllassll, llz
M Mpllasall ll2
llagg12
Kig
6(1 USa+ 13++1)3/2
/ 1+
Note that here, we do not need to work with the remaining terms of order v since we know n and /p are much larger than /s.
G Proofs of Risk and Estimation Error for the SPriFed-OMP algorithm
Before we provide the risk and estimation error analyses we first state and derive commonly referred to result (Lemma 3 in Meinshausen & Yu (2009) and Lemma 3.1 in Wasserman & Roeder (2009)) regarding the 2-norm of the product X where Xs. refers to the features coinciding with the true model indices and is the model error as shown in Scction 2
Lemma 29. The 2-norm of the product XT e is upper bounded by ynso M (2 log((s/p))) with probability Pb where ps is the base probability and the terms in the product are defined in Section
Proof:
(1)
|| xx
elle
Vn
Σ
23
JES
(2)
Vns,
max Z3
jeS
2ns log 1og(2s/pu))
(1) sets Z, = 1 X7e. (2) follows by definition a maximum. Now, m(Z,) = 0 and Var(Z,)
1 1 X330² 0 as the absolute value of coordinates Xij bounded by Xas- Therefore, (3) fol- n lows by the Lemma 36 with probability Pb.
44

---

Published in Transactions on Machine Learning Research (06/2024)
G.1 Proof of Estimation Error Theorem 9
From Theorem 7 we know given that if satisfy the theorem's 's assumptions recover the true model basis with high probability. We will function under this high probability event and assume that the predicted basis A is equal to S while computing the estimation error. Thus, by Criifed-MMP our estimation error can be derived as below,
Aa = ||á as 1|2
[1(3s)) ) 78* 0.5 ll2
[[x35 X3* + +na) =18) (X S4 y + 17888 - asssle
( 11(X3, Sg Xs,) 1 1/ + Ths ) -05*
(X3, Xsa) ) (T + na5 (X Xs*) 15x)-11 111-
n3 [x Xs+) ) -Xx3 y + 778 )|/
@ 11(x3, xs )- -X
54 6 (X Xs )
(X3, Xsa) ) (I 178 (X5, Xsw) 1-1
(X XSa)
Sq y + 1338/ )||
Xse
XT.
XT X
718 l|2
|| + ||(
n
XT X
n7 XT X
+ II(
(11 +
-11-1
11
11
S+
X S*
-1
X
S
y
+
1h8 )l|
n
n
n
Kgg, 2 log 22)
(1)
(1 Co+1l/ 2ns log /2// pb)) Jo. XM
pb
n
n(1
(o+1)
+ (1 Cx+1)
KM
113
XT Sx
X
y-1
XT y
T7is )|12
Kig8 1 2 logg( pb
22)
(5) (1 (s+1) 11
/oll//////1/ 2s log
28 pb
vn
n21 1 - (s+1)
KM
3/2 Koy
2 2oog
20
x x y
Thi )ll
+ (1 (o+1)2
11(
+
2 log 20 md
(6) (1 Co+1l/ 2s log 25/ pb 1o.
Rg8
v'
ne1
Cs+1)
3/2 RiNiM 1
/2 2n2
n(1 (o+1)2 (1 (4t1)llass ll2
28 Ko 2log
po
1 + Cot1Me
o(V 8 slo((s)
(1) follows by the Woodbury Identity (Eqn. 31
(2) follows since X as+ + XT
Xs, OSS, + (3) follows by the triangle iequality and division and multiplication by n. (4) is based on bounds on the eigenvalues of x,, Xs,, the Lemma 19 as well as by the Gaussian concentration bounds for the noise term The Thss AO, nRaTl.) with probability 1 Pb- Furthermore, the first term's 's bound is
45

---

Published in Transactions on Machine Learning Research (06/2024)
derived by the Lemma 29 and it holds with probability 1 1- Ps- (5) follows from bounds eigenvalues of X5, Xs. and the upper bound of square matrices' maximum singular value (Theorem 2.4 from Rudelson &
Vershynin (2008) and the by the Gaussian concentration bounds for the term n3 7/ N/(0, K 5 1,)) (5) also holds with probability 1 pb- Assuming Ki reasonably small, we notice that if g the estimation error will be dominated by the second term The expression holds with 1 - 4ps as use the concentration incquality four times and combine these events via the union bound.
las, ll then
G.2 Proof of Risk Analysis Theorem 10
From Theorem 7 we again know given that if satisfy the theorem's assumptions can recover the true model basis with high probability. We will function under this high probability event and assume that the predicted basis A is equal to S while computing the estimation error. Thus, by SPriFed OMP our estimation error can be derived as below,
AR R(á; X, y. n)
n
(Iz y1)² -1x,0s - -2i)²)
(1xssa á
-11--118s..0 a8* - -3113))
71
2
1
(IXSs (ox) -'784 y112 1|xs as - -3113)
8
1
(IXSs, (X Xs* + +n) ( (X3 + 1hs y/12
71
|Xs as u11²)
(4) 1 (IIXs, (1X3 X ) (X 1788
-X SM Xsa) - na (X Xse 1-
n Xsa) )-1 1X + T7se y/1
||xs, as u11²)
55) 1 (IXXs, ((X T
Sq Xs )- (ThEN + +X E)
Xse (X Xsa) - no (xT S4 Xseo -11-
XT
Xsa)
((T NT.y + 1hi )112)
5+
(6)
X 9
XT
Xs*
-1 (Ths + +X c)
Sx
71
n
n
Xs*
XT
Xs*
X S.
Xs* ----1
S
(T -1
T
Vn
18
X5+
XT
17
7L
(7)
X SM
XT X S
9W
11
11
Xs.
XT
Xs*
XT E
2
54
S.
||
Vn
11
n
X3a
XT X
8
+ 2
S4
(II
Vn.
XT
X S4
1)8
XT X 5
XT
Thi
)
72
n
46

---

Published in Transactions on Machine Learning Research (06/2024)
+ (0+1)Ki88
2 2 2e
(8)
$ 2
n21 1 (s+1)
(1 + (++1) 1/ 2ns
/2ns log (25/ pb) 0r X NNY 2
+
n11 - So+11
2 2log( 2x²) $3 N
+ 2
po
(1 Sat1)llassll 122
n(1 Sot1)2
R log( 2g)
))²
+ v 1 + Sot11he
pa
n
0 (0(2lo0(())
n
(1)-(3) follow from definitions of risk and the output of SPriFed OMP. (4) follows by the Woodbury expression
(Eqn. 31p. (5) follows since as (X3, x ) X y, Xs, (X Xs, )-1x,, y and y Xs. as, + c. (6) follows by including the n inside the squared norm. (7) follows since ||a [a-bbl b1l? & 2[[|a]]2 + [|611)) which follows from Cauchy-Schwand
inequality. (7) The terms (7) however are similar to the intermdiate term (3) from Theorem 9 except for multiplication by Xs./ / and the squared norm. Clearly by leveraging, the same inequalities and the RIP definition can obtain (8).
H Additional Results and Notation
H.1 Simple Matrix Properties
For a general matrix A E RTxp, we state some simple properties that normally hold irrespective of its distributions. For column index subset S, the pscudo-inverse of As is given by At = (A5 Furthermore, we can easily identify the projection matrix for As, that maps As onto its orthogonal components by, Pg = I Ps. where Ps = AgA A projection matrix Ps has the properties P3 Ps and P5 Ps. Verifying these properties is straightforward by plugging in the value of Ps in terms of As.
The Singular Value Decomposition of A, is written as A UEVI where, u R E (diaa, matrix), V E RPxP. U.V are unitary and UTU UUT 1; LVV VVT I. Further- more, the SVD of AT A is given by V(ΣΣΕЛT ATAV= = VD and therefore, the matrix AT A shares the same eigenvalue and singular values.
VDVT, where D E) Thus, we
that
Denote the maximum and minimum singular values of a matrix A by omar (A) and Jmin (A), respectively. Similarly, define the maximum and minimum eigenvalues of matrix by mmin (A) and Aman (A) respectively. Thus, Amin Amin (X" = maz x)) = o2 ma (X) and Amin (X" X) Tran (X"X) X) (X). Finally, the zt singular value and eigenvalue of the matrix A is given by (A) and Xx(A) respectively.
Lemma 30. (Spectral Norm eigen-value bounds] Consider the matrir A Raxp and vector RP then,
mmia mmin (A)llwlla & ||Aw|l2 & (max((A)]lull)
Lemma 31. /Woodbury Identity: Kailath Variant/ (page 153 from Bishop et al. (995)). Petersen et al. (008)) For conformable matrices A, B,B.C we have the following expression for the inverse of malris sum,
(A + BC) A- A -C
Assuming, B = III N we oblain
Assuming, B = N₂ = I we obtain -
(A+ A
A- A
47

---

Published in Transactions on Machine Learning Research (06/2024)
H.2 Concentration bounds for Random Variables
We have previously seen in the differential privacy section, that require that the matrix values or their functional outputs be bounded. Therefore, here we consider some of the useful properties of random variables that allows us to bound their contributions.
Lemma 32. |Concentration Inequality (Boucheron et al. 2013 For Gaussian random variable x with distribution o") we have,
20 Pr[la] < 1 1 2e 20
Lemma 33. [Union Boundj The union bound states for any events Ei, Ez,... En we have,
PRO E.) & Σ PRE.)
Lemma 34. [Norm of matriæ with subgaussian entries] (Theorem 4.3.5 from Vershynin 2018
Consider matric A E R2xp where its entrics Aij are independent, mean zero, subgaussian random variables. Then, for any > O we have,
|| & CK(V VD+1)
with probability at least 1 1- - and K max,, ||Arslluzii [
Lemma 35. [Lower Bound of Minimum Singular Value for Random Matria]: (Theorem 1.2 from Rudelson & Vershynin (2008) ) Let 21.....2p 2p be independent, centered real random variables with variance at least and sub- Gaussian momenls bounded by B. Let A RpxP matric whose rows are independenl copies
of the random vector 2p). Then for every E 2 0
Pr[omin (A) 3 I CE d vP
where C DE 1) depend polynomially only on B.
Lemma 36. /Concentration of the marimam random variable] Suppose have k. random variables agii E [k] each with distribution o2). We provide upper bound for the marimum of these k random variables following,
h Pr[max poa i=1
B >
Pb
where B a 2log(////oo) and pa is the total fasture probability such that po % Proof: Consider the events E, s.t., lad & Biie [k] and suppose Pr[la,] > B] & Po- With Lemma 32 applied to Ne, we have,
Pr[[2; > B <
2c
20
2 ]] expp log((2/)))) /20²)
Pr[læd| > /
2 2
Po
2exp( - log(2/po))
Pd
Then, with the union bound, consider the probability of the event Eo s.t. max (rs & B. Then, Pr[ Pr > B] (where at least one value is larger than the bound). Then,
Pr = Pr
B
<
Σ
Pr P
>
B
48

---

Published in Transactions on Machine Learning Research (06/2024)
k. Po
Pr[Eol = 1- Pr(Ep = - k
The first inequality is due to Boole's ' inequality. In particular, if we wish to bound our failure probabililies to a fixed value ps, then we can have Po 2h and thus our bound B = 0 / 2k ps is achieved.
49


Reviews:
[{"review_id": "yRge8TWMXK", "reviewer": "Reviewer_FeBV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written, with good presentation of background and the methodology.\n- The method comes with theoretical guarantees.\n\nWeaknesses:\n- It looks like in Algorithm 3, NOISY-SMPC on $X_k$ and $X_{l^*}$ is used multiple times but with different noise scale. I'm wondering whether the privacy budget for the proposed method is overestimated.\n- Assumption 2 which requires bounded $X$ seems quite restrictive. Could the authors provide some justifications why this is a realistic setting?\n- The accuracy analysis is hard to parse. Theorem 7 and 8 do not have privacy parameter, making it hard to understand how privacy affect the recovery accuracy. Similarly in Theorem 9 and 10, while $O(slog(s))$ error is good, I don't see the privacy parameter in the bound. Is it implicitly omitted?\n- In the current experiments the privacy parameter is fixed. Could the authors show the pareto privacy-utility tradeoff?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work the authors propose a new method for private sparse recovery in the context of federated learning based on OMP. The proposed method is able to recovery the sparse basis with $O(\\sqrt{p})$ samples. Empirical results show that the proposed method is able to significantly outperform prior baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Improving utility bounds in Theorem 7-10 to make it clear how privacy affects the utility.\n2. Adding pareto privacy utility frontier is useful.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "u77p8mP5Cn", "reviewer": "Reviewer_dfg4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The paper is very well written; the computations are carefully detailed, a lot of intuition is given when concepts and algorithms are introduced, which makes the reading pleasant.\n- This work is the first one to combine both federated and privacy constraints in the overparametrized regime of sparse basis recovery, which is of main interest for the community.\n- This work is complete in the sense that it presents both theoretical and practical results, which strengthens the soundness of the approach.\n- Section 5, which features the utility results, is particularly exhaustive and insightful.\n- The numerical results are meaningful, as the authors propose several ablation studies.\n\n**Weaknesses**\n- The justification for choosing Gaussian Differential Privacy instead of other differential privacy approaches such as Rényi Differential Privacy (RDP) is partial: the authors invoke that the composition rule has a better behaviour, but it is hard to see why (for example, the composition in RDP is straightforward)\n- No ablation study is conducted on the differential privacy parameters used in the numerics: in the synthetic datasets, the authors take $\\epsilon=5.34$, while they consider $\\epsilon=8.34$ for the realistic datasets, without further justification. These values are unfortunately too high to be used in practice. Hence, the utility/privacy tradeoff is not well highlighted in the numerics.\n- This work does not tackle the question of heterogeneity among the datasets, which is nonetheless a major issue in FL. As far as I understand, the authors study settings where the whole data is homogeneous and is assumed to be separated between clients (see the numerics). In practice, practitioners observe heterogeneity across the local datasets, which hurt the aggregation in the naive FL setting. For instance, this setting has been studied in [1], where the authors propose to combine privacy with control variates.\n\n[1] Noble et al. Differentially Private Federated Learning on Heterogeneous Data. 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper tackles the challenging problem of federated sparse basis recovery (i.e. the data is split among clients, the operations are computed by a central server) under privacy constraints (namely differential privacy) in the case where the number of model dimensions $p$ is much larger than the number of samples $n$. The authors intend to fill a gap in literature where either private solutions or federated solutions have been proposed up to now for sparse basis recovery; while most of these methods can be extended to a private-federated setting in a straightforward manner, it systematically hurts their accuracy. To mitigate this issue, the authors propose a new approach which combines both federated and private aspects simultaneously, called SPriFed-OMP. This algorithm elaborates on the federated adaptation of the well-known algorithm 'Orthogonal Matching Pursuit', while introducing privacy via Gaussian Differential Privacy. They propose an alternative version, SPriFed-OMP-GRAD, which revisits their first method from a gradient perspective. To justify their approach, the authors present a theoretical analysis of their algorithms (namely, privacy and utility results), which demonstrate that they can recover the true sparse basis with high probability in the case where $n=O(\\sqrt{p})$. Finally, they conduct numerical experiments on both synthetic and realistic datasets, and compare their approach to concurrent works.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I recommend the authors to :\n- add a more detailed justification on the use of Gaussian Differential Privacy\n- add numerical experiments where the differential privacy parameter $\\epsilon$ takes several values (on both synthetic and realistic datasets) to observe the dependence to the privacy constraint\n- add a discussion on the modifications of their algorithms to handle heterogeneity issues and numerical experiments which show the robustness of their current setting to this question", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4G96fmGSvi", "reviewer": "Reviewer_qoft", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. Two effective differentially private FL algorithms for sparse basis recovery are proposed, privacy guarantee and utility guarantee are provided  for the proposed algorithms. \n2. Experiments show that the proposed algorithms outperform the baselines (DP-SGD, OMP et al.). \n\nWeaknesses\n\n1. The main concern is that the computation cost and the communication cost of the proposed algorithms seem heavy.   SPriFed-OMP and SPriFed-OMP-GRAD need to run Noisy-SMPC and PRIVATE-OLS algorithms many times, the effectiveness of the algorithms may be hard to guarantee when the dimensions are very high or the sample size is large. It looks like the efficiency of the algorithm is sacrificed in exchange for its effectiveness.\n\n2. Theorem 10 provides the risk analysis of SPriFed-OMP, and it shows that the risk is in the order of $O(s/n)$. It seems that it is not good enough. Bassily et al.(2020) and Wang et al.(2022) proved that for Lipschitz non-smooth loss or non-Lipschitz smooth loss, DP-SGD can achieve the optimal rates $O(1/\\sqrt{n} + \\sqrt{p}/n)$. It would be better if the similar rate can be shown for the proposed algorithms.\n\n\n\n[1] Raef Bassily, Vitaly Feldman, Crist´obal Guzm´an, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.\n\n[2] Wang P, Lei Y, Ying Y, et al. Differentially private SGD with non-smooth losses. Applied and Computational Harmonic Analysis, 2022, 56: 306-336.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focused on privacy-preserving sparse basis recovery problem for high dimension data analysis under the federated learning setting.  Based on the Orthogonal Matching Pursuit algorithm, they propose two new private sparse basis recovery algorithms SPriFed-OMP and SPriFed-OMP-GRAD for the DP-FL problem. The effectiveness of the proposed algorithm is evaluated both theoretically and empirically.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In the introduction, page 2, the paper mentioned that the empirical risk rate for DP-SGD with Lipschitz losses is $O(p/n)$, while it has benn proved that the optimal rate $O(\\sqrt{p}/n+1/\\sqrt{n})$ can be achieved even for excess population risk. \n\n2. It would be better if the comparison of GPU time or other measures of computation cost could be provided in the experiments.\n\n3. Is there any possible that the risk rate in Theorem 10 can be improved? I guess it might not be easy, the present results are fine with me. \n\n4. The paper mentioned in Section 4 that Gaussian DP optimally composed over multiple iterations. Could the authors explain why it is better than RDP?\n\n5. In NOISY-SMPC, all clients compute $q_i$ and submit is to the server. How about sampling some clients in each iteration (uniformly or using Poisson sampling) to update $q_i$ and submit their local updates to the server? It might decreases the communication cost. The guarantee of privacy could use sub-sampling property [1] to get a better bounds. \n\n[1] Wang Y X, Balle B, Kasiviswanathan S P. Subsampled rényi differential privacy and analytical moments accountant. The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019: 1226-1235.", "broader_impact_concerns": "no concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All of the reviewers are positive about accepting the paper, and the authors have already addressed most of the critique and comments in the rebuttal process. However, I think some room for improvement still remains, which I think the authors can address with another revision.

Please consider the following points when preparing the final version:

- Please have still a look at the comment of reviewer FeBV : You could make the utility bounds more understandable by writing them in terms of the privacy parameters $\varepsilon$ and $\delta$ instead of the noise scale parameter $\sigma$. Please make it more explicit what does $\sigma_{\varepsilon}$ mean.

- Related to the discussion with reviewer dfg4 on the privacy analysis and to the related modifications : As the privacy guarantees are essentially those of a composition of Gaussian mechanisms, it is obvious that GDP will give the best possible $(\varepsilon,\delta)$-DP guarantees for the method. One can consider a non-adaptive composition of Gaussian mechanisms also as a vector-valued Gaussian mechanism, and then it is obvious that the GDP-bound gives a tight bound whereas RDP does not, since GDP gives tight bounds for the Gaussian mechanism (see e.g. Balle and Wang, 2018). And with given sensitivities for individual mechanisms, in case of adaptive compositions, the situation is similar, thanks to the results, e.g., by Dong et al. (2019) which you also cite. You could consider rephrasing that part and replacing/augmenting the numerical comparisons with short reasoning.

- In the privacy analysis of Alg. 3 (Theorem 6), is the DP cost of steps 4-5 included ? 

- Add names of the datasets either to figures or captions.

- Please carefully check the writing. Few example: p.1: "Forward-Backward Algorithmand Least Angles Regression, \emph{those} leverage sparsity..." -> "Forward-Backward Algorithmand Least Angles Regression, which leverage sparsity..." 
Figure 1 y-label: "arifact" - "artifact". There seem to be other similar examples.

- I find the notation a bit confusing: $\mathbf{X}$ seems to denote both the set of features, i.e., $\mathbf{X} = \{ x_1, \ldots, x_n \}$, where $x_i \in \mathbb{R}^n$ for all $i \in [n]$, but also the matrix $\mathbf{X} \in \mathbb{R}^{n \times p}$, where the feature vectors are row vectors. In Alg. 2 to 5, you have $p$ features and $n$ labels. Please go through the notation carefully.
Decision: Accept (poster)