We prove that the lazy random walk on the discrete cube, censored to any increasing set of fixed positive density, mixes in time $O(n\log n)$, answering a question of Ding and Mossel. More precisely, for every nonempty increasing set $A\subseteq \{0,1\}^n$, \begin{equation} t_{\mathrm{mix}}(P) \le K\mu(A)^{-3}n\log(en). \label{eq:mixing-time-bound} \end{equation} where $\mu$ is uniform on the cube and $K$ is an absolute constant. The proof uses hypercontractivity on the ambient cube to strengthen Poincar\'e inequality on coordinate sections. A stopping-time occupation inequality for increasing sets converts the resulting local bound into a uniform bound on hitting times of large sets. See the appendix for a better estimates of the constant and the dependence on \(\mu(A)\).
Consider $n$ independent, non-negative, mean at most one random variables, $X_1,X_2,\ldots$. We show the following bound on the probability of their sum exceeding a threshold $t$: \[ \mathbb{P}\left[\sum_{i=1}^n X_i\ge t\right] \leq 1-\left(1-\frac{1}{t}\right)^n \text{ for all } t\ge 2n+1 \,. \] To prove this, we cons...
We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|\Gamma|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(\Gamma)\le k \quad\t...
We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017),...
Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\, \mathrm{d} x$ on $\mathbb{R}^d$, where $U$ is continuously differentiable and $m$-strongly convex with a globally $L$-Lipschitz gradient, $0<m\leq L<\infty$, and $\kappa=L/m$. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds...
We prove Breiman's conjecture under the first-moment assumption. Let $Y_1,Y_2,\ldots$ be iid nonnegative random variables with $\mathbb P\{Y_1>0\}>0$, normalized by their sum. If the resulting randomly weighted sum converges to a nondegenerate law for one fixed integrable, nonconstant mark distribution, then the tail o...
Uniform stability is a classical tool for controlling the generalization error of a learning algorithm. Bousquet, Klochkov, and Zhivotovskiy (2020) showed that the problem can be reduced to a moment inequality for a sum of weakly interacting functions of independent random variables. Their bound contains an additional...
Thanh Nguyen-Cung, B. T. Nguyen· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
