Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inference
Authors: Licong Lin
Mufang Ying
Suvrojit Ghosh
Koulik Khamaru
Cun-Hui Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Adaptive linear regression
bandit algorithms
high dimensional statistics
statistical inference
TL;DR: We study the low-dimensional estimation and inference problem in adaptive linear models.

Abstract: Estimation and inference in statistics pose significant challenges when data are collected adaptively. Even in linear models, the Ordinary Least Squares (OLS) estimator may fail to exhibit asymptotic normality for single coordinate estimation and have inflated error. This issue is highlighted by a recent minimax lower bound, which shows that the error of estimating a  single coordinate can be enlarged by a multiple of $\sqrt{d}$ when data are allowed to be arbitrarily adaptive, compared with the case when they are i.i.d. Our work explores this striking difference in estimation performance between utilizing i.i.d. and adaptive data. We investigate how the degree of adaptivity in data collection impacts the performance of estimating a low-dimensional parameter component in high-dimensional linear models. We identify conditions on the data collection mechanism under which the estimation error for a low-dimensional parameter component matches its counterpart in the i.i.d. setting, up to a factor that depends on the degree of adaptivity. We show that OLS or OLS on centered data can achieve this matching error. In addition, we propose a novel estimator for single coordinate inference via solving a Two-stage Adaptive Linear Estimating equation (TALE). Under a weaker form of adaptivity in data collection, we establish an asymptotic normality property of the proposed estimator.

Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inference
Licong Lin Department of Statistics University of California, Berkeley liconglin inbooggl@bbekkeee... edu
Mufang Ying Department of Statistics
Rutgers University- New Brunswick my428@scarletmail etutee. edu
Suvrojit Ghosh
Koulik Khamaru Department of Statistics Rutgers University New Brunswick
Department of Statistics
Rutgers University New Brunswick sg1565@scarletmaill rutggrs..tgeee.e..
kk1241 @stat. rutgers. edu
Cun-Hui Zhang
Department of Statistics
Rutgers University New Brunswick
echang@stat.rutgerr
Abstract
Estimatiin and inference in statistics pose significant challenges when data are collected adaptively. Even in linear models, the Ordinary Least Squares (OLS) estimator may fail to exhibit asymptotic normality for single coordinate estimation and have inflated error. This issue highlighted by recent minimax lower bound, which shows that the eттor of estimating single coordinate can be enlarged by a multiple of vd when data are allowed to be arbitrarily adaptive, compared with the case when they are i.i.d. Our work explores this striking difference in estimation performance between utilizing i.i.d. and adaptive data. We investigate how the degree of adaptivity in data collection impacts the performance of estimating a low-dimensional parameter component in high-dimensional linear models. We identify conditions on the data collection mechanism under which the estimation error for low-dimensional parameter component matches its counterpart in the i.i.d. setting, up to a factor that depends on the degree of adaptivity. We show that OLS OLS on centered data can achieve this matching error. In addition, we propose a novel estimator for single coordinate inference via solving a Two-stage Adaptive Linear Estimating equation (TALE). Under weaker form of adaptivity in data collection, we establish an asymptotic normality property of the proposed estimator.
1 Introduction
Estimating a low-dimensional parameter component in a high-dimensional model is fundamental problem statistics and machine learning that has been widely studied in e.g., semiparametric statistics [35]]] g) causal inference [6 [5] and bandit algorithms 27 When data are independently and identically distributed (i.i.d.), it is often possible derive estimators that are asymptotically normal with rate of convergence of Vn, and that achieve the semi cam-meerattticc variance lower bound
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

that is independent of the dimension. There is now a rich body of literature that studies this problem
under various scenarios [5 33
In this work we are interested in the same estimation and inference problem but under the setting where the i.i.d. data assumption fails. Specifically, we consider an adaptive collection framework where the data collected at time i is allowed to be dependent on the historical data collected up to time i 1. This adaptive framework incorporates datasets originated from applications in many fields, including sequential experimental design [5] bandit algorithm 227. time series modeling (7]. adaptive stochastic approximation schemes
13
1.1 An interesting lower bound
To see the intrinsic difference between the i.i.d. and the adaptive data collection settings, we consider
the canonical example of linear model = x: 0" + E, where the parameter 0* (0) 02) e
RI x Rd-1
sid E=~N((0, 1). Clearly, when the covariates for are deterministic, a straightforward
calculation yields
Oots, 01 d (S,")),, and B((S,") (Dols. -1)
where Oats the OLS estimator and S,, = En= x is the sample covariance matrix.
However, somewhat surprisingly. when the covariates teshin are allowed to be collected in an arbitrary adaptive manner, a recent work [20] the authors proved the following (informal) counter- intuitive minimax lower bound on the scaled-MSE (defined in Definition 2.2)
min max T (0 01 2 ed log(n),
(2)
0 0"
where the extra d-factor enters the estimation of a single coordinate. This lower bound indicates that a dimension independent single coordinate estimation is infeasible when the data are collected arbitrarily adaptively. This is undesirable especially in the high dimensional scenario where d + oc. since a Vi-consistent estimation is unattainable. Motivated by the contrast between i.i.d. and adaptive data collection, we pose the following question in this work:
Can we bridge the gap between iid and adaptive data collection, and obtain an estimator for tow-dimensional parameter component in linear models, such that its performance depends on the degree of adaptivity?
1.2 Contributions
In this work, we initiate the study of how the adaptivity of the collected data affects low-dimensional estimation high-ddmensiioal linear model. We explore the previously posed question and provide an affirmative answer.
We begin by introducing general data collection assumption, which term (k, aadddtiiiv Broadly speaking, (k, ad-adaptivity implies that the data pairs { v:) E Id x R are collected in a way that the first k coordinates of x; (denoted by x²d") are chosen adaptively based on the historical data, while the remaining d - k coordinates of æ; (denoted by ædadd) are i.i.d. across time i E [m].
Assume the collected data are (k, d) adaptive from a linear model y = T + E. We analyze the lower-dimensional estimation problem under the scenarios where the i.i.d. non-adaptive components aqad are either zero-mean or nonzero-mean. In the zero mean case, we show that the ordinary least squares estimator (OLS) for the first k-coordinate yields a scaled mean squared error (scaled- MSE) of log(n) (Thcorem 3.1b. For the nonzero- case, a similar result is achieved using the OLS estimator centered data (Thcorem 3.2). Consequently, we find that the degree of adaptivity significantly impacts the performance of single coordinate estimation, in the sense that the scaled-MSS -MEE is inflated by factor of k, where & denotes the number of adaptive coordinates (see Corollary 3.3
Although OLS for single coordinate has dimension independent scaled-MSS when the collected data are (1, dd-adapiive it should be noted that OLS may exhibit non-normal asymptotic behavior [13] 20 when data are adaptively collected. Therefore, we propose a novel estimator by solving Two- stage Adaptive Linear Estimating Equation (TALE). When the collected data are (1, adddppiiee and the non-adaptive component zero mean, we show that our new estimator is asymptotically normal and has comparable scaled-MSE as the naive OLS estimator (see Theorem 3.4

---

2
Problem set up
Consider linear model
y 0 +E,
where the parameter E gd and zero mean noise variable. Given access to data set {( vi) from the model B are interested in the estimation and inference problem of low-dimensional parameter component lna R where 0 =O (h
In this paper, we are interested in adaptive data collection regime. Concretely, we assume that the data collected adaptively in the following way
Definition 2.1 ((k, adaapiiivy The collected samples {(z;; U/) Vi)s forms a filtration {F) with Fo and F; ( ,, Ms). Let be an unknown distribution gd-k, We assume that at each stage, 2
The adaptive component add Ti,1sk is collected from some unknown distribution that could depend on Fi-1.
The non-adaptive component apad 1id sample from and independent of (andd F,-1).
When = 0, Definition 2.1 reduces to an i.i.d. data collection strategy; when A = d it corresponds the where the data allowed to be collected arbitrarily adaptively. Consequently, (k: d)- adaptivity connects two extreme scenarios, and the degree of adaptivity increases as & increases.
Example 2.1 (Treatment assignment) As concrete example, consider the problem of treatment assignment to patients. At round i, we observe the health profile of the patient i, which we denote by 2; dd-1. Our job assign treatment A; E {0, 1} based on the patient's health profile æ; and also our prior knowledge of effectiveness of the treatments. It is natural to capture our prior the sigma field generated by previous data-points. As already pointed out in (2). in the adaptive regime the estimator error for treatment effect scales as /d/n: in words, we have to pay for dimension factor Vd even if we are only interested in estimating a one-dimensional component. While for our treatment assignment example, the dimension d - of the covariate vector x; is large in practice, it is natural to assume that the treatment assignment dependent on k < d 1, a few (unknown) components. Under this assumption, it is easy to see that this treatment assignment problem is (k, d) d'-adaptive. We show that the treatment effect can be estimated at rate / /k/n & dd/n.
knowledge using =,=o(Ai, 11 H,,.... Ai-1: 3; y/-1)) 11
2.1 Statistical limits
Before we discuss how obtain estimators for a low-dimensional parameter component of 0*, establish some baselines by recalling existing lower bounds. Throughout this section, we assume the noise E üdd (0, o²). We start with defining the metric for comparison.
Definition 2.2 (scaled mean squared error (scaled-MSE)) Given subset I C [d]. We define the scaled-MSE an estimator Öz for Oz R!4 be B[(O, 0T) [ TT] -1 (0 θτ)], where
S, Ei= x is the sample Gram matrix.
Roughly speaking, when the covariates æ; are all fixed, the scaled-MSE compares the performance of Oz against the estimator with minimal variance (OLS), Moreover, we have the following result:
Proposition 2.2 (A simplified version of Theorem 2 in Khamaru et al. (20)
(a). Given set C [d]. Suppose the data model 31. Then the scaled-MSR satisfies
are i.d.d. ((0, d)-adaptive) from
inf sup E. 0r
07 |
2 0² Z
(s=))
Φ eRERd
Furthermore, the equality holds when choosing Or be the OLS estimator for 0z,
3

---

(b). Suppose the data points {( 1-) are allowed to be arbitrarily adaptive ((d, d)- adaptive). For any (n, d) with d 2 2 and 2 d', and any non-empty set I E [d]. there exists a data collection algorithm such that
inf sup E Or 0 GRERd
02
(S. )(x)) 2 d' do² log(n),
(5)
where C, e O are some universal constants.
Proposition 2.2 exhibits the striking difference between two extreme data collection mechanisms. While the scaled-MSE scales O(II) when data are i.i.d., the scaled-MSF for single coordinate (e.g., setting I = {1}) can be of the order O(d) if the data are allowed to be collected arbitrarily adaptively.
Let I = [d] \ I. By the matrix inverse formula, we have
[SS
|z]] )zz]
(In) -
(Sn)IoI= - X1 (In - Px XI:
where Px,e denotes the projection onto the column space of Xx= E Rnxlzl, In this work, we are often interested in the special cases where I [k:] (or {e} for & E [k]),, which denote (a single coordinate of) the adaptive component.
2.2 Related work
Adaptive linear model In the early works by Lai et al. [24 231. the authors studied regression models when the data adaptively collected. They established the asymptotic normality of OLS under a stability assumption on the covariate matrix. However, the stability assumption might be violated under various setting, including data collected from online bandit algorithms such as UCB [27 2 31 34, (2), forecasting and autoregressive models 14, 38 24]. Recent works [3] 20 addressed this issue and proposed debiasing estimators with inferential guarantee in linear models with fixed dimension. While allowing for arbitrarily adaptively collected data, their results impose an additional vd factor in the error bound for single coordinate estimation, limiting their applicability in
linear models with increasing dimensions [9 28
Parameter estimation in bandit algorithms
Though with the primary goal being achieving a low regret, the problem of parameter estimation under adaptive data are also studied when designing
online bandit algorithms 1 26 29 (77). Many online bandit algorithms are built based on the
for the reward function [2] 177. which can be viewed as finite sample estimation and inference of the unknown parameter of a model. Most related our paper, in linear bandits, the works I (26] derived non-asymptotic upper bound scaled-MSE of OLS for the whole parameter vector, as well as for single coordinate. However, the upper bound on scaled-Mi -MME for estimating single coordinate is inflated by a factor of d compared with the i.i.d. case, as suggested by the lower bound in [20].
estimation or construction adaptive confidence
Inference using adaptively collected data The problem of estimation and inference using adap- tively collected data has also been studied under other settings. The work by Hadad et al. [15] and Zhan et al. [40] proposed a weighted augmented inverse propensity weighted (AIPW, 32] ) estimator for treatment effect estimation that is asymptotic normal. Zhang et al. 43 analyzed weighted M-estimator for contextual bandit problems. Lin al. 33 proposed weighted Z-estimator for statistical inference in semi parametric models. While investigating more intricate models, these works are built on the strong assumption that the adaptive data collection mechanism is known. In contrast, our (k, d) addapiiiy assumption allows the adaptive component to be collected in an arbitrary adaptive way.
Semi- parametric statistics A central problem in semi peramperaittric statistics is to derive vn- consistent and asymptotic normal estimators of -iw-dmensional parameter component in high- dimensional or semi- -armmeareettric models [S] 6
33 36 4 g, 41] Most works in this literature assume i..d. data collection and aim to obtain estimators that achieve the optimal asymptotic variance (i.e., semi-parametric efficient 35 16) On the other hand, our work focuses complementary perspective, with the goal of understanding how the data collection assumption affects the statistical limit of low-dimensional parameter estimation.

---

2.3 Notations
In the paper, we use the bold font to denote vectors and matrices (e.g., x, 0, E), and the regular font to denote scalars (e.g., I. E). Given data { H=) from the linear model (3) that are
(k; d)-adaptive, we use x E IR# xp E Rd to denote the adaptive and non-adaptive covariates. We also write 0* = (6 0 0ad ) to denote the components that correspond to the adaptive and non-adaptive covariates. Let X = (0I ..... ) E IRu be the covariate matrix, with X (or Xasd) representing the submatrices consisting the adaptive (or non-adaptive) columns. We use X; to denote the j-th column of the covariate matrix.
For matrix M with rows, let M_j be the matrix obtained by deleting the j-th column of M. We define the projection operator PM M M(M M) M) 'M" and the (columnwise) centered matrix M = (I, P1,,) MM, where I x x is the identity matrix and 1, TR is the all-one vector. For a symmetric M > O, we define | == Vær Mæ. Lastly, we use c, c', c" > 0 to denote universal constants and C, C², C" >> 0 to denote constants that may depend the problem specific parameters but not on k d, n. We allow the values of the constants to vary from place to place.
Main results
This section is devoted to main results on low-dimensional estimation and inference. In Sec- tion 3.1 and 3.2 we discuss the problem of estimating fow-dimensional component of 8*, and Section 3.3 is devoted to inference of low-dimensional components.
3.1 Low-dimensional estimation
Suppose the collected data {(x;, y:)) are (k,, d) adaativee In this section, we are interested in estimating the adaptive parameter component 0z RR
In addition to (ks, addapiiii, we introduce the following assumptions on the collected data {(x, y))
Assumption
(A1) There exists a constant Ux > 0 such that
1 S min (X mmax (aa) S nUxx
(A2) The non-adaptive components {æpad) } are i..d. sub-Gaussian vectors with parameter v > 0, that is, for any unit direction u E gd-1
E[exp[A(e ((u, x. nad
E[xxpad) 5 22
AA E R.
(A3) There exist constants < Jmin < Tmax such that the covariance matrix of the non-adaptive component Σ = Cov [ad satisfies,
0 < amin S mmin (E) S Tmax
Σ) Tmax-
(A4) Conditioned on (æ;, F,-1, the noise variable e, in is zero mean sub-Gaussian with parameter > 0, i.e.,
Eie a FF-1] = 0, and Eledes ( F APo YAER,
and has conditional variance 0² = Ele F-1] for all [n]].
Let us clarify the meaning the above assumptions. Assumption (Al) is the regularity assumption on the adaptive component, Roughly speaking, we allow the adaptive component to be arbitrarily adaptive as long as _ Xad is not close to be singular and a:dd has bounded &g -onoo.. This is weaker than the assumptions made in [I5 30), which assume that the conditional distribution of Xad is known. Assumption (A2) (A3) on the non-adaptive component, assume its distribution is non-singular and light-tailed. Assumption (A4) a standard assumption that characterizes tail behavior of the zero-mean noise variable. We remark that the equal conditional variance assumption in Assumption ( (A4) mainly required Theorem 3.4 while is sufficient to assume o² being a
uniform upper bound of the conditional variance in Theorem 3.1 and 3.2
5

---

3.1.1 Warm up: zero-mean non-adaptive component
We start with discussing special case where the non-adaptive component arian is zero-mean. In this case, we prove that the Ordinary Least Squares (OLS) estimator on (X, y) for Oad is near-optimal; see the discussion Section 2.1 Denote the OLS estimator by Ø (0 0 mand) T. Throughout, we assume that the sample size and dimension d satisfies the relation
n
Cdd,
(6)
log (n/d)
where C is an independent of (n, d) but may depend on other problem specific parameters. With this set up, our first theorem states
Theorem 3.1 Given data points { ((.: from a (k, d)-adaptive model, and tolerance level 5 E (0, 1/2). Let, assumption (aatfton[]A]]) (A4) the bound (6) in force, and the non-adaptive component ap is drawn from a zero-mean distribution. Then, have
10ad Oual Siallx, XIa -Px )aa S C"
Xad)/o)
(7a)
k log(n/6)).
(7b)
with probability at least
See Appendix A.3 for detailed proof. A few comments regarding Theorem 3.1 are in order. One might integrate both sides of the last bound to get a bound on the scaled-MSE. Comparing the bound (7b) with the lower bound from Proposition 2.2 up to some logarithmic factors.
this bound is tight in minimax sense,
It is now worthwhile to compare this bound with the existing best upper bounds in the literature. Invoking the concentration bounds from [26] Lemma 16] one have that
||.nd Ozal II (T,, Px,.d X 0nad
Ond Saalx _ X.a Se Se. dlog(nn0)
One might argue that the first inequality is loose component 0%d E R However, invoking the lower bound from Proposition 2.2, we see that the bound (8) is the best you can hope for if we do not utilize the (k, d)-adattivity structure present in the data. See also the scaled-MSE bound for a single coordinate estimation in 26 Theorem 8) which also has dimension dependence in the scaled-MSE bound.
only want to estimate low-dimensional
3.1.2 Nonzero-mean non-adaptive component
In practice, the assumption that the non-adaptive covariates are drawn i.i.d. from distribution P with zero mean unsatisfactory. One would like to have similar result where the distribution P has an unknown non-zero mean.
Algorithm 1 Centered OLS for l adaptive coordinates (X, y)
1: And f- -= Anad f- x
2: Xad Xad Inftadt Xnad Xnad 1n
3: Run OLS on centered response vector y ÿ 1, and centered covariate matrix
= (Xadi Xnad) E Raxd; obtain the estimator Ø -e_.. nad
Before we state our estimator for the nonzero-mean case, is helpful to understand the proof intuition of Theorem 3.1 A simple expansion yields
θ 8% X X x Xad) Xaa)-1(X X P x
ad Xad) e smaller order terms
show that the interaction term X] adaptivity and zero-mean property of Xnad. In particular, under zero-mean property, each entry of
ad Px is small compared the other terms under (ki d)-

---

the matrix X Xnad is a martingale difference sequence, and can be controlled via concentration This martingale property is not true when the columns of Xnad have a nonzero mean. As remedy, we consider the mean-centered linear model:
inequalities [T.
y yー 1, X ad
0 ad
X nad O + (e 16--- 6 1n)
where Xad = Xud 1n mm Xad. and Xuad Xuad 1, Xnad centered version of the matrices Xad and Xnad. respectively. The centering in (9) ensures that X is approximately zero-mean, but unfortunately. it breaks the martingale structure present in the data. For instance, the
elements of _nd Xnad not the column mean from each entry. Nonetheless, turns out that subtracting the sample mean, while breaks the martingale difference structure, does not break it in adversarial way, and
of martingale difference sequence because have subtracted
still
control the entries of X_ nnnd See Lemma A.1 part (b) for one of the key ingredient in the proof. We point out that this finding is not new. Results of this form are well understood in various forms in sequential prediction literature, albeit in a different context. Such results can be found in earlier works of Lai, Wei and Robbins [21 [2 24 and also in the later works by several authors 11 and the references therein.
Our following Theorem 3.2 ensures that the intuition developed in this section so far is useful to characterize the performance of the solution obtained from the centered OLS.
Theorem 3.2 Given data points {(x, Vi )i=1 from (k, d)--aapptive model, and tolerance level
E (0, 1/2). Let, assumption (Al) (A4) and the bound 6 be in force. Then, 0ad obtained from
Algorithm ! satisfies
T C Int Xad xad)/8
1|0ad
0 1 (I, -P Pxnnd Xun
(10)
C log(//)))
with probability at least 1 5.
See Appendix for a proof. Note that the variance of aad is given by X (I, - P Xad. The covariance matrix is the same X (I, P Px,ma) Xadd when the one vector 1, belongs to the column space of Xnad-
3.2 Single coordinate estimation: Application to treatment assignment
Let us now come back to Example 2.1 that we started. Let, at every round i, the treatment assignment A; depends on 1: (unknown) coordinate of the covariates æ; Rd--1. We assume that the covariates x/.s drawn i.i.d. from some unknown distribution P. Assuming the response is related to the treatment and covariates via a linear model, it is not hard to see that this problem satisfies (k, d)-adaptivity property. The following corollary provides bound on the estimation error of estimating the (homogeneous) treatment effect.
75
75
OLS
+
COLS
Scaled MSE
Scaled MSE
50
50
25
25
0
0
0
100
200
100
200
Dimension of adaptive covariates
Dimension of adaptive covariates
Figure 1: The plot depicts the empirical relation between the scaled MSE of the OLS and centered OLS estimate from Algorithm| I and the number adaptive covariates (k:) for carefully constructed problem. See Section B.I for simulation details.
7

---

Corollary 3.3 Suppose the assumptions from Theorem 3.2 are in force, and & E [k] be an index corresponding to one of the adaptive coordinates. Then, the wth coordinate of the the centered OLS estimator from Algorithm Saporittmmssatie satisfies
V Colgg det (et(X Xad)/0)
C log(n/o)
10ad. Cad,el I
& (Ln Px )
The bounds above hold with probability at least 8, and X_ denote the matrix obtained by removing the 8th columnfrrom X.
See Appendix A.5 for a proof of this Corollary. We verify the result of Corollary 3.3 via simulations as shown in Figure [ From the figure we see that the scaled MSE increases linearly as the number of adaptive covariates increases, matching with our theoretical predictions. See Appendix B for more details about the simulation.
3.3 Inference with one adaptive arm
In this section, we provide a method for constructing valid confidence intervals for 0nd- To simplify the problem, restrict our attention the case of adaatiidty and E[æqudd 0.
A two-stage estimator
Our goal is to derive an asymptotically normal estimator for target parameter in presence of nuisance component. We call our estimator a "Two-stage-adaptive haalppii---nnerresstttttnnnnnaae
based
estimator, or TALE-estimator for short. We start with prior estimate 0 0ndd 0 Bad and define our estimate ITALE for 0%a as a solution this
TALE-estimator:
Σ wr 2dd OTALE aad 0 (ad) O.
(11)
Recall that ÊTALE is scalar and the equation has unique solution as long as Eisiso wit
The weights (witisn in equation [II are of predictable random scalars (i.e. wy E (2 Fi-1)). Specifically, start with so O and so Fo, and define
w; [(81/80)27)
where
8 5p
Σ (2
and
(12a)
V80
t
f(x) = V /xllog e2x (log log e2x)²
for x > 1.
(12b)
Let us first gain some intuitions why TALE works. By rewriting equation have
warndd ad (BIALE
8%d
w
nad O nad
nad)
(13)
Un
Following the proof in 39 we have di (0 o2). Besides, one can show that with proper goes to infinity,
choice of prior estimator 0 Pt
aad- the bias term b, converges zero in probability important note that (39] considers the linear regression model where the number covariates is fixed, and the sample size goes to infinity. In this work, however, we are interested in a setting where the number of covariates can grow with the number of samples. Therefore, our approach, TALE-estimaton has distinctions with the ALEE estimator proposed in [39]. The above intuition is
formalized in the following theorem. Below, we use the shorthand 0 OLS OLS
nad to denote the coordinates of
the least squares estimate of 0 corresponding to the non-adaptive components.

---

Theorem 3,4 Suppose s/ + su/s, = o1(),, n/(log((n) -d))
d - and assumptions (A1) (A4) Pr
are in force. Then, the estimate OIALE: obtained using weights from (2a) and 0 nad - Onadi satisfies
OLS
Σ w.rf ) (BIALE fad) N(O,
Vv Eisisn W
where ō is any consistent estimate of a. Moreover, the asymptotic variance SYALE is optimal up to logarithmic-facttn
See Appendix A.6 for proof of this theorem. The assumption 1/50 su/s, op(1) in the theorem essentially requires $o grows to infinity in a rate slower than 8n. Therefore, in order to construct valid confidence intervals for OTALE. one has to grasp some prior knowledge about the lower bound of Sn. In our experiments in Section we set Su log log(n). Finally, it is also worth mentioning that one can apply martingale concentration inequalities (e.g. [[] to control the terms b, and 2, in equation
L3 which in turn yields the finite sample bounds for êTALE estimator. Finally, consistent estimator a can be found using 24 Lemma 3].
4 Numerical experiments
In this section, investigate the performance of TALE empirically, and compare it with the ordinary least squares (OLS) estimator, W-decorrelation proposed by Deshpande et al. [13], and the non- asymptotic confidence intervals derived from Theorem 8 in Lattimore et al. [26). Our simulation set up entails the motivating Example 2.1 treatment assignment. In our experiments, at stage i, the
061 is the least square estimate based on all data up to the time point i-1; here, the first coordinate of ((1) associated with treatment assignment. The detailed data generation mechanism can be found in Appendix. From Figure[[ we see that both TALE and W-decorrelation have valid empirical coverage (i.e., they are close to above the baseline), while the nonasymptotic confidence intervals are overall conservative and the OL.S downwardly biased. addition, TALE confidence intervals that are shorter than those of W-decorrelation, which indicates better estimation performance. Similar observations occur in the nigh-dimensional model in Figure (bottom), where we find that both the OLS estimator and W-decorrelation are downwardly biased while TALE has valid coverage.
treatments A; E {0, }} are assigned on the sign of 0(0) where 0 (0t)) 0
Upper coverage
coverage for 9
Width two-sided
Empincal coverage prababliy
1.0
Emgiiicall covern coverage prbbabiity
1.0
0.9
0.9
0.20
OLS
0.8
Baseline
Baseline TALE
width
Widecom Concen
TALE
0.8
QLS
0.10
0.7
W-detor
Widecorr
0.7
0.7
0.8
0.9
0.7
0.8
0.9
0.7
0,8
0.9
Target coverage probabiiity (1-gg
Target coverage probabilty (1
Target coverage probability (1.
Empircaal coverage probsbitty
1.0
Upper coverage 8
Empincaal coverage probabiity
1.0
coverage 8;
Width two-sided for
0.150
OLS
0.9
0.9
With Ch
0.125
W-decorr
0.8
Baseline
Baseline TALE
0.100
TALE
0.7
GLS
0.075
Widezorr
Widecorr
0.7
0.050
0.6
0.7
0.8
0.9
0.7
0.8
0.9
0.7
0.8
0.9
Target coverage probabiiit (1-
Target coverage probabilit
Target probabillty
Figure 2: Empirical coverage probability and the width of confidence intervals versus target coverage probability - a for TALE, the OLS estimator, non-asympiotic concentration inequalities, and W. decorrelation, We select the noise level o 0.3. Top: n 1000, d 10. Bottom: 500, d 50. At bottom right we do not display the result for concentration since the CIs are too wide, We run the simulation 1000 times and display the +1 standard deviation.

---

Histogram of the scaled errors for 0
Histogram of the scaled errors for 0
0.6
TALE
0.6
TALE
OLS
OLS
Density
0.4
Density
0.4
0.2
0.2
0.0
0.0
-2
0
4
4
-2
0
2
(6 8 1/v Var(e,)
(6: 0,1/ Var(e,)
Figure Histograms of the scaled errors for TALE and OLS. Left: n 1000, d 10. Right: 500, d = 50. We choose the noise level o = 0.3 and repeat the simulation 1000 times. Observe that the distribution of the OLS estimator is much more different than standard normal, and it exhibits a downwards bias (31. while TALE is in good accordance with standard normal distribution.
Discussion
In this paper, we investigate the statistical limits of estimating a low-dimensional component a high dimensional adaptive linear model. We start by recalling recent lower bound [20]. which states that we need to pay for the underlying dimension even if we want to estimate a low (onen--iiensional component. Our main result is show that in order to estimate low-dimensional component, need to pay only for the degree of adaptivity k, which can potentially be much smaller than the underlying dimension d. Additionally, we propose two-stage estimator for the -in-dimnniional target component, which is asymptotically normal. Finally, we demonstrate the effectiveness of this two-stage estimator via numerical simulations. For the future work, there are several avenues for further exploration that can contribute to more comprehensive understanding of adaptive regression models. First all, would interesting to generalize the (k, (dd--adapivvig for the case when the number of adaptive components may vary between samples. is also interesting to investigate if the current assumptions can relaxed or not. For statistical inference part, would be interesting to extend the TALE estimator to the case when the number of adaptive components is great than one.
10

---

Acknowledgments
This work was partially supported by the National Science Foundation Grants DMS-23113044 CCF- 1934924, DMS-2052944 and DMS-2210850.
References
[1] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In J. Shawe- Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] Peter Auer. Using confidence bounds for exploitation-exploraiio trade-offs. of Machine Learning Research, 3(Nov):397-422, 2002.
[3] Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
[4] Alexandre Belloni, Victor Chernozhukov, and Ying Wei. Post-selection inference for generalized linear models with many controls. Journal of Business & Economic Statistics, 34(4):606-619, 2016.
[5] Peter Bickel. On adaptive estimation. The Annals of Statistics, pages pages 647-671, 1982.
[6] Peter Bickel, Chris AJ Klaassen, Peter J Bickel, Ya' acov Ritov, J Klaassen, Jon A Wellner, and Ritov. Efficient and adaptive estimation for semiparametric models, volume 4. Springer, 1993.
[7] George EP Box, Gwilym Jenkins, Gregory C Reinsel, and Greta M Ljung. Time series analysis: forecasting and control. John Wiley & Sons, 2015.
[8] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21(1):C1-C6, 2018.
(9] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings, 2011.
[10] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Annual Conference Computational Learning Theory, 2008
[11) Victor H. de la Peña, Michael J. Klass, and Tze Leung Lai. Self-normalized processes: expo- nential inequalities, moment bounds and iterated logarithm laws. The Annals of Probability, 32(3):1902- 1933, 2004.
[12] Victor H de Pena, Michael Klass, and Tze Leung Lai. Theory and applications of multivariate self-normalize processes. Stochastic Processes and their Applications, (1211)):211-22222 2009.
[13] Yash Deshpande, Lester Mackey, Vasilis Syrgkanis, and Matt Taddy. Accurate inference for adaptive linear models. In International Conference on Machine Learning, pages 1194-1203. PMLR, 2018
[14] David A. Dickey and Wayne A. Fuller. Distribution of the estimators for autoregressive time series with unit root. Journal of the American Statistical Association, 74(366):477-31,, 1979.
[15] 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 Sciences, 218115)e2144602) 18, 2021.
[16] Jinyong Hahn. On the role of the propensity score in efficient semiparametric estimation of average treatment effects. Econometrica, 66(2):315-331, 1998.

---

[17] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensiones sparse linear bandits, Advances in Neural Information Processing Systems, 33:10753-10763 2020.
[18] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[19] Adel Javanmard and Andrea Montanari. Confidence intervals and hypothesis testing for high- dimensional regression. The Journal of Machine Learning Research, 15(1):2869-2900 2014.
[20] Koulik Khamaru, Yash Deshpande, Lester Mackey, and Martin J Wainwright. Near-optimal inference in adaptive linear regression. arXiv preprint arXiv:2 2021.
[21] T_ I__ Lai and Herbert Robbins. Strong consistency of least-squares estimates in regression models. Proceedings of the National Academy of Sciences, 74(7):2667-266) 1977.
[22] T Lai, Herbert Robbins, and C Zi Wei. Strong consistency of least squares estimates in multiple regression ii Journal of multivariate analysis, 933):343-361, 1979.
[23] Tze Leung Lai. Asymptotic properties of nonlinear least squares estimates in stochastic regression models. The Annals of Statistics, pages 1917-1930, 1994.
[24] Tze Leung Lai and Ching Zong Wei. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statisties, (0(1):154-16,, 1982.
[25] Tor Lattimore. A lower bound for linear and kernel regression with adaptive covariates. In The Thirty Sixth Anmual Conference on Learning Theory, pages (095-21133 PMLR, 2023.
[26] Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite- armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737. PMLR, 2017.
[27] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
(28) Lihua Lei, Peter J Bickel, and Noureddine El Karoui. Asymptotics for high dimensional regression m-estimates: fixed design results. Probability Theory and Related Fields, 172:983- 1079, 2018.
[29] Lihong Li, Yu Lu, and Dengyong Zhou, Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080 PMLR, 2017.
[30] Licong Lin, Koulik Khamaru, and Martin Wainwright. Semi-parametric inference based on adaptively collected data. arXiv preprint arXiv:2303.02534 2023.
[31] Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou. Why adaptively collected data have negative bias and how to correct for it. Advances in Neural Information Processing Systems, 84: 14:12 2018.
[32] James M Robins. Correcting for non-compliance randomized trials using structural nested mean models. Communications in Statistics Statistics-Therry and methods, 23(8):2379-244 1994.
[33] Peter M Robinson. Root-n-consistent semiparametric regression. Econometrica: Journal of the Econometric Society, pages 931-954, 1988.
[34] Jaehyeok Shin, Aaditya Ramdas, and Alessandro Rinaldo. On the bias, risk, and consistency of sample means in multi-armed bandits. SIAM Journal on Mathematics of Data Science, 1(4):1278-1300, 2021.
[35] Anastasios Tsiatis. Semiparametric theory and missing data. 2006.
[36] Mark Van der Laan, Sherri Rose, et al. Targeted learning: causal inference for observational and experimental data, volume 10. Springer, 2011.
[37] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48.
Cambridge University Press, 2019.
12

---

[38]
John S. White. The limiting distribution of the serial correlation coefficient in the explosive case ii. The Annals of Mathematical Statistics, 30(3):331833, 1959.
[39] Mufang Ying, Koulik Khamaru, and Cun-Hui Zhang. Adaptive linear estimating equations. arXiv preprini arXiv:2307.07320, 2023.
[40] Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 2125 2135, 2021.
[41] Cun-Hui Zhang and Stephanie Zhang. Confidence intervals for low dimensional parameters in high dimensional linear models. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):217-242, 2014.
[42] Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances in 2020.
Neural Information Processing Systems,
[43] Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical inference with m-estimators adaptively collected data. Advances in Neural Information Processing Systems, 34:7460-7471, 2021.
13

---

Appendix
Table of Contents
A
Proofs
14
A.1
Auxiliary lemmas
14
A.2
Proof Proposition 2.2
15
Proof Theorem
A44
Proof of Theorem 3.2
17
A.5
Proof of Corollary
19
A.6
Proof of Theorem 3.4
20
Proof cmma
22
Proof Lemma A.2
23
A.9
Proof Lemma A.3
25
A 10 Proof of Lemma A.4
25
B
Simulation set up
25
Single coordinate estimation
25
B.2 Single coordinate inference
26
A Proofs
Throughout the proof, we use c, e" to denote constants universal constants. We use C, C², C" > to denote constants that may depend on the problem specific parameters. Concretely, we use them to denote constants that only depends polynomially on (1, Omax 1/0min: U, Ux). We allows the values of the constants vary from place to place.
A.1 Auxiliary lemmas
Before stating our main theorems, list some useful lemmas, which can be of independent interest. All the proofs of lemmas can be found in Appendix A
Lemma A.1 Given n d 2 1. Let ((a,, be sequence of pairs such that a, E Rd are meesuaaaee and b; E RR are Fe-measurable w.r.. some filtration (Fi) Assume in addition that bj are zero-mean sub- Gaussian random variables with parameter a conditioned on F i.e.,
F 1] 0, and (e(e F e²x2122 for all E.R.
Let A (ai..... ] and (b.....,bl bb,) Suppose that S 0 O (ATA) S max (ATA) S
B for some constant B > 0.
(a). (A simplified version of Theorem in Abbasi al. (I].) With probability over 1-6
PAbli b PAb < co (og(det(ATA))) S co lod(log(B//))
for some universal constant > 0.
(b). Les A A P1, A be the centered matrix, then with probability over
b < c del A A)/5) co co2
for some universal constant > O.
In the proofs we choose (A (X nad: E), (Xad, E), (Xad, xj) for [k: 1.d. It is readily verified that conditions in Lemma A. are satisfied under assumptions in Theorem 3.1 and 3.2 See the proof of this lemma in Section A.7
14

---

Lemma A.2 Suppose the data set (.)] is (k, -d-adaptive and satisfies Assumption (Al)
(A4) Suppose the sample size condition (6) force. Adopt the notations in Section 3.1.2 Define
Xnad nad - E nsd] and recall that Xadd = (In, Pi,, Xadd. For the matrices Xnad, Xnad.
we have the following with probability over
nnd nad) olop S
(14a)
min (and))
717min
Ind llop S max
(14b)
X nad Xnad Mlop CV </oooo/C/o)vVa------
Omin (Xnad);
(14c)
C CVoo(nn/5v)
( and Xnad)
(X nad Xnad) Illop S
(14d)
n/3/2
k
Px Xnad
P Px Ilop S C &Cylognn/O
(14e)
[I Anad
Px nad ) 1 SC
(14f)
for some parameter-dependent constants C' > O. Moreover, equation 0 4a). replacing Xnad with the zero-mean matrix nad defined in Section 3.1.1
(1bb also hold when
See the proof in Section A.8
Lemma A.3 Under assumptions in Theorem
3.1
with probability over
C(d k)k log(n/5)
X
ad P Xad
X Xad
for parameter-dependentt constant C > 0.
See the proof in Section
A.9
Lemma A.4 Under assumptions in Theorem
3.2 with probability over 6
C(d k)k
Xad
ad Xad
n
for some parameter-dependent
constant C >
See the proof in Section A.I0
A.2 Proof of Proposition 2.2
Part (a). Proposition 2.2 a) is standard result on the minimax optimality of the OLS estimator in linear models. A proof of this result using Bayes argument can be found in the proof of Theorem 2(a) in Khamaru et al. 200..
((,)) conditioned on X. Therefore (0 (0ols,z - 02) ~ of, conditioned on X, where (S,, >zz denotes the submatrix S that consists of the coordinates in I. follows immediately that
By properties of the OLS estimator, we have (0.ls - 0")
E 0r
07
o² tr([Iz) O²|I
(S. )xr)
for any 0" E RRd. As result, the OLSS estimator attains the minimax lower bound when the data are i.
Part (b). When [Z] = 1, part (b) follows immediately from Theorem 2(b) of Khamaru et 20
with v chosen to be the one-hot vector supported on I. When [Z] > 1, w.l.o.g. assume I consists of the first [Z] coordinates of [d]. It suffices to show the scaled-MSB for I is always no less than the scaled-MSE for the first coordinate.
15

---

This follows from properties of Schur complement and the projection operator,
02 0
(S, 1771
-02 - 07) T ' (In
-xx
(x - -07)
(01 02) T
di 0
(=
0
(0r - 04) -7)
0 I
0
D2
Ix-1
d1 0
01 f
(0l 07
*)
D2
2 di (0) 0
where PM denote the projection onto the orthogonal space of the column space of M and
= x P X
x P X 1 Px XT.-1) (X X X X1;
D2 = X I.-1 P
XI,-1-
Using the properties of projection operator and linear space decomposition, it can be verified that
dj x Px X1 =
x (I, Px_,)x
00 02 0i|12
Therefore
2 01 -09 0i
This completes the proof.
(S. 11
[(S -1
A.3 Proof of Theorem
By the definition of the OLS estimator, have
X Xd Xad
X X
X X
0-0- =
X XTad Xnd
X X,ax Xund
X
Applying the block matrix inverse formula, we obtain
aad 0 XXd To simplify notation, we define
X X Px.ee Xad) -X X P EX.
R:: X Xad
X Px.pxx Pxane Xad:
R2 XJde X Xx E,
and let
R = X ad
Xad
RS = XT x
Therefore
@nn 02a) R (nn
0zd)
R2 R Ro.
We claim the following results which we prove later. With probability over 8
0 0 { 1 R R
(15a)
R. R R2 R. R R < C'lognn det((X)) [ T Xad)/6),
(15b)
R R R < C' (ong(de(XX))) X (
(15c)
Taking these claims as given, we establish
@nn R
Ri 0 0
R2
R Rs
< 2R T Ri R2, R
(16)
R
R
R
R
R
R
R
R R2 < C' C'lo(nn det ad Xad)/6)
(17)
where equation T6p uses claim 15a and equation displays together completes the proof.
uses claim 15b).
15c
Putting the last two
16

---

Proof of claim (5a)
The first and third inequality follows from the definition of R1 and RS. The
second inequality follows from Lemma A.3 and noting that C(d-R)k (og(n/)) 1/2 under the sample size assumption with C
6 chosen sufficiently large.
Proof of claim 15b Define PA- == (ATA) AT for any E Raxd Then we have
|Pabl2 = 2 for any b E R", Note that
R2 R R2 R2 R R2l
< R2 R2) R R22 R2)l + + R2) Ri Rz
Pxxnd Px P
Px + P Px Px.
E "xxma (Xnaddnadl) Xnad) 1/2 ( nad Pxna X
X
nad Xnad) 1122 Px2dx x
+ 2/e Pond (Xind X xnd))
-1/2x
nad Px Xxa El
X nad Px.m Xnadllin Illo
X
Px Px,,
El12
P el2
Xnnd
+
Px E112
Omin nad Bndd)
Ouin (X nad Xnad) 1/2
Applying equation (4a) and Lemma A.1 the last display, we continue
RR Rí R2 R2 R2 R2
C
nad Px Xand) P Px E X Px...
elle
tr (x
[P El
max
(x) Px x;) |x Px E112
ktISisd CVEmaxHHisisal x Px.xxi))1 E|12
P PX E|12
vn
Cld k)2 log(n det Xaa)/)) log(n/6)
Cvk(d k)
log(n det ( log" (n/8))
log2
n
< log(n det Xet)
where the fourth line uses Lemma A.1 and equation (14a). the last line follows from the sample size assumption (6).
Proof claim 15c
This a direct consequence of Lemma A. since e are conditionally zero- mean sub-Gaussian by Assumption (A4)
A.4 Proof of Theorem 3.2
Let μ² (HaT ( T
denote the mean vector of E [x.: and define
Xand == Xnad Lad
We write nad proof of Theorem 3.1
X++1
Ka]. The proof of this theorem follows the same basic steps the
Recall that 0nd E R denotes the non-adaptive component of the centered OLS estimator. By definition and the matrix inverse formula, we have
end ad (X II P Xand (and) X XIa P
To simplify notation, we introduce
R = TI
(I,
P
Xads
Ry == X (I, -Px )
and
R3 == Xad (In -
Xad:
Rig Xnn(In Pr e
Rndd
~ R4 == X E
R3 = X arl xad:
17

---

Consequently,
0nd 0%a) ( - 0mn)
R R R4.
Again, claim the following results which we prove later. With probability over - 8
0 1 2
R3 3 R3 R3: R
(18a)
R4 R R4
R R1 C Colo(nn det(X X and Xad)/o),
(18b)
C'lo((n det X T xad)/o)
R4 R
R4
(18c)
With the claims hand, we obtain
Ond R.
0%a)
R3 1ad
(nd)
Rg
R
R4
2
Rg R4.
(19)
Rg
R4
R
R.
R
R4
R4
Rg R4 S Colo(nn det X /6)
(20)
where equation
19 uses claim 18ap and equation
20
uses claim 18b).
(1c).
Combining the last
two displays concludes the proof.
Proof of claim 18a
The first and third inequality follows from the definition of R3 and R3. For
the second inequality, we have
R3 Rs -R3 R&) (Rs Rs)
Xad Px Xnd + X 8za (P 8and - -x Xad
ad Xad + x ad Xnd R3,
where the last line uses Lemma A.2 A.4 and noting that ((d=k)&log(n//) size assumption 6 with C' in 66) chosen sufficiently large.
1/4 under our sample
Proof of claim
18b
Recall that we define PA = 1/A for any A E Rxd Note that
R R R4
R
R R
$ (Ra R4) Rg R R4) + 2 R4 RA) R R
$ 2[ R4) T
R R R.) + RA4 R R
(R4 R.)
+ +I R,) R R [Ra RA) R R
=: 2(W1 + W2 + W3 + WWl,
where
Wi E T(PP PP
Xand
P Pxmm Px (Pxmm
P P
W₂ l T(P P -P Px el
W3 = E "P Px PX
W4 le PP
nad Px..el. El.
We next bound Wi(i 1,2, 4) respectively.
For W, and Wz, we have from Lemmal A.I and equation 14f that
W. < (1 X P
Px
)el12 S
W2 < ||e T (Px Xind P Px..)ll
Pl xnm El12 S CVV
18

---

For W3, similar to the proof of claim (1b).. we have
W3 = = Px Annd
nad und) 1/2
nad Px Xam Xand X
-1/2P x 2nnd
nad
(d k) maxx+ P Rnd xj
|P Xmad E
Omin nad Xudd)
Cld - 2)2 log(ndet(2 X aad) log(n/6)
S log(n del ad Xxd)/6)
where third line follows from Lemma A.1 Likewise,
and the last line follows from the sample size assumption (
W4 E Px P Px,E
E
$ P $1|2|1 and R xand)
1/2 11 1
X Rad P
Xnd E|12
cvd-k
mmin (R Rnd &nad)/) k+15JEd
max
||x] P
Xnd
||2|| Rnd
el12||
E|12
C(d - kt)
lot (X ad X llo(n//))
Vn
S det(( Xaa)//))
where the third inequality follows from Lemma A.I again. Putting pieces together yields the desired result.
Proof of claim 18c)
This is direct consequence of Lemma A.I
A.5 Proof of Corollary 3.3
W.l.o.g. assume 8 = 1. By Schur decomposition, we have
(0nd- 02a) T X Xad 02a)
(0ni Ora) (1 X1 Xad.-1
X T ad xadd
-1
X, (I,
P Pxad,11 X1
O
1--1
X - X1d,
X ad, 11 11d, xad,-1)
X T
I 1--1
(0ad 0ad
X1 (In - P
OT
(ad.1 - 02d.1
0ad.1 Oād.1 *)
X Xud, Xrd,-1/
2 (0ad,1 Ozd 0z (I, Px X... )81)
Therefore by Lemma
A.4 the sample size assumption (6 and Theorem 3.2 establish
(#ad,1 - 0% 2 (In - P (x.)
< (0ad 0ga) T X Xaa (Oad - 0%a) S C(0ad - 0%a) " (I, P P Xan 0%a)
Cllogín det (x xa)) Cl log(n(8).
Corollary 3.3 follows immediately from the fact that I, - Px_, - I, - P P since X
consists of some columns of X_1.
19

---

A.6 Proof of Theorem 3.4
We start with the following decomposition
Σ w.a
(OTALE
Σ
+
nad
(0 (fadd
@
To prove the theorem, it suffices to show
N(O,a
and
where A stands for convergence in distribution and is constant that is specified in equation 21
Proof of Un completeness, we provide a proof here. Note that function f is positive decreasing function and satisfies properties
(O, a o²)): The proof of this part directly follows from Theorem 3.1]. For
J f(x)d== and l P(x)dr =a.
(21)
Furthermore, it can be shown that
8²( 8i
(ardd)
1 f(8:/80) f(s(-1/5)) = =0((1.
max
(1) and
max Isisn
(22)
IS
Next we compute
(2nd)2
frau/o ((x)dx Eisn (sss/ (x. 5an/20 (2(x))de
An/40
f (s1/50)
90
1=1
i=1
((01150) - 1)f (1) Eisal EisaCrleilon P(R,/00)
8m/
(x) (1+
Eisn f2 so) (zze))
In equation (i), we consider the mean value theorem where |0:/50 (xx)dx= =f Consequently, we have
Eisn
(s.//ao) (E.//0l (155((//50)0 Eisn (o
Eiso
Pls 1/50]
Σ Eisn ((E:/50) (xtd))//s0
< max 1 P(ss/80)
(2(8 = (1.).
We conclude that
f. (2(x)d = a (1)
50/50
Σ : + +p)(
(23)
By noticing max sish wf max sisn gale central limit theorem that
f (s:/so) 1/56 = (1), we conclude from martin-
Σ mie S N((,a
Moreover, applying Slutsky's theorem yields
1
Σ
n
d N' 1).
(24)
aCE 1/21/2
20

---

Proof of bn _ 0: To simplify notations, let w (wi,...,, W.)) Without loss of generality, consider the first column of the design matrix collected adaptively. By the definition by we observe that
pad
Pr nad
(uad)
waz; 10 S
pad 1l2 10.10mad
0 Raad
10mmd
(25)
w xead ).
0 12
nad
2n.
bb,
Analysis of b By the construction of the weights (wissssn we have
|w0 $ J, P(z)de==
(26)
Applying Lemma A.1 with A and b x xlad conclude that with probability at least
6,
(w T xpadds s c log( w (1//8) I
(27)
where e is a universal constant. Therefore, with probability at least 6,
1 Vd. Vev²a (og(aa/0))
(28)
Pr Analysis of b, note mad ned the OLS estimate. Therefore, we can use biock-wise matrix inverse formula to get its expression. Precisely, we have
ools
(X and Xand) 1x] nad X
nad 0
+ JTd Xnad) ' Tade
|x
Px..XX11 x113
(29)
X nad X nadd -
X nad X X Xundl (X X nad Xnad) - 1 XTud u
||x Px...X X1
Therefore, upper bound b, by
bn.2 5
[X
and Xnad)
IIlopp
||X |Xx X1//2 ||x ell2
X1
Px X1
+
|X The Xpad) 1x Tad
(30)
[2) (2)
(X had Xnad)
|| Iad x - [[ Xnad) -1x "Tadeel2.
Xi
Px mad Xi 13
(9)
21

---

To analyze terms (222 b and by make use of the results from Lemma A.1 Lemma A.2 and
Lemma
A.3 Specifically, we have with probability 1 5, the following statements hold
(1) n.2
Xa Illop
X Xxaadxlla
||x|=||2 æ|12
|x|
Px 11
( o'
1 (1 (1- --Clloggn//6/n) | |x111//
1x1|l2 /1ggod/))x11////
||x 1 log([>>] (12/6)
e' d'Vllog(n dd/d)
Cdlog(n) (1/6)/n)m
602
11xX nad nad) ) -1x xxaadlla ellell2 2/222122 S (II nad Xnad) || |Xaade e|12
(31)
(8) d'
(dgg(1/))
n
6,2
nad nad) 'Illpp | and ||(
nad X nndd) 'x
X1
P Px..dd x1
(10)
| (ogg///og(d (log(d/8)
""
(1 - Cdlog(n/6)/m))
3/2
flog(dn2/8)) /8)33/2
S " (1 - Cdllogg/88)))
n3322
where d, c" and e" are universal constants that are independent of and d. inequatity (+), we use Lemma A.3 to obtain a lower bound for ||x - Px... X1 x1 and apply Lemma A. and Lemma A.2 to control the other three terms separately. Inequality (ii) makes use the fact that TijE; is sub-exponential with parameter (cve, cv/) conditioned Fi-1 for j ....., d. Therefore, by
incquality and the sample size assumption, we obtain for S j S d.
xx] el S vwy/log(/// Vn vlog(d/5) DU v n log(d/)))
with probability over 1 - 5/d d for any 2 S S Applying a union bound to j = 2....,
. d, we have
X | < C'nd
(32)
for some constant C". Inequality (iit) makes use of the bound for b and Lemmas A.1 and A.2
Therefore, when da log (m)/n - 0, we conclude
b 2n. = (1).
(33)
With 6n P. at hand, direct application of Slutsky's 's theorem yields
w.aaaaa nad ) -(0mad 0nad) P O.
(34)
V Eisign wf
Putting things together, we conclude that
wra ) (DTALE - 0f) N0,,0,
(35)
V W
A.7
Proof of Lemma A.1
Proof of Part (a)
The proof follows immediately from choosing V Ia Theorem of Abbasi
et al. [
22

---

Proof of Part (b) Define S1 = A A and Aaug = A
1n Then
b b_P bJ AS -1 5,,5 -1 A
b Auug (A ang
A Augg)"
Lx (A
(Is 0)
(Ik
0) (A auag Aug
-A
A aug
X b A (A
A ang )
Sug (A aug Aug))
A T b
aug
aux
bT Aaug (AT (Aaug A Aaus)
S co log(det( A aug
A A6))
c log(n det(A A)/5)
for all h: ++152 < d with probability over 1 6. Here the first equality comes from the definition of P: the second equality uses the fact that the coefficients of A in the ordinary least squares (OLS) estimator for the linear model ~ A + equals the OLS estimator for the centered linear model b b A. i.c.
Ix 0
(I&
0) (A Anug)
aug
A sug
S₁ 7
(A PI,,A)
S1
0g
third line is due to the fact that
Angg Aaugi the fifth line follows from Lemma A.1
0g
0
and the last line exploits the Schur complement of A A A.
A.8 Proof of Lemma A.2
Let μ² (Had (und)
denote the mean vector of [2[x and define
X Xuad
Ln
Proof of (14a) and [4b).. Applying the concentration result for a sample covariance matrix of nub-Gaussian ensemble (see e.g., Theorem 6.5 in Wainwright (37)), we obtain
d k log (1/8) + k + log(1/8)
nad nad nop S cv'n
n
with probability over 1 8. Using Weyl's theorem (see e.g., Theorem 4.3.1 in Horn al. 18] the sample size assumption and the last display, we find that
Omin uad Xad) 2 710mi (E) - X Ind Xnnd - n22illop 2 70
2
Similarly, we have X nnd op (amax X 14bp.
und Xnnd)) < /n(mmax + Omin/ S
220
This concludes [4a].
Proof of (1c
Recall that we use fi. = (Pad (uad) T to denote the empirical average of (æ;) 1=1 From Assumption (A2) and properties sub-Gaussian vectors, we have with probability over
P Mimalle S cu (oogoo(ddk)/))))) /
(36)
follows immediately that X|[
Xnad olpp = (P Pind) llop ||Anad Mund / C' (lg((n/8))d
The second inequality in (4ch follows from equation (1a)) and the sample size assumption
Proof of equation 14d) and 14e).
By Woodbury's matrix identity, we have
X
aad
X
nad Xand) lloo
Dari
nadi x |lop nad Xnnd X nad X Xndd |llop |II (X nnd Xnad) -Iloop-
X
23

---

By equation 14a
14b
14c
and standard triangular inequality, we find
Xaad
und nnd ol S CC/log(n/o)V/L k)n min
20min ( X Xnd))
where the second inequality follows from the sample size assumption (6 Therefore, we have
2
||| nad Xnad) ol S
min (X nad X Kadd
and hence
[ bad Xund) (X nad Xnad) 'Ilopp S
X nad X nad nad nad llop
Omin X
nad xnad) )2
C CV log(n/0)
(37)
n3/2
This gives equation (1d Moreover, note that
P Xmnd llop
Xnnd
X madd Xand) (X und Xand) 1 X llop
nad
(X Bad Xnna) -1 (Xnnd Anna))lloy + 2|| [ nnd Xnad) T (X nad X Xand) nnalllop
+ [Xnad= Xnad) (X
nad op
(x X nad) (X nad X nadd) 'Illop
X Xaad oloop (Ill Xnad Xnad op 2 Xasd (lpp)) ||| [X and Xnad) 'Ilopp 'Iloop
It follows immediately from equation
14a]. 14b).
(14c). 14d and (37 that with probability over
1-8
C
Clo((n (nd0///dddd-aa -
P X,nd
P Px Pxama
llop I
n2
This yields equation (14e)
Proof of equation
I4f.
Define = ft n². We have
Xnnd
Xnad Jell2
X Xnad X -1 AI E|12 + |I (Xan Xnsd) X [ and x
< Xund XX Xnad Xnad)
|lopl A 12 E| Xnad X (Xnaa Xnnd)
-nnd X und Xnnd)
1llop11
X had X Illp |P &.m e112-
Since |1,Tel < cv co (1)8) with probability over - 8 by Assumption (A4) and concentration of Sabb-Gasssinn variables, and
nad and Xnad) Xnad [ and Xnad)
llop
X nad X op Ill (X (Xnad
(Xnndddnaa Xnad)
-llpop
Xnad |lop nnd Xnad)
T
X nnd X 'llop
by tion
the
triangular
inequality,
it follows
immediately from
combining
equa-
14a
14b).
14c
14d).
36).
37
that
(d k) log(n/0) log(1/5) + (d - k)2 log loggl222///) (n/0)
X
Px
P
Jell2 c[V
Sc
n
with probability over 1 1-6 6.

---

A.9 Proof of Lemma A.3
Denote (X ad aad) 1/2X X ad (X Xad) 11/2 by B. By our construction and noting that
B lopp - (r) suffices to show
(r B C(d k)k log(n/0)
with probability over 1 for some C 0. Plugging in the definition of P Px..a we obtain
tr(B) tr( tr((X Xad) x Xnad (Xnutt madd) -'x nad Xud (X Xac)
= tr(X nad and (X) Xad) 'x x Xnnd (X 1)
< tr nad Xnd [X ad Xad) X X nad)) |Il(X nad X Xnad) - 'Ilp
tr( had Xnd (X Xxdxxxx. X
X Xadx X
(38)
M0wii
with probability over 1 1- where the third line follows from Neumann's 's trace inequality (see e.g.. Theorem A.15 Bai et al. (I), and the last line uses equation ([4a). Write X = [x1, X2, ..,.... Xx]
Baxk and nad Xk+1, X6+2, x.]] E Rnx(ddk), Following the calculation, we further have
tr [ nad Xad (X ad Xad)
X Xnad) = E Xj Px.
(39)
It follows from Lemma A. that
x Px Ck Chlog(n/))
(40)
for all + j I d with probability over 1 The desired result follows immediately from combining equation (40) with (38 and (39)
A.10 Proof of Lemma A.4
Following the same arguments as in the proof of Lemma A.3 with X replaced by X = X P1, Xad. suffices to show
x P_Px.. x, I Ckllognn6))
(41)
for all & 1+11js with probability over This follows immediately from Lemma A.1 (b).
B Simulation set up
We provide implementation details of our simulations this section. The code is available at www.:ooo--iiiioooo-nndeeeeee
https://github..
B.1 Single coordinate estimation
In this section, detail the simulation up that was used to generate the Figure [ The goal of this simulation is to display the effect of degree of adaptivity i on the estimation of a single coordinate, and provide empirical validation the theory developed in the paper (c.f. Corollary 3.3
We want to design an adaptive data collection mechanism, which can capture the estimation lower bound. Therefore, we adopt similar data collection procedure as provided in Khamaru et al. [20]. for related information.
We also refer readers to Lattimore 255
Simulation set-up:
Sample size n 1000, = 300.
The degree adaptivity & varies from 2 to 200 with step size equal to 3.
Replication number 20 for each level of adaptivity (k, d).
0ad and other coefficients are generated independently from N/ 1).
xpad is generated independently from uniform distribution on the sphere - If x has mean not equal to zero, then we consider anda plus Rayuad, where Ean is generated from (1,
25

---

Data collection method: Here we modified the data collection algorithm from Section 5.2.2 in Khamaru et al. [20] The only difference between our data collection algorithm and the one in Khamaru et al.
20 is that we replace 1
bw (Vu,w
Uu,w) by
w=l
Mayy U
bw
(Yu.u
au,w
Bad @
a uut(w- (w- 1)d11)
(42)
Figure I shows that empirical relation between the MSE of the centered OLS estimate of the first coordinate and the degree of dependence k.
B.2 Single coordinate inference
In this section, we detail the simulation set up that is used generate the Figure 2 and
We generate dataset {(r,, J:) that satisfies the assumptions in Theorem 3.4 On this simulated dataset, we compare our method with the ordinary least squares (OLS) estimator, W-decorrelation proposed by Deshpande (13), and the non-asymptotic confidence intervals derived from Theorem in Lattimore al. [26].
We begin by describing our data generating mechanism. We assume the data ((a,, vi)
Rd TR.
are generated from linear model y x 0* Es, where E sid (N10 (?). We generate the covariates (x, 1 in the following way
1. We assume the non-adaptive component B4,2:d are WV,, I2-1) across E [n].
2. For the adaptive coordinate, choose 11,1 and assume æ1,1 {0,1) for all E [m].
3. At each stage i 2 2, denote by 8()) the OLS estimator for the first coordinate 0f obtained using the first 1 samples (X15-1, y V.i-i).. 1). With probability we choose 24,1
g > 0 and æ;,1
otherwise; with probability p we simply choose T4 1 to
encourage exploration.
Recalling Example 2.1 on treatment assignment, in the simulated data, we use the OLS estimator to obtain prior estimate of the treatment effect 0j and assign the treatment to the i-th patient if
the prior estimation suggests that the treatment has a positive effect (i.e., 0(4) > 0). Moreover, to encourage exploration, we assign the treatment (i.e., FT,1 1) with some small probability p. regardless the prior estimation.
Throughout the simulation we choose =1-1/Va and 0 0, which corresponds to the case where no treatment effect is presented. We choose the noise level 0.3 and the probability p = 0.8. In the simulations we assume the noise level is known for simplicity. We run our simulations on both a low-dimensional model (n 1000, d = 10) and high-dimensional model (n 500, d = 50).
Comparison with W-decorrelation by Deshpande et al. 13 decorrelation, we follow Algorithm in [3, with the parameter À log(n) be the 1/n-quantile of Jmin (X X). To estimate the quantile, we use the sample estimate from 1000 i...d. data matrices X's to estimate the quantile.
In our implementation of W-
26


Reviews:
[{"review_id": "5m8pYWZViG", "reviewer": "Reviewer_4hmk", "summary": "This paper investigates degree of adaptivity in data impacts the performance of estimating a low-dimensional parameter component in high-dimensional linear models.  The main result is giving an error bound of a low-dimensional component that does not have diension dependence. They propose an estimator TALE. For a special case when there is a single adaptive coordinate and non-adaptive components have zero mean, this estimator is asymptotically normal.\n\nThe manuscript is easy to read through and the technical content of the paper appears to be correct albeit some typos:\n\nLine 69: Adaptive\nLine 478 in the appendix: $X_{\\mathrm{ad}}$", "questions": "Numerical experiments:\n- The authors highlight that TALE exhibits shorter confidence intervals (CIs) compared to W-decorrelation, suggesting better estimation performance. However, it's noteworthy that OLS achieves much shorter CIs than TALE, especially in the higher-dimensional scenario where $d=50$. CI of TALE is about 50% longer than that of OLS. It would be helpful if the authors address this observation to provide a comprehensive evaluation of the methods. Also, given that, how could the authors conclude that TALE outperforms OLS in terms of estimation performance? \n- From Figure 2, we can see that OLS is indeed downwardly biased. However, we can also observe that the magnitude of errors might be the same. The main results show a tighter bound (from $d=50$ to $k=1\"), but the practical benefit is not evident. Additional analysis or insights would help demonstrate its significance.", "limitations": "In addition to the limitations mentioned earlier, the authors noted that they did not provide asymptotic normality guarantees when the adaptive component has more than one dimension.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Theoretical results:\n- The authors define (k,d)-adaptivity to quantify the level of adaptivity along with a concrete example. Using this idea, they can get the upper bound depending on $k$ in stead of full dimension $d$. These results could bridge the gap between iid and arbitrarily adaptive data collection.\n\nExperiments:\n- Compared to other methods like OLS, estimation errors for TALE are in good accordance with a norm distribution.\n", "weaknesses": "Theoretical results:\n- The main result in this paper demonstrates the advantages of utilizing the $(k,d)$-adaptivity structure, yielding a scaled-MSE bound in the order of $k\\log(n)$ instead of $d\\log(n). While this is a positive outcome, it's worth considering that the result is based on a different norm, which makes it less convincing.\n\nExperiments:\n- In the introduction,  the paper aims to obtain an estimator with performance dependent on the degree of adaptivity. Besides, the main results highlight that having $k$ in the upper bound. Therefore, I believe it would be better for the authors to experiment with different levels of adaptivity.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and provide helpful feedback! We truly appreciate your comments and suggestions and believe they can make our work better.\n\nIn the following we hope to address each of the points made in the review, in the order as they came out.\n\n**Typo: Line 69: Adaptive Line 478 in the appendix:**  Thanks for pointing out the typos! We have fixed them.\n\n**Strengths:**  Thanks for your kind words.\n\n**Weakness:**\n* First, we want to clarify that we use scaled-MSE as the metric in both our lower bound and upper bound results. Namely, eq. (5) and (7) are both bounds on the scaled-MSE when $\\mathcal{I}=\\mathrm{ad}$. Therefore we believe it is fair to conclude the improvement of the estimation error from $d\\log(n)$ to $k\\log(n)$ since they are computed under the same metric (see Proposition 2.2 and Theorem 3.1). We will clarify this in the final version of the paper. The reason we choose scaled-MSE as the metric is that we believe this is the most appropriate metric to use when evaluating an estimator in linear models.   As shown in eq. (1), under fixed design the scaled-MSE accounts for the variance $\\mathbf{S}_n^{-1}$ induced by the design matrix, and is of order $O(1)$ for a single coordinate. Unlike $l_2$ norm or other more common metrics, the value of scaled-MSE is free from the choice of the designed matrix $X$ (while the $l_2$ error of one coordinate of  OLS is of order square root of the (1,1)-entry of  $\\mathbf{S}_n^{-1}$), and thus is fairer to use when comparing the performance of estimators across different linear models.  In addition, we agree that in Theorem 3.2 (eq. 10) the metric we use does not exactly match the scaled-MSE, but they are the same whenever the non-adaptive component contains the all-one vector, which is often the case in practice.\n\n*  Thanks for the suggestion! Instead of proposing novel estimators for estimation, our main focus of the parameter estimation part is more theoretical-oriented, with the goal of understanding the theoretical limits (and the worst-case scenarios) of parameter estimation under different levels of adaptivity. Therefore, we did not include experiments on the level of adaptivity in the paper. However, to validate our theory, we conducted additional simulations by keeping $d$ fixed and varying $k$. By adopting a similar adaptive data collection procedure to the one presented in Khamaru et al.[20], we are able to show that the single coordinate estimation error grows linearly in $k$. Please see the global rebuttal and attached pdf for the simulations. \n\n**Question:** Thank the reviewer for pointing out the confusion in the experiment results. We hope our reply below can clarify the concerns.  As mentioned in the paper,  the reason we propose TALE is to obtain an estimator with inferential guarantee even when the data are adaptively collected. We completely agree that OLS usually has smaller estimation errors and smaller \"confidence intervals\" in practice than TALE. However, the issue of OLS is that it does not have valid inferential guarantees when data are adaptively collected, in contrast to the i.i.d. case. In Figure 1 (left), we see that OLS fails to have valid upper tail coverage (meaning the line corresponding to OLS is close to or above the baseline). In Figure 2 we see OLS estimator is not even unbiased. As a consequence, the \"CI\" deduced from OLS may not be valid, meaning that for example a 80% percent \"CI\" only covers the true parameter with 75% probability. \n\n Therefore, the takeaway is that, if we only need an estimation of the true parameter without knowing how good or safe the estimation is, we should simply apply OLS. However, if we also want to know the quality of our estimation and provide confidence intervals for it, TALE might be a better option. In other words, TALE trades off accuracy for inferential guarantee, and we suggest people choose between OLS and TALE based on practical needs.\n\nIn direct reply to your questions: 1). We are sorry that our writing might have left the impression TALE has a better estimation performance than OLS (line 306). As we mentioned we believe OLS likely has a better estimation performance, and what we did (line 306) was comparing the estimation performance between W-correlation and TALE. Sorry again for the confusion.     2). We agree that in Figure 2 the magnitude of errors of OLS and TALE seem to be the same.  This is actually in accordance with our theoretical results. As stated in Theorem 3.1, 3.4,  OLS gives O(1) scaled-MSE for single coordinate under (1,d)-adaptivity and zero-mean $X_{\\mathrm{nad}}$,  which are assumed in the experiment setup, and TALE has near-optimal asymptotic variance. The main benefit of using TALE is its asymptotic normality guarantee instead of the estimation performance.  (Not sure if we understood your question correctly, feel free to let us know if you have more concerns.) \n\n**Limitations:**  We express our gratitude to the reviewer for their insightful question. Our immediate objective is to extend the TALE estimator to encompass multiple coordinates and incorporate $(k,d)$ adaptivity. To ensure asymptotic normality guarantees for all $k$-coordinates associated with $x_{ad}$, we need to construct $k$-dimensional weights $w$ which ensure asymptotic normality of the term $v_n$ and facilitate good control of the bias term $b_n$ (see equation (13) in the paper).  Currently, we are able to formulate weights $w$ that ensure the asymptotic normality of the term $v_n$. However, the conditions necessary for effectively controlling the bias term $b_n$, with these weights, are somewhat stringent based on our present calculations. In the revised version of our paper, we will highlight this limitation and provide an elaborate discussion on the methodology behind constructing these weights in $(k,d)$-settings, shedding light on the challenges posed in controlling the bias term. \n\n\n\n\n \n\n\n\n\n"}, {"review_id": "TNWmFrWh2h", "reviewer": "Reviewer_nCuW", "summary": "As I have communicated with the area chair, I will not be reviewing due to a conflict of interest. Submitting default ratings intended to be ignored below.", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "NA", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "h9QzexYqDi", "reviewer": "Reviewer_1ej5", "summary": "The paper introduces a new data collection assumption that captures the partially adaptive data and then derives a bound for scaled MSE of order $k\\log n$, where $k$ is the number of entries that are collected adaptively.  Finally they also introduce a novel estimator for single coordinate inference which has  an asymptotic normality property.", "questions": "It is not very clear to me what is the technical difficulty to generalize the original bound involving $d$ (Lemma 16 of Lattimore and Szepesvari) to the bound of order $k$, and how the proof in this paper solves it. ", "limitations": "See 2. in Weakness section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly structured and well-written. The theorems seem solid, and the assumptions are general. The authors also provide a concrete example of $\\textit{treatment assignment}$ to showcase the power of their theorems. ", "weaknesses": "1. The numerical section is focused on the performance of TALE, missing out the numerical verifications for Theorem 3.1 and 3.2, which are the main theorems of the paper. \n\n2. There still seem to be some fundamental limitations for the definition of $(k,d)$-adaptivity. For example, $(k,d)$-adaptivity requires a fixed number of entries in covariates $x$ are adaptively collected, which ignore the important scenario when such the number and indices of such entries may vary. \n\n3. While the example of $\\textit{treatment assignment}$  is very helpful, no comparison has been made against the state-of-the-art statistical tools and no numerical experiments are provided.\n\n4. Typo in line 106.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and provide helpful feedback! We truly appreciate your comments and suggestions and believe they can make our work better.\n\nIn the following, we hope to address each of the points made in the review, in the order they came out.\n\n**Strengths:** We are grateful for your positive feedback!\n\n**Weakness:**\n\n1. Thanks for your valuable suggestion. Our main focus of the parameter estimation part (theorem 3.1, 3.2) is more theoretical-oriented, with the goal of understanding the theoretical limits (and the worst-case scenarios) of parameter estimation under different levels of adaptivity. Therefore we did not provide simulation results in the first version of our work. To address your concern,  we have conducted additional simulations regarding estimations by varying the levels of adaptivity.  More specifically, we keep $d$ fixed and varying the number of adaptive variables $k$. By adopting a data collection procedure similar to the construction in Kharmaru et al.[2], Lattimore [1],  we demonstrate the single coordinate estimation error grows linearly in $k$. See the global rebuttal and attached pdf for more details on the experiment.\n\n2. Yes there are indeed some limitations in our definition of $(k,d)$-adaptivity. As the reviewer mentioned, the assumption does not directly apply to changing number of adaptive entries. One way to remedy this issue is to define $k$ to be the maximum number of adaptive entries across time. We agree that this solution is a bit crude when the number of adaptive coordinates varies a lot. One interesting and promising future direction is to understand the case when the number of adaptive coordinates is small for \"most\" of the samples.  We thank the reviewer for this engaging question.\n\n3. Since throughout the paper we assume the data are generated from linear models, the state-of-the-art estimator people use is simply the OLS estimator, which is also semi-parametric efficient when data are i.i.d.  Other standard estimators for the average treatment effect (e.g., doubly robust estimators, IPW, AIPW) are more useful when the linear model assumption does not hold. In the current version of the paper, we focused on establishing the theoretical baseline for estimation and inference in the high dimensional adaptive linear model regime, and we chose simulated experiments for comparing various competing methods. We also conducted additional simulations which validate the theory developed in Theorems 3.1 and 3.2 of our paper, and we intend to include them in the final version of the paper. Our immediate future goal is to apply these methods to real datasets and see how these methods compare with existing state-of-the-art methods. We thank the reviewer for their thoughtful suggestion. \n\n4. Fixed it. Thank you!\n\n**Question**: Thanks for asking the technical question. On one hand, Lemma 16 (or Theorem 8) of Lattimore and Szepesvari assumes completely adaptive covariates (i.e., $(d,d)$-adaptivity). Therefore, according to the lower bound in our Proposition 2.2,  the $d$ dependence in Theorem 8 of Lattimore and Szepesvari is unimprovable. On the other hand,  we can obtain $k$ (instead of $d$) dependence under $(k,d)-$adaptivity because the assumption implicitly imposes a martingale condition on the covariate vectors and hence allows us to have tighter bounds on terms like $X^\\top_{\\mathrm{ad}}X_{\\mathrm{nad}}$. We refer the reviewer to Lemma A.3, A.4 and proofs of the theorems for more details.\n\n1. Lattimore, Tor. \"A Lower Bound for Linear and Kernel Regression with Adaptive Covariates.\" In The Thirty Sixth Annual Conference on Learning Theory, pp. 2095-2113. PMLR, 2023.\n\n2. Khamaru, Koulik, Yash Deshpande, Tor Lattimore, Lester Mackey, and Martin J. Wainwright. \"Near-optimal inference in adaptive linear regression.\" arXiv preprint arXiv:2107.02266 (2023)."}, {"review_id": "2OJoxVfkRK", "reviewer": "Reviewer_Pp5b", "summary": "This paper considers the issue of adaptive data collection in a linear regression model. To summarize the main idea, let us focus on the leading example in the paper (that is, Example 2.1, treatment assignment). In this example, a patient is treated based on effectiveness of the previous treatments as well as a small number of covariates. When the treatment is assigned adaptively in an unknown way, the treatment effect can be estimated via OLS only at a rate $\\sqrt{d/n}$, where $d$ is the dimension of the entire covariate vector (not the dimension of the covariates used for treatment assignment) and $n$ is the sample size. This result is shown by previous work in Khamaru et al. [21] and a simplified version is given as Proposition 2.2 in the paper. One of the main results in the paper is that the centered OLS estimator of the treatment effect attains a better rate of convergence, that is, $\\sqrt{k/n}$, where $k-1$ is the dimension of the covariates used for treatment assignment. The inference problem is further studied for the case that $k=1$. That is, the treatment assignment mechanism does not depend on the covariates but on the effectiveness of the previous treatments. The paper proposes an adaptive estimator called Two-stage Adaptive Linear Estimating Equation (TALE) Estimator. The adaptive weights are constructed in a particular fashion to develop asymptotic normality (see Theorem 3.4). Numerical experiments show potential usefulness of the proposed TALE estimator.         ", "questions": "- Line 191: it seems that the conditional variance $\\sigma^2$ is a constant, meaning that it does not depend on $(x_i, \\mathcal{F}_{i-1})$. This is a restrictive assumption and could be commented in line 198.\n- The centered OLS is a proposed solution in the paper. I am wondering whether this estimator is the same as one that includes the intercept term. In other words, since it is conventional to use the intercept term in regression models, I am curious whether the standard practice already solves the research question raised in the paper (without fully realizing the importance of including the constant term in the regression model). \n- The centered OLS algorithm on page 6 is not fully implementable in an online fashion. This is because computation of the sample means requires access to the full dataset. It might be useful to add some remarks regarding how to carry out online estimation for the centered OLS.\n- Lots of notations are used before section 2.3. It might be better to move the notations section to improve readability of the paper.\n- The TALE estimator is highly related to the concurrent work [2] entitled \"Adaptive Linear Estimating Equations\". It would be useful to clarify the differences between this work and the current paper.\n\n ", "limitations": "The numerical results are promising but there is no theoretical result in the paper that implies that the TALE estimator should perform strictly better than W-decorrelation. It might be helpful to fully discuss what numerical results are predicted by asymptotic theory and what are not.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper considers a highly important problem in the literature: adaptive data collection (e.g., bandits) is increasingly important in a number of fields. \n- The paper clarifies the important open question in the literature, that is, \"Can we obtain a good estimator for a low-dimensional parameter component in linear models when the degree of adaptivity is given?\".\n- The proposed TALE estimator has desirable theoretical properties and shows promising numerical results.", "weaknesses": "- The non-adaptive component $x_i^{\\mathrm{nad}}$ is assumed to be independent of the adaptive component $x_i^{\\mathrm{ad}}$ (see lines 84-85). This seems quite strong in the sense that if this is the case, we could just drop the non-adaptive component $x_i^{\\mathrm{nad}}$ in the regression model and then we automatically obtain the $\\sqrt{k/n}$ rate, provided that the variance of the new regression error, which now includes the omitted part $\\theta^\\top x_i^{\\mathrm{nad}}$, is bounded by a constant that is independent of $d$. Using the scenario in Example 2.1 with $k=1$ (that is, the treatment assignment mechanism depends only on the effectiveness of the previous treatments), it might be preferable to consider the difference-in-means estimator (that is, to include only the intercept term and a treatment indicator) instead of estimating the treatment effect via regression adjustment. It would be useful to carefully discuss the issue of independence between the adaptive and nonadaptive components. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and provide helpful feedback! We truly appreciate your comments and suggestions, and believe they can make our work better.\n\nIn the following we hope to address each of the points made in the review, in the order as they came out.\n\n**Summary and strengths:** Thank you for the detailed summary and positive feedback!\n\n**Weakness:**\n\n1. Thanks for the question on the data assumption. We agree that the assumption might seem a bit strong, as the treatment is only allowed to be dependent on historical data and  $k-1$-th coordinates of the current covariate vector.  Regarding the alternative approach you proposed, we believe it is a good approach as long as the non-adaptive component $\\theta^\\top x^{nad}_i$ is small (independent of d) and has a near-zero mean. However, when the dimension of the non-adaptive component is relatively large, $\\theta^\\top x^{nad}_i$ may contribute significantly to the outcome $y_i$. Concretely, our assumption (A2) suggests that $\\theta^\\top x^{nad}_i$ is roughly of order $\\nu | |\\theta^*| |_2$, and therefore can not simply be bounded by a constant when $ | |\\theta^*| |_2$ is large, e.g., $O(\\sqrt{d})$ (note that we make no assumption on $ | |\\theta^*| |_2$ in the paper).  Hope this help explain why we prefer OLS over the DID estimator. \n\nThe requirement of the independence of $x_i^{ad}$ and $x_i^{nad}$ comes from a somewhat intrinsic technical difficulty. Assume $x_i^{nad}$ is zero mean for simplicity of discussion (otherwise we just consider $x_i^{nad}-E[x_i^{nad}]$).  Namely, in the analysis we are required to provide an $O(\\sqrt{n})$ bound for $X_{ad}^\\top X_{nad}=\\sum_{i=1}^n x_i^{ad}x_i^{nad\\top}$. To do so, we somehow inevitably need a martingale assumption on $x_i^{ad}x_i^{nad\\top}$, and a sufficient condition for it to be a (matrix-valued) martingale is that $x_i^{nad}$ is independent of $x_i^{ad}$. (Note that we only need $x_i^{nad}$ to be zero-mean conditioned on $x_i^{ad}$, and the independence assumption used in Theorem 3.1 can be relaxed.) \n\n\n\nTechnically speaking, the data assumption made in our work can be viewed as a complement to the quite strong assumption that the adaptive treatment assignment mechanism (i.e., the propensity score  $E[x_i^{ad}|x_{i}^{nad},\\mathcal{F}_{i-1}]$)  is known [16, 30, 39, 41], since in the alternative case one can subtract the conditional expectation from $x_i^{ad}$, and therefore $(x_i^{ad}-E[x_i^{ad}])x_i^{nad\\top}$ forms a martingale and enjoys an $O(\\sqrt{n})$ bound. \n\n**Questions:**\n\n1. Thanks for your advice. The equal conditional variance assumption is used in Thm 3.4 since it might be difficult to estimate the variance if it is time-dependent. The estimation results in Thm 3.1, 3.2 only require a uniform upper bound on the conditional variance. We have added a comment to line 198.\n\n2. Yes from basic properties of linear models we know the centered OLS estimator is the same as the  (corresponding coordinates) of the OLS solution of a linear model with an additional intercept term. We choose to present it as the centered OLS estimator (which is also the standard practice) since it is more consistent with Thm 3.1 in which we assume the non-adaptive component is zero-mean and centering looks like a natural thing to do when the non-adaptive component has nonzero mean. Our main goal in Thm 3.1 and 3.2 was to show that one can have an improved single coordinate scaled-MSE than the pessimistic minimax lower bound under some reasonable data-collection assumptions, and we do not view the centered OLS as a novel estimator proposed.\n\n\n3. As you already correctly pointed out that centered OLS is the same as OLS with an intercept. Consequently, one can use OLS with intercept formulation to obtain the centered OLS in an online fashion. \n\n4. Thanks! We will fix this.\n\n5. The focus of the paper \"Adaptive linear estimating equations\" is to establish a framework for inference for the whole parameter $\\theta^\\star \\in R^d$ under $(d, d)$ adaptivity, leading to an estimate known as the ALEE estimate. However, it's worth noting that the ALEE estimate is not suitable for the high-dimensional regime, where the dimension $d$ is allowed to grow alongside the number of samples $n$. Additionally, the $1$-dimensional confidence intervals from the $d$ dimensional confidence regions produced by ALEE are too wide, especially in the case when $d$ is large. \n\nIn our current work, our contribution is two-fold. First, we show that the estimation error for a single coordinate depends on the degree of dependence $k$ of that coordinate, and we can estimate that coordinate with a rate $\\sqrt{k/n}$ -- much smaller than the minimax rate $\\sqrt{d/n}$. Second,  we address the limitations of ALEE in high-dimensional models by introducing the Two-stage ALEE estimate (TALE). This novel approach is designed to be applicable and effective in the high-dimensional regime when there are additional structures present in the data, e.g. $(k, d)$ - adaptivity. Please also see the comments in the next paragraph. \n\n\n**Limitations:** Both TALE and W-decorrelation are designed to provide asymptotically normal inference, but they are focused on different regimes. The $W$-decorrelation estimator is designed for the fully adaptive regime ($(d,d)$ - adaptive regime), and may require the number of samples to be much larger than the dimension $d$ in worst cases. Indeed, in W-decorrelation type debiasing methods, the bias term decays at the rate $d / log (n)$ in the worst case, and these methods are only designed for the case when $d$ is fixed and the number of samples $n \\gg e^d $.  In our current work, we are focused on the high dimensional case when the dimension of the problem $d$ can grow with the number of samples. Our main inference result (Thm 3.4) is that under $(1, d)$ adaptivity, we can perform valid one-dimensional inference when $d \\approx \\sqrt{n}$ up to some logarithmic terms. \n"}, {"review_id": "PIoyzyH4Om", "reviewer": "Reviewer_tdeW", "summary": "In \"Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inference\" the authors consider the problem of estimating a low-dimensional signal in a high-dimensional linear model where data collection is allowed to be adaptive. The notion of adaptivity employed in this paper restricts itself to k components, meaning that the k first (wlog) covariates are allowed to be adaptive while the remaining are assumed i.i.d. This is in contrast to prior work where all components are allowed to be adaptive which yields very detrimental minimax lower bounds even in the case where only one component is to be estimated. Based on this new notion of adaptivity, the authors propose a scheme to estimate the low-dimensional signal yielding beneficial scaling guarantees, both in mean square error and asymptotic normality.    ", "questions": "1. Regarding Example 2.1.: Based on how the filtration is defined and the dimensionality of the quantities one can infer that A_i is considered to be the first coordinate of the covariates in the linear model. I don't see the loss of generality in instead defining x_i to include the treatment assignment as x_1i. This makes the mapping to the linear model more obvious.\n2. Regarding significance of the model. The underlying assumption is that variable selection is not necessary in this case, i.e. the low-dimensional coordinates to be estimated are known prior, and they are the only ones that are affected by adaptive covariates while the remaining are i.i.d.. Can the authors expand on the treatment assignment example to provide with a situation in which this would be the case? ", "limitations": "-", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Originality: the authors study a novel scenario and provide a novel scheme with reasonable guarantees. The work has sufficient novelty.\n2. Quality: the paper is technically sound and the results are appropriately stated.\n3. Clarity: The main results of the paper and some intuition on how they are established are clear. The example provided could be a bit clearer. I expand on this in the Questions section.\n4. Significance: This may be to my own ignorance but the significance of the considered model is not entirely clear to me. I again will expand on this in the Questions section.", "weaknesses": "I merge this with the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and provide helpful feedback! We truly appreciate your comments and suggestions, and believe they can make our work better.\n\nIn the following we hope to address each of the points made in the review, in the order as they came out.\n\n**Summary and strengths:** Thank you for writing a detailed summary and for the kind words. We really appreciate them.\n\n**Questions:**\n\n1. Thanks for the suggestion! Yes we implicitly think of the treatment $A_i$ as the first coordinate of the covariate vector. The reason we separated them is to follow the conventions in causal inference literature, in which the treatment and the covariate vector are denoted separately. Sorry for the confusion we made and thanks again!\n\n2. First, we thank the reviewer for this engaging question. In the treatment assignment problem (Example 2.1), the goal is to estimate the treatment effect --- coordinate associated with $A_i$, and from the right-most bound in Corollary 3.3 we see that the estimation rate only depends on the degree of adaptivity $k$ (or an upper bound of it), but the location of the adaptive coordinate is unknown. Indeed, the centered OLS or the OLS do not use the location of adaptive coordinates in any way. In other words, in order to have an upper bound on the estimation error of the treatment assignment coordinate, we only need to have an upper bound on the number of regressors $k$ the treatment assignment $A_i$ depends on, and do not need to know the specific treatment allocation rule --- which gives you information regarding the location of these regressors. Finally, the rate in Corollary 3.3 is unimprovable due to our minimax lower bound from Proposition 2.2. We will clarify this important distinction in the modified version of the paper, and we thank the reviewer for pointing this out.\n\n\n"}, {"review_id": "EMcsaA6MyW", "reviewer": "Reviewer_KiDv", "summary": "The paper studies the statistical limits of some adaptive linear models.\n\nThe paper defines the notion of $(k,d)$-adaptivity (Definition 2.1), and then it proves, under some conditions and for a $(k,d)$-adaptive model and failure probability $\\delta$, that\n- (Theorem 3.1) the estimation error of the adaptive components is bounded by $k\\log(n/\\delta)$ if the non-adaptive component has zero mean,\n- (Theorem 3.2) and similar results hold if the mean of the non-adaptive component is not zero;\n- (Theorem 3.4) moreover, there exists an estimator (TALE) that enjoys asymptotic normality.\n\nThe experiments present an interesting phenomenon: The TALE estimator coincides well with the normal distribution.\n\n", "questions": "- From the paper it is a bit hard for me to understand what \"adaptivity\" precisely means. The definition of $(k,d)$-adaptivity only specifies that the adaptive components $x_i^{ad}$ depend on the sigma field $F_{i-1}$. Would it be much simpler and clearer to say \"dependency\" instead of \"adaptivity\"?\n", "limitations": "The authors discussed future works and limitations at the end of the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is written clearly and the presentation is smooth and relatively easy to follow.\n\n\n\n\n", "weaknesses": "I have a major concern about whether the paper is technically solid and I wish to read the response from the authors:\n- Regarding Theorems 3.1 and 3.2, could the authors justify how the proof techniques differ from prior works? It appears to me that the two results are basic extensions of prior proofs (so, correct me if I am wrong).\n- Theorem 3.4 holds only for a single adaptive coordinate. Could the authors elaborate on the difficulty of extending the results for general $(k,d)$-adaptivity?\n\n\nMinor:\n- the same symbol $\\sigma$ is used to represent sigma field, variance of a random variable, and singular values. In my humble opinion, this might be confusing.\n\n\n**NOTE**: I am not an expert on statistics in general and on this particular line of research, so it is not for me to say whether the paper is significant or novel.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and provide helpful feedback! We truly appreciate your comments and suggestions, and believe they can make our work better.\n\nIn the following, we hope to address each of the points made in the review, in the order as they came out.\n\n**Strengths:** Thanks for your kind words!\n\n**Weakness:**\n\n1. We believe that one of the main contributions of our work is identifying an assumption (i.e., (k,d)-adaptivity) under which a $d$-independent estimation is attainable. As a direct consequence of the assumption,  we are hence able to exploit the underlying martingale structure in terms like $X^\\top_{ad}X_{nad}$ to obtain tighter bounds on them (please view our rebuttal to Reviewer Pp5b for more details), which contribute to the proof of Theorem 3.1 and 3.2. The main techniques used in the proofs are martingale concentration inequalities, matrix concentration inequalities, and matrix calculations (see e.g., Lemma A.1, A.2 for more details).  From our viewpoint, the proofs in Theorem 3.1, 3.2 are built based on basic concentration inequalities, and are intrinsically different from those in previous works, e.g., Theorem 8 in  Lattimore and Szepesvari, since our data assumption allows us to get tighter bounds on certain terms (e.g., $X^\\top_{ad}X_{nad}$) in a different way which cannot be done without such an assumption. \n\n2. We express our gratitude to the reviewer for their insightful question. Our immediate objective is to extend the TALE estimator to encompass multiple coordinates and incorporate $(k,d)$ adaptivity. To ensure asymptotic normality guarantees for all $k$-coordinates associated with $x_{ad}$, we need to construct $k$-dimensional weights $w$ which ensure asymptotic normality of the term $v_n$ and facilitate good control of the bias term $b_n$ (see equation (13) in the paper).  Currently, we are able to formulate weights $w$ that ensure the asymptotic normality of the term $v_n$. However, the conditions necessary for effectively controlling the bias term $b_n$, with these weights, are somewhat stringent based on our present calculations. In the revised version of our paper, we will provide an elaborate discussion on the methodology behind constructing these weights in $(k,d)$-settings, shedding light on the challenges posed in controlling the bias term. We extend our gratitude once again to the reviewer for their meticulous observations, which greatly contribute to the refinement of our work.\n\n\n3. Thanks for the suggestion! We agree that the overuse of $\\sigma$ might cause confusion in understanding the paper and we will fix it.\n\n**Questions:**  We use the term \"adaptivity\" to imply that the data are collected in an adaptive manner, in contrast to i.i.d. manner. This term is also used in other works [14, 21, 30], while another name \"stochastic linear model\" has also been used in history [23, 24]. We sincerely apologize if our use of the term \"adaptivity\" caused any unnecessary confusion."}]

Author rebuttal:
## Additional simulation:

As suggested by some of the reviewers, in this global rebuttal we display the effect of degree of adaptivity $k$ on the single coordinate estimation. These simulations provide empirical validation to the theory developed in the paper (Theorem 3.1, 3.2). To better visualize the result, we want to design an adaptive data collection, which can capture the estimation lower bound. Therefore, we adopt a similar data collection procedure as provided in Khamaru et al. [2] and also see Lattimore [1] for related information. 

**Simulation set-up:** 

1. Sample size $n = 1000$, $d = 300$.
2. The degree of adaptivity $k$ varies from 2 to 200 with step size equal to $3$.
3. Replication number $20$ for each level of adaptivity $(k,d)$.
4. $\theta^\mathrm{ad}_1 = 1$ and other coefficients are generated independently from $\mathcal{N}(0,1)$.
5. $\boldsymbol{x}_i^\mathrm{nad}$ is generated independently from uniform distribution on the sphere $\mathbf{S}^{d - k - 1}$ plus $\mathbf{E} \boldsymbol{x}_i^\mathrm{nad}$, 
where  $\mathbf{E} \boldsymbol{x}_i^\mathrm{nad}$ is generated from $\mathcal{N}(0, \mathbf{I})$.

**Data collection method:**

Here we modified the data collection algorithm from Section $5.2.2$ in the paper [2]. The only difference between our data collection algorithm and the one in [2] is that we replace
$m_{u, v} \coloneqq \sum_{w=1}^v b_w\left(y_{u, w}-a_{u, w}\right)$ by 
$$m_{u, v} \coloneqq \sum_{w=1}^v b_w \left(y_{u, w}-a_{u, w} - \boldsymbol{\theta}^{\mathrm{nad} \top} \boldsymbol{x}^\mathrm{nad}_{u+(w - 1)(d - 1)} \right).$$
In the modified data collection method above, we are able to address the non-adaptive components in the ridge estimates. See Section $5.2.2$ in paper [2] for more details.










**References:**
1. Lattimore, Tor. "A Lower Bound for Linear and Kernel Regression with Adaptive Covariates." In The Thirty Sixth Annual Conference on Learning Theory, pp. 2095-2113. PMLR, 2023.

2. Khamaru, Koulik, Yash Deshpande, Tor Lattimore, Lester Mackey, and Martin J. Wainwright. "Near-optimal inference in adaptive linear regression." arXiv preprint arXiv:2107.02266 (2023).

Meta-review: This paper studies the effect of data adaptivity in the estimation of linear models. In particular, the authors investigate how the degree of adaptivity in data collection impacts the performance of estimating a low-dimensional parameter component in high-dimensional linear models. Toward this goal, the authors introduce the notion of (k,d)-adaptivity, which quantifies the amount of adaptivity in different coordinates of the linear model. In particular, a dataset is called (k,d)-adaptive if the first k coordinates of the covariates are designed adaptively, while the remaining d-k coordinates are iid. Under (k,d)-adaptivity, the authors show that the simple OLS estimator achieves a scaled-MSE error rate that scales with k. This is a generalization of the fully-adaptive scenario, in which the scaled-MSE scales with the dimension d, as well as a generalization of the fully non-adaptive case where the full dataset is assumed to be iid. For the special case of (1,d)-adaptive dataset, the authors provide a new algorithm, called TALE, which, unlike the simple OLS, enjoys an asymptotic normality property.

Five reviewers have reviewed the paper, and their overall assessment of the paper was positive. I agree with this assessment and believe the paper is a solid contribution with interesting results. Several reviewers have mentioned that the authors should highlight the key differences between their proposed proof technique and that of Khamaru et. al. [21]. I agree with this comment and encourage the authors to address this in their revised manuscript, as well as add the new complementary experiments to the main body of the paper.
Decision: Accept (poster)