Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regression
Authors: Haodong Liang
Yanhao Jin
Krishna Balasubramanian
Lifeng Lai
Venue: ICLR 2026 Poster (2026)
Keywords: differential privacy
endogeneity
bi-level gradient descent
instrumental variables
Primary area: learning theory

Abstract: We study instrumental variable regression (IVaR) under differential privacy constraints. 
Classical IVaR methods (like two-stage least squares regression) rely on solving moment equations that directly use sensitive covariates and instruments, creating significant risks of privacy leakage and posing challenges in designing algorithms that are both statistically efficient and differentially private.
We propose a noisy two-stage gradient descent algorithm that ensures $\rho$-zero-concentrated
differential privacy by injecting carefully calibrated noise into the gradient updates. 
Our analysis establishes finite-sample convergence rates for the proposed method, showing that the algorithm achieves consistency while preserving privacy. 
In particular, we derive precise bounds quantifying the trade-off among optimization,
privacy, and sampling error. 
To the best of our knowledge, this is the first work to provide both privacy guarantees and provable convergence rates for instrumental variable regression in linear models. 
We further validate our theoretical findings with experiments on both synthetic and real datasets, demonstrating that our method offers practical accuracy-privacy trade-offs.

Published as a conference paper at ICLR 2026
DIFFERENTIALLY PRIVATE TWO-STAGE GRADIENT DESCENT FOR INSTRUMENTAL VARIABLE REGRES- SION
Haodong Liang, Yanhao Jin, Krishnakumar Balasubramanian, Lifeng Lai University of California, Davis
Davis, CA 95616, USA
(hdliang, yahjii kbala, 1flai 1 J@ucdavis.edu
ABSTRACT
We study instrumental variable regression (IVaR) under differential privacy con- straints. Classical IVaR methods (like two-stage least squares regression) rely on solving moment equations that directly use sensitive covariates and instruments, creating significant risks of privacy leakage and posing challenges in designing al- gorithms that are both statistically efficient and differentially private. We propose a noisy two-stage gradient descent algorithm that ensures p-zero-conee rzzero-concentrated dif- ferential privacy by injecting carefully calibrated noise into the gradient updates. Our analysis establishes finite-sample convergence rates for the proposed method, showing that the algorithm achieves consistency while preserving privacy. In par- ticular, we derive precise bounds quantifying the trade-off among optimization, privacy, and sampling error. To the best of our knowledge, this is the first work to provide both privacy guarantees and provable convergence rates for instrumen- tal variable regression in linear models. We further validate our theoretical find- ings with experiments on both synthetic and real datasets, demonstrating that our method offers practical accuracy-privacy trade-offs.
INTRODUCTION
Instrumental variable regression (IVaR) is a foundational tool causal inference, designed re- cover structural parameters when standard estimators fail due to endogeneity, In many observational settings, covariates are influenced by unobserved confounders, causing naive methods (such as the ordinary least squares (OLS) in the context of linear regression) to produce biased and inconsistent estimates. IVaR circumvents this by leveraging instruments. which are variables that are predictive of the endogenous regressors but independent of hidden confounders, to enable consistent estimation of causal effects (Hausman) 200T Wooldridge/ 2010 Angrist& & Krueger, 200T). This perspective is increasingly important in machine learning, for example in recommendation systems where user exposure is confounded by prior preferences (Si et al.) 2022), or reinforcement learning where actions and rewards are jointly influenced by unobserved context (Xu et al., 2023). In such settings, IVaR provides a principled way to disentangle causal effects from spurious correlations, enabling more reliable decision making.
However, many applications of IVaR involve sensitive data, such as individual health records, fi- nancial transactions, or user interactions, where protecting privacy is of paramount importance. In such settings, releasing model estimates or even intermediate statistics can leak information about individuals in the dataset. Differential privacy (DP) (Dwork al. 2006) provides a mathematically rigorous framework to ensure that an algorithm's 's output does not reveal sensitive information about any single data point. Despite the importance of IVaR in causal inference, to the best of our knowl- edge, there are no prior works addressing the problem of performing IVaR under differential privacy. This gap motivates the central question of this paper:
Can we design differentially private algorithms for instrumental variable models that achieve stafistically efficient convergence rates?

---

