-
作者：Amarnik, David; Adik, Ilias
作者单位：Massachusetts Institute of Technology (MIT); New York University
摘要：We study the computational-statistical gap of the planted clique problem, where a clique of size k is planted in an Erdos-Renyi graph G(n, 1/2). The goal is to recover the planted clique vertices by observing the graph. It is known that the clique can be recovered as long as k >= (2 + epsilon) log n for any epsilon > 0, but no polynomial-time algorithm is known for this task unless k = Omega (root n). Following a statistical-physics inspired point of view, as a way to understand the nature of ...
-
作者：Legried, Brandon; Roch, Sebastien
作者单位：University System of Georgia; Georgia Institute of Technology; University of Wisconsin System; University of Wisconsin Madison
摘要：Ancestral sequence reconstruction is a key task in computational biology. It consists in inferring a molecular sequence at an ancestral species of a known phylogeny, given descendant sequences at the tip of the tree. In addition to its many biological applications, it has played a key role in elucidating the statistical performance of phylogeny estimation methods. Here we establish a formal connection to another important bioinformatics problem, multiple sequence alignment, where one attempts ...
-
作者：Erdos, Laszlo; McKenna, Benjamin
作者单位：Institute of Science & Technology - Austria
摘要：We consider quadratic forms of deterministic matrices A evaluated at the random eigenvectors of a large N x N GOE or GUE matrix, or equivalently evaluated at the columns of a Haar-orthogonal or Haar-unitary random matrix. We prove that, as long as the deterministic matrix has rank much smaller than root N, the distributions of the extrema of these quadratic forms are asymptotically the same as if the eigenvectors were independent Gaussians. This reduces the problem to Gaussian computations, wh...
-
作者：Durmus, Alain; Eberle, Andreas; Enfroy, Aurelien; Guillin, Arnaud; Monmarche, Pierre
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; University of Bonn; Universite Paris Saclay; Universite Clermont Auvergne (UCA); Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Sorbonne Universite; Universite Paris Cite
摘要：In this paper, we provide bounds in Wasserstein and total variation distances between the distributions of the successive iterates of two functional autoregressive processes with isotropic Gaussian noise of the form Yk+1 = T gamma (Yk)+ gamma sigma 2Zk+1 and Yk+1 = T gamma ( Yk)+ gamma sigma 2 Zk+1. More precisely, we give nonasymptotic bounds on rho(L(Yk),L( Yk)), where rho is an appropriate weighted Wasserstein distance or a V-distance, uniformly in the parameter gamma , and on rho (pi gamma...
-
作者：Ganassali, Luca; Massoulie, Laurent; Semerjian, Guilhem
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Inria; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite Paris Cite; Sorbonne Universite
摘要：In this paper we address the problem of testing whether two observed trees (t, t') are sampled either independently or from a joint distribution under which they are correlated. This problem, which we refer to as correlation detection in trees, plays a key role in the study of graph alignment for two correlated random graphs. Motivated by graph alignment, we investigate the conditions of existence of one-sided tests, that is, tests which have vanishing type I error and nonvanishing power in th...
-
作者：Ganassali, Luca; Lelarge, Marc; Massoulie, Laurent
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Inria
摘要：Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We study the likelihood ratio test and obtain sufficient conditions under which this task is impossible or feasible. We propose MPAlign, a message-passing algorithm for graph alignment inspired by the tree correlation detection problem. We prove MPAlign to succeed in polynomial time at partial alignment whenever tree detection is feasi...
-
作者：Davydova, Michel
作者单位：Inria; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS)
摘要：Neural computations arising from myriads of interactions between spiking neurons can be modeled as network dynamics with punctuate interactions. However, most relevant dynamics do not allow for computational tractability. To circumvent this difficulty, the Poisson hypothesis regime replaces interaction times between neurons by Poisson processes. We prove that the Poisson hypothesis holds at the limit of an infinite number of replicas in the replica-mean-field model, which consists of randomly ...
-
作者：Fang, Xiao; Koike, Yuta
作者单位：Chinese University of Hong Kong; University of Tokyo
摘要：We prove the large-dimensional Gaussian approximation of a sum ofnindependent random vectors inRdtogether with fourth-moment error boundson convex sets and Euclidean balls. Our bounds have near-optimal depen-dence onnand, compared with classical third-moment bounds, can achieveimproved dependence on the dimensiond. For centered balls, we obtain anadditional error bound that has a sub-optimal dependence onn, but recoversthe known result of the validity of the Gaussian approximation if and onlyi...
-
作者：Besancon, Eustache; Coutin, Laure; Decreusefond, Laurent; Moyal, Pascal
作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite de Lorraine
摘要：Continuous time Markov Chains, Hawkes processes and many other interesting processes can be described as a solution of stochastic differential equations driven by Poisson measures. Previous works, using the Stein's method, give the convergence rate of a sequence of renormalized Poisson measures toward the Brownian motion in several distances, constructed on the model of the Kantorovitch Rubinstein (or Wasserstein-1) distance. We show that many operations (like time change, convolution) on cont...
-
作者：Qin, Qian; Wang, Guanyang
作者单位：University of Minnesota System; University of Minnesota Twin Cities; Rutgers University System; Rutgers University New Brunswick
摘要：Random-scan Gibbs samplers possess a natural hierarchical structure. The structure connects Gibbs samplers targeting higher-dimensional distributions to those targeting lower-dimensional ones. This leads to a quasi-telescoping property of their spectral gaps. Based on this property, we derive three new bounds on the spectral gaps and convergence rates of Gibbs samplers on general domains. The three bounds relate a chain's spectral gap to, respectively, the correlation structure of the target d...
