Label Robust and Differentially Private Linear Regression: Computational and Statistical Efficiency
Authors: Xiyang Liu
Prateek Jain
Weihao Kong
Sewoong Oh
Arun Suggala
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy; Private Estimation
TL;DR: We provide the first efficient algorithm that achieves a near-optimal rate for DP linear regression and achieves privacy and robustness against label corruptions simultaneously.

Abstract: We study the canonical problem of linear regression under $(\varepsilon,\delta)$-differential privacy when the datapoints are sampled i.i.d.~from a distribution and a fraction of response variables are adversarially corrupted. We provide the first provably efficient -- both computationally and statistically -- method for this problem, assuming standard assumptions on the data distribution. Our algorithm is a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two key innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. Our method requires only linear time in input size, and still matches the information theoretical optimal sample complexity up to a data distribution dependent condition number factor.  Interestingly, the same algorithm, when applied to a setting where there is no adversarial corruption, still improves upon the existing state-of-the-art and achieves a near optimal sample complexity.

Label Robust and Differentially Private Linear Regression: Computational and Statistical Efficiency
Xiyang Liu
Prateek Jain Google Research praj prajain@google.comm com
Paul Allen School of Computer Science & Engineering
University of Washington
xiyangl@cs wiyaangles..washington.... edu
Weihao Kong
Sewoong Oh
Google Research
Paul Allen School of Computer Science & Engincering University of Washington, and Google Research sewoongêcs washington. edu
welhackong@google.ccom com
Arun Sai Suggala
Google Research arunss@google. com
Abstract
We study the canonical problem of linear regression under (e, -ddifffrrett privacy when the datapoints sampled i.i.d. from distribution and fraction of response variables are adversarially corrupted. We provide the first provably efficient both computationally and statistically method for this problem, assuming standard assumptions on the data distribution. Our algorithm a variant the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two key innovations: a full-batch gradient descent to improve sample complexity and novel adaptive clipping guarantee robustness. Our method requires only linear time in input size, and still matches the information theoretical optimal sample complexity up data distribution dependent condition number factor. Interestingly, the same algorithm, when applied to setting where there is no adversarial corruption, still improves upon the existing state-of-the-are and achieves near optimal sample complexity.
Introduction
33 is standard notion of privacy widely adopted by both industry With widespread usage of ML and statistical techniques, DP becomes even more critical ensure private information of participating individuals is not revealed in any form via the learned model. An statistical estimator is said to be (s, d) -iiffeerrentlll private if presence/absence of individual's 's data point in the dataset does not significantly change the estimated output. Smaller e > 0 and & E [0, 1] imply stronger privacy guarantees.
Differential Privacy (DP)
and government 76. 35
36
2
While privacy preserving statistical estimators have been studied extensively in recent past, several critical questions remain open (see App. A for a survey). Consider the canonical statistical task of linear regression with i.i.d. samples, (x; E Rd , E [R) drawn from I; (0, Σ), _.7 w" 2i, (O,, 22) and E[ [ 0 for some true parameter w² E IRd. The emror is measured in (1/r)][æ 20 - w*llx == (1/a)]
w²)l, which correctly accounts for the signal- to-noise ratio each direction; the direction of large eigenvalue of Σ, we have larger signal x;
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

but the noise 2; remains the same. We expect smaller errors in those directions, which is accounted for in the error measure (1/o)]] w' ||x.
Minimax optimal sample complexity for estimating the optimal linear regression model with DP was recently established. For the lower bound, using recently introduced score attack technique, [16] Theorem 3.1] shows that n S2dd/a + d/ (Ea)) samples are necessary to achieve an error of (1/o)][ı I|x (in expectation). For the matching upper bound, High-dimensional Propose- [T0] show that n Ö(d/ a2d +d/ (Ea)) samples are also sufficient. The first term of d a²² is the fundamental sample complexity even if privacy is not required, and the second term of (ea)) is the cost of privacy.
Test-Release (HPTR) in [61] and Robust-to-Prive
This implies that, statistically, the problem appears to be solved. However, computationally. the problem is still open despite multiple studies of the problem. That is, the statistical optimal algorithms still take exponential time.
After series of efforts in computationally efficient approaches as surveyed in App. A
81 achieves
the best known sample complexity of n = O(d/a² + xdd/ + x² x²d/z), where is the condition number of the covariance Σ of the covariates. Compared to HPTR, the cost of computational efficiency is factor of к in the second term and the third term that is unnecessary. As the condition number can be quite large, improving the dependence on K is of utmost importance. Furthermore, the technique of [81] strictly requires sampling without replacement, whose analysis relies on having an explicit form of the end-to-end update. In particular, their analysis technique is not applicable to the case with corrupted samples.
In contrast, we propose a novel method (Alg. D that builds upon full-batch gradient descent and applies carefully chosen adaptive clipping which is a general technique used in practice as well D. Together with an intuitive but intricate analysis technique. we improve the sample complexity to n = O(d/a² + x x2/² d/(()))())))))))
Corollary 1.1 (Corollary of Thm. 3.1 for sub-Gaussian data). Alg. D is (c,8)-DP. Let S = (a ys) }=) be a dataset of i.idd samples with xi NO, Σ). y1 - x w* + 2, and 2 ~N(0, 0²) for some unknown true parameter w" = E(g,a E Rd and unknown E and 0². Then ='d + <>/2d/(ea)) samples are sufficient for Alg. 1 to achieve (1/a)ll0- - w'll> || Ö(a)
with high probability, where k := >maxx (E) (0m//min( (E).
Due to space constraints, we focus on nab-Gaussian distributions in the main text and provide comparisons to prior work in Tab. [ Our analysis in App. H. applies to more general family of light-tailed distributions, called sub-Weibull. Next, when the noise the samples heavy-tailed, a similar algorithm can be applied with carefully chosen clipping thresholds to account for the heavier tail. Concretely, for k-th moment bounded distributions, the tail of the distribution gets increasingly heavier with smaller k. This would require larger number of samples to achieve the same accuracy, which is captured in our sample complexity of n O(d/a2k/(kk) + x (sa((s((((()1)))) We explain the heavy-tailed setting, provide a detailed analysis and a proof, and discuss the results in App. L This is the first efficient algorithm with provable guarantees achieving (s, 8D-P.
Corollary 1.2 (informal version of Coro. L.7 for heavy-tailed noise). Alg. 4 is (E.5)-DP. Let S = ((,,,))) b:) be a dataset of i..dd samples with 2; ~ NO Σ), yi = xz w + 2s. and the zero-mean, independent, and heavy-tailed noise 2; satisfies | = 0(1) for some unknown true parameter w² E Rdd and unknown Σ and o². Then n = (dd/ 2k/kk) + (sa22/(saa/(((11)) samples are sufficient for Alg. high probability, where k Amaxx
4 in App. to achieve an error rate of (1/a)]| wl = Ō(a) with
(E))
Perhaps surprisingly, we show that Alg. [ is also robust against label-corruption, where an adversary selects an arbitrary acorrupt fraction of the data points and changes their response variables arbitrarily. Ideally, we want a robust algorithm against a stronger adversary who can corrupt the covariates also. However, even for a simpler problem of private mean estimation, achieving robustness against such a strong adversary with Odd) samples requires heavy machinery (convex relaxations of sum-of-squares optimization) with significantly more computations (although polynomial) (45).
Our lower bound in Prop. 3.9 together with the lower bound in [6 on the uncorrupted case, shows that n = Q(d/a² + d/ (ea) samples are necessary to achieve an error rate of (1/a)]]и- - w wi =
((a + A.orrupt). In particular, it is impossible to achieve an error below acorrpp even if we have

---

Table I: Suppose data is drawn from linear model in d-dimensions from sub-Gaussian covariates with covariance Σ and sub- Gaussian noise with variance o². To achieve an error rate (1/a) / w" ""Il>: || = a with (c, -DD DP-RobGD requires the least number of samples among computationally efficient algorithms. This improves over [8T] by factor of x²/² in the second term, where is the condition number of Σ. We hide polylogarithmic factors d, k. and 1/6. DP-Theil-Sen only analyzed when and its dependence εe is unknown.
Algorithm
Runtime
Sample Complexity
TukeyEM 6
poly
guarantee
DP-Theil-Sen
poly
d2
k
Ea
DP-AMBSSGD 8
poly
a2 + d
K
k
DP-RobGD [Theorem 3.8
poly
a² +
d
og
1/2
ca
HPTR [6], cobust-to-private
10
exp
a +
d'
Lower Bound [66
a²
ca
infinite samples (Prop. 3.9 and hence there no need aim for < Occorrupt This lower bound is matched by exponential time approaches, HPTR in [6]] and Robust-to Priitt--revteeeee in (I0), which also guarantee robustness. Currently, there no efficient algorithm that can guarantee both privacy and robustness for linear regression. To this end, we provide the first efficient algorithm guaranteeing both, with a sample complexity that is optimal to a 2//2 factor.
Corollary 1.3 (Corollary of Thm.
H.3 for sub-Gaussian data with adversarial label corruption). suppose Ocorrupt Ocorrup--fractin of the labels are corrupted arbitrarily.
Under the hypotheses of Coro.
T.I.
Then Od/a22 + k² /2/
[Ea)
samples are sufficient for Alg. 1 achieve error rate of
(1/o))lı w 11 Ō(a (coorrup)) with high probability, where K >max(2))////ammam (2i)//mmn)2))
When Occorupt = 0, this recovers the non-robust result from Coro. 1.1 A similar robustness guarantee
also holds for heavy-tailed settings. We provide formal statement App-[[
Contributions. For a canonical problem of private linear regression under sub-Gaussian distributions, the best known efficient algorithm [8]] requires
n = δ (
d
Rd
R2d
Ea
achieve (1/a)ll0- w=llx a. We provide the first efficient algorithm that improves this
n 0 d
k2/2d
80
which nearly matches the exponential-tin algorithms [61]T]] and the lower bound [66 up 1/2 in the second term. For the same problem, we show that the same algorithm is the first to achieve robustness against adversarial corruption of the labels.
Under a heavy-tailed tailed distribution of the noise, we provide the first computationally efficient algorithm, the best of our knowledge, that achieves sample complexity close that of exponential-time algorithm of [61] There is no matching lower bound in the heavy-tailed setting. This is also the first efficient algorithm to achieve robustness against adversarial corruption of the labels under heavy-tailed noise.
2 Problem formulation and background
When there is no adversary, we present results under the standard linear model with sub-Gaussian covariates and noise. In App. H we present more general family of (K, -.sbb-Webbblllll Weibull distributions that recovers the standard sub-Gaussian family special case when a 0.5. The necessity of such assumptions on the tail is explained in Sec. 3.4
Assumption 2.1 nub--Gaussian model). We have i.i.d. samples S = ((x; E Rd yr E {R)]2 from distribution PE of linear model yı (I,, w²) + 24. where the input vector I; has zero
3

---

mean B[z;] = 0 and a positive definite covariance Σ := B[r,æ] > 0, and the (input dependent)
label noise 2; has zero mean E|2,] and variance o² := E [ We further assume E|z,2,| =
which is equivalent to assuming that the true parameter w² = Σ TE Flyya; We assume the marginal
distributions of T3 and 2, are K -ub--aussian with K = ((1): ), as defined below.
Definition 2.2. x: E R2 is
(v.a)² if for all e E IR E exp (<
S 2.
Given dataset S that is i..dd sampled from Pxa we ,²2 satisfying Asmp. 2.1 our goal is estimate w" that minimizes [//o)ll@ w=Ilx which is also equivalent to minimize the excess population risk, i.e. [(w") (()) where C(w) = ((e,))>P w [(y (w,x)))]
Notations. A vector x E Id has the Euclidean norm ||||| For a matrix M, we use || to denote the spectral norm. The error is measured in || =" w'I := 22 ==w) w²)l for some PSD matrix E. The identity matrix is denoted by I E Rdxd Let [n] = (1.2..... n). Ō(.) hides some constants terms, K- (1), and poly-logari terms in n, d, 1/e. log(1/0), 1/C, and 1/Ccorrupt. For vector x E Rd we define clip,(2) == x min al/l///]]
Background on DP. Differential Privacy a standard measure of privacy leakage when data is accessed via queries, introduced by [3 Two datasets S and S' are said to be neighbors if they differ at most by one entry, which is denoted by ~ S' stochastic query q is said to be (c, 6)- differentially private for some 5 > 0 and 8 E [0, IJ, if PP(((S) E A) S Pa(((( E A) + 8, for all neighboring datasets S ~ 5" and all subset A of the range of the query. We build upon two widely used DP primitives, the Gaussian mechanism and the private histogram. A central concept in DP mechanism design is the sensitivity a query, defined as Ag == sups (l{(S) ((S))l We describe Gaussian mechanism and private histogram in App. B
2.1 Comparisons with the prior work
The state-of-the approach introduced by [8] is based on DP-SGD (7], where privacy ensured by gradient norm clipping and the Gaussian mechanism. Two additional technical components are adaptive clipping and streaming SGD. Adaptive clipping with an appropriate threshold 0, ensures that no data point is clipped (under the sub-Gaussian assumption), while providing a bound on the sensitivity of the average mini-batch gradient (to ensure we do not add too much noise). The streaming approach, where each data point is only touched once and discarded, ensures independence between the past iterate W,y and the gradients at round + 1, which the analysis critically relies on. For T = ((s) iterations where λ. is the condition number of the covariance E, the dataset S = (( y1) = is partitioned into [B, ( subsets of equal size: |B. = (nn/k)) 3 At each round the gradients clipped and averaged with additive Gaussian noise chosen to satisfy (c, 6)DD:
Wi+1 + Wt (7(
1 B.
Σ iEB,
clipo, (I, x, - v)) + Pe log( 1.25/6)
1/:)
(I)
el [.
where 44 ~ NO, Iz). In 81 slight variation of this streaming SGD is shown achieve an error of [/ w" w0|l= = with O(d/a²+ kd/(sa) + x²d/s) samples (Row in Tab. [..
Our technical innovations. Our approach builds upon such gradient based methods but makes several important innovations. First, use full-batch gradient descent, opposed to the streaming SGD above. Using all n samples reduces the sensitivity of the per-round gradient average by a factor, and thus decreases the privacy noise added in each iteration. This improves the second term of sample complexity from kd/(sa) to x//2d/(se d/(=a) and removes the third term completely. However, full-batch GD loses the independence that the streaming SGD enjoyed between wy and the samples used in the round t + 1. This dependence makes the analysis more challenging. We instead propose using the resilience to precisely track the bias and variance of the (dependent) full-batch average gradient. Resilience is central concept in robust statistics that links the tril-property of the distribution to the bias, which we explain in Sec. 5
Next, one critical component in achieving this improved sample complexity is the new analysis technique we introduce for tracking the end-to-end gradient updates. Since our gradient descent algorithm is not guaranteed to make progress every step, cannot use the vanilla one-step analysis.

---

Taking the full end end-to-end analysis by expanding the whole gradient trajectory will introduce too many correlated cross-terms which are very hard to control. Therefore, we leverage an every K-step analysis and show that the objective function at least decreases geometrically every K steps. To be more specific, our analysis technique in App. H (steps and 4) opens up the iterative updates from the beginning the end, and exploits the fact that Amax (172))(
(22))))))) is upper bounded by 1/(t + 1) when |n>]|| < 1. This technique is critical in achieving the near-optimal dependence in R. This might be of independent interest other analysis of gradient-basee algorithms. We refer to the beginning of step 3 in App. H for detailed explanation.
Finally, we propose novel clipping that separately clips æi and (w, xx y1) in the gradient. (1] 2; y.)2,, This is critical in achieving robustness to label-corruption, as we explain in Sec. 3.1
Label-robust and private linear regression
We introduce a novel gradient descent approach. This achieves an improved sample complexity compared to the state-of-the-art algorithm and robustness against label corruption.
3.1 Algorithm
The skeleton of our approach in Alg. is the general DP-SGD 7 with adaptive clipping (7]. We partition the dataset into three equal-sized subsets: $1, S2, S3. S and S2 are used in adaptively estimating the clipping thresholds, and S3 is re-used every step to compute the average gradient.
The standard adaptive clipping, e.g.. 81], is not robust against label-corruption. Under sub- Gaussian distribution, a positive fraction of the covariates, 2n rr's, can be close to the origin. If the adversary chooses corrupt those points with small norm, || |l. they can make large changes in the corrupted residual, (y4- W. z4), while evading the standard clipping by the norm of the gradient; the norm of the gradient, ||a,, (w; w, xx:)l = ||=;|| 1y;- w. zzl. can remain under the threshold. This is problematic, since the bias due to the corrupted samples in the gradient scales proportionally to the magnitude of the residual (after clipping). To this end, we propose clipping the norm and the residual separately: clipe(1; [c,ppp (ur, T. - v.). This keeps the sensitivity of gradient average bounded by (0,). The subsequent Gaussian mechanism line 11 ensures (Co. 5DP each round. Applying advanced composition in Lemma B.5 of T rounds, this ensures end-to-end (c, S)-P.
Novel adaptive clipping. When clipping with clip (zx), 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 robust as there is 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 (Lemma J.3 we estimate
upper bounded by ||= 2|2 < <TTT(EE log(1/() with probability the unknown Tr(2) using Private Norm Estimator in Alg. 3 in App. F and set the norm threshold
O = K /21 log(n/C) (Alg. line 4). The n in the logarithm ensures that the union bound holds.
When clipping with clipe, (w) xy - y.). the purpose of clipping the residual by its magnitude, |y; - w., æz| I(w" we) x, + 2ıl. is to bound the sensitivity of the gradient and also to provide robustness against label-coruption. We want to choose a threshold that only clips corrupt data points and at most a few clean data points. In order to achieve an error (1/o)][uus 1y wr]ls: = we know that any set of (1 a) fraction of the clean data points is sufficient to get a good estimate of the average (llur w"
1| w0 + CKK log(1/(2a))) Lemmal J.3 guarantees that the unclipped subset will be large enough, i.e., (1 a)n. At the same time, this threshold on the residual small enough to guarantee robustness against the label-corrupted samples. We introduce the robust and DP Distance Estimator in Alg. to estimate the unknown (squared and shifted) distance, ||w,,-''
gradient. By clipping at (w' - w.) TT; x; + 2,
-ireww" w" 11 +o2. and set the distance threshold 0, = 2//2H
K /
/92
(og(1/(2())
(Alg. [ line 7). Both norm and distance estimation rely on DP histogram (Lemma B.2 but over set
of statistics computed on partitioned datasets, which explain in detail in App. C
5

---

Algorithm 1: Robust and Private Linear Regression
Input: 5= {(x, y:) y:) DP parameters (E, T, learning rate 7), failure probability Ç, target a, distribution parameter K
Partition dataset S into three equal sized disjoint subsets $ = S1 U. U..
do f
8 20 loTlog((/bu) So f Š. wo + 0 60. Co)
3 -- PrivateNormEssimattr(....
11 using Alg.
3
App
④ Kv2T (ogg((/(")) (n/So)
for 0, 1.2. 7 do
7t < PrivateeDistanceessinnttoor
We,Co, 6o, a, Co) 2/27 V /9C2k² (2a().
// using Alg.
App-
Sample v1 ~ N (0, Ia)
g. + clipe (2, )llip, (a. Wi yi)
10
Φ: (v (00g(1.)//)))0))
W++11 We 17 Eies, 0100 + tvv))
12
Return WT
3.2 Analysis without adversarial corruption
We show that Alg. [ achieves an improved sample complexity. We provide the proof for a more general class of distributions in App- H and sketch of the proof in Sec. [ We address the necessity of the assumptions in Sec. 3.4 along with some lower bounds.
Theorem 3.1. Alg. is (e, 6)-D.. Under sub- Gaussian model of Asmp. 2.1
for any failure probability
Ç E (0, 1) and target error rate as if the sample size is large enough such that
/2 log( ( log(t)
Ō K2 Kodlog"
d d+ +
(t)+
(2)
a²
Eα
with a large enough constant, then the choices of a step size 17 1= 1/CCCCCCmaaa (E)) for any C 2 1.1 and the number of iterations, T θ (ı log ([Iw"]) []) for condition number of the covariance = Amnax (E) Xmiin (E), ensures that, with probability 1 Alg. Dachieves
Bn ( [[] - - w" w01 0 k o² log?
(2))
(3)
where the expectation taken over the noise added for DP, and Ô and G()) hide logarithmic terms in K, a, d, 1/e, 1og(1/8), 1/a, and k.
Remark 3.2. Omitting some constant and logarithmic terms, Alg.
requires
n 0( d +
k1/2d
(4)
a
samples to ensure an eπrоr rate of (L w w0 = From 16 Theorem 3.1], there exists an = 22d/a² + d/(ea)) lower bound, and our upper bound matches this lower bound up to factor of x 1/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 the state-of-the-art. The best existing efficient algorithm by [8]] requires n Ódda²² + kd/(sa) + x²d/E) achieve the same error rate. Compared to Eq. (4). the second term is larger by a factor of 22/2 compared to the second term in Eq. 4 Further, [8] requires xdd/s, which is not needed in Eq. d4).
Ō(²²).
(N, Ia) and 2 ~ (0, 2²) such that the condition number is one, our bound given by Eq. 4 nearly matches the lower bound (116, Theorem 3.1 up to logarithmic factors.
Remark 3.3. Consider the standard settings of linear regression with
Remark 3.4. Note that the leading term in Eq. is the first term d/a² when target error a S S//2//2 Our first term is independent of x. which matches the lower bound for non-private lincar regression.

---

Remark 3.5. The third term x²d/= in 81 is independent of error rate a but scales as x². This term required to ensure the privacy noise added in each iteration is small enough for their DP-SGD to make progress (Appendix. B.2.2 in [I). Our algorithm is based on full-batch gradient descent, which uses all n samples and thus reduces the sensitivity of gradient average by x: factor. we show in Eq. (59) that our algorithm only requires n = ((11))) ) to make progress for each iteration. This is strictly smaller than our dominant term K x2/2d/(Ee)) (Ea) and does not show up in final guarantee. We provide formal proof in App. [+]
result,
Remark 3.6. One of the key innovations in Alg. Tis the adaptive distance estimator (Alg 2 in App The goal is to privately estimate the (shifted) distance of the current estimate, i.e., || w >> + o² without the knowledge of u*. We show Thm. [.I that our novel distance estimator only requires an error-independet sample complexity n O(x- Note that the DP-STAT (Algorithm 3 in [8]) can also be used to estimate the distance. But it requires the knowledge of domain size ||w" || + a. We completely remove this requirement, improve the dependence on K and (ng( and show it is also robust, as introduced in the next section. We provide the algorithms and analysis in App.[land the formal proof in App. D
to achieve a constant multiplicative error.
3.3 Robustness against label corruption
We assume there exists a good dataset Sgnod that satisfies Asmp 2.1 We only get access to a label- corrupted dataset under the standard definition of label corruption, e.g., [15]. There are variations in literature on the definition, which we survey in App.
Assumption 3.7 (Ccarapa-corrption) Given a dataset Sgood = {(r, y))) 1. an adversary inspects all the data points, selects d'corrupt data points denoted as S,,, and replaces the labels with arbitrary labels while keeping the covariates unchanged. We let Shad denote this set of acorrupt newly labelled examples by the adversary. Let the resulting set be Scorrupt := Sgood U Shad \ Sp..
Our goal is to estimate the unknown parameter w", given corrupted dataset Scorrupt. distribution parameter K, and (an upper bound on) the corruption level Ofcorrupt.
Under the non-private scenario, i.e., E 0c, recent advances led to optimal algorithms for linear regression that are robust to label corruptions [15] [2]; if the corruption level is smaller than the target error rate, i.e., Ccorrupt S a, then n = ((d/ a²) samples are sufficient to achieve an error rate of (1/a)][0 w' w'l1s= = a. The sample complexity of d/a² is optimal as it matches the information theoretic lower bound. The condition Occorrupt S a is necessary since it is information theoretically impossible to achieve error a less than Ocorrupt, as we prove in Prop. 3.9 Setting the target error to the minimum possible value of a Orcorrupt: we say that these algorithms achieve optimal robustness since the minimum robust error rate of (1/o)]læ w' = ((Ccorrups) can be achieved with minimal sample complexity of n Ö(d/a² (orrppt) We aim to achieve such optimal robustness simultaneously with differential privacy in a computationally efficient manner.
Theorem 3.8. Under sub- Gaussian model of Asmp. 2. and Gcorrupe- corruption of Asmp. 3.7 if
the corruption level is below the target error rate, a 2 Gcorrupt, then n = O(d/a² + k2/2d (Ea)) samples are sufficient for Alg. to achieve an error rate of (1/02)
w" 1 = Ō(a)).
This is the first efficient approach to achieve robustness and (e, 6)-DP simultancously. The existing such algorithms take exponential time [6] Corollary C.2] and 100, but achieve optimal sample complexity of n Od/ + d/ (sa)). Notice that there is no dependence question if computationally efficient private linear regression algorithms can achieve such an optimal s-independent sample complexity. We make the first advance towards this ambitious goal with the above theorem. Our sample complexity is sub-optimal only by a factor of /K in the second term. This is achieved by individually clipping the covariate, Ii, and the residual, (w, x4 yi), in Alg. and carefully tracking the bias of clipping with the use of resilience in the analysis in App.
It remains an open
3.4 Lower bounds
Necessity of our assumptions. A tail assumption on the covariate x, such as Asmp. 2.1 is necessary to achieve n = (d) sample complexity in Eq. (4). Even when the covariance Σ is close to identity, without further assumptions on the tail of covariate I, the result in (13] implies that for 8 < 1/n, it is necessary for an (E, estimator to have n (2d2/2 samples to achieve
7

---

6-10 --lt))
Feremeeee Extimation
Eximmtoo
10ah
Partinetee Fictmatton
10"7
10--
20
10"
10"
10" 10a
10'
Number Samples
Private
DP-SSP
DP-AMBSSG
DP-RobGD
DP-RobGD*
Figure I: Performance of various techniques on DP linear regression. d 10 in all the experiments. n 10", A = in the 2nd experiment. n = 10", a = in the 3rd experiment, where x is the condition number of 2 and o² is the variance of the label noise 24.
||0 "nw==l>> || ((a) (see Eq. (3) in 83 Note that this lower bound is factor /2/2 larger than upper bound that benefits from the additional tail assumption.
A tail assumption on the noise 2; such as Asmp. 2.1 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. [6]] Proposition C.5] implies that for 5 = e - and 4-th moment bounded 2; and any (s, 6DDP estimator requires n = 22dd (Ed/) which is factor of 1/a larger, to achieve (1/a²)ll - w w=||> Ō(a).
(dd((a))
The assumption that only labels are corrupted is critical for Alg. I The average of the clipped gradients can be significantly more biased, if the adversary can place the covariates of the corrupted samples in the same direction. particular, the bound the bias of our gradient step in Eq. (44) in App. would no longer hold. Against such strong attacks, one requires additional steps to estimate the mean the gradients robustly and privately, similar to those used robust private mean estimation [60 56 44 g There is no known linear-time algorithm to achieve this, and this is outside the scope of this paper.
Lower bounds under label corruption. Under the Ocoerupt label corruption setting (Asmp. 3.7p with infinite data and without privacy constraints, algorithm is able learn w" with Eg error better than Gcorrupt. We provide formal derivation for completeness.
1.7pp..7)
Proposition 3.9. Let " KK be a class of distributions on (Iii from in Asmp. 2.7 Let Sn,a be an a-corrupted dataset of n i.i.d. samples from some distribution DD E Dr so* K under Asmp.3.7 Let M be class of estimators that are functions over Sn,cx. Then there exists a constant such that minn,DeM
model
maxs,, DED p se W
[B[l
w w1 c o².
A proof is provided in App. L A similar lower bound can be found in M Theorem 6.
4 Experimental results
4.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 App.[K. K 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 {>,);- are first sampled from (0, Σ) and then projected to unit sphere. We consider diagonal covariances Σ of the following form: Σ 0] = K, and E(i, i] = 1 for all i 2 1. Here k 2 1 is the condition number of Σ. We generate noise 2; from uniform distribution over [-o, a)). Finally, the response variables are generated as follows y4 x =" 24. All the experiments presented below are repeated times and the averaged results are presented. We set the DP parameters (c, as
e 6 min(10-6 2). Experiments for 0.1 can be found in Fig, in the App. Baseline Algorithms. We compare our estimator with the following baseline algorithms:
Non private algorithms: ordinary least squares (OLS), one-pass stochastic gradient descent with tail-avergging (SGD). For SGD, step-size is 1/(2Amax) and minibatch size is n/T' where T' 3x log n.
8

---

Private algorithms: sufficient statistics perturbation (DP-SSP) 38 831, differentially private stochastic gradient descent (DP-AMB)GGD) 81. DP-SSP had the best empirical performance among numerous techniques studied by [3]] and DP-A MBBSGDD has the best known theoretical guarantees. The DP-SSP algorithm involves releasing X X and x differentially privately
and computing (X*X)= XXTy OP-AMBSSGD is private version of SGD where the DP noise is set adaptively according to the excess error in each iteration. For both algorithms,, we use the hyper-parameters recommended in their respective papers. To improve the performance of DP-AMBSSGD, we reduce the theoretical clipping threshold by a constant factor.
DP-ROBGD. We implement Alg. with the following key changes. Instead of relying on PrivateNorrmEstnaan to estimate I, 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 use 20% of the samples to compute "te in line (instead of the 50% stated in Alg. D). In our experiments also present results for a variant of our algorithm called DP-ROBGD* which outputs the best iterate based on %t. 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 Alg. | and achieved similar performance in our experiments.
Results. Figure I presents the performance of various algorithms as we vary n, Ki a. It can be seen that DP-ROBGD outperforms DP-AMBSSGD in almost all the settings (and DP-ROBGD* outperforms DP-ROBGD in all cases). DP-SSP has poor performance when the noise is low, but performs slightly better than DP-Rot RROGD in other settings. A major drawback of DP-SSP is its computational complexity which scales as Ond + d In contrast, the computational complexity of DP- ROBGD has smaller dependence on d and scales as Ö(dxx). Thus the latter is more compu- tationally efficient for high-dimensional problems. More experimental results on both robust and private linear regression can be found in the App. K
Sketch of the main ideas in the analysis
We provide the main ideas behind the proof of Thm. 3.1 The privacy proof is straightforward since no matter what clipping threshold we use the noise we add is always proportionally to the clipping threshold which guarantees privacy. In the remainder, we focus on the utility analysis.
The proof of the utility heavily relies on the resilience
(also known as stability (27), which states that given a large enough sample set S. various statistics (for example, sample mean and sample variance) of any large enough subset of S will be close to each other. We define resilience as follows.
7
Definition 5.1 (61 Definition 23]). For some a (0,1), P1 E R4, P2 R4, and ps E R4,, Ps E R4,, we say dataset S Sgood {(x Rd, ve [ is (a,P1, P1, Ps: Presientl with respect to (w", o) for some w" E Rdd positive definite Σ 0 e Rdxd and >> 0 if for any T C Sgood of size [T] 2 (1 a)m, the following holds for all v E Rdd:
Σ (ETT
(v, (vi - xI wn) si Eeo
(5)
(u,21)² - -Eu S IE. Ev.
(6)
T
(Vi- xI7 w=/ 18--00" 0² S 2302
(TT
Σ ETT
(v,
S SpiVo Ev.
We give an overview of the proof for non-robust case as follows. First, we introduce some notations. Let Letg." (t) = (x. w, - yr);;; be the raw gradient and ((1) == clips (1; )elipe (x. wy ys) be the clipped gradient. Note that when the data follows from our distributional assumption, with high probability,
samples are not clipped by the norm: cIi Zi. We can write down one step of gradient update

---

(see Alg. D as follows:
Wi+1 wº
I - -
(wi =²)
Σ SE8
2/2
+
Σ
(0)
9. )-
norty
iES
(zv)
(K)
(ai)
(863
In the above equation, the first term is a contraction, meaning w; is moving toward w.. The second term captures the noise from the randomness in the samples. The third term captures the bias introduced by the clipping operation, and the fourth term captures the added noise for privacy. The second term is standard and relatively easy to control, and our main focus is on the last two terms.
The third term (n/n) Eees(g;) 9i can be controlled using the resilience property. We prove that with our estimated threshold, the clipping will only affect a small amount of datapoints, whose contribution to the gradient is small collectively.
Now we have controlled the deterministic bias. Then, we upper bound the fourth term, which is the noise for the purpose of privacy, and show the expected prediction error decrease every gradient step. The difficulty is that, since our clipping threshold is adaptive, the decrease of the estimation error depends on the estimation error of all the previous steps. This causes that in some iterations, the estimation error actually increases. In order get around this, split the iterations into length chunks, and argue that maximum estimation error in a chunk must be a constant factor smaller than the previous chunk. This implies we will reach the desired error within (1x) steps.
Conclusion
We provide novel variant of DP-SGD algorithm for differentially private linear regression under label corruption. We show the first near-optimal rate that achieves privacy and robustness to label corruptions simultaneously. When there is no label corruption,
result also improves upon the state-of-the-ar method [81] in terms of the condition number к. Compared to [81], our algorithm has two innovations: 1) we introduce novel adaptive clipping, which is critical in achieving robustness against label corruptions; and 2) we use full batch gradient descent and a novel convergence analysis get the near-optimal sample complexity.
Acknowledgement
We thank Abhradeep Guha Thakurta for helpful discussions while working on this paper. This material based upon work supported by the National Science Foundation under grants no. 2134012, 2019844, 2112471, and 2229876, and is supported in part by funds provided by the National Science Foundation, by the Department of Homeland Security, and by IBM. Any opinions, findings, and conclusions recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or its federal agency and industry partners.
10

---

References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] John M Abowd. The US Census Bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2867-2867, 2018.
[3] Anish Agarwal, Devavrat Shah, Dennis Shen, and Dogyoon Song. On robustness of principal component regression. Advances in Neural Information Processing Systems, 32, 2019.
[4] Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang. Privately estimating gaussian: Efficient, robust and optimal. arXiv preprint arXiv:2212.0800 2022.
[5] Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression. arXiv preprint arXiv:2007.05115, 2020.
[6] Kareem Amin, Matthew Joseph, Mónica Ribero, and Sergei Vassilvitskii. Easy differentially private linear regression. arXiv preprint arXiv:2208. 07355,, 2022.
[7] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34, 2021.
[8] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory, pages 1075-1076. PMLR, 2022.
[9] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in 11 geometry. In International Conference on Machine Learning, pages 393-403. PMLR, 2021.
[10] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. arXiv preprint arXiv:2302.01855, 2023.
[11] Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 102-115, 2021.
[12] 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.
[13] Racf Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Elfi- cient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464 473. IEEE, 2014.
[14] Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar. Consistent robust regression. Advances in Neural Information Processing Systems, 30, 2017.
[15] Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding. Advances in neural information processing systems, 28, 2015.
[16] T Tony Cai, Yichen Wang, and Linjun Zhang. Score attack: A lower bound technique for optimal differentially private learning. arXiv preprint arXiv:2303.07155 152, 2023.
[17] Kamalika Chaudhuri. Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
[18] Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithmss, pages 2755-2771. SIAM, 2019.

---

[19] Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni, Michael Jordan, Nicolas Flammar- ion, and Peter L Bartlett. Optimal robust linear regression nearly linear time, arXiv preprint Ntt::2007.0813: 2020.
[20] Christopher A. Choquette-Choo, Krishnamurthy Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Correlated noise provably beats independent noise for differentially private learning, 2023.
[21] Arnak Dalalyan and Philip Thompson. Outlier-robust estimation of sparse linear model using & -penalized huber's m-estimator. Advances neural information processing systems, 32, 2019.
[22] Jules Depersin. spectral algorithm for robust regression with subgaussian rates, arXiv preprint arXiv:200..00072, 2020.
[23] Ilias Diakonikolas, Samuel Hopkins, Daniel Kane, and Sushrut Karmalkar. Robustly learning any clusterable mixture of gaussians. arXiv preprint arXiv:2005.00 2022000050677,,. 17, 2020.
[24] 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):742-864, 2019.
[25] 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 Learning, pages 1596-1606, 2019.
[26] 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 Machine Learning, pages 999-1008. PMLR, 2017.
[27] Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.0591 2019.
[28] 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, pages 1047-1060, 2018.
[29] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithms, pages 2745-222 2754.. SIAM, 2019.
[30] Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, and Benjamin IP Rubinstein. Robust and private bayesian inference. In International Conference on Algorithmic Learning Theory, pages 291-305 Springer, 2014.
[31] Yihe Dong, Samuel Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. Advances in Neural Information Processing Systems, 32, 2019.
[32] Cynthia Dwork and Jing Lei. Differential privacy and robust statisties. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380, 2009.
[33] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-2864 Springer, 2006.
[34] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3-4):211 407, 2014.
[35] Ú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, pages 1054-1067, 2014.
12

---

[36] 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-6) 2016.
[37] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, pages
2020.
[38] James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of
bayesian data analysis. arXiv preprint mxXiv:1603002990 2016.
[39] Arun Ganesh, Mahdi Haghifam, Thomas Steinke, and Abhradeep Thakurta. Faster differentially private convex optimization via second-order methods. arXiv preprint S.Ki::2305.130000 2023,
[40] Arun Ganesh, Daogao Liu, Sewoong Oh, and Abhradeep Thakurta. Private (stochastic) non- convex optimization revisited: Second-order stationary points and excess risks. arXiv preprint arXiv:2302. 09699, 2023.
[41] Quan Geng, Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The staircase mechanism in differential privacy. IEEE Journal of Selected Topics in Signal Processing, 17781177-1118, 2015.
[42] Antonious M Girgis, Deepesh Data, Suhas Diggavi, Ananda Theertha Suresh, and Peter Kairouz. On the renyi differential privacy of the shuffle model. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pages 2321-2341, 2021.
[43] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34: 1631-11642, 2021.
[44] Samuel B Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via sum-of-squares exponential mechanism. In Proceedings of the 54th Anmual ACM SIGACT Symposium Theory of Computing, pages 1406- 1417, 2022.
[45] Samuel Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies privacy in statistical estimation. arXiv preprint arXiv:2212.050115 2022.
[46] Peter Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pages 192-518. Springer, 1992.
[47] Arun Jambulapati, Jerry Li, and Kevin Tian, Robust sub-gaussian principal component analysis and width-independer schatten packing. Advances in Neural Information Processing Systems, 33, 2020.
[48] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27, 2014.
[49] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385 PMLR, 2015.
[50] Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. arXiv preprint urXiv:2106.0133: 2021.
[51] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv: 171 100900 2017.
[52] Ashish Khetan, Zachary Lipton, and Animashree Anandkumar. Learning from noisy singly- labeled data. In International Conference on Learning Representations, 2018.
[53] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings. 2012.
[54] Adam Klivans, Pravesh Kothari, and Raghu Meka. Efficient algorithms for outlier-robust. regression. In Conference On Learning Theory, pages 1420-1430. PMLR, 2018.
13

---

[55] 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.
[56] Pravesh K Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. arXiv preprint arXiv:21 /at:::///2.0358,, 2021.
[57] Arun Kumar Kuchibhotla and Abhishek Chakrabortty. Moving beyond sub-gaus sabb-aussiaaity in high-dimensional statistics: Applications in covariance estimation and linear regression. arXiv preprint arXiv: 2018.
[58] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimiza- tion and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103, 15352, 2021.
[59] Xiyang Liu, Weihao Kong, Prateek Jain, and Sewoong Oh. DP-PCA: Statistically optimal and differentially private pca. In Advances in Neural Information Processing Systems, 2022.
[60] Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. Advances in Neural Information Processing Systems, 34, 2021.
[61] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory, pages 1167-1246. PMLR, 2022.
[62] Frank D McSherry. Privacy integrated queries: an extensible platform for data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Manage- ment of data, pages 19-30, 2009.
[63] Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis loannidis. Differentially private regression with unbounded covariates. In International Conference on Artificial Intelligence and Statistics, pages 3242-3273. PMLR, 2022.
[64] Kentaro Minami, HItomi Arai, Issei Sato, and Hiroshi Nakagawa. Differential privacy without sensitivity. In Advances in Neural Information Processing Systems, pages 956-964, 2016.
[65] Darakhshan J Mir. Differential privacy: an exploration of the privacy-utility landscape. Rutgers The State University of New Jersey-New Brunswick, 2013.
[66] Ilya Mironov, Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE, 2017.
[67] Ankit Pensia, Varun Jog, and Po-Ling Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv preprint arXiv:2009. /2976, 2020.
[68] Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06444 06485, 2018.
[69] Holger Sambale. Some notes on concentration for a-subexponential random variables. arXiv preprint 2 2020.
[70] Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory, pages 789-827. PMLR, 2019.
[71] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing, pages 245-248. IEEE, 2013.
[72] Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private clipped gradient descent convex generalized linear problems. arXiv preprint arXiv:2006.06677 2020.
[73] Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: criterion for learning in the presence of arbitrary outliers. arXiv preprint 1rXiv:170.004940 2017.
14

---

[74] Thomas Steinke and Alexander Knop. Differentially Private Linear Regression via Medi- ans. 2023].
2022. [Online; accessed 28-April-
[75] Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, and Prateek Jain. Adaptive hard threshold- ing for near-optimal consistent robust regression. In Conference on Learning Theory, pages 2892 2897. PMLR, 2019.
[76] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Pri- vacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02733 2017.
[77] Henri Theil. A rank-invariant method of linear and polynomial regression analysis. Indagationes mathematicae, 12(85):173, 1950.
[78] Kiran K Thekumparampil, Ashish Khetan, Zinan Lin, and Sewoong Oh. Robustness of conditional gans noisy labels. Advances in neural information processing systems, 31, 2018.
[79] John W Tukey. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vancouver, 1975, volume 2. pages 523-531, 1975.
[80] John W Tukey and Donald H McLaughlin. Less vulnerable confidence and significance procedures for location based on a single sample: Trimning/winsorizaiin 1. Sankhyā: The Indian Journal of Statistics, Series A, pages 331-352, 1963.
[81] Prateek Varshney, Abhradeep Thakurta, and Prateek Jain, (nearly) optimal private linear regression via adaptive clipping. arXiv preprint arXiv:2207.04686. 2022.
[82] Duy Vu and Aleksandra Slavkovic. Differential privacy for clinical trial data: Preliminary evaluations. In 2009 IEEE International Conference on Data Mining Workshops, pages 138-143. IEEE, 2009.
[83] Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction estimation in unbounded domain. arXiv preprint 10XXvv8883300590 2018.
[84] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR, 2019.
[85] Yu-Xian Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pages 2493-2502 PMLR, 2015.
[86] Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt- on differential privacy for scalable stochastic gradient descent- bessenttbbsed analytics. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1307-1322, 2017. 2017.
[87] Liang Zhang, Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He. Bring your algorithm for optimal differentially private stochastic minimax optimization. arXiv preprint DXXiv2206.00366 2022.
[88] Liang Zhang, Kiran Koshy Thekumparampil. Sewoong Oh, and Niao He. DPZero: dimenniooninndependent and differentially private zeroth-order optimization. arXiv preprint arXiv:2310.09639 2023.
[89] Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. Generalized resilience and robust statistics. arXiv preprint arXiv: (tt::::99000..3 2019.
[90] Yuqing Zhu, Jinshuo Dong, and Yu-Xin fu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pages 1782-48177 PMLR, 2022.
15


Reviews:
[{"review_id": "amaI7rU3vs", "reviewer": "Reviewer_1PSa", "summary": "This paper presents a variant of the Differentially Private Stochastic Gradient Descent (DP-SGD) algorithm aimed at achieving efficient linear regression under differential privacy, even in scenarios where a portion of response variables is adversarially corrupted. The introduced methodology involves a full-batch gradient descent to optimize sample complexity and an adaptive clipping mechanism for robustness. The algorithm, exhibiting linear time complexity with respect to input size, also matches the theoretically optimal sample complexity, considering a distribution-dependent condition number factor.", "questions": "The authors assert that their methodology represents \"the first efficient approach to achieve robustness and (ε, δ)-Differential Privacy (DP) simultaneously\". However, previous research, as indicated in references [1] and [2], appears to have discussed the interplay between DP and robustness. Could the authors clarify the novel aspects of their approach in the context of these prior works, if any?\n\nThe manuscript refers to a variant of Stochastic Gradient Descent (SGD) being utilized in the process. Is this variation generalizable, or is it specifically tailored for the application to Linear Regression models?\n\n\n[1] Phan, H., Thai, M. T., Hu, H., Jin, R., Sun, T., & Dou, D. (2020, November). Scalable differential privacy with certified robustness in adversarial learning. In International Conference on Machine Learning (pp. 7683-7694). PMLR.\n[2] Lecuyer, M., Atlidakis, V., Geambasu, R., Hsu, D., & Jana, S. (2019, May). Certified robustness to adversarial examples with differential privacy. In 2019 IEEE symposium on security and privacy (SP) (pp. 656-672). IEEE.", "limitations": "Experimental results are overly simplistic.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents a focused yet intriguing investigation into the Label Robust and Differentially Private Linear Regression problem.\n\nThe proposed algorithm demonstrates improved sample complexity relative to existing polynomial-time algorithms.", "weaknesses": "The presentation of experimental results appears overly simplistic, resulting in some difficulties in interpretation. The study would greatly benefit from a more comprehensive representation of data, rather than relying solely on a single figure (Figure 1). Additionally, only one value of $\\kappa$ is used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and address each comment as follows.\n\n1. Experiments: A primary motivation for this project is to understand theoretically the fundamental tradeoffs involved in privacy, accuracy, and robustness in solving linear regression. Our algorithmic contributions can have implications for practical deep learning scenarios as we discuss below, but extensive experimental study would be outside the scope of this theoretical paper. We appreciate the reviewer’s constructive feedback but would like to respectively claim in the following that we attempted to include many experiments illustrating the effectiveness of our proposed algorithm. Specifically, in the main text, we have provided three plots in Figure 1, showcasing our algorithm's performance under non-robust settings with various choices. The first two plots utilize $\\kappa=1$ mainly to showcase the dependence on other parameters, namely, the number of samples and the noise $\\sigma^2$. However, this choice of $\\kappa$ is not cherry-picked, as all competing algorithms suffer similarly with increasing $\\kappa$. To demonstrate this fact, we have included the third plot (the rightmost panel), which illustrates that the relative performance of the algorithms remains similar as we increase the condition number $\\kappa$ from 1 to 10^2. We consistently observe improvement over the best existing algorithm [78] across different choices of $\\kappa$. Furthermore, in Appendix J, we have included additional experiments with strong label corruptions. As a theoretical paper, we believe we have provided more than enough details and interpretations for experiments, especially considering that prior works on DP linear regression, such as [10, 58, 78], lack any experimental evaluation.\n\n2. Comparisons to certified robustness: In certified robustness to adversarial examples, the adversary perturbs a sample to confuse the classifier at inference time. It is a fundamentally different concept from the robustness to adversarial corruption at train time we discussed in our manuscript. Specifically, in certified robustness, the adversary is only allowed to perturb a sample up to some **norm constraints** and also **at inference time**. In contrast, our corruption model (Assumption 3.7) allows the adversary to inspect the training dataset and pick $\\alpha$-fraction of **training data points** to perturb them **arbitrarily**. This constitutes a much stronger threat model. Applying methods from certified robustness to the corruption model we considered here will result in failure. Hence, we do not consider them as prior work.\\\nWe have provided a thorough related work study in Appendix A. Note that as of today, the only provably robust and DP linear regression papers are [10, 58], but they require exponential time. We are the first efficient algorithm to achieve label robustness and DP simultaneously.\n\n3. Generalization to other models: Our method is specifically designed for DP and label-robust linear regression for sub-Gaussian data, and our main contribution lies in providing theoretical guarantees. However, with some light modifications, the proposed technique can potentially be applied to general deep models. Let us explain how one could make advances toward such an ambitious goal, as the reviewer suggested. Our algorithm involves adaptive clippings separately for the residual and features, which can also be applied to general models. For example, let us focus on deep neural networks trained on quadratic loss to keep notations simpler. The empirical risk we minimize is given by $\\sum_{i=1}^n \\frac{1}{2} (f_w(x_i)-y_i)^2$. Taking the gradient with respect to the neural network weights $w$, we obtain the gradient $G=\\sum_{i=1}^n (f_w(x_i)-y_i) \\nabla f_w(x_i)$. This gradient can be broken down into two terms: the residual $(f_w(x_i)-y_i)$ and the \"feature\" $\\nabla f_w(x_i)$. Applying the intuition from linear regression, we propose clipping the residual and the feature separately to improve robustness against label corruption. \\\nWe strongly believe that separately clipping the residual and feature (as opposed to clipping the gradient as a whole) will enhance robustness against label corruption for deep neural networks. Empirical evidence supporting this conjecture can be found in the case of CLIP models, multimodal foundation models achieving SOTA performances in vision tasks trained on image-text pairs [R1]. As the data is scraped from the web, a significant portion of the text can be considered garbage (analogous to corrupted labels). To combat this label corruption, one standard method is filtering: (1) train a CLIP model on the corrupted data; (2) filter all the training data using the \"Residual\" on this trained CLIP model and discard large residuals; (3) retrain a CLIP model on the filtered dataset. This approach, first proposed by the LAION dataset, filtered using this technique [R2], improves the model's accuracy on the ImageNet benchmark by a remarkable 12% on the zero-shot classification that CLIP models are trained to do. Given the empirical success of this filter-once approach, we believe that filtering based on the residual for training deep neural networks is a very promising direction, especially when the data is noisy or adversarially corrupted. Our method applies similar filtering techniques within the training iterations, aiming to achieve similar gains by clipping the contribution of noisy data. This represents an exciting direction for training foundation models from noisy web-scale data with limited quality control.\n\n[R1] “Learning Transferable Visual Models From Natural Language Supervision”, Alec Radford et al. Proceedings of the 38th International Conference on Machine Learning, PMLR 139:8748-8763, 2021.\n\n[R2] “LAION-5B: An open large-scale dataset for training next generation image-text models”, Christoph Schuhmann et al.  NeurIPS 2022 Track Datasets and Benchmarks\n \n"}, {"review_id": "sUdhNJxwdw", "reviewer": "Reviewer_xavj", "summary": "This paper focuses on differentially private linear regression with potential label corruption. The proposed algorithm is based on DP-SGD and introduces new components such as full batch-size GD and adaptive norm clipping. The paper achieves the best sample complexity under the assumption of sub-Gaussian data distribution in the absence of corruption, with a polynomial running time. Additionally, it presents the first algorithm for DP linear regression in the presence of label corruption, supported by experimental validation.", "questions": "- Line 181: Should it be \"$\\Theta(\\theta_t)$\" instead?\n- In Algorithm 1, why are the three subsets equally divided? Is it possible to improve performance by adjusting their sizes?", "limitations": "Yes, limitations are discussed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-structured and easy to follow. Privacy and robustness are crucial in current machine learning research, making the studied topic highly relevant. The analysis of adaptive norm clipping introduces a novel technique that could have implications for future research. The results obtained in the paper are promising, and the proposed algorithm makes a substantial contribution to the field.", "weaknesses": "The paper's focus on a specific distribution requirement for the samples and only considering corruption in the labels limits its generalizability. It would be beneficial to explore more general cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and address each comment as follows.\n1. Distributional requirement: We thank the reviewer for pointing this out, since this was an important contribution of this paper that was not clearly written in the paper. We focused on the subGaussian case in the main text to make it easy to follow. However, our results include general distributional assumptions: the sub-Gaussian in Assumption 2.1, the sub-Weibull in Assumption I.1 and heavy-tailed in Assumption M.2. **These are not restrictive, but rather can capture a wide range of distributions we might encounter in practice. For any given distribution family, we can apply the appropriate distributional assumption from the above and apply our techniques.  This captures the correct dependence of the error rate on the tail behavior of the distribution.** For example, the most relaxed assumption is the 4-th moment bounded distribution, which any distribution for linear regression needs to satisfy and hence includes almost all distributions of interest. The cost of being inclusive in this case is the worse sample dependence of the resulting error. \n&nbsp;\\\n&nbsp;\\\nFirstly, between the sub-Weibull and Heavy-tailed, we cover (how our algorithm depends on) most of the known distributions. sub-Weibull is a general assumption that covers a wide range of light-tailed distributions, e.g., sub-Gaussian distribution (a=0.5), sub-exponential distribution (a=1), Gaussian distribution (K=4, a=0.5). Here, a smaller $a$ means a lighter tail and our error and sample complexity characterizes the dependence on the tail. Similarly, for heavy tailed distributions, we cover $k$-th moment bounded distributions and here larger $k$ implies lighter tail. Our error rate and sample complexity captures the dependence on this tail behavior. \n&nbsp;\\\n&nbsp;\\\nSecondly, these assumptions are not specific to our algorithm, as we show with counter examples that have significantly larger errors in Section 3.4 “Necessity of our assumptions” (Line 273-278.). When there is no such tail assumption, it is not possible to achieve the optimal rate with $O(d)$ samples. Fundamentally, error in private linear regression depends on the tail of the distribution regardless of the algorithm used. To capture this fundamental dependence as tightly as we can, we are making our distributional assumptions. \n&nbsp;\\\n&nbsp;\\\nWe believe that these are not restrictive as we cover most distributions, including real world distributions (as we are only characterizing the tail and we cover almost the entire range of lightness/heaviness of the tail). We will add this discussion to the main text.\n&nbsp;\\\n&nbsp;\n2. Label corruptions: Our focus on label corruption in DP linear regression represents a crucial problem at the intersection of robustness and privacy. This setting stands out as the only one where we can achieve a sample complexity of $\\tilde{O}(d)$ with computationally efficient algorithms under sub-Gaussian data. In contrast, existing algorithms dealing with adversarial corruption of both covariates and labels ([10] and [58]), are limited to exponential time complexity. Our paper identifies a non-trivial setting where near-optimality is attainable with a computationally efficient algorithm. We firmly believe that offering a near-optimal algorithm for such a case constitutes a significant contribution to the literature, especially at the intersection of robustness and privacy. It remains an open problem if a computationally efficient algorithm exists that can achieve both privacy and robustness for more general and powerful adversaries. We believe this is outside the scope of our paper and an exciting research direction.\n&nbsp;\\\n&nbsp;\n\n3. Equal sized subsets: We thank the reviewer for point this out. In Algorithm 1, for notational convenience we let $|S_1|=|S_2|=|S_3|$ and merge all sufficient conditions on $S_1$, $S_2$, and $S_3$ together. We assume that the dataset of size $3n$ is partitioned into three equal-sized sets $S_1,S_2,S_3$, each of size $n$. This choice makes the notations much simpler for presentation, while not changing the final guarantee as we do not keep track of the constant factors in sample complexity. It is true that the sufficient conditions on the sizes of $S_1, S_2$, and $S_3$ are different, and one could potentially gain in the constant factor in sample complexity from better partitioning of the dataset. In particular, it is sufficient to have $|S_1|=\\tilde O(\\log(1/\\delta)/\\varepsilon)$, $|S_2|=\\tilde O(d/\\varepsilon)$ and $|S_3|=\\tilde O(d/\\alpha^2+\\kappa^{1/2}d\\log(1/\\delta)/(\\varepsilon \\alpha))$, with large enough constants. We will add this note to the revised version.\n&nbsp;\\\n&nbsp;\n\n4. Typos: We thank the reviewer for pointing out the typo. We will fix all the typos in the revision. \n"}, {"review_id": "h7hRk1w8iQ", "reviewer": "Reviewer_kzNP", "summary": "This paper introduces the first computationally and statistically efficient algorithm for differentially private and label-corruption robust linear regression. In particular, they improve over the best sample complexity achieved by non-robust algorithms in terms of the condition number of the covariance matrix. This is achieved through a variant of DP-SGD with a new adaptive clipping technique. The authors also show the empirical improvement of their proposed method over existing techniques on a synthetic dataset.", "questions": "Refer to Weaknesses section for questions.\n", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Technically solid paper on an important topic. Some of the analysis methods are original and interesting.\n* The paper is well written and the contributions are clear.", "weaknesses": "### Weaknesses:\n\n* It is clear that there is an improvement in terms of sample complexity, but my main concern is the significance of the improvement, especially that a polynomial dependence on the condition number remains, which may be extremely large. Do you think it is possible to suppress the dependence on the condition number, and how?\n\n* Is there any novelty in the proof of the lower bound in Proposition 3.9 compared to [11]?\n\n* Can you show the exact runtimes of your algorithm compared to that of [78]?\n\n* While I understand that the paper is mainly theoretical, I fail to think of any practical scenarios where an adversary can only corrupt labels.\n\n\n\n### Minor comments:\n\n* Typos: line 178: proportional -> proportionally, line 363: increase -> increases\n* Equation 3: $\\nu_t$ -> $\\nu_T$\n* Definition 2.2: (suggestion) random variables are typically denoted with capital letters\n* Lemma B.2: $\\infty$ -> {$\\infty$}", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and address each comment as follows.\n1. Polynomial dependence on $\\kappa$: We kindly direct reviewer to our general response for further details.  \n&nbsp;\\\n&nbsp;\n2. Proposition 3.9: Compared to [11], our proof is a simpler version that only covers Gaussian data. We agree with the reviewer that the technique is not particularly novel and we add the proof only for completeness.\n&nbsp;\\\n&nbsp;\n3. Exact runtime compared to [78]:  We want to emphasize that we did not try to optimize the implementation for computational efficiency and the numbers we are reporting could potentially be significantly improved. For $n=10^7$, our algorithm takes 280 seconds for each trial, and [78] takes 13 seconds for each trial. Since [78] does not provide any experiments, we implement both algorithms. \n&nbsp;\\\n&nbsp;\\\nIn total, we process $Tn = 3\\kappa \\log(n)n$ samples (full-batch gradient descent for $T$ iterations) and [78] processes $n$ samples (since it is a streaming algorithm). That is why our algorithm is $3\\kappa\\log(n)\\approx 20$ times slower. Currently, we only use a single CPU for our experiments. This gap can potentially be made significantly smaller if we parallelize the computation by using multiple GPUs. Since all of these gradients computation and distance estimation can be fully parallelized.\n&nbsp;\\\n&nbsp;\n\n4. Practical scenarios for label corruption: We thank the reviewer for pushing us to think more carefully about the motivation and will add the following discussion in the revision.\n&nbsp;\\\n&nbsp;\\\nFirst concrete scenario where only the label can be corrupted by adversaries is crowdsourced annotation. An important procedure in the standard machine learning pipeline is annotating the data using crowdsourcing platforms. For example, ImageNet, one of the most popular computer vision datasets, contains more than 14 million images hand-annotated on Amazon’s Mechanical Turk. In this case, the images are clean since the data curator had full control over the quality. However, a subset of the workers can collude to corrupt the labels of a fraction of the training data. The fraction $\\alpha$ of the labels being corrupted corresponds to how much resource the adversary has to “bribe” many workers. We believe this scenario is practical, realistic, and consistent with our assumptions.\n&nbsp;\\\n&nbsp;\\\nAnother concrete scenario which is slightly less relevant is knowledge distillation. In knowledge distillation, a trainer is given a teacher model (possibly trained by an adversary) and wants to train a student model. The trainer has clean images that are quality-controlled, but the labels are coming from the teacher model that is potentially corrupted. Although this scenario is practical, realistic, and consistent without assumptions, it is not clear in this case what $\\alpha$ means since the teacher model can corrupt an arbitrary number of labels without additional cost. Perhaps the adversary has  another goal, such as not being detected by the student trainer, that limits how much the labels can be corrupted.\n&nbsp;\\\n&nbsp;\n\n\n\n5. Typos: We thank the reviewer for pointing out the typos. We will fix all the typos in the revision. \n"}, {"review_id": "DOvLLnvR3A", "reviewer": "Reviewer_yhsn", "summary": "This work studies the problem of $(\\varepsilon, \\delta)$-differently private linear regression. The covariates are drawn from a Gaussian distribution $N(0,\\Sigma)$ with unknown covariance $\\Sigma$ and the random noise in the model is either Gaussian or heavier-tailed. Further, a small fraction of the labels can be corrupted. The error is measured as $\\lVert \\Sigma^{1/2} (\\hat{w} - w^*) \\rVert_2$ (when the variance of the random noise equals 1), where $w^*$ is the true regression vector.\n\nLet $\\kappa$ be the condition number of $\\Sigma$. For the case that the noise is Gaussian the authors propose an algorithm that achieves error $\\alpha$ in polynomial time using $\\tilde{O}(\\tfrac d {\\alpha^2} + \\sqrt{\\kappa} \\cdot \\tfrac d {\\varepsilon \\alpha})$ samples. Previous efficient algorithms for this task needed $\\tilde{O}(\\tfrac d {\\alpha^2} + \\kappa \\cdot \\tfrac d {\\varepsilon \\alpha} + \\kappa^2 \\tfrac d \\varepsilon)$. On the other hand, it is known that  $\\Omega(\\tfrac d {\\alpha^2} + \\tfrac d {\\varepsilon \\alpha})$ samples are necessary information-theoretically. This can be achieved by inefficient algorithms, i.e., there is no dependence on the condition number.\n\nTheir results for heavy-tailed noise are similar to the results for Gaussian noise. Previously there were no known results in this setting. Their algorithm is based on differentially private stochastic gradient descent (DP-SGD).", "questions": "Since both you and previous work analyze DP-SGD and incur (some) dependence on the condition number, is there any reason to believe that this approach might inherently have at least some dependence on this?", "limitations": "The authors mention open questions that are note answered by their work in multiple places.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Previous works have also used DP-SGD for this problem. The authors give a more careful analysis (and tweak it in some places) which yields an algorithm with an improved sample complexity. One of their tweaks allows them to also handle corruptions in the labels. It is nice to see that this algorithmic approach can be made robust to corruptions in the labels.\n\nOverall, the paper is well-written.", "weaknesses": "Qualitatively, there is still a dependence on the condition number. So this work does not give new insights into whether this is necessary or not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and address each comment as follows.\n\n1. Polynomial dependence on $\\kappa$: We kindly direct reviewer to our general response for further details.\n&nbsp;\\\n&nbsp;\n\n2. The GD-type of methods has inherent $\\kappa$ dependence: Our work and the prior work [78] are the only two methods that achieve $\\tilde{O}(d)$ samples for DP linear regression, even without considering robustness. The $\\kappa^{0.5}$ dependence in our work arises from the compositions of $\\tilde{O}(\\kappa)$ iterations. Given that both algorithms are iterative in nature, it leads us to conjecture that as long as the number of iterations has a dependence on $\\kappa$, complete removal of the dependence may not be feasible. One possible approach to reduce the number of iterations is applying Newton's method, which could potentially bring it down to $\\tilde{O}(1)$. However, it remains unclear how to privatize the OLS solution without increasing the sample complexity to $\\tilde{O}(d^{1.5})$ as we need to compute $\\Sigma^{-1}$ privately. As a result, while we continue to explore avenues for improvement, we believe our current work represents a significant advancement in our understanding of iterative algorithms for private linear regression. We believe that the technical advances we make in this paper, using resilience to handle the dependence in the iterates, could potentially be an important tool in understanding other private iterative algorithms, even though the (small) dependence on $\\kappa$ still remains and is open if this is necessary.\n"}]

Author rebuttal:
We address common concerns regarding the significance of our $\kappa$ improvement. For linear regression without adversarial corruption or privacy, the dependence on $\kappa$ can be removed by simply applying an OLS solution. For linear regression with robustness and privacy simultaneously, there are exponential-time approaches that achieve optimal sample complexity without $\kappa$ dependencies [10, 58]. However, this becomes significantly more challenging for efficient algorithms even when either one of robustness or privacy is required. We are making progress in reducing the dependence on $\kappa$ for a problem that achieves both label-robustness and privacy, which we believe is significant progress in this intersection. We provide some evidence below. 

As an example of how dependence on $\kappa$ can become significantly more challenging, let us consider a stronger adversarial corruption setting where the input can also be corrupted. In this case, the best known efficient result for linear regression is in [R1], which achieves sample complexity of $n=O(\kappa^2d/\alpha)$ or $n=O((d^2+\kappa d)/\alpha)$. Getting this took several important innovations over many works. It remains an open question if this $\kappa$ dependence can be removed or not. We believe our work falls under a similar effort for private and label-robust linear regression. 

As another example of how dependence on $\kappa$ can become significantly more challenging, let us consider a simpler problem of private mean estimation. Over the past few years, there has been substantial effort in estimating Gaussian mean [R2, R3]. However, these methods are either exponential-time or sub-optimal in $d$ and $\kappa$. A recent breakthrough by [R4, R5] achieved efficiency and full optimality for Gaussian mean estimation with general covariance. It's worth noting that this breakthrough was a consequence of numerous papers on mean estimation, each incrementally improving the dependence on the condition number (among other things). Every one of these papers has contributed significantly to jointly enhancing our understanding of the problem and devising new techniques (both algorithmic and analytical), ultimately culminating in [R4, R5]. For linear regression, achieving complete removal of $\kappa$ dependence with an efficient algorithm remains an ongoing pursuit. While we strongly believe such progress will happen in the near future, allowing us to entirely omit the dependence on $\kappa$ with an efficient algorithm, to the best of our knowledge, no such solution currently exists. One might think that we can simply use (i) covariance-aware mean estimation from [R4,R5] to aggregate the gradients in linear regression, or (ii) apply stable covariance to least-squares and add noise. Neither of them strictly improves upon our result. The first one still suffers from number of iterations scaling as $\kappa$, where the composition of privacy costs us a factor of $\kappa^{0.5}$, which cannot be recovered; even together with all the advances we make in our paper, this costs at least $\kappa^{0.5}$ in the second error term. Without the advances in our paper, this will cost $\kappa$ factor in the second error term like [78]. The second approach of least squares does not achieve zero error even when the noise in the data (i.e. $\sigma^2$) is zero, which is strictly worse than our approach (among other issues that we will not go into details here). Nonetheless, we recognize that progress in research unfolds over time, and our submission provides several valuable tools (both algorithmic and analytical) that will play critical roles in advancing toward this goal.



[R1] “Robust regression revisited: Acceleration and improved estimation rates” Arun Jambulapati, Jerry Li, Tselil Schramm, Kevin Tian, NeurIPS 2021

[R2] “A Private and Computationally-Efficient Estimator for Unbounded Gaussians”, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, Jonathan Ullman Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:544-572, 2022.

[R3] “Covariance-Aware Private Mean Estimation Without Private Covariance Estimation”, Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, Lydia Zakynthinou, NeurIPS 2021

[R4] “Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions”, Gavin Brown, Samuel B. Hopkins, Adam Smith, COLT 2023

[R5] “A Fast Algorithm for Adaptive Private Mean Estimation”, John Duchi, Saminul Haque, Rohith Kuditipudi, COLT 2023


Meta-review: This paper studies the problem of differentially private linear regression with label robustness. The proposed algorithm seems to be novel and the theoretical results are strong.

The reviewers are positive and agree that the current paper has a solid contribution to the DP linear regression literature, especially to the setting with label corruptions. There are still concerns regarding the limited scope of the setting (only label corruptions) and experiments (too simple). I agree it is important to consider more general settings and conduct thorough empirical evaluations. But I do not think these are major concerns.

In light of this, I recommend acceptance and encourage the authors to incorporate the suggested discussions into the revision.
Decision: Accept (poster)