Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
77
0
0.0
(
0
)
Added by
Kevin Tian
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when applied to well-conditioned distributions. Our main result is a nearly-tight lower bound of $widetilde{Omega}(kappa d)$ on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results up to logarithmic factors and answering an open question of Chewi et. al. We also show that a polynomial dependence on dimension is necessary for the relaxation time of HMC under any number of leapfrog steps, and bound the gains achievable by changing the step count. Our HMC analysis draws upon a novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.
rate research
Read More
We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length $m$ and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an $O(m^{1/2-varepsilon})$ time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.
The determinant can be computed by classical circuits of depth $O(log^2 n)$, and therefore it can also be computed in classical space $O(log^2 n)$. Recent progress by Ta-Shma [Ta13] implies a method to approximate the determinant of Hermitian matrices with condition number $kappa$ in quantum space $O(log n + log kappa)$. However, it is not known how to perform the task in less than $O(log^2 n)$ space using classical resources only. In this work, we show that the condition number of a matrix implies an upper bound on the depth complexity (and therefore also on the space complexity) for this task: the determinant of Hermitian matrices with condition number $kappa$ can be approximated to inverse polynomial relative error with classical circuits of depth $tilde O(log n cdot log kappa)$, and in particular one can approximate the determinant for sufficiently well-conditioned matrices in depth $tilde{O}(log n)$. Our algorithm combines Barvinoks recent complex-analytic approach for approximating combinatorial counting problems [Bar16] with the Valiant-Berkowitz-Skyum-Rackoff depth-reduction theorem for low-degree arithmetic circuits [Val83].
We prove that any two-pass graph streaming algorithm for the $s$-$t$ reachability problem in $n$-vertex directed graphs requires near-quadratic space of $n^{2-o(1)}$ bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out $o(n^{7/6})$ space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most $k$. We call this the $Dyck_{k,n}$ problem. We prove a lower bound of $Omega(c^k sqrt{n})$, showing that the complexity of this problem increases exponentially in $k$. Here $n$ is the length of the word. When $k$ is a constant, this is interesting as a representative example of star-free languages for which a surprising $tilde{O}(sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When $k$ is not a constant, $Dyck_{k,n}$ is not context-free. We give an algorithm with $Oleft(sqrt{n}(log{n})^{0.5k}right)$ quantum queries for $Dyck_{k,n}$ for all $k$. This is better than the trival upper bound $n$ for $k=oleft(frac{log(n)}{loglog n}right)$. Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the balanced parentheses problem into the grid, we show a lower bound of $Omega(n^{1.5-epsilon})$ for the directed 2D grid and $Omega(n^{2-epsilon})$ for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an $O((m+n)log n)$ algorithm for finding a canonical version of such a stable colouring, on graphs with $n$ vertices and $m$ edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