Published as a conference paper at ICLR 2026
Our work focuses answering this question in the context of linear IVaR models. To situate contributions, we briefly review existing work on DP methods for OLS regression, with additional discussion in Section L.1 Several predominant approaches have emerged in the literature: (i) pertur- bion methods, where the empirical covariance and cross-covariance matrices are privatized before solving the normal equations; (ii) consensus-based methods, including propose-test-releas and ex- ponential mechanism approaches, which directly privatize the estimator through carefully designed randomized output rules; and (iii) gradient perturbation methods, where iterative optimization al- gorithms are made private by clipping gradients and injecting calibrated Gaussian noise. W While all three approaches ensure differential privacy, gradient perturbation combined with clipping has been shown to yield the sharpest statistical rates in OLS regression, particularly in high-dimensional and finite-sample regimes (Bassily al. 2014 4, Brown et al., 2024a).
Given the centrality of IVaR in causal inference, it is natural to explore whether the aforementioned techniques can be adapted to this setting. Unlike OLS, however, IVak is based on moment con- ditions involving both covariates and instruments, making it less straightforward to design private algorithms. In particular, sufficient-statisties perturbation and consensus-baad based methods have not been explored, and their adaptation is non-trivial due to the inherent ill- polsddsssssss of IVaR under weak instruments and the sensitivity of the moment equations. These challenges stem from the fact that the closed-form 2SL. estimator depends nested matrix multiplications and inversions, whose sensitivities are difficult to characterize directly. To address this, we design a two-stage gradient-descent-baie algorithm that enables injecting noise at the iteration level in principled manner. This structure allows us to rigorously control sensitivity, calibrate the noise, and derive non-asymptotic utility guarantees. Specifically, we make the following contributions in this work:
We introduce DP-2S-2-- (Algorithm [ the first differentially private algorithm for instrumental variable regression, built noisy gradient descent with gradient clipping.
We establish finite-sample non-asymptotic error bound for DP-2S -2S-GD GD (Theorem 3.1 explicitly characterizing the trade-off between optimization, privacy, and sampling error. The main technical challenge is to carefully control the interaction between privacy-induces of the gradient dynamics across iterations, with the privacy guarantee ensured by Proposition 33.1 We validate our theoretical analysis with experiments on synthetic and real-world datasets, demon- strating practical accuracy-privace trade-offs (Section
noise and the contraction
By developing differentially private algorithm for IVaR and establishing its theoretical bound, we enable researchers to perform robust causal analyses without compromising the confidentiality of individuals in the dataset.
1.1 RELATED WORK
Differential Privacy for Regression. One can group private regression methods into the follow- ing broad families. (1) Output/objective perturbation (private empirical risk minimization (ERM)): add noise to the final estimator (output perturbation) or inject a random linear/quadratic term into a strongly convex loss before optimizing (objective perturbation); these one-shot mechanisms give
(s. DDP guarantees and excess-risk bounds for convex ERM (Chaudhuri et al. (2011); Kifer et al. 2012); Bassily et al. (2014)). Recent refinements, c.g. Redberg et al. (2023). leverage subsam- pling and tighter accounting to improve accuracy. (2) Sufficient-statitiiss (matrix) perturbation: release noisy surrogates of (X X, X y) (or related the (regularized) normal equations; this route enables OLS-specific inference but can suffer un- der ill-conditioning because noise is injected at the fram-matrix level (Dwork et al. (2014); Sheffeet (017)) Tsfadia et al.] (2022) proposes a aassample-andaaggeeaall framework that can, in prin- ciple, be adapted to regression settings by privately estimating the relevant sufficient statistics on carefully selected data subsets. Further developments in this direction include Bernstein & Sheldon (019) and Ferrando & Sheldon (2024). (3) Exponential mechanism: privately selects an output by randomly choosing among candidates with probabilities that grow exponentially with their quality score, with parameters controlling how strongly it favors the higher-scoring options. This mecha- nism is frequently applied in constructing algorithm to privately select regression model from pool of non-private OLS fits on subsets of the data (Ramsay& & Chenouri (2021). Cumings- MMennn (2022), Amin et al. ). (4) Gradient perturbation (DP+(S)GD): clip per-example (mini-batch or full) gradients and add Gaussian noise at each step, tracking privacy with bounded log moment generating function of privacy loss random variable Wang et al. 2019) Rényi DP, and subsampled-
moment structures) and then solve
2

---

Published as a conference paper at ICLR 2026
RDP-which yields tight composition for many small releases and scales well to large n. p without forming X X. (Abadi et al. (2016); Bun & Steinke (2016); Mironov (0117) Wang et al. (2019))
We favor gradient perturbation for multi-stage estimators like IVaR because it (i) composes tightly across many noisy steps using modern privacy accountants, (ii) avoids spectrum-dependent blow- ups from noising X X (Sheffet (017)) and (iii) yields strong convergence rates while fitting stan- dard training pipelines (including using minibatches, streaming, early stopping) and enabling mod- ular, stage-wise design, which preferable for practice (Bassily al. (2014). Abadi et al. (2016). Although there exists DP techniques for estimating gram matrices that avoid blow-ups, e.g., via carefully calibrated noise or regularization (Brown al. (2023), Kamath al. (2019)). the purely sufficient cettisticsbbseed pipelines require larger sample sizes (polynomial to condition number) than gradient-based approaches to reach comparable accuracy in high dimensions (Brown et al.) 2024b). That said, we note that the convergence of private first-order gradient methods still depend heavily on the condition number Varshney et al. (2022; Liu al. (023)).
Instrumental Variable Regression (a)))) has been extensively studied in econometrics (Angrist & Krueger |2001 Angrist & Pischke, 2009). Classical methods such as two-stage least squares (2SLS) admit closed-form solutions but face limitations in modern applications: they do not scale well to high-dimensional or streaming data, cannot easily incorporate regularization, and are restricted to linear models. This has motivated optimization-basee based approaches, including convex-concave for- mulations of nonlinear IV (Muandet et al. 2020). stochastic optimization methods for scalable and
online estimation (Della Vecchia & Basu 2023 Chen et al.] 2024; Fonseca al. 2024), and bi-
level gradient descent algorithms with convergence guarantees (Liang et al. 2025). Extensions to nonlinear IV include kernel-based methods (Singh al. 2019) and DeepIV (Hartford al. 2017). Despite these advances, prior work assumes unrestricted access to the data and does not provide end-to-end differential privacy guarantees, which are increasingly critical in sensitive domains such as healthcare, finance, and online platforms. To our knowledge, no existing method offers DP guar- antees with finite-sample convergence rates for linear IV/2SL.S S that explicitly account for instrument strength, sample size, dimension, and iteration complexity.
Notations: Throughout this paper, unless otherwise specified, we use lower-case letters to denote random variable or individual data samples, and upper-case letters to denote datasets, i.e. collections of samples. Bolded letters represent vectors and matrices, whereas unbolded letters represent scalars.
PRELIMINARIES
2.1 PRIVACY NOTIONS
We first review widely used notions of privacy in the literature. Two datasets D and D' are said to neighbors if they differ in exactly one entry. The concept of neighboring datasets allows us to formally quantify the level of differential privacy. The two most common notions are (c, differential privacy and zero-concentrated differential privacy (zCDP).
Definition 2.1 ((E, Diffferretia Privacy (Dwork et al. 20066). A randomized mechanism M sat- isfies (e. 8) ddifferrretti privacy if for all neighboring datasets D, D' and all measurable sets S, we have Pr(M E S] e Pr(M(DD) E S] + 5. Here 2 0 controls the multiplicative privacy loss, while 5 E [0, 1] allows for a small probability of arbitrary deviation.
Definition 2.2 ZerooCoonentrated Differential Privacy (zCDP) (Dwork & Rothbbum 2016 Bun
& Steinke 2016). A randomized mechanism M satisfies pr-ero-concentratee differential privacy (p-zCDP) if for all neighboring datasets D, D' and all a > 1, we have the D. (M) MD)) s po, where D. (PIlQ) denotes the Rényi divergence (see Appendix A for the definition) of order between distributions P and Q.
While (c, DD is the most widely used notion of privacy, can be too coarse for analyzing iterative mechanisms, as composition accumulates E and 8 linearl []] In contrast, zero-concentrated differ- ential privacy (zCDP) characterizes privacy loss through Rényi divergences, which ensures that the privacy loss random variable enjoys a sub-Gaussian concentration property. This yields two key benefits: (i) tighter composition, since zCDP parameters add under composition, and (ii) smooth
(c,, 8DP also satisfies advanced composition that asymptotically matches zCDP, but the composition more cumhersome and typically less practical than the clean additive composition offered by zCDP.
3

---

Published as a conference paper at ICLR 2026
conversion, since p-zCDP implies (e, (E.P) with E p 2 log (1/6) see Bun & Steinke (016 Proposition 1.3). As a result, we choose zCDP for technical convenience since it provides simple additive composition rule and leaner formulas in context where compose large number of identical Gaussian mechanisms across both stages in 2SLS algorithm.
2.2 IVAR MODEL AND ASSUMPTIONS
Endogencity is a central challenge in linear regression. Suppose we aim to estimate the causal effect of the regressor x RR on the outcome y IR. However, there exists an unobserved confounder that affects both x and y, thereby violating the standard exogeneity assumption that x is uncorrelated with the noise. As a result, the OLS estimator becomes biased and inconsistent. Instrumental variable regression (IVaR) is a widely adopted method to handle endogeneity by including z E IR,, an instrumental variable (IV), to the model (Angrist & Krueger 2001
B x + E1,
x = O z + E2,
where the error terms 6 and 62 are correlated due to the common confounder uz; see Figure for an illustration. Given the dataset (Z, X, Y) {(z, x,, y)) the objective of the IVaR model is to solve the following bi-level optimization problem:
= arg min BER?
((B) = Σ U - -T-
} s.t. 6 arg min @cRix
Σ 3=1
||; O
TT,,
2
13]
(2)
Optimization problem 2 admits closed-form solution. A classical approach to solve equation the two-stage least squares (2SLS) estimator; see Definition 2.3
2 is
Definition 2.3 (2SLS estimator). Given observational data (Z, X, Y) = (zz,,,, k)]= the 2SLS
estimator A2SLS is obtained through two consecutive OLS regressions:
First stage: Regress X on Z to obtain é
ii Second stage: Regress Y on X == ZO obtain BOSLS:
32SLS é Z z
In the following sections, will use 3 to denote the 2SLS estimator for simplicity. We impose the following standard assumptions for IVaR model.
Assumption (IVaR Assumptions). A random variable z E R? is a valid IV, if satisfies:
Fully identification: q 2 p (without loss of generality, we assume data Z, X are full rank). Correlation to Corr x) * 0.
(iii) Exclusion to yy Corr(z, E1) = 0.
In Assumption I condition (i) ensures the existence of the unique solution 3 in equation 2 condition (ii) guarantees that the instrument explains nontrivial variation in the endogenous regressor x, and condition (iii) ensures that the instrument affects the outcome y only through These conditions are crucial for eliminating endogeneity and achieving consistent estimation for B.. See |Stock & Watson [201]] Chapter 12) for detailed discussion. We further impose the following assumptions to establish non-asymptotic rates.
Assumption 2. We assume the following conditions hold:
(i) z is mean-zero isotropic sub-Gaussian random vector. That is, E|z] = O, E[zz I
and for some a= > 0, [ii & exp( u² " }. Vu E R, v E RR.
(ii) C1 Cg mean-zero- sub- Habb-Gaussian. That is, E 0. Elezl = 0. and for some 01, 0, - ), and [[c"(ea.v)] < exp F f Vu E R
E [E < exp( o
'Throughout this paper, assume each entry of the dataset is independently and identically distributed (i.id.).
4

---

Published as a conference paper at ICLR 2026
Exclusion: No direct 2 z path
relevance
causal effect
Instrument x
Endogenous regressor
Outcome
Unobserved confounder
Figure 1: IVaR model: Instrument z is correlated with the endogenous regressor x and influences the outcome y only indirectly through x, while an unobserved confounder u affects both x and y.
Assumption 2 provides the minimal conditions required to leverage concentration results from high- dimensional random design analysis (Vershynin] 2018). Specifically, with condition (i), we have the high-probati boab-rbbbbility concentration bound for the empirical covariance matrix z (see Lemma D.2 "t
Condition (ii) further ensures high-probability concentration of the cross terms Z E1 and Z &a (see Lemma D.3). where (E E2) {(EI, =2.) denotes the sample realization of errors. With these conditions, we derive high probability concentration bound for the sample covariance matrix of X- Zâ (see Lemma D.6), and finally establish the non-asymptotic error bound ||@ 3 (see Lemma D.7p.
Privacy in IVaR may required at different levels depending on the application. some cases, protecting only the causal effect 3 is sufficient, for instance when the first-stage compliance relation @ public, secondary, or not sensitive. other cases, privacy must also extend the first-stage parameter θ such when instruments involve sensitive behavioral data, proprietary mechanisms, or institutional policies. To ensure end-to-end privacy in the IVaR model, we adopt the framework of 7CDP We allocate two privacy parameters: 01 for the first-stage parameter estimates (0(9)7 J1=1 and pa for the second-stage parameter estimates ((3(0) By the composition property of zCDP, the overall procedure satisfies (pi + p2)-2CDP.
ALGORITHM AND THEORETICAL GUARANTEES
We begin with a baseline two-stage gradient descent algorithm, denoted as 2.5 2D-GD, for solving the IVaR problem equation 2 The detailed procedure is deferred to Appendix [ Algorithm
The method alternates between two coupled updates at each iteration: (i) updating the first-stage projection matrix O (*), which maps instruments Z covariates X, and (ii) updating the second- stage regression parameter ((()) based the predicted covariates. This iterative procedure can be viewed as gradient- based analogue of the classical two-stage least squares estimator.
In this section, propose differentially private two-stage gradient descent algorithm, termed DP-2S GDD, to solve the IVaR problem eq while ensuring rigorous privacy guarantees. The algorithm is summarized in Algorithm Compared with 2S-GD, DP 2S-GD incorporates two key modifications: (i) per-sample clipping is applied to gradients in both stages to bound the sensitivity of each update, ensuring that no single datapoint can disproportionately affect the results, and (ii) Gaussian perturbations are injected into both the θ- and B-updates at every iteration, with noise scales calibrated to the target privacy budgets P1 and /22
The privacy analysis proceeds by treating the two stages as separate Gaussian mechanisms with sensitivity controlled by clipping parameters Yi and 72. By the properties of zero-concentrated differential privacy, the choice of noise scales λ1 A2 uniquely determines the effecttive privacy losses P1, P2, which compose additively across iterations. Consequently, for any pre-specified privacy budgets (p1, P2), guarantees. We next establish formal theoretical results, including both privacy accounting and utility bounds for the resulting estimators.
calibrate (A1,Az) to ensure that DP-2S-GD achieves the desired privacy
5

---

Published as a conference paper at ICLR 2026
Algorithm DP-2S-GD
1: Input: Data Z E Raxq X RRxx,, Y RR, target privacy budgets p1, step sizes
a > O, number of iterations T
2: Parameters: Noise scales λ1 Ag > 0, clipping thresholds Y/, 72
3: Initialize 3 = pp. O 0xxp
4: for = 0, 1.
do
5: Draw (4) with vec (ec(E()) N Ai Ip)
6: Draw (1 ~N p
7:
( - -
CLIP 71 (z 0 x, + ()(
8: g((+1) = 3 - - E
CLIP 72 (1) 2. (+) -v)) + az
9:
end for
10: return (0(0))=2, (B(OTE
Proposition 3.1. If we set d1
271
and X2
272
Algorithm p-rCDP, where
= P1 + P2
27' 2
The proof Proposition 3.1 is provided in Appendix B
Remark 3.1. Proposition 3.1 highlights several tradeoffs among the parameters. To preserve the same privacy levels P2. the noise scales λ1, must increase with larger clipping thresholds Y, 72, or with larger number of iterations T. Conversely, larger sample size n allows for smaller noise scales while maintaining the same privacy guarantees.
Theorem 3.1. For any fixed @ E 1R9xP and 3 RP, consider the Algorithm with fixed step sizes satisfying
2
0 0< <
0<as 27(T) + 7(7)
(1+)
under Assumption with parameters
2m1
T
222
T
72 =00 (Vr / + log(nT)
A1 and number of iterations
A2
71
(4)
PI
n
P2
Pin
T
(5)
p(v9 VT)6
where is a small constant. If
(V7 + vT)²
n 2 ci max pq(TT + log(pg))
(6)
mmn((11.22
for any fixed with probability 1 C2e we have
S (()( VDlVT VT) VT VPJ(T + log(pg) -Bll -311 1
(7)
(ei p2)
/n.
where 0 < ((T) < 1 the contraction rate, 5(T) > 0 is numerically small term, and ((T). the high-probability upper/lower bounds the eigenvalues of è z zé of Ö(T), (()), and k(T) are deferred to equation! 10
Tz The specific definitions
n
The proof of Theorem 3.1 is presented in Appendix C We now offer several remarks regarding
this theorem. In the presentation of Theorem 3.1 all constants cu, C1, O2 and scaling factors hidden in "<" are independent of major parameters n, P. q, T, P1. P2. T. These constants only depend on problem-specific parameters B, θ 01,00.

---

Published as a conference paper at ICLR 2026
Remark 3.2. Consider the population optimization problem ming [(3) = E [yy z ) and
the (deterministic) two-stage gradient descent algorithm:
θ (+++l) = O MonB
z ) - -x]]] ((++1) = =((0 aGDE
- z(z 0 - v)
It can be easily shown that under Assumption 2 the sufficient condition for learning rates to guar- antee monotonic convergence are
0 < GGD 2,
AGD
|
We note that in our learning rate condition equation 3 the randomness in data. If we have infinite samples, the condition equation becomes
introduce 8(r) and (T(r) account for
0 x<n <, 0 <<<<
2 O 2 + d (+)
Comparing to JJDD and OGD, notice that we have the same y/ condition. However, the a condition slightly tighter to control the randomness introduced by the first-stage estimates (())
Remark 3.3. From equation 10 the optimal contraction rate x* (T) is achieved when the learning rates are set as
2 (1 + ((T))) + (1 - 8(T))2
Mapprox
approx 7(()) 2(T)
(8)
In this case, have
7(T) (((T)) + (T(T)=
x (T) (1- (1 -1-
(1
max (H)(T), (T)
We emphasize that although Vappnox and approx minimize the contraction rate, they should be viewed approximately optimal step sizes, the scaling constants in the bound equation[vvar with differ- ent choices of step sizes. Empirically, we also observe that the estimator's 's error is fairly insensitive in neighborhood of Nappox: O See Appendix G.1 for empirical results.
Remark 3.4. From Proposition 3.1 the choice of \I A2 in 4 that Algorithm iis p-zCDP. The parameters "i and 72 are selected so that, with high probability, the clipping operation does not alter the gradients; see Lemma D.1 for details.
The error bound equation consists of three dominant terms. The first term <(T) & characterizes the convergence of the gradient descent algorithm, which decays exponentially with T. The second term vF))++/T)² VT captures the cumulative effect of the injected Gaussian noise, by n/min(pp.pez
Remark 3.5.
which grows with V due the parameter choices in equation that ensure privacy. The third term vp((++)og(pg)
represents the inherent statistical error in estimating 3 via noiseless gradient descent, which decreases with larger sample size This decomposition highlights the trade-offs between convergence phase and privacy requirement, while also accounting for the structural statistical ac- curacy attainable from gradient descent.
V
Remark 3.6. The condition for T' in equation is necessary to control the noise scale a in Proposition 3.1 since the derivation of equation relies the high-probability concentration of | With limited sample size n, if P1 is small, i.e. want high privacy on ( (T), we can only set a moderate number of iterations T, otherwise the bound equation 7 doesn't 't hold. See Section for experiments.
Remark 3.7. For given sample size n, the dominating terms for each T' range are:
log
T x
po(Ttlok))))>
if <
log
A(T)
||30))_1111 S
/pg (T log(pg))
log
po(r+)og(p9)²
n min unin(pr,p299(7 + log())))²
if
< <T
Vn
log 1
(Vi + V7)6
k((T)
- + 3
if nt min(p1 (11, P2 )g(T log(pg))
pinz-c
VT.
<T<
n min(p1, }2}
(49 + VT)
p(1q VT)6
7

---

Published as a conference paper at ICLR 2026
Error vs. Iterations
contraction
plateau
T-growthh
Figure 2: Qualitative trend of the error bound equation as function of T.
Hence, the optimum number of iterations 7 is sub-linear but super-logarithmic to n. Figure quali- quali- tatively illustrates the trend of the error bound equation 7 as a function of T. This is consistent with our experimental observations in Section[4
Corollary 3.1. Consider running Algorithm Twith #1 co and p2 (i.e. no privacy provided). For any T > 0, the bound equation is dominated by
[1 ( /pq(T + log(pq))
Vn.
which is exactly the convergence rate of the 2S-GD algorithm 2
Remark 3.8. We note that when P1, P2 additional vp factor compared to the error rate of 2SLS estimator || 3ll (see Lemma D.7 for the precise statement). This performance gap is an inherent limitation of gradient-basee approximations to 2SLS, which is further confirmed by simulations in Appendix G33 As intuitive explanation, the closed-form 2SLS estimator solves both stages in equation 2 Jusing sample moments, whereas the gradient-descent procedure has to approximate the second-stage moment condition. In the popula- tion, the optimality condition for 2SLS ensures E (y - x }] = O. However, in the simite-sample gradient-descent iteration, the update direction will eventually depend on Z (Y ZÔ,3), which involves the empirical residual r : zé,, particular, the quantity || r|| has an error rate +lo(p))og(pg) (see Lemma D.8 which yields the additional yp factor.
and T + oc, the eтror rate equation 9 still has an
V
Remark 3.9. In practice, the intermediate estimates (O(+)T= are not always required to be leased, in some settings it suffices ensure privacy only for { In Algorithm setting simply
P1 implies that noise E(t) needs to be injected in the first stage, and turn (,((0TT Jr= under privacy budget P2. Under this regime, the enror bound equation 7 continues to hold, except that the condition on T' equation 5 is no longer required. See Appendix F.] for further details.
4 EXPERIMENTS
We conduct experiments using both synthetic data and real data to validate our theoretical findings. For all experiments, set 5, and step sizes 17 (1+6(=))a 24(r)+2(r)* As practical guideline, = 0.1 is considered as strong privacy, = 1 considered as moderate privacy, and p 10 considered weak privacy?
4.1 SYNTHETIC DATA SIMULATIONS
We generate synthetic data according to the IVaR model in equation| between 6 and <2, we include a confounder u E IR"" and set 6 u, + e, and 62 = u + Ey.
|
To simulate the correlation
'The corresponding (c, DDP values using the conversion formula = p+2 / plogpl/))1/)) (with 10 10- (.1 + () (2.25, 10 "), p 8) (7.79, 10-5) "), and 10 (c, = (31.47, -).
8

---

Published as a conference paper at ICLR 2026
Algoritmm 1 Error (o-3) q
Algorthi 1 Emorr vs 1p-550 9::00
p-m 00, 2.-3.00
p.m1,00 pum t0
Re-5 00, 2i-5.00 30
pow 90 ped 00
para p--1.00
20
pur 0,00
1.0
1.5
0.6
1.0
0.4
0.2
Sample
Sample size
Figure 3: Comparison of Algorithm I performance versus n. We set T = 20, (a) (a) p == 5, (b) p q 50. Note that the T condition equation 3 is not satisfied in (b). We set the total budget 10 and compare three regimes: (i) P2 9, (ii) 5, P2 5, (iii)
92 1.
The curves are averaged over 100 runs, with vertical bars representing the standard errors.
Algorithim 1 Eraor us (nw 1000, p=S, qm51
Algorithm 1 Ennrr vs (o=1000, p=5, q=5)
So-100 10-100
0.5
196, poo0.1
p-i. p--103
p-100, punt
0.7
(oeld, goml00
25.5 (hanadine)
(hanebir))
0.25
0.5
0.20
0.4
0.15
0.3
0.2
8.10
beratone
Baration
(a)
(b)
Figure 4: Comparison of Algorithm [ performance versus number of iterations T. We fix 1000, p = = 5, (a) keep P2 large and vary Pt. (b) keep large and vary P2. The curves are averaged over 100 runs, with vertical bars representing the standard errors.
and generate each entry of the dataset (2 Y) {(zi, xi,))) according the following model: X; θ
+ u, + Emii and y; 3 x; + & u; 6y.i, where the ground-truth parameters are B E IR, θ E Raxp, $ E Rrxp, & E R", These parameters are drawn as follows: (0,, I,), O 5Igxp
with Eg ((.. Diy ~N(00,) 1), and Φ (O I,). For each simulation, we then sample z, ~ (.O,L, ~ NO. I,) Ens ~ ~NOO I,). and Cy. ~ 1O),
Algorithm T across different sample sizes n under varying privacy allocations. We fix the total privacy budget at
Figure compares the performance
/ + P2 10, set the number of iterations to T 20, and examine three regimes: (i) Pi 1. 9, (ii) P1 = 5, P2 5. and (iii) P1 9, P2 = 1. In Figure Ja), with
= = 5, all points lie in the plateau region of Figure so the error decreases at the rate _ contrast, Figure 3(b) sets = q = = 50. V
Here, T = 20 violates condition equation leading to significantly larger eπrrrs compared to Figure (a). The impact of T is further investigated in Figure 4 from which we observe that, with limited sample size n, if enforce high privacy guarantee on (+) ) (G)))) (i.e. with small P1), the error grows significantly after certain T' is reached. This cutoff aligns with the condition on T' specified in equation In contrast, when privacy is required only for (((()) ) (i.e., with small P2). the error behavior closely matches the theoretical predictions illustrated in Figure

---

Published as a conference paper at ICLR 2026
Average f path
16
Distribution of final estimates across 1000 runs
Average g
Buss
25L5
-2
B
CLS
Coefiiient estimate
2.5
10.0
15.0
Iteraation
Average @lll path
Average 8I
0.03
achoss runs
-8-
0.01
2.5
7.5 10.0
15.0
37.5
gm
Iteration
(a)
(b)
Figure 5: Results on the Angrist dataset with T = 20, 1, = 1. (a) Boxplot of estimated ( over 1000 runs. (b) Learning paths of parameters , ((),, over 1000 runs. The shaded area represents the standard error.
4.2 REAL-DATTA EXPERIMENTS
We further evaluate our algorithm on the Angrist dataset (Angrist & Evans 1998). which has been widely applied in the IVaR literature. This study examines the causal effect of children bearing on female labor supply. leveraging the gender composition of the first two children as an instrumen The endogenous regressor x is the number of children bearing, the outcome y is the mother's labor supply measured in number of working weeks per year, and the instrument is a binary variable indicating whether the first two children are of the same gender. The original dataset contains 394, 835 samples. For illustration purpose, we randomly draw subset of 20, 000 samples and keep n = 8065 effective observations with number of children 2 2. We center all variables z, x. y and run Algorithm [ with T 20 iterations. Figure 5 presents the results over 1000 independent runs with privacy budgets #1 P2 1. As shown in Figure 5a| the estimated g concentrates around -43,, indicating that having an additional child reduces the mother's s labor supply by approximately 4.3 weeks per year. This estimate is consistent with the 2SLS benchmark.
From Figure 5b] we observe that Algorithm D converges in expectation after about 15 iterations. The dispersion of the estimates is determined by the privacy budgets: increasing /r and P2 yield estimates that are more tightly concentrated around the 2SL. benchmark, while smaller budgets result in greater variability. Additional experiments provided in Appendix G.4
CONCLUSION
We have introduced DP-2S-GD, differentially private two-stage gradient descent method for IVaR problem. The algorithm achieves (p) + p2)-zCDP by injecting carefully calibrated Gaussian noise. We have established finite-sample convergence guarantees that capture the trade-offs among opti- mization dynamics, privacy constraints, and statistical eтror. Our theoretical analysis shows that setting the number of iterations T' to be sub-linear yet super-logarithmic in n minimizes the estima- tion error, a result that is corrohorated by our experiments. We have further illustrated the practical utility of our method through an application to the Angrist dataset. On the other hand, we note that, regardless the privacy constraint, the convergence of the two-stage gradient descent estimator to / slower by vp compared to the convergence of 3 to the true parameter ,3 (see Remark 3.8). Im- proving this rate (via algorithmic modifications) and establishing lower-bounds for privacy-accurage tradeoffs for the IVaR problem are interesting future directions.
'Research shows that parents whose first two children are of the same sex are significantly more likely to have an additional child (Westoff & Parke 1972). At the same time, the composition of the first two children be treated as randomly assigned and is directly related the mother's lahor supply.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
All theoretical results are proved in the Appendix, and code for reproducing all experiments is provided in the supplementary material. LLM was used to polish writing and for finding related work.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, 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, pp. 308-318, 2016.
Kareem Amin, Matthew Joseph, Mónica Ribero, and Sergei Vassilvitskii. Easy differentially private linear regression. arXiv preprint wrXiv:2288.0735. 2022.
Joshua D. Angrist and William N. Evans. Children and their parents' labor supply: Evidence from exogenous variation in family size. The American Economic Review, 88(3):450-477, 1998. ISSN 00028282. URL http: / www. jstor.
Joshua D. Angrist and Alan B. Krueger. Instrumental variables and the search for identification: From supply and demand to natural experiments. Journal of Economic Perspectives, 15(4):69-85, 2001. URLhtttps
www. aeaweb. oww.ee...r//rrtteceee//. 12000/125///ee/ 15. .5.69.9
Joshua D Angrist and Jöm-Steffen Pischke.
Mostly harmless econometries: An empiri- cist's companion. Princeton University Press, 2009. ISBN 9780691120355.
URL
https::/prest www.prrincctoooo edu /bt.k//oo/////// bobooks/hardaee
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. 2014 IEEE 55th annual symposium on foundations of computer science, pp. 464-473. IEEE, 2014.
Garrett Bernstein and Daniel R Sheldon. Differentially private bayesian linear regression, Advances in Neural Information Processing Systems, 32, 2019.
Gavin Brown, Samuel Hopkins, and Adam Smith. Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions. In The Thirty Sixth Annual Con- ference on Learning Theory, pp. 5578-5579. PMLR, 2023.
Gavin Brown, Krishnamurthy Dvijotham, Georgina Evans, Daogao Liu, Adam Smith, and Abhradeep Thakurta. Private gradient descent for linear regression: Tighter error bounds and instance-specift uncertainty estimation. arXiv preprint arXiv:2402.1353: 2024a.
Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan Perdomo, and Adam Smith. Insufficient statistics perturbation: Stable estimators for private least squares. arXiv preprint arXiv:2404.1 15409, 2024b.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, pp.
Springer, 2016.
David Card. Using geographic variation in college proximity to estimate the return to schooling. NBER Working Papers 4483, National Bureau of Economic Research, Inc, 1993. URL https:
//EconPapers repec. org/ RePEc:nb: :tw::nnrnbbbbrrr. nbeeww 4483.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal Machine Learning Research, 12(3), 2011.
Xuxing Chen, Abhishek Roy, Yifan Hu, and Krishnakumar Balasubramanian. Stochastic op- timization algorithms for instrumental variable regression with streaming data. In Proceed- ings of Neural Information Processing Systems, Vancouver, Canada, December 2024. URL https: (tops://asee /tts:///rxiiv wtt//as//2/3...//3 http::////rrdv..oorraa///////// 19463

---

Published as a conference paper at ICLR 2026
Ryan Cumings- Menon.. Differentially private estimation via statistical depth. arXiv:2207.12602 2022.
arXiv preprint
Riccardo Della Vecchia and Debabrota Basu. Stochastic online instrumental variable regression:
Regrets for endogeneity and bandit feedback. arXiv preprint arXfv:2302.09357, 2023. URL
https://arxiv wtt.abs////oooooooo.ot...t...ort abs///02 03302.09355
Cynthia Dwork and Guy N Rothblum. Concentrated differential 10X.01603301887, 2016.
privacy. arXiv preprint
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.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for
principal component analysis. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing, pp. 1--00, 2014.
Cecilia Ferrando and Daniel Sheldon. Private regression via data-dependent sufficient statistic per- turbation. arXiv preprint arXiv:2405. 2024.
Yuri Fonseca, Caio Peixoto, and Yuri Saporito. Nonparametric instrumental variable regression through stochastic approximate gradients. In Proceedings of Neural Information Processing Systems, Vancouver, Canada, December 2024. URL https::/ www.aaxxivvrr.. 05639
/ wtwp://///bbb/2222222
Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy. Deep iv: A flexible approach for counterfactual prediction. In International Conference on Machine Learning, pp. 1414-1423. PMLR, 2017.
Jerry Hausman. Mismeasured variables in econometric analysis: problems from the right and problems from the left. Journal of Economic perspectives, 15(4):57-67, 2001. URL https:
/ //www. aeaweb. org/ att//attiico 2ee.
Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Conference on Learning Theory, pp. 1853-1902. PMLR, 2019.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings, 2012.
B. Laurent and P. Massart. tional by model selection. The Annals of Statistics, 28(5):1302-1336 2000.
Adaptive estimation of quadratic func-
org doi: 10.1214/ao/10115557..
URL https: wew.euccc...c. for 10. 00.1214/a0//0015553333 full
sel ection/
Haodong Liang, Krishna Balasubramanian, and Lifeng Lai. Transformers handle endogeneity in in-context linear regression. The Thirteenth International Conference on Learning Represen- tations, 2025. htttt://////
/tLl:tsts////peeeevviee /wwpn/eeeeeeeeeeeeooe/eeee net. http:/oormmmdddee heet//oorunndd-00EE3220
Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, and Arun Sai Suggala. Near optimal private and robust linear regression. arXiv preprint arXiv:2301.13225. 2023.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer f foundations sympo- sium (CSF), pp. 263-275. IEEE, 2017.
Krikamol Muandet, Arash Mehrjou, Si Kai Lee, and Anant Raj. Dual instrumental variable regression. In Proceedings of Neural Information Processing Systems, Vancouver. Canada, December 2020. URL https: htttp:::/pprcceeiggs..oom 1c383cd30b c2 20a2288bb2222 1118::::00010200033eeeeeee111111 Abs.tbllb-bbbtttt.... html
Kelly Ramsay and Shoja' eddin Chenouri. Differentially private depth functions and their associated medians. arXiv preprint arXiv:2101.02800 2021.
12

---

Published as a conference paper at ICLR 2026
Rachel Redberg, Antti Koskela, and Yu-Xiang Wang. Improving the privacy and practicality of objective perturbation for differentially private linear learners. Advances in Neural Information Processing Systems, 019113889-13853, 2023.
Or Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pp. 3105-3114 14. PMLR, 2017.
Zihua Si, Xueran Han, Xiao Zhang, Jun Xu, Yue Yin, Yang Song, and Ji-Rong Wen. A model- agnostic causal learning framework for recommendation using search data. In Proceedings of the ACM web conference 2022, pp. 224-233, 2022.
Rahul Singh, Maneesh Sahani, and Arthur Gretton. Kemel instrumental variable regression. Ad- vances in Neural Information Processing Systems, 32, 2019.
J.H. Stock and M.W. Watson. Introduction to Econometrics. Addison-Weslen 3rd edi- tion, 2011. ISBN 9780138009007 URL https: scholars. edu/ publicat 1 onns int roduct ion eccnometrics
Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Friendlycore: Prac- tical differentially private aggregation. International Conference on Machine Learning, pp- 21228-11663, PMLR, 2022.
Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. (nearly) optimal private linear regression via adaptive clipping. arXiv preprint arXiv:220..04686, 2022.
Roman Vershynin. High- High-Dimensional Probability: An Introduction with Applications in Data
Science. Cambridge University Press, 2018. ISBN 978- 1-119999944444444 URL hetps:
7/www. http://.......ee//oo//o//o//////
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd international conference artificial intelligence and statistics, pp. 1226-1222 1235. PMLR, 2019.
Charles F. Westoff and Robert Parke. Demographic and social aspects of population growth. Com- mission Population Growth and the American Future, 1972. URL https://catalog.
dathitrust.c ott//eoo///00000000000
Jeffrey tion and
M
Wooldridge. Panel
Econometric Press,
Analysis of Cross
Sec-
Data.
MIT
2nd
edition,
2010.
ISBN
9780262232586.
URL
Yang Xu, Jin Zhu, Chengchun Shi, Shikai Luo, and Rui Song. An instrumental variable approach to confounded off-policy evaluation. In International Conference on Machine Learning, pp. 38848- 38880. PMLR, 2023.
13

---

Published as a conference paper at ICLR 2026
A ADDITIONAL DEFINITIONS
Definition A.1 (Rényi Divergence). Let P and Q be probability distributions on measurable space F), with absolutely continuous with respect to Q. For a 1, the Rényi divergence order between P and Q is defined
(a a log / (dg(s)) (a)) dQ(x).
This family of divergences interpolates between several well-known measures: (1) As a - 1, (a(lll + DKL ()) the Kullback-Leibe divergence, and (ii) As oc, Da (PlIQ) 4 dP log sup 2Q (z), the log of the essential supremum of the likelihood ratio.
Definition A.2 (2S-GD). We introduce the baseline two-stage gradient descent algorithm without privacy constraints, denoted 23-GD, in Algorithm
Algorithm 2S-GD
1: Input: Data Z E IR_ X E Raxp, Y RR
2: Parameters: Step sizes 1). a 0, number of iterations T
3: Initialize ((0) 0p. O 0xxp
4: for t- = 0, l.......
do
5: (++1) ( 2 "Σn
- (z ( -x,)
6: g(++1) = (*) a _ (t) (z, (*)) y4)
7: end for
8: return {0(0) (B
B PROOF PROPOSITION 3.1
Proof. At iteration t we are releasing two Caussian-mechanne on sums of clipped sample gradients (each clipped to norm not larger than 71 and 72), one with noise scale X (for )) and one with noise scale A2 (for B). By the standard zCDP analysis:
-pddate: Sensitivity of the summed (clipped) gradients is A 2m,, and we add noise E with vec [=) ~ N (0, I2 Ip). By property of Gaussian mechanism, this step satis-
2 x>
fies P1
zCDP
3-update: Similarly, A2 2n2 this step is po
2-
n '
By linear composition each iteration costs
2
71
22
Pperit P1
+
n
Over T iterations the overall mechanism satisfies
= n²
2T
x
2
+
X
>CDP.
C PROOF OF THEOREM 3.1
Before the full proof, we would like to provide a high-level summary of our proof strategy to facili- tate readers' understanding. Conceptually, our proof tackles three key challenges:
(1) Two-stage coupling: We control pair of noisy recursions (+)()) Jesr and (3(0)) her where the second-stage gradient at time t depends on the noisy first stage iterate O This coupling does not appear in standard DP-SGD analyses.
14

---

Published as a conference paper at ICLR 2026
(2) Noise propagation: Since add Gaussian noise every step and stage, the privacy countant composes over all 2T iterations. To obtain a meaningful error bound for the final iterate ((T), we need to separate the contributions of optimization, privacy, and sampling eπror. This decomposition gives rise to the three terms in Theorem 3.1 and explains the tradeoff pattern shown in Figure 2 and our experiments.
(3) Non-asymptotic rate: The analysis retains explicit dependence on all major parameters: sample size instrument dimension q. regressor dimension p. privacy budgets p2), and confidence parameter T.
The whole proof of Theorem 3.1 decomposed into several supporting lemmas in Appendix D to handle all these challenges.
We first re-state the result with additional details.
Theorem 3.1. For any fixed + E RR and B E RR, consider the Algorithm ! satisfying
with step sizes
2
4 0<a< 27(T) +7())
0 < 17 <
(1 (1+8(T)) oT))2))
under Assumption] 2 with parameters
2
272
T
71 =1 =c 100==00 2va + V + loog(n))
\
P1
P2
and number of iterations
TS Pinz-c
p(v9 VF)6
where 0 is small constant. If
(Vq+ vF)² 3
n 2 Ci max pq((T+ + log(pg))
p2
for any fixed r, with probability 1 - C2e we have
VTlv + vF)a VT
/pq(T + log(p)) Vn
(T -B11 S x(())
ny m/minfp1, p2]
where
8(7) Coo? + VT) Vn
2(7) = (1- 8(T)) (amin ( - x(7))²² 7(7) == (1 (1)) (101 + ((7))²
11-6(
((T) 22 po (T + log(2pg))
Vn (1 - 5(7))
(10)
[1 (T(
1,11 a(27(T) + (())
kg(T) = max
2
kT(T) max
(1 (1-(6()) (116(1))(.(11-1))) 1
(1 8(7))
<(T) =
15

---

Published as a conference paper at ICLR 2026
Proof. Denote ég
(1)
(4)
θ and (1)
e/ 3(0) 1300-8. 3. We have
((+1)
! T
70( x) + +15
0
I
"z T Z
C
(6)
+
" z T (x- / + + (t)
n
I
! Z Z
4+ (0) Σ
(I
? Z 2)
1-
( Z (x ZÔ)
11
(II)
n
n
i=0
I
! Z
1+1
6
(0)
+
11
! Z z
bi
30
71
n1
NO9
(++1)
(8)
a
(
(0 ( Y) + (z (2)
9
3
n
OTT Z Z
3 + 2
(
- ZT Y- (0(() T 20(1)) /
+ tax
1OT Z
(4) TT
Y - (- 3) + (v)
8
(0TT ZO(1)
(1)
OT
7 (0 6) ()) n
(011) zT (Zô, y)) + ozl
I oH
(0)
((()
Z Ze (1) β
0 ( Z r (z
C n
n
(12)
where (( == ()) Z ()()) and ZÓg Y.
We first show that H(() is close to the target
A T TZ. We define the event
FIg.T { |1 0 = |
6 sk
Conditioning on the event FT,TT, we then have
H H|
( zo - T Zé
(0) Z ((0 é) + (e -) z ZO]
< } (I0@)) + ||]|)] Z
n
Z Z
< @|| + s)]l
|le,
VT STST
From Lemma D.2 we have with probability at least 1 TT
Z T Z
n S {1+8
so that
( H| S @ + e)(1 + 8(7)))& VT SIST.
Suppose 2(7), are some high probability bounds such that Amin (H) > 2(T) > 0, Amax (H) S
(()). From Lemma D.6 we can take
2
Co Pq (T log (2pq)
2(7): = (1- 5(7))2 (mmii(e)
Vn (1 6(7))
2
||1|| c00 pg (T + log (pg())
:0):== = (1 5(7))²
Vπ 5(T))²
16

---

Published as a conference paper at ICLR 2026
If e satisfies the following condition:
2(r) 2(2 + + (1+ 8(T))2²
L.c. we choose
2(T)
E |1612 12 + 2(1 + 0(T))² |+||
(13)
by Weyl's inequality, we then have
2(T)
Amin (H()) 2
Amin (H) [[ H 2 2
(+))) I Amax (H) + ( H 1 (() + 2(T)
Amaa
2
This in turn implies that on E when 0 <<< < 22(7) we have
|I (H S
max
admin ()min(H())) mmx [H
(C((T)
1./1 a(27(T) + (T(T))
}
(14)
max
= KK((T) <1,
2
2
hence the error recursion equation|
12
satisfies
|| ( || S
(0
(9( z ( Ze ||
0 10 z ZTrll (1|
and
||o (
(= 10
TTo)
Kig kT((T) (-a(T)---- (10(4) z
Ze 20000 01 1 (+)T zJ rl)) +
1- 1-k3(7))10) |||||
n k=To
0 1 T @|
T-1
a |T T-1
I (ig(7)² TTo TTo 10@
(To)
Σ
kg(T) -
k=To
[1|
Ki((T)
S <KO(T)T To To
TToo
(To)
+ + 8())))1111
Σ
k ||e@
+ a
IZ rl
kg(T) T- (+)))(
n
k=To
1 (-k |1||.
(15)
Under event ET, we have the uniform bound:
( [
S
||
| +
vT, S <T
||o (k)
Se
TT
< T.
Besides, from Lemma D.5 and Lemma D.7 we have when n = [(p((T + log(p4))), ||¹| and || are bounded by some constants with high probability:
|| 1 |+]|| $ 1.
From Lemma D.8
we have
IZ Tz|l|| S Vrpgg( (T + log(pg))
Since (O, ATI,), we have with probability 1 1- TT,
|| A2 (vp VF).
17

---

Published as a conference paper at ICLR 2026
Then from equation 15
T-1
Hi((T) --1 az Z r|[[|||| + +6)
T-1
(1 + Σ ||0 || S T|
(To) | +
Σ
T-1-k
k=
R= 7o
1 kg( |||
$ <na(T)² 1 (T)) |+ a(1 +
ax a r||[|6@] +
+
1 1- (T() ||||
a
1 1 (T)
12 (1 kg(TT)
| +s((+ss) + spa(T log(pg))
$ xa(
(Tb)
(1 (1+s) + A2
Vni
(16)
remains to bound
le
(Ta) B
Denote L (9) : I- 0, .,................. To -. Note that from Lemma
D.9
To
[
|| can be bounded by a constant for any To S T. From equation
12
we have
To
To-1 T6-1
To- Tn-1
%
(26)
L
(0)
Σ
II
(
+ (1)
z Ze (3) (
Ze
(N) zJr
+ a
Σ
II
(0)
t=++1
Then
To-1 II
a(1@
+ +
z ZT |||
To To-
||e
(Ta)
S
(1)
||e|00
1
(
t=0
k= 1=
a<l
+ E Z r||
To
To
[+1
+ 1 (T)(T) |||||
n
A=0
t=k+1
< ||||| + @| || + 2
Z
|||||
(1) + e) Z r|
|| [x00
To -2 (2
n
k=0
VPq(T
log(pg)
< + (1 + o
max 0SkSTo-1
|
#1+ A2 (vp + vT)
(17)
Now, it remains to determine the values of E, To. T, and the bound for max 11e
From Lemma
D.4 where take A1
2x1 T
with probability least 3e have
pi
ET.,T { S s, VTo < ke T3 hold where
mA
e = (T
To | + v1 (T)
(Vrq + V 2p (log(p) + +T)
2m71
'T
(Vr + 22 (log(p) 7)
(18)
+ n2/1 Ke (T)2
Pr
$ (o + (MT),
where
8(7) Cooj + VT)
Vni (T(T) == max { 1 1/(1 (11-
8(T)) ((11-(7))
(1++)()))3))
((T) = A krq v (log(p) + +7)
'A rigorous analysis requires setting := log(T') to account for the union bound. However, under condition equation 4 log(T)) grows slower than any positive power of thus omit this term. Similar argument applies to later analysis.
18

---

Published as a conference paper at ICLR 2026
Similarly, we have with probability at least 1 - 3e
||og (K)
|||@| + VI- (T)
1711
(VPT + 22 (log(p) + +1)
max osks7o-1
(19)
=E+ (1 ke ||@||
11+ ((T).
Next, we need to pick T, To such that condition equation 13 is satisfied:
2(T)
S |1
||O| 8.
(20)
2(1 + 6(7))²
This can be done by setting
Ko
27771
T
(vPq + v (log(p) +T) +T)
1 2
(21)
n
Ke
P1
where from Lemma D.I.
when n Z (Vg + v=) max -
voab ). we set 71
ci(V +
Vpi
VT + log(nT))?. We take
7(7)
)1
2(1+8 611
To 2 logne(t)
(rg
to(n),
(22)
2||@1
2
T Pin2
(23)
R(T)2
where is small constant to guarantee equation
21 converges to 0 as n oo, and
R(T) = (V7 + (vP + p(log(p) + +))
(24)
S +v((v++V7)
Plugging T and m into ((T), we have
p(T) A1
(Vpq+ + (log(p) + +
2n
T
(VMI+ (log()) + +T)
n
P1
R(T)) VT
VPi
So when satisfies condition equation and the bounds equation 18 euquuioo
21 and n satisfies condition equation 6 we have j(T) S 1,
19 can be bounded by constants:
E
1,
max 0
||e (8) 1
(25)
To
( 2
1+
In equation 22 we have (n) + log1-n
So to(n) is upper bounded by
constant integer C2. With To C2, plug in equation 25 into equation 17 have
Vpq(T + log(p4))
| (C2) S 1 + (1 + To
max ||o 0sksTu-1
(1 (1+
A2 (VD+ VT)
Vn
11+Ca (1 1+
vpq(T + + log(pa))
+ do (VD+ vF)
Vn
11+12 (VD+ VT).
(26)
19

---

Published as a conference paper at ICLR 2026
We further take To max ( C2.. Note that from equation 16 the bound of ||e/ (T) will always
decrease after T > To : C2. Hence, the bound equation 26 still holds for To:
(bb g S 1 + A2 (vP + VT)
|
(27)
Plug in equation 27 into equation 16.
we have the final bound:
++)+++))+ vPq(T log(pg)
lle (2)
xa(TT) To lle
(To)
(1+ + 42 (vp+ VT)
Vn
$ <na(T) (1+ X2 (vp+ V=)) + [Ke(T) + u(T)) + vpr(T + (lo((pg))
+ >2 (vp VF)
Vn
(Pu(T + log(pg))
$ (nO(T) + =k(TT) _ + ((T) + d2 (2p VF)
Vn
(28)
where 1u(T) 2
R(r) VT vpi n 2
21y
From Lemma
D.1
we
take
Y2 =
22 (va VT + log(nT))
Continue on equation 28
we have
R(T)
VT
R(T)
VT
(P + log(pg))
I1 S x + (T)
VPi
P2 n
Vn
(29)
(+)
(sit)
(iv)
which concludes the proof. The error bound equation 29 consists of four terms: (i) the effect of
shrinkage factor (T) (ii) the estimation error from e := θ (4) - Ô, (iii) the error from additive
noise (*), and (iv) the random residual error from ZÔg Y.
D SUPPORTING LEMMAS
In this section, we collect the supporting lemmas that were used in the proof of the main theorem. Throughout the proof, suppose that Assumption and Assumption 2 hold. Unless otherwise specified, we assume the learning rates a, 17 satisfy condition equation with parameters chosen
according to equation 4 and sample size satisfies condition equation 6 Lemma D.1 (No clipping condition). Under Assumption
71 (Vr + / + log (0g(n]]
72 2 ( V log(n()
learning rates a, v) satisfy condition equation
3 and n satisfies following condition
- (vQ+
/min(p1, P2)
then the Algorithm cliiss gradients with probability least če -7
The proof Lemma i. in Appendix E.
Lemma D.2 (High probability bound of sub-Gaussian random matrices). Suppose Z is an X matrix whose rows Z, are independent mean-zero sub-Gaussian isotropic random vectors with sub- Gaussian norm Zz 1l I 02 for all i = 1....,m. n. Then, for any > 0, we have with probability at
least 1 2e
VT 8(T)) < mmin (Z) maax (Z) < Vo 8(T)),
where 5(T) C When 2 Cho (Vg + v=) 2 further have
v
(1 0()))² < Amin (Z 2) < Amax iz Z) < n(1 + 8(7))²
where Co is universal constant, Tmin (c), Tmax (-) denote the minimum and maximum singular values of a matrix, Amii (.), Amax (-) denote the minimum and maximum eigenvalues matrix, respectively.
20

---

Published as a conference paper at ICLR 2026
The proof of Lemma D.2 is in Appendix E.2
Lemma D.3 (High probability bound for the product of sub-Gaussian random matrices), Let Z be an n X q matrix whose rows Z, are independent mean-zero aub-Gausiian random vectors with sub- Gaussian norm || Z 11 I Jz for all I...., n. Let &g be an n x p matrix whose rows E2, are independent mean- sub-Gaussian random vectors with sub-Gaussian norm [|2,,ilyz S 0g for all i = 1,...,, n. Then, for any > 0, we have with probability at least 1 - -
Iz |2 < c00202//pp4 (T + log(2p4)).
The proof of Lemma D.3 is in Appendix E.3
Lemma D.4 (High probability bound of additive noise). Let e = (1-
2)
e + N
where N( = Σi= (I z z) t- 3 and E(i are generated from Algorithm
Suppose
the learning rate 7 satisfies the following condition:
2
0 0<
(1 (1+661)) 5(T))²²
where ö(r) = Coo2lvitV have
When 2 coo² (V + vT)², with probability at least 1 3e-
vn
||
1111
(VM + 22 (log(p) (logl)))+ +T))
V1 12 (T)
and
||@@| (1) ||
S n (T)
(0)
1
(vPq + /2p (log(p) + +T)).
v1 n (T)
where (T) = max
711
Coo2lv
)2
111-1(1 Coo2(vātV )3
<1.
vn
//
The proof of Lemma D.4 in Appendix E.4
Lemma D.5. Let = ê θ (Z Z) TT Ez. When 2 Choilv9 + vT)², we have with
probability least 1 3T-
CoO, pq (T (ogg((29 log(2pg))
V (1 - 8(T))²
Co02(v7+V7 Vn
where 8(T) ==
Co, co are absolute constants.
The proof of Lemma D.5 is in Appendix E.S
Lemma D.6. Suppose Assumption holds. Let H _ zÓ. When 2 Cipa(T +
"
1 the following inequalities hold with probability least T::
2
C00=02 /pq (r log (pq))
Amin (i) (1 - (1-11116
(1-)))) Omin (0)
/n 8(T))²
||a||| C00 PM (T + log((ogg) (2pg))
Amax (H) (1+ 8()))²
Vnl (1 - (1))))
The proof of Lemma D.6 is in Appendix E.6
Lemma D.7. Suppose Assumption holds. When n 2 Cipg(T (og(p))) we have the following inequality holds with probability at least 1 - -e
<g ( + log(g))
| 3| 5
Vn
The proof of Lemma D.7 is in Appendix
E.7
21

---

Published as a conference paper at ICLR 2026
Lemma D.8. Letr Z For any fixed when (Lpg(T++oo(pp))) with probability at least 1 3e "T we have
Z r|| S O (Vrig (T + log(pg))).
The proof Lemma is in Appendix E.8
Lemma D.9. Let [()) = I _0(0) z ze(4,,
We have with probability 1 -e-
7, for any
0 < To T
To
S 1.
The proof of Lemma is in Appendix E.9
E PROOF OF SUPPORTING LEMMAS
E.1 PROOF OF LEMMA D
Proof. Consider non-clipping version of Algorihm For t = 0,..., 1, we have
Denote eg = ==((0-_ -
- and ogg = 3(0) -B.
(1+1)
C
(t)
7
Z
(t
X + +)((t)
n
(30)
Z Z
c
(1)
+
" Z
X (xzz) + ,,
n
n
and
(++1)
(8)
a
(O) Z
00 (0 3( Y) + atv
9
11
T
(4)
( Z T Y- (t)) z 20 +av(1)
6/
Z
(1)
OT
Y 2 + av)
0/ +
n
n
(OTT
ze (0)
(1)
0 TT
7 (z(0()) - 2) 3) a
(0(0T zT (zêg v)) + az
03
n
n
a θ
(T)
Z
Ze
"1
(T) (T
r (z
n
(31)
where L
I
O Z ze : ZÔ,3 Y. By iteratively applying recursion formulas
equation 30 euuuation
31 until 0, with (0) = 0 0px and (3 Op. we have
e())
I
" Z
Z
θ Σ 1 1I
"
=(1)
71
n
t-1
a 1-1
1-1 II
t-1
(00 = 3
I O 3
Σ
(
(T) Z
Ze
(1)
3
0
ZTr
a
10
n i=
i=0
j=it1
1=0
The gradients at step are given by
2, T (1) x
9: = z;
of = e (T)
z 3 (t)
g
zi
y/
Bound on (t):
We have
! (0]l -
2:
0 (1)
x, + -
2,
22

---

Published as a conference paper at ICLR 2026
(
2, (x] - 2 6)
2,2
O +
+ 2 (x] - 2 0]]
2
2,2
θ 9
(1 zz T 2) 3
Σ
1-1
(1
- Zz
t-1-j =(1
+ +1|2 (xT - -2
71
1=0
2
-
(I - 2 zTZz (o - 8))
(6--8)
+ [,27
(I-
27 z Z
-
n
n
(68)
1-1-j
+ Σ 172,2
T [ ZTzzZ z
=
+ 2/ (x] 2 θ)
j=0
(cv)
(128)
We further have
1 11-2g ZZ z) )) (6-
(i) = Z,Z T
71
[I ' ZTTzZ z) 11) 6 o
|2:11
1+
n
(i))
[ (I- " Z 2) )
n
| |
(
77 Z TzZZ 2) |0||
n II -I"ZZaz Z
(mi)
Σ 12.2
T
1-1-5 =0}
n2
S n 1
I 1 T z
n
S 11 2
II Iz Z
1-115
| ||.
n
1=0
(iv) = | (xT - 2 T)) || = =|1z,22,1|
< 22 ||E2,|||
Under sub-Gaussian assumption on z; and E2, we have with probability at least 1 - -7
| S (v
||22,1| 02 02 (Vp+ VF).
From Lemma D.4 we have when 0 < <イ< at least 1 1 2e
<
[[+0(T))²
2 and 2 Chot(V vF)? with probability
||| Zz Z|| < (T( 1 n
From Lemma D.5 when n 2 Clal( + VF)², we have with probability at least 1 3T-
| θ|| 1 1.
23

---

Published as a conference paper at ICLR 2026
Additionally, by standard concentration results in random matrix theory, with probability -e, we have
- I (VD+ Va 1 22
To sum up, have
( 5 + VFY,
(i) 2 V VFP.
(mii - 0z vF) (V VT). /F) (vD+ V7).
(iv) S 0=02
With A1 2011 V we take o' r log(nI) and plug everything back in the final bound, we have with probability at least 5T e
11 (1)] o V + log(n()))
1+ (VD+ Vq + V + log(n(()
S o + V log(nT))
1 7
T
(V + / + log(n7))
P1
We want to choose appropriate 71 such that [1)] S 71
with high probability, for all
O, ...., T Therefore, the condition for 71 is n. /
0aa2(V9 + T + log(n)))
71 2
1 02 /o+ HloR(NT))
VP / + V log(nTT)
(32)
2
2 ( + V (oggnnt)
which is subject to the condition
n n= Ω
(V + VF)²
T V pi
(VD+vg+VVT)
(VT+ v
T
p1
where we ignore the / llo(nnT)) term since it grows slower than any positive power of n. Finally, taking the union bound over i I..... and O..... T 1 completes the proof.
Bound on (1):
From equation 32 if we take 71 2 (vT + T + log(nT)) with probability at least 1 - ce
[19, ()) < 7,, Vi 1...., and L 0, ...... T 1. Now we analyze the gradient of (1). Under
model
y: 33 JT c
2; 0 2, C2,
we have
of (t) ) (T)
2; 2 (0)()))))))))))))
2. 0 x ( y1
e (T)
2; 7 (0)) ((0) 2 O (0 3 (0 B 3 ( 2, + E2,)) -E1.3)
e (TT
Z,Z. (t) (3 3) +
T
2
0 B 003 (()) (3 E2s + cas)
(OT
7,7 (t) (3(0) 3
(
(1))) + 3 O (0)
2; (3 E2i + E1s
2,7,
(1)
(6))
(11)
(33)
24

---

Published as a conference paper at ICLR 2026
Note that
2-1 1
[-1
1-1 t-1
3 - 3
3
a
L
9 (1) (Z
Ze 0 2 TTr
Σ a II LODO
i=0
i=0
j=++1
II km
L (0) (3(0) - 3)
L6)
0 Z Ze B 0 z r avl!)
im0 jmit1
where i(0) := E [ LOD( Similar to equation 27
we take To == ==mxx [ C2). When
t I To. we have
| - 31 11+000
(34)
When To < S T, the error begins to shrink with i, so the bound equation 34 holds uniformly for all l = ,,..,, T. It remains to determine the bound for || ||. Note that since u ~VO0, >gT2).
we have with probability 1 1-
| X2 (vo+ VT log(T)) Vi ......TT T-
Case 1: t S To. In this case, we have
|500
01
f=
To 1
|
0=0 j=++1
To To
S do (v++ + + log(
|
1=0 j=++1
SATTo (vø+ (
where the last line follows from the fact that from Lemma D.9
1172-11 [ || can be bounded by constant, following
Case 2: >> To. We have
6-1 1-1
To 1-1
こ = Σ 1o
I
Σ
L
Σ
1
i= j=it1
j=it1
For any j 2 To. we have
| S kT(T)
< 1. Hence, we have
+ Σ
|000|| 5
L (
L000
:T
j=++1
To
To
I
Σ
J-
+=+==
To To
Σ
1 (
II
Lo 200
+
1
T
S AoZTo (vD+ + log(T))
+ Σ
k
(VD+ + V + log(TT
T=To
SAZTO (vp+ V + +log(T))
25

---

Published as a conference paper at ICLR 2026
So have the following uniform bound:
||3(0) - 31| - 1 AoTo (VD+ +
T2VT
1
(VD+ VT+ Vt I....,
n nVP2
where we ignore the error from
||,3 - 3|| as diminishes with n, according to Lemma D.7
Besides,
according to equation 25
we have
| 10 O 2
Then we have with probability 1 1-c'e for
for any t = 1, T. = I,...,n.
(1) n.2. 2,2,0/1 ( (3(0) - (3)
S o 7 + VT + +lgg()))))) 2
12VT
(VD V + VT+ 1
1+
n/P2
(ii) + ( 7 T (t))) 2 [
S (v7 + V + log(n)))2
(ini) = 1000 (+) 2, (3 E2i + +
S + log( (n] // VT).
where the last inequality follows from the term (gT 62: + +1;) is zero-mean sub-Gaussian with pa- rameter == vož||B1 + oo. Plug in (i)-(ii)) and equation 34 into equation 33
we have the
dominating term
(01f o (Vg+ / + log(n7)) (1+
(1
I+
T2VT
(Vr+ VT + 1og(7))
nv/2
In order to guarantee the no-clipping condition, we can take 7/2 such that
(1+ 72VT (VD+ / V log(()))
of (Vg+ V ++++++(+TT)
S 72-
nVP2
Solving for 72, we have
03( + V T + log(n:T))
72
(35)
T
(og(nT)
(VP+ + /T log(T))
n/P2
which is subject to the condition
(v + v7)² VT Vp2
(Vp+ (1++VT)) VT)
n ==
Ω
VT
Ω
(v vテ)
Vp2
where we ignore the Vlog(n(T)) term since it grows slower than any positive power of n.
E.2 PROOF OF LEMMA D.2
Proof. The first inequality chain follows directly from the standard concentration inequality for sub- Gaussian random matrices (see (Vershynin 2018). Theorem 4.6.1). The second inequality chain
follows from the fact that (Z) (x Z) for =1, 1,...,4.
26

---

Published as a conference paper at ICLR 2026
E.3 PROOF OF LEMMA D.3
Proof. We have the (i, k)-th entry of Z T E2 is given by
Ez' E2) = Σ 2,
the sub-exponential norm this term can bounded by
(Z E2) jk: llv1
Σ
Zi E2inlles S0z02/n.
Thus we have the tail bound for each (j)::):
P (1 E2) jk 12 7) S 2e saor
Taking the union bound over j = 1,... and k = 1,..., we have
P ( T E2 2 -) P | E2 E2llmax 2
T
S
2pqe
viq
Equivalently, with probability least e have
|Z E2ll < cgo=02//mpa (T log(2p)))
E.4 PROOF OF LEMMA D.4
Proof. From Lemma D.2 when 2 Cho (Vq vF)², with probability at least 2e- we have
Z Z
Amin
2 (1 - -0(7))²
Z
Amax
< (1+ (1+0(7))
where 8(r) (
When < 1) ([+d(T)) we can bound the spectral radius of
V
I " Z Z with probability at least 1 Te= n
p (( ! ZTz < (T = max {|- 1- (1 (1 - (1 <1,
1
where p(-) denotes the spectral radius of a matrix. If we define the event Ene(T) = {Z (I- 2z TTZZ) < (7)))), then conditional event Exa(T), have the following holds for each column = 1,2....,P..
N
" 2 71
Hi = N 0, 0,
I (I
" ZTZZZ
" Z TTZ
2(++1)
b
n
1=0
Σ2
where
Σ S ?
Σ
1
I
Zzzzz
2(t-1)
n
< 1 Σ (T)
1=0
27

---

Published as a conference paper at ICLR 2026
1f2 XP
5 (T)
standard result following Lemma with probability at least e=
(Laurent Massart 2000) gives the following bound holds
I
1 || &
tr(Ek)
2||Ex|1 (log(p) + r)
qlE/ا|l + 2|| (log(p) + +))
7
(Vq+ / (log(p) +
x (T)
Taking the union bound over each column h ,....,P. P. we have the following holds with probabil- ity at least 1 - E conditional on (
|
(VP4 + 2p (log(p) + r))
and
||e S (T
e
00)
+
(T) (VDq+ + 2p (log(p) + T)
V1
Finally, uncondition on (T) and take the union bound over the event Exe(T) gives the desired result.
E.5 PROOF OF LEMMA D.5
Proof. We have
M [[ z) -z Eg/
Z E2ll
(36)
0² Jiin (Z)
From Lemma D.2 we have when n 2 Cirs + vF)², with probability at least 1 2T we have
- (2) Amin (z 2 n - 8(T))
(37)
For the numerator, from Lemma D.3 we have with probability at least c
|z E2ll < coo.02y/npa (T log(2p4)).
(38)
Finally, plug in equation 37 and equation 38 into equation
36 have with probability at least
c00=02 02 v npp (T + log (2q))
c0 pq (T (2gg))
|
(1 1 5(T))
VT (1-18(7) 8(r))
E.6 PROOF OF LEMMA D.6
Proof. We decompose è + L. where & = (Z=Zz)- -1 Eg. We have
1 ( 4
Amiu (H) Amiu
T z 4) Z
Z Z
Amiu (
)amia ((0 + v T
T (e 1)
(39)
Zz
Z Z
Amin
( v)
28

---

Published as a conference paper at ICLR 2026
It remains give high probability bound for mii (Z) and o ( D. For the first term, from
Lemma D.2 we have when n 2 C 2 + vT),, with probability at least 2e we have
Z z
min
Z
Amin
(1 (1-)()))²²
(40)
where 8(7) (v vn
For the second term, we apply Werl's inquality:
min
- + v
mnin ( ||
(41)
From Lemma
D.5 we have with probability at least 3,-
C00 pd (T + log(2pg))
(42)
vn 6(T))
Note that the RHS of equation (pa(T + log(p4))²). Plug in equation 40 40equation 41equation into equation 39 we have:
should be greater than 0, which requires "
Amin (H) (1 8(T))² (amin (e) |
2 (1 8(T))} Omin (0) c00202 pq (T + log (2pg))
(43)
v (1 - 8(T))
Similarly, we have
1 (0 4)) ZZ 4
Amax
H Amax
Z
max
Amax (0 - ( v)
(44)
(1 8(T))² (||@|| |
||||| + C00 / pa (T + (ppg)
< (1 + 8(T))²
v (1 - -(()))
which completes the proof.
E.7
PROOF OF LEMMA D.7
Proof. We have
B B- 16-- 6 -
(X ' x -1 Y
(xTz(z Zz ZZz 2)-77 '%,6. 33
2Z ZZ
So that
||3 - 31 - (I( -|| X 2||l (Z 2) -1 1 T
E
(45)
From Lemma D.2 and Lemma we have the following bounds:
D.6 when 2 C1P4( T (lg )2, with probability at least
-M
(I 2) n
|| S 1.
(46)
Similar to equation
38 have with probability at least 1 - TT
Z E11 c002011 (T log(24) O (Vng (T log(g)))
(47)
29

---

Published as a conference paper at ICLR 2026
It remains to derive bound for |X Z||. We have
T z (
(20)
= E
where from Lemma D.2 we have with probability at least 2,
Z | - m11 + 0(1+)(7))3
and from equation 38 with probability at least -
IZ
E2ll c00202y/pp (r log(2p4)) O (Vrpy (T + log(pg)))
so we have with probability at least 3,
x ||| n1 |
@|| + co0,022 npq (T log(2p4)) O (n+ /rpg (T + log(pg)))
(48)
From equation 45
with equation 46equation 47 eequation
48
when
CiollVq + VF) with
probability least 1 4e
/nq (T log(4)) (n + / npg (r + log(pg)))
|| 311 x
n²
v (T + log(4))
qyP(T log(a))(( + log(pg))
VT
When 12 (pg(T log(p))))). the above expression can be further simplified
|/ B1 V + log(4))
(49)
Vn
which concludes the proof.
E.8 PROOF OF LEMMA D.8
Proof. We can decompose as:
r ZÔ3 Y =23 (20 + E2) El
ZâÍ Z03 Eg, E3
zÔğ Z03 + zeg Z03 EgB E1
=Z(6 )) B ze (8- 3) EgB E
and
Z = 2T 0 2) 3 z zo (3 (3-3) 3) - -T (E23+ + E1) | 0 || BI|. and Z (E₂ + E1) |. From Lemma D.2 we
(50)
It suffices to bound |Z Z]|.
have with probability least 2e
Z Z < n n + [(T))² Sn.
From Lemma D.5
we can take
Co0=022 pM (T + log (2pq)
[Vml(T log(pg))
6
e
0
/n 5(7))² 2
Vn
From Lemma D.7
| B 3 < / log(g))
30

---

Published as a conference paper at ICLR 2026
For the eπror Etotal
E2B 1,, note that Etotal, Ej= E2,6, E1, is zero-mean sub-
Gaussian with parameter ő := v 03 31 + of and hence the sub-exponential norm of Z Etotal can be bounded by
|| Z Peotal)lllly = Σ Z Etotal, 1l S 0zōVn
Thus we have the tail bound:
P (I(Z) Exoral )al 2) S 2e P0m
Taking the union bound over le 1........................
......... 9. we have
2 r) P Iz Etotail 2 [-)
P (1|Z Etotal
S 2ge coesayna
/q
Equivalently, with probability at least 1 - e
Iz' Erotail
coo,ō (r + log(22)) O (y'g (T + log(g)))
Plugging these bounds into equation 50 we have with probability at least 1 - 3e
I r|| < z (1 + + z Z @ + || Etotatl
IZ T Z|((|| + 66)6 + IZ Z || + | Exotor|l
$ 1 /p4 (T )
// + log(g))
+ /pq (r + log(p4)) + /nq (T + log(4))
n/ S /npa (T + log(p4))
Vn
Vn
E.9 PROOF OF LEMMA D.9
Proof. We have
L I
( Z ze
θ + 6 2 z ( - - "+ 6 |1
I
(1)
= I
+ 6 2 ( +
< 1 + a [ /||
(1e5
+ 1101)
n
$ 1+ (le 111)
where (0) (1)
é. Note that from Lemma D.4 with parameters choice equation 4 and sample
size condition equation 6 we have ||o || S 1, Vt 0, 1,.... [C2] - 1. So that there exists a
constant CL, such that || < CL, Vt = 0, 1.... [C2s 1, where Co is the upper bound of (n
in equation 22 Besides, when 0 < a < 2(())+2(7) from equation 14 we have [1 < 1, Vt
[C2].... To Therefore, we have
Tg-1
II [ 09
[Ca] $1. - c
==0
which concludes the proof.
31

---

Published as a conference paper at ICLR 2026
F ADDITIONAL DISCUSSIONS
F.1 PRIVACY FOR 3 ONLY
In Algorithm | the privacy parameter p with respect O ..... θ 3 ..... B However,
in some applications, may only care about the privacy of the major estimator ((1) ..... B(T). We note that in Algorithm [ maintaining the privacy guarantees. We have the following lemma:
one can modify the output to only include ( ,.... ( while still
Lemma F.1. For P1 E (0, oo) and X E [0, oo) Algorithm is p-zCDP for output ((1). B(T,
where p = P2
2f72 x²
Suppose that P1 oo, i.. we remove 3. the additive noise of the first stage. One can show that can get slightly tighter bound for equation|] 7 However, for any fixed P2. we observe that there is no improvement on the rate of convergence than Theorem 3.1
Consider the following algorithm:
Algorithm AP-22--GD-
1: Input: Data Z E RR X E Raxp, Y E R
2: Parameters: Clipping threshold 722 > noise scale Xe > 0, step sizes a, 17 > 0, number of iterations T, initial estimates g(0)) Opp (0) 0xxp
3: for t = 0, .
do
4: Draw u11) ~ ~0, (3Ip)
5: ( @ Σ (2 (+) x!_
6:
g((+1) = (()) +ht E CLIP [0(() 2; (z. (0))0)))0) v1)} + av
7: end for
8:
return ((),....,3777)
We have the following theorem:
Theorem F.1. For any fixed + E Roxp and 3 E R2, consider the Algorithm with step sizes satisfying
2
0 <<Λ 1 <
0< a < 27(7) 2(7)
(1 (1+
under Assumption
2 with parameters
2m
T
272
T
=co (VT + V T + log(nT))
A
X2
m1
pi
P2
(V7 + vF)
n 2 c1 max pT(T + log(pg))
vP2
for any fixed with probability 1 =2e T. we have
[| - -131 S k(T) V 3
Vpg(T + log(pg))
VT
n
Vn
where the definitions of x()), (T), (T) and ((T) are the same as in Theorem 3.1
Proof. The proof follows from similar approach as in the proof of Theorem
3.1
However, in equa-
tion 11 we can simplify as follows:
(++1)
(I 7Z TTzZ
(0)
%
32

---

Published as a conference paper at ICLR 2026
So in equation 18 take
E = (T)
S
(T)
and in equation 19
||
- | S
max 0gAST
Thus, to satisfy condition equation 20 we only need
To S E,
where E v |
7(7)
|||. Comparing this with equation 21 we can that there
2(1+)())
no constraint T. We only need to take
To 2 to(n),
where lo(n) is defined in equation 22 equation 27 we have
We still take partition point To max [, C2). similar to
||e
(Ta)
S111+ (VD
Further, from equation 16 we have
|1e (2) S kK((T) T to le +E(+++))+ + VPg(T + log(pg))
(10)
(1+ + A2 (Vp VF)
Vn
S (ma(T) (1 + A2 (VD + v=)) + (T) + VPq(T + log(pg))
+ A2 (Vp + VT)
Vn
S rnØ(T) + ke(T)² + p + log(pg))
+ (VD+
Vn
(51)
where d2-
213 n
V _r_ and 72 = =02 (va+ V + +lg(nT)) 2
T
Plug in X2 into equation 51 we have
R(T)
VT
VPq(T + log(pT)
|l 3
(T) || S <T(T) + -k
P2
(52)
(a1)
(si6)
(io)
Comparing equation 52 with equation 29 we observe that the error term in (ii) is reduced due the
absence of noise in T update. When On)). this improvement is insignificant as the order of
the bound equation 52 is dominated by (iv). However, in Theorem F. since there is no restriction
on T, equation 52 holds for all T.
We conduct experiments to compare the performance Algorithm I and Algorithm 3 under the
same setup as in Section 4 We fix 1000 and p q 5. For Algorithm [ we set
and vary P2 E {0.1, 1, 10,, while running both algorithms for a range of iterations. The results We observe that when T Onn), the two algorithms exhibit comparable diverges, whereas 3
shown in Figure
performance. However, when T grows larger, to maintain stable error trajectory.
33

---

Published as a conference paper at ICLR 2026
Algorithm 1 Emer v (n-1000 p-5)
Algorithi Emoo Tin-1000. 1000000000.....
R-1 Ev.0.1
p--d.1
p-1
pmmp
20
2515 (osefino)
-- 2515 Oasecieel
0.-
500
2000
1020
2320
500
1000
1850
2002
2320
Bnration:
feestios:
(a)
(b)
Figure 6: Comparison of Algorithm and Algorithm We fix n --- and
vary P2 {0.1, 1, 10). (a) Error curve for Algorithm where we set f1 1. (b) Error curve for
Algorithm 3 All the curves are averaged over 100 runs, with vertical bars representing the standard errors.
F.2 COMPARISON TO FRIENDLYCORE APPROACH
In this section, we provide brief comparison between our two-stage gradient perturbation ap- proach and computationally friendly approach. Tsfadia et al. (2022) proposes general DP meta- framework for aggregation tasks (e.g.. averaging, clustering, covariance estimation) on data metric space. The key idea is: Given dataset D = (XI..... x.,) in metric space and "friend- ship" predicate fx, y) that encodes when two points are close well-behaved, FriendlyCore is DP procedure that extracts subset C' C D (the "core") with two properties:
Structural niceness: is f-friendly (e.g.. all points in lie a ball of radius r, or satisfy a separation condition useful for clustering). Outliers that violate the predicate removed.
Stability and DP: For neighboring datasets D, D', the cores C, C' differ only small number of points, and FriendlyCore itself is (e, dDP or p-zCDP. This lets you plug into any friendly-instance DP algorithm without ro-ng worst-case sensitivity analysis.
Section Tsfadia et al. 2022 shows how to use this framework for private averaging, clustering, and covariance estimation. For averaging. Algorithm 5.1 FC Avg does:
Split the privacy budget as P1 = 0.1p, = 0.9p.
Run FriendlyCore on with a predicate that enforces an effective diameter r (all but a few outliers lie in ball of radius r
On the core C, run FriendlyAvg. which is essentially Gaussian- mean estima- tor tuned for zCDP
Algorithm 5.1 from Tsfadia al. (022) can be used building block to make DP ver- sion this 2SLS analysis: The 2SLS estimator depends on sample means of sufficient statis- tics: 1Z Z, 1z X, iz Y. Stack and vectorize these matrices into vector in Rd with q² pq q Og) Each data point contributes vector of this form; call these contributions x; Under the lab-Gaussian design, each &; has bounded effective diameter
r r= +(Ve+ VT)
with high probability. Using that Algorithm 5.1 (FC Avg) gives p-zCDP estimate of the mean of the sufficient-statistie vector with error
r d
=o
-0
vd++
VF
= =041 Vd dr ntPP
=
34

---

Published as a conference paper at ICLR 2026
Lemma D.7 proof shows that 3 is smooth function of those sample covariances. The final timate PrC is then post-processing step that applies the usual 2SLS formula these privatized moments. If we replace the non-private moment estimates in Lemma D.7 by the FC_Avg priva- tized moments, the Lipschitz dependence of 3 on the moments converts the FC_Avg error into an additional term the error bound, scaling like at the order of L +oy= where the Lipschitz constant (see Lemma F.2) Hence, the eroor bound for FriendlyCore-basee DP 2SLS estimator would be the combination of the non-private rate from Lemma D.7 plus this additional term. In particular,
ny/p
B11 =0 +OvT -0L nVD
yPu(T log(pg))
|18 B11 & 118 311 11-11--900
VTi
Remark F.1. Comparing this bound with our bound in Theorem similar. At the same time, the FriendlyCord CorndlyCore-baed estimator reflects different set of algorithmic and statistical trade-offs from our DP-2S-GD method:
3.1 we see that the orders are
Black-box generality vs. algorithm-award -aware design. FriendlyCore offers a highly general subsample-an aggregate framework that applies to broad class of moment-based estimators, including 2SLS, by treating them as black-box functions of empirical moments. contrast, DP-2S-GD directly privatizes the two-stage gradient procedure itself. This algorithm--aware approach enables us to analyze how privacy noise propagates through the optimization dynamics and obtain an explicit privacy- iteration trade-off (e.g., the "too many itera- tions hurt" behavior in Figure 2), which does not emerge in one-shot subsample-aggrees aggregate pipelines.
Subsample-and agg-ageeeaa vs. full-data iterative updates. FriendlyCore relies on re- peated subsampling to identify stable "core" before applying the estimator on that core, which provides robustness and generality but increases computational cost and effectively reduces the sample size available to each subsample. DP-2S-GB GD uses all samples at every iteration with per-sample gradient clipping and simple zCDP accountant, making it at- tractive in large-scale, iterative, streaming settings where repeated subsampling may be impractical.
Lemma F.2. Let s == vec Z x TTY),
n n x ). and ((s) denotes the mapping from BUSLS- There exists constant L > 0 such that for any two sets of moments s), S2, we have
[1((s)) - B(s2)] & L||s| 82ll.
Proof. Let Σ.; - 2T moments and define the "moment vector"
Σ.r 1ZT
Dzy 12 Y denote the empirical second
(E.., Σ.n. Σ Ezy)
From these moments we form the usual 2SLS normal equations
(s)) h(s),
where := P,X, h(s) = X.Y, : P===Z(Z -) Hence,
G(s) = Σg E Egn
h(s) = E.: E.
with Ex, ET Thus the 2SLS estimator can be written
(s)) G(s) -h(s).
Consider two sets of moments $1, 82 with corresponding
G, = G(s;), h = h(s:),
B = :=s,)( = -G-
11=1,2).
We have
B Bg = - - G h2
= = h2) + (G G h22
35

---

Published as a conference paper at ICLR 2026
= G h2) +
GT
G. G, h2
where in the last equality we used the identity
G
Taking norms and using submuliiplicatiiity,
|| - 32 - G G [|| h2l + | GG - G |
|22||
(53)
Assume (as in Assumption that the population Gram matrix is well conditioned, so that high-probability event
min (G.) 2 Ao 0 |G S A i= 1,2,
and that the moments are uniformly bounded so that ||h2|| < Cr. Here the specific formula of λ could be referred Lemma D.6 Moreover, G(s) and h(ss) are smooth (in fact, rational) functions
of the entries of (Ee., Ezzi en and in neighbourhood of the true moments there exist constants Cc. C₁ such that
G2 Gill Cclls2 sill.
Ib2 h1 S Chl(s2 S ||-
Plugging these bounds into equation 53 yields
1 Cnllsi s2ll
1131 321l <
CoColIs: sall L[[s) -82/1
Ao
18
where
Ch
CGCh
= Ao
+
X
Hence the 2SLS map 3 + (s) is Lipschitz in the sample moments:
[13(s;) B(82)] S L|[s] 82 ||-
G ADDITIONAL EXPERIMENTS
G.1 TUNING STEP SIZE
In this section, empirically examine how the step sizes and r affect the convergence of Algo- rithm T Using the same setup as Section 4.1 we fix n = 2000 and = = r 5, and run vary
In each plot, admissible range given by equation 3 while fixing the other step size at a sub-optimal level (close to its upper bound). The results, shown Figure 7 indicate that long as v and lie within the theo- retically justified region, the convergence behavior is fairly insensitive to the exact step-size choice. As noted in Remark 3.2 our theoretical upper bound for a is slightly conservative due the need control the randomness introduced by the first-stage estimates (t)
Algorithm
I for T = 20 iterations, with A1 P2
of 7),
its
36

---

Published as a conference paper at ICLR 2026
Algorithm 1 error vs eta (p=5.qm5)
Algorithm 1 error vs alpha (p=5, 5, g=5)
0.200
Algorithm 1 2SL5 baseline
Algorithm
0.175
25LS baseline
0.8
0.150
1mm -Pruel
0.6
0.4
0.2
0.025
0.000
0.5
1.0 stepsize n
1.5
0.005
0.010 0.015 0.020 0.025 0.030 0.035
stepsize o
(a)
(b)
a. Mmax and Ommx are given by equation 3 The (approximate) optimal Nappox and Opppox are calculated
Figure 7: Convergence behavior under different step sizes a7.a. The (theoretical) upper bounds
according to equation 8 (a) Varying v while fixing = Omax. (b) Varying while fixing
0.9%/max- All the curves are averaged over 100 runs, with vertical bars representing the standard errors.
G.2 EFFECT OF CLIPPING THRESHOLD
In this section, we empirically examine how the clipping thresholds ? and ?22 influence the utility of Algorithm| [ Using the same setup as in Section[4.] we fix = 2000 and p q = r = 5, and
run Algorithm| 1 for T = 20 iterations under privacy budgets f) = P2 = 5. For simplicity, we set 71 = 72 y and vary > over the range [1, 1000). The results are reported in Figure g
We observe that when y set too small, the per-sample gradients are frequently clipped, causing the updates to be severely distorted and resulting in larger estimation error. As increases, clipping becomes less frequent and the estimation error decreases. However, once y exceeds a certain level, the sensitivity of the gradients grows, which requires injecting larger noise to satisfy the target privacy budget. This increased noise leads to larger fluctuations in the final estimates. Consequently, the most effective choice of y is the smallest value that ensures gradient clipping does not occur with high probability.
Algorithmm Error 2000, T-20, S,
2545 (auocinec) + Algorthrm 2
2.0
1.5
35
Uiganng
Figure 8: Effect of clipping threshold 7 on the utility of Algorithm We fix n = 2000, = q = 5, T = 20, P1 = P2 5. and set ?1 = 72 7. The error curve is averaged over 100 runs, with vertical bars representing the standard errors.
G.3 CONVERGENCE RATE COMPARISON
In this section, empirically compare the convergence rate of 2S-GD (Algorithm 2 and the
standard 2SLS estimator. The experiment setup is exactly the same as in Section 4.1 We set
p q 20, and vary n from 500 to 5000. For the 25-GD estimator, we run 7 100
37

---

Published as a conference paper at ICLR 2026
iterations that it converges sufficiently. The results shown in Figure We observe that the convergence rate of 28 GDD is slower than that 2SLS.
25LS
0.7
-0- 63-
0.5
Figure 9: Comparison of the convergence rates 2S-GD and 2SLS. The error curves (| 3||
(for 2S-GD) and ||@ 31l (for 2SLS) are averaged over 100 runs, with vertical bars representing the standard errors.
G.4 ADDITIONAL EXPERIMENTS ANGRIST DATASET
We provide additional experimental results on the Angrist dataset with different privacy parameters P1, P2- We consider two settings of privacy parameters: (i) P1 0.1, 0.1; (ii) 10, P2 The results are shown in Figures and [T] We observe that when Pl. P2 are small, the estimates of ((2) have larger variance. When P1 P2 are larger, the estimates of ( more concentrated around the expected value. In both settings, the estimates of (3()) converge in expectation within = 20 iterations.
Average f path
Distribution of final estimates across 1000 runs
Averoge g
25L5
#PP1 across runs
Coefficient estimate
2.5
7.5
12.5
15.0
Iteration
Average 9l path
0.04
Average Q!!
0.03
Ele across
0.01
0.0
2.5
5.0
7.5
10.0 Iteration
12.5
15.0
17.5
8m
(a)
(b)
Figure 10: Results on the Angrist dataset with 7 = 20, = 0.1, P2 = 0.1. (a) Boxplot of estimated
((T), over 1000 runs. (b) Learning paths of parameters (t)), (t)) over 1000 runs. The shaded area represents the standard error.
38

---

Published as a conference paper at ICLR 2026
Average f! path
Distribution of final estimates acress 1000 runs
Average gra
Buss
-2
Coefiiient estimate
2.5
15.0
Iterration
Average path
-4-
Average 81U
-3-
achoss runs
2515
OLS
2.5
7.5 10.0
15.0
37.5
gm
Iteration
(a)
(b)
Figure 11: Results on the Angrist dataset with T = 20, =00 P2 10. (a) Boxplot of estimated
( over 1000 runs (b) Learning paths of parameters , ( over 1000 runs. The shaded area represents the standard error.
G.5 EXPERIMENTS ON CARD DATASET
The Card dataset (Card] 1993) is widely used empirical dataset in labor economies for studying the causal effect of education on earnings. In this study, the endogenous regressor individuals' years of schooling (educ), and the outcome variable is log earnings (Iwage). There are several instru- ments available, most notably the college-proximity indicators (nearc2 and nearc4), which capture whether an individual grew up near two-year four-year college. Additional instruments include parental Iotucation-fatbaee 's and mother's years of schooling (Tathedue and motheduc)-wiie provide further exogenous variation educational attainment.
There are 2191 samples in total. We consider the following covariates: Z = =[nearc2, nearc4, fathe- duc, motheduc], X =[educ], Y [Ilwge)]. We standardize each column of to have zero mean and unit variance. We run Algorithm | with privacy parameters P1, P2 E {0.1, 1, 10), and number of iterations 7 = 15. We report the boxplot of final estimates and the learning path for 300) The results are shown in Figure 12 We observe that as P2,22 increase, the estimates of 3(2) become more concentrated. In all settings, the estimates of (()) converge in expectation within 10 iterations.
39

---

Published as a conference paper at ICLR 2026
bution that ietraate srmes
Siertaution estimnns scross 1000
Dieributton fra scros nre
3.1
175
6:03
2885
3.55
-0.4%
-1.5
-2.5
Avarage Maacm
Average p peth
Roo
0:33
Avo
0.11
2.11
030
8:0
033
2.55
0.00
12
11
12
(a)
(b)
(c)
Figure 12: Experimental results on the Card dataset with T 15. Each column shows the boxplot
of final estimates (top) and learning path (bottom). (a)p1 = P2 0.1. (b)p1 = 1. (c)p1 =
P2 10. The shaded area in the learning path represents the standard error.
40


Reviews:
[{"review_id": "8iSICqmMG6", "reviewer": "Reviewer_hM7v", "summary": "The paper proposes a differentially private estimator for (a specific formulation of) instrumental-variable regression. The paper suggests noisy gradient descent, in which the key parameters $\\Theta$ (a matrix) and $\\beta$ (a vector) are updated at each round using a noisy gradient measurement. THe paper gives natural conditions under which this algorithm provably converges (and also provides bounds on its error in estimating the vector $\\beta$).\n\nThe algorithm's convergence is also evaluated empirically on synthetic and real data.", "questions": "* Privacy notions: Remark 3.8 states that, when $\\Theta^{(t)}$ is not released, \"setting $\\rho=\\infty$ implies that no noise $\\Xi^{(t)}$ needs to be injected in the first state, and we can simply return $\\{\\beta^{(t)}\\}$ under privacy budget $\\rho_2$.\" I don't see why that's true---the hidden $\\\\Theta^{(t)}$ values encode information about the sensitive data and propagate it throughout the computation. At the very least the statement deserves a more careful formulation and explanation. (Also, why would $\\beta$ be useful without $\\Theta$? The latter seems necessary to interpret the former as a predictor of $y$)\n\n* What are the relevant facts about the standard 2S-LS estimator for this paper? It is mentionedand compared to the 2S-GD estimator in Remark 3.7, but the algorithm and its convergence rate are not precisely described, which makes the comparison hard to follow.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper addresses a widely-used statistical method \n* The paper appears technically sound. Though I did not check the proofs carefully, the authors present and discuss their results clearly, and the results and proofs seem plausible.", "weaknesses": "* The final bounds were hard to interpret, partly because they necessarily involves quite a few different parameters. It would be helpful to provide some baselines, both in the form of nonprivate methods, and in the form of alternate approaches to designing DP algorithms. For example, a few of the questions I couldn't answer as a reader were:\n\n    * What level of noise is acceptable? That is, how are the results of DP IVaR supposed to be used, and when does the noisy version meet the needs of application? Even if the answer is context dependent, providing one context in which the overall usefulness of the answer can be evaluated would be helpful. \n\n    * How does the proposed method compare to a more straightforward perturbation of the sufficient statistics for the model (presumably the covariance matrix of the concatenation $(z,x,y)$). \n    \n    * When is DP IVaR more useful than DP OLS on its own? As far as I know, IVaR and OLS are normally used in tandem. However, presumably the noise levels have to be low enough to for them to be meaningfully compared. When is that possible? In what parameter ranges do the results of the paper imply the validity of such a comparison?  \n\n* It would be good to compare the bounds in this paper to those implied by other work on DP nonconvex optimization.", "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": "", "extra_scores": {}}, {"review_id": "JNXcGiqxsP", "reviewer": "Reviewer_sNPP", "summary": "This paper studies differentially private instrumental variables (IV) regression and proposes **DP-2S-GD**, a two-stage gradient-descent algorithm that enforces Renyi differential privacy through clipping and Gaussian noise injection (in a usual DP-GD style but with two different sets of parameters). The method provides end-to-end privacy guarantees for the classical two-stage least squares (2SLS) setting for IVaR. The authors prove a non-asymptotic convergence bound that decomposes optimization error, sampling error, and noise due to privacy. They also characterize a privacy-iteration trade-off and show how privacy budgets affect convergence behavior. Experiments on synthetic data and the Angrist–Evans dataset support the theoretical predictions, demonstrating that the estimator remains stable and competitive under useful privacy levels.", "questions": "1. Can the authors report the privacy levels used in all experiments in terms of the standard $(\\epsilon, \\delta)$-DP, in addition to $\\rho$-zCDP, so that readers can directly compare privacy strengths with prior work?  \n\n2. Can the step sizes be tuned or derived in a way that yields an explicit non-asymptotic convergence guarantee depending only on problem parameters (e.g., Lipschitz constants or curvature), rather than through broad stability bounds?  \n\n3. Would it be possible to consider a stochastic variant of the algorithm, where each optimization step uses a new sample so that $T$ and $n$ are coupled? This might lead to a simpler and more interpretable result, since the trade-offs between optimization and generalization would coincide. It could also remove the “overfitting” behavior seen in Figure 2, where the error decreases and then rises as $T$ grows. This is not a major issue, but it could better bring other aspects such as the utility-privacy trade-off on the centerstage.  \n\n4. The motivation for the IVaR setup remains somewhat unclear. Can the authors give concrete examples of real situations where one can actually observe or construct the full dataset $(z, x, y)$ required for the two-stage regression? In settings where the true causal graph is unknown, how can one justify the validity of Assumptions 1 and 2? Some discussion or examples of practical data sources would help clarify this premise.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper fills a clear gap by proposing a differentially private version of instrumental variable regression. The formulation is simple and technically consistent, combining a two-stage gradient procedure with zCDP-based privacy guarantees. The analysis provides non-asymptotic convergence bounds for $\\beta$ (the regression parameter of interest) that decompose statistical, optimization, and privacy errors, making the results partially interpretable. The privacy proof is correct and applies zCDP effectively to handle iterative updates. The experiments, though limited, support the theoretical claims and clearly show the predicted privacy–accuracy and overfitting behavior (from Figure 2). The writing is clear, notation consistent, and the argument proceeds logically from setup to results.", "weaknesses": "**Untuned step-sizes and incomplete convergence analysis (major weakness)**\n\nThe paper provides only upper bounds for the step sizes \\(\\eta\\) and \\(\\alpha\\) ). These conditions ensure convergence in principle but leave the question of the optimal step-sizes open. As a result, the convergence theorem lacks interpretability: there are too many definitions, and not all of them depend on just problem dependent parameters. This limitation gives the impression that the analysis has not been fully worked out. A sharper result would express convergence explicitly in terms of well-defined problem constants and privacy noise scales. Since this is the main contribution of the paper, and the algorithm itself is not very surprising, I am inclined to reject the paper in its current form. I would like to see a fully worked out, non-asymptotic convergence guarantee before I can recommed acceptance. If it is hard to tune all the parameters for a high probability guarantee, can the authors atleast provide one for an in expectation result? \n\n**Limited baselines**\n\nThe experiments lack comparison with simple private 2SLS variants, such as perturbing sufficient statistics or applying output perturbation (which were indeed discussed in the paper while providing a survey of related methods). Including such baselines would help quantify the benefit of the proposed algorithm beyond intuitive reasoning.\n\n**Non-private performance gap**\n\nEven without privacy, the estimator remains slower than classical 2SLS, introducing an additional factor in the rate. The paper acknowledges this but does not explain what causes this.", "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": "", "extra_scores": {}}, {"review_id": "oZdo8fg8t3", "reviewer": "Reviewer_Gj3i", "summary": "This submission presents a differentially private algorithm for instrumental variable regression, a central tool in causal inference. The standard non-private algorithm for this task involves solving two least-squares problems. The algorithm presented here is a two-stage version of DP gradient descent. They give a theoretical analysis of the algorithm's convergence (under the assumption that the data arise from a well-specified model with subgaussian noise). For appropriate hyperparameter settings, as we add get more samples the error from privacy becomes lower than the error from sampling.\n\nThey also present experiments on synthetic and real data, and the method seems quite practical.", "questions": "Can you formally combine Lemma D.7 with the FriendlyCore approach and compare the resulting theorem with your Theorem 3.1?\n\nCan you briefly describe what (if any) new technical challenges your main convergence proof must overcome?\n\nCan you fix the following minor issues with your background discussion?\n- $(\\varepsilon,\\delta)$-DP algorithms satisfy basic composition, where the privacy terms accumulate linearly, but also *advanced* composition [see 2]. Here the asymptotics match those of zCDP, but the latter is usually more practical.\n- You mention that gradient-perturbation methods can avoid spectrum-based blowups, but (i) private first-order methods still suffer on ill-conditioned data [3,4] and (ii) there are techniques for privately estimating $X^T X$ that avoid these blow-ups [5,6], although when used within a sufficient-statistics approach for regression they may incur higher sample complexity than necessary [see 7 for discussion].\n\n[2] https://dpcourse.github.io/2025-spring/lecnotes-web/DP-S25-notes-lec-10-adv-composition.pdf\n\n[3] https://arxiv.org/abs/2207.04686\n\n[4] https://arxiv.org/abs/2301.13273\n\n[5] https://arxiv.org/abs/1805.00216\n\n[6] https://arxiv.org/abs/2301.12250\n\n[7] https://arxiv.org/abs/2404.15409", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Instrumental variable regression is an important task and extremely worthy of study under privacy. While there is a lot of work on private ordinary least squares, I'm surprised there's none on this topic.\n\nThe method presented here is a clear contribution, both theoretically and practically. I was unable to verify the proofs, but the results are very plausible.", "weaknesses": "The main convergence proof is quite long and, to my taste, comes with insufficient exposition. It was hard for me to understand which parts of the analysis are new. \n\nThere are no approaches that explicitly tackle DP IVaR, but there are well-known techniques that directly yield results. In particular, the \"subsample and aggregate\" framework can usually make use of any non-private estimator with meaningful concentration guarantees. For the task here, combining the Algorithm 5.1 of \"FriendlyCore\" [1] with the submission's Lemma D.7 yields a zCDP estimator with $\\ell_2$ error roughly $\\sqrt{pq/n}$, I think. This matches the non-private error and, in some regimes, might be better than Theorem 3.1's $\\sqrt{p}q^{3/2}/n$ term.\n\n[1] https://arxiv.org/abs/2110.10132", "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": "", "extra_scores": {}}, {"review_id": "OzNNTP5v4W", "reviewer": "Reviewer_Cx28", "summary": "This paper addresses the problem of instrumental variable (IV) regression under differential privacy constraints. The authors propose  a noisy two-stage gradient-descent algorithm that injects calibrated Gaussian noise and uses per-sample gradient clipping to obtain $\\rho$-zero-concentrated differential privacy (zCDP). They also provide a formal privacy accountant and derive finite-sample convergence bounds that explicitly characterize the trade-offs among privacy budgets $(\\rho_1,\\rho_2)$, sample size $n$, problem dimensions $p,q$, and the number of iterations $T$. The authors validate the theory with synthetic simulations and a real-data application.", "questions": "1. Do you see a path to extend your framework and privacy analysis to nonlinear IV methods? What are the main technical obstacles?\n2. Can you provide more intuition about the source of the extra $\\sqrt{p}$ factor compared to 2SLS, and whether an improved analysis or algorithmic modification could remove or reduce this gap?\n3. In the utility analysis, it seems that the authors do not explicitly incorporate gradient clipping into the iterative update equations. The clipping thresholds only appear in the gradient sensitivity, which determines the noise scale. Could the authors explicitly include the gradient clipping step in the iteration and provide a corresponding convergence analysis? Furthermore, how should practitioners choose the clipping thresholds in practice, and how sensitive is the empirical performance to these choices?\n4. How should the step sizes be selected in practice? Have the authors conducted any sensitivity analysis to evaluate how the choice of step sizes affects the empirical performance and convergence?\n5. The utility analysis requires a condition on $T$ to keep noise scales manageable. In practice, does early stopping based on a private validation objective suffice? Could you provide an algorithmic prescription to choose $T$ that balances convergence and privacy noise?\n6. In the real data analysis, both the endogenous dimension $p$ and the instrumental dimension $q$ are equal to 1. Are there any real datasets with higher-dimensional instruments or regressors where the proposed method could be demonstrated? It would be interesting to see how the algorithm performs in such multi-dimensional settings.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper addresses a compelling problem that is likely to interest the statistics and econometric community, particularly those focused on IV regression and privacy.\n2. This paper gives a clean privacy accountant and a detailed non-asymptotic utility bound.\n3. This paper is well written and clearly structured.", "weaknesses": "1. The method and proofs are limited to the linear IV model. It may be more interesting to consider nonlinear IV or machine learning-based IV methods. \n2. Even under the non-private setting, the error rate has an additional $\\sqrt{p}$ factor compared to that of the z2SLS estimator. This worsened dimension dependence could be limiting in moderate-to-high-dimensional problems.\n3. The necessity of privacy protection in IV method should be more clarified, it is more likely a combination of two methods in the present version.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)