notesum.ai

Published at April 24

Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data

NeurIPS

Released Date: April 24, 2024

Authors: Xuxing Chen¹, Abhishek Roy², Yifan Hu³, Krishna Balasubramanian

Aff.: ¹Department of Mathematics, University of California, Davis; ²Halıcıoglu Data Science Institute, University of California, San Diego; ³College of Management, EPFL; Department of Computer Science, ETH Zurich

Arxiv: https://openreview.net/pdf/43a926a61c18c89e80089a783c8d885ad119771d.pdf

Algorithm	Memory cost	Arithmetic Operations
O2SLS (Della Vecchia and Basu, 2023, v1)	$t(d_{x}+d_{z})+d_{z}d_{x}+d_{x}$	$\mathcal{O}(d_{x}^{3}+td_{x}^{2}+td_{x}d_{z})$
O2SLS (Della Vecchia and Basu, 2024, v3) (Sec. A)	$d_{x}^{2}+d_{z}^{2}+d_{z}d_{x}+d_{x}$	$\mathcal{O}(d_{x}^{2}+d_{z}^{2}+d_{z}d_{x})$
TOSG-IVaR (our Alg 1)	$d_{x}$	$\mathcal{O}(d_{x})$
OTSG-IVaR (our Alg 2)	$d_{x}d_{z}+d_{x}$	$\mathcal{O}(\min(d_{x}^{2},d_{z}^{2})+d_{z}d_{x})$