Adaptive Principal Component Regression with Applications to Panel Data
Authors: Anish Agarwal
Keegan Harris
Justin Whitehouse
Steven Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: adaptive data collection
principal component regression
error-in-variables regression
panel data
synthetic controls
synthetic interventions
causal inference
TL;DR: We derive adaptive bounds for online (regularized) principal component regression, and apply them to the problem of unit-specific counterfactual estimation under different interventions in panel data settings.

Abstract: Principal component regression (PCR) is a popular technique for fixed-design error-in-variables regression, a generalization of the linear regression setting in which the observed covariates are corrupted with random noise. We provide the first time-uniform finite sample guarantees for online (regularized) PCR whenever data is collected adaptively. Since the proof techniques for PCR in the fixed design setting do not readily extend to the online setting, our results rely on adapting tools from modern martingale concentration to the error-in-variables setting. As an application of our bounds, we provide a framework for counterfactual estimation of unit-specific treatment effects in panel data settings when interventions are assigned adaptively. Our framework may be thought of as a generalization of the synthetic interventions framework where data is collected via an adaptive intervention assignment policy.

Adaptive Principal Component Regression with Applications to Panel Data
Anish Agarwal" Department of IEOR Columbia University
Keegan Harris
Justin Whitehouse
School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 keeganh@cs.. cmm.cmm......oo edu
School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 jwhiteho&cs. cmu edu
New York, NY 10027 aa51 19m19ccmcmmmbaa edu
Zhiwei Steven Wu School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 zhiweivêcs cmu cmu.edu edu
Abstract
Principal component regression (PCR) is a popular technique for fixed-design error-in-variables regression, generalization of the linear regression setting which the observed covariates are corrupted with random noise. We provide the first time-uniform finite sample guarantees for online (regularized) PCR whenever data is collected adaptively. Since the proof techniques for analyzing PCR in the fixed design setting do readily extend the online setting, results rely on adapt- ing tools from modern martingale concentration to the As application of our bounds, we provide framework for experiment design panel data settings when interventions are assigned adaptively. Our framework may thought of generalization of the synthetic control and synthetic interventions frameworks, where data is collected via an adaptive intervention assignment policy.
setting.
Introduction
An omnipresent task in machine learning, statistics, and econometrics is that of making predictions about outcomes of interest given an action and conditioned on observable covariates. An often overlooked aspect of the prediction task is that in many settings the learner only has access to imperfect observations the covariates, due to e.g. measurement error or inherent randomness problem domain. Such settings sometimes formulated as error error-in-varian in-variablee regression: learner is given access to a collection data (Zn. an Yn)221, where Z,, E RR' are the observed covariates, a, E {1, .1.....24 A} is the action taken, and Y, E R is the outcome for each observation n. Typically, the outcomes are assumed to he generated by a linear model Y, == (0(a.), ), X,,) + S,, and 7,, == X, +en where X,, Rdd are the true covariates, En E R2d is the covariate noise, ((a,) E Rd is an unknown slope vector associated with action an,, and &n E 1R is the response noise. Note that the learner does not get to see the true covariates X,. Observe that when e,, = we recover the traditional linear regres- sion setting. Such an error-in-vaan -oanrii--ariillss model can encompass many forms of data corruption including measurement error, missing values, discretization, and differential privacy see [10, 5] for details.
Our point of departure from previous work is that we allow the sequence of data (Zn. an Ya)211 to be chosen adaptively. In other words, we provide bounds for learning the prror-in-varialle regres-
Forr part of this work, Anish was postdoc Amazon, Core AI.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

sion setting when the data seen at the current round n is allowed to depend on the previously-seen
data (Zm, Om, Yn) Sm Adaptive data collection occurs when the choices of future observations can depend on the inference from previous data, which is common in learning paradigms such as multi-armed bandits [58, 78], active learning [74], and time-series analysis [76, 36]. Similar to prior work on adaptive data collection that shows that valid statistical inference can be done when the true covariates are observed [34, 67, 43, 91, 92], our work provides the first time-uniform finite sample guarantees for uutor-in-variable regression using adaptively collected data.
Concretely, we focus on analyzing principal component regression (PCR) [54], a method that has been shown to be effective for learning from noisy covariates [10, 7] and a central tool for learning from panel data [8, 5, 7]. At high level, PCR "de-noises" the sequence of observed covariates (Zn 221 as (Zn 22 by performing hard singular value thresholding, after which linear model is learned using the observed outcomes 221) and the denoised covariates (Zn)22 See Section 3.2 for further technical background on PCR.
1.1 Contributions
1. We derive novel time-uniform bounds for an online variant of regularized PCR when the sequence of covariates is chosen adaptively. The techniques used to derive bounds for PCR in the fixed-sample regime [7] do not extend to the setting in which data is collected adaptively; thus, we require new tools and ideas to obtain our results. Specifically, our results rely applying recent advances in martingale concentration [50, 51], as well as more classical results on self-normalized concentration [3, 32, 33] which are commonly applied online regression problems, to the error-in-variables setting. As example of the bounds we obtain, consider the task of estimating the underlying relationship ((a) between true (i.e. noiseless) covariates and observations, given access adaptively-chose noisy covariates and their corresponding actions and observations. The fz estimation error of the adaptive PCR estimator 0n (a) can be bounded as
110% (a) - 0())) (0
with high probability, where sur, (a) is the signal-to-noise ratio associated with action a at round (Definition 3.5). measure of how well the true covariates stand out from the noise, x (a) is the condition number of the true covariates. Intuitively, if sur, (a) is high the true covariates can be well-separatee from the noise, and therefore PCR accurately estimates ((a) as long as the true covariates are well-conditioned.
Despite the harder setting we consider, our PCR bounds for adaptively collletee data largely match the bounds currently known for the fixed sample regime, and even improve upon them in two important ways: (1) Our bounds are computable, i.e. they depend on known constants and quantities available to the algorithm. (2) Unlike Agarwal et al. [7], our bounds do not depend on the fi-norm of O(a), i.e., we do not require approximate sparsity of ((a) for the bounds to imply consistency. This is important because PCR is a rotationally-invarin
algorithm, and so its performance guarantees should not depend on the orientation of the basis representation of the space to be learned. The price we pay for adaptivity is that sur, (a) is defined with respect to bound on the total amount of noise seen by the algorithm so far, instead of just the noise associated with the rounds that is taken. As a result, our bound for 0, (a) may not be tight if is seldomly selected.
2. We apply our PCR results to the problem of online experiment design with panel data. In panel data settings, the learner observes repeated, noisy mcasurements of units (c.g. medical patients, subpopulations, geographic locations) under different interventions (c.g. medical treatments, discounts, socioeconomic policies) over time. This an ubiquitous method of data collection, and as result, learning from panel data has been the subject of significant interest in the econometries and statistics communities (see Section 2). A popular framework for learning from panel data is synthetic control (SC) [1, 2], which uses historical panel data to estimate counterfactual unit measurements under control. Synthetic interventions (SI) [8] is recent generalization of the SC framework which allows for counterfactual estimation under treatment, in addition to control. By leveraging online PCR, we can perform counterfactual estimation of unit-specific treatment effects under both

---

treatment and control, as in the SI framework. However, unlike the traditional SI framework, we are the first establish statistical rates for counterfactual unit outcome estimates under different interventions while allowing for both units and interventions to be chosen adaptively. Such adaptivity may naturally occur when treatments are prescribed to new units based on the outcomes of previous units. For example, this is the case when the intervention chosen for each unit is the one which appears to be best based on observations in the past.
2 Related work
Error-in-variable regression There is a rich literature on arror-in-variablee regression (e.g. [42, 57, 28, 44, 84, 47,47, 41J). with research focusing on topics such high-dimensional [62, 56, 31, 72] and Bayesian settings [70, 81, 40J. Principal component regression (PCR) [54, 22, 10, 7] is a popular method for error-in-variables regression. The results of Agarwal et al. [7] are of particular relevance to us, as they provide finite sample guarantees for the fixed design (i.c. non-adaptive) version of the setting we consider.
Self-normalized concentration There has been recent uptick in the application of self normalzdddl martingale concentration to online learning problems. In short, celf-normalized concentration aims to control the growth of processes that have been normalized by a random, empirical, measure of accumulated variance [32, 33, 50, 51, 88]. Self-normalized concentration has led to breakthroughs in wide-ranging areas of machine learning such as differential privacy [85, 86), PAC-Bayesian learning [30], convex divergence estimation [63], and online learning [87, 29, 3]. Of particular importance for our work are the results of Abbasi- Yadkori et al. [3], which leverage self-normalized concentration results for vector-valued processes [32, 33J to construct confidence ellipsoids for online regression tasks. We take inspiration from these results when constructing our estimation error bounds for PCR in the sequel.
Learning in panel data settings Our application to panel data builds off of the SI framework [8, 91, which itself is a generalization of the canonical SC framework for learning from panel data 2,,2,52, 52, 35, 17, 60, 89, 13, 14, 59, 16, 20, 23, 27, 39I. In both frameworks, a latent factor model often used to encode structure between units and time-steps [25, 61, 15, 18, 19, 68, 64, 65). Specifically, it is assumed that unit outcomes are the product of unit- and time//nterenntion-secciie latent factors, which capture the heterogeneity across time-steps, units, and interventions, and allows for the estimation of unit-specific counterfactuals under treatment and control. Other extensions of the SI framework include applications in biology [79], network effects [11], combinatorially-mann interventions [4], and intervening under incentives [45, 66]. Finally, there is a growing line of work at the intersection of online learning and panel data. Chen [26] views the problem of SC as an instance of online linear regression, which allows them to apply the regret guarantees of the online learning algorithm follow-the-eaader [55] to show that the predictions of SC are comparable to those of the best-in pest-in-hindsight weighted average of control unit outcomes. Farias et al. [38] build the SC framework to estimate treatment effects adaptive experimental design, while minimizing the regret associated with experimentation. The results of Farias et al. [38] are part of growing line of work on counterfactual estimation and experimental design using
bandits [69, 77, 90, 24].
3 Setting and background
Notation We use boldface symbols to represent matrices. For N E N, we use the shorthand [N] : {I,...,N] NJ. Unless specified otherwise, ||||| denotes the f--norm of vector v, and ||A lop the operator norm of matrix A. We use diag(a),...
a&) to represent a k x k diagonal matrix with entries ai,..., (gg. For two numbers a, b E IR we use A b shorthand for min(a, b). and V b to mean max(a, b}. Finally, gd-1 denotes the d-dimensional unit sphere.
3.1 Problem setup
We now describe our error-in-varialle setting. We consider learner who interacts with an environ- ment over a sequence of rounds. At the start of each round n 2 1, the environment generates covariates X, E W* C. IRd, where W* is low-dimensional linear subspace of dimension dim(W") < d.
3

---

We assume that r (but not W*) is known to the learner. Such "low rank" assumptions are reasonable whenever, e.g. data is generated according dimensional statistical settings [53, 12, 48]. As we will see in Section 5, analogous assumptions are often also made in panel data settings. The learner then observes noisy covariates Z,, == X,, + Cn. where Cn E Rd is a random noise vector. Given Zn the learner selects an action an E [A] and observes Yn ;= (0(an). Xn) + Sn. where &n is random noise and ((a) for a E [A] are unknown slope vectors in W that parameterize action choices such that [[0(a)]l2 S L for some L E R. We require that the covariate noise is "well-behaved" according to one of the two the following assumptions:
latent factor model, a popular assumption in high-
A Assumption 3.1 (SubGaussian Covariate Noise), For any n 2 1, the noise variable en satisfies (a) en is o-subGaussian, (b) Ee,- = 0, and (c) [| llop I N, for some constant ?y >> 0. Assumption 3.2 (Bounded Covariate Noise). For any 2 1, the noise variable en satisfies (a) |G,ll I vCd, (b) Re, 0, and (c) Exn = E, for some mnsitive-definit matrix E satisfying [Σ] S % for some constant y >
Note that Assumption 3.2 is a special case of Assumption 3.1, which allows us to get stronger results in some settings. We also impose the following constraint on the noise in the outcomes.
Assumption 3.3 (SubGaussian Outcome Noise). For any n 2 1, the noise variable En satisfies (a) BG,- = 0, (b) En is n-subGaussian, and (c) E& S a. for some constant a.
Under this setting, the goal of the learner is estimate ((a) for [A] given an (possibly adaptively- chosen) observed sequence (Zn, an Yn)n21- For n 2 1. we define the matrix Zn E Rnxd to be the matrix of observed (i.e. noisy) covariates, with Z,.-.., 7n as its rows. Similarly, X, (X1, XT)² E RRax is the matrix of noiseless covariates (which are unobserved), and E, (EI....,, ..,)' E Raad, Yn = (Y,...,,Y, YY)"" E |nx11 and En (EI.....E..) E [Rx are defined analogously. For any action a E [A], let (a) == {s S n G2 = n) be the set of rounds up and including round on which action was chosen. Likewise, let c. (a) (a)) denote the number of rounds by round n on which action a was chosen. For a E [A]. we enumerate
(a)a) in increasing order as i S ... I (a)( Finally, we define Z, (a) E [a)(d to be ((a) = (Zi,...,, Zinndos) and define Xn((),, En(a, Ya(a), and (a) analogously.
3.2 Principal component regression
Background on singular value decomposition Any matrix A Ruxd may be written in terms of its singular value decomposition A = U'V'' where U BaxdAn and V E Rddddn are matrices with orthonormal columns, and Σ = diag(o (A).... (A)) E TR (ddAn) ((dAA) is a diagonal matrix containing the singular values of A, where assume 01 (A) ..... 2 ad)n(A) 2 O. Given a truncation level k. we define the truncation of A onto its top l principal components as A& := Uądiag(or 1 (A),.... ThAdAn VA) where UA E g=xkkddn is the matrix with the first k A d A n columns of U, and Vv Bnnknddn is defined analogously. Given such singular value decomposition, we can define the projection matrix onto the subspace spanned by the top k right singular vectors as P& Rdxd given by Pa- := V.
For n 2 1, a E [A]. and (a) as defined above, we write the k-truncated singular value decomposition of (a) as (a) = - (a)dga() (Z,(a)). Tknnnd (Z,, (a)) (. (a), and the corresponding projection onto the top i: right singular vectors of Z, (a) as P P,,,((a) When k: = r, (a). (Recall r dim dim) By P. we denote
we leverage the simplified notation (a) the projection matrix onto the true, underlying subspace W'. While P is never known, our results leverage the fact that (a) converges to P nicely over time. We define the projected noisy covariate matrix matrix to be (a) == Z. (a)...)) and define (a), (n(a) similarly. Any quantity with "Y" is defined equivalently to quantities with "*" except with P in place of (a(a). We are now ready to introduce our procedure for estimating ((a) for a E [A], called adaptive (or online) principal component regression.
Definition 3.4 (Adaptive Principal Component Regression). Given regularization parameter and
p 2 0 and truncation level & E N, for a E [A] and n 2 1 let (a) = Z,, (a = (a) Z,, (a) + pPn, Regularized principal component regression estimates (()) as @a(a) (a( (a
4

---

Setting p = O recovers the version of PCR used in Agarwal et al. [7]. In words, (unregularized) PCR "denoises" the observed covariates by projecting them onto the subspace given by their k-truncation, before estimating ((a) via linear regression using the projected covariates. We choose to regularize since it known that regularization increases the stability of regression-style algorithms. This added stability from regularization allows us to exploit the online regression bounds of Abbasi- Yadkori et al. [3] to measure the performance of our estimates. Throughout the sequel, we only consider adaptive PCR with truncation level k =.
3.3 Signal to noise ratio
We now introduce the concept of signal to noise ratio, which will be integral in stating and proving our results. The signal noise ratio provides measure of how strongly the true covariates (this the "sig- nal" of the problem, measured through (X,(((a)) stand out sequentially with respect to the "noise" induced by &, (which we will measure through the relevant high probability bounds on | llep).
Definition 3.5 (Signal to Noise Ratio). We define the signal to noise ratio associated with an action E [A] at round n as
(a)
snr,, (a)
Un
where (Un)n21 is noise-dependent sequence growing as Un O +0 vd+ Vlog (1 log(n))
The price we pay for adaptivity is encoded directly into the definition of the signal to noise ratio, (a). While one may imagine defining snr,, (a) as the ratio between (X,, (a)) and [a),(a)) bounding [|E,, (a)llop is a nontrivial task as the rows of En( may be strongly correlated. To circumvent this, apply the trivial bound (a) S |1E.1lop- Thus, the price of adaptivity in our setting is that the signal from covariates associated with an action a must stand out with respect to the total covariate noise by time The growth condition on Un presented in Definition 3.5 is
(a)
motivated follows: w.h.p E l|E ~ vd + vn, and the extra additive /log (1 log(n)) factor is the price we pay for having high probability control of [|ε, llop uniformly over rounds. Below we provide an exact definition for Un. as this choice leads to bounds with known constants and simple conditions on snr, (a) for validity.
We consider the following two sequences (Un) in defining signal to noise ratio, which both satisfy ||En I Un, Vn 2 with probability at least 1 - ō, per Lemma B.3.
3 13 + (65/22(()) + nyy when Assumption 3.1 holds
U = 3 \nCdrrs(n) + [dd) + my when Assumption 3.2 holds.
da ). = 22 and N = 17d is an In the above, 8 E (0, 1), (n( = 2 log (og(2n) + log
upper bound the 1/8-covering number of gd-1, While the exact forms of the above sequences (Un)a21 may appear complicated, it is helpful to realize that, under either Assumption 3.1 or 3.2, we have Un 0 (Vū+ + Vlog (} log(n))) i.e., the growth condition on Un presented in Definition 3.5 is satisfidd.
We can likewise define the empirical signal to noise ratio associated with action as sir, == (Z. Note that unlike the (true) signal noise ratio (a), the empirical version snr, (a) computable by the learner. Thus, it will be integral in stating our empirical-style bounds in the section that follows.
We conclude this section by comparing our notion of signal to noise ratio to that of Agarwal et al. [7], who define (a) instead as (a)) i.e. the ratio of the "signal" in the covariates to the v Vi
expected operator norm of covariate noise El Since the goal of our work is high-probability (not in-expectation) estimation guarantees for PCR, we believe using high probability bounds on | lop is more natural when defining (a).
5

---

4 Adaptive bounds for online (regularized) PCR
We now present the main results of this work worr-highh-eee brihh-robbbbility, time- and action unimormmi bounds measuring the convergence of the PCR estimates 0, (a) to the true slope vectors ((a). Unlike existing results [6-8], our bounds are valid when the covariates (X1))21 and actions (an, 2n21 are determined in an online (potentially adversarial) manner.
We first point out why the analysis of Agarwal et al. [7, 8] breaks down in the setting of adaptive (or online) PCR. First, many of the concentration inequalities leveraged in Agarwal et al. [7] do not hold in the adaptive design setting. As a particular example, the authors leverage the Hanson- Hanson-Wright inequality [82, 73] for quadratic forms to study how the noisy covariate matrix Z, concentrates around the true matrix x,, This inequality fails to hold when the design points (Xn)n21 depend on the previous observations. Second, the techniques leveraged by Agarwal et al. [8] to extend the convergence guarantees of PCR to the multiple action setting fail to hold when the n-th action an is selected based on previous observations. Lastly, the bounds presented in [7] are are inherently fixed-time in nature-a a simple way to convert existing fixed-time bounds to time-uniform ones would be to perform union bound over time steps, but that introduces looseness in the bounds.
We are able to construct our bounds by exploiting connections between online PCR and self- normalized martingale concentration [50, 51, 32, 33]. In particular, we combine martingale based results for constructing confidence ellipsoids for online regression [3, 32, 33] with methods for high-dimensional covariance estimation [83, 80] to prove our results. Exploiting this connection what allows us extend the results of Agarwal et al. [7] to the adaptive design, time-uniform setting. We begin with a bound which, up to constants and polylogarthmic factors, captures the rate of convergence of online PCR in terms of (a) the underlying signal to noise ratio and (b) the conditioning of the observed data.
Theorem 4.1 (Rate of Convergence for Online PCR). Let ô (0.1) 1) be an arbitrary confidence parameter. Let p > 0 be chosen to be sufficiently small, as detailed in Appendix F. Further, assume that there is some no
such that rank(X (X no (a)) and snrn(a) (a) 2 2 for all no. Then, with
probability at least 1 - (A6)), simultaneously for all actions E [A] and time steps n. 2 nhy we have
110m (a) 0(a)) (
1
where Ks ((,,(a)) = o. (a)
(x)) is the condition number (ignoring zero singular values) of X (a).
Theorem 4.1 is proved in Appendix E. We begin by comparing our bounds to those of Agarwal et al. [7, 8J. At any fixed time, our bounds take on roughly the same form as those of the aforementioned authors, having an inverse quadratic dependence on the signal to noise ratio. To make their bounds non-vacuous, the authors need to make the "soft sparsity" assumption of [0(aa]l1 bound, on the other hand, suffers no dependence on the nn-mo the 0(a)'s 's. This makes intuitive sense, the specific choice of basis should not impact the rate of convergence of PCR. However, our bounds pay a price for adaptivity- in particular, the signal to noise ratio associated with an action is defined with respect to a bound on the total operator norm of the matrix E,, If an action is selected very infrequently, the above bound may become loose.
O(vd). Our
While the above bound is stated in terms of signal to noise ratio, if we make additional assumptions, we can obtain bounds directly terms of d, n, and r. In particular, the following "well-balancing" assumptions suffice.
Assumption 4.2 (Well-balancing assumptions). For all 2 no. the following hold: (a)
o, (X,, e (Vonca for all i E [r], (b) c.(a) = O(ca(a')) for all a' E [A], and (c)
A = 0r))
Corollary 4.3. Assume the same setup as Theorem 4.1, and further assume Assumption 4.2 holds. Then with probability at least O(A)), simultaneously for all actions E [A] and time steps
2 Da, we have
100, - (o)()))(())133 ddn

---

Corollary 4.3 shows that Theorem 4.1 obtains the same estimation rate as Theorem 4.1 of Agarwal al. [7] if assumption Assumption 4.2 holds. This "well-balancing" assumption says roughly that all non-zero singular values of X,, are of the same order, each action is selected with the same frequency, and that the number of actions is, at most, proportional to dimension of the true, unknown subspace. As noted by Agarwal et al. [7], the assumption of a in many works in econometrics and robust statistics, and additionally holds with high probability if the entries of X,, are i.i.d[62, 21, 37]. Further, it is often the case that there only few available actions (for instance, in the synthetic control literature there are only two actions [2, 1, (,3,), justifying the assumption that A = (r)). Lastly, ensuring that each action is played (very roughly) the same number times can be viewed as a price for adaptivity.
spectrum" (for x,,) is common
The proof of Theorem 4.1 is immediate as corollary from the following, more complicated bound. Theorem 4.4 below measures the convergence of 0 (a) to O(a) in terms of empirical (i.e. observed) quantities. We imagine this bound to be the most practically relevant of our results, as, unlike the results of Agarwal et al. [7]. it is directly computable by the learner, involves known constants, and places minimal conditions on the signal to noise ratio.
Theorem 4.4 (Empirical Guarantees for Online PCR). Let E (0, 1) be arbitrary confidence parameter, Let p > 0 be chosen to be sufficiently small, as detailed in Appendix F. Further, assume that there is some no 2 such that rank(X (a)) = and (a) > 2 for all n 2 no. Then, with probability at least 1 - (AA)), simultaneously for all actions a E [A] and time steps n 2 no, we have
I
(orr,((o)
(a) - 010)
74 11+2210 216x(
snr, (a)2
o, (z(Zn(a))
where k (a)) = 01(Za( (a))
o.(Zn(a)) |10(a)]2 S T,, and in the above we define the "error" term err,(a) (a)
be
err, := = 32pL2 2 64n/ log (A) (
r log (1 0.(2z(())))
P
+ +n7² 22n
+ 20 (C(cn(a)) + 6c, (c)(a)a.
We see that the above bound, with the exception of the third term, more or less resembles the bound presented in Theorem just written in terms of the observed covariates Z,, (a) instead of the true covariates (a). We view the third term as a slowly growing "error" term. In particular, all terms in the quantity (a), are either constant, logarithmic the singular values of Z., (a). or linear in ev (a). the number times by round n action a has been selected. This implies that err, (a) = Ō(n + d). ensuring err, (a) is dominated by other terms in the asymptotic analysis. We now provide the proof of Theorem 4.4. The key application of self normalized, martingale concentration comes into play in bounding the quantities that appear in the upper bounds of terms Ti and T2 (to be defined below).
Proof. Observe the decomposition, for any n 2 1 and a E [A]
(a) ((a) = (a) - B(a)) + (P- - (a))((()))
where p is the projection onto the subspace orthogonal to W* and (a) is the projection onto the subspace orthogonal to the learned subspace (i.e. that spanned by Zn.((a)) Since Pa(a)(O((a) ((a)) and (P- - P (a)))(a) are orthogonal vectors, we have
[ - (a)) || = (a.())() - -(a))) (P,
We bound these two terms separately, beginning with the second term. Going forward, fix an action E [A]. Observe that with probability at least 1 - 5, simultaneously for all n 2 no(a),
(P. - P-P )((a
< (
(a) - -P- - |0(aa)12
2
op
< 1.2 P (a) P
1
P.(aa)
P
op
AL
6L
<
o, (X,, (a)}²
o, (Z)(2
7

---

where the equality in the above comes from observing [ P (a) - lop = |P
Pllop. the second-to-last last inequality comes from applying Lemma B.4, and the last inequality follows from the second part of Lemma B.6.
We now bound the first term. Observe that write
(a((a) (Pn(a) -((a)) 1 = (Zn(aa)) (a( (0n(a)- -0(a))
(I)
(a))2 (a) (x(a))a(0))xx(((000)) (a()) 2 + (x(a)0(a) - 2n (a)0(a)
2
where the first inequality follows from the fact that (.((a) (Z. (a)) Zn (a) (a) and
o, (Z)((a)) = or (Z, (a)), and the second inequality comes from applying the parallelogram in- equality. First we bound Ti. We have, with probability at least 1 - O()), simultaneously for all n 2 no(a)
Ti 8 Pa(a))/2 -0(0)) (a) +8 (a)(((( - (a(a)((a)
s 32pL2 + 64n7 log A ( + rlo (1+ (1=o(2(())))) )) +16L2U
+ 6 V2c, (a))s(()(())) + 10n) (s(n(a((())) + (c,(a)a 8T2,
where the first inequality follows from Lemma D.I. and the second inequality follows from applying Lemmas C.1 and D.3. (n(n) 2 log log(2n) log
defined in Lemma A.2. We now bound T2. With probability at least 1 - 0(8) simultaneously for all n 2 no. have
da?
125
T2 S 2T. (a))² PPP
+ 2T. |
8L30, (L (a)) + 22
o, (X,(a))
12L (a)) 222
(Z)
The first inequality follows from Lemma D.2, the second inequality follows from applying Lemmas B.4 and B.3, and the final inequality follows from Lemma B.6.
Piecing the above inequalities together yields the desired result, which can be checked via the argument at the end of Appendix D. A union bound over actions then yields that the desired inequality holds over all actions a E [A] with probability at least (
Application to causal inference with panel data
We now apply bounds for adaptive PCR online experiment design in the context of panel data. In this setting, the learner is interested in estimating unit-specific counterfactuals under different interventions, given sequence of unit outcomes (or measurements) over time. Units can range from medical patients, to subpopulations or geographic locations. Examples of interventions include medical treatments, discounts, and socioeconomic policies. Synthetic control (SC) popular framework used to estimate counterfactual unit outcomes in panel data settings, had they not been treated (i.e. remained under control) [1, 2]. In SC, there a notion of pre-inter ine-intervention time period in which all units are under control, followed by post-intervention time period, in which every unit undergoes one of several interventions (including control). At high level, SC fits a model of a unit's ss pre-treatment outcomes using pre-treatment data from units who remained under control the post-intervention time period. then constructs a "synthetic control" by using the learned model to predict the unit's post-intervention outcomes, had they remained under control. Synthetic interventions (SI) a recent generalization of the SC framework, which allows for counterfactual estimation of unit outcomes under different interventions, in addition to control [8]. Using our

---

bounds from Section 4, we show how to generalize the SI framework of Agarwal et al. [8] to settings where interventions are assigned via an adaptive intervention assignment policy.
As motivating example, consider an online e-commerce platform (learne) which assigns discounts (interventions) users (units) with the goal of maximizing total user engagement the platform. For concreteness, suppose that the e-commerce platform assigns discounts greedily with respect to the discount level which appears be best at the current round (i.e. maximizes total engagement for the current user), given the sequence of previously observed (user, discount level, engagement level) tuples. Under such a setting, the intervention assigned at the current round will be correlated with the observed engagement levels at previous rounds, thus breaking the requirement of the SI framework [8] that the intervention assignment is not adaptive previously observed outcomes.
Formally, we consider a panel data setting in which the principal observes units over sequence of rounds. In each round n, the learner observes unit n. under control for To N time steps, followed by one of A interventions (including control, which we denote by 0) for the remaining T To time steps, where T N. Overloading notation to be consistent with the literature on panel data, denote the potential outcome of unit n at time under intervention a by X
n's pre-treatment outcomes (under control) by Yn.pre == [ ( 1 n.t E R, the set of unit n.To E RTo, and their post- nopost == [Y [ar(a n.TT+1 - E TT intervention potential outcomes under intervention a by y-(a)
We use a to refer to an arbitrary intervention in {O..... A - 1} and On to denote the realized intervention unit n actually receives in the post-intervention time period. We posit that potential outcomes are generated by the following latent factor model over units, time steps, and interventions.
Assumption 5.1 (Latent Factor Model). Suppose the outcome for unit at time step t under treatment a E {O....,AA 1} takes the form
y(O)) n.t = (U((), V,,) + F.,t:
(a)
where ((()) E IR" is a latent factor which depends only on the time step t and intervention a, V, E R' is latent factor which only depends unit n, and (a) is zero-mean SubGaussian random noise
with variance at most 0². We assume, without loss of generality, that ((U(()) Va)l S for all 1. t e [T), a E {0, (O.....A-.11
Note that the learner observes yr(1) for only the intervention a,, that unit n is under at time step t, and never observes U,(0) Vz, or G,, Such "low rank" assumptions are ubiquitous within the panel data literature (see references in Section 2). We assume that is known to the leamee, although principled heuristics exist for estimating r in practice from data (see, e.g. Section 3.2 of Agarwal et al. [8]). Additionally, we make the following "causal transportability" assumption the latent factors.
Assumption 5.2 (Linear span inclusion). For any pext-intervention time step t E [To 1,7] and intervention {0, ......... A 1}, assume that U!!() span(((())) ite [To]]).
Intuitively, Assumption 5.2 allows for information be inferred about the potential outcomes in the post-intervention time period using pre-treatment observations. The goal of the learner is to estimate unit-specific counterfactual outcomes under different interventions when the sequence of units and interventions is chosen adaptively. In line with previous work in SI and SC, our target causal parameter is the (counterfactual) average expected post-intervention outcome.
Definition 5.3. The average expected post-intervention outcome of unit under intervention a is
(a
1
By(a) a,t
D.post
=
T
To
To+1
where the expectation taken with respect (e..eET
While we consider the average post-intervention outcome, our results may be readily extended to settings in which the target causal parameter is any linear combination of post-intervention outcomes. Next we show that under Assumption 5.1 and Assumption 5.2, EY((s) may be written as linear combination of unit n pre-intervention outcomes. We note that similar observations have previously been made the panel data literature (e.g. [46]), but we include the following lemma for completeness' sake.

---

Lemma 5.4 (Reformulation of average expected post-intervention outcome). Under Assump- tion 5.1 and Assumption S.2, there exists slope vector 8(a) E RT7, such that the average expected post-intervention outcome of unit nt under intervention is expressible
Eyla) n.post
(0(a) EY,.)EYynppp EYn.pre).
T To
((a) may be interpreted as unit-independent measure of the causal relationship between pre- and post-intervention outcomes. Using this reformulation, adaptive guarantees for the estimation of causal effects time may now be obtained by applying our online PCR results of Section 4. Overloading
the notation of Section 3, we let X, (EY1, 1.pres.... .......,Eyyn.pee EYn, Zn (Y (Yi.pre..... Y pre )²
en.pre = (c,,1...., E To and
(0) TT En = (E1.pre En.pre) En = Ei=To+ =n=
E,, En = (5)
(an)
Y, T To
yla 1.
1
y(an)) n.t
T T-
Finally, we define quantities such as Z, to bounding primary quantity of interest in the panel data setting: prediction error for the average expected post-intervention outcome.
(a) analogously to Section We now turn
Theorem 5.5 (Prediction error of average expected post-intervention outcome). Let 6 E (0. 1) be an arbitrary confidence parameter and p > be chosen to be sufficiently small, detailed in Appendix F. Further, assume that Assumptions 5.1 and 5.2 are satisfied, there is some no 2 1 such that rank(Xng (a)) = т, and snr, (a) Z 2 for all n 2 no- If S 1T and S TTo n. then under Assumption 4.2 with probability at least 1 O(A)), simultaneously for all interventions E AO....,A-
L +L+
r(Lv1)
(Y n.post n.postl
(P(()
VT-T
VTAAn
V(T - (T) (To An)
where Ryyaa p.post T-E (0n(a), Yn.pre) is the estimated average post-intervention outcome for
unit under intervention
more complicated expression which does not require Assumption 4.2 To 7 may be found in Appendix G. Observe that [Ey
n,post n.post - 0 with high probability as T, T,To, co.
We conclude this section by comparing our results with those of the (non-adaptive) synthetic in- terventions framework of Agarwal et al. [8]. Since we are regressing over time, our method for estimating Æy(a) is known
horizontal regression method in the panel data literature. This is in contrast to vertical regression methods, which regress over units. See Shen et al. [75] for more details on the similarities and differences between horizontal and vertical regression methods in panel data settings. While we do not exactly match the bound of Agarwal et al. [8] since their synthetic interventions framework of uses a vertical regression method, the two bounds similar, with the
n.post
notable differences being as follows: (1) The bound of [8] contains a "slow" 0(r1/2T, 1/4) term which does not appear in analysis. (2) The non-adaptive SI bound also contains a term which scales as Õ VT- To in the worst case, while our bound has no such dependence. However, this comes at the price of slow rate whenever L is large compared VT To-
6 Conclusion
We obtain the first adaptive bounds for principal component regression and apply them to the problem of online experiment design in the context of panel data, where we allow for interventions to be as- signed according to an adaptive policy. Exciting directions for future work include applications of our results to domains such as differential privacy, and using our bounds to obtain contextual bandit algo- rithms (e.g. based on LinUCB [3]) capable of regret minimization when given access to noisy contexts.
Acknowledgements
KH is supported in part by an NDSEG Fellowship. KH, JW, and ZSW are supported in part by NSF FAI Award #1939606. The authors would like to thank the anonymous NeurlPS reviewers for valuable feedback.
10

---

References
[1] Alberto Abadie and Javier Gardeazabal. The economic costs of conflic:: case study of the basque country. American economic review, 93(1):113-13) 2003.
[2] Alberto Abadie, Alexis Diamond, and Jens Hainmueller. Synthetic control methods for compar- ative case studies: Estimating the effect of california's 's tobacco control program. Journal of the American statistical Association, 105(490):493-500 2010.
[3] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[4] Abhineet Agarwal, Anish Agarwal, and Suhas Vijaykumar. Synthetic combinations: causal inference framework for combinatorial interventions. arXiv preprint arXiv:2303, 2023.
[5] Anish Agarwal and Rahul Singh. Causal inference with corrupted data: Measurement error, missing values, discretization, and differential privacy. arXiv preprint arXiv:2107.02788) 2021.
[6] Anish Agarwal, Devavrat Shah, Dennis Shen, and Dogyoon Song. On robustness of principal component regression. Advances in Neural Information Processing Systems, 32, 2019.
[7] Anish Agarwal, Devavrat Shah, and Dennis Shen. On principal component regression in a high-dimensional error-in-variables setting. arXiv preprint arXiv:2010.14449 2020.
[8] Anish Agarwal, Devavrat Shah, and Dennis Shen. Synthetic interventions. arXiv preprint arXiv:2006.0769) 2020.
[9] Anish Agarwal, Munther Dahleh, Devavrat Shah, and Dennis Shen. Causal matrix completion. arXiv preprint arXiv:2109.15152 2021.
[10] Anish Agarwal, Devavrat Shah, Dennis Shen, and Dogyoon Song. On robustness of principal component regression. Journal of the American Statistical Association, 1131576)
2021. doi: 10.10800012244999000
[11] Anish Agarwal, Sarah Cen, Devavrat Shah, and Christina Lee Yu. Network synthetic interven- tions: A framework for panel data with network interference. arXiv preprint arXiv:2210.11335 2022.
[12] Deepak Agarwal and Bee-Chung Chen. Regression- based latent factor models. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 19-28, 2009.
[13] Muhammad Jehangir Amjad, Devavrat Shah, and Dennis Shen. Robust synthetic control. Journal of Machine Learning Research, 19:1-51, 2018.
[14] Muhummad Amjad, Vishal Mishra, Devavrat Shah, and Dennis Shen. mrse: Nulti-dimensional robust synthetic control. Proceedings of the ACM Measurement and Analysis of Computing Systems, 3(2), 2019.
[15] Manuel Arellano and Bo Honore. Panel data models: Some recent developments. Handbook of Econometrics, 02 2000.
[16] Dmitry Arkhangelsky, Susan Athey, David A. Hirshberg, Guido W. Imbens, and Stefan Wager. Synthetic difference in differences, 2020.
[17] Susan Athey, Mohsen Bayati, Nikolay Doudchenko, Guido Imbens, and Khashayar Khosravi. Matrix completion methods for causal panel data models. Journal of the American Statistical Association, 1 1166536)
2021.
[18] Jushan Bai. Inferential theory for factor models of large dimensions. Econometrica, 71(1):135- 171, 2003. ISSN 00129682, 14680262. URL http://www. jstor. stt2le/300210........
[19] Jushan Bai. Panel data models with interactive fixed effects. Econometrica, 1224) 2009. ISSN 001 14680262. URL http:////e jstor. wwtpstable///eooooooo/ooo...eeet 402638859.

---

[20] Jushan Bai and Serena Ng. Matrix completion, counterfactuals, and factor analysis of missing data, 2020.
[21] Jushan Bai and Serena Ng. Matrix completion, counterfactualls and factor analysis of missing data. Journal of the American Statistical Association, (166566)1776-1111 2021.
[22] Eric Bair, Trevor Hastie, Debashis Paul, and Robert Tibshirani. Prediction by supervised principal components. Journal of the American Statistical Association, 101(473):19--377, 2006.
[23] Eli Ben-Michael, Avi Feller, and Jesse Rothstein. The augmented synthetic control method, 2020.
[24] Aldo Gael Carranza, Sanath Kumar Krishnamurthy, and Susan Athey. Flexible and efficient contextual bandits with heterogeneous treatment effect oracles. In International Conference on Artificial Intelligence and Statisties, pages 7190-7212. PMLR, 2023.
[25] Gary Chamberlain. Panel data. In Z. Grilichest and M. D. Intriligator, editors, Handbook of Econometrics, volume 2, chapter 22, pages 1247-1318, Elsevier, 1 edition, 1984. URL attoss://Econaapers... repec. www.ee.........eeeeeeeeeeeeeeeee Drgg/eePE:eeeeee eec:cchhppp ecochp:
[26] Jiafeng Chen. Synthetic control as online linear regression. Econometrica, 91(2):465-491 2023.
[27] Victor Chemoozukko, Kaspar Wuthrich, and Yinchu Zhu. Practical and robust f-test based inference for synthetic control and related methods, 2020.
[28] Andrew Chesher. The effect of mcasurement error. Biometrika, 78(3):451-46,, 1991.
[29] Sayak Ray Chowdhury and Aditya Gopalan. On kemeliied multi-armed bandits. In International Conference on Machine Learning, pages 844-853. PMLR, 2017.
[30] Ben Chugg, Hongjian Wang, and Aaditya Ramdas. A unified recipe for deriving (time-uniform) pac- pac-bayes bounds. arXiv preprint arXiv:2302.0342), 2023.
[31] Abhirup Datta and Hui Zou. Cocolasso for high high-dimensional error-in- inorrin-variablss regression. 2017.
[32] Victor H de la Peña, Michael J Klass, and Tze Leung Lai. Self-normalized processes: exponen- tial incqualities, moment bounds and iterated logarithm laws. 2004.
[33] Victor H de Peña, Michael Klass, and Tze Leung Lai. Pseudo-maximization and self- normalized processes. 2007.
[34] Yash Deshpande, Lester Mackey, Vasilis Syrgkanis, and Matt Taddy. Accurate inference for adaptive linear models. In International Conference on Machine Learning, pages 1193-1203. PMLR, 2018
[35] N. Doudchenko and G. Imbens. Balancing, regression, difference in iiffifferences and synthetic control methods: A synthesis. NBER Working Paper No. 22791, 2016.
[36] Walter Enders. Applied econometric time series. John Wiley Sons, 2008
[37] Jianqing Fan, Weichen Wang, and Yiqiao Zhong. An E eigenvector perturbation bound and its application to robust covariance estimation. Journal of Machine Learning Research, 18(207): 1-42, 2018.
[38] Vivek Farias, Ciamac Moallemi, Tianyi Peng. and Andrew Zheng. Synthetically controlled bandits. arXiv preprint arXiv:2202.0007, 2022.
[39] Iván Fernández- Val, Hugo Freeman, and Martin Weidner. Low-rank approximations of nonsep- arable panel models, 2020.
[40] Jorge I Figueroa-Zúñiga, Cristian I. Bayes, Victor Leiva, and Shuangzhe Liu. Robust beta regression modeling with errors-in iaaa----vvariales: a bayesian approach and numerical applications. Statistical Papers, pages 1-24, 2022.
12

---

[41] Wayne A Fuller. Measurement error models. John Wiley & Sons, 2009.
[42] Zvi Griliches and Vidar Ringstad. Error-in-the-variabls bias in nonlinear contexts. Economet- rica: Journal of the Econometric Society, pages 368-370, 1970.
[43] Vitor Hadad, David A Hirshberg. Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the national academy of sciences, (18(15)e2014402) 18, 2021.
[44] Daniel B Hall. Measurement error in nonlinear models: modern perspective, 2008.
[45] Keegan Harris, Anish Agarwal, Chara Podimata, and Zhiwei Steven Wu. Strategyproof decision- making in panel data settings and beyond. arXiv preprint wrXiv22211.142353 2022.
[46] Keegan Harris, Dung Daniel Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu. Strategic instrumental variable regression: Recovering causal relationships from strategic responses. In International Conference on Machine Learning, pages 8502-8522. PMLR, 2022.
[47] Jerry Hausman. Mismeasured variables in econometric analysis: problems from the right and problems from the left. Journal of Economic perspectives, 15(4):57-67, 2001.
[48] Peter D Hoff. Multiplicative latent factor models for description and prediction of social networks. Computational and mathematical organization theory, 15(4):261, 2009.
[49] Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classifiers and pac-bayes finite-sample guarantees. In Artificial Intelligence and Statistics, pages 384-392. PMLR, 2014.
[50] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform chernoff bounds via nonnegative supermartingales. 2020.
[51] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. 2021.
[52] Cheng Hsiao, H. Steve Ching, and Shui Ki Wan. A panel data approach for program evaluation: Measuring the benefits of political and economic integration of hong kong with mainland china. Journal of Applied Econometrics, 27(5):705-740, 2012. doi: http://doo.orr//1100002222
1230.
[53] Rodolphe Jenatton, Nicolas Roux, Antoine Bordes, and Guillaume R Obozinski. A latent factor model for highly 2012.
data, Advances in neural information processing systems, 25,
[54] Ian T Jolliffe. A note on the use of principal components in regression. Journal of the Royal Statistical Society Series C: Applied Statistics, 300)330,,333, 1982.
[55] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-30) 2005.
[56] Abhishek Kaul and Hira L Koul. Weighted 11 penalizzed corrected quantile regression for high dimensional measurement error models. Journal of Multivariate Analysis, 140:72-91. 2015.
[57] In- Won Kim, Michael Liebman, and Thomas F Edgar. Robust error-in-variable estimation using nonlinear programming techniques. AIChE Journal, 36(7):985-993, 1990.
[58] Tor Lattimore and Csaha Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[59] Kathleen T. Li. Inference for factor model based average treatment effects. Available at SSRN 3112775, 2018
[60] Kathleen T. Li and David R. Bell. Estimation of average treatment effects with panel data: Asymptotic theory and implementation. Journal of Econometrics, 197(1):65 - 75, 2017. ISSN 0304-4076. doi: https://doi.org// htt.://oo..og///.00006.ccoooooom
[61] Kung-Yee Liang and Scott L. Zeger. Longitudinal data analysis using generalized línear models. Biometrika, 13(1):13-22, 04 1986. ISSN 0006-3444. doi: 10. 10.1099/biomet773.1.1. URL
https://doi. 10./10...// 1093 /008///oome//3.111 1. 13.
13

---

[62] Po-Ling Loh and Martin J Wainwright. High- digehdimensional regression with noisy and missing data: Provable guarantees with non-convexity. Advances in neural information processing systems, 24, 2011.
[63] Tudor Manole and Aaditya Ramdas. Martingale methods for sequential estimation of convex functionals and divergences. IEEE Transactions on Information Theory, 2023.
[64] Hyungsik Roger Moon and Martin Weidner. Linear regression for panel with unknown number of factors interactive fixed effects. Econometrica, 83(4): 2015. ISSN 00129682, 14680262. URL http: / www. jstor. htt//stabee4336669///
[65] Hyungsik Roger Moon and Martin Weidner. Dynamic linear panel regression models with interactive fixed effects. Econometric Theory, 33(1):158-195, 2017. doi: 10.1017/
$02664666150003288.
[66] Daniel Ngo, Keegan Harris, Anish Agarwal, Vasilis Syrgkanis, and Zhiwei Steven Wu. Incentive- aware synthetic control: Accurate counterfactual estimation via incentivized exploration. 2023.
[67] Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou. Why adaptively collected data have negative bias and how to correct for it. In International Conference on Artificial Intelligence and Statistics, pages 1261-1269. PMLR, 2018.
[68] M. Hashem Pesaran. Estimation and inference in large heterogeneous panels with a multifactor error structure. Econometrica, 74(4):967-1012, 2006. ISSN 00129682, 14680262. URL http://www jstor. . brggsttable//805tt
[69] Chao Qin and Daniel Russo. Adaptivity and confounding in multi-armed bandit experiments. arXiv preprint arXiv:2202.090336 2022.
[70] Park M Reilly and Hugo Patino-Leal. A bayesian study of the variaii--vriablls model. Technometrics, 23(3):221-231, 1981.
[71] Steven Roman, Axler, and FW Gehring. Advanced linear algebra, volume 3. Springer, 2005.
[72] Mathieu Rosenbaum and Alexandre B Tsybakov. Sparse recovery under matrix uncertainty. The Annals of Statistics, pages 2620-2651, 2010.
[73] Mark Rudelson and Roman Vershynin. Hanson- wwiihtt inequality and uub-gaussian concentra- tion. 2013.
[74] Burr Settles. Active learning literature survey. 2009.
[75] Dennis Shen, Peng Ding, Jasjeet Sekhon, and Bin Yu. A tale of two panel data regressions. arXiv preprint arXiv: 2448) 2022.
[76] Robert H Shumway, David Stoffer, and David S Stoffer. Time series analysis and its applications, volume 3. Springer, 2000.
[77] David Simchi-Levi and Chonghuan Wang. Multi-armed bandit experimental design: Online decision-making and adaptive inference. In International Conference on Artificial Intelligence and Statistics, pages 3086-3097. PMLR, 2023.
[78] Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1 2019.
[79] Chandler Squires, Dennis Shen, Anish Agarwal, Devavrat Shah, and Caroline Uhler. Causal imputation via synthetic interventions. In Conference on Causal Learning and Reasoning, pages 688-711. 711. PMLR, 2022.
[80] Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
[81] Sridhar Ungarala and Bhavik R Bakshi. A multiscale, bayesian and error-in-variables approach for linear dynamic data rectification. Computers Chemical Engineering, 24(2-7):4454455 2000.
14

---

[82] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[83] Martin Wainwright. Iligh-dimensional statistics; non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[84] Tom Wansbeek and Erik Meijer. Measurement error and latent variables. A companion to theoretical econometrics, pages 162-179, 2001.
[85] Justin Whitehouse, Aaditya Ramdas, Steven Z. Wu, and Ryan M Rogers. Brownian noise reduction: Maximizing privacy subject accuracy constraints, Advances in Neural Information Processing Systems, 35:1 35:11217-11221 1228, 2022.
[86] Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Steven Wu. Fully-adaptive composition in differential privacy. In International Conference on Machine Learning, pages 36990-37007. PMLR, 2023.
[87] Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ramdas. On the sublinear regret of GP-UCB. Advances in Neural Information Processing Systems, 2023.
[88] Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ramdas. Time-uniform eof-nnomaliize concentration for vector-valued processes. arXiv preprini arXiv:2310.09100 2023.
[89] Yiqing Xu. Generalized synthetic control method: Causal inference with interactive fixed effects models. Political Analysis, 25(1):57-76, 2017. doi: 10. 20.1017/pan.2016.22
[90] Jingwen Zhang, Yifang Chen, and Amandeep Singh. Causal bandits: Online decision-making endogenous settings, arXiv preprint arXiv:221 I. .8864,, 2022.
[91] Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical inference with m-estimators on adaptively collected data. Advances in neural information processing systems, 34:7460-7471, 2021.
[92] Kelly W Zhang, Lucas Janson, and Susan A Murphy. Statistical inference after adaptive sampling in non-markovian environments. arXiv preprint arXiv:2202. 07098, 2022.
15


Reviews:
[{"review_id": "uB20S9OgfY", "reviewer": "Reviewer_M8r1", "summary": "This study provides finite sample guarantees  for PCR regression in the online setting where covariates and interventions are chosen adaptively. The key technical contributions hinge on applying recent results on self-normalized martingale concentration to this problem. The authors further apply these novel bounds in the context of learning from panel data when interventions are assigned adaptively.", "questions": "* How common is the problem of learning with noisy covariates, especially in an online setting?\n* While I don't see an explicit assumption, do the error terms have to be homoscedastic for the analysis to work? \n* How strong are the assumptions 3.1-3.3 and how do they compare with those in similar literature?\n* Could you provide some experimental evaluation?\n\t\n", "limitations": "The authors don't explicitly addressed the limitations of their work. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well written, with a good mix of intuition and technical detail. The theoretical findings around the self normalized martingale concentration application are insightful. The application to adaptive panel data setting illustrates the usefulness of this method well. Furthermore, this method enables some future work around noisy LinUCB bounds which I look forward to. In general, I found this paper to be engaging and believe that with a few additional adjustments, it has the potential to make a valuable contribution to the conference.", "weaknesses": "The problem addressed in this paper appears to be quite specific, and it is unclear how frequently online learning with noisy covariates occurs in practical scenarios. It would be beneficial to include concrete examples that illustrate situations where this problem could arise. Additionally, one notable concern is the absence of an experimental section in this work. While the paper primarily focuses on theoretical aspects, it would be valuable to have an experimental evaluation of the proposed bounds to further validate their effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our submission. Please find our replies to your questions/comments below. \n\n[*How common is the problem of learning with noisy covariates, especially in an online setting?*]\n\nWe would like to point out that our application to panel data is a salient application of online learning with noisy covariates. As we mention in the text, our framework may be thought of as a generalization of the synthetic interventions framework to adaptive settings, which itself is a generalization of the canonical synthetic control framework (and is a popular method for counterfactual estimation both in theory and in practice). \n\nMoving away from panel data, another setting in which online learning from noisy data may arise is when the observed covariates need to be measured by a physical instrument. Since no measurement is perfectly accurate or exact, it may be helpful to explicitly take such measurement error into consideration when learning.\n\nFinally, it has been shown that error-in-variables regression is a useful lens to think about differential privacy and regression ([5, 10]). In particular, if the covariates have been made differentially private by adding Gaussian noise, and we want to use these covariates for a downstream regression task, then this is an instance of  error-in-variables regression. And of course in many such settings, data is collected adaptively, and no prior results are able to tackle such a setting.\n\n[*While I don't see an explicit assumption, do the error terms have to be homoscedastic for the analysis to work?*]\n\nIt suffices to consider error terms with the same upper bound on their variance, but can be heteroscedastic otherwise. The assumptions of either bounded or subGaussian noise both provide for a uniform upper bound on the variance of noise variables. \n\n[*How strong are the assumptions 3.1-3.3 and how do they compare with those in similar literature?*]\n\nAssumptions 3.1 and 3.3 are fairly mild and are standard in the literature on “error-in-variables” regression (see e.g. [7,8]). Assumption 3.2 is a stronger assumption (bounded random variables vs subGaussian). We emphasize that Assumption 3.2 is not required for any of our results to hold; it just allows us to make stronger statements (e.g. tighter constants) in some settings. We believe the setting of bounded noise is of high utility for applications of our bounds, as noise is often bounded in real-world settings (for instance, a given piece of information associated with an individual may be a percentage, which will always lie between 0 and 1). \n\n\n[*Could you provide some experimental evaluation?*]\n\n\nAs stated in the global rebuttal, we chose to focus on theoretical depth for our adaptive bounds on PCR (Theorem 4.1, Theorem 4.4) and our application to panel data (Theorem F.5) in this submission, as a meaningful empirical comparison cannot be made with previous work since the constants in the non-adaptive bounds are not specified, and therefore the non-adaptive bound cannot be computed.\n"}, {"review_id": "VUAyRtmnsD", "reviewer": "Reviewer_Dfi8", "summary": "This paper studies theoretical properties of the principal component regression (PCR) when data are collected adaptively and are corrupted with measurement errors. In particular, it gives an upper bound of the estimation error of the regression coefficients of the PCR. The derived bounds are then used to study the estimation error of causal effects in panel data setting.", "questions": "1. Regarding the theoretical results. \n (a) The model is assumed to be $Y_n=<\\theta(a_n),X_n>+\\xi_n$ where $X_n\\in W^*$ with $dim(W=r<d)$. The parameter vector $\\theta(a)$ is a d-dimensional vector that also resides in $W^*$. This setting is sort of strange because I am not even sure $\\theta(a)$ is identifiable in such a setting. Please clarify.\n (b) Related to the above question, in definition 3.4, the matrix $\\hat\\nu_n(a)$ should be of at most rank $k<d$ by definition. Is it even invertible? \n(c) In Corollary 4.3, the convergence rate becomes faster when $d$ increases. This is a little counterintuitive. When d-increases, there are more parameters to be estimated and one would expect a slower convergence rate. Can you explain the intuition behind this finding?\n(d) Corollary 4.3, in a special case, when $d=r$, no dimension reduction is needed and the model under study becomes a regular linear regression model. Then the convergence rate is $O(1)$. This is true in linear regression models with measurement errors since the bias in regression coefficient estimates does not vanish, see, e.g., Carroll et al. (1995). Does this mean the derived bound only applies for the case $d\\to\\infty$?\n\n2. Regarding adaptivity. The authors emphasize that the data are collected adaptively, and hence can be correlated. However, the correlation issue is not adequately addressed in the theoretical proof.\n\n(a) On page 4, lines 159-160, the authors introduce the notation $\\mathbf P$ as the projection of $\\mathbf Z_n$ onto the true subspace $W_*$. However, since rows of $\\mathbf Z_n$ are adaptively collected with a stochastic action sequence $A_n=\\{a_1,\\cdots, a_n\\}$. Therefore,  $\\mathbf Z_n$ is dependent on $A_n$ and so should the $\\mathbf P_{n,k}$. Therefore, $\\mathbf P_{n,}$ should be written as $\\mathbf P_{n,k} (A_n)$. And the authors claim that $P_{n,k} (A_n)\\to P$. If $A_n$ is stochastic, what is the sample version $\\hat{\\mathbf P}_{n,k}$ converges to as $n\\to\\infty$? What is the exact definition of $P$?\n\n(b) On page 5, line 184, the authors comment that \"bounding $||\\varepsilon_n(a)||_{op}$ is a nontrivial task as the rows of $\\varepsilon_n(a)$ may be strongly correlated\". However, the matrix $\\varepsilon_n$ is a just stacked version of rows in $\\varepsilon_n(a)$'s. In a special case where the first half of the rows all take action $a_1$ and the second half of rows all take action $a_2$. If rows in $\\varepsilon_n(a_1)$ and $\\varepsilon_n(a_2)$ are highly correlated, I don't see why rows in $\\varepsilon_n$ are not highly correlated. I think the paper implicitly assumes that the measurement errors are independent of the actions taken. However, if this is the case, rows in $\\varepsilon_n(a)$ would also be independent as well and the adaptivity wouldn't matter. Please clarify.\n\n(c) Similar to the above question, in the proofs of Lemma A.2-A.4 and B.3, the measurement errors are assumed to be independent of each other. However, the paper emphasizes that the data are collected adaptively. This pretty much means that the measurement errors $\\epsilon_i$'s are independent of actions taken. Again, the adaptivity wouldn't matter in this case.\n\n3. There is no numerical evaluations to support the theoretical findings.\n\n4. There is no real data application so that one can evaluate the practical usefulness of the derived bounds.\n\nReference:\n1. Carroll, R. J., Ruppert, D., & Stefanski, L. A. (1995). Measurement error in nonlinear models (Vol. 105). CRC press.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and the problem under study if of interest. The theoretical findings appear to be interesting.", "weaknesses": "1. There are some issues with the theoretical findings which I elaborate later.\n2. There is no numerical evaluations to support the theoretical findings.\n3. There is no real data application so that one can evaluate the practical usefulness of the derived bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our work; our replies are below.\n\n\n[*Reply to 3 & 4.*]\n\nSee global rebuttal.\n\n\n[*Reply to 1(a)*]\n\nThe assumption that $\\theta(1), ..., \\theta(A)$ lie in a low-dimensional subspace follows from the latent factor model that is ubiquitous in panel data. This can be seen in Lemma F.4; we are happy to provide more details if necessary. In the high-dimensional setting, the $\\theta(a)$ need not be identifiable. As shown in existing work, the minimum l2-norm $\\theta(a)$ consistent with observed data is, in fact, identifiable. This $\\theta(a)$ is the unknown slope vector lying in the low dimensional subspace. The conclusions of this work establish that not only are the $\\theta(a)$ identifiable, but also that they are consistently estimable in the large sample limit under reasonable assumptions on signal to noise ratio. \n\n[*Reply to 1(b)*]\n\nThe matrix is not in general invertible, but this is not a problem as the restriction of $\\widehat{V}_n(a)$ (viewed as a linear transformation) to the top r eigenspace (i.e. the subspace spanned by the top r eigenvectors) will be invertible given that the empirical signal-to-noise ratio is not zero. The vector being hit on the left by $\\widehat{V}_n(a)$ in the construction of the estimate of $\\theta(a)$ lies in the top r eigenspace by definition, and thus the action of $\\widehat{V}_n(a)$ is uniquely defined. The use of $\\widehat{V}_n(a)^{-1}$ could freely be replaced by the Moore-Penrose pseudo-inverse of $\\widehat{V}_n(a)^+$ (which is defined on all of $R^d$, not just the top r eigenspace) with no effect on computation.\n\n[*Reply to 1(c)*]\n\nInterestingly, since the true parameter is rank-r (which we assume to be fixed) the growing dimension d is actually beneficial, as each column of the matrix can be thought of as a “repeated measurement” of the r latent factors (i.e. a linear combination of the r latent factors). This is in line with the matrix completion literature where how well the matrix is de-noised grows as $r / (\\min{n, d})$, and thus requires both dimensions to be growing and that $r << \\min{n, d}$. Indeed the PCA step of the PCR algorithm can be thought of as “de-noising” the noisily observed covariates as is done in matrix completion.\n\n[*Reply to 1(d)*]\n\nOur bounds in Theorems 4.1 and 4.4 are fully non-asymptotic (i.e. they provide finite-sample guarantees). In the case $d = r$, there is no low rank structure for PCR to exploit, and thus the algorithm is not useful in this setting. We emphasize the result presented in Corollary 4.3 holds in any scaling regime of the parameters $d, n,$ and $r$. For instance, the bound would hold if $d, r$ were fixed and $n$ were taken to grow towards infinity (setting of classical asymptotic statistics) or if $n, r$ were taken to grow with $d$ (the setting for modern high-dimensional statistics).\n\n\n[*Reply to 2(a)*]\n\n\nUnder the assumptions of Theorem 4.1 and 4.4 (that $rank(X_n) = r$ for $n$ sufficiently large), the recovered projection matrix for the non-noisy data is unique, representing the unique orthogonal projection operator onto the true subspace $W^*$. This assumption can be viewed as requiring sufficiently diverse treatment assignments to units in the panel data setting.\n\n\n[*Reply to 2(b)*]\n\nIf the case of bounding $\\|\\epsilon_n(a)\\|$, the choice of action in round $n$ and the observed noise $\\epsilon_n$ are correlated random variables (e.g. our choice of action or chosen treatment of an individual will be influenced by the noise present in covariates). More formally, suppose $n_1, \\dots, n_k$ are the (random) rounds on which treatment $a$ was assigned. Conditioned on knowing that treatment $a$ was given on these rounds, the distributions of $\\epsilon_1, \\dots, \\epsilon_n$ are no longer independent, and $E(\\epsilon_n | A_n = a)$ may not be even equal to zero. Just because the $\\epsilon_1, \\dots, \\epsilon_n$ are marginally independent does not imply they are conditionally independent.  For instance, we may have a treatment rule “assign treatment 1 if the first covariate exceeds 5, else assign treatment 0”. Thus we cannot apply concentration results that require that the rows of the matrix have mean 0 or that the rows are independent, as this will generally not be the case. The rows of $\\epsilon_n$ are independent by assumption on the noise in covariates (there is no dependence on the action in the construction of $\\epsilon_n$). In particular the rows are just i.i.d. random vectors under our assumptions. \n\n\n[*Reply to 2(c)*]\n\nThe measurement errors could equivalently be taken to be subGaussian and mean 0 *conditioned* on the information observed up to time $n - 1$ (i.e. our results would still follow if we assume $E(\\epsilon_n | F_{n  -1}) = 0$ and $\\log E(\\exp\\{\\langle \\lambda, \\epsilon_n\\rangle\\} | F_{n - 1}) \\leq \\frac{\\|\\lambda\\|^2}{2}$, where $F_n$ is the $\\sigma$-algebra generated by the observations made up to time $n$ (think of this as the “history” of the interaction up to time $n$). Martingale concentration naturally applies to this more general dependence structure (in which the noise in covariates is not necessarily independent). However to greatly simplify notation used in proofs, we assume independence. Note that while the noise in covariates in round $n$ is independent of actions taken in rounds $1, \\dots, n - 1$, it is NOT independent of the action taken in round $n$ (the conditional distribution of $\\epsilon_n$ given the observation $A_n$ may not even by mean zero). Moreover, the choice of covariates is not assumed to be independent. One simple way of viewing this is that nature uses the information accumulated up to (not including) time $n$ to generate the covariate $X_n$, and then adds as corruption an independent sample from a standard, multivariate normal distribution. The learner then uses this corrupted covariate to determine a course of treatment. The noise here is independent of previous observations and treatment, but not of the $n$th choice of treatment. "}, {"review_id": "MUdi8H7I8f", "reviewer": "Reviewer_jhsg", "summary": "This work studies the properties of principle component regression in the adaptive setting, where future observations may depend on the values of previously observed observations. The authors provide a time-uniform bounds on the L_2 error of online principal component regression that extend prior work to the adaptive setting. In the process they also remove a previously required assumption of soft sparsity, replacing it with a dependence on the signal to noise ratio. Finally, the authors describe how the results on PCR may be applied to the panel data setting which is commonly modeled via latent factor models.", "questions": "It’s a little confusing why we would have separate noise assumptions over the treated and control series (assumptions 3.1 and 3.2, respectively). I recognize that 3.1 contains 3.2 but the assumption is considerably stronger. It’s not clear to me when we would be able to assume both the low rank assumption and bounded noise in practical settings. \n\nThe regularization justification seems a little strange. Aren’t we already imposing a regularization by restricting to the top $k$ principle components? It’s not entirely clear to me why imposing additional regularization is necessary in this setting. \n\nTheorem 4.4 seems like it could be quite loose in empirical settings. Do the authors have empirical results that examine this? \n\nSmaller items: \n\nIn Theorem 4.4 $L$ appears to be undefined in the main text. \n\nIt’s unclear within the main text whether the authors are employing assumption 3.1 or 3.2. Given that the latter is stronger, this should be stated either within the theorem text or directly before/after.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* This is an interesting task setting. Adaptivity is common in practical settings, and this paper does a good job of providing a nice theoretical grounding for PCR in this setting. \n\n* The authors do a nice job of providing clear, interpretable theoretical results. Decent motivation is also provided. \n\n* The application to causal inference is a nice motivation (though it would have been nice to see an extended discussion)", "weaknesses": "Overall, while this is a nice set of results it would have been nice to see (a) a much more extended application of the theory to causal inference (or another relevant use case), and (b) the presence of _some_ amount of empirical evidence for the results. The authors also argue strongly that an advantage of the proposed approach is removing the soft sparsity assumption and replacing it with the SNR assumption. However, it's not clear to me in the adaptive case when we would expect for this to be advantageous. Shouldn't we expect some actions to be significantly favored during, e.g., a contextual bandit procedure that is pointed toward in the conclusion? It's also not entirely clear to me how useful the bounds provided in Theorem 4.4 are going to be outside of a theoretical setting. It would have been nice to have seen some empirical results to demonstrate their relative utility in lieu of the in-line proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our submission. Please find our responses to your questions/comments below. \n\n\n[*Overall, while this is a nice set of results it would have been nice to see (a) a much more extended application of the theory to causal inference (or another relevant use case)*]\n\nWe would like to point out that we include a more thorough application of our adaptive bounds to panel data in Appendix F (see Theorem F.5 for a non-trivial application of our bounds). While we included this application in the appendix due to space constraints, we are happy to move more of these results to the main body in the revision. \n\n\nAs for another use case, it has been shown that error-in-variables regression is a useful lens to think about differential privacy and regression ([5, 10]). In particular, if the covariates have been made differentially private by adding Gaussian noise, and we want to use these covariates for a downstream regression task, then this is an instance of  error-in-variables regression. And of course in many such settings, data is collected adaptively, and no prior results are able to tackle such a setting.\n\n[*Overall, while this is a nice set of results it would have been nice to see … (b) the presence of some amount of empirical evidence for the results.*]\n\nAs mentioned in the global rebuttal, we chose to focus on theoretical depth for our adaptive bounds on PCR (Theorem 4.1, Theorem 4.4) and our application to panel data (Theorem F.5) in this submission, as a meaningful empirical comparison cannot be made with previous work since the constants in the non-adaptive bounds are not specified, and therefore the non-adaptive bound cannot be computed.\n\n\n[*The authors also argue strongly that an advantage of the proposed approach is removing the soft sparsity assumption and replacing it with the SNR assumption. However, it's not clear to me in the adaptive case when we would expect for this to be advantageous. Shouldn't we expect some actions to be significantly favored during, e.g., a contextual bandit procedure that is pointed toward in the conclusion?*]\n\nWe would like to emphasize that the primary advantage of our bounds is that they hold in adaptive settings, whereas the bounds in previous work do not, and that we explicitly quantify the penalty paid for adaptivity (Line 182). With that being said, (1) it is reasonable to assume that in most contextual bandit tasks, different contexts have different optimal actions. Furthermore, (2) there is often sufficient diversity in the sequence of contexts encountered by a contextual bandit algorithm. For instance, in “A Contextual Bandit Bake-off”, Biette et al. find that when implementing popular contextual bandit algorithms on a wide variety of datasets, the greedy algorithm performed surprisingly well (2nd overall out of all algorithms implemented). The explanation given for the good performance of the greedy algorithm is that the inherent diversity in the distribution over contexts was oftentimes enough to provide sufficient exploration for good performance. Putting (1) and (2) together, we believe that in many practical contextual bandit settings, one or two actions will not be significantly favored over others.\n\n\n[*It’s a little confusing why we would have separate noise assumptions over the treated and control series (assumptions 3.1 and 3.2, respectively). I recognize that 3.1 contains 3.2 but the assumption is considerably stronger. It’s not clear to me when we would be able to assume both the low rank assumption and bounded noise in practical settings.*]\n\nWe emphasize that Assumption 3.2 is not required for any of our results to hold, and that all theorems hold under Assumption 3.1. We will make this clearer in the next revision. Assumption 3.2 just allows us to make stronger statements (e.g. tighter constants with respect to the results obtained under Assumption 3.1) in some settings. We also note that the low rank and bounded noise assumptions are orthogonal to one another, as assuming one does not make it easier or harder for the other to hold. \n\n\nFurthermore, the stated bounds do not require specifying which assumption (either 3.1 or 3.2) holds, as this only makes a difference in the definition of the signal-to-noise ratio. If Assumption 3.1 (resp. Assumption 3.2) holds, one would use the definition of signal-to-noise with $U_n$ corresponding to the line below 193 (resp. line above 194). \n\n\n[*The regularization justification seems a little strange. Aren’t we already imposing a regularization by restricting to the top $k$ principle components? It’s not entirely clear to me why imposing additional regularization is necessary in this setting.*]\n\nAs we note in Section 3, we choose to regularize since it is known that regularization increases the stability of regression-style algorithms in online learning settings. Since regularizing is a popular choice in online settings, by regularizing we are able to utilize existing online regression bounds from previous work. Such regularization is required for, e.g. the Method of Mixtures result of Abbasi-Yadkori et al. [3] (Lemma A.1). \n\n\n[*Theorem 4.4 seems like it could be quite loose in empirical settings. Do the authors have empirical results that examine this?*]\n\nPlease see our above comments regarding the lack of an empirical evaluation. \n\n\n[*In Theorem 4.4 $L$ appears to be undefined in the main text.*]\n\nThank you for pointing this out. $L$ is an upper-bound on the l2 norm of $\\theta(a)$. \n\n[*It’s unclear within the main text whether the authors are employing assumption 3.1 or 3.2. Given that the latter is stronger, this should be stated either within the theorem text or directly before/after.*]\n\nPlease see our above answer regarding your question on separate noise assumptions.\n"}, {"review_id": "kOGYeGpPdv", "reviewer": "Reviewer_1mVx", "summary": "Principal components regression (PCR) is common technique for handling data with error-in-variables. Prior studies had established bounds for PCR in traditional settings, but those bounds were not relevant for settings where data is collected adaptively. This paper provides computable bounds for the L2 error for coefficients in PCR specific to the adaptive data setting.", "questions": "Presumably there are no other established results for models with error-in-variables and adaptive data. While the results are interesting, is there any point of comparison for other methodologies in this relatively narrowly defined area?", "limitations": "Limitations have been adequately addressed", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "- The results of the paper are both new and technically sound.\n- The bounds are computable under fairly reasonable assumptions.\n- While I am not very familiar with martingale concentration, this paper provides further evidence that it is a reasonable approach for online learning problems.", "weaknesses": "- The paper satisfactorily describes how the new bounds compare to similar results for PCR in non-adaptive settings. However, there is limited discussion about why PCR might be a preferred methodology for online learning problems, beyond previous results in a generic error-in-variables setting.\n- I commend the authors for including a section for an application of their work in an otherwise heavily theoretical paper. However, after some setup, the ultimate result appears to simply be a restatement of Theorem 4.1 / Corollary 4.3 but with some terms being a bit more concrete. The ultimate applicability of the result is not obvious.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our submission. Please find our replies to your questions/comments below. \n\n[*The paper satisfactorily describes how the new bounds compare to similar results for PCR in non-adaptive settings. However, there is limited discussion about why PCR might be a preferred methodology for online learning problems, beyond previous results in a generic error-in-variables setting.*]\n\nWe would like to point out that our application to panel data is a salient application of online learning with noisy covariates. As we mention in the text, our framework may be thought of as a generalization of the synthetic interventions framework to adaptive settings, which itself is a generalization of the canonical synthetic control framework (a popular method both in theory and in practice). \n\nMoving away from panel data, another setting in which online learning from noisy data may arise is when the observed covariates need to be measured by a physical instrument. Since no measurement is perfectly accurate or exact, it may be helpful to explicitly take such measurement error into consideration when learning.\n\nIn offline settings, almost all previous works in high-dimensional error-in-variables regression other than PCR requires oracle knowledge of the second moment of the noise matrix (e.g. [61, 70]). It has been shown recently that PCR both theoretically and empirically is able to deal with such error-in-variables without knowledge of the noise distribution, which is clearly valuable in practice.   \n\n[*I commend the authors for including a section for an application of their work in an otherwise heavily theoretical paper. However, after some setup, the ultimate result appears to simply be a restatement of Theorem 4.1 / Corollary 4.3 but with some terms being a bit more concrete. The ultimate applicability of the result is not obvious.*]\n\nWe would like to point out that we include a more thorough application of our adaptive bounds to panel data in Appendix F (see Theorem F.5 for a non-trivial application of our bounds). While we included this application in the appendix due to space constraints, we are happy to move more of these results to the main body in the revision. \n\n\n[*Presumably there are no other established results for models with error-in-variables and adaptive data. While the results are interesting, is there any point of comparison for other methodologies in this relatively narrowly defined area?*]\n\nTo the best of our knowledge, there are no other results at the intersection of error-in-variables and adaptive data.\n\nThough it might seem as a narrowly-defined area, we formally establish that our results have important applications to the area of causal inference with panel data, in particular to the field of synthetic controls.  Specifically, our results allow us to estimate a variety of causal parameters of interest despite the intervention assignment being adaptive to the data itself, which clearly is true in many real-world settings. All previous formal results in the synthetic controls literature do not allow for adaptive data collection. \n\nSecond, it has been shown that error-in-variables regression is a useful lens to think about differential privacy and regression ([5, 10]). In particular, if the covariates have been made differentially private by adding Gaussian noise, and we want to use these covariates for a downstream regression task, then this is an instance of  error-in-variables regression. And of course in many such settings, data is collected adaptively, and no prior results are able to tackle such a setting.\n\nWe do indeed compare our results with the baseline of if the data is not collected adaptively (e.g. line 182), and we precisely quantify the penalty we pay in terms of sample complexity due to the adaptive data collection.\n"}]

Author rebuttal:
We would like to thank the reviewers for their helpful reviews. We have responded to each of your comments, and we hope to address any follow-up questions you may have in the discussion. 

To summarize our main contributions, we provide the first time-uniform finite sample guarantees for principal component regression whenever data is collected adaptively. Additionally, we apply our results to the problem of estimating unit-specific treatment effects in panel data settings, where our methodology may be thought of as a generalization of the popular synthetic control framework to settings in which data is collected adaptively. 

A common complaint from reviewers was that our submission contains no empirical results. We chose to focus on theoretical depth for our adaptive bounds on PCR (Theorem 4.1, Theorem 4.4) and our application to panel data (Theorem F.5) in this submission, as a meaningful empirical comparison cannot be made with previous work since the constants in the non-adaptive bounds are not specified, and therefore the non-adaptive bound cannot be computed.

Meta-review: The reviewers are largely in agreement that the authors provide a technically strong theoretical contribution to the literature on principal component regression and and to the synthetic control literature in causal inference. There is however an overall feeling among reviewers that the setting analyzed is quite specific and there are some assumptions on the independence of unobserved noise in the response variable on chosen actions can be strong in some applications. In looking at the work, I found the application to causal inference quite interesting and the latter assumption within that context a reasonable one. The authors are strongly encouraged to improve upon presentation and motivation if the paper is accepted.
Decision: Accept (poster)