An official website of the United States government
We study the problem of testing identity against a given distribution with a focus on the high confidence regime. More precisely, given samples from an unknown distribution p over n elements, an explicitly given distribution q, and parameters 0< epsilon, delta < 1, we wish to distinguish, with probability at least 1-delta, whether the distributions are identical versus epsilon-far in total variation distance. Most prior work focused on the case that delta = Omega(1), for which the sample complexity of identity testing is known to be Theta(sqrt{n}/epsilon^2). Given such an algorithm, one can achieve arbitrarily small values of delta via black-box amplification, which multiplies the required number of samples by Theta(log(1/delta)). We show that black-box amplification is suboptimal for any delta = o(1), and give a new identity tester that achieves the optimal sample complexity. Our new upper and lower bounds show that the optimal sample complexity of identity testing is Theta((1/epsilon^2) (sqrt{n log(1/delta)} + log(1/delta))) for any n, epsilon, and delta. For the special case of uniformity testing, where the given distribution is the uniform distribution U_n over the domain, our new tester is surprisingly simple: to test whether p = U_n versus d_{TV} (p, U_n) >= epsilon, we simply threshold d_{TV}({p^}, U_n), where {p^} is the empirical probability distribution. The fact that this simple "plug-in" estimator is sample-optimal is surprising, even in the constant delta case. Indeed, it was believed that such a tester would not attain sublinear sample complexity even for constant values of epsilon and delta. An important contribution of this work lies in the analysis techniques that we introduce in this context. First, we exploit an underlying strong convexity property to bound from below the expectation gap in the completeness and soundness cases. Second, we give a new, fast method for obtaining provably correct empirical estimates of the true worst-case failure probability for a broad class of uniformity testing statistics over all possible input distributions - including all previously studied statistics for this problem. We believe that our novel analysis techniques will be useful for other distribution testing problems as well.
more »
« less
Sample Complexity of Probabilistic Roadmaps via epsilon-nets
We study fundamental theoretical aspects of probabilistic roadmaps (PRM) in the finite time (non-asymptotic) regime. In particular, we investigate how completeness and optimality guarantees of the approach are influenced by the underlying deterministic sampling distribution $${\X}$$ and connection radius $${r>0}$$. We develop the notion of $${(\delta,\epsilon)}$$-completeness of the parameters $${\X, r}$$, which indicates that for every motion-planning problem of clearance at least $${\delta>0}$$, PRM using $${\X, r}$$ returns a solution no longer than $${1+\epsilon}$$ times the shortest $${\delta}$$-clear path. Leveraging the concept of $${\epsilon}$$-nets, we characterize in terms of lower and upper bounds the number of samples needed to guarantee $${(\delta,\epsilon)}$$-completeness. This is in contrast with previous work which mostly considered the asymptotic regime in which the number of samples tends to infinity. In practice, we propose a sampling distribution inspired by $${\epsilon}$$-nets that achieves nearly the same coverage as grids while using significantly fewer samples.
more »
« less
- Award ID(s):
- 1931815
- PAR ID:
- 10192547
- Date Published:
- Journal Name:
- IEEE International Conference on Robotics and Automation
- ISSN:
- 1049-3492
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
An $(n,r,s)$-system is an $$r$$-uniform hypergraph on $$n$$ vertices such that every pair of edges has an intersection of size less than $$s$$. Using probabilistic arguments, Rödl and Šiňajová showed that for all fixed integers $$r> s \ge 2$$, there exists an $(n,r,s)$-system with independence number $$O\left(n^{1-\delta+o(1)}\right)$$ for some optimal constant $$\delta >0$$ only related to $$r$$ and $$s$$. We show that for certain pairs $(r,s)$ with $$s\le r/2$$ there exists an explicit construction of an $(n,r,s)$-system with independence number $$O\left(n^{1-\epsilon}\right)$$, where $$\epsilon > 0$$ is an absolute constant only related to $$r$$ and $$s$$. Previously this was known only for $s>r/2$ by results of Chattopadhyay and Goodman.more » « less
-
This is the second in a pair of works which study small disturbances to the plane, periodic 3D Couette flow in the incompressible Navier-Stokes equations at high Reynolds number Re . In this work, we show that there is constant 0 > c 0 ≪ 1 0 > c_0 \ll 1 , independent of R e \mathbf {Re} , such that sufficiently regular disturbances of size ϵ ≲ R e − 2 / 3 − δ \epsilon \lesssim \mathbf {Re}^{-2/3-\delta } for any δ > 0 \delta > 0 exist at least until t = c 0 ϵ − 1 t = c_0\epsilon ^{-1} and in general evolve to be O ( c 0 ) O(c_0) due to the lift-up effect. Further, after times t ≳ R e 1 / 3 t \gtrsim \mathbf {Re}^{1/3} , the streamwise dependence of the solution is rapidly diminished by a mixing-enhanced dissipation effect and the solution is attracted back to the class of “2.5 dimensional” streamwise-independent solutions (sometimes referred to as “streaks”). The largest of these streaks are expected to eventually undergo a secondary instability at t ≈ ϵ − 1 t \approx \epsilon ^{-1} . Hence, our work strongly suggests, for all (sufficiently regular) initial data, the genericity of the “lift-up effect ⇒ \Rightarrow streak growth ⇒ \Rightarrow streak breakdown” scenario for turbulent transition of the 3D Couette flow near the threshold of stability forwarded in the applied mathematics and physics literature.more » « less
-
Abstract: We consider the quadratic Zakharov-Kuznetsov equation $$\partial_t u + \partial_x \Delta u + \partial_x u^2=0$$ on $$\Bbb{R}^3$$. A solitary wave solution is given by $Q(x-t,y,z)$, where $$Q$$ is the ground state solution to $$-Q+\Delta Q+Q^2=0$$. We prove the asymptotic stability of these solitary wave solutions. Specifically, we show that initial data close to $$Q$$ in the energy space, evolves to a solution that, as $$t\to\infty$$, converges to a rescaling and shift of $Q(x-t,y,z)$ in $L^2$ in a rightward shifting region $$x>\delta t-\tan\theta\sqrt{y^2+z^2}$$ for $$0\leq\theta\leq{\pi\over 3}-\delta$$.more » « less
-
We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time. When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sub-linear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilon-approximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d-1)/(2d-1)}) poly log n time algorithm for computing epsilon-approximate bottleneck matching in d-dimensions. All previous algorithms take Omega(n^{3/2}) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size |V'|^{delta}, for delta in [1/2,1), we can apply our algorithm to compute a maximum matching in O~(mn^{delta/1+delta}) time improving upon the O(m sqrt{n}) time taken by the HK-Algorithm.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
