7 papers
MaxCut for Covariances
Gleb Smirnov
Let have a multivariate totally positive () law. We prove that $$ \sum_{i<j}\mathbb{E}\left[\left|\mathrm{Cov}(X_i,X_j \mid X_{[n]\s…
Deep belief networks are exact
Gleb Smirnov
We prove that every strictly positive probability distribution on \(\{-1,1\}^n\) is represented exactly by a sigmoid belief network with finite parameters. This answers a question…
Random sets are close to low-discrepancy sets
Gleb Smirnov, Roman Vershynin
We show that a random sample from an arbitrary probability measure on is close to a low-discrepancy point set. Namely, after moving only a small fraction of the samp…
Discrepancy and Fisher information
Gleb Smirnov, Roman Vershynin
We give an online algorithm that keeps a symmetric random walk inside a convex body by discarding some of its steps. The expected number of discarded steps is controlled by a Fishe…
Thinning to improve two-sample discrepancy
Gleb Smirnov, Roman Vershynin
The discrepancy between two independent samples \(X_1,\dots,X_n\) and \(Y_1,\dots,Y_n\) drawn from the same distribution on typically has order \(O(\sqrt{n})\) even…
Improving discrepancy by moving a few points
Gleb Smirnov, Roman Vershynin
We show how to improve the discrepancy of an iid sample by moving only a few points. Specifically, modifying \( O(m) \) sample points on average reduces the Kolmogorov-Smirnov dist…