An official website of the United States government
Abstract In this paper, we propose a new framework to construct confidence sets for a $$d$$-dimensional unknown sparse parameter $${\boldsymbol \theta }$$ under the normal mean model $${\boldsymbol X}\sim N({\boldsymbol \theta },\sigma ^{2}\bf{I})$$. A key feature of the proposed confidence set is its capability to account for the sparsity of $${\boldsymbol \theta }$$, thus named as sparse confidence set. This is in sharp contrast with the classical methods, such as the Bonferroni confidence intervals and other resampling-based procedures, where the sparsity of $${\boldsymbol \theta }$$ is often ignored. Specifically, we require the desired sparse confidence set to satisfy the following two conditions: (i) uniformly over the parameter space, the coverage probability for $${\boldsymbol \theta }$$ is above a pre-specified level; (ii) there exists a random subset $$S$$ of $$\{1,...,d\}$$ such that $$S$$ guarantees the pre-specified true negative rate for detecting non-zero $$\theta _{j}$$’s. To exploit the sparsity of $${\boldsymbol \theta }$$, we allow the confidence interval for $$\theta _{j}$$ to degenerate to a single point 0 for any $$j\notin S$$. Under this new framework, we first consider whether there exist sparse confidence sets that satisfy the above two conditions. To address this question, we establish a non-asymptotic minimax lower bound for the non-coverage probability over a suitable class of sparse confidence sets. The lower bound deciphers the role of sparsity and minimum signal-to-noise ratio (SNR) in the construction of sparse confidence sets. Furthermore, under suitable conditions on the SNR, a two-stage procedure is proposed to construct a sparse confidence set. To evaluate the optimality, the proposed sparse confidence set is shown to attain a minimax lower bound of some properly defined risk function up to a constant factor. Finally, we develop an adaptive procedure to the unknown sparsity. Numerical studies are conducted to verify the theoretical results.
more »
« less
Confidence sequences for sampling without replacement
Many practical tasks involve sampling sequentially without replacement (WoR) from a finite population of size $$N$$, in an attempt to estimate some parameter $$\theta^\star$$. Accurately quantifying uncertainty throughout this process is a nontrivial task, but is necessary because it often determines when we stop collecting samples and confidently report a result. We present a suite of tools for designing \textit{confidence sequences} (CS) for $$\theta^\star$$. A CS is a sequence of confidence sets $$(C_n)_{n=1}^N$$, that shrink in size, and all contain $$\theta^\star$$ simultaneously with high probability. We present a generic approach to constructing a frequentist CS using Bayesian tools, based on the fact that the ratio of a prior to the posterior at the ground truth is a martingale. We then present Hoeffding- and empirical-Bernstein-type time-uniform CSs and fixed-time confidence intervals for sampling WoR, which improve on previous bounds in the literature and explicitly quantify the benefit of WoR sampling.
more »
« less
- Award ID(s):
- 1916320
- PAR ID:
- 10251947
- Publisher / Repository:
- Curran Associates
- Date Published:
- Journal Name:
- Advances in neural information processing systems
- Volume:
- 33
- ISSN:
- 1049-5258
- Page Range / eLocation ID:
- 20204-20214
- Format(s):
- Medium: X
- Location:
- Neural Information Processing Systems
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present new algorithms for computing many faces in arrangements of lines and segments. Given a set $$S$$ of $$n$$ lines (resp., segments) and a set $$P$$ of $$m$$ points in the plane, the problem is to compute the faces of the arrangements of $$S$$ that contain at least one point of $$P$$. For the line case, we give a deterministic algorithm of $$O(m^{2/3}n^{2/3}\log^{2/3} (n/\sqrt{m})+(m+n)\log n)$$ time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $$\log^{2.22}n$$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of $$\log^{1/3}n$$ in certain cases (e.g., when $$m=\Theta(n)$$). For the segment case, we present a deterministic algorithm of $$O(n^{2/3}m^{2/3}\log n+\tau(n\alpha^2(n)+n\log m+m)\log n)$$ time, where $$\tau=\min\{\log m,\log (n/\sqrt{m})\}$$ and $$\alpha(n)$$ is the inverse Ackermann function. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $$\log^{2.11}n$$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of $$\log n$$ in certain cases (e.g., when $$m=\Theta(n)$$). We also give a randomized algorithm of $$O(m^{2/3}K^{1/3}\log n+\tau(n\alpha(n)+n\log m+m)\log n\log K)$$ expected time, where $$K$$ is the number of intersections of all segments of $$S$$. In addition, we consider the query version of the problem, that is, preprocess $$S$$ to compute the face of the arrangement of $$S$$ that contains any given query point. We present new results that improve the previous work for both the line and the segment cases. In particulary, for the line case, we build a data structure of $$O(n\log n)$$ space in $$O(n\log n)$$ randomized time, so that the face containing the query point can be obtained in $$O(\sqrt{n\log n})$$ time with high probability (more specifically, the query returns a binary search tree representing the face so that standard binary-search-based queries on the face can be handled in $$O(\log n)$$ time each and the face itself can be output explicitly in time linear in its size).more » « less
-
Ramanan, Kavita (Ed.)The paper concerns the stochastic approximation recursion, \[ \theta_{n+1}= \theta_n + \alpha_{n + 1} f(\theta_n, \Phi_{n+1}) \,,\quad n\ge 0, \] where the {\em estimates} $$\{ \theta_n\} $$ evolve on $$\Re^d$$, and $$\bfPhi \eqdef \{ \Phi_n \}$$ is a stochastic process on a general state space, satisfying a conditional Markov property that allows for parameter-dependent noise. In addition to standard Lipschitz assumptions and conditions on the vanishing step-size sequence, it is assumed that the associated \textit{mean flow} $$ \ddt \odestate_t = \barf(\odestate_t)$$ is globally asymptotically stable, with stationary point denoted $$\theta^*$$. The main results are established under additional conditions on the mean flow and an extension of the Donsker-Varadhan Lyapunov drift condition known as~(DV3): (i) A Lyapunov function is constructed for the joint process $$\{\theta_n,\Phi_n\}$$ that implies convergence of the estimates in $$L_4$$. (ii) A functional central limit theorem (CLT) is established, as well as the usual one-dimensional CLT for the normalized error. Moment bounds combined with the CLT imply convergence of the normalized covariance $$\Expect [ z_n z_n^\transpose ]$$ to the asymptotic covariance $$\SigmaTheta$$ in the CLT, where $$z_n\eqdef (\theta_n-\theta^*)/\sqrt{\alpha_n}$$. (iii) The CLT holds for the normalized averaged parameters $$\zPR_n\eqdef \sqrt{n} (\thetaPR_n -\theta^*)$$, with $$\thetaPR_n \eqdef n^{-1} \sum_{k=1}^n\theta_k$$, subject to standard assumptions on the step-size. Moreover, the covariance of $$\zPR_n$$ converges to $$\SigmaPR$$, the minimal covariance of Polyak and Ruppert. (iv) An example is given where $$f$$ and $$\barf$$ are linear in $$\theta$$, and $$\bfPhi$$ is a geometrically ergodic Markov chain but does not satisfy~(DV3). While the algorithm is convergent, the second moment of $$\theta_n$$ is unbounded and in fact diverges.more » « less
-
Over the years, researchers have found that student engagement facilitates desired academic success outcomes for college undergraduate students. Much research on student engagement has focused on academic tasks and classroom context. High impact engagement practices (HIEP) have been shown to be effective for undergraduate student academic success. However, less is known about the effects of HIEP specifically on engineering and computer science (E/CS) student outcomes. Given the high attrition rates for E/CS students, student involvement in HIEP could be effective in improving student outcomes for E/CS students, including those from various underrepresented groups. More generally, student participation in specific HIEP activities has been shown to shape their everyday experiences in school, both academically and socially. Hence, the primary goal of this study is to examine the factors that predict academic success in E/CS using multiple regression analysis. Specifically, this study seeks to understand the effects of high impact engagement practices (HIEP), coursework enjoyability, confidence at completing a degree on academic success of the underrepresented and nontraditional E/CS students. We used exploratory factor analyses to derive “academic success” variable from five items that sought to measure how students persevere to attain academic goals. A secondary goal of the present study is to address the gap in research literature concerning how participation in HIEP affects student persistence and success in E/CS degree programs. Our research team developed and administered an online survey to investigate and identify factors that affect participation in HIEP among underrepresented and nontraditional E/CS students. Respondents (N = 531) were students enrolled in two land grant universities in the Western U.S. Multiple regression analyses were conducted to examine the proportion of the variation in the dependent variable (academic success) explained by the independent variables (i.e., high impact engagement practice (HIEP), coursework enjoyability, and confidence at completing a degree). We hypothesized that (1) high impact engagement practices will predict academic success; (2) coursework enjoyability will predict academic success; and (3) confidence at completing a degree will predict academic success. Results showed that the multiple regression model statistically predicted academic success , F(3, 270) = 33.064, p = .001, adjusted R2 = .27. This results indicate that there is a linear relationship in the population and the multiple regression model is a good fit for the data. Further, findings show that confidence at completing a degree is significantly predictive of academic success. In addition, coursework enjoyability is a strong predictor of academic success. Specifically, the result shows that an increase in high impact engagement activity is associated with an increase in students’ academic success. In sum, these findings suggest that student participation in High Impact Engagement Practices might improve academic success and course retention. Theoretical and practical implications are discussed.more » « less
-
Abstract The spread of infectious disease in a human community or the proliferation of fake news on social media can be modelled as a randomly growing tree-shaped graph. The history of the random growth process is often unobserved but contains important information such as the source of the infection. We consider the problem of statistical inference on aspects of the latent history using only a single snapshot of the final tree. Our approach is to apply random labels to the observed unlabelled tree and analyse the resulting distribution of the growth process, conditional on the final outcome. We show that this conditional distribution is tractable under a shape exchangeability condition, which we introduce here, and that this condition is satisfied for many popular models for randomly growing trees such as uniform attachment, linear preferential attachment and uniform attachment on a D-regular tree. For inference of the root under shape exchangeability, we propose O(n log n) time algorithms for constructing confidence sets with valid frequentist coverage as well as bounds on the expected size of the confidence sets. We also provide efficient sampling algorithms which extend our methods to a wide class of inference problems.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
