Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data

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.

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. 2. 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. 3. 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. 4. 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. 2. 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.

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?

Rating

6

Confidence

2

Soundness

3

Presentation

4

Contribution

2

Limitations

The limitations and future works are thoroughly discussed in the paper. Besides from that, I do not see more limitations.

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$. This 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.

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. 2. 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. 3. Could you explain why using two different synthetic settings for Algorithm 1 and Algorithm 2 in the Numerical Experiments section?

Questions

See "Weakness".

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

See "Weakness".

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.

Strengths

The proposed method offers robust theoretical guarantees and is validated through comprehensive experimental results.

Weaknesses

None

Questions

I am curious about how the matrix inversion harm a algorithm performance in this setting.

Rating

5

Confidence

1

Soundness

3

Presentation

3

Contribution

3

Limitations

None

Summary

This paper proposes and analyzes on-line algorithms for instrumental variable regression (IVaR) with streaming data. Specifically, the authors consider the model: $Y = g_{\theta^*}(X) + \epsilon_1$
 where the covariate $X$ and noise $\epsilon_1$ are possibly correlated, but an instrumental variable $Z$ is available that satisfies: $X = h_{\gamma^*}(Z) + \epsilon_2$
 with $\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): $Minimize_g F(g) := E_Z E_{Y|Z} [ ( Y - E_{X|Z} [g(X)])^2 ].$ Considering 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): $\nabla F(\theta) = E_Z[ (E_{X|Z}[g(\theta;X)] - E_{Y|Z}[Y]) \cdot \nabla_{\theta} E_{X|Z}[g(\theta; X)]].$ This 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.

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. The 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: **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. **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.

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: (a) How would Algorithm 2 (or a variant) perform with nonlinear models? (b) Do the authors believe extending Algorithm 2 to nonlinear models is feasible, and what challenges might arise in the algorithm's design? 2. 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? 3. Suggestions (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 ..." (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." (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. (d) **Miscellaneous/Potential typos**: i) Line 52: $X|Z$ instead of $Z|X$? ii) Line 154: remove "under" 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.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

This is primarily a theoretical work, and the authors discussed the potential limitations of their assumptions.

Response to the Authors' Rebuttal

I thank the authors for addressing my concerns and questions. I find most of their responses satisfactory, and would like to encourage them to incorporate the explanations and remarks into the revision. However, I am still not clearly seeing how Algorithm 2 can be immediately applied to the scenario where the relationship between $X$ and $Z$ is non-linear, as the authors claim. Specifically, the update rules in Eqs. (13) and (14) -- which stem from Eq. (11) and include an additional modification trick to promote stability as discussed in Lines 220 -- 226 -- seem to rely on the linear model assumption. Thus, it is unclear to me how these would translate to the non-linear model setting described by the authors, namely, the setting where $Y = {\theta^*}^{\top} X + \epsilon_1$ with $X = h_{\gamma^*}(X) + \epsilon_2$. I believe the update rule should involve $\nabla h_{\gamma_t}$ and possibly a similar modification to promote algorithmic stability. Could you please clarify the update rules for this setting by specifying the counterparts of Eqs. (13) and (14), and any necessary modifications (if needed) that corresponds to replacing $g(\theta_t, X_t) = X_t^{\top} \theta_t$ with $Z_t^{\top} \gamma_t \theta_t$ in the linear setting?