Experimental Designs for Heteroskedastic Variance

Most linear experimental design problems assume homogeneous variance although heteroskedastic noise is present in many realistic settings. Let a learner have access to a finite set of measurement vectors $\mathcal{X}\subset \mathbb{R}^d$ that can be probed to receive noisy linear responses of the form $y=x^{\top}\theta^{\ast}+\eta$. Here $\theta^{\ast}\in \mathbb{R}^d$ is an unknown parameter vector, and $\eta$ is independent mean-zero $\sigma_x^2$-sub-Gaussian noise defined by a flexible heteroskedastic variance model, $\sigma_x^2 = x^{\top}\Sigma^{\ast}x$. Assuming that $\Sigma^{\ast}\in \mathbb{R}^{d\times d}$ is an unknown matrix, we propose, analyze and empirically evaluate a novel design for uniformly bounding estimation error of the variance parameters, $\sigma_x^2$. We demonstrate the benefits of this method with two adaptive experimental design problems under heteroskedastic noise, fixed confidence transductive best-arm identification and level-set identification and prove the first instance-dependent lower bounds in these settings. Lastly, we construct near-optimal algorithms and demonstrate the large improvements in sample complexity gained from accounting for heteroskedastic variance in these designs empirically.

Paper

Similar papers

Peer review

Reviewer Jphn7/10 · confidence 1/52023-06-23

Summary

This paper studies linear experimental design in the presence of heteroskedastic noise. The model can observe noise linear measurements generated by unknown model parameters, with sub-Gaussian covariance depends on the measurement vector. The goal is to estimate the unknown covariance matrix and corresponding covariance wrt measurement $x$. The algorithm works as follows: it uses the first half of the samples to construct a least-squares estimator for the model parameter, then use the second half to estimate the noises and consequently, the covariance. This algorithm leads to a sample complexity depends quadratically on $d$. As applications, the proposed approach can be used for best arm identification and level set identification. Finally, experiments are conducted to empirically validate the algorithm.

Strengths

This paper studied an interesting problem, in practical setting, heteroskedastic noises usually present, so it is important to study the sample complexity and efficient algorithm for this setting. The presentation of the paper is good, it is a good mixture of motivation, intuition and technicality. I enjoyed reading the paper. The results obtained in this paper are strong.

Weaknesses

It will be better to also include the runtime complexity of the proposed algorithm. Linear bandits now admit highly efficient algorithms with curated data structures [Yang et al., ICML'22] and so does efficient experimental design [Allen-Zhu et al., ICML'17]. It will be interesting to study the runtime complexity of the proposed algorithm. [Yang el al., ICML'22]: S. Yang, T. Ren, S. Shakkottai, E. Price, I. Dhillion, S. Sanghavi. Linear Bandit Algorithms with Sublinear Time Complexity. [Allen-Zhu et al., ICML'17]: Z. Allen-Zhu, Y. Li, A. Singh, Y. Wang. Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach.

Questions

What is the runtime complexity of the proposed algorithm?

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes.

Reviewer jG9W6/10 · confidence 2/52023-07-02

Summary

This paper investigates the problem of linear regression under heteroskedastic noise with adaptive data collection. The proposed algorithm begins with estimating the covariance structure via Alg 1 and then using this in Alg 2 to construct an optimal design for estimating $\theta$. The algorithm is instance-optimal up to an additive term depending on the conditioning $\kappa$. They conclude with experiments demonstrating their algorithm's performance.

Strengths

* This work analyzes a useful problem and proposes a nice adaptation of RAGE to their setup.

Weaknesses

* I'm not sure how common or realistic this assumption is, but the heteroskedasticity model (i.e., that $\sigma_x^2 = x^T\Sigma^\star x$) seems very restrictive to me. It would be nice to have some further discussion about this and possibly about extending the algorithm to more general noise settings. * As they remark in the paper, the lower bound is weakened by the fact that the noise variances are considered to be known, and so the lower bound essentially becomes the same as Fiez et al. The lower bound would be much more compelling to me if it could incorporate the difficulty associated with estimating $\Sigma^\star$ (which could also address the current $\kappa$-dependent gap between the upper and lower bounds).

Questions

* Regarding the optimality of Alg. 2, what is the appropriate regime to be thinking of for the quantities in Theorems 1 and 2? For example, how should the $\log(\Delta^{-1})\log(|Z|/\delta)$ multiplicative factor differing between the upper and lower bounds compare against $\psi^\star$. Also, how large will $d$ be, given that the additive suboptimality terms has a $d^2$ factor in it? Minor: * In Alg. 1, should it say $\lambda^\star_x$ in line 4 and $\lambda^\dag_x$ in line 8? Otherwise, I don't see how the quantities computed in lines 3 and 7 are used.

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

3 good

Contribution

3 good

Limitations

The authors adequately addressed the limitations.

Reviewer VoEg7/10 · confidence 4/52023-07-06

Summary

