Near Optimal Private and Robust Linear Regression
Authors: Xiyang Liu
Prateek Jain
Weihao Kong
Sewoong Oh
Arun Suggala
Venue: Submitted to ICLR 2023 (2023)
Keywords: differential privacy
private estimation
linear regression
label corruption

Abstract: We study the canonical statistical estimation problem of linear regression from $n$ i.i.d. examples under $(\varepsilon,\delta)$-differential privacy when a fraction of response variables are adversarially corrupted.   We propose a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. When there is no adversarial corruption, this algorithm improves upon the existing state-of-the-art approach and achieves near optimal sample complexity. Under label-corruption, this is the first efficient linear regression algorithm to provably guarantee both $(\epsilon,\delta)$-DP and robustness. Synthetic experiments confirm the superiority of our approach. 

Under review as a conference paper at ICLR 2023
NEAR OPTIMAL PRIVATE AND ROBUST LINEAR RE- GRESSION
Anonymous authors Paper under double-blind review
ABSTRACT
We study the canonical statistical estimation problem of linear regression from n i.i.d. examples under (c, -ddifferrent privacy when fraction of response variables are adversarially corrupted. We propose variant of the popular dif- ferentially private stochastic gradient descent (DP-SGD) algorithm with two in- novations: full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. When there is no adversarial corruption, this algorithm improves upon the existing state-of-the-art approach and achieves near optimal sample complexity. Under label-corruption, this is the first efficient linear regression algorithm provably guarantee both ()-P) and robustness. Synthetic experiments confirm the superiority of our approach.
INTRODUCTION
Differential Privacy (DP) is widely accepted notion of privacy introduced in (Dwork et al., 2006), which is now standard in industry and government (Tang et al., 2017; Erlingsson et al., 2014; Fanti et al., 2016; Abowd, 2018). A query to database is said to be (e, 8) 8)-differentially private if a strong adversary who knows all other entries cannot identify with high confidence whether you participated in the database not. The parameters and 5 restrict the Type-I and Type-II errors achievable by the adversary (Kairouz et al., 2015). Smaller E > and E [0, imply stronger privacy guarantees.
Significant advances have been made recently in understanding the utility-privace trade-offs in canonical statistical tasks. We provide a survey in App. A. However, several important questions remain open, some of which we address below. A canonical statistical task of linear regression is when n i..dd samples, {(I; E Rd yi E R)) are drawn from H, (N, Σ), yi x, w" + 2is and 2; ~ (O, o²). The error is measured in | - w == 2 accounts for the signal-to-noise ratio in each direction; in the direction of large eigenvalue of Σ. we have larger signal in x; and the same noise in 24, and hence expect smaller error.
w w²))l which correctly
When computational complexity is not concerned, the best known algorithm is introduced by Liu et al. (2022b), called High-dimensional Propose-Test-Bee Test-Relassee (HPTR), that can be flexibly applied variety of statistical tasks to achieve the optimal sample complexity under (c, 5DD For linear regression, n = ((daa))d)(sa)) samples are sufficient for HPTR to achieve an error of (1/ar) | w w1 = a with high probability. This optimal, matching known information theoretic lower bounds. It remains an important open question if this can be achieved with an efficient algorithm. After a series of work surveyed in App. A, Varshney et al. (2022) achieves the best known sample complexity for an efficient algorithm: n = Ó(Rdd/= + d/aa + kd/ (sxx). The last term is sub- optimal by factor of the condition number of the covariance Σ of the covariates, and the first term is unnecessary. We further close this gap in the following.
Theorem (informal version Theorem with no adversary). Under the (E, w", ; K, momdell in Assumption 1, n = Odd/a² + ////2d((aa) samples are sufficient for Algorithm to achieve an error rate of (1/a)][u w' 1 Ō(a) and (s, DDP,, where k == Amax (E)/ Amin (E).
Perhaps surprisingly, we show that the same algorithm is also robust against label-corruption, where an adversary selects arbitrary Occrrupt fraction of the data points and changes their response variables arbitrarily. When computational complexity is not concerned, the best known algorithm is HPTR by Liu et al. (2022b) that also provides optimal robustness and (c, 5DDD simultancously, i.e.,

---

Under review as a conference paper at ICLR 2023
Old/a² + d/(e)) samples are sufficient for HPTR to achieve an enror of (1/o)llı- w0133
for any corruption bounded by acorrupt I a. Note that this is a strong adversary who can corrupt both the covariate, I,, and the response variable, Yı. Currently, there is no efficient algorithm that can guarantee both privacy and robustmess for linear regression. Under a weaker adversary who can only corrupt the response variable, we close this gap in the following.
Theorem 2 (informal version of Theorem 3 with adversarial label corruption). Under the hypotheses Scoerupt-Corrupphr corruption model of Assumption 2. if acorrupt I then samples are sufficient for Algorithm to achieve an error rate of (1/o)]l00-
of Theorem and under Cccerupt
O(d/a² a2l/a2220 xx//dd/ w" 1 = (aa) and (e,8)-Di -DD. where K == Xmax / Amin (E).
We start with the formal description of the setting in Sec. and present the approach of Varshney et al. (2022) for private but non-robust linear regression. We build upon this approach and make two innovations. First, we propose full-batch gradient descent, which is more challenging to analyze but achieves improved dependence on the condition number x. Crucial in overcoming the challenges in the analysis is the notion of resilience explained in our proof sketch (Sec. 6). Secondly, we propose novel adaptive clipping method that ensures robustness against label corruption. We present our main algorithm (Alg. 1) in Sec. 3 with theoretical analysis and justification of the assumptions. Our adaptive clipping is both robust and private. We use truncated mean to ensure robustness and private histogram to ensure privacy in Sec. 4. We present numerical experiments on synthetic data that demonstrates the sample efficiency of our approach Sec. 5. We end with a sketch of our main proof ideas in Sec. 6, which might be of independent interest to those requiring tight analysis of linear regression in other settings.
PROBLEM FORMULATION AND BACKGROUND
For linear regression without adversarial corruption, the following assumption is standard for the uncorrupted dataset Sgood. except for the fact that we assume a more general family of (K, au-sub- Weibull distributions that recovers the standard sub-Gaussiar family a special case when
1/2. multiset Sgood = {(z; E Rd yt E R]]=== of n i..dd samples is from linear model y; (I;, + Zú. where the input vector I, is zero mean, B[x,] = 0, with a positive definite covariance E- = E E[r > 0, and the (impul dependent) label noise 2; is zero mean, E[z]] = O, with variance 0² : E|2 We further assume E[z,2,] 0, which is equivalent to assuming that the true parameter w" = E distribution xf;
Assumption 1 (EE o², w", K, a) -omoel.)).
- Ely, We assume that the marginal x, is (K, a)-sub- Weihull and that of 2; is also (K, a)-sub- -eiibll defined below.
Sub-Weibee Weibull distributions provide Gaussian-lit -ike tail bounds determining the resilience of the dataset in Lemma J.7, which our analysis critically relies on and whose necessity is justified in Sec. 3.3. Definition 2.1 we say a random vector I E R&d is from a (K, a) ()-subb-W hubb-Wibulll distribution for all v E Rdd,
distribution Kuchibhotla & Chakrabortty (2018)), ). For some K,a >> O,
1/(20)
(u, x)
E
exp
<1.
KK 2)
Our goal is to estimate the unknown parameter w", given upper bounds on the sub-Weibun Weibull param- eters (K, a) and a corrupted dataset under the the standard definition of label corruption in (Bhatia et al., 2015). There are variations in literature, which we survey in Appendix A.
an adversary inspects all the data points, selects Occorrupe data points denoted as Sr, and replaces the labels with arbi- trary labels while keeping the covariates unchanged. We let Stad denote this set of Ceorrupt newly labelled examples by the adversary. Let the resulting set be S ;= Sgood U Spad \ Sy. We further assume that the corruption rate bounded by Georrupt S G. where ā is a known positive constant satisfying ā S 1/10, 72C₂ K2 a log2"() (1/(Ga) log(k) S 1/2, and 2C K2 log" (1 (1/ (1/(2x)) 2 1 for the (K, a-)-ubb-WWyw Weibull distribution of interest and positive constant C2 defined in Lemma J.7 that only depends on (K.
Assumption 2 (frormp-corruptioon) Given dataset Sgood = =(x,,,))) vt))
Notations. A vector E Bd has the Euclidean norm ||~r|]. For a matrix M, we use || to denote the spectral norm. The emor is measured in || w" ||>: == // w²)l )| for some PSD matrix E.
2

---

