The Experts below are selected from a list of 57 Experts worldwide ranked by ideXlab platform
Van Vu - One of the best experts on this subject based on the ideXlab platform.
-
A Simple SVD Algorithm for Finding Hidden Partitions
Combinatorics Probability and Computing, 2017Co-Authors: Van VuAbstract:Finding a Hidden Partition in a random environment is a general and important problem which contains as subproblems many important questions, such as finding a Hidden clique, finding a Hidden colouring, finding a Hidden biPartition, etc.In this paper we provide a simple SVD algorithm for this purpose, addressing a question of McSherry. This algorithm is easy to implement and works for sparse graphs under optimal density assumptions. We also consider an approximating algorithm, which on one hand works under very mild assumptions, but on other hand can sometimes be upgraded to give the exact solution.
-
A simple SVD algorithm for finding Hidden Partitions
arXiv: Combinatorics, 2014Co-Authors: Van VuAbstract:Finding a Hidden Partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a Hidden clique, finding a Hidden coloring, finding a Hidden biPartition etc. In this paper, we provide a simple SVD algorithm for this purpose, answering a question of McSherry. This algorithm is very easy to implement and works for sparse graphs with optimal density.
Hervé Glotin - One of the best experts on this subject based on the ideXlab platform.
-
ICPR - Bayesian Non-parametric Parsimonious Gaussian Mixture for Clustering
2014 22nd International Conference on Pattern Recognition, 2014Co-Authors: Faicel Chamroukhi, Marius Bartcus, Hervé GlotinAbstract:Clustering is one of the essential tasks in machine learning and statistical pattern recognition. One of the most popular approaches in cluster analysis is the one based on the parametric finite mixture model. However, often, parametric models are not well adapted to represent complex and realistic data sets. Another issue in the finite mixture model-based clustering approach is the one of selecting the number of mixture components. The Bayesian non-parametric statistical methods for clustering provide a principled way to overcome these issues. This paper proposes a new Bayesian non-parametric approach for clustering. It relies on an Infinite Gaussian mixture model with an Eigen value decomposition of the covariance matrix of each cluster, and a Chinese Restaurant Process (CRP) prior over the Hidden Partition. The CRP prior allows to control the model complexity in a principled way, and to automatically learn the number of clusters from the data. The covariance matrix decomposition allows to fit various flexible models going from simplest spherical ones to the more complex general one. We develop a Gibbs sampler to learn the various models and apply it to simulated data and benchmarks, and a real-world data issued from a challenging problem of whale song decomposition. The obtained results highlight the interest of the proposed non-parametric parsimonious mixture model for clustering.
-
Bayesian Non-parametric Parsimonious Gaussian Mixture for Clustering
2014 22nd International Conference on Pattern Recognition, 2014Co-Authors: Faicel Chamroukhi, Marius Bartcus, Hervé GlotinAbstract:Clustering is one of the essential tasks in machine learning and statistical pattern recognition. One of the most popular approaches in cluster analysis is the one based on the parametric finite mixture model. However, often, parametric models are not well adapted to represent complex and realistic data sets. Another issue in the finite mixture model-based clustering approach is the one of selecting the number of mixture components. The Bayesian non-parametric statistical methods for clustering provide a principled way to overcome these issues. This paper proposes a new Bayesian non-parametric approach for clustering. It relies on an Infinite Gaussian mixture model with an Eigen value decomposition of the covariance matrix of each cluster, and a Chinese Restaurant Process (CRP) prior over the Hidden Partition. The CRP prior allows to control the model complexity in a principled way, and to automatically learn the number of clusters from the data. The covariance matrix decomposition allows to fit various flexible models going from simplest spherical ones to the more complex general one. We develop a Gibbs sampler to learn the various models and apply it to simulated data and benchmarks, and a real-world data issued from a challenging problem of whale song decomposition. The obtained results highlight the interest of the proposed non-parametric parsimonious mixture model for clustering.
Dmitry Krachun - One of the best experts on this subject based on the ideXlab platform.
-
STOC - An optimal space lower bound for approximating MAX-CUT
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, 2019Co-Authors: Michael Kapralov, Dmitry KrachunAbstract:We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output half of this value as the estimate for the size of the MAX-CUT. On the other extreme, for any fixed є > 0, if one allows O(n) space, a (1+є)-approximate solution to the MAX-CUT value can be obtained by storing an O(n)-size sparsifier that essentially preserves MAX-CUT value. Our main result is that any (randomized) single pass streaming algorithm that breaks the 2-approximation barrier requires Ω(n)-space, thus resolving the space complexity of any non-trivial approximations of the MAX-CUT value to within polylogarithmic factors in the single pass streaming model. We achieve the result by presenting a tight analysis of the Implicit Hidden Partition Problem introduced by Kapralov et al. [SODA’17] for an arbitrarily large number of players. In this problem a number of players receive random matchings of Ω(n) size together with random bits on the edges, and their task is to determine whether the bits correspond to parities of some Hidden biPartition, or are just uniformly random. Unlike all previous Fourier analytic communication lower bounds, our analysis does not directly use bounds on the l2 norm of Fourier coefficients of a typical message at any given weight level that follow from hypercontractivity. Instead, we use the fact that graphs received by players are sparse (matchings) to obtain strong upper bounds on the l1 norm of the Fourier coefficients of the messages of individual players using their special structure, and then argue, using the convolution theorem, that similar strong bounds on the l1 norm are essentially preserved (up to an exponential loss in the number of players) once messages of different players are combined. We feel that our main technique is likely of independent interest.
-
An Optimal Space Lower Bound for Approximating MAX-CUT
arXiv: Data Structures and Algorithms, 2018Co-Authors: Michael Kapralov, Dmitry KrachunAbstract:We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial $2$-approximation for this problem that uses only $O(\log n)$ space, namely, count the number of edges and output half of this value as the estimate for the size of the MAX-CUT. On the other extreme, for any fixed $\epsilon > 0$, if one allows $\tilde{O}(n)$ space, a $(1+\epsilon)$-approximate solution to the MAX-CUT value can be obtained by storing an $\tilde{O}(n)$-size sparsifier that essentially preserves MAX-CUT value. Our main result is that any (randomized) single pass streaming algorithm that breaks the $2$-approximation barrier requires $\Omega(n)$-space, thus resolving the space complexity of any non-trivial approximations of the MAX-CUT value to within polylogarithmic factors in the single pass streaming model. We achieve the result by presenting a tight analysis of the Implicit Hidden Partition Problem introduced by Kapralov et al.[SODA'17] for an arbitrarily large number of players. In this problem a number of players receive random matchings of $\Omega(n)$ size together with random bits on the edges, and their task is to determine whether the bits correspond to parities of some Hidden biPartition, or are just uniformly random. Unlike all previous Fourier analytic communication lower bounds, our analysis does not directly use bounds on the $\ell_2$ norm of Fourier coefficients of a typical message at any given weight level that follow from hypercontractivity. Instead, we use the fact that graphs received by players are sparse (matchings) to obtain strong upper bounds on the $\ell_1$ norm of the Fourier coefficients of the messages of individual players, and then argue, using the convolution theorem, that similar strong bounds on the $\ell_1$ norm are essentially preserved once messages of different players are combined.
Faicel Chamroukhi - One of the best experts on this subject based on the ideXlab platform.
-
ICPR - Bayesian Non-parametric Parsimonious Gaussian Mixture for Clustering
2014 22nd International Conference on Pattern Recognition, 2014Co-Authors: Faicel Chamroukhi, Marius Bartcus, Hervé GlotinAbstract:Clustering is one of the essential tasks in machine learning and statistical pattern recognition. One of the most popular approaches in cluster analysis is the one based on the parametric finite mixture model. However, often, parametric models are not well adapted to represent complex and realistic data sets. Another issue in the finite mixture model-based clustering approach is the one of selecting the number of mixture components. The Bayesian non-parametric statistical methods for clustering provide a principled way to overcome these issues. This paper proposes a new Bayesian non-parametric approach for clustering. It relies on an Infinite Gaussian mixture model with an Eigen value decomposition of the covariance matrix of each cluster, and a Chinese Restaurant Process (CRP) prior over the Hidden Partition. The CRP prior allows to control the model complexity in a principled way, and to automatically learn the number of clusters from the data. The covariance matrix decomposition allows to fit various flexible models going from simplest spherical ones to the more complex general one. We develop a Gibbs sampler to learn the various models and apply it to simulated data and benchmarks, and a real-world data issued from a challenging problem of whale song decomposition. The obtained results highlight the interest of the proposed non-parametric parsimonious mixture model for clustering.
-
Bayesian Non-parametric Parsimonious Gaussian Mixture for Clustering
2014 22nd International Conference on Pattern Recognition, 2014Co-Authors: Faicel Chamroukhi, Marius Bartcus, Hervé GlotinAbstract:Clustering is one of the essential tasks in machine learning and statistical pattern recognition. One of the most popular approaches in cluster analysis is the one based on the parametric finite mixture model. However, often, parametric models are not well adapted to represent complex and realistic data sets. Another issue in the finite mixture model-based clustering approach is the one of selecting the number of mixture components. The Bayesian non-parametric statistical methods for clustering provide a principled way to overcome these issues. This paper proposes a new Bayesian non-parametric approach for clustering. It relies on an Infinite Gaussian mixture model with an Eigen value decomposition of the covariance matrix of each cluster, and a Chinese Restaurant Process (CRP) prior over the Hidden Partition. The CRP prior allows to control the model complexity in a principled way, and to automatically learn the number of clusters from the data. The covariance matrix decomposition allows to fit various flexible models going from simplest spherical ones to the more complex general one. We develop a Gibbs sampler to learn the various models and apply it to simulated data and benchmarks, and a real-world data issued from a challenging problem of whale song decomposition. The obtained results highlight the interest of the proposed non-parametric parsimonious mixture model for clustering.
Andrea Montanari - One of the best experts on this subject based on the ideXlab platform.
-
STOC - Semidefinite programs on sparse random graphs and their application to community detection
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016, 2016Co-Authors: Andrea MontanariAbstract:Denote by A the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing over the set of positive semidefinite matrices X with diagonal entries X_ii=1. We prove that for large (bounded) average degree d, the value of this semidefinite program (SDP) is --with high probability-- 2n*sqrt(d) + n, o(sqrt(d))+o(n). For a random regular graph of degree d, we prove that the SDP value is 2n*sqrt(d-1)+o(n), matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted Partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is Partitioned into subsets of size n/2, with edge probability a/n (within group) and b/n (across). We prove that SDP detects the Partition with high probability provided (a-b)^2/(4d)> 1+o_d(1), with d= (a+b)/2. By comparison, the information theoretic threshold for detecting the Hidden Partition is (a-b)^2/(4d)> 1: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: (i) A new 'higher-rank' Grothendieck inequality for symmetric matrices; (ii) An interpolation method inspired from statistical physics; (iii) An analysis of the eigenvectors of deformed Gaussian random matrices.
-
Semidefinite Programs on Sparse Random Graphs and their Application to Community Detection
arXiv: Discrete Mathematics, 2015Co-Authors: Andrea MontanariAbstract:Denote by $A$ the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing $\langle A-E\{A\},X\rangle$ over the set of positive semidefinite matrices $X$ with diagonal entries $X_{ii}=1$. We prove that for large (bounded) average degree $d$, the value of this semidefinite program (SDP) is --with high probability-- $2n\sqrt{d} + n\, o(\sqrt{d})+o(n)$. For a random regular graph of degree $d$, we prove that the SDP value is $2n\sqrt{d-1}+o(n)$, matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted Partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is Partitioned into subsets of size $n/2$, with edge probability $a/n$ (within group) and $b/n$ (across). We prove that SDP detects the Partition with high probability provided $(a-b)^2/(4d)> 1+o_{d}(1)$, with $d= (a+b)/2$. By comparison, the information theoretic threshold for detecting the Hidden Partition is $(a-b)^2/(4d)> 1$: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: $(i)$ A new `higher-rank' Grothendieck inequality for symmetric matrices; $(ii)$ An interpolation method inspired from statistical physics; $(iii)$ An analysis of the eigenvectors of deformed Gaussian random matrices.