The paper considers the problem of Experimental Designs for Heteroskedastic Variance. Here, a learner has access to finite set of measurement vectors $\mathcal{X}$ and may query observations of the following form for chosen $x \in \mathcal{X}$: $y = x^\top \theta^* + \eta$ where $\eta$ is mean-zero and sub-Gaussian with variance $\sigma^2_x = x^\top \Sigma x$. The paper first designs a procedure to estimate $\Sigma$ and then utilizes this estimate for two related problems featuring linear objectives: Best-arm Identification and Level-set Identification. The paper then shows that when heteroskedastic variance is present, this procedure leads to improved results for these tasks. The paper then conducts empirical experiments to validate their claims. The main technical contribution of the paper is the procedure to estimate $\Sigma$. If $\theta$ were known, $(y - \theta^\top x)^2$ provides an unbiased estimate of $\sigma_x^2$. However, since $\theta^*$ is not known, the paper first estimates it via a weighted least-squares estimator where the weights are chosen to ensure that each $x \in \mathcal{X}$ is well-represented in the spectrum of the weighted second-moment matrix. This ensures that $\theta$ is accurate (at least along the $x$ in $\mathcal{X}$). Then, a similar sampling procedure is used with the vectors $\phi_x = \mathrm{vec} (xx^\top)$ and noting that $(y - x^\top \theta^*)^2$ is an unbiased estimate of $\sigma_x^2 = \mathrm{vec} (xx^\top)^\top \mathrm{vec} (\Sigma)$ which is a linear equation in $\Sigma$. A similar weighting procedure is used to obtain an estimate of $\Sigma$ such that $\sigma_x^2$ is well-approximated for any $x \in \mathcal{X}$. These estimates are then used to design improved strategies for the aforementioned estimation tasks with linear objects. Overall this is a nice paper with strong technical results. The setting seems novel and interesting and the technical analysis is non-trivial. The main question I have for the authors is that the sampling procedure incurs large sample complexities in some extreme cases. Say, $\mathcal{X}$ corresponded to the standard basis vectors. In this setting, the error bound on estimating $\sigma_{e_1}$ depends on $\max_j \sigma_{e_j}$ while intuitively this dependence seems extreme. Furthermore, the fact that $d^2$ samples are needed to estimate $\Sigma$ only along the directions in $\mathcal{X}$ also seems too large if $\mathcal{X}$ is not too large. It would be great if the authors can comment on these dependencies.

Strengths

See main review

Weaknesses

See main review

Questions

See main review

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

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Reviewer mrcD3/10 · confidence 4/52023-07-07

Summary

This paper considers the online linear experimental design problem that is affected by heteroskedastic noise. The authors propose a two-phase sample splitting method aimed at estimating the unknown parameters of noise variance, utilizing the principle of G-optimal experimental designs. Furthermore, the study extends the application of the proposed methodology to handle fixed confidence transductive best-arm and level set identification problems under conditions of heteroskedastic noise. The paper also deals with the instance-dependent lower bounds.

Strengths

This paper does solid work and is in relatively good shape.

Weaknesses

1. The problem is not well motivated. It is unclear what are the practical applications of this problem. 2. The numerical experiments only contain some toy examples. It is unclear how it performed in a large-scale set. 3. Comparision between the previous works are not present. 4. The problem setting looks weird. The sensing noise variance is $x^T \Sigma x$, why it depends on the sensing vector $x$? What are the motivations for this problem setting?

Questions

1. How is the current approach compared to the previous works? Both in a theoretical sense and numerical experiments. 2. What motivates the problem setting, that is, the sensing noise variance is $x^T \Sigma x$.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

See above.

Reviewer Jphn2023-08-10

Thank you for your response! You mentioned the runtime complexity mainly depends on Frank-Wolfe, I wonder whether recent developments on data-structure-based Frank-Wolfe methods would lead to a more efficient implementation of your algorithm: [Xu et al., NeurIPS'21] and [Song et al., Arxiv'22]. These papers show that by cleverly using data-structures, the complexity of Frank-Wolfe can be improved beyond an exhaustive search over the entire convex hull. [Xu et al., NeurIPS'21] Zhaozhuo Xu, Zhao Song and Anshumali Shrivastava. Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures. [Song et al., Arxiv'22] Zhao Song, Zhaozhuo Xu, Yuanyuan Yang and Lichen Zhang. Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures.

Authorsrebuttal2023-08-14

This is an interesting question. The traditional Frank-Wolfe algorithm steps in the direction of the point on the convex hull of the constraint boundary that has the smallest inner product with the gradient. Both the papers you reference focus on the use of efficient data structures to find this direction. In our case of the simplex, this step reduces to finding the smallest entry of the gradient. Thus, it is not clear that additional efficiency gains are possible using the ideas presented in the referenced papers.

Reviewer Jphn2023-08-14

Thank you for your comments, I would suggest to incorporate a more detailed description of your algorithm in the paper. I'll keep my score as is.

Reviewer VoEg2023-08-18

Reviewer Response

Thank you for the response. I will retain my current evaluation.

Reviewer mrcD2023-08-20

Thank you

Dear author, Thanks for your response. I would like to remain my previous rating. The reason is as follows. 1. The numerical experiments are very limited. Only FIgure 3 is presented to test the theory. Also, these examples are quite small, basically some toy examples. There are no large-scale experiments to evaluate and test your theory. 2. The theoretical contribution is very limited. As a researcher specializing in theory, I am quite confident to say that the proof techniques in this paper are quite standard. I am afraid that there is not enough contribution in this direction as well. In summary, this paper not only lacks the theoretical contributions but also enough numerical experiments to prove the effectiveness of its algorithm in reality.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC