An official website of the United States government
In this work, we propose a method to construct a uniform error bound for the SK predictor. In investigating the asymptotic properties of the proposed uniform error bound, we examine the convergence rate of SKโs predictive variance under the supremum norm in both fixed and random design settings. Our analyses reveal that the large-sample properties of SK prediction depend on the design-point sampling scheme and the budget allocation scheme adopted. Appropriately controlling the order of noise variances through budget allocation is crucial for achieving a desirable convergence rate of SKโs approximation error, as quantified by the uniform error bound, and for maintaining SKโs numerical stability. Moreover, we investigate the impact of noise variance estimation on the uniform error boundโs performance theoretically and numerically. We demonstrate the superiority of the proposed uniform bound to the Bonferroni correction-based simultaneous confidence interval under various experimental settings through numerical evaluations.
more »
« less
Experimental Designs for Heteroskedastic Variance
Most linear experimental design problems assume homogeneous variance, while the presence of heteroskedastic noise is present in many realistic settings. Let a learner have access to a finite set of measurement vectors that can be probed to receive noisy linear responses. We propose, analyze and empirically evaluate a novel design for uniformly bounding estimation error of the variance parameters. We demonstrate this method on 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.
more »
« less
- Award ID(s):
- 2136034
- PAR ID:
- 10482131
- Publisher / Repository:
- NeurIPS
- Date Published:
- Journal Name:
- Thirty-seventh Conference on Neural Information Processing Systems
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Low-rank matrix recovery problems involving high-dimensional and heterogeneous data appear in applications throughout statistics and machine learning. The contribution of this paper is to establish the fundamental limits of recovery for a broad class of these problems. In particular, we study the problem of estimating a rank-one matrix from Gaussian observations where different blocks of the matrix are observed under different noise levels. In the setting where the number of blocks is fixed while the number of variables tends to infinity, we prove asymptotically exact formulas for the minimum mean-squared error in estimating both the matrix and underlying factors. These results are based on a novel reduction from the low-rank matrix tensor product model (with homogeneous noise) to a rank-one model with heteroskedastic noise. As an application of our main result, we show that show recently proposed methods based on applying principal component analysis (PCA) to weighted combinations of the data are optimal in some settings but sub-optimal in others. We also provide numerical results comparing our asymptotic formulas with the performance of methods based weighted PCA, gradient descent, and approximate message passing.more » « less
-
Parameter estimation and optimal experimental design problems have been widely studied across scienceand engineering. The two are inextricably linked, with optimally designed experiments leading to better-estimated parameters. This link becomes even more crucial when available experiments produce minimal data due to practical constraints of limited experimental budgets. This work presents a novel framework that allows for the identification of optimal experimental arrangement, from a finite set of possibilities, for precise parameter estimation. The proposed framework relies on two pillars. First, we use multi-fidelity modeling to create reliable surrogates that relate unknown parameters to a measurable quantity of interest for a multitude of available choices defined through a set of candidate control vectors. Secondly, we quantify the estimation potential of an arrangement from the set of control vectors through the examination of statistical sensitivity measures calculated from the constructed surrogates. The measures of sensitivity are defined using analysis of variance as well as directional statistics. Two numerical examples are provided, where we demonstrate how the correlation between the estimation potential and the frequency of precise parameter estimation can inform the choice of optimal arrangement.more » « less
-
In this paper, we study the problem of optimal data collection for policy evaluation in linear bandits. In policy evaluation, we are given a \textit{target} policy and asked to estimate the expected reward it will obtain when executed in a multi-armed bandit environment. Our work is the first work that focuses on such an optimal data collection strategy for policy evaluation involving heteroscedastic reward noise in the linear bandit setting. We first formulate an optimal design for weighted least squares estimates in the heteroscedastic linear bandit setting with the knowledge of noise variances. This design minimizes the mean squared error (MSE) of the estimated value of the target policy and is termed the oracle design. Since the noise variance is typically unknown, we then introduce a novel algorithm, SPEED (\textbf{S}tructured \textbf{P}olicy \textbf{E}valuation \textbf{E}xperimental \textbf{D}esign), that tracks the oracle design and derive its regret with respect to the oracle design. We show that regret scales as ๐ห(๐3๐โ3/2) and prove a matching lower bound of ฮฉ(๐2๐โ3/2) . Finally, we evaluate SPEED on a set of policy evaluation tasks and demonstrate that it achieves MSE comparable to an optimal oracle and much lower than simply running the target policy.more » « less
-
Dealing with high variance is a significant challenge in model-free reinforcement learning (RL). Existing methods are unreliable, exhibiting high variance in performance from run to run using different initializations/seeds. Focusing on problems arising in continuous control, we propose a functional regularization approach to augmenting model-free RL. In particular, we regularize the behavior of the deep policy to be similar to a control prior, i.e., we regularize in function space. We show that functional regularization yields a bias-variance trade-off, and propose an adaptive tuning strategy to optimize this trade-off. When the prior policy has control-theoretic stability guarantees, we further show that this regularization approximately preserves those stability guarantees throughout learning. We validate our approach empirically on a wide range of settings, and demonstrate significantly reduced variance, guaranteed dynamic stability, and more efficient learning than deep RL alone.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
