Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inference

Summary

The paper studies the statistical limits of some adaptive linear models. The 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 - (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, - (Theorem 3.2) and similar results hold if the mean of the non-adaptive component is not zero; - (Theorem 3.4) moreover, there exists an estimator (TALE) that enjoys asymptotic normality. The experiments present an interesting phenomenon: The TALE estimator coincides well with the normal distribution.

Strengths

The paper is written clearly and the presentation is smooth and relatively easy to follow.

Weaknesses

I have a major concern about whether the paper is technically solid and I wish to read the response from the authors: - 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). - 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? Minor: - 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. **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.

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"?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors discussed future works and limitations at the end of the paper.

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.

Strengths

1. Originality: the authors study a novel scenario and provide a novel scheme with reasonable guarantees. The work has sufficient novelty. 2. Quality: the paper is technically sound and the results are appropriately stated. 3. 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. 4. 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.

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. 2. 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

-

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.

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. - 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?". - 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.

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. - 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). - 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. - Lots of notations are used before section 2.3. It might be better to move the notations section to improve readability of the paper. - 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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

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.

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.

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. 2. 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. 3. 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. 4. Typo in line 106.

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.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See 2. in Weakness section.

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.

Strengths

NA

Weaknesses

NA

Questions

NA

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

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. The manuscript is easy to read through and the technical content of the paper appears to be correct albeit some typos: Line 69: Adaptive Line 478 in the appendix: $X_{\mathrm{ad}}$

Strengths

Theoretical results: - 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. Experiments: - Compared to other methods like OLS, estimation errors for TALE are in good accordance with a norm distribution.

Weaknesses

Theoretical results: - 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. Experiments: - 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.

Questions

Numerical experiments: - 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? - 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.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

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.

Reply to the rebuttal

Dear authors, Thanks for your rebuttal. It is well received. I also read comments from other reviewers. 1. Since the bound (Eq. 7) from Theorem 3.1 is very similar to prior works (Eq. 8), it would be a good idea to discuss and highlight the technical differences in the revision, as emphasized in the rebuttal. 2. Thanks for the detailed elaboration on challenges for extending to the more general cases. Discussing this point as a limitation of the present work would also be of interest to readers. I think the rebuttal adequately addressed my comments. I am happy to keep my positive evaluation of the paper. Regards, KiDv

Thanks

I am grateful to the authors for their careful rebuttal. Most of my comments are well addressed. In view of that, I changed my rating upward by one point (from 6 to 7).