Under review as a conference paper at ICLR 2023
The identity matrix is denoted by Ia E Rddd Let [n] 2,,, nn. ...,......... O(-) hides some constants terms, K, a = (1), and poly-logarithmic terms in n, d. 1/E, log(1/6), 1/5, and 1/ //Coorupp-
2.1 BACKGROUND ON DP
Differential Privacy (DP) is standard measure of privacy leakage when dataset is accessed via queries, introduced by Dwork et al. (2006), Algorithms with strong DP guarantees provide plausible deniability strong adversary who knows all other entries in that dataset and tries identify particular user's entry (Kairouz et al., 2015). Two datasets S and S' are said to be neighbors if they differ at most by one entry, which is denoted by S S stochastic query q said to be (e, 6) -)-ffferrettial private for some & >> () and 5 E [0, 1]. if ((a(S) E A) S (S)) E A) + 6, for all neighboring datasets S S and all subset of the range of the query. We build upon two widely used DP primitives, the Gaussian mechanism and the private histogram. A central concept DP mechanism design is the sensitivity of a query, defined as A, == sups (1((5) ((") We describe private histogram in App. B.
Lemma 2.2 (Gaussian mechanism Dwork Roth (2014)). For a query with sensitivity Ag the Gaussian mechanism outputs (S + (o, (A and achieves (e.8)-DP.
2.2 STANDARD APPROACII IN PRIVATE LINEAR REGRESSION
When there is no adversarial corruption, the state-of- of-teo art approach introduced by Varshney et al. (2022) is based on stochastic gradient descent with clipping and additive Gaussian noise to ensure privacy. There are two main components this approach: adaptive clipping and streaming SGD. Adaptive clipping with appropriate threshold 0 ensures that no data point is clipped while pro- viding a bound on the sensitivity of the average mini-batch gradient, which ensures we do not add much noise. The streaming approach, where data point is only touched once and discarded, ensures independence between the past iterate w and the gradients at round t, which the analysis critically relies on. For 7 = (1s), iterations where is the condition number of the covariance E of the covariates, the dataset S = {(rr, y:) }=1 is partitioned into ( (B.)²= subsets of equal size. At each round t < T. the gradients are clipped and averaged with additive Gaussian noise:
1
clipo, (x, xs - v.)) + 0. 2 log(1.25/
w++1 f Wi 17
1/1
(1)
B₁
B|B
EE
where 14 NN(O,aa) In Varshney et al. (2022), a variation of this streaming SGD is shown to require n = Ó(x2d/=+ d/a² + kd/(sa)) to achieve an error [| - w w = 0(oaa²).
Our approach builds upon such gradient based methods but makes two important innovations. First, we use full-batch gradient descent, as opposed to the streaming SGD above. Using n samples reduces the sensitivity of the per-round gradient average, allowing us to improve the sample com- plexity to Óddaa² 2 + x²/2d/((a)) to achieve eтrоr of WT w" || O(oaa²). However, we lose the independence between Wt-1 and the gradients the current round, which makes the analysis more challenging. We instead rely resilience to precisely track the bias and variance of the (dependent) full-batch gradient average. Resilience is a central concept in robust statistics which explain in Sec. 6. The second innovation make is separately clipping I, and (w, I; 34) in the gradient. This is critical in achieving robustness to label-corruption, as we explain in Sec. 3.1.
3 ROBUST AND DIFFERENTIALLY PRIVATE LINEAR REGRESSION
We introduce gradient descent approach for linear regression with novel adaptive clipping that ensures robustness against label-corruption. This achieves near-optimal sample complexity and, for the special case of private linear regression without adversarial corruption, improves upon the state-of-the-arr algorithm.
3.1 ALGORITHM
The skeleton of our approach in Alg. 1 is the general DP-SGD Abadi et al. (2016); Song et al. (2013) with adaptive clipping Andrew al. (2021). However, the standard adaptive clipping is not robust
3

---

Under review as a conference paper at ICLR 2023
against label-corruption under the more general (K, -ub-uWbbll Weibull assumption. In particular, it is possible under sub- Weibull distribution that a positive fraction of the covariates are close to the origin, which is not possible under Gaussian data due to concentration. In this case, the adversary can select to corrupt those points with small norm, || making large changes in the residual, (yi 1 24), while evading the standard clipping (by the norm of the gradient), since the norm of the gradient, [1; i. x;)ll = problematic, since the bias due the corrupted samples in the gradient scales proportional to the magnitude of the residual (after clipping). To this end, we propose clipping the norm and the residual separately: (1;
| lys w, zy/. can remain under the threshold. This is
(w,_ I; v.). This keeps the sensitivity of gradient average bounded by e0,, and the subsequent Gaussian mechanism in line 8 ensures (en, 60) each round. Applying advanced composition in Lemma B.4 of I rounds, this ensures end-to-end (s, 8)-P.
Novel adaptive clipping. In (zi)) the only purpose of clipping the covariate by its norm, ||=:|| is to bound the sensitivity of the resulting clipped gradient. In particular, we do not need to make it robust as there no corruption in the covariates. Ideally, we want select the smallest threshold θ that does not clip any of the covariates. Since the norm of a covariate is upper bounded by
||> < I²T log (1/C) with probability 1 - (Lemma J.3), we estimate the unknown Tr(E)) using Private Norm Estimator in Alg. 3 in App. F and set the norm threshold θ = K log" (n/C) (line 3). The n the logarithm ensures that the union bound holds.
vi), the purpose of clipping the residual by its magnitude, 1y: w. æs| = 1w w;)Tx;; x; + 2z/. is to bound the sensitivity of the gradient and also to provide robustness against label-corruption. We want to choose a threshold that only clips corrupt data points and at most a few clean data points. We know that any set of (1 c0rorrppts)) fraction of the clean data points is sufficient to get a good estimate of the average gradient, and we can find such a large enough from
In clipo, (w]
set of points that satisfy I(w" - we) x, + 2/ < (Ilw, - "1 + o²)CK² 2 Lemma J.3. At the same time, this threshold the residual is small enough guarantee robustness against the label-corrupted samples. We introduce Robust Private Distance Estimator in Alg. to estimate the unknown (squared and shifted) distance, ||w, w" 11 + o², and set the distance
threshold 0, = 2//2 V 1 log""(1/(2a)) (line 6). Both norm and distance estimation rely on private histogram (Lemma B.1), but over a set of statistics computed on partitioned datasets, which we explain in detail in Sec. 4.
Algorithm 1: Robust and Private Linear Regression
Input: dataset S [Zx, yı) ) = privacy parameters (e, 8), number of iterations T, learning rate 17, failure probability Ç. target error rate a, distribution parameter (K,
Partition dataset S into three equal sized disjoint subsets S = S1 S, US.
do + 6/(22),, so + /
So + //3, wp + 0
I <- PrivateNormmEstimattor/r for / = 1, 1,2...., T do
60. Co). e + K KV2T log" (n/Co)
W/: Cr; 80 a, So)
0, + 2/27 |9 log (1/(2a)). (og((a)))))
Sample Vt ~ N (0, La)
w++1= wi n n Eies, (clipo(z)cclip,,, (m) 21 v1)) + (log(1225/6jjee)
san
Return WT
3.2 ANALYSIS
We show that Algorithm I achieves a ncar-optimal sample complexity. We provide a proof in Ap- pendix H and a sketch of the proof in Section 6. We address the necessity of the assumptions in Sec. 3.3, along with some lower bounds.
w", ,K, K,,a a)-mdel of Assumption I and acorrppt" corruption of Assumption 2 and for any failure probability < E (0, 1) and target error rate Z
Theorem 3. Algorithm I is (e, DD- Under (E, ,2,
4

---

Under review as a conference paper at ICLR 2023
Ocorrupt= if sample size is large enough such that
d log(1() +
/T log( () log"(()
n n= δ log
2a+1
(2)
a²
Sex
with large enough constant where Ô hides poly-logarithmic terms in d, n, and then the choices of a small enough step size, 1) S 1/(1.1Amax (2)), and the number of iterations, T = é (rc log ([]==())) for condition number of the covariance is == Amax (E)/ / /m/iimiia))) ensures that, with probability
Algorithm achieves
Ev, (o.La) ||w w wl - [K'' ok' log am
())).
(3)
where the expectation is taken over the noise added for DP, and θ()) hides logarithmic terms in K, a, d, n, 1/e, log(//)) 1/a, and R.
Optimality. Omitting some constant and logarithmic terms, Alg.
requires
d n 0(
0(2 K <//odlo(L//))
E0
samples to ensure an error rate of [ Ō for any a 2 Ofcorrupt. The lower bound on the achievable error of a² 2 x² o²a2 corrrupt is due to the label-corruption and cannot be improved, as it matches an information theoretic lower bound we provide in Proposition 3.1. In the special case when the covariate follows a nu--Gaussian distribution, that is (K, 1/2)-sub- -/)/suuu-Weilllll Weibull for a constant K, there is an n M(d/a² + d/(sa)) lower bound (Cai et al. (2019), Theorem 4.1), and our upper bound matches this lower bound up to a factor of k//2 in the second term and other logarithmic factors. Eq. (4) is the best known rate among all efficient private linear regression algorithms, strictly improving upon existing methods when (1g( = O(1). We discuss some exponential time algorithms that closes the 1/2 gap in Sec. 3.3.
Comparisons with the state-of-the-art. The best existing efficient algorithm by Varshney et al. (2022) can only handle the case where there no adversarial corruption, and requires n O(=2d//oo(1////e + d/o2² nd (lo((1//)))((a))) to achieve an error rate of a²a?. Compared to Eq. (4), the first term dominates in its dependence in K, which is a factor of larger than Eq. (4). The third term is larger by factor of 2// but smaller by factor of log ///l//(11))))) (1/8), compared the second term in Eq. (4).
In the non-private case, when oc, recent line of work has developed algorithms for linear gression that are robust to label corruptions (Bhatia et al., 2015; 2017; Suggala et al., 2019; Dalalyan & Thompson, 2019). Of these, Bhatia et al. (2015); Dalalyan & Thompson (2019) are relevant to our work as they consider the same adversary model as us. When v, 's and z are sampled from (O Σ) and ((00, o²), Dalalyan & Thompson (2019) proposed a Huber loss based estimator that achieves error rate of a² log2(n/5) (n/5) when = Ô (i²d/a²). Under the same setting, Bhatia et al. (2015) propoased hard thresholding based estimator that achieves a²a² eттor rate with Ô (d/a²) sample complexity. Our results in Theorem 3 match these rates, except for the sub-optimal depen- dence on (1/a). Another line of work considered both label and covariate corruptions and developed optimal algorithms for parameter recovery (Diakonikolas et al., 2019c;b; Prasad et al., 2018; Pensia et al., 2020; Cherapanamjeri et al., 2020; Jambulapati et al., 2020; Klivans al., 2018; Bakshi & Prasad, 2021; Zhu et al., 2019; Depersin, 2020). The best existing efficient algorithm, e.g. Pensia et al. (2020) achieves error rate of a² log(1 1/a) when n = Ô (d/o²). and the uncorrupted I; and 2; are sampled from (V(0, and (0,
Under both privacy requirements and adversarial corruption, the only algorithm with a provable guarantee is the exponential time approach, known as High-dimensional (HPTR), of (Liu et al., 2022b, Corollary C.2), which achieves a sample complexity of n Odd/a² 2 + (d + log(1/6))/ (Ea)). Notice that there is no dependence on and the log(1/5) term scales as 1/(Ea) opposed to kdd /dd"///(sa) of Eq. (4). It remains open question if computationally efficient private linear regression algorithms can achieve such a x-independent sample complexity. Further, HPTR is robust against stronger adversary who corrupts the covariates also and not just the labels. Under this more powerful adversary, remains an open question if there is an efficient algorithm that achieves n O(d/o² + d/(ea)) sample complexity even for constant and 8.
5

---

Under review as a conference paper at ICLR 2023
3.3 LOWER BOUNDS
Necessity of our assumptions. A tail assumption on the covariate I; such as Assumption 1 is necessary to achieve n = O(d) sample complexity in Eq. (4). Even when the covariance Σ is close to identity, without further assumptions on the tail of covariate æ, the result in Bassily et al. (2014) implies that for < 1/n and sufficiently large n, no (e, 5)-P estimator can achieve excess risk || w0 = better than (2(d"((=>n²) ({) (see Eq. (3) in Wang (2018)). Note that this lower bound is factor d larger than our upper bound that benefits from the additional tail assumption.
A tail assumption on the noise 2, such as Assumption I is necessary to achieve dependence on the sample complexity in Eq. (4). For heavy-tailed noise, such as k-th moment bounded noise, the dependence can be significantly larger. (Liu et al., 2022b, Proposition C.5) implies that for å e(d) and 4-th moment bounded x; and 24, any (E,6)-DP estimator requires ((dd((ca)) to achieve excess risk Bi]l@ w' [[3]] = Ō(oaa²).
(sa((sa)
The assumption that only label is corrupted is critical for Algorithm 1. The average of the (adap- tively) clipped gradient can be significantly more biased, if the adversary can place the covariates of the corrupted samples in the same direction. In particular, the bound on the bias of our gradient step in Eq. (42) in App. H would steps to estimate the mean of the gradients robustly and privately, similar to those used in robust private mean estimation Liu et al. (2021); )); Kothari al. (2021); Hopkins al. (2022); Ashtiani & Liaw (2022). Pursuing this direction is outside the scope of this paper.
longer hold. Against such strong attacks, one requires additional
Lower bounds under label corruption. Under the acorrupt label corruption setting (Assumption 2), even with infinite data and without privacy constraints, no algorithm is able to learn w² with &g error better than Gcorrupt. We provide formal derivation for completeness.
K.a be class of joint distributions on (1i, from oE, w", K, momellll in Assumption from some distribution D E Dr.ga w= ,K...a under Assumption 2. Let M be a class of estimators that are functions over the datasets Sn.or Then there exists a positive constant e such that
Proposition 3.1. Let D KKa
Let Sn,a be an a-corrupted dataset of i.i.d samples
min A.EEM
max
Billu
[
2 ca² 0²
(5)
Su..e DED 2 K,a K.a,,
A proof is provided in Appendix I.1. similar lower bound can be found in (Bakshi & Prasad, 2021, Theorem 6.
4 ADAPTIVE CLIPPING FOR THE GRADIENT NORM
In the ideal clipping thresholds for norm and the residual, there is an unknown terms which we need to estimate adaptively, ([|wr w" [| + d²) and Tr(E), up to a constant multiplicative error. We privately estimate the (squared and shifted) distance to optimum, (llu,- -w" 123 + o²), with Alg. 2 -w'
and privately estimate the average input norm, || = Tr(E), with Alg. 3 in App. F. These used to get the clipping thresholds in Alg. 1. We propose trimmed mean approach below for distance estimation. The norm estimator is similar and is provided in App. F.
Private distance estimation using private trimmed mean. The goal is to estimate the (shifted) distance to optimum, ||w,, 1 + o², up to some constant multiplicative error. Note that this is precisely the task of estimating the variance of the residual b, yi w, x;. When there is no ad- versarial corruptions and no privacy constraints, we can simply use the empirical variance estimator (1/m) Eiejo] (y/- w/ xx)² 2 to obtain good estimate. However, the empirical variance estimator is not robust against adversarial corruptions since one outlier can make the estimate arbitrarily large. A classical idea is using the trimmed estimator from (Tukey & McLaughlin, 1963), which throws away the 2a fraction of residuals b; with the largest magnitude. For datasets with resilience property as assumed in this paper, this will guarantee an accurate estimate of the distance to optimum in the presence of a fraction of corruptions.
To make the estimator private, it is tempting to simply add a Laplacian noise to the estimate. How- ever, the sensitivity of the trimmed estimator is unknown and depends on the distance the optimum

---

Under review as a conference paper at ICLR 2023
that we aim estimate; we cannot determine the variance of the Laplacian noise need to gener- ate. Instead, we propose to partition the dataset into & batches, compute an estimate for each batch, and form a histogram with over those & estimates. Using private histogram mechanism with ge- ometrically increasing bin sizes, we propose using the bin with the most estimates to guarantee a constant factor approximation of the distance to the optimum. We describe the algorithm as follows.
Algorithm 2: Robust Private Distance Estimator
Input: S2 = (Tx ()) H current weight Wt, privacy (En, og), a.
Let b, < (y: wi xz)², F, for all i [n] and +- {b:)
Partition S into k = [C] log( [6o])) subsets of equal size and let G, be the j-th partition.
For j E [k], denote v as the (1 - 3a))--uunttill
Gj and dj f To,T Eieo, b, b,1 s v5
Partition [0, oo) into bins of geometrically increasing intervals
Ω = (.... ( (1. [2.29) [22 ,....} U {[0,0]
Run (co, dDP histogram learner of Lemma B.1 on } over $2
all the bins are empty then Return
Let [e,r] be a non-empty bin that contains the maximum number of points in the DP histogram
return !
This algorithm gives an estimate of the distance up to a constant multiplicative error as we show in the following theorem. We provide a proof App.
Theorem 4. Algorithum is (Cu, 50) For Occorrupt Occorup--oorruppe -corrupted dataset S2 and upper bound on Ocorrupt that satisfy Assumption and 37C,K² log (1/(6a)) S 1/4 and any Ç (0, 1),
if
n 00
(6)
a
with large enough constant then, with probability 1 Ç, Algorithm returns é such that å [1l w 1|3 + + S A[]l o
Remark 4.1. While DP-STAT (Algorithm in Varshney et al. (2022)) can also be used estimate ||w; wt w/|lx + a (and it would not change the ultimate sample complexity in its dependence on k. e, and n), there are three important improvements we make: (i) DP-STAT requires the knowledge of l|w" ||x + a; (ii) our utility guarantee has improved dependence in K and log (n); and (iti) Algorithm 2 is robust against label corruption.
Upper bound on clipped good data points. Using the above estimated distance to the optimum in selecting threshold 9,, we also need to ensure that do not clip too many clean data points. The tolerance in our algorithm to reach the desired level of accuracy is clipping ((a) fraction of clean data points. This is ensured by the following lemma, and provide proof in Appendix E.
Lemma 4.2. Under Assumptions 1, if 0, 2 99C22² log" (1/(2a)) (Ilw* - -wallx + t), then
(i Sq Sgood :Iw, X, yi 2 0.}l S om, for all L E [T].
EXPERIMENTAL RESULTS
5.1 DP LINEAR REGRESSION
We present experimental results comparing our proposed technique (DP-RoBGD) with other base- lines. We consider non-corrupted regression in this section and defer corrupted regression to the next section. We begin by describing the problem setup and the baseline algorithms first.
Experiment Setup. We generate data for all the experiments using the following generative model. The parameter vector (w") is uniformly sampled from the surface of unit sphere. The covariates {z,) 1 are first sampled from (0 Σ) and then projected to unit sphere. We consider diagonal covariances Σ of the following form: [[ 0] = k, and Σji, i] = 1 for all i 2 1. Here x 2 is the condition number of Σ. We generate noise 2; from uniform distribution over [-a,a). a). Finally,

---

Under review as a conference paper at ICLR 2023
6-10, x-1
Panemette Eximetion
Fanamete: Esometion
Parcameto: Exttenction
10
20"1
10-3
10:3
10:4
2071
1071
Samples
Non Private OLS
SPP
Non Private SGD
DP AMB5SGD
DP RobGD
DP RobGD*
Figure 1: Performance of various techniques on DP linear regression. d 10 in all the experiments. n 10", = 1 in the 2nd experiment. n. 10", in the 3rd experiment.
the response variables are generated as follows 1/4 (2r4, )) + 2,. All the experiments presented below are repeated times and the averaged results are presented. We set the DP parameters (c, 6) as = 1, 0 min 10
²)) Experiments for e 0.1 can be found in the Appendix.
Baseline Algorithms. We compare our estimator with the following baseline algorithms:
ordinary least squares (OLS), one-pass stochastic gradient descent with tail-averaging (SGD). For SGD, we use constant step-size of 1/(2>max) with n/T minibatch size, where I" = 3x log
Non private algorithms:
Private algorithms: sufficient statistics perturbation (DP-SSP) (Foulds et al., 2016; Wang, 2018), differentially private stochastic gradient descent (MP-AMDS)GD) (Varshney et 2022). DP-SSP had the best empirical performance among numerous techniques studied by Wang (2018), and DP-AMBSSGD has the best known theoretical guarantees. The DP-SSP algo-
rithm involves releasing X X and X differentially privately and computing (XTX)- AM-SSBD private version of SGD where the DP noise is set adaptively according to the excess error in each iteration. For both the algorithms,, we use the hyper-parameters recom- mended their respective papers. To improve the performance of DP-AMBSSGD, we reduce the clipping threshold recommended by the theory by constant factor.
DP-ROBGD. We implement Algorithm with the following key changes. Instead of relying PrivateNormEstinaator to estimate r, we set it to its true value Tr(E). This is done for a fair comparison with DP-AMBSSGD which assumes the knowledge of Tr(E). Next, we 20% of the samples to compute "/ in line 5 (instead of the 50% stated in Algorithm 1). In our experiments we also present results for variant of our algorithm called DP-ROBGD* which outputs the best iterate based on instead of the last iterate. One could also perform tail-averaging instead of picking the best iterate. Both these modifications are primarily used to reduce the variance in the output of Algorithm 1 and achieved similar performance in our experiments.
Results. Figure 1 presents the performance of various algorithms as we vary K. CT It can be seen that ROBGO outperforms AM-MMBSD in almost all the settings. DP-SSP has poor performance when the noise a is low. but performs slightly better than DP-ROBGD in other settings. major drawback of DP-SSP is its computational complexity which scales as O(nd² + d='). In contrast, the computational complexity of OP-ROBGD has smaller dependence on d and scales as Ö(nd)). Thus the latter is more computationally efficient for high-dimensional problems.
5.2 DP ROBUST LINEAR REGRESSION
We now illustrate the robustness of our al- gorithm. We consider the same experi- mental setup above and randomly cor- rupt a fraction of the response variables by setting them to 1000. The figure the right presents the results from this experi- ment. It can be seen that none of the base- lines are robust to adversarial corruptions. They be made arbitrarily bad by in-
0-0.122-
10'
303
30-1
10:3
Romomerer
10 corruptions
107
8

---

Under review as a conference paper at ICLR 2023
creasing the magnitude of corruptions. In contrast, OP-RoBGD is able to handle the corruptions well. More experimental results on a harder adversary can be found the Appendix.
SKETCH OF THE MAIN IDEAS IN THE ANALYSIS
We provide the main ideas behind the proof of Theorem 3. The privacy proof straightforward since no matter what clipping threshold we get from private norm estimator and private distance estimator, the noise we add is always proportionally to the clipping threshold which guaranteed privacy. The focus of this section will be the utility of the algorithm.
The proof of the utility heavily relies on the resilience Steinhardt et al. (2017) (also known as sta- bility Diakonikolas & Kane (2019)), which states that given large enough sample set S, varies statistics (for example, sample mean and sample variance) of any large enough subset of will be close each other. We provide the formal definition of resilience in Appendix C.
The main effort for proving Theorem 3 lies in the analysis of the gradient descent algorithm. With- clipping and added noise for differential privacy, convergence property of gradient descent for linear regression is well known. The convergence proof of noisy gradient descent is also relatively straightforward However, our algorithm requires clipping and added noise together for robustness and privacy purposes, and the key difference between our setting and the classical setting is the ex- istence of adversarial bias and random noise in the gradient. We give an overview of the proof of our robust and private gradient descent as follows.
First we introduce some notations. Let g. = (xx w yr; be the raw gradient, 9: clipo, (z) wt y: (1;)) be the clipped gradient. Note that when the data follows from our distributional as- sumption, clipa (a+²) = 24 for E Spood- We can write down one step of gradient update as follows:
W2+1 w
Wt 11
Σ
91
(1)
+ drel
w
n
I
7 TE
Σ REG
x - ww)
+
17 11
Σ
JiZ + 7 (1 Ti VEG
9. - ((--1))
Σ Spod
(t) 9;
71
iEG
iE
In the above equation, the first term contraction, meaning w. is moving toward w². The sec- ond term captures the noise from the randomness of the data set. The third term captures the bias introduced by the clipping operation, the fourth term 2 Eies g captures the bias introduced by the adversarial datapoints, the fifth term captures the added Gaussian noise. The second term is standard and relatively easy to control, and our main focus on the last three terms.
The third term " prove that with our estimated threshold, the clipping will only affect small amount of data- points, whose contribution to the gradient is small collectively. The fourth term _ Σiesun g Exesmn clipo, (z. w, y4 can be controlled since there is only small amount data points whose label is corrupted, the clipo, (x.J we yi) is controlled by the clipping threshold and the x; part satisfies resilience property which implies small, say Smad, must have small Eiesun zill-
"iEG(o
(t-1) g(t-1)) can be controlled using the resilience property. We
Now we have controlled the deterministic bias. Then, we upper bound the fifth term, which the noise introduced by the Gaussian noise for the purpose of privacy, and show the expected prediction error decrease in every gradient step. The difficulty that, since our clipping threshold is adaptive, the decrease of the estimation error depends the estimation eπror of all the previous steps. This causes that in some iterations, the estimation error actually increase. In order to get around this, we split the iterations into length chunks, and argue that the maximum estimation error in chunk must be a constant factor smaller than the previous chunk. This implies we will reach the desired emror with in ((x) steps.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC

---

Under review as a conference paper at ICLR 2023
conference on computer and communications security, pp. 318-3008110 2016.
John M Abowd. The US Census Bureau adopts differential privacy. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2867- 2867, 2018.
Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression. arXiv preprint arXiv:2007.05157, 2020.
Kareem Amin, Matthew Joseph, Mónica Ribero, and Sergei Vassilvitskii. Easy differentially private linear regression. arXiv preprint arXiv:2208.0733: 2022.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34, 2021.
Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaus- sians and beyond. In Conference Learning Theory, pp. 1075-1076. PMLR, 2022.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in I1 geometry. In International Conference on Machine Learning, pp. 393-403. PMLR, 2021.
Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 102-115, 2021.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in Neural Information Processing Systems, 32, 2019.
Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding. Advances in neural information processing systems, 28, 2015.
Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar. Consistent robust regression. Advances in Neural Information Processing Systems, 30, 2017.
Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance-awarc private mean estimation without private covariance estimation. Advances in Neural Information Processing Systems, 34, 2021.
Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv preprint arXiv: /902.04499 2019.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3). 2011.
Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly- linear time. Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms, pp. 2755-2771. SIAM, 2019.
Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni. Michael I Jordan, Nicolas Flammar- ion, and Peter I. Bartlett. Optimal robust linear regression in nearly linear time. arXiv preprint MxXi:2007.08/333 2020.
Arnak Dalalyan and Philip Thompson. Outlierrobuust estimation of a sparse linear model using L -penalized huber's m-estimator. Advances in neural information processing systems, 32, 2019.
Jules Depersin. A spectral algorithm for robust regression with subgaussian rates. arXiv preprint arXiv:2007.06072. 2020.
10

---

Under review as a conference paper at ICLR 2023
Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint
2019.
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pp. 190-. PMLR, 2017.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 1047-1060, 2018.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability, SIAM Journal on Computing, 48(2)7722 864, 2019a.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stew- art. Sever: robust meta-algorithm for stochastic optimization. International Conference on Machine Learming. pp. 1596-1606, 2019b.
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for bust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithmx, pp. 2745-2754. SIAM, 2019c.
Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar. Robustly learning any clusterable mixture of gaussians. arXiv preprint arXiv:2005.064 2020.
Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, and Benjamin IP Rubinstein. Robust and private bayesian inference. In International Conference on Algorithmic Learning Theory, pp. 291-305. Springer, 2014.
Yihe Dong, Samuel Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. Advances Neural Information Processing Systems, 32, 2019.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty- first annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 15-4))211-4077, 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1066 1064-1067,11 2014.
Giulia Fanti, Vasyl Pihur, and Úlfar Erlingsson. Building rappor with the unknown: Privacy- preserving learning of associations and data dictionaries. Proceedings on Privacy Enhancing Technologies, 2016(3):41 -1,, 2016.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020.
James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of preveriy bayesian data analysis. arXiv preprint arXhv:1603.07294, 2016.
Quan Geng, Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The staircase mechanism in differential privacy. IEEE Journal of Selected Topics in Signal Processing, 9(7):1176-1144 2015.
Antonious M Girgis, Deepesh Data, Suhas Diggavi, Ananda Theertha Suresh. and Peter Kairouz. On the renyi differential privacy the shuffle model. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pp. 2321 22211, 2021.
11

---

Under review as a conference paper at ICLR 2023
Sivakanth Gopi. Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34:1 34:11631-11642, 2021.
Samuel B Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp.
1 1406-1417, 2022.
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 SIGMOD-SIGACTSSIGAI
Symposium on Principles of Database Systems, pp. 227-236, 2022.
Peter Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pp. 492- 518. Springer, 1992.
Arun Jambulapati, Jerry Li, and Kevin Tian. Robust sub-gaussian principal component analysis and width-independent schatten packing, Advances in Neural Information Processing Systems, 33, 2020.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27, 2014.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pp- 1376-1385. PMLR, 2015.
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. arXiv preprint arXiv:2106.01336 2021.
Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.088:
2017.
Ashish Khetan, Zachary C Lipton, and Animashree Anandkumar. Learning from noisy singly- labeled data. In International Conference on Learning Representations, 2018.
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 Proceedings. 2012.
Adam Klivans, Pravesh K Kothari, and Raghu Meka. Efficient algorithms for outlier-robust regres- sion. In Conference On Learning Theory, pp. 1420-1430. PMLR, 2018.
Weihao Kong, Rajat Sen, Pranjal Awasthi, and Abhimanyu Das. Trimmed maximum likelihood estimation for robust learning in generalized linear models. arXiv preprint arXiv:2206.04777, 2022.
Pravesh K Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. arXiv preprint arXiv:21 2021.
Arun Kumar Kuchibhotla and Abhishek Chakrabortty. Moving beyond sub- uub-gaussianity in high- dimensional statistics: Applications in covariance estimation and linear regression. arXiv preprint arXiv:1804.02605. 2018.
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprint 103.::2003./522 2021.
Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. Advances in Neural Information Processing Systems, 34, 2021.
Xiyang Liu, Weihao Kong, Prateck Jain, and Sewoong Oh. DP-PCA: Statistically optimal and differentially private pea. arXiv preprint arXiv:2205.13709 2022a.
Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory, pp. 1167-1246. PMLR, 2022b.
12

---

Under review as a conference paper at ICLR 2023
Frank D McSherry. Privacy integrated queries: extensible platform for analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp. 19-30, 2009.
data
Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis loannidis. Differentially private re- gression with unbounded covariates. In International Conference Artificial Intelligence and Statistics, pp. 3242-3273, PMLR, 2022.
Kentaro Minami, HItomi Arai, Issei Sato, and Hiroshi Nakagawa. Differential privacy without sensitivity. In Advances in Neural Information Processing Systems, pp. 956-964, 2016.
Darakhshan Mir. Differential privacy: an exploration of the privacy-utility landscape. Rutgers
The State University of New Jersey-New Brunswick, 2013.
llya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations sympo- sium (CSF), pp. 263-275. IEEE, 2017.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv preprint arXiv:2009. 12976, 2020.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradcep Ravikumar. Robust esti- mation via robust gradient estimation. arXiv preprint arXiv:/802.064:: 2018
Holger Sambale. Some notes on concentration for a-subexponential random variables. arXiv preprint arXiv:2002.10761 2020.
Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory, pp. 789-827. PMLR, 2019.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. 2013 IEEE global conference on signal and information processing. pp. 245-248 IEEE, 2013.
Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private clipped gradient de- scent convex generalized linear problems, arXiv preprint arXiv:2006.066 067733, 2020.
Jacob Steinhardt, Moses Charikar, and Gregory Valiant, Resilience: A criterion for learning in the presence of arbitrary outliers. arXiv preprint arXiv:1703.0mg
2017.
Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, and Prateek Jain. Adaptive hard thresholding for near-optimal consistent robust regression. In Conference Learning Theory, pp. 2892-2822222 2897. PMLR, 2019.
Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint 1rXiv:1709.02755: 2017.
Henri Theil. A rank-invariant method of linear and polynomial regression analysis. Indagationes mathematicae, 12(85):173, 1950.
Kiran K Thekumparampil, Ashish Khetan, Zinan Lin, and Sewoong Oh. Robustness of conditional
gans to noisy labels. Advances neural information processing systems, 31, 2018.
John W Tukey. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians Vancouver, 1975, volume 2, pp. 523-531, 1975.
John W Tukey and Donald H McLaughlin. Less vulnerable confidence and significance procedures for location based on a single sample: Trimming/winsorizattonnn Sankhya: The Indian Journal of Statistics, Series A, pp. 331-352 1963.
Prateck Varshney, Abhradeep Thakurta, and Prateek Jain. (nearly) optimal private linear regression via adaptive clipping. arXiv preprint Atl::2007004688 2022.
13

---

Under review as a conference paper at ICLR 2023
Duy Vu and Aleksandra Slavkovic. Differential privacy for clinical trial data: Preliminary evalua- tions. In 2009 IEEE International Conference on Data Mining Workshops, pp. 138-143. IEEE, 2009.
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. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation unbounded domain. arXiv preprint 1803.028 2018.
Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and
stochastic gradient monte carlo. In International Conference Machine Learning, pp. 2493- 2502. PMLR, 2015.
Yu-Xiang Wang. Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. The 22nd International Conference on Artificial Intelligence and Statistics, 1226-1235. PMLR, 2019.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. Proceedings of the 2017 ACM International Conference Management of Data, pp. 1307-1322, 2017.
Liang Zhang. Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He. Bring your own al- gorithm for optimal differentially private stochastic minimax optimization. arXiv preprint 200.:222066003333, 2022.
Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. Generalized resilience and robust statistics. arXiv preprint arXiv:1909.068 08755, 2019.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pp. 4782-4817 PMLR, 2022.
14

---

Under review as a conference paper at ICLR 2023
APPENDIX
A RELATED WORK
Differentially private optimization. There is a long line of work at the intersection of differentially
privacy and optimization (Chaudhuri et al., 2011; Kifer et al., 2012; Bassily et al., 2014; Song al,, 2013; Bassily et al., 2019; Wu et al., 2017; Andrew et al., 2021; Feldman et al., 2020; Song et al,, 2020; Asi et al., 2021; Kulkarni et al., 2021; Kamath et al., 2021; Zhang et al., 2022). As one of the most well-studied problem in differentially privacy, DP Empirical Risk Minimization (DP-ERM) aims to minimize the empirical risk (1/n) Eies {(z;; w) privately. The optimal excess empirical
risk for approximate DP (i.e.. 8 > 0) is known to be GD - vd/(sn), where the loss is convex and G-Lipschitz with respect to the data, and D is the diameter of the convex parameter space (Bassily et al., 2014). This bound can be achieved by several DP-SGD methods, e.g., (Song et al., 2013; Bassily et al., 2014), with different computational complexities. Differentially private stochastic convex optimization considers minimizing the population risk EN-D [e(x,, w),, where data is drawn Li.d. from some unknown distribution D. Using some variations of DP-SGD, Bassily et al. (2019) and Feldman et al. (2020) achieves a population risk of G1/ Vic + (en(e))).
DP linear regression. Applying above results for the linear model, by observing that G = (c)) if D = =(1), the sample complexity required for achieving generalization error is n = d², Existing works for DP linear regression, for example (Vu & Slavkovic, 2009; Kifer et al., 2012; Mir, 2013; Dimitrakakis et al., 2014; Wang et al., 2015; Foulds et al., 2016; Minami et al., 2016; Wang, 2018; Sheffet, 2019; Wang & Gu, 2019; Hu et al., 2022) typically consider deterministic data. Under the ii.d. Gaussian data setting, this translates into a sample complexity of = d3/2 /(ea), where the extra d2/2 due to the fact that no statistical assumptions are made. For ii.d sub- Weibull data, recent work (Varshney ct al., 2022) achieved nearly optimal excess population risk d/n + d'/ /{=2n²) using DP-SGD with adaptive clipping, up to extra factors the condition number. This is closest to work and we provide detailed comparisons in Sections 2.2 and 3.2. Under Gaussian assumptions, Milionis et al. (2022) analyze linear regression algorithm with sub-optimal guarantees. (Dwork & Lei, 2009; Alabi et al., 2020; Amin et al., 2022; Liu et al., 2022b) also consider using robust statisties like Tukey median (Tukey, 1975) or Theil-Sen estimator (Theil, 1950) for differentially private regression. However, (Dwork & Lei, 2009; Amin et al., 2022) lack utility guarantees and (Alabi et al., 2020) restricted -iedimensio data. Liu et al. (2022b) achieves optimal sample complexity but takes exponential time.
Robust linear regression. Robust mean estimation and linear regression have been studied for a long time in the statistics community (Tukey & McLaughlin, 1963; Huber, 1992; Tukey, 1975). However, for high dimensional data, these estimators generalizing the notion of median to higher di- mensions are typically computationally intractable. Recent advances in the filter-based algorithms, e.g.. (Diakonikolas et al., 2017; 2020; 2019a; 2018; Cheng et al., 2019; Dong et al., 2019), achieve nearly optimal guarantees for mean estimation in time linear in the dimension of the dataset. Mo- tivated by the filter algorithms, Diakonikolas et al. (2019c;b); Prasad et al. (2018); Pensia et al. (2020); Cherapanamjeri et al. (2020); Jambulapat et al. (2020) achieved nearly optimal rate with d samples for robust linear regression, where both data I; and label yi are corrupted. Another type of efficient methods that achieve similar rates and sample complexity in polynomial time is based on sum-of-square proof' (Klivans et al., 2018; Bakshi & Prasad, 2021), which can be computation- ally expensive in practice. Zhu al. (2019); Brown et al. (2021); Liu et al. (2022b) achieve nearly optimal rates using d samples but require exponential time complexities. An important special case of adversarial corruption is when the adversary only corrupts the response variable in supervised learning (Khetan et al., 2018) 8) and also in unsupervised learning (Thekumparampil et al., 201 8). For linear regression, when there only label corruptions, (Bhatia et al., 2015; Dalalyan & Thompson, 2019; Kong et al., 2022) achieve nearly optimal rates with O(d) samples. Under the oblivious la- bel corruption model, i.c., the adversary only corrupts a fraction of labels in complete ignorance of the data, (Bhatia et al., 2017; Suggala et al., 2019) provide consistent estimator w, such that lim,,-0o E [ - "01, = 0 with (d) samples.
Robust and private linear regression. Under the settings of both DP and data corruptions. the only algorithm by Liu et al. (2022b) achieves nearly optimal rates a log( (og()/)) with optimal sample complexities of d/a² + d/(ea). However, their algorithm requires exponential time complexities.
15

---

Under review as a conference paper at ICLR 2023
B PRELIMINARY ON DIFFERENTIAL PRIVACY
Our algorithm builds upon two DP primitive: Gaussian mechanism and private histogram. The Gaussian mechanism is one examples of larger family of mechanisms known as output perturba- tion mechanisms. In practice, it is possible to get better utility trade-off for output perturbation mechanism by carefully designing the noise, such as the stair-case mechanism which are shown to achieve optimal utility in the variance (Geng et al., 2015) and also in hypothesis testing (Kairouz al., 2014). However, the gain is only by constant factors, which we do try to optimize this paper. We provide reference for the private histogram below.
Lemma B.1 (Stability-basee histogram (Karwa & Vadhan, 2017, Lemma 2.3)). For every K
NU oc, domain S2 for every collection of disjoint bins BI..... Bg defined on Q n E N, 6 2 0, E (o, 1/n), B 0 and a E (0, 1) there exists (s, d)dffferretllll private algorithm M : Q R such that for any set of data X1, XI,..., Xn E Q
1. Py 1 EX,B,
2. ..... ,K)) MX Xn), and
3.
n 2 min {
8
log log(2K/a)
8
log log(4/o6))
EB
EB
then,
P(Íe pul Sal580 3)
When the databse is accessed multiple times, we use the following composition theorems to account for the end-to-end privacy leakage.
Lemma B.2 (Parallel composition McSherry (2009)). Consider a sequence of interactive queries {g each operating on a subset Ss of the database and each satisfying (e, ()-P) If Sy are .........K qK (Sx)) is (e, 6)-P.
disjoint then the composition (Si), Q2 (S2)....,
Lemma B.3 (Serial composition Dwork & Roth (2014)). If database is accessed with an (11, DP mechanism and then with an (Ez, DDP mechanism, then the end-to-end privacy guarantee is (E1 + E2, 61 + DDP
In most modern privacy analysis of iterative processes, advanced composition theorem from Kairouz al. (2015) gives tight accountant for the end-to-end privacy budget. can be improved for specific mechanisms using tighter accountants, e.g.. in Mironov (2017); Girgis et al. (2021); Wang et al. (2019); Zhu et al. (2022); Gopi al. (2021).
Lemma B.4 (Advanced composition Kairouz et al. (2015)). For s S 0.9, an end-to-end guar- antee of diifferreeti privacy is satisfied if database is accessed times, each with (2/(2))) //22k) private mechanism.
(og(2/))),
C DEFINITION OF RESILIENCE
Definition C.1 ((Liu et al., 2022b, Definition 23)). For some a E (0, P1 E RR, P2 E R4, and Pa P.... P4 E B.,, we say datasel Spood {(x; IRd yi RK is (a, P2, P3, -resiiint with respect to (wo F.,a) for some w² Rdd, positive definite Σ Rdxd and 0 if for any
16

---

Under review as a conference paper at ICLR 2023
T C Sgood size (T) 2 (1
ai),, the following holds for all R
Σ
(1, (vi - x w²)) ".]ww))
S p1 Vu Euo,
(7)
(ETT
(u, - - Iu S p22 I2 Ev.
(8)
CCT
Σ
(yi 2. w2/²² - -0² S p30²
(9)
(ATT))T
Σ (v,
SPIVOT Ev.
(10)
(ET
D PROOF OF THEOREM ON THE PRIVATE DISTANCE ESTIMATION
We first analyze the privacy. Changing data point (si, vt) can affect at most one partition in (G, = This would affect at most two histogram bins, increasing the count of one bin by one and decreasing the count in another bin by one. Under such bounded l sensitivity, the privacy guarantees follows from Lemma B.I.
Next, we analyze the utility. In the (private) histogram step, we claim that at most only two consecutive bins can be occupied by any Øz's. This is also true for the private histogram, be- cause the private histogram of Lemma B.1 adds noise non-empty bins only. By Lemma B.1, if k 2 clog(1 (ddgg(o))/Eo one of these two intervals (the union of which contains the true distance |w:-- - " - 13 + o²) is released. This results in a multiplicative error bound of four, as the bin size increments by a factor of two.
To show that only two bins are occupied, we show that all Jj's are close to the true distance. We first show that each partition contains most 2ccorrupt fraction of corrupted samples and thus all partitions (2a, 6ā, 6p, 6p, 6p, -coorupt good, where p(C₂, K, a, a) "og (1/6a) and j' (C2, K, a, σ+) = Ka log" (1/Gā), as defined in Definition J.6.
Let B |n/k] be the sample size in each partition. Let Co c/2. Since the partition is drawn uniformly at random, for each partition Gj. the number of corrupted samples a satisfies a'n ~ Hypergeomettri((1 Okcorrupt n//k). The tail bound gives that with probability
Co.
a' S Ocurrupt + (k/n) log(2/Go) I 2ā,
where the last inequality follows from the fact that the corruption level is bounded by Occoruppiion S a and the assumption on the sample size in Eq. (6) which implies n 2 log(1 (og(1/(6660) ((60Co)) log log(1/Go)/(aen)
For a particular subset Gj. Lemma J.7 implies that if B O((d + log(1/ (o))//"))))))) then Gj is (a', 6a, 6p, 6p, 6p, 67¹) coorupp good set with respect to (w", E, o) from Assumption 1. This means that there exists a constant C2 > O such that for any Ti gooo with [Ti| 2 (1 B, we have
(or w' w.)² I|w"
we 11
s 6C2k2a log 20 (1/(6))) -
T
iET:
Σ 2 σ²
S &C2k2 xxxkxllogg 20 (11((a))o
log
Ti
iET
and
1 [Tg
Σ (1i, w² ---==" -wi) $6C2K²a log (1/(6)))ll w: willzo
Note that for i E Sgood, b, = 2/ + 22, -2, (w w() x, + (w - w/) nn (w" - -w)). By the triangular inequality, we know, under above conditions.
Σ b; - || - w - 0² < 20g IT
well + 02)
(11)
T1
17

---

Under review as a conference paper at ICLR 2023
Which also implies that any subset T2 Sgood and [T2] S 6ā| GālSgooul have
1 T2l
b,
11w= well3 o²
< 12Cgk log (1/(22111/())(() well o2)
(12)
iET2
Recall that 4 is the (1-3ā) ( -uuantile of the dataset Gy. Let := E Sgood : b. S b J. where with a slight abuse of notations, we use Suood to denote the set of uncorrupted samples corresponding to Gj and Stad to denote the set of corrupted samples corresponding to Gj. Since the corruption is less than a', we know (1 - 3ā - B S [T] S (1 - 3ā + a') B. By our assumption that a' S 20,
we have |E| 2 (3ā -a')aa)B a') 2 aB where É == S good \ E. Using Eq. (12) with choice of T2 E.
we get that
min b. - 11ee well 0² - 120gkK² log (1/( - -wrll + t
(13)
This implies that
V/ S 120gK2 log" (I((6)))(l)"" +
(14)
Hence
1
|6, 1|""" w/ 0²|
b.
l(b: S 1b - 11 w
B
tEG,
= 1 Σ b, 1110 - well
0²
+ B
Σ
b, 1lb s 1
B
ET
iESunl
S 37
ā log (1/(6ā))
we + +
(15)
where we applied Eq. (14) and Eq. (11) in the last inequality.
On a fixed partition Gj. we showed that if B = O(dd + log(1/G))/aa)) then, with probability
1 1 Co. 10g I| w 0²1 < } (I] well3 + o²), which follows from our assumption that 37CrK²
know if B O((d + log(k/Co) (o))/a"), then - So. loy - || we w - o² < [( well + o²) holds for all j E [k). Since the upper bound lower bound ratio is 5/3 which is less than 2. All the dy must lie
log log (6/(a)) < 1/4. Using union bound for all subsets,
in two bins, which will result in a factor of 4 multiplicative error.
E PROOF OF LEMMA 4.2 ON THE UPPER BOUND ON CLIPPED GOOD POINTS
Let pCC2, a,) = 2C2 log log2211/222) and (C K, a, = 202 log" (1)(2))).
Lemma J.7 implies that if n O(dd log(L/())((a)) with large enough constant, then there exists a universal constant C2 such that S3 is, with respect to (w", ..,). (Acorrupt: 2a, P. P, P, ~')- corrupt good. The rest of the proof is under this (deterministic) resilience condition. By the re- silience property in Eq. (8), we know for any T C
CS Sgood with T 2 22))n
w= T (w= - wi) -Ilw= 1 wrll3 $2CgK3a 20 (1/(2))l w. 1..
T
iET
(16)
Let E = {i E Sgood : (w- -w)) u (w" - we) > ||0" we (xC
+ 1)}-
Denote à = FFl/n. We want to show that â < a Let T be the set of points that contain the smallest a/2 fraction in {(w" wx) T x..r (w" (w:) wi))iiSSoont We know [T] (1 a/2)n 2
(1 2.. To prove by contradiction, suppose ā > a/2, which means all data points in Sgood
larger than ||=" wxlli (8C2 (1g + 1). From resilience property in Eq. (16),
18

---

Under review as a conference paper at ICLR 2023
know
(w- - -w)) I,,;; (w² - wi)
EE SESpood
1
(w" wp) I:20 (w" -we)
(w² - T T
-wr) 2 (w" -wi))
n
iEg 12
11-2 2) 11-202
(10(112200)) 2C2 a allog 20
-11
20 1100 - well (8C2K² log
+ 1)[l weell
2a
2a
2C2K3 log (1/2a)) ]|w) we
11
which contradicts Eq. (16) for Sgood. This shows â S a/22
Similarly, we can show that K E Sgood : of > (2 K22 log 20 (1/ + +1} S a/2. This means the rest (1 ar) points Sgood satisfies V(w" - w)) 2 (w* - w;) + |zs| S (1w, -
="|| || + a) y (8C2 2 log (1/(2))
+ 1). Note that for all i E Sgood, we have
|
Vıl = | (we w²) Zi
S | (we w²)l |22
V (w w2) Txaa (w* wi) + |21)
By our assumption that C₂ log 20 (1/(2ā)) 2 1 which follows from Assumption 2, we have
{
E Sgood ||=,5 We - vill s ([]Wr w01l + σ)v 9C2K2 (10(22))
2 (1 a)n. (17)
F PRIVATE NORM ESTIMATION: ALGORITHM AND ANALYSIS
Algorithm 3: Private Norm Estimator
Input: S {xx, 14 1." 1=1 target privacy (5o, do), failure probability Ç.
Let a; <- || Let S = {a, )
Partition S into 1: = [c log()/(6)C))e subsets of equal size and let G, be the j-th partition.
For each j E [k]. denote vi = (L/IG,)) Eiea, ag
Partition [0, oo) into bins of geometrically increasing intervals
Ω2 = {..... [2- 2/4 2-4)),, [2-1/4 1). [1. 21/)) [21/4 22/4) ..... ([0,0)}
Run (Eo, 6o) histogram learner of Lemma B. on { over s2
if all the bins are empty then Return 1
Let [e, r] be a non-empty bin that contains the maximum number of points in the DP histogram
Return \
Lemma F.1. Algorithm 3 is (Eo, 86) If (a,) are i.i.d. samples from (K, subb--bbbll tributions with zero mean and covariance E and
Weibull dis-
n1 Ō log 2a (1/(6o())
Eu
with large enough constant then Algorithm returns I such that, with probability 5.
Tx v2Tr(E).
22
We provide proof in App. F.1.
19

---

Under review as a conference paper at ICLR 2023
F.1 PROOF OF LEMMA F.1 ON THE PRIVATE NORM ESTIMATION
By Hanson- Wright inequality in Lemma J.1 and union bound, there exists constant c > 0 such that with probability S.
(Voos1/C) + log lo/(((11()
20 2 Tr(E) ck2 c Tr(E)
(18)
b
This means there exists a constant d' such that if 2 d' dK2 log (k/C), then for all j E [k]]
1 - Tr(x)] - (r(()
(19)
With probability ç. (w, lie in interval size / TrE). Thus, at most two consecutive bins are filled with { Denote them as / = I, U 12. Our analysis indicates that (P(1/2 E 7) 2 0.99. By private histogram in Lemma B.1, if k: 2 log(1 log(1/(6())/e, 10r prl I 0.01 where P is the empirical count on / and アy is the noisy count released. This results in multiplicative error of v2.
Under this condition, one of these two intervals
G PROOF OF THE RESILIENCE IN LEMMA J.7
We apply following resilience property for general distribution characterized by Orlicz function from Zhu et al. (2019).
Lemma G.1 ((Zhu et al., 2019, Theorem 3.4)). Dataset S = {I; E Rd from a distribution D. Suppose is zero mean and satisfies BEND tb
Jizi consists i.i.d. samples
(u Tx)²
for all E Rd, where *+)) is Orlicz function. Let E EzzD( (x:x T. Suppose a S ā, where â satisfies (1 + ā/2)- 2x o2p (2/a) < 1/3, ā S 1/4. Then there exists constant C1, C2 such that if 2 (l( + (og((1()))(((
with probability 1 - Ç, for any T C S of size [T] 2 (1 a)n, the
following holds:
||
1/2
Σ xi FET
(20)
[
and
Ia 1-1/2
Σ
2
E I-1/2
(21)
[T]
iET
Let (t) = 1/(20)) Weibull, then know
easy to see that v+() is a valid Orlicz function. Then x; is (K, -u-b-
1/2
1/2
Σ
< C2Kay/oog (0 (1/a))
(22)
iET
and
1
La - 1-22 1/2
Σ
x
1-1
log""alo""(//o"
(23)
iET
This implies
(1 - C2C 20/00// - 1112
1
Σ
1-1
3 31 ao (1/aa)
T
iET
(24)
20

---

Under review as a conference paper at ICLR 2023
Using the fact that CT = Bf B, we know
(1 - C2K (1/a))2
m., 3 (1+ log (1/a)) (L/a))
(25)
RET
This implies resilience properties of x; and 2, in Eq. (8) and Eq. (9) in Definition C.1 respectively. Next, we show the resilience property of z;zg.
By ab S =/2 ba for any fixed TRd 2
((kerr))))) 2) 12 [K402 2.
1/(1a)
exp ((K
(Las K2r" 2iv
u) 12)
1/(20)
((x00²
27
1/(2a)
Elexp
S
/2
exp
K202
12
(26)
1
((
(Loor, o) 12) 1/(20)
27
1/(2a)
2
E
exp
K2v Ev
+ E
exp
K20z
(27)
(28)
Since E[x;2:] = 0, (Zhu et
al., 2019, Lemma E.3) implies that there exists constant C1 C2 > 0 such that if ci (((++log((())((e)))) with probability 1- for any T Sgood of size [ > (1 0)m,
Σー
Jitii RET
S <22Koa or log (1/a).
(29)
H PROOF OF THEOREM ON THE ANALYSIS OF ALGORITHM
The main theorem builds upon the following lemma that analyzes (stochastic) gradient descent method, where the randomness is from the DP noise we add and the analysis only relies on certain deterministic conditions on the dataset including resilienece and concentration. Theorem 3 follows in straightforward manner by collecting Theorem 4, Lemma F.1, Lemma 4.2, and Lemma H.1.
Lemma H.1. Algorithm / is (s, 5)-D.. Under Assumptions I and 2 for any E (0,1) and > Gcorrupt satisfying kaa log 2a (1/ax) log(s) S for some universal constant > 0, if distance threshold is small enough such that
Oe S 33///2 K log
log (1/(2a)) -Ilw" wellx
(30)
and large enough such that the number of clipped clean data points is no larger than om, at every round, the norm threshold is large enough such that
θ K
Tr(E) log (n/C),
(31)
and sample size is large enough such that
0 (K3dlog((d/)) log (n/C) d d log(1/))
+ x2T/\/dlog(T//) log" (ng"()n((())
a²
(32)
with large enough constant, then the choices of a step size, n= 1/ (2)) for some C 1.1, and the number of iterations, T Ô (x log (1|w" [])), ensures that Algorithm outputs wr satisfying the following with probability S;
w [[3] S Kt o (k)a log loggo (1/a),
(33)
where the expectation is taken over the noise added for DP and θ(:) hides logarithmic terms in K, a, d, n, 1/e, (1))))))))) 1/a.
21

---

Under review as a conference paper at ICLR 2023
Proof of Lemma H.1. We first prove a set of deterministic conditions on the clean dataset, which is sufficient for the analysis of the gradient descent.
Step 1: Sufficient deterministic conditions the clean dataset. Let Sgood be the uncorrupted dataset for S3 and Sbad be the corrupted datapoints in S3. Let G := Sgood N.S. = S3 Shad denote
the clean data that remains in the input dataset. Let Xmax = | Define Σ == (1/n) Eiea ,,
B- Ia- E Lemma J.4 implies that if n = O d log(d/() log 2 (n/C)). then
0.90 - Σ 1.1E.
(34)
We pick step size y such that 1) S mmx11))max) ensure that v 1/ Since the covariates his are not corrupted, from Lemma J.3, we know with probability - Ç, for all E S3
||=,1|2 S K2 Tr(E)) log2 (n/S).
(35)
Lemma J.7 implies that if n sal constant C2 such that Sa is, following Definition J.6, with respect to tu",Z,o0 (Acorrupp: a, C2 log" (1/a), C2K²a (1/a), C2 (1/a) C2Ka log (1/a))- corrupt good. Such corrupt good sets have sufficiently large, 1 - accorupts fraction of points that satisfy a good property that we need: resilience. The rest of the proof is under Eq. (34), Eq. (35), and that good is resilient.
O(dd + (og(1/))((23) then there exists univer-
Step 2: Upper bounding the deterministic noise in the gradient. In this step, we bound the deviation of the gradient from its mean. There are several sources of deviation: (t) clipping, (ti) adversarial corruptions, and (iii) randomness of the data noise and privacy noise. We will show that deviations from all these sources can be controlled deterministically under the corrupt-goddeess (i.e., resilience).
Let Φ, = (v2 (1.(5. (0100,))))()))))) which ensures that we add enough noise to guarantee (Eo, DDP for each step of gradient descent. This follows from the standard Gaussian mechanism in Lemma 2.2 and the fact that each gradient is clipped to the norm of O6,, resulting in a DP sensitivity of 00./n. The fact that this sensitivity scales as 1/n is one of the main reasons for the performance gain we get over Varshney et al. (2022) that uses a minimatch of size n// k with sensitivity scaling as k/n. Define gf") := (x, wt M:). For i Sgood, we know y: x w" + 2i. Let 0: clipo (x:)c(pp (1]] w, v1). Note that under Eq. (35), clipa x, for all E S3.
From Algorithm 1, we can write one-step update rule as follows:
W141
1) =w,
Σ
Ji
(4) +
+
11
7
I
(wi - w²) + Σ
3iZ
+
7 n1
(g. (t)
-g!0) - -nov
Σ
g
71
iEG
iEG
IEG
iE iE
(36)
Let F2 = G: :: 0: 1 12. NrTw; w: y be the set of clipped clean data points such that Eie (9:
(8)
gf = EiER, (9: (1)
- 5. (.)). We define è := (L/n) Eieg T24, u, == (1/n) EiEF, I (wi
w*), ut (2) = (1/n) EieF, e, - -, and ut (3) == (I/n) Σ EiesuaaBE 9i
(1)
We can further write the update rule as:
(2) Wr+1 - w = B(w.- - w²) + nu + mu + 1 no.n - mju (3)
(37)
We bound each term one- Since G C S Sgoud and |G| (1 acorrupt) ),, using the resilience property in Eq. (7), we know
||-1//0||| (1 -ccorpppt)
max 1-2 ||||==
Σ
V. (1
acorrupt) )
IeG
< (1 acorrupt ) C22R2aog 2a (1/a)a
(38)
< C2K2alog 20 (1/a)o.
(39)
22

---

Under review as a conference paper at ICLR 2023
Let â | By assumption, we know à (which holds for the given dataset due to Lemma 4.2), and
12-1/32 122-1/2 Σ
2n0e (wz w")l
iE
From Corollary J.8, we know
1
1/2
T3 T (W,- w''l - -1|we w= 11
BB
iE
1
u Σ111/2/ 1/2 p2,, (we, - w¹'ll
max v TT//22 - w²) w:/|o||=1
max w:||u||=1
Eg
iEBL
T 3 1/2 Ttt; 2 1/1122:1//2 w")ll - u T (20e - w²)
max =
Ed
E
1
E. 10-1/22,,07 5-1122 - In) 5. w1)|
w: w:||u||=1
Ee
iEEc
1/2 T2 5-1/2 -Is) E2 - w²)
Σ
Eg
FE
Σ 1/1211,00 I20, E 1-1 -Ia)
(w) (w) w1)ll
iE
2 ã
C₂K² a log 2a (1/a) 1/1. 1ooe-wwlls w01lx
This implies that
Σ
1/22111 (1)
< | |
J: (w: w')l
E
< (ā + 2C2 a log 2a (1/ci) l/ - w'llx:
< a (1/a) ww w") 11x
(40)
where the last inequality follows from the fact that ā I and assumption that C2K2 (l/a) > from Assumption 2. Similarly, use resilience property in Eq. (7) in- stead of Eq. (8), we can show that
Σ 1/2 (2) log
(41)
(3) Next, we consider u, have
Since |Saad < Occorrupt TI and Egl S on, using Eq. (10) and Corollary J.8,
|| 1/2 1/2 (3)
Σ
--12 1/2 x,clipo, (x) w. y.)
max w n
VESuNAUE < 20 Ka (1/o))
< 6C K2 log 24
(1
(1/a)(l - w" +o)
(42)
Now we use Eq. (39), Eq. (40), Eq. (41) and Eq. (42) to bound the final error from update rule in Eq. (37).
Step 3: Analysis of the t-steps recurrence relation. We have controlled the deterministic noise in the last step. In this step, we will upper bound the noise introduced by the Gaussian noise for the purpose of privacy, and show the expected distance optimum decrease every step.
23

---

Under review as a conference paper at ICLR 2023
(2) Define u1 (6 + ub + U1 ut ) We can rewrite Eq. (37)
Wt+1 - w²= -Bww w²) + rque - 176111
(43)
=B w²) + 1 Σ B³ B'u= 11
Co..BBuu
(44)
Taking expectations of E-norm square with respect to vI," Mts we have
(45)
I 2|1 (wo -2--2111 2"'1 + +2E[Iln
B u
+ Σ
Tr(B"'))E('
(46)
i=0
i=0
I 2| (wo - w2)l + 2n
B u ||s BJ [lls
(47)
k=0 1=0
(48)
where at the second step we used the fact that 1/1, 12, -.. are independent isotropic Gaussian.
Note that
BllB'ur-ils = 01151/2/''511/2 1/2 -il
S n/|$1/28855 //12 112-1/2
I 1/111//''1111 p(a) (1lwr- - wllls + o))
1 p(a) (1 w' w'lls: + o)),
where p(a) = 1.1(6C2 + ( (L/a), and the second inequality follows from Eq. (40),
Eq. (41), Eq. (42) and the deterministic condition Eq. (34). Note that the last inequality is true because 77 S 1m(1.1)max) and // 2| I
[ - S Amax 1).
This implies
Bin
B u, Bl
uu llll
(49)
1=0 j=0
p(a)2
4E
+ 1)(j + [BIlwa11 w² [|]+ - -
o²)
(50)
1=
MMaa
(max (max
10 +0²)
(51)
i+1
< 8(log (())) (max E[ll [| ()ap(())(mx)
-
(52)
Then,
1 (wo "2"") "²3 = 1/112 (wo) - w²)l1
< (1 1 w 1 < - -202+1)/ w w01
24

---

Under review as a conference paper at ICLR 2023
and for
(53)
2 llo((1.25/66) xx2 log (n/Cn)C2R k2
(2)) log 20 (00"""11(22/011 (1/(2o)) w/ w01
0²2)
112 2
1511
egn2²
(54)
<4
) (Bll) 02)
(55)
We have
11 2e (|10 20(0lo (max =lloo=--""((')) [E(d]
Note that this also implies that
Bl](wr+e- - w=) 313/ [ee]
22 21/N / - w01l3 + 20p(a)²
22-21/n
( - ucr d²)
(56)
which implies
1
B]ll(u+++ - =="133 s 2e 2// 2//E[l/ -
- w"1 + 20p(a)²
2 [y - -/+ +
1=0
(57)
< 2c 2/<E[[| wp w" 13] + 20(1og 2) p(a))
(max E ///////+=""""" +
iE(1]
(58)
Step 4: End-to-end analysis of the convergence. In the last step, we shown that the amount of estimation error decrease depends the estimation error of the previous 1 steps. In order for the estimation error to decrease by constant factor, we will take t = k. Roughly speaking, we will prove that for every K steps, the estimation error will decrease by a constant factor, if is much larger than O(log x) ){a))a²) This implies we will reach O(log x) o²) error with in ((s) steps.
For any integer 2 0, as long as ((s- [[[[w; - w' [ 2 2(log K) x)² (())002
max (()
E [[[ - w
S
1/2 c
+ (log x) )a)
max ie((s-1)x+1,sm
E[[lu: w= [3]] + (log 2x) Ma))222 (59)
Assuming (log) n²2 < 11/2- 1/e2, the maximum expeeted error in length sequence decrease by a factor 1/2 every time.
Now we bound the maximum expected error in the first length sequence: max [B[[ w" [ Since
B [, w [
Se
21/K 21/0||w0 w0| (log (paz)))((a) max Billu, w" w11l + (log o2
JE(0,1-1]
As function of i, max B[llu, w. w01 only increase when is smaller than
1 -log i) p(a) (1 w' lI (log ((a))))
Thus we conclude
max Elllu: - w. [2 < 1- (log k3) pp( (1100- - w w01l + (log (())) [E(0xx11
s = log([1 (1(((())o) log()1==1/((())))) will give us
E B[llwsk+1 - w² [3] < (log x3 2(
25

---

Under review as a conference paper at ICLR 2023
1 LOWER BOUNDS
1.1 PROOF OF PROPOSITION 3.1 FOR LABEL CORRUPTION LOWER BOUNDS
We first prove the following lemma.
Lemma L.1 Consider an a label-corrupted dataset S = (Zx,,:))= with a < 1/2, that is generated from either 2t (O, 1). y4 1)) or aa (O, 1), ~N a² ), 0z; + 2g. It is impossible to distinguish the two hypotheses with probability larger than 1 /22
In the first case,
[ 0 )
(2x, Ui) ~ Pi P -N(0,
In the second case,
1 a
(2;, ~ P2 = -N(0.
a 1
By simple calculation, it holds that DKL (P1 ( Then, Pinsker's 's inequality implies that Drv (err(Pil(P2))) a/2. Since the covariate 2; follows from the same distribution in the two cases, and the total variation distance between the two cases is less than a/2. This means there an label corruption adversary that change a/2 fraction of y:'s in Pi make it identical to P2. Therefore, algorithm distinguish the cases with probability better than 1/2 under a fraction of label corruption.
1og(1-aa)) a²) S a2/2 for all < 1/2.
Since Σ = o² E [3/4, 1], the first case above has w" O, and the second case has w" a, this implies that no algorithm is able to achieve [|]| - w= ||>=] < aa for all instances with ||w*|| < under fraction of label corruption.
J TECHNICAL LEMMAS
Lemma J.1 (Hanson- Wright inequality for subWeibull distributions Sambale (2020)). Let S (z, E gdin Jizi be a dataset consist of i..d. samples from (K, a) a -ub Weibull distributions, then
P
Σ
|..1 Tr(2) 2t) $2exp 2xxp
min
nt²
nt
}) (60)
KT(Tr(E))²'
(2TT(E)
Lemma J.2. Let Y Lap(b). Then for all h >> we have P([Y) 2 hb) - Lemma J.3. I E 12d is (K, s-sbublilb for some E [1/2, Then
for any fixed v RRd, with probability 1 1.
(,,,0)² < T Eo (1/C)
(61)
with probability 1
||]|| < K2 Tr(2) log (1/C)
(62)
We provide proof in Appendix J.1.1.
Lemma J.4. Dataset S = {z; E Rd Jim1 consists i.i.d. samples from a zero mean distribution DD Suppose D is (K, a) a))subbeibuul Define E = EzzDlaa T.. Then there exists a constant ei > 0 Oucch that with probability 1.
k2dlog(d/() log (n/C)
log
Σ
c1
|E||
(63)
Lemma J.5 (Lemma F.1 from Liu et al. (2022a)). Let x Rd NO0, E). Then there exists
universal constant Cg such that with probability 1
||0|| < C CTT((E)
(64)
26

---

Under review as a conference paper at ICLR 2023
Definition J.6 (Corrupt good set). We say dataset S is (Ccorrupt: a. P1. P2: Ps. Pa)-corrupt good with respect to (w", 2. if is Gcorupt of an (a, P1, P2. Ps. P1) -resiieee dataset Sgood.
Lemma J.7. Under Assumptions and there exists positive constants ei and C2 such that if 2 e1 (i + log(1/())/a², then with probability - Ç. Sgood is, with respect to (w", o, (a, C2 a log2((/o)) C2 a log (1/a), C2 (1/a)) C2K log" (1/2((1)/)))aa (1/a))-resilient.
We provide a proof in Appendix G.
Corollary J.8 (Lemma 10 from Steinhardt et al. (2017) and Lemma 25 from Liu et al. (2022b)). For a (a, Pt, P2, P3, pa) rresilientt set S with respect to (w", Σ,7) and any 0 < ā S a, the following holds for any subset T S of size at least on and for any unil vector Rd;
Σ (u, -x
5
2 2 à
PI Vu
(65)
(TTT)ET
2 à
x0, -0 20
5
p2v'
T Ev
(66)
Z,ET
2 à
Σ
(y:
x. w² 0²)
Ps 0² and
(67)
[T]
(2..UJET
1 [T
Σ (0,
2 ā
P4 V V Ev.
(68)
ZGET
J.1. PROOF OF TECHNICAL LEMMAS
J.1.1 PROOF OF LEMMA J.3
Using Markov inequality,
P (u. x)) 30)222) 2() =P ( 2 )
(69)
1/2 Elelna)
(70)
/// ((BB(1,2))))//20)
(71)
= exp ( (-
62
2/(20)
(72)
K2 xx)
This implies for any fixed v, with probability 1 1-
(x, 0) < K22 T..TEloo Fxx 2
log (1/C).
(73)
For j-th coordinate, let = ej where j E [d]. Definition 2.1 implies
1/(2a)
1/(2a)
E
exp
J K2 K2 Tr(E)
E
exp
51.
(74)
27

---

Under review as a conference paper at ICLR 2023
d-10
1m10.0m),41,,-00
c- 0.1
C-0.
10
10
10-2
Panemntee Extimetion
Eximedio
20
10"
10
10:23
Parcameter
20
10
Samples
Non Private OLS
SSP
Non Private SGD
DP AMB5SGD
DP RobGD
DP RobGD*
Figure 2: Performance of various techniques DP linear regression. d 10 in all the experiments. n 10", = the 2nd experiment. n. 10", in the 3rd experiment.
Note that f(x) x is concave function for < and x >> O. Then (al + ax S aî +... ox
..)
holds for any positive numbers a1.- .a > By our assumption that 1/(2a) S 1. we have
|
1/(2a)
1 + 23
x2 1/(2a)
Elexp
Elexp
(75)
K2Tr(>)
1/(2o)
exp
K2TT(E)
(76)
j=1
1/(2a)
2 d
Elexp
(
(77)
d
$ 1.
(78)
By Markov inequality,
IP [| 2 t) = TP (ell=liVo 6e
(79)
S t//1 B Bielle|///og
(80)
1/(2a)
$ exp
(81)
K2 Tr(E)
This implies with probability S.
||=||2 < K2 Tr(E) log 2og22(11 (1/C)
(82)
K EXPERIMENTS
K. DP LINEAR REGRESSION
Experimental results for c = 0.1 can be found in Figure 2. The observations are similar to the c = case. In particular, DP-SSP has poor performance when is small. In other settings, DP-SSP has better performance than DP-ROBGD.
K.2 DP ROBUST LINEAR REGRESSION
In this section, we consider a stronger adversary for DP-ROBGD than the one considered Sec- tion 5, Recall, for the adversary model considered in Section 5, DP-ROBGD was able to consistently estimate the parameter w" (i.e., the parameter recovery errоr goes down to 0 as n + oo). This be- cause the algorithm was able to easily identify the corruptions and ignore the corresponding points while performing gradient descent. We now construct a different instance where the corruptions hard to identify. Consequently, DP-ROBGID
longer be consistent against the adversary.
28

---

Under review as a conference paper at ICLR 2023
100
20-1
Parametter Extimaation
+7377
10
Peremeter
10-1
10-5
10"
10'
10:7
10"
Number Samples
fraction of corruptions
Figure 3:
Performance against the stronger adversary
This hard instance is inspired by the lower bound in Bakshi & Prasad (2021) (see Theorem 6. of Bakshi Prasad (2021)). This is a 2 dimensional problem where the first covariate is sampled uni- formly from 1. The second covariate, which is uncorrelated from the first, is sampled from distribution with the following pdf
if x E (-1,1}
((x
I-o
if xf [-
20d
otherwise
We set a = 0.1 in our experiments. The noise 2; sampled uniformly from [-a, We consider two possible parameter vectors w 1) and w² (1,-1), It can be shown that the total variation (TV) distance between these problem instances (each parameter vector corresponds to one problem instance) is ((a) (Bakshi & Prasad, 2021). What this implies is that, one can corrupt at most fraction of the response variables and convert one problem instance into another. Since the distance (in E norm) between the two parameter vectors is ((a)), any algorithm will suffer an error of Q(ar).
We generate 10" samples from this problem instance and add corruptions that convert one problem instance to the other. Figure 3 presents the results from this experiment. It can be seen that our al- gorithm works as expected. In particular, recovery error increases with the fraction of corruptions.
not consistent in this setting. Morcover, the parameter
29


Reviews:
[{"review_id": "rAb3FdOqCP", "reviewer": "Reviewer_gANM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of differentially private linear regression with potentially corrupted labels. To handle the corrupted labels, the authors proposed a new private adaptive clipping technique. The proposed method can deal with both privacy concerns and corrupted labels. The experiment results validate the effectiveness of the proposed method in the corrupted setting. Furthermore, the authors claim that the proposed method can also improve the sample complexity requirements to achieve a certain level of accuracy in the noncorrupted case compared with existing methods.", "summary_of_the_review": "The author proposed an efficient, robust, and differentially private algorithm for solving the linear regression problem. The proposed method seems to be promising. However, it suffers from the low corruption level and the improvements over the previous method in the noncorrupted setting are unclear.", "strength_and_weaknesses": "The strength of the paper:\n1. The proposed method is able to handle corrupted labels.\n2. Experiments validate the effectiveness of the proposed method.\n\nThe weaknesses of the paper:\n1. In the noncorrupted setting, it is unclear to me why it can improve the sample complexity requirement compared with Varshney et al. 2022. For the minibatch method proposed by Varshney et al. 2022, it seems that the minibatch size is chosen in the order of the full batch size. Thus it is unclear to me why using the full gradient as suggested in this paper can improve the sample complexity? Whether the improvement comes from Algorithm 2? These need to be further clarified.\n2. The requirements on $S_1$, $S_2$ and $S_3$ are not clear.\n3. Why the requirement of $n$ in equation (5) is independent of $\\kappa$? According to the last inequality on Page 16, it seems that the $\\bar \\alpha$ depends on $\\kappa$, and thus $n$ should also depend on $\\kappa$.\n4. Although the proposed method is able to handle label corruption, the corruption level is so small that it should be less than the desired accuracy level. Can you relax this requirement?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cG9mkkPz9r", "reviewer": "Reviewer_p2zY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies linear regression from i.i.d. examples under $(\\epsilon, \\delta)$-differential privacy in the settings (i) where there is no adversary and (ii) when a fraction of response variables are adversarially corrupted. While there exists a clear understanding about the optimal (inefficient) private and robust algorithm that solves this problem (namely the HPTR algorithm), it is not known whether this optimal sample complexity can be attained by a computationally efficient algorithm. Hence, this paper aims to improve on the number of samples required by the previous best-known algorithm by Varshney et al. (2022). This improvement is obtained by DP-SGD with some additional ideas.\n", "summary_of_the_review": "The authors provide an efficient private and robust algorithm for linear regression, improving on the previous sample complexity bound. I believe that the contribution is beyond the acceptance threshold. ", "strength_and_weaknesses": "At a technical level, the authors analyze DP-SGD for the linear regression problem (without an adversary) using two additional ideas. First, the work of Varshney et al. (2022) proposes a single pass approach while, in this work, a full-batch gradient descent algorithm is employed. This gives an improvement in the sample complexity. Second, adaptive clipping is used in order to ensure robustness against label-corruption. \n\nIn general, the paper is interesting and the result is nice. The  proposed private algorithm attains an improved sample complexity guarantee while being computationally efficient and robust to label noise. My main concern deals with the issue of technical novelty; the paper relies on standard techniques for achieving privacy (e.g., private histograms) and robustness (e.g., resilience). While the clipping idea is nice, it is essentially ad-hoc for label noise and cannot handle corruption in the covariates. Nevertheless, I believe that the contribution is sufficient for acceptance.\n\nThe paper is mostly well-written (there are various typos that can be fixed) and the results and previous work are clearly presented. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XsSGeeBvacg", "reviewer": "Reviewer_bBtg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors study linear regression from a differential privacy perspective. They propose a variant of the differentially private stochastic gradient descent (DP-SGD) algorithm with two innovations: a full-batch gradient descent to improve sample complexity and an adaptive clipping to guarantee robustness. Some theoretical results and empirical evidence are presented.\n", "summary_of_the_review": "This is an interesting paper overall, but when we dig a little deeper there are several unanswered questions. \n", "strength_and_weaknesses": "Strengths:\n\n\nAuthors have a good grasp of some of the challenges of differentially private computations in the linear regression context. The paper is well-written. Section~4 on adaptive clipping is an interesting contribution, where I think the results can be improved, but the approach of using a a robust approach and trying to enforce differential privacy on it is interesting. \n\n\nWeakness:\n\nA few of the weaknesses are technical and can possibly be easily corrected. However, some of the weaknesses are probably not adjustable with minor changes. \n\n1) The use of sub-Weibull distributions is more of a distraction. This is primarily because we would want the differentially private estimator to have consistency and other desirable statistical properties, for which sub-Gaussian conditions are often necessary. It is not clear what sub-Weibull adds to either the robustness or differential privacy components of this paper. Also, this assumption does not seem verifiable. \n\n2) The requirement that $\\bar{\\alpha}$ is known in Assumption 2, and the complex bound for it seem unverifiable and not very practical. \n\n3) For high-dimensional regression, it is not clear that the proposed scheme can achieve sparsistency. \n\n4) Along the same lines, it is entirely possible that the norm or non-zero elements of a sparse $w^{*}$ may not have any relation with the leading eigen values/vectors of $\\Sigma$. Hence it is not clear the bounds for the weighted loss function considered here relate to the sparsity of $w^{*}$ or the noise variance.\n\n4) Also, it is not clear what additional complexity is arising from the corruption in the labels arising from an adversarial framework. This would only make sense if an oracle knew the original observations (indexed by $S_{r}$), and the proposed algorithm achieved some kind of a risk bound with respect to this oracle. Since the corruption can be arbitrary, it seems a standard robust statistics approach would have been sufficient here. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "V-quNTV2_p", "reviewer": "Reviewer_gS7K", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of linear regression under DP constraint and adversarial corruption. The authors propose a kind of variant of DP-SGD with a full-batch GD to improve sample complexity and adaptive clipping to guarantee robustness. Their theoretical results can improve the SOTA sample complexity without adversarial corruption. Under label corruption, they give the first provably linear regression algorithm to guarantee both DP and robustness. They also give experimental results on synthetic data to verify their theoretical results.\n\n", "summary_of_the_review": "The lower bound is not clear. ", "strength_and_weaknesses": "Strength:\nThe paper is well-motivated since privacy and robustness become more and more important in ML model. This is the first efficient linear regression algorithm to provably guarantee both DP and robustness. The authors propose a private norm estimator and a robust private distance estimator by using private histogram mechanism for adaptive clipping and also give theoretical results for this algorithm. Based on this algorithm, they propose their DP-SGD method. The authors give both theoretical sample complexity and experimental results for the method. The proofs seem to be correct, and the experimental results also accord with their analysis.\n\nWeaknesses:\n1. The lower bound in Section 3.3 is not clear.\n2.  The ‘n’ in equation (1) should be B_t.\n3.  The step 1 of algorithm 1 should be three subsets.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject