Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data
Authors: Xuxing Chen
Abhishek Roy
Yifan Hu
Krishna Balasubramanian
Venue: NeurIPS 2024 poster (2024)
Keywords: instrumental variable regression
stochastic gradient descent
stochastic approximation
2SLS
Primary area: causal_inference
TL;DR: We propose the first stochastic approximation algorithm for instrumental variable regression with streaming data and provide analysis.

Abstract: We develop and analyze algorithms for instrumental variable regression by viewing the problem as a conditional stochastic optimization problem. In the context of least-squares instrumental variable regression, our algorithms neither require matrix inversions nor mini-batches thereby providing a fully online approach for performing instrumental variable regression with streaming data. When the true model is linear, we derive rates of convergence in expectation, that are of order $\mathcal{O}(\log T/T)$ and $\mathcal{O}(1/T^{1-\epsilon})$ for any $\epsilon>0$, respectively under the availability of two-sample and one-sample oracles respectively. Importantly, under the availability of the two-sample oracle, the aforementioned rate is actually agnostic to the relationship between confounder and the instrumental variable demonstrating the flexibility of the proposed approach in alleviating the need for explicit model assumptions required in recent works based on reformulating the problem as min-max optimization problems. Experimental validation is provided to demonstrate the advantages of the proposed algorithms over classical approaches like the 2SLS method.

Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data
Xuxing Chen
Abhishek Roy*
Department of Mathematics University Californi,, Davis xuxchen@ucdavis. edu
Halıooğlu Data Science Institute University of California, San Diego
a2roy@ucsd. edu
Yifan Hu
Krishnakumar Balasubramanian
College of Management, EPFL Department of Computer Science, ETH Zurich yifan. hu@epfl.cc.m
Department of Statistics University of California, Davis kbal aualavisssiss. edu
Abstract
We develop and analyze algorithms for instrumental variable regression by viewing the problem conditional stochastic optimization problem. In the context of least-squares instrumental variable regression, our algorithms neither require matrix inversions mini-batches and provides fully online approach for performing instrumental variable regression with streaming data. When the true model linear, derive rates of convergence in expectation, that of order O (log T (T)) and O(1/T1-9) for any > 0, respectively under the availability of two-sample and one-sample oracles, where T is the number of iterations. Importantly, under the availability of the two-sample oracle, our procedure avoids explicitly modeling and estimating the relationship between the independent and the instrumental variables, demonstrating the benefit of the proposed approach over recent works based reformulating the problem as minimax optimization problems. Numerical experiments are provided to corroborate the theoretical results.
Introduction
Instrumental variable analysis is widely used in fields like econometrics, health care [TM17], social science [Bol12], and online advertisement to estimate the causal effect of a random variable, X, outcome variable, Y, when unobservable confounder influences both. By identifying instrumental variable correlated with the variable X but unrelated to the confounders, researchers isolate the exogenous variation in X and estimate causal relationship between X and Y. In the context of regression, Instrumental Variable Regression (IVaR) addresses endogeneity issues when independent variable is correlated with the error term in the regression model, leveraging an instrument variable such that independent of X Z. In this paper, we focus on the following statistical model:
= go- (X)+ with X = hy (Z)
where X dh and ( are correlated and 62 a centered unobserved noise (independent of Z E IRd)), leading to confounding in the model between X and Y E RR. Here and 62 are dependent, and 8" and y" are true parameters for the respective function g and h. Our goal to design efficient algorithms that recovers 8" from the data.
FXC and AR contributed equally this work.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Traditionally, IVaR algorithms are based on two-stage estimation procedures, where we first regress Z and X to obtain an estimator X, and then regress X and Y, with the essence that X is independent of Y, and thus eliminating the aforementioned endogeneity of the unknown confounder. A vast literature has devoted to understanding the two-stage approaches [HH05, DFFRII, HLLBT17], with the parametric two-stage least-squares (2SLS) procedure being the most canonical one [A195]. The main drawback of this approach is that the second-stage -tage regression problem is affected by the estimation error from the regression problem corresponding to first stage. In fact, [AP09] call the first stage regression as "forbidden regression", due to the concerns in estimating nuisance parameter.
Considering the squared loss function, [MMLR20) 220 formulate the IVaR problem as a conditional stochastic optimization problem [HZCH20]:
min F(g) := Eyzly Ex(zlo(X))) GEG
However, [MMLR20] did not solve problem (2) efficiently, and resort to reformulating (2) further as minimax optimization problem. Indeed, they mention explicitly in their work that "it remains cumbersome to solve (2) directly because of the inner expectation". " Then, they leverage the Fenchel conjugate of the squared loss, leading a minimax optimization with maximization over continuous functional space. Following [DHP+ 17], [MMLR20] propose to use reproducing kernel Hilbert space (RKHS) handle the maximization over continuous functional space. See also [LS18, BKS19, DLMS20, LCY+200 BKM 23] for similar minimax approaches. The issue with such an approach is that approximating the dual variable via maximization over continuous functional space inevitably introduces approximation error. Hence, although there is no explicit nuisance parameter estimation step like in the two-stage approach, there an implicit one, which makes the minimax approach less appealing as an alternate to the two-stage procedures.
In this work, contrary to the claim made in [MMLR20] that problem (2) is cumbersome to solve, we design and analyze efficient streaming algorithms to directly solve the conditional stochastic optimization problem in (2). Direct application of methods from [HZCH20] for solving (2) is possible, yet their approach utilizes nested sampling, i.e., for each sample of Z. [HZCH20) generate a batch of samples of X from P(X[Z), to reduce the bias in estimating the composition of non- linear loss function with conditional expectations. Thus their methods are not suitable for the streaming setting that we are interested in. Considering (2), we first parameterize the function class
G := {g(0; X) 0 E Rd Now, defining Fg))= = F(0), we observe that the gradient (()) admits the following form
FF) = Ez (Ex x)] - Vo) X)].
(3)
which implies that one does not need the nested sampling technique to reduce the bias. However, the presence of product of two conditional expectations Æ (9; X)] still causes significant challenges in developing stochastic estimators of the above gradient in the streaming setting. In this work, we overcome this challenge and develop two algorithms that are applicable to the streaming data setting avoiding the need for generating batches of samples of X from X))
Contributions. We make the following contributions in this work.
Two-sample oracles: Our first algorithm leverages the observation that if we have access to a two-sample oracle that outputs two samples X and X' that are independent conditioned on the instrument Z, we can immediately construct an unbiased stochastic gradient estimator of the gradient in (3). Based on this crucial observation, Stochastic Gradient IVaR (TOSG-IVaR) method (Algorithm 1) that avoids explicitly having to estimate model the relationship between Z and X thereby overcoming the "forbidden regression" problem.. Under standard statistical model assumptions, for the case when g is a linear model, we establish rates of convergence of order O (log T/T) for the proposed method, where T is the overall number of iterations; see Theorem 1.
propose the Two-Sample One-stage
One-sample oracles: In the case when we do not have the aforementioned two-sample oracle, we estimate the stochastic gradient in (3) by using the streaming data to estimate one of the conditional expectations, and the corresponding prediction to estimate the other, resulting in the One-Sample Two-stage Stochastic Grudient IVaR (OTSG-IVaR) method (Algorithm 2). Assuming further that the X depends linearly on the instrument Z, we establish a rate of convergence of order (11/Tl=1), for any 0; see Theorem 2.

---

1.1 Literature Review
IVaR analysis. Instrumental variable analysis has a long history, starting from the early works by [Wri28] and [Rei45]. Several works considered the aforementioned two-stage procedure for IVaR; a summary could be found in the work by [AP09]. Nonparametric approaches based on wavelets, splines, reproducing kernels and deep neural networks could be found, for example, in the works by [HLLBT17, SSG19, BKS19, MMLR20, MZG+21, 21, XCS+21, ZGG+ PSF24). Another popular approach for IVaR is via Generalized Method of Moments (GMM); see, for example, [CP12, BKS19, DLMS20J for an overview. Such approaches essentially reformulate the problem minimax problem and hence suffer from the aforementioned "forbidden regression" problem.
Identifiability conditions for IVaR. Several works in the literature have also focused on establishing the identifiability conditions for IVaR in the parametric and the nonparametric setting. Regardless of the procedure used, they are invariably based on certain source conditions motivated by the inverse problems literature (see, for example, [CFR07, CR11, BKM BKM+23]) 23]) or the related problem of completeness conditions, which posits that the conditional expectation operator is one-to-one [BF17, 2CY semi-parametrie identifiability is also considered recently in the work of [CPS*23] Our focus this work is not focused on the identifiability; for the formulation (2) that we consider, [MMLR20] provide necessary conditions for identifiability that we adopt.
Stochastic optimization with nested expectations. Recently, much attention in the stochastic optimization literature has focused on optimizing a nested composition of T expectation functions. Sample average approximation algorithms in this context considered in the works of [EN13] and [HCH20]. Optimal iterative stochastic optimization algorithms for the case of T were by derived by [GRW20]. For the general T 2 1 case, [WFL17] provided sub-optimal rates, whereas [BGN22] derived optimal rates; see also [ZX21] and [CSY21] for related works under stronger assumptions, and [Rus21] for similar asymptotic results. While the above works required certain independence assumptions regarding the randomness across the different composi- tions. [HZCH20, HWX+24] studied the case of T 2 where the the randomness are generically dependent. They termed this problem setting as conditional stochastic optimization, which is the framework that the IVaR problem in (2) falls in. Compared to prior works, for e.g., [GRW20] and [BGN22], in order to handle the dependency between the levels, [HZCH20] require mini-bate batches in each iteration, making their algorithm not immediately applicable to the purely streaming setting. In this work, we show that despite the problem (2) being a conditional stochastic optimization problem, mini-batches are not required due the additional favorable quadratic structure available in IVaR.
Streaming IVaR. [VSH+16, DVB24] analyzed streaming versions of 2SLS in the online' and adversarial settings. Focusing on linear models, [VSH+ 16] provide preliminary asymptotic analysis assuming access to efficient no-regret learners, while [DVB24] provide regret bounds under the strong assumption that the instrument is almost surely bounded. Furthermore, our algorithms have significantly improved per-iteration and memory complexity compared to [DVB24]; see Sections A and B for details. [CLL* 23] developed stochastic optimization algorithms for the GMM formulation and provide asymptotic analysis. Their algorithm requires access to an offline dataset for initialization and is hence not fully online. The above works (i) do not focus on avoiding the forbidden regression problem and (ii) do not view IVaR via the conditional stochastic optimization lens, like we do.
Two-sample One-stage Stochastic Gradient Method for IVaR
Recall that goal is to solve the objective function given in (2). By [MMLR20, Theorem 4], the optimal solution of (2) gives the true underlying causal relationship under the following assumption.
Assumption 2.1. (Identifiability Assumption)
The conditional distribution P x is continuous in Z for any value of X.
'Their notion of online is from the literature online learning (SS* 12].
3

---

Algorithm Two-sample One-stage Stochastic Gradient-IVaR (TOSG-IVaR)
Input: I of iterations T, stepsizes {ar)?= initial iterate 01.
I: for = 1 to T do
2: Sample Zr, sample independently X, and X; from P Px|z, and sample Y, from Pyjx,
3: Update 0,
0.t1 = (0 X,) Vo)oog(0;; (0) X;).
4: end for
Output: 0r.
The function class G == {o(0; X) E Rd0} is correctly specified, i.e, it includes the true underlying relationship between X and
Notice that both assumptions are standard in the IVaR literature INP03, CP12, MMLR20), and makes the objective in (2) is the meaningful for IVaR. However, [MMLR20] resort to reformulating the objective function in (2) as a minimax optimization problem as described in Section 1. While their original motivation was to avoid two-state estimation procedure and avoid the "forbidden regression", their minimax reformulation ends up having to solve a complicated approximation the original objective resulting in having to characterize the approximation error which is non-trivial.
Algorithm and Analysis. Our aim in this work is to directly solve the original problem in (2), leveraging the structure provided by the quadratic loss. Given the gradient formulation in (3), natural way to build unbiased gradient estimator is to generate X and X', two independent samples of X from the conditional distributions P xx|z for a given realization of and generate one sample of Y from the conditional distribution Pvjx. Then, an unbiased gradient estimator is
(0) = (g(#: X) Vog(e;;
(4)
This could be plugged into the standard stochasic gradient descent algorithm, which give us the Two-sample Stochastic Gradient Method for IVR (TSG-IVaR) method illustrated in Algorithm In particular, the algorithm never requires estimating (or modeling) the relationship between X and Z as needed in the two-stage procedure PO9] and the minimax formulation based procedures [MMLR20, LS18, BKS19, DLMS20, LCY 20, BKM 233. Furthermore, this viewpoint not only provides a novel algorithm for performing IV regression, but also provides novel data collection mechanism for the practical implementation of IVaR. In addition, such two-sample gradient method is not very restrictive when the instrumental variable Z takes value in a discrete set. this case, implement the two-sample oracle, it is enough simply pick two sets of samples (X, Y, Z) and (X', Y', Z) for which Z has repeated observations (which is possible when Z is a discrete random variable) from a pre-collected dataset.
Assumption 2.2. The tuple (Zz, Xt, X Y() is independent and identically distributed, across t.
To demonstrate the convergence rate of Algorithm 1, we first consider the case when g is a linear function, i.e., (0; X) 0 0. We make the following assumptions.
Assumption 2.3. Suppose there exists μ > such that Ez EX|Z|X] Ex|z[x]T] ž pl.
Assumption 2.4. Let (01, 02, 03, 01) R4. For any Z, X' and X i..dd generated from Pz|x and generated from Py|x. There exists constants Cz2 Cy. Cany Czp > 0 such that
E
Ex z x|X|Ex 2[X] [2] C. X
(5)
E
|XX'
Br [x]]2 S Cydle
(6)
Ex Ez Ex|z[X] Ex12 [x] [p|] s Candoo
E
[Ex|2[X]
(7)
[Ev]z(M] Ex|z|X] - EEz Eriz Ex| ip] S Cy
E
(8)
where || denotes the Euclidean norm and operator norm for vector and matrix respectively.

---

The above assumptions are mild moment assumptions required on the involved random variables. The following result demonstrates that Assumptions 2.3 and 2.4 are naturally satisfied even under non-linear modeling assumption on (1). We defer its proof to Section D.3.
Lemma 1. Suppose there exist 02 E RRd,, 7/ E IRdx xdx a non-linear map & RR - Rd,, and positive semi-definite matrix Σ E Rddx such that
Ez p6 2) <7. = pl, E1l =(())
~ ~N(0, -) X -(: + E2. = 0. + 62 ~ ~N(0, 6 ~ ~((,00))) (9)
where 61,C2 are independent of Z and
E [21)) S 02 dz, E [11ó(1 2) 667 T) - -B(0(7 2) p07 2) [11]] S Cdz. (10)
Then Assumptions 2.3 and 2.4 hold with 91 = 02 = and d2 = 04 1. If Φ is an identity map, then the conditions involving & become 7, Σn. ž ,l, ir(n, "x: = E || T - =1 S Cdz.
The above assumption is standard in the stochastic approximation, statistics and econometrics litera- ture. It could be further relaxed to Markovian-type dependency assumptions, following techniques in the works of [DAJJ12, SSY18, Eve23, RBG22]; we leave a detailed examination of the Marko- vian streaming setup as future work. Under the above assumptions, we have the following result demonstrating the last-iterate global convergence of Algorithm 1.
Theorem 1. Suppose Assumptions 2.3, 2.4, and 2.2 hold. In Algorithm 1, defining of = 2C2d 2Czz and o = Cyd d set a = a
log T nT
S "
N²4307 Then, we have
E 00 1
3110. (pf + 03) log
0[ 0.1131
1²T
Proof techniques. In the analysis of Theorem 1, the following decomposition (see (18) for the derivation) plays crucial role:
0.+1 0. A, + Br:
A, 0, 0-44 Ez E [x|z(x] Ex 2 0. + a4t1EE Ey|2[M] Exz2 [x]] On,
B. - (X,X, -x,
Ez [Xxz|X] Ex|z(x]"]) (y:x/-Ez 1E [E [Ex12(x]]):
where A, corresponds to deterministic component, and B, corresponds to the stochastic component arising due to the use of stochastic gradients. Standard assumptions on the variance of the stochastic gradient made in the stochastic optimization literature include the uniformly bounded variance assumption [Lan20] and the expected smoothness condition [KR20]. In the IVaR setup, such standard assumptions do not hold as 9, potentially can be unbounded and thus the gradient estimator can be unbounded. Hence, we establish our results under natural statistical assumptions arising in the context of the IVaR problem, which form the main novelty in our analysis. Furthermore, compared to [MMLR20], notice that we use two samples of X from the conditional distribution IP x and
achieve an (L/TT) last iterate convergence rate to the global optimal solution, which is the true underlying causal relationship under Assumption 1. In comparison, [MMLR20] only provide asymptotic convergence result to the optimal solution an approximation problem.
Additional discussion. interesting to explore other losses beyond squared loss (for example to handle classification setting [CF21J), potentially using the Multilevel Monte Carlo (MLMC) based stochastic gradient estimators. While [HCH21], develops such algorithms, the main challenge about how to avoid mini-batches required in their work leveraging the problem structure in instrumental variable analysis. Furthermore, in the case when g0; X) parametrized by non-linear models, for instance, neural network, we provide local convergence guarantees under additional stronger conditions made typically in the stochastic optimization literature.
Assumption 2.5. Let the following assumptions hold:
Function F(0) is l-smooth.
5

---

The iterates {0. T+1 generated by Algorithm 1 are in a compact set A. The random objects Z and Y (Z have bounded variance for any Z. i.e., there exist a > 0 such that
E |||X B| 2 2 14 S E B|y 1 2 S o
Proposition 1. Suppose Assumptions 2.1, 2.2, and 2.5 hold. Choosing Algorithm I we have
O (vT)) for
min E [IVF(()) ISST
VT
The proof of the proposition is immediate. Note that under Assumption 2.5, we can deduce that the unbiased gradient estimator v(0) (g(0; X) Vog((( X') has bounded variance since
Var(v(0)) -Var(g(0; VaranannaaVVV X'))
Var(g(0: Y) Veg(O X())) + Var( Vur(Vog(e (ur(Ve((0;X)) [E]g(;)))
YT) S o
where the variance and expectation are taken conditioning on Z and 6, and > 0 is constant that only depends on a, function g and the compact set Assumption 2.5. Then one can directly follow the analysis of non-convex stochastic optimization (see, for example, [GL13, Theorem 2.1J) obtain Proposition 1. Relaxing the Assumption 2.5 (lypically made in the stochastic optimization literature) with more natural assumptions the statistical model and obtaining result as in Theorem for the non-convex setting is left as future work.
One-sample Two-stage Stochastic Gradient Method for IVaR
We now examine designing streaming IVaR algorithm with access the classical one-sample oracle, i.e, we observe streaming set of samples (Xe, Y, Zz) at each time point Note that in this case, using the same X, (instead of X₃) in (4) makes the stochastic gradient estimator biased.
Intuition. Consider the case of linear models, i.e., Y 0_ x + E with X = 7 E2, where 0, E Rd and % E Rdd, as also considered in Lemma 1. Recall the true gradient in (3) and the stochastic gradient estimator of Algorithm in (4). Since we no longer have X/. we replace the term X with the predicted mean of X, given Z.. Suppose that 7 is known. We specifically replace (org(0(; = X by E [1]] = 7. Z. In such a case, indeed we have an unbiased gradient estimator:
E4 Th 2x 02 Yi)] = E, R2 X. (E [x.) 0, EEZ, [Y])]
E hr_ 2,2, (0: - 0.)] - E27 0.) VoF(O.).
where E, [:] is the conditional expectation w.r.t the filtration defined on (71, 01, 72, 02, .t 0z). In reality, is unknown beforehand. Hence, we estimate % using some online procedure and replace (o,g(0r X/) by Yt. Zz instead of 7._ Zz. It leads to the following updates:
0.+1 = 0: - a++1% Zx 0. - -Y),,
7+ = "t- - B. -- X.T).
(11)
A closer inspection reveals that the updates in (11) diverge until 7 is close enough to %.. Is easy to see this fact from the following expansion of 0c+1 - 0.. We have
0 0, QQ. 0.) amt1(1s 74) Ezy + + + amt17 T Ez, (0, 0.)
+ a04417 T E2,700, a1+17t Ez,Y. ac+17 Z,E2, T0.,
(12)
where
Ez, = Ez 2 7.77 εz,y, Ezy ZY, (1-
T Ezrx).
However, the matrix 7/ Exy, may not positive semi-definite, even if Ez positive definite. Thus the negative eigenvalues associated with 7/" Σzy, might cause the 0, iterates to first diverge, before

---

OTS6-V5R
6-
Inglap
10g 03
Figure 1: (11) can initially diverge before converging eventually, leading to a worse performance in practical settings compared to Algorithm 2. See Appendix C.2 for the experimental setup.
Algorithm 2 One-Sample Two-stage Stochastic Gradient-IVee -VarR (OTSG- IVaR)
Input: Stepsizes {arht {Be,. initial iterates 7/, 01-
for = 2, do
2: Sample Ze, sample X, from Px 2,, Sample Y, from Py|x,
3: Update
0c+1 01 -0.-04177 7r(2, n0, - Ye),
(13)
7+1 7/- - - 7-- -x,,)
(14)
4: end for
eventually converging "/t gets closer 7.. We illustrate this intuition in simple experiment in Figure 1. To resolve this issue, we propose Algorithm 2, where we replace g(,, X.) = X, 0, with 7,7 7e0 in (11). With such modification, in the corresponding decomposition for 0.+1 0_ (see (40)), we have Q, = (I- 0 Exxx), where the matrix product 7t. Σx> is always positive semi-definite. Hence, with a properly chosen stepsize ar could quantify the convergence of 0, to 0g non-asymptotically. Nevertheless, assuming a warm-start condition on lg. we also show the convergence of (11), in Appendix E.3 for completeness.
Algorithm and Analysis. Based on the intuition, we present Algorithm 2. One could interpret the algorithm as the SGD analogy of the offline 2SLS algorithm [ [AI95]. Is also related the framework of non- non-linear two-stage stochastic approximation algorithms [DR20, DTSM18, MP06]; albeit the updates of 6, and 7/ are coupled since both updates use Z, Furthermore, the dependency between the randomness between the two stages in the IVaR problem, makes the analysis significantly different and more challenging from the classical analysis two-stage algorithms (see below Theorem 2 for additional details). Finally, while Algorithm 2 is designed for linear models, the intuition behind the method is also applicable to non-lincar models (i.c., between Z and X, and X and Y). We focus on linear models in this work in order to derive theoretical results. A detailed treatment of the nonlinear case (for which the analysis is significantly nontrivial) is left for future work. We make the following additional assumptions for the convergence analysis of Algorithm 2.
Assumption 3.1. For some constants Cz, Czy > O, we have the following bounds on the fourth moments:
E [|E2 ZZ 1 C..e
[1E2Y ZY S Czyaee 1 max(Us. 16). (15)
Assumption 3.2. There exist constants < uz 5 Az < 2o such that uzla, - Ez - AzIa..
The above conditions are rather mild moment conditions, similar to Assumption 2.4, and could be easily verified for the linear model setting we consider.
Assumption 3.3. {r e is within compact set of diameter C.d2 for some constants C, 0. 0.
7

---

We emphasize that Assumption 3.3 is only for the uncoupled sequence Ye. which is an SGD sequence for solving strongly-convex problem. It holds easily in various cases, for example by projecting the iterates onto any compact sets or a sufficiently large ball containing 7" It is also well-known that, without any projection operations, {7e) sequence is almost surely bounded [P]92] under our assumptions. Finally, similar assumptions routinely appear in the analysis of SGD algorithms in various related settings; see, for example, [Tse98, GOP19, HS19, NJN19, AYS20, RGP20J.
We now present our result on the convergence of {0r}, below in Theorem 2 (see Appendix E. for the proof). comparison to Theorem I (regarding Algorithm 1). we highlight that Theorem 2 provides an any-time guarantee, as the total number of iterations is not required in advance by Algorithm 2.
Theorem 2. Suppose Assumptions 2.3, 2.2 (without X(). 3.1, 3.3, and 3.2 hold. In Al- gorithm 2. for any L > 0, set at Cat flt12 and 3e ,..6(117...))) [1>)] 2,,,,,,,0500 min Ax 0/2 x² C22,
Cgt where Ca
2 and CB = 2x =12=1122x /128. Then, we have
E [10 - 0-1 =0 (1-!
Remark 1. In Theorem 2, we present the step-size choices for the fastest rate of convergence. In the proof of Theorem (see Appendix E. we show that convergence can be guaranteed for
range of step-sizes given by Oit. Cat Bt = Czt where 1/2 < a, < b, 2 2a t- 1og(2/t- 1))). In
with corresponding rate being WE [110, - 0 [|
particular, one requires b < 1 to ensure (at- a4t1)/ai o(a)), and (3, 1/31 o(3)), as is standard in stochastic approximation literature (see, for example, [CLTZ20, PJ92]).
Proof Techniques. The major challenge towards the convergence analysis of {0:}e lies in the interaction term 7: Zii 7:00, between T/e and 0g in (13). This multiplicative interaction term leads to an involved dependence between the noise in the stochastic gradient updates for the two stages. Such a dependence has not been considered in existing analysis of non-linear two time-scale algorithms [MP06, MSB + $09, DTSM18. DR20, XL21, WZZ21, Doa22]. In addition, [Doa22] considers the case when the noise sequence is not only independent of each other but also independent of iterate locations. Furthermore, they assumes (see their Assumption 3) that the condition in Assumption 2.3 holds for all whereas Assumption 2.3 only needs to hold for y,,, that is much milder. Similarly, many works (for example, Assumption in [WZZ21], Assumption in [XL.2]] and Theorem 2 in [MSB+ +09) assume that the iterates of both stages are bounded in compact set and consequently, and hence the variance of the stochastic gradients are also uniformly bounded.
In our setting, firstly, the stochastic gradient in (13), evaluated at (0c, 7)) is biased:
E. 1To 22 m0: Y.) = E. [7c 22(2, 10 2,_ 0.)] E3 [7e" 1Z22((000--- - -00-)] =M (B; - 0.) + 7/ E2(1 - 7.)0. + 7 E0, 0.) = V.F((.).
Furthermore, even under Assumption 3.3, the variance of the stochastic gradient is not (13) uniformly bounded. Overcoming these issues, in addition to the aforementioned dependence between the noise in the stochastic gradient updates for the two stages, forms the major novelty in our analysis. We proceed by noting that if 7.. Σz, and Ezy were known beforehand, one conduct deterministic gradient updates, i.e., 0.+1 = 0. att.Y (I2r/08 - E2y). to obtain f.. By standard results
~
on gradient descent for strongly convex functions (see, for example, [Nes13], (0.)e converges exponentially fast as stated in Lemma 4. Hence, it remains show that the trajectory of 0, converges
to the trajectory of Og. That is. defining the sequence 6, O. Or, our goal is establish the convergence rate of E [[]] We first provide an intermediate bound (see Lemma 6) and then progressively sharpen
tighter bound (see Lemma 7). In doing so, it is also required to show that E [|( is bounded, which we prove in Lemma 5. The proof of Lemma 5 is non-trivial and requires
carefully chosen stepsizes satisfying Et a4 oiv (3) < co.
4 Numerical Experiments
Experiments for Algorithm 1 (TOSG-IVaR), We first consider the following problem, in which (Z, X, Y) is generated via
Z ~ N(O, X = == 2) c (h tx), Y 0. x c (h1 + ty),
8

---

(d)
(f)
(h)
Figure 2: |[[|0, 0-]1²] of Algorithm under different settings detailed in Section 4.
where c > 0 is scalar to control the variance of the noise vector, and h is the first coordinate of The noise vectors (or scalar) h, Ez, cy are independent of Z, and we have h N (11,, Id_). Ex (O, La ).y (O, 1). In each iteration,
tuple (X,X', Y) is generated and used to update 0, according Algorithm 1. We set (dz, dz) E { [4, 8), (8, 16) } {0.1. 1.0), and ((s) E s²).
repeat each setting 50 times and report the curves of E|||0 - 0. 10 in Figure 2, where the expectation is computed as the average of |10, 0. of all trials, and the shaded region represents the standard deviation. The first row and the second row correspond respectively. Here, 0.1 for odd columns and
((s) = and (()) x² 1.0 for even columns. We have (dz, d.) (4,8)
for the first two columns and (dg, d,) = (8, 16) for the last two columns. Empirically, we can observe that our Algorithm I performs well across all different settings.
Experiments for Algorithm 2 -VaR). Next, we compare our Algorithm 2 as well as its variant and Algorithm in [DVB24]. We write "OTSG-IVaR" "CSO Eq. (11)" and "[DVB23]" to represent Algorithm Algorithm with the updates replaced by (11) and Algorithm in [DVB24] (see Appendix A). We follow simulation settings similar to [DVB24]:
Y 0 X
x=
c= o= Ia,),
pc1 + (0.00.55) (16)
where E is the first coordinate of e, 0, E Rd is a unit vector chosen uniformly randomly, and Ys [R xda where Yi 0 for i j, and Mi for i == = 1, ... dg. and 1,2, dy. Here p controls the level of endogeneity in the model. We compare the performance
Algorithm with (11), and O2SLS [DVB24] for p 1,4, 4, and o. 0.5, 1. By varying d, control the correlation between X and Z. We consider two settings (dg, dg) = (1, 1), and (dz d,) = (8. 16). Figure we plot E [[0, - []]]] where the E [-] is approximated by averaging over 50 trials, and both axes in log scale (base 10). We also show, in Figure 4, the convergence of the test Mean Squared Error (MSE) evaluated over 400 test samples to the best possible test MSE where 0, and 7 are known beforehand. For Figures 3 and 4, the first row and second row corresponds to (dz, d=) = (1, 1) and (dz, dz) = (8, 16) respectively, and a, 0.5 in columns. We have p 1.0 for the first two columns and p 4.0
As performance metric,
odd columns and for the last two columns. We can observe that O2SLS has much larger variance in different settings, while algorithms perform consistently well in all settings. We further conduct experiments real-world datasets provided in [AE96] and [Rya12]. Due to space limit, we include the numerical results in Section C.3 of the Appendix.
1.0 in
5 Conclusion
presented streaming algorithms for least-squares IVaR based on directly solving the associated conditional stochastic optimization formulation in (2). Our algorithms have several benefits, including avoidance of mini-batches and matrix inverses. We show that the expected rates of convergences for the proposed algorithms of order O and (11TTl-9) for any
0, under the

---

(d)
(f)
(h)
Figure Comparison of [B[|0 - 0. [|a]] (log-log scale) for Algorithm 2, Eq. 11 and [DVB24].
(8)
(b)
(c)
(d)
(c)
(f)
(h)
Figure 4: Comparison of test MSE (log-log scale) for Algorithm 2, Eq. 11 and [DVB24).
availability of two-sample and one-sample oracles, respectively. As future work, it interesting develop streaming inferential methods for IVaR. Leveraging related works for the vanilla SGD [PJ92, ABE19, SZ22, CLTZ20, ZCW23] the setting Algorithms and 2, provides concrete direction to establish Central Limit Theorems and develop limiting covariance estimation procedures.
Acknowledgments and Disclosure of Funding
YH was supported as part of NCCR Automation, National Centre of Competence (or Excellence) in Research, funded by the Swiss National Science Foundation (grant number HINF40_225150 KB was supported in part by NSF grants DMS-20539 18 and DMS-2413426.
References
[ABE19]
Andreas Anastasiou, Krishnakumar Balasubramanian, and Murat Erdogdu. Normal approximation for stochastic gradient descent via non-asymptotic rates of martingale clt. In Conference Learning Theory, pages 115-137. PMLR, 2019. (Cited page 10.)
[AE96] Joshua Angrist and William N Evans. Children and their parents' labor supply: Evidence from exogenous variation in family size, 1996. (Cited pages and 16.)
10

---

[A195] Joshua D Angrist and Guido W Imbens. Two-stage least squares estimation of average causal effects in models with variable treatment intensity. Journal of the American statistical Association, 90(430):431 1995. (Cited pages 2 and 7.)
[AP09] Joshua D Angrist and Jörn-Steffen Pischke. Mostly harmless econometrics: An empiri- cist's 's companion. Princeton university press, 2009. (Cited on pages 2, 3, and 4.)
[AYS20] Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. Advances in Neural Information Processing Systems, 73:17552-77535 2020. (Cited on page 8.)
[BF17] Andrii Babii and Jean-Pierre Florens. Is completeness necessary? estimation in non- identified linear models. arXiv preprint
2017. (Cited page 3.)
[BGN22] Krishnakumar Balasubramanian, Saced Ghadimi, and Anthony Nguyen. Stochastic multilevel composition optimization algorithms with level-independent convergence rates. SIAM Journal on Optimization, 32(2): 2022. (Cited on page 3.)
[BKM 23] Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, and Masatoshi Uehara. Minimax instrumental variable regression and 1_2 convergence guarantees without identification or closedness. arXiv preprint 2xXi::3322.05000 2023.
(Cited on pages 2, 3, and 4.)
[BKS19] Andrew Bennett, Nathan Kallus, and Tobias Schnabel. Deep generalized method of moments for instrumental variable analysis. Advances in neural information processing systems, 32, 2019. (Cited on pages 2, 3, and 4.)
[Bol12] Kenneth Bollen. Instrumental variables in sociology and the social sciences. Annual review of sociology, 38(1):37-72, 2012 (Cited page
[CF21] Samuele Centorrino and Jean-Pierre Florens. Nonparametric instrumental variable estimation of binary response models with continuous endogenous regressors. Econo- metrics and Statistics, 17:35-63, 2021. (Cited page 5.)
[CFR07] Marine Carrasco, lean-Pierre Florens, and Eric Renault. Linear inverse problems in structural econometrics estimation based on spectral decomposition and regularization. Handdbook of econometrics, 6:5633-5751, 2007. (Cited on page 3.)
[3] Xiaohong Chen, Sokbae Lee, Yuan Liao, Myung Hwan Seo, Youngki Shin, and Myunghyun Song. SGMM: Stochastic approximation to generalized method of mo- ments. arXiv preprint arXiv:2308. 1 13564, 2023. (Cited pages 3 and 16.)
[CLTZ20] Xi Chen, Jason D Lee, Xin T Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic gradient descent. Annals of Statistics, 48(1):251-277 2020. (Cited on pages 10, and 20.)
[CP12] Xiaohong Chen and Demian Pouzo. Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals. Econometrica, 80(1):277-321, 2012. (Cited on pages and 4.)
[CPS 23] Yifan Cui, Hongming Pu, Xu Shi, Wang Miao, and Eric Tchetgen Tchetgen. Semi- parametric proximal causal inference. Journal of the American Statistical Association, pages 1-12, 2023. (Cited on page 3.)
[CR11] Xiaohong Chen and Markus Reiss. On rate optimality for ill-posed inverse problems in econometrics. Econometric Theory, 27(3):497-522 2011. (Cited page 3.)
[CSY21] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimiza- tion is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4944 2021. (Cited page 3.)
[AJJ112] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael Jordan. Ergodic mirror descent. SIAM Journal on Optimization,
2012. (Cited on page 5.)
[DFFR1]] Serge Darolles, Yanqin Fan, Jean-Pierre Florens, and Eric Renault. Nonparametric instrumental regression. Econometrica, 79(5): 2011. (Cited on page 2.)
[DHP-17] Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. In Artificial Intelligence and Statistccs pages 1458- 1467. PMLR, 2017. (Cited on page 2.)

---

[DLMS20] Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax esti- mation of conditional moment models. Advances in Neural Information Processing Systems, 33:12248-1222 12262, 2020. (Cited on pages 2, 3, and 4.)
[Doa22] Thinh T Doan. Nonlinear two-time-scabe stochastic approximation convergence and finite-time performance. IEEE Transactions on Automatic Control, 2022. (Cited on page 8.)
[DR20] Thinh Doan and Justin Romberg. Finite-time performance distributed two-time-scale stochastic approximation. In Learning for Dynamics and Control, pages 26-36. PMLR, 2020. (Cited on pages and 8.)
[DTSMI8] Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. In Conference On Learning Theory, pages 1199-1233, PMLR, 2018. (Cited on pages 7 and 8.)
[DVB23] Riccardo Della Vecchia and Debabrota Basu. Online instrumental variable regression: Regret analysis and bandit feedback. arXiv preprint arXiv:2302.0033571. 2023, (Cited on pages 15 and 16.)
[DVB24] Riccardo Della Vecchia and Debabrota Basu. Stochastic online instrumental vari- able regression: Regrets for endogeneity and bandit feedback. arXiv preprint arXiv:2302.092357:3. 2024. (Cited on pages 3, 9, 10, 15, 16, and 17.)
[EN13] Yuri M Ermoliev and Vladimir Norkin. Sample average approximation method for compound stochastic optimization problems. SIAM Journal on Optimization,
23(4):2231-2266 2013. (Cited on page 3.)
[Eve23] Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. In International Conference on Machine Learning, pages 9412-9439. PMLR, 2023. (Cited
page 5.)
[GL13] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, (3(4)22341-2366 2013. (Cited page
[GOP19] Mert Gurbuzbalaban, Asu Ozdaglar, and Pablo A Parrilo. Convergence rate of inere- mental gradient and incremental newton methods. SIAM Journal on Optimization, 2944) 2019. (Cited on page 8.)
[GRW20] Saced Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal Optimiza- tion, 30(1):960- 2020. (Cited on page 3.)
[HCH20] Yifan Hu, Xin Chen, and Niao He. Sample complexity of sample average approximation for conditional stochastic optimization. SIAM Journal on Optimization, 30(3):2103- 2133, 2020. (Cited on page 3.)
[HCH21] Yifan Hu, Xin Chen, and Niao He. On the slas-variance-cst tradeoff of stochastic optimization. Advances in Neural Information Processing Systems, 34:221 19 22111,, 2021. (Cited page 5.)
[HH05] Peter Hall and Joel L Horowitz. Nonparametric methods for inference in the presence of instrumental variables. Annals of statistics, 23(6)::904-2929, 2005, (Cited on page 2.)
(HLLBT17) Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy. Deep iv: A flexible approach for counterfactual prediction. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 1414-1423, JMLR, 2017. (Cited on pages 2 and 3.)
[HS19] Jeff Haochen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In International Conference on Machine Learning, pages 2624-2633. PMLR, 2019. (Cited on page 8.)
HWX-22 24] Yifan Hu, Jie Wang, Yao Xie, Andreas Krause, and Daniel Kuhn. Contextual stochastic bilevel optimization. Advances in Neural Information Processing Systems, 36, 2024. (Cited on page 3.)
12

---

[HZCH20] Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and upplications in meta learning. Advances in Neural Information Processing Systems, 33:2759 -7770, 2020. (Cited on pages and 3.)
[KR20] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.0333 03322, 2020. (Cited on page 5.)
[Lan20] Guanghui Lan. First-order and stochastic optimization methods for machine learning,
volume 1. Springer, 2020. (Cited on page 5.)
ILCY-20) Luofeng Liao, You-Lin Chen, Zhuoran Yang, Bo Dai, Mladen Kolar, and Zhaoran Wang. Provably efficient neural estimation of structural equation models: An adversarial approach. Advances in Neural Information Processing Systems, 33:8947-8958, 2020. (Cited on pages 2, 3, and 4.)
[LS18]] Greg Lewis and Vasilis Syrgkanis. Adversarial generalized method of moments. arXiv preprint 1eXXiv:/003.00 164, 2018. (Cited on pages 2 and 4.)
[MMLR20] Krikamol Muandet, Arash Mchrjou, Si Kai Lec, and Anant Raj. Dual instrumental variable regression. Advances in Neural Information Processing Systems, 33:27 10-2211, 2020. (Cited pages 2, 3, 4, and 5.)
[MP06] Abdelkader Mokkadem and Mariane Pelletier.
Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms. Annals of Applied Probability, 16(3):1671-1700) 2006. (Cited on pages 7 and 8.)
[MSB 09] Hamid Maei, Csaba Szepesvari, Shalabh Bhatnagar, Doina Precup, David Silver, and Richard S Sutton. Convergent temporal-different learning with arbitrary smooth function approximation. Advances in neural information processing systems, 22, 2009. (Cited on page 8.)
[MZG-21] 21] Afsaneh Mastouri, Yuchen Zhu, Limor Gultchin, Anna Korba, Ricardo Silva, Matt Kusner, Arthur Gretton, and Krikamol Muandet. Proximal causal learning with kernels: Two-stage estimation and moment restriction. In International conference on machine learning, pages 7512-7523. PMLR, 2021. (Cited on page 3.)
[Nes13] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013. (Cited on page 8.)
[NJN19] Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. SGD without replacement:
Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703-477 PMLR, 2019. (Cited page 8.)
[NPO3] Whitney K Newey and James L Powell. Instrumental variable estimation of nonpara- metric models. Econometrica, 71(5):1565-13 1578, 2003. (Cited page 4.)
[Pap03] Christos H Papadimitriou. Computational complexity. In Encyclopedia of computer science, pages 260-265. 2003. (Cited on page 15.)
[PJ92] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838-855 1992. (Cited on pages 8, 10, and 26.)
[PSF24] Caio Peixoto, Yuri Saporito, and Yuri Fonseca. Nonparametric instrumental variable regression through stochastic approximate gradients. arXiv preprint arXiv:2402.05639, 2024. (Cited page
[RBG22] Abhishek Roy, Krishnakumar Balasubramanian, and Saeed Ghadimi. Constrained stochastic nonconvex optimization with state-dependent Markov data. Advances in Neural Information Processing Systems, 35:23256-23277 2022. (Cited on page 5.)
[Rei45] Olav Reiersøl. Conftuence analysis by means of instrumental sets of variables. PhD thesis, Almqvist & Wiksell, 1945. (Cited on page 3.)
[RGP20] Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos.. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, pages 7964-7973. PMLR, 2020. (Cited on page 8.)
[Rus21] Andrzej Ruszczynski. A stochastic subgradient method for nonsmooth nonconvex multilevel composition optimization. SIAM Journal on Control and Optimization, 2933):230 2021. (Cited page
13

---

[Rya12] Stephen P Ryan. The costs of environmental regulation in a concentrated industry. Econometrica, 80()):019-1000
2012. (Cited on pages and 16.)
[SS 12] Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trendy@ in Machine Learning, 4(2):107-19,, 2012. (Cited on page 3.)
[SSG19] Rahul Singh, Maneesh Sahani, and Arthur Gretton. Kernel instrumental variable regression. Advances in Neural Information Processing Systems, 32, 2019. (Cited on page 3.)
[SSY18] Tao Sun, Yuejiao Sun, and Wotao Yin. On Markov chain gradient descent. Advances in neural information processing systems, 31, 2018. (Cited page 5.)
[SZ22] Qi-Man Shao and Zhuo-Song Zhang. Berry-esseen bounds for multivariate nonlinear statistics with applications to m-estimators and stochastic gradient descent algorithms. Bernoulli,
2022. (Cited on page 10.)
[TM17] Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. Mobile health: sensors, analytic methods, and applications, pages 495-517, 2017. (Cited on page 1.)
[Tse98] Paul Tseng. An incremental gradient (-projection) method with momentum term and adaptive stepsize rule. SIAM Journal on Optimization, 8(2):506-331, 1998. (Cited on page 8.)
[VSH 16] Arun Venkatraman, Wen Sun, Martial Hebert, Bagnell, and Byron Boots. Online instrumental variable regression with applications to online linear system identification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016. (Cited on page 3.)
[WFL17] M. Wang, E. X. Fang, and B. Liu. Stochastic compositional gradient descent: Al- gorithms for minimizing compositions of expected-valls functions. Mathernatiaal Programming, 161(1-2)419-449, 2017. (Cited on page 3.)
[Wri28] Philip Green Wright. The tariff on animal and vegetable oils. Number 26. Macmillan, 1928. (Cited page 3.)
[WZZ21] Yue Wang, Shaofeng Zou, and Yi Zhou. Non-asymptotic analysis for two time-scale tdc with general smooth function approximation. Advances in Neural Information Processing Systems, 34:9747-9758, 2021. (Cited page 8.)
[1C Liyuan Xu, Yutian Chen, Siddarth Srinivasan, Nando de Freitas, Arnaud Doucet, and Arthur Gretton. Learning deep features in instrumental variable regression. In International Conference on Learning Representationss 2021. (Cited on page 3.)
[XL21] Tengyu Xu and Yingbin Liang. Sample complexity bounds for two timescale value- based reinforcement learning algorithms. In International Conference on Artificial Intelligence and Statistics, pages 81 811-819. PMLR, 2021. (Cited on page 8.)
[ZCW23] Wanrong Zhu, Xi Chen, and Wei Biao Wu. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 118(541):393-445) 2023. (Cited on page 10.)
[ZGG [22] Yuchen Zhu, Limor Gultchin, Arthur Gretton, Matt Kusner, and Ricardo Silva. Causal inference with treatment measurement error: a nonparametric instrumental variable approach. Uncertainty in Artificial Intelligence, pages 2414-2424. PMLR, 2022. (Cited on page 3.)
[ZX21] Junyu Zhang and Lin Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM Journal on Optimization, 31(2):1131-113 2021. (Cited on page 3.)
14

---

Appendix
A Online updates of [DVB24]
For the sake of clarity, we present the O2SLS algorithm proposed in [DVB24, v3]' in the streaming format, without any explicit matrix inversions that we used in our experiments:
Oc+1 (1 Ucn 2 n0) U Z,Y,
70+1 (I ViZi2, )a ViZiXi
Unn Z2Z2 niu,
UL+1 = U² + 2 nien Ze
V.Z. V2
V44 Vi 1 Z V.Z
Vo = I->
where U2, Vi two additional matrix sequences which tracks the matrix inverse of Ei 7. Z, "/, and (ATa, + + Z,7,) respectively for user defined parameter X. As men- tioned in [DVB24], we choose = The major difference between O2SLS and Algorithm that O2SLS takes an online two-stage regression approach minimize suitably defined regret whereas we take a conditional stochastic optimization point of view which requires carefully chosen step-sizes. In our Algorithm 2, we do need explicitly implicitly do matrix inverse which can potentially cause stability issues. Furthermore, unlike [DVB24], we neither assume Σi= Z,Z, is invertible for all f nor do we assume that Z is a bounded random variable for our analysis. Finally, the per-iteration computational complexity and memory requirement of Algorithm 2 significantly better than O2SLS; see Section B.
B Per-iteration Complexities
For the linear case, i.e., the underlying relationship between Z and X as well as X and Y are linear, Table summarizes the per-iteration memory costs and number of arithmetic operations of the original O2SI. [DVB23], the updated O2SLS [DVB24] that we provide matrix form update in Appendix A, TOSG-IVaR (Alg 1), and OTSG-IVaR (Alg 2) at the 1-th iteration.
Notice that the original version of O2SLS [DVB23] has a per-iteration and memory cost dependent on the iteration number an offline 2SLS at each iteration. The updated O2SLS [DVB24] (the algorithm that we compare to) uses samples obtained iteration explicit matrix inversion, it is obvious that its arithmetic operations and memory cost per iteration are larger than our TOSG-IVE -VaR and OTSG-IVaR.
needs use all the samples accumulated till the iteration to conduct
perform the update. Although the updated O2SLS avoids
We highlight that the TOSG-IVaR, which uses two samples X and X' from the conditional distribution P(X Z), requires only (dz) memory and arithmetic operations each iteration.
For fair comparison, we assume that two n x matrices multiplication admits an O(n²) complexity, ie., using normal textbook matrix multiplication. We also assume computing the inversion of matrix admits an Onn)) complexity. Interested readers may refer to [Pap03] for more details about faster algorithms with better complexities for matrix operations.
Note that the streaming algorithm not present in version 1, i.e., [DVB23, v1].
15

---

Table 1: Memory cost and the number of arithmetic operations at iteration t.
Algorithm
Memory cost
Arithmetic Operations
O2SLS [DVB23, vI]
1(d2 + dg) + dgd2 + dz
O + ld + (d
O2SLS [DVB24, v3] (Sec. A)
de + d: + d.ds . + dx
Old + d + dzdz)
TOSG-IVaR (our Alg 1)
dz
O
OTSG-IVaR (our Alg 2)
d=dı + dz
(min(d (d2,, d)) + dzdz)
C Ex Experimental Details
C.1 Compute Resources
All experiments in Section 4 were conducted on computer with an 11th Intel(R) Core(TM) i7- 11370H CPU. The time and space required to run our experiments are negligible and we anticipate they can be conducted in almost all computers.
C.2 Experimental Details for Figure
In Figure show example where the updates (11) may diverge first before converging eventually and finite time performance can be much worse compared to Algorithm 2. For this experiment, choose the model presented in (16) with dæ d2 = 1, 0, = 1. -1, 4, and o, = 1. When initialized at "mo = 10, and 0n = O, the updates in (11) keeps diverging rapidly at first whereas Algorithm 2 is much more stable. So, by the end of 100, 000 iterations, while Algorithm achieves an еπгоr of zs 10-5, (11) achieves zs 10" that is worse than it was at initialization because (II) has not recovered from the initial divergence phase yet. However, once (11) starts converging, the convergence rate of (11) is similar to Algorithm 2 as one can see from Figure (also see our discussion on the convergence of (1 in Section E.3).
C.3 Additional Experiments Real- World Dataset
In this section we provide experimental results on real-world datasets provided in [AE96] and [Rya12]. The results are included in Figures 5 and 6 respectively. Following the convention in Section 4, write "OTSG-IVaR", "CSO Eq. (11)" and "[DVB23]" to represent Algorithm 2, Algorithm 2 with the updates replaced by (11) and Algorithm in [DVB24].
C.3.1 Children and Their Parents' Labor Supply Data in [AE96]
The outcome Y is number of working weeks divided by 52, the regressor X is 1nnumber of children is greater than 2), and the instrumental variable Z is 1 [first two siblings are of same sex), where 1(.) is the indicator function. At each time we randomly sample data-point from this dataset without replacement. Since the "true" parameter 0, is unknown in real data, we use the offline model parameter estimate as our ground truth, following [C].+233. We include the results Figure 5. in which we observe that CSO performs similar to [DVB23] whereas OTSG-IVaR performs much better in terms of convergence speed. Moreover, the estimation errors of CSO and [DVB23] plateau after 10,000 iterations whereas OTSG-IVaR keeps on improving the estimate over the observed horizon.
C.3.2 U.S. Portland Cement Industry Data in [Rya12]
Response variable is lsg(shipeed), and the predictor X is log(price). There 4 instrumental variables given by wage in dollars per hour for skilled manufacturing workers, electricity price, coal price, and gas price. Unlike the previous dataset, we have only 483 data samples here. So, mimic an i.i.d. data stream, we divide our training into multiple epochs of length equal to the number of training data samples, and over each epoch, at each iteration, we sample one data point uniformly randomly without replacement from the training data to generate the data-stream. Both OTSG-IVaR and CSO perform much better than [DVB23] in terms of convergence speed. Figure 6(b) a magnified view of iterations > 50 to highlight the performance difference between various algorithms.
16

---

0159-N0 (DV923)
05
-15
-20
-10
Iog M5
Figure 5: Comparison of [8] - 0.112] (log-log scale) for Algorithm 2, Eq. 11 and [DVB24].
CTSS Ved
3TSG-VVA
csp Eq (11) [DV923]
csp to. (31)
[0v923]]
Ing
(a)
(b)
Figure 6: Comparison of [E[]0; - []] (log-log scale) for Algorithm 2, Eqq 11 and [DVB24).
D Proofs for Section 2
D.1 Proof of Theorem
Proof. We aim to find the optimal 0.. According (2), we know
Ez [x|z[X] Ex|z[x] 0. Ez Byiz|r]- Ex|2[x]
(17)
The updates in Algorithm I can be written as
0c+1 (00+1(X,71) -Y)xX
Hence have
0,+1 0.
-0, aut EE Ex|z(X] Ex]22X]]] 0r + 1441E2 Eriz [Y] Ex12 [X] -0.
-att1 (X,X. Ez Ex|z|X] [x|z[x]T] 0r + a+t1 (Y,X - Ez E Eriz[r] Ex Ex [X] [x]] )
(18)
Now we analyze the convergence and variance separately. For the convergence part, we have
02 a Ez Ex Ex|z/X]- Ex Ex|z|x|T 0: + E2 ErIz(M)- Ex|z[x]] 0, = aut EE Ex|z(X) (X) Ex|z(x]7] (0. -o))
(19)
17

---

For the variance part we have
B |x;x; - Ex [x|2 Ex|z[X]
=B
|XXX Ex|Z, [X] [x]
+ Ex [X] Exiz, - -Ez Ex| Ex|2 [X] 113
22
|
Ex 2. [x] Exiz,
[X] - Ez [x|z(x] EE x [x]
[P]]
,2C, + d0 =: of
(20)
Similarly, we have
|X,X - Ez [r|z/r]- Ex|z [x] 12]
E
E
| Exiz. M Exiz [I] + [Er,z, [ Exiz, [X] Ez By Z Ex [ 13
<Cyd
Cyrr =: =.
(21)
Now we know from (18), (19), (20), and (21) that
|00+1 0-112 ||A:11 + 200+1 (Ac, Br) + abtt1lB.11
(22)
where
A; (1 114 [x|Z[X] Ex12 [X] [] 0.)
B: - (X,X,-- Ez -xX121A7-EXxx21 (12X; - Ez [Brzz ( Exzz(x]))
This implies
Epess 0: [100+1--000 - -1.123
-I1(1 - 044 a1+1lEz IEz [x|2[X]
(Ex12(x]]] (XxI((X)-Bxxx(x17)) -0)-1
+ a E X/,.., [xxx - E2 Ex| [xxz||X] Exi2 [x] x - (yxx; Ez Eriz(M] Ex1z (x
[P]]
<(1 - 11))1 - 12 + 30 (o/110. 0.11² + 1.. 12 + 02.10.133
<((1 00+1/13 + 3 1): - 0.112 1 0, + 03
(23)
where the first inequality uses Cauchy-Schwarz inequaallaiiiie the definition of o 02 and Assumption 2.4. Choosing a++1 such that
((1 11) o S 1441/
P
112 30
and taking expectation on both sides (23), we have
E 110 1r] < (1 o++ 144 0.113] 17 10
Now, we use the following result.
Lemma 2. Suppose we have three sequences {ar) (b.)0 fre satisfying
0t41 S rrat + br, ri >
(24)
for any t 2 0. Define R&+1 = II Fh we have
Re+1b;
0141 S Re+190 +
R441
By Lemma 2, we know
[|100+1 0=1 < II [ 81108B110000 1100 0-112 (30 + +303110=113)
Σ
II (1 - a,n))
0
==
1=0
j=++1
18

---

Now if we set a, we know
t E [100- 0.119] <(1 o.p) 'TE 100 - 0.12) a² 12
azd)) (301110.11 + 303110. 10.111.113) 11.)
==
Se Se-tamE
|100 - -0.11]
+ -h (307|10.11 + 30 30 0.13)
Choosing a, T such that
lon T
know
1²
a
+30f
E
1100 0.113
+ 3110.11 + o log T
E 100 0.112
T
2
D.2
Proof of Lemma 2
Proof. We notice from (24) that for any
S i
we have
0++1
by
R
R;
Ri+1
Taking summation on both sides, we have
ac+1
40
b,
Re+1
Ro
R1+1
which completes the proof by multiplying R,41 on both sides.
D.3 Proof of Lemma
Proof.
We first notice that Assumption 2.3 holds since
Ex Ex|z[X] Ex [X]] Ex p67 2) 607. 267_2)
2 pI.
For (5) and (6), we have
|X'X - Ex xX [P]
E
E
116 T =) + ohn 2) + c6 [13
<3E
2) 11 +1eeb=211
=3E
1 2) c6 2) 2) 1067 c 2) [6]c6/]] Ocd)), (25)
and
E
Y Ey E
=E
x + + EXII 0.112)
|X'XX 0, 2x- 0. 11 + 2E Goloo!! Z) 661
=0( de - of du o dz),
where the first inequality uses Cauchy-Schwar Schwarz inequality, and the second equality uses (9), (10) and (25). For (7) we have
Ex [X] Ex [x - Ex Exiz (x] Exiz X [P]]
E
| T 2)0(7 TT - E [0(>] 2) 2) 12 = O(d,)
where the last equality uses (10). Using the above conclusion in (8), have
E
Eriz(-]- Exiz [X] - Ez E Eriz(r]- E ExIz [x] [p]
= [xxz[X] Ex z [ To - Ez Exiz(X) Ex12 [X] T 0. 0.][P]] [2]
0(10-112d2..
19

---

E Proofs for Section 3
E.1 Proof of Theorem 2
Proof of Theorem 2. Recall that Ez., and Ez,Y, are the i.id. noise sequences
Ez. Ex 74
E2,,, = Σzy - Z.Yr.
Note yy., and O- can be written as 7 = E which going use throughout the proof.
Exx E Rdd=xd=, and 0. = =1,,E270 "
"IE
Yx Exy E Rdd
To quantify the bias, we use the following bound on [lh - 7+1l) - 3.2 of [CLTZ20].
1,2, 4, proved in Lemma
Lemma 3. Suppose Assumption 2.2, and Assumption 3.2 hold. Then we have
Ilh 1-11*] (V for k = 1,2,4.
(26)
We proceed by noting that if 7s. Ez. and Ezy were known beforehand, one could the following deterministic gradient updates to obtain 0..
00t1 = - a (M2T.00 -iiz)
(27)
Lemma 4. Let Assumption 2.3 be tree Then, choosing Mi O with 1/2 < we have |10 0.1 O (exp(-t!-o)
Define the sequence 5; 0 G. We will establish the convergence rate of E [| l2 From (13), and (27), we have the following expansion 8,41.
b = Q15e + 04+1 D,0, + a441(% - "2) - -44171 Ez,Y. + 0411% E2,1
(28)
where
Q: Q 11717 2iz+))
D. 12 7t 2i7t..
First we will establish an intermediate bound on E []] To do so, we will need the following result which shows that E [100, 11]] is bounded for all t which we prove in Section E.2.
Lemma 5 (Boundedness of fourth moment of ||0 0.1l). Let the conditions in Theorem be true. Then, choosing ai, Br such that a₁ I d= 4/2 and [ + avvB.) < 00, we have [|0 0_ 0_ is bounded by some constant M > 0.
Lemma (Intermediate bound on B|||o )). Let the conditions in Theorem 2 be true. We have the following intermediate bound on [1]
E | ? O [3,d + 1441dxx00/2 vdg3i)
(29)
Proof of Lemma 6. Recall the update for d+t1 obtained in (28).
8
Qroe ae+ D,O, + aut (n+ --) Exy a0417 Ez,,. + anti 17.00
Then,
1|8++111 =6; Q&88, + af Dr0, + (n -+)) Ezy - ni Tzzx, + + T 12.700.12 + 1: Qe (D,0; + (7: - (2)=-a)" TT)TT
(30)
+ 20 Qi (76 E2, n. 7 TEz.x.)
20

---

Then, choosing a1 (11n+11222) < 1, using Young's inequality and Assumption 2.2, from (30) we get,
[1
[2]
5(1 11+ |6:111 + 4 (1) + I1( - -7-) Ez>ll²)
4 (11 I2 [llE2.y. [ī]] + 11 [llEz, (11:11))
+ 201+10 T Qe (D,0, + -++ Σ2y)
11 a++141 10/11 + 40 (11,11 + 11(7 n.)) -2,))=2>7 E2r 113)
4Ca
d 82 d //2 ///10.113) +
201+10; T Qi (D,0, + (7 - EE2y)
where the last inequality follows by Assumption I, l,ndd Assumption 3.3.
Now, taking expectation on both sides, we obtain
E [1
[2] 51
11+1 [110,1]] + 4a E [I + [l]( - -
Ezx 112)
4Ca2+1
d2x d/ [10(1]
20141
[ |o.
T Q.D.o.1
E [0o "TTTr( - 7.) "Q(((--76)
(31)
Now, the following bounds are true:
1. We have that
2 E |I oa+i E P. [110.11]] S d= 2x 1 7
(32)
where the first inequality follows by Canchy-Schwarz inequality, the second inequality follows by (42), and Lemma 5.
2. Using Σzy O(), and Lemma get
a E [ll( - 74) T E2> S de
(33)
3. We have that
at+iB [10. (66TQQ.A T.DDDal0
Sa0+1 |1
11+1/1
E
4o [16.1]'
E
(1)))
E (10.
16
01+1/1 E [|6.]12]
4d.+2>
2x
out1
(34)
16
where the first inequality follows by Hölder's inequality, the second inequality follows by Young's
inequality, Cauchy- Scchwrr inequality, and ||Qr]la < and the third inequality follows by (42), and Lemma 5.
4. Using 1|Q.122 < 1, |Ezr||2 = O(1), Cauchy-Schwarz, inequality. and Lemma 3, we get,
a E [6o Qe(7 7+) -Exl
Son+
E ||]6||22| - -71112]
<a0+1
V
E [1 [1:] E [llee 7 112)
Vdūhart1
Vdz3aut1 E [16+11]]
(35)
2
Combining (31), (32), (33), (34), (35), and Lemma 5, we have
E [16 [
21

---

5(1 ac 14 E [1|:|19] + 1
+2x -
1 d
+ 201+1 [LEE |16. / 4d 3//+ dd + v dz [10: /2)
(36)
21 7 a141 (
|| + ( 3,d - 2M 11 + 4 (
+ 04++1 dz3t
2(1 31 /4) [16 + (8a 1 / + 1 xxx) + a++ v d23. (37)
In the above, the third inequality follows by choosing 3t - /z (64dg), and a+t1 v d.d < 1. Then, from (37), have
1 = =0 (s.dd + aat1d xx + v ddz3.)
E
Coming back to the proof of Theorem 2, observe that, we can sharpen the bound (35) using Lemma which allows to avoid the use of Young's inequality. This leads to the following improved version of the recursion in (37) using which we can improve the term vd,3 3 in (29) as follows:
[[] [2] 2(1 Tuar+1/8)) [[6..1]]
+ a (Bid!txx + aatid 0 + vat+13.d /22 + (3,d2)3/1)
-0 (add + autid 0 + Vatt13dd
(3td2)3/4)
In fact, this trick can be used repeatedly to sharpen the bound even further as shown in Lemma 7.
Lemma 7 (Final improved bound on ()))) Let the conditions in Theorem be true Then using Lemma 6, we have,
E 1
oo (d.3))1-2
Σ
(a 02-(0x00/22-112 (d B+ + a(Hi)d :
i=0
where is any non-negative integer.
Proof of Lemma 7. If we have
E [|6 =0 (al+idxxt012 + B,de+2x v do
then from (35), we have,
8, TiQQ - Exzr SV [11 [11T - 7- 11]]
-0 (0(Va+18Bdd//t22--0 B,d! + (d28))3/1).
(38)
Then, similar to (36), we have,
1 1121
5(1 a4+1
[11&21] + 3 122 + 4C 4
+ 20141
ME
[1|0& || /16 + 40 401+220 Br/ + /i + B,d+** + (d.3.)3/44
5(1 11))+1188)B
[116.1]]]
014+10
(dg,))3/4
2 1-2-1122 1-2-1 " //4(4x4002-1122 B d 21--x
-0 (d..8)3/44
Σ
1 1-2 'd.
111 + Be(1 + 2- d )
1=0
22

---

Now if we repeat this step number of times (where r is to be set later), by progressive sharpening we get the following bound.
E [1
50 (d=36))-
2- 1441831-220 - + Bc + dz Σ
1=0
Coming back to the proof of Theorem 2, we have that by combining Lemma 4, and Lemma 7,
E [10 1=11²] - 2E
[|]]|]]] + +2E 100 - -0.113 11]
(d=3)))-2
o, 1-2 (0x + B + 2 a(Fi)dd+2
(39)
Now, in (39), for some arbitrarily small number e 0, choosing 0r min(0.5d 4x 1/2 x C, (15())=112222-11))
1+1/2 //28, Br = 1
and setting r [log2 ((1/2)- - 1) -1 we get,
E 01 0. 03 0 (max (1-1te, ( log( (1/((111)-111)))1 -1))
E.2 Proof of Lemma
Proof. Using the form of 92, from (13) we get,
Oct1 - 0, =Q 0.) a't1(n 7-) T Ezy + a+41 a4t1 D,O, + 0ut177 T Ez, 7e - -0.)
+ on+17 700. 02+17 E2,21
(40)
where @. = (I - 04417 Σ27;) = Qi + aa-1 Dr. Recall that Dj = 77 7 TE27. By
Assumption 3.3, we have the following bound on ||Drll
|Dell2 O4
(41)
We have the following bound on E [1]] by Lemma
E [[ E [[[(>- - -1) T E27. 7h Ez(r- 70) = 0
(42)
From (40), we have
| 11113 <(,, 0.) TT) (7( 0.) +aa 117 (0, 0.)
+ 201++ (0. - 0.) [.,)TQQ(11 -
+ 20 (0.- 0.) T D.0. + A1,t A2,1
(43)
where
AL. 2z 2 - 7/)) T EEz + D.
+ 27 7,) D.O. + 31 T Ez, r.0.112 + 31/ T E2,v112)
(44)
and
A2, =204+ (Q:(0: - 0.) + a0t11 - -7,) TEZY
+ D.0.) ( T (0 (76
- 0.) + re- T
n.0 +7 T [22x)))
Define
Ag, = 30 11 (0: - 0.) 1 + 20 (0g - 0.) TQe -7x) T Egy
20141 (0. 0.) TQ. + AA, A2,1-
(45)
Then, choosing CR X2 < 1, which ensures || < 1, we have
||0++1 - 0.11 < 10, - 0. 2(0, - 0.) T Q² 0.) 0.) + A3,
(46)
We now have the following bounds:
23

---

1. Using Assumption 3.1, and Assumption 3.3,
1 [l Ez, (1 - -0.113] S x ai+1 E [100 0.112]
(47)
2. We have that
((0: - T - -v-) TE2x)²
2 E ||0: - 0_ 11 -7=113]
E [110: 0-112] EE| [ll -7-113)
d.3. (1 + E. [110. 0- 0111)) /2,
(48)
where, the first inequality follows by ||0, = (1), and |Ezz = O()) The second inequality follows by Cauchy-Schwarz inequality. The last inequality follows by vab S [a + 6)/2, and Lemma 3.
3. We have that
E ((0) 0.) Q(D.0.))
< [1]0, 0. 11: De
< V E 1110, 0- 13 E |1
2 d. +2x 3, (1 (1+ [1]0. e. (11] /2.
(49)
where, the first inequality follows by 1| O(1), and ||0~ 0(1) The second inequality
follows by Cauchy-Schwane inequality. The last inequality follows by vab < (a+ + b2/ and (42).
4. Using Assumption 3.1, Assumption 3.3, (42), and Lemma have
E [4,,]] = O (d a441).
(50)
5. Using Young's 's inequality, Assumption 3.1, Assumption 3.3, Lemma 3, ||22/ 1|2 (1.|l2 O(1), and (42), we have
E [Ag $2ai+ E (1: - 0.) + a441(m - 7x) ac+1 110,11
+ 2a E |1 T (0, - 0.) + 7 T2, n0. + 7 T (2.Y.
Saz -=x (1+ E [10] -0.11)).
(51)
6. Using 110.12 0(1), Assumption 3.1, and Assumption 3.3.
B E (0c-0.) TQ" -0.) T (0, - 0.)1| Sa [110: - 0- -0 (52)
7. We have that
a+ [100 - 0.) TZ) - 0.) -., - -i) Ezrl
Saa E [110, 0, 0.1121 71
Sa441 (E [|10; 1111)) 3/4 (E [lh 7 1= 1/1
S0141 V d.B. (E [1]0, 0. (11)]
3/4
30141 d E [110, 0.1 0.41 Lz
(53)
4
where, the first inequality follows by 112.12 0(). and || = 0(1), the second inequality follows by Cauchy-Schwanl inequality, the third inequality follows by Lemma 3 and the fourth inequality follows by Young's inequality.
24

---

8. Similar to (53), we have,
a1 E [(0, - (100.-0)T -1000-000000000000000-----000-00
- 0.)(0, - 0.) T.) Q.D.O.1 d= / OV+IVBL
3d2/2t* a4t1 TE [100, - 0.11 +
(54)
9. Using 110:122 O1), Cauchy-Schwerr inequality, (50), and Young's inequality,
E (0: 0.) (0. 0., A1.
<B
[1|+ 0- 0.112Ar.1]
[1 - 0_ (1 [A4
/ (1 + E [110: - -0.11))
(55)
10. By Assumption 2.2, we have,
Ex (0. - 0.)
T @7 0.) 02. = 0.
(56)
Now using Jensen's 's inequality, and combining (47), (48), (49), (50), and (51), we have,
E [A <45a E [llm Ez, (6: 0.]11 + 20a E ((0: 0_) T 76) -x E2r)²
+ 20 TE [(0) (..0--.)TQ.D.0, 32 + 5B [A 1, + 5E [Ag,]]
La 1 [110, 0 [1] + d
(1+ EE [110, 0.112))
+ 1 + 2x 3: (1 + E [1]0, 0. 1111))) + d w + a (2x+1)/ (1 + [10, 0,1l)))
1
Saft dext0 (1 + E [10, - 0 1
(57)
Combining (52), (53), (54), (55), and (56), we get,
E
(0, 0.) Q (0: A3.
Sa d 1xx00/2 1/2 ||0: 0.11%] + 30 1
[110: - -0.11%] + a++1 dgg
4
3d 32 x ac+ / BB [110, - 0- [ + d 1/2+x a++1 3Bc
de /1x+0/2 2x
24 (1 + [100 - 0. 0.11g)
4
Slar-1 de 0/x40/2 01+1 V Betid! /2+ (1+x)((11))) 110 -0(1-) (2)
(58)
Combining (46), (57), and (58), we have,
E [10 - 01 S(1 + at deut 01+1 / B (2+x) (1 + [10, - -=
(59)
Now choosing a, Be such that a₁ I d 4-4 and Σx (af+) + + B141) < co, we get
E ||0 0, 11 < M,
(60)
for some constant 0 S M < oc.
E.3 Comment on the convergence of (11)
We now discuss the convergence properties of the update sequence (1I), which we refer to as the conditional stochastic optimization (CSO) based updates, which we restate below:
0++1 0: 1 (x, 0, Yt),
M+
B.t1 (. 7t. X,
Similar to (40), for the above updates, we have the following expansion:
0,11 0, (Q. 0.) act1(1 - -24) Ezy
a + T
+ a1117 T Ez, (0, 0.)
25

---

+ 0141 E2,7 + a411% Ez,y, - -1+17 T 2, 8c.
where Ex, = Ex - 2: Enn = Ezy Z,Y, Q = (1-00417) E27.)) = Qt + 04+11 Dr, and
D2 = (%/ - 7/.."271..
Recall that the reason for the initial divergence of the updates in (11) are the potential negative eigenvalues of "/t Ezn.. Here we will show that 7t Σzz, positive semi-definite or Y is close enough to such that the negative eigenvalues (if any) are not too large in absolute values, then the updates in (11) indeed exhibit the same convergence rate as Algorithm 2.
Assumption E.1. Let either of the following two conditions be true. For all 2 tv.
1. EyY, is positive semidefinite. 2. 11 - -- dz
Note that Condition of Assumption E.1 is idealized condition which is difficult ensure for all t in reality. But of course this is true, then 7/2 2y> does not have a negative eigenvalue to cause divergence and the proof then follows exactly like Lemma 5.
Hence, we will focus on the more realistic Condition of Assumption E.1 which holds true almost surely [P]92]. Since we are interested in the asymptotic rate of convergence of CSO updates (due to the requirement of Assumption E.I), we will only concentrate on the iterations t 2 to. In this case, the proof steps are similar to Theorem 2 except for two major differences, that we discuss below.
Difference 1: Potential negative definiteness of "/ E2y::
Under Condition 2, >t Ezy, can indeed be negative definite. In general, if 7t T Ez7, negative definite then that undesirable as explain Section 3. In terms of the proof,
longer write
(0: - )*) Q (0, 8*) I 10: - 0.11 2 (which was possible to in (43) the proof of Lemma 5). Subsequently, (46) breaks down. But we will show that under Condition 2 the negative eigenvalues are not too large in terms of absolute values. Specifically, we can write,
(0: 0*) TT) Qi(0, -0")
=(, T + 0.+ D. + a141 D. Qi + oi D. D.)(O. 0*)
(61)
<(1 200+ D+Il) 00. - 0.112 + ai D. 1 0.11
<(1 + 20 / d (;); 0. a DrI 2110: 0,
The term 124,11Da111100 enough in the sense that we choose the stepsizes such that ( aa+1 13.) < co. Using this one can now show a similar bound as (59) and consequently show E [[]0, - 02 [1t] bounded.
0- is of the order of Aa.: defined in (45). Now a--1 ve-IVd.i, is small
Now let
what happens in the absence of Condition 2. Here one could use the fact (1 + 20t=11| S (1 1 ac,d)) which is too big. Recall that we want something at least of the order of 01+1 to show that 0, sequence is bounded. One could also try to use the fact that E [I]]] is small by Lemma 3. But since D, and O, are interdependent, one needs to decouple them. One way to do this would be to use Sauchy-Shward incqualityas shown below.
E | 0, [ < [E E I110,
0.1141 S Vd,3,E [1|0, 0. [1
But that leads to the presence of E [[]0] - [ in (43) which is potentially problematic due to the fact that on the left-hand side we have E [[|001 - 0. 12].
Difference 2: Presence of additional error term 04417 T Z,c,,1 T0,:
When comparing (12) with (40), yet another crucial difference is the presence of the term 0++177 Zee2,t 0, We will show by the following observations that this error term gets absorbed by other terms already present in (40) without affecting the convergence rate. Specifically, the following holds.
26

---

1. Using the independence between 2, and 62,1, and by Assumption 2.2, we have,
[, - 0.) a041 (7: - 7-) Ezy + #441 D,O, + out17 70,70 - 0.)
+ 024177 7a0)" n Z222, 0zl = O.
2. We also have that
a² Es [(1> T (2,,,) "t" Zee2, 0t]
-7 >i 10-1111111 10.11 21 + 7/ 22 (0: 0.))
<a T 1z + l1 Ez>((0 0. 01 + -10.
This shows that the above term is of the same order as A1, and A3, defined in (44), and (45).
3. Finally, have
Be || Zre2, 00.131 x af (1h 11 0. + 1100112110-11).
So this term is of the order of A3, well.
Combining the above facts and following similar procedure as the proof of Theorem 2, one can show that the CSO updates achieve similar rate under additional Assumption E.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sections 2, 3, and 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss some limitations of our analysis and some future directions the end of Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
Sections 2, 3, and the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Sections 4, C.I, and C.2.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer: [Yes]
Justification: Sections 4, C.I, and C.2. We also provide the code in the main supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
oopPoliioo olycy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ mublic/guidess Caleee/CooSSubbieee cobbbmisssiinss seissssoiccyyyyyc for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Sections 4, C.I, and C.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Sections 4, C.I, and C.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: attps://neurrpps http:pp....c....tittctcccceeeeee
Answer: [Yes]
Justification: Sections 2 and 3. Our research conforms in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Sections and 3. Our work is mainly about theory and algorithm design, so there is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Sections 2 and 3. Our work is mainly about theory and algorithm design, and poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Sections 4, C. and C.2.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Sections 4, C.I, and C.2. The code is in the supplementary material. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Sections 2 and 3. Our paper is mainly about theory and algorithm design, and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Sections and 3. Our paper is mainly about theory and algorithm design, and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "V6RF7SRbnh", "reviewer": "Reviewer_E97U", "summary": "This paper proposes and analyzes on-line algorithms for instrumental variable regression (IVaR) with streaming data.  Specifically, the authors consider the model:\n\n$Y = g_{\\theta^*}(X) + \\epsilon_1$ \n\nwhere the covariate $X$ and noise $\\epsilon_1$ are possibly correlated, but an instrumental variable $Z$ is available that satisfies:\n\n$X = h_{\\gamma^*}(Z) + \\epsilon_2$ \n\nwith $\\epsilon_2$ being a centered (unobserved) noise.  Building on the prior works [MMLR20] and [HZCH20], the authors consider the IVaR problem formulated as a conditional stochastic optimization problem, presented in Equation (2):\n \n$Minimize_g F(g) := E_Z E_{Y|Z} [ ( Y - E_{X|Z} [g(X)])^2 ].$\n\nConsidering a parameterized family of regression functions $G := \\{ g(\\theta; X) | \\theta \\}$, the authors observe that the gradient of F admits the expression as in Equation (3):\n\n$\\nabla F(\\theta) = E_Z[ (E_{X|Z}[g(\\theta;X)] - E_{Y|Z}[Y]) \\cdot \\nabla_{\\theta} E_{X|Z}[g(\\theta; X)]].$\n\n\nThis paper propose and analyze two streaming algorithms to solve the optimization problem formulation above. Notably, the proposals in this work do not require reformulating it to a minimax optimization problem as done in [MMLR20] or employing a nested sampling technique to reduce the bias in gradient estimation as in [HZCH20]. Specifically, the authors assume the availability of an oracle that can generate a sample $X$ (or two independent samples $X$ and $X’$) conditioned on $Z$, and then propose a stochastic gradient descent for IVaR. Additionally, the authors establish the rate of convergence assuming linear models. The proposed algorithms and claims are supported by numerical experiments with synthetic data.", "questions": "1. While Algorithm 1 is generally applicable with the availability of two-sample oracles, Algorithm 2 seems to hinge critically on linear models. The authors note in lines 244-245 that a detailed treatment of the nonlinear case is left for future work due to its complexity in analysis, but I am curious if designing a working algorithm based on the insights in this paper would be feasible at least. Could the authors provide insights on the following: \n\n    (a) How would Algorithm 2 (or a variant) perform with nonlinear models?\n\n    (b) Do the authors believe extending Algorithm 2 to nonlinear models is feasible, and what challenges might arise in the algorithm's design?\n\n2. In line 57, can authors elaborate on why \"Eq. (3) implies that one does not need the nested sampling technique to reduce the bias\" with more details?\n\n3. Suggestions\n\n    (a) **Lines 150 - 151**:  I suggest the authors state Assumption 2.3 as follows: \"... $P_{Y|X}$.  There exist constants such that $C_x, C_y, C_{xx}, C_{yx} > 0$ such that ...\"\n\n    (b) **Line 161**:  I guess it might make more sense to move Assumption 2.4 up to Line 147, right after the sentence \"... pre-collected dataset.\"\n\n    (c) **Page 9**: The authors may want to summarize the information in Lines 315 - 323 in the captions of Figures 3 and 4 for readers' convenience.  Also, it could be helpful to summarize the experimental results in the main text explicitly.\n\n    (d) **Miscellaneous/Potential typos**: \n\n        i) Line 52: $X|Z$ instead of $Z|X$?\n\n        ii) Line 154: remove \"under\"\n\n        iii) Eq. (10) and Line 159: Please consider ending the sentence in Eq. (1) and start a new sentence in Line 159. Also, \"if\" in Line 159 should be capitalized.", "limitations": "This is primarily a theoretical work, and the authors discussed the potential limitations of their assumptions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work provides a simple yet effective algorithmic solution to solve the IVaR problem formulated as a stochastic optimization problem, overcoming challenges highlighted in prior work [MMLR20] and adapting the method in [HZCH20] for streaming settings. This avoidance of the need for nested sampling (=generating batches) is enabled by leveraging the structure of the quadratic loss in the gradient expression.\n\nThe paper is well-organized and presents its core ideas clearly. Section 2 introduces the two-sample oracle assumption, which, while somewhat idealistic, is reasonable for discrete-valued $Z$ as remarked by the authors. Section 3 then transitions to a more realistic one-sample oracle, focusing on linear models and modifying the algorithm and analysis from Section 2 accordingly. All required assumptions and propositions are stated explicitly and clearly.", "weaknesses": "While this work makes several significant theoretical contributions, especially in advancing the analysis, there are areas for potential improvement:\n\n**1. Motivation for IVaR Problems (with Streaming Data)**: The importance of IVaR problems, especially with streaming data, should be highlighted more. Discussing example scenarios in addition to citing references would better motivate and convince readers of the problem's relevance.\n\n**2. Further Experimental Validation**: Although this work is primarily theoretical, augmenting the experiment section with a more comprehensive set of experiments would be beneficial. It would be particularly valuable to see how the proposed algorithms perform on real-world datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer E97U,\n\nThank you for your insightful review. Below we provide our response to your concerns and questions.\n\n### **Weaknesses**\n\n>W1. Motivation\n\n**Response**:\n\nAs mentioned in the general response \"Adv 3 - Emerging applications\", a motivation for developing online/streaming IVaR is that of mobile health applications like Just-In-Time Adaptive Interventions (see, e.g., [TM17]) which also serves as a motivation for the work of [DVB23a]. Our work is directly applicable for several such applications. Taking your suggestion into account, we will be adding a discussion about this application in detail in our revision.\n\n[TM17] Tewari, Ambuj, and Susan A. Murphy. \"From ads to interventions: Contextual bandits in mobile health.\" Mobile health: sensors, analytic methods, and applications (2017): 495-517.\n\n\n>W2. Experimental Validation\n\n**Response**:\n\nPlease see our general response where we have added two real-data experiments. The results show the benefits of the proposed algorithms, thereby supporting the theoretical results.\n\n### **Questions**\n\n> Q1. While Algorithm 1 is...\n\n**Response**:\n\nWe thank the review for asking this insightful question. Please see the explanation under **Non-linear settings** in the general response. We will add the above explanation as a remark in our revision. \n\n>Q2. In line 57...\n\n**Response**:\n\nFor general conditional stochastic optimization, its objective and gradient are of the form \n\n$$F(\\theta) = \\mathbb{E}_{Z} l (\\mathbb{E}\\_{X\\mid Z} [g(\\theta;X)] - \\mathbb{E}\\_{Y \\mid Z} [Y])$$\n\nand \n\n$$\\nabla F(\\theta) = \\mathbb{E}_{Z}[\\nabla\\_{\\theta} \\mathbb{E}\\_{X\\mid Z}[g(\\theta;X)] \\nabla\\_{\\theta} l(\\mathbb{E}\\_{X\\mid Z}[g(\\theta;X)] - \\mathbb{E}\\_{Y\\mid Z} [Y])],$$\n\nwhere $l$ is a non-linear and non-quadratic function. Therefore, $\\nabla_\\theta l$ is non-linear. For the composition of non-linear function and expectation term $\\nabla\\_\\theta l(\\mathbb{E}\\_{X\\mid Z}[g(\\theta;X)] - \\mathbb{E}\\_{Y\\mid Z} [Y])$ for a given $Z$, getting a low-bias estimator requires a large batch of samples from the conditional distribution of $(X,Y)$ given $Z$ for the following observation: $\\|\\nabla\\_\\theta l(\\mathbb{E}\\_{X\\mid Z}[g(\\theta;X)] - \\mathbb{E}\\_{Y\\mid Z} [Y]) - \\mathbb{E}\\nabla\\_\\theta l(\\frac{1}{m}\\sum_{i=1}^m g(\\theta;X_i)- \\frac{1}{m}\\sum_{i=1}^m Y_i)\\|$ $\\leq S_l \\mathbb{E}\\|\\mathbb{E}\\_{X\\mid Z}[g(\\theta;X)]  -\\frac{1}{m}\\sum_{i=1}^m g(\\theta;X_i) + \\frac{1}{m}\\sum_{i=1}^m Y_i- \\mathbb{E}\\_{Y\\mid Z} [Y]\\|=\\mathcal{O}(1/\\sqrt{m})$. Here $S_l$ denotes the Lipschitz smooth parameter. However, when $l$ is just $\\|\\cdot\\|^2$ as in the instrumental variable regression, $\\nabla l$ is linear. Thus the right-hand-side of the above inequality simplifies to $0$, meaning that for any $m$, it is an unbiased estimator. Thus it suffices to use $m=1$ and avoids to use batch.  This observation, while being straightforward in hindsight,  has not been observed in previous work (which all hence used more complicated algorithmic design).\n\n\n>Q3. Suggestions\n\n**Response**:\n\nWe really appreciate your careful reading and insightful suggestions. We will incorporate them in our revision. \n\nWe sincerely hope that our responses have answered your questions and concerns, in which case, we would appreciate if you could raise your scores appropriately. If you have additional questions, please reach out to us during the discussion period and we will be happy to clarify.", "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": "Y3DCauhdsz", "reviewer": "Reviewer_hwGZ", "summary": "The paper shows algorithms for instrumental variable regression that dont need matirx inversions and mini-batches. At the same time, the paper give the rates of convergence.", "questions": "I am curious about how the matrix inversion harm a algorithm performance in this setting.", "limitations": "None", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method offers robust theoretical guarantees and is validated through comprehensive experimental results.", "weaknesses": "None", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer hwGZ,\n\nThank you for your comments. Below we provide our response to your questions.\n\n### **Question**\n\n>Q1. Matrix inversion\n\n**Response:**\n\nPlease kindly refer to Appendix B for a summary table (Table 1) on arithmetic operations complexity per-iteration. Using the method with matrix inversion (DVB23b, v1), it requires $d_x^3+t d_x^2$ arithmetic operations where $d_x$ is the dimension of the input $X$ and $t$ denotes the $t$-th iteration. Using the method in their updated version (DVB23a, v3), the computational and memory complexity per-iteration is still much higher than our methods. This quantifies the inefficiency of matrix-inversion based methods. \n\nWe have also provided real-world experiments demonstrating the improved and efficient performance of our algorithm over other approaches.\n\nWe sincerely hope that our responses have answered your questions and concerns, in which case, we would appreciate if you could raise your scores appropriately. If you have additional questions, please reach out to us during the discussion period and we will be happy to clarify.", "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": "xZjuMqRFt0", "reviewer": "Reviewer_WDCF", "summary": "This paper tackles the instrumental variable regression. The problem setting assumes a model $Y=g_{\\theta^*}(X) + \\epsilon_1$, but unlike the ordinary regression model, there are correlations between $X$ and $\\epsilon_1$. The model assumes in addition an instrument variable $Z$ such that $Y$ and $X$ are independent conditional on $Z$, and $X=h_{\\gamma^*}(Z)+\\epsilon_2$. The target is to estimate $\\theta^*$. The canonical approach is to use the two-stage least square (2SLS) method, where we first regress $X$ on $Z$ and then regress $Y$ on the $\\widehat{X}$ that is estimated by $Z$. \n\nThis paper considers an online setting where samples $(X_t, Y_t, Z_t)$ arrive sequentially. They propose two stochastic gradient descent (SGD) based algorithms. The first algorithm assumes that for each $Z_t$ we can resample $X_t'$ from the conditional distribution of $X | Z=Z_t$. The second algorithm does not make this assumption and can be considered an SGD version of the 2SLS algorithm. The paper provides the L2 convergence guarantee for both algorithms and they design experiments to demonstrate the effectiveness of their algorithms.", "questions": "See \"Weakness\".", "limitations": "See \"Weakness\".", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper is clearly written and contains rigorous theoretical analysis. It presents online algorithms to address the instrumental variable regression problem. Compared to their offline counterparts, these online algorithms are more memory-efficient and computationally stable. The proof of their Theorem 2 introduces an intermediate sequence $\\widetilde{\\theta}_t$ with known dynamic, and evaluates the convergence rate of $|\\theta_t - \\widetilde{\\theta}_t|$. This technique is of separate interest.", "weaknesses": "1.  The contribution of the paper appears marginal. The first algorithm requires data resampling and this limits its applicability. The second algorithm is an intuitive adaption of the 2SLS algorithm to the SGD setting. The theorems are proved in the simple linear setting.\n2. Apart from avoiding matrix inversion, the paper lacks necessary explanations as to why we should prefer an SGD version of 2SLS over the canonical offline 2SLS. It would be beneficial if more content were devoted to the advantages of Algorithm 2 compared to traditional benchmarks. For example, a theoretical comparison with 2SLS or an empirical comparison using real-world data would be helpful.\n3. Could you explain why using two different synthetic settings for Algorithm 1 and Algorithm 2 in the Numerical Experiments section?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WDCF,\n\nThank you for your review. We provide responses to your concerns in 'weaknesses'.\n\n**W1** - We strongly disagree with your view that the paper's contribution is marginal. As noted in Prop 1, Alg. 1 is not restricted to linear models; it can handle non-linear and non-convex cases, including DNNs, without explicitly specifying or estimating the model between $Z$ and $X$. \n\nWe also contest your claim that Algorithm 1's data resampling limits its applicability. Instead, it offers a novel approach for online data collection to avoid forbidden regression issues.\n\nRegarding the proof techniques for Alg 1 (Thm 1), classical SGD convergence methods do not apply directly because the gradient estimator $v(\\theta)$ does not meet the bounded variance  ([Lan20])  or expected smoothness ([KR20]) assumptions. We provide a novel analysis based on weaker statistical assumptions for streaming data compared to those in the optimization literature.\n\nWe now highlight the additional challenges in the proof of Alg. 2 (see, also, the part after Remark 1).\n\n**Challenge 1 (Interaction between iterates):** The major challenge towards the  convergence analysis of $\\\\{\\theta_t\\\\}_t$ lies in the interaction term $\\gamma_t Z_tZ_t^\\top\\gamma_t\\theta_t$ between $\\gamma_t$ and $\\theta_t$ in equation (13). Note that this multiplicative interaction term is neither a martingale-difference sequence not does it have finite variance which could have led to a simpler analysis. This involved dependence between the noise in the stochastic gradient updates for the two stages does not appear in existing problem setups and corresponding analysis of non-linear two time-scale algorithms [MP06,DTSM18,Doa22] (more related references in the paper).\n\n**Challenge 2 (Biased Stochastic Gradient):**\nIn our setting, as shown below, the stochastic gradient in equation (13) evaluated at $(\\theta_t,\\gamma_t)$ is biased unlike existing works on two-time-scale algorithms (see [MP06,DTSM18,Doa22] for example).\n\n$$\n\\begin{aligned}\n&\\mathbb{E}\\_{t,Z_t}[\\gamma_t^\\top Z_t(Z_t^\\top\\gamma_t\\theta_t-Y_t)]=\\mathbb{E}\\_{t,Z_t}[\\gamma_t^\\top Z_t(Z_t^\\top\\gamma_t\\theta_t-Z_t^\\top\\gamma_*\\theta_*)]=\\mathbb{E}\\_{t}[\\gamma_t^\\top\\Sigma_Z(\\gamma_t\\theta_t-\\gamma_*\\theta_*)]\\\\\\\\=&\\gamma_t^\\top\\Sigma_Z\\gamma_t(\\theta_t-\\theta_*)+\\gamma_t^\\top\\Sigma_Z(\\gamma_t-\\gamma_*)\\theta_* \\neq \\gamma_{\\ast}^\\top\\Sigma_Z\\gamma_*(\\theta_t-\\theta_*) =\\nabla_\\theta F(\\theta_t).\n\\end{aligned}\n$$\n\n**Challenge 3 (No Bounded Variance Assumption of Stochastic Gradient):** \nWe do not assume boundedness of $\\{\\theta_t\\}$ iterates unlike existing works (see Assumption 1 in [WZZ21], Assumption 2 in [XL21] and Theorem 2 in [MSBPSS09]). This assumption ensures uniform boundedness of the variance of the stochastic gradient requiring a simpler analysis compared to us.\n\nResolving these issues firstly require proving that $\\mathbb{E}[\\|\\theta_t\\|_2^4]$ is bounded (Lemma 5) which is non-trivial and requires carefully chosen stepsizes satisfying\n\n$\\sum_{t=1}^\\infty(\\alpha_t^2+\\alpha_t\\sqrt{\\beta_t})<\\infty.$\n\nUsing this bound on $\\mathbb{E}[\\|\\theta_t\\|_2^4]$, we prove the convergence of sequence $\\delta_t\\coloneqq \\theta_t-\\tilde{\\theta}_t$, the error between true iterates and auxiliary iterates we defined. This requires a novel proof technique where we first provide an intermediate bound (see Lemma 6)  and then progressively sharpen to a tighter bound (see Lemma 7). \n\n[MSBPSS09] H. Maei, C. Szepesvari, S. Bhatnagar, D. Precup, D. Silver, and R. Sutton. Convergent temporal-difference learning with arbitrary smooth function approximation. NeurIPS 2009\n\n[Lan20] G. Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020\n\n[KR20] A. Khaled and P. Richtárik. Better theory for SGD in the nonconvex world.\n\n**W2** - Alg. 2, the SGD version of 2SLS is applicable for various emerging applications of online/streaming IVaR, i.e., mobile health applications like Just-In-Time Adaptive Interventions (e.g., [TM17],[DVB23a]). Comparing to other online IVaR methods, ours achieve a much better per-iteration computational and memory costs as illustrated in Appendix B Table 1. \n\nFrom an algorithmic perspective, integrating non-linear models into offline 2SLS requires additional optimization, typically handled by Stochastic Gradient Descent (SGD) methods. Recent research in both machine learning (e.g., [VSH+16, DVB23a]) and economics (e.g., [CLL+23]) has focused on developing online methods for IVaR.  In our general response, we outlined the specific non-linear models which could be handled by our Alg. 2. Note that Alg. 1 already handles non-linear models (see Prop 1). We believe our work significantly advances streaming IV regression and expect further research to extend our methodology to more general non-linear settings.\n\nIn addition, we added experiments of Alg 2 on real-world dataset. Please see the general response and the attached PDF for the results. \n\n**W3** - Alg. 1 and Alg. 2 have different settings (oracles, assumptions, etc.). In Alg. 1, we assume that we have access to 2-sample oracles (i.e., 2 independent samples $X, X'$ can be drawn given $Z$), and the algorithm can handle the cases when $g(\\theta; X)$ is linear (Thm 1) and non-linear (Prop 1). Hence we consider both linear ($\\phi(s) = s$) and non-linear ($\\phi(s) = s^2$) settings in the experiments of Alg. 1. In Alg. 2, we mainly consider the case when we only have access to 1-sample oracle (i.e., 1 sample $X$ can be drawn given $Z$), and the model is linear.\n\n[TM17] A. Tewari, and S. A. Murphy. \"From ads to interventions: Contextual bandits in mobile health.\" Mobile health: sensors, analytic methods, and applications (2017)\n\nWe sincerely hope that our responses have answered your questions and concerns, in which case, we would appreciate if you could raise your scores appropriately. If you have additional questions, please reach out to us during the discussion period and we will be happy to clarify.", "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": "MCra1UTFm2", "reviewer": "Reviewer_AcA7", "summary": "This paper proposes two stochastic optimization algorithms for instrumental variable regression (IVaR) that operate on streaming data without requiring matrix inversions or mini-batches. When the true model is linear, the paper proves that TOSG-IVaR converges at a rate of $\\mathcal{O}(\\log T/T)$ and OTSG-IVaR at a rate of $O(1/T^{1 - \\iota})$ for any $\\iota > 0$, where $T$ is the number of iterations. The proposed approaches avoid the \"forbidden regression\" problem of having to estimate the nuisance parameter relating $Z$ and $X$. Numerical experiments validate the theoretical results.", "questions": "The theoretical analysis focuses on the linear model setting. What are the challenges in extending the analysis to non-linear models, and what kind of assumptions or modifications would be required?", "limitations": "The limitations and future works are thoroughly discussed in the paper. Besides from that, I do not see more limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper provides a novel perspective on instrumental variable regression (IVaR) by formulating it as a conditional stochastic optimization problem, which allows for the development of fully online algorithms that operate on streaming data. \n\n2. The proposed algorithms, TOSG-IVaR and OTSG-IVaR, avoid the need for matrix inversions and mini-batches, making them computationally efficient and suitable for large-scale datasets. \n\n3. By directly solving the conditional stochastic optimization problem, the algorithms avoid the \"forbidden regression\" issue and the need to approximate a dual variable over a continuous functional space, which is a limitation of prior minimax formulations.\n\n4. This paper is well-structured. The background, contributions, and limitations are explicitly presented. The proof techniques is clearly summarized and the experimental results do support the performance of both algorithms.", "weaknesses": "1. The paper does not provide a comprehensive comparison with existing IVaR methods, particularly in terms of computational complexity and empirical performance on real-world datasets. Such a comparison would strengthen the paper's contributions. \n\n2. The assumptions made for the theoretical analysis, such as the identifiability conditions and moment assumptions, may be restrictive in some practical settings. A discussion on the robustness of the proposed algorithms under violations of these assumptions would be valuable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer AcA7, \n\nThank you for your insightful review. Here we provide response to your questions and concerns.\n### **Weaknesses**\n**W1** - Please note that many existing IV methods are not applicable for online/streaming setting. We also wish to clarify that in Appendix B Table 1 we have compared the computational complexities (specifically, per-iteration arithmetic and memory complexity) of our method to that form [DVB23b] (which is a recently proposed online/streaming IV method) and demonstrated our benefits. In our experimental results (Section 4), we have also compared our algorithms against that in [DVB23b] and demonstrated the benefits.  In particular, we wish to highlight that our algorithm converges much faster. \n\nFinally, as a part of the rebuttal, we have provided empirical results on real-world dataset as well. Compared to [DVB23b], our method also performs better on the considered real-world datasets.\n\nIf you are aware of another IVaR method that is applicable to the online/streaming setting that we have missed in our literature review, we would greatly appreciate if you could point it out specifically to us. We will be happy to compare against that in our revision as well. Thank you in advance.  \n\n**W2** - First, we would like to point out that the identifiability conditions and moment assumptions we make are rather standard in the literature and can be satisfied in multiple cases (see, e.g., Lemma 1). It is also satisfied in our simulation experiments. Further relaxations of the moment and identifiability conditions have indeed been made in the literature in the offline settings. Taking your suggestion into account, we will add a discussion to them in our revision. A detailed study of developing algorithms and sample complexity results under relaxed assumptions is truly beyond the scope of this work.\n\nRegarding the robustness aspect, we point out under the setting in Section 4, identifiability conditions (Assumption 2.1) can be easily verified. Moment assumptions (Eq. (5), (6), (7), (8)) also hold:\n- (5)$$\\begin{aligned}&\\mathbb{E}\\Big[\\|X'X^\\top-\\mathbb{E}\\_{X|Z}[X]\\mathbb{E}\\_{X|Z}[X]^\\top\\|^2\\Big]\\\\\\\\\n=&\\mathbb{E}\\Big[\\|c(h'+\\epsilon_x')\\phi(\\gamma_{\\ast}^\\top Z)^\\top+c\\phi(\\gamma_{\\ast}^\\top Z)(h+\\epsilon_x)^\\top+c^2(h'+\\epsilon_x')(h+\\epsilon_x)^\\top-c\\mathbf{1}\\_{d_x}\\phi(\\gamma_{\\ast}^\\top Z)^\\top-c\\phi(\\gamma_{\\ast}^\\top Z)\\mathbf{1}\\_{d_x}^\\top-c^2\\mathbf{1}\\_{d_x}\\mathbf{1}\\_{d_x}^\\top\\|^2\\Big]\\\\\\\\\n\\leq&3\\mathbb{E}\\Big[\\|c((h'+\\epsilon_x')-\\mathbf{1}\\_{d_x})\\phi(\\gamma_{\\ast}^\\top Z)^\\top\\|^2\\Big]+3\\mathbb{E}\\Big[\\|c\\phi(\\gamma_{\\ast}^\\top Z)((h+\\epsilon_x)-\\mathbf{1}\\_{d_x})^\\top\\|^2\\Big]+3\\mathbb{E}\\Big[\\|c^2((h'+\\epsilon_x')(h+\\epsilon_x)^\\top-\\mathbf{1}\\_{d_x}\\mathbf{1}\\_{d_x}^\\top)\\|^2\\Big]\\\\\\\\=&\\mathcal{O}(c^2d^2+c^4d^2).\n\\end{aligned}$$\n- (6)$$\\begin{aligned}&\\mathbb{E}\\Big[\\|YX'-\\mathbb{E}\\_{Y|Z}[Y]\\mathbb{E}\\_{X|Z}[X]\\|^2\\Big]\\\\\\\\=&\\mathbb{E}\\Big[\\|(\\theta_{\\ast}^\\top X+c\\cdot(h_1+\\epsilon_y))X'-(\\theta_{\\ast}^\\top\\mathbb{E}\\_{X|Z}[X]+c)\\mathbb{E}\\_{X|Z}[X]\\|^2\\Big]\\\\\\\\\\leq&3\\mathbb{E}\\Big[\\|(X'X^\\top-\\mathbb{E}\\_{X|Z}[X]\\mathbb{E}\\_{X|Z}[X]^\\top)\\theta_*\\|^2\\Big]+3c^2\\mathbb{E}\\Big[\\|(h_1+\\epsilon_y-1)\\phi(\\gamma_{\\ast}^\\top Z)\\|^2\\Big]+3c^4\\mathbb{E}\\Big[\\|(h_1+\\epsilon_y)(h'+\\epsilon_x')-\\mathbf{1}\\_{d_x}\\|^2\\Big]\\\\\\\\=&\\mathcal{O}(\\|\\theta_*\\|^2(c^2d^2+c^4d^2)+c^2d_x^2+c^4).\\end{aligned}$$\n- (7)$$\\begin{aligned}&\\mathbb{E}\\Big[\\|\\mathbb{E}\\_{X\\mid Z}[X]\\cdot\\mathbb{E}\\_{X\\mid Z}[X]^\\top-\\mathbb{E}_Z\\Big[\\mathbb{E}\\_{X\\mid Z}[X]\\cdot\\mathbb{E}\\_{X\\mid Z}[X]^\\top\\Big]\\|^2\\Big]\\\\\\\\\n\\leq&3\\mathbb{E}\\Big[\\|\\phi(\\gamma\\_{\\ast}^\\top Z)\\phi(\\gamma\\_{\\ast}^\\top Z)^\\top-\\mathbb{E}\\_{Z}\\Big[\\phi(\\gamma\\_{\\ast}^\\top Z)\\phi(\\gamma\\_{\\ast}^\\top Z)^\\top\\Big]\\|^2\\Big]+3c^2\\mathbb{E}\\Big[\\|\\mathbf{1}\\_{d_x}\\phi(\\gamma\\_{\\ast}^\\top Z)^\\top-\\mathbb{E}\\_Z\\Big[\\mathbf{1}\\_{d_x}\\phi(\\gamma\\_{\\ast}^\\top Z)^\\top\\Big]\\|^2\\Big]+3c^2\\mathbb{E}\\Big[\\|\\phi(\\gamma\\_{\\ast}^\\top Z)\\mathbf{1}\\_{d_x}^\\top-\\mathbb{E}\\_{Z}\\Big[\\phi(\\gamma\\_{\\ast}^\\top Z)\\mathbf{1}\\_{d_x}^\\top\\Big]\\|^2\\Big]\\\\\\\\\n=&\\mathcal{O}(d_z+c^2d_xd_z).\\end{aligned}$$\n- (8)$$\\begin{aligned}&\\mathbb{E}\\Big[\\|\\mathbb{E}\\_{Y\\mid Z}[Y]\\cdot\\mathbb{E}\\_{X\\mid Z}[X]-\\mathbb{E}\\_Z\\Big[\\mathbb{E}\\_{Y\\mid Z}[Y]\\cdot\\mathbb{E}\\_{X\\mid Z}[X]\\Big]\\|^2\\Big]\\\\\\\\\\leq&2\\mathbb{E}\\Big[\\|(\\mathbb{E}\\_{X\\mid Z}[X]\\cdot\\mathbb{E}\\_{X\\mid Z}[X]^\\top-\\mathbb{E}\\_{Z}\\Big[\\mathbb{E}\\_{X\\mid Z}[X]\\cdot\\mathbb{E}\\_{X\\mid Z}[X]^\\top\\Big])\\theta\\_{\\ast}\\|^2\\Big]+2c^2\\mathbb{E}\\Big[\\|\\phi(\\gamma\\_{\\ast}^\\top Z)-\\mathbb{E}\\_{Z}\\Big[\\phi(\\gamma\\_{\\ast}^\\top Z)\\Big]\\|^2\\Big]\\\\\\\\=&\\mathcal{O}((d_z+c^2d_xd_z)\\|\\theta_*\\|^2+c^2d_z).\n\\end{aligned}$$\n\nIn particular, the constant $c$ represents the strength of endogeniety and as shown above we could precisely characterize how this strength of endogeniety affects the number of iterations (or samples in the streaming setting).  This demonstrates an instance of quantifying the robustness of the made assumptions (here the robustness is wrt to the constant $c \\in (0,\\infty)$. In the general response, we have also added a detailed discussion of Algorithm 2's performance under certain non-linear modeling assumptions, which is yet another robustness study of the proposed algorithms.\n\n### **Questions**\n\n**Q1** - We would like to point out Proposition 1 extends the linear setting to the non-linear setting, in which we require boundedness of the variance of the gradient estimator $v(\\theta)$. Relaxing the boundedness of the variance condition while still achieving convergence under the non-linear setting is challenging and left as our future work. Please also see the explanation under **Non-linear settings** in general response.\n\nWe sincerely hope that our responses have answered your questions and concerns, in which case, we would appreciate if you could raise your scores appropriately. If you have additional questions, please reach out to us during the discussion period and we will be happy to clarify.", "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:
Dear reviewers,

Thank you for your comments and questions. Below we provide our general response. We first present real-data experiments, and then re-emphasize points which were potentially overlooked.

### **Real Data Examples** 
We illustrate Alg. 2 on 2 datasets: Angrist and Evans (1998) Children/Parents' Labor Supply Data and U.S.Portland Cement Industry Data. Please see the global response PDF (attached) for the plots and experimental details.
### **Advantages of our approach**
 - Avoiding "forbidden regression": Note that one of the main benefits of the online approach to IVaR that we discovered in our work is that of avoiding "forbidden regression" under the 2-sample oracle. To our knowledge, this solution is not available for any existing online and offline procedures in the current literature, and provides a novel data-collection mechanism for practitioners. 

 - Computational benefits: SGD-type algorithms have played a crucial role in scaling up statistical ML methods. Recent works ML (e.g., [VSH+16, DVB23a]) and economics (e.g., [CLL+23]) develop online IVaR methods. Our algorithms have state-of-the-art computational complexities (Appendix B) for online IVaR in linear settings, even compared to offline procedures like 2SLS. 

 - Emerging applications: Another motivation for developing streaming IVaR is mobile health applications like Just-In-Time Adaptive Interventions (see, [TM17] and [DVB23]). Our work is directly applicable for several such applications. We will add a discussion about these applications in our revision.

[TM17] A. Tewari, and S. A. Murphy. "From ads to interventions: Contextual bandits in mobile health." Mobile health: sensors, analytic methods, and applications (2017): 495-517.

### **Non-linear settings**

Our work is not restricted to just the linear setting. For Alg. 1, Prop. 1 extends the results to the non-linear setting.

**For Alg. 2, it can be immediately applied to the setting where the relation between $X$ and $Z$ is non-linear.** Consider the model:
\begin{align*}
Y=\theta_{\ast}^\top X+\epsilon_1\quad\text{with}\quad X=h_{\gamma_*}(Z)+\epsilon_2
\end{align*}

### **Unbiasedness of the Alg. 2 output** 

Assume that one can learn $h_{\gamma_*}$ efficiently, i.e., say we have $h_{\gamma_t}\approx h_{\gamma_*}$ for some large $t$ (see below for the required conditions). Considering the update for $\theta_t$ in Algorithm 2 (Eq. (13)), we have
$$\theta_{t+1}=\theta_t-\alpha_{t+1} h_{\gamma_t}(Z_t)(h_{\gamma_t}(Z_t)^\top \theta_t-Y_t)\approx \theta_t-\alpha_{t+1} h_{\gamma_*}(Z_t)(h_{\gamma_*}(Z_t)^\top \theta_t-Y_t).$$
It is easy to see that the limit point $\theta_\infty$ of this update will satisfy, $$\mathbb{E}[h_{\gamma_*}(Z)h_{\gamma_*}(Z)^\top]\theta_\infty= \mathbb{E}[h_{\gamma_*}(Z)h_{\gamma_*}(Z)^\top]\theta_*$$
which implies that $\theta_t$ is an unbiased estimator of $\theta_*$ as long as $\mathbb{E}[h_{\gamma_*}(Z)h_{\gamma_*}(Z)^\top]$ is invertible (Assumption 2.2).

### **Alg. 2 convergence proof intuition**
In the proof of Thm. 2, the major challenge is to control the interaction term $\gamma_t Z_tZ_t^\top\gamma_t\theta_t$. We use Lemma 3 which establishes the convergence rate of $\mathbb{E}[\|\gamma_t-\gamma_*\|^2]$. Analogously, in the nonlinear setting, we need to prove the convergence of $\gamma_t$ to $\gamma_*$ or $h_{\gamma_t}(Z)$ to $h_{\gamma_*}(Z)$. This is possible when the loss function $\mathbb{E}[\|X-h_{\gamma}(Z)\|^2]$ is strongly-convex, or satisfies Polyak-Łojasiewicz (PL) inequality [KNS16]. This allows for considerable flexibility in the model choices including basis expansion based non-linear methods and wide Neural Networks [LZB22]. Since the update equation for $\gamma_t$ (Eq (14)) does not involve $\theta_t$, the rest of the proof follows by similar techniques except for the obvious changes required due to the above modification, e.g., the term $\gamma_{\ast}^\top\Sigma_Z\gamma_*$ will be replaced by $\mathbb{E}[h_{\gamma_*}(Z)h_{\gamma_*}(Z)^\top]$.


[KNS16] H. Karimi, J. Nutini, and M. Schmidt. "Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition." In ECML PKDD 2016.

[LZB22] C. Liu, L. Zhu, and M. Belkin. "Loss landscapes and optimization in over-parameterized non-linear systems and neural networks." Applied and Computational Harmonic Analysis 59 (2022): 85-116.

Now, consider the case where the upper level is non-linear, i.e., 
\begin{align*}
    Y=g_{\theta_*}(X)+\epsilon_1\quad\text{with}\quad X=\gamma_{\ast}^\top Z+\epsilon_2.
\end{align*}
In this case, the lower level problem can be solved efficiently as it is a simple linear regression problem. For brevity, assume that $\gamma_*$ is known. In that case, the update for $\theta_t$ in Alg. 2 takes the following form.
\begin{align*}
    \theta_{t+1}=\theta_t-\alpha_{t+1}\nabla g_\theta(Z_t^\top\gamma_*)(g_{\theta}(Z_t^\top\gamma_*)-Y_t).
\end{align*}
Under suitable convergence conditions, this update finds the root of $$\mathbb{E}[\nabla g_\theta(Z^\top\gamma_*)(g_\theta(Z^\top\gamma_*)-Y)]=0,$$ or equivalently, the root of,
\begin{align*}
    &\mathbb{E}[\nabla g_\theta(Z^\top\gamma_*)(g_\theta(Z^\top\gamma_*)-g_{\theta_*}(Z^\top\gamma_*+\epsilon_2)-\epsilon_1)]=0\\
    &\mathbb{E}[\nabla g_\theta(Z^\top\gamma_*)g_\theta(Z^\top\gamma_*)]=\mathbb{E}[\nabla g_\theta(Z^\top\gamma_*)g_{\theta_*}(Z^\top\gamma_*+\epsilon_2)].
\end{align*}
It is easy to see that for general non-linear $g$, $\theta=\theta_*$ may not be a solution to the above equation, i.e., Alg. 2 will find a biased solution. This demands a modified version of Alg. 2 involving an additional debiasing step. As the analysis of Alg. 2 is already quite challenging for the model where the upper layer is linear (see "Proof Techniques" after Remark 1 in the paper and our reply to Reviewer WDCF), we defer the analysis of the case where $Y$ depends non-linearly on $X$ to the future work.

Meta-review: Four reviewers have reviewed the paper, and their overall evaluation is positive. I concur with their assessment and believe the paper makes a strong contribution with compelling results. Two reviewers requested additional experiments and comparisons, to which the authors have responded satisfactorily. I strongly recommend that the authors include these additional simulations in the final version of the paper.
Decision: Accept (poster)