Daniel Stefankovic

is this you? claim profile

0

  • Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models

    The Gibbs sampler is a particularly popular Markov chain used for learning and inference problems in Graphical Models (GMs). These tasks are computationally intractable in general, and the Gibbs sampler often suffers from slow mixing. In this paper, we study the Swendsen-Wang dynamics which is a more sophisticated Markov chain designed to overcome bottlenecks that impede the Gibbs sampler. We prove O( n) mixing time for attractive binary pairwise GMs (i.e., ferromagnetic Ising models) on stochastic partitioned graphs having n vertices, under some mild conditions, including low temperature regions where the Gibbs sampler provably mixes exponentially slow. Our experiments also confirm that the Swendsen-Wang sampler significantly outperforms the Gibbs sampler when they are used for learning parameters of attractive GMs.

    04/06/2017 ∙ by Sejun Park, et al. ∙ 0 share

    read it

  • On The Projection Operator to A Three-view Cardinality Constrained Set

    The cardinality constraint is an intrinsic way to restrict the solution structure in many domains, for example, sparse learning, feature selection, and compressed sensing. To solve a cardinality constrained problem, the key challenge is to solve the projection onto the cardinality constraint set, which is NP-hard in general when there exist multiple overlapped cardinality constraints. In this paper, we consider the scenario where the overlapped cardinality constraints satisfy a Three-view Cardinality Structure (TVCS), which reflects the natural restriction in many applications, such as identification of gene regulatory networks and task-worker assignment problem. We cast the projection into a linear programming, and show that for TVCS, the vertex solution of this linear programming is the solution for the original projection problem. We further prove that such solution can be found with the complexity proportional to the number of variables and constraints. We finally use synthetic experiments and two interesting applications in bioinformatics and crowdsourcing to validate the proposed TVCS model and method.

    03/21/2017 ∙ by Haichuan Yang, et al. ∙ 0 share

    read it

  • Subset Selection for Gaussian Markov Random Fields

    Given a Gaussian Markov random field, we consider the problem of selecting a subset of variables to observe which minimizes the total expected squared prediction error of the unobserved variables. We first show that finding an exact solution is NP-hard even for a restricted class of Gaussian Markov random fields, called Gaussian free fields, which arise in semi-supervised learning and computer vision. We then give a simple greedy approximation algorithm for Gaussian free fields on arbitrary graphs. Finally, we give a message passing algorithm for general Gaussian Markov random fields on bounded tree-width graphs.

    09/26/2012 ∙ by Satyaki Mahalanabis, et al. ∙ 0 share

    read it

  • Structure Learning of H-colorings

    We study the structure learning problem for graph homomorphisms, commonly referred to as H-colorings, including the weighted case which corresponds to spin systems with hard constraints. The learning problem is as follows: for a fixed (and known) constraint graph H with q colors and an unknown graph G=(V,E) with n vertices, given uniformly random H-colorings of G, how many samples are required to learn the edges of the unknown graph G? We give a characterization of H for which the problem is identifiable for every G, i.e., we can learn G with an infinite number of samples. We focus particular attention on the case of proper vertex q-colorings of graphs of maximum degree d where intriguing connections to statistical physics phase transitions appear. We prove that when q>d the problem is identifiable and we can learn G in poly(d,q)× O(n^2n) time. In contrast for soft-constraint systems, such as the Ising model, the best possible running time is exponential in d. When q≤ d we prove that the problem is not identifiable, and we cannot hope to learn G. When q<d-√(d) + Θ(1) we prove that even learning an equivalent graph (any graph with the same set of H-colorings) is computationally hard---sample complexity is exponential in n in the worst-case. For the q-colorings problem, the threshold for efficient learning seems to be connected to the uniqueness/non-uniqueness phase transition at q=d. We explore this connection for general H-colorings and prove that under a well-known condition in statistical physics, known as Dobrushin uniqueness condition, we can learn G in poly(d,q)× O(n^2n) time.

    08/17/2017 ∙ by Antonio Blanca, et al. ∙ 0 share

    read it

  • Inapproximability of the independent set polynomial in the complex plane

    We study the complexity of approximating the independent set polynomial Z_G(λ) of a graph G with maximum degree Δ when the activity λ is a complex number. This problem is already well understood when λ is real using connections to the Δ-regular tree T. The key concept in that case is the "occupation ratio" of the tree T. This ratio is the contribution to Z_T(λ) from independent sets containing the root of the tree, divided by Z_T(λ) itself. If λ is such that the occupation ratio converges to a limit, as the height of T grows, then there is an FPTAS for approximating Z_G(λ) on a graph G with maximum degree Δ. Otherwise, the approximation problem is NP-hard. Unsurprisingly, the case where λ is complex is more challenging. Peters and Regts identified the values of λ for which the occupation ratio of the Δ-regular tree converges. These values carve a cardioid-shaped region Λ_Δ in the complex plane. Motivated by the picture in the real case, they asked whether Λ_Δ marks the true approximability threshold for general complex values λ. Our main result shows that for every λ outside of Λ_Δ, the problem of approximating Z_G(λ) on graphs G with maximum degree at most Δ is indeed NP-hard. In fact, when λ is outside of Λ_Δ and is not a positive real number, we give the stronger result that approximating Z_G(λ) is actually #P-hard. If λ is a negative real number outside of Λ_Δ, we show that it is #P-hard to even decide whether Z_G(λ)>0, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis - specifically the study of iterative multivariate rational maps.

    11/01/2017 ∙ by Ivona Bezakova, et al. ∙ 0 share

    read it

  • On Counting Perfect Matchings in General Graphs

    Counting perfect matchings has played a central role in the theory of counting problems. The permanent, corresponding to bipartite graphs, was shown to be #P-complete to compute exactly by Valiant (1979), and a fully polynomial randomized approximation scheme (FPRAS) was presented by Jerrum, Sinclair, and Vigoda (2004) using a Markov chain Monte Carlo (MCMC) approach. However, it has remained an open question whether there exists an FPRAS for counting perfect matchings in general graphs. In fact, it was unresolved whether the same Markov chain defined by JSV is rapidly mixing in general. In this paper, we show that it is not. We prove torpid mixing for any weighting scheme on hole patterns in the JSV chain. As a first step toward overcoming this obstacle, we introduce a new algorithm for counting matchings based on the Gallai-Edmonds decomposition of a graph, and give an FPRAS for counting matchings in graphs that are sufficiently close to bipartite. In particular, we obtain a fixed-parameter tractable algorithm for counting matchings in general graphs, parameterized by the greatest "order" of a factor-critical subgraph.

    12/20/2017 ∙ by Daniel Stefankovic, et al. ∙ 0 share

    read it

  • Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs

    We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers q≥ 3 and Δ≥ 3, we develop algorithms that produce samples within error o(1) from the q-state Potts model on random Δ-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes may induce linear-sized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of q and Δ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we simplify the algorithm significantly by utilising the random-cluster representation of the model. In particular, we show that a percolation-type algorithm succeeds in sampling from the random-cluster model with parameters p,q on random Δ-regular graphs for all values of q≥ 1 and p<p_c(q,Δ), where p_c(q,Δ) corresponds to a uniqueness threshold for the model on the Δ-regular tree. When restricted to integer values of q, this yields a simplified algorithm for the ferromagnetic Potts model on random Δ-regular graphs.

    04/22/2018 ∙ by Antonio Blanca, et al. ∙ 0 share

    read it

  • The complexity of approximating the matching polynomial in the complex plane

    We study the problem of approximating the value of the matching polynomial on graphs with edge parameter γ, where γ takes arbitrary values in the complex plane. When γ is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of γ, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree Δ as long as γ is not a negative real number less than or equal to -1/(4(Δ-1)). Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all Δ≥ 3 and all real γ less than -1/(4(Δ-1)), the problem of approximating the value of the matching polynomial on graphs of maximum degree Δ with edge parameter γ is #P-hard. We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real γ it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #P-hard on graphs with bounded connective constant for a dense set of γ values on the negative real axis. Nevertheless, we show that the result does extend for any complex value γ that does not lie on the negative real axis. Our analysis accounts for complex values of γ using geodesic distances in the complex plane in the metric defined by an appropriate density function.

    07/13/2018 ∙ by Ivona Bezakova, et al. ∙ 0 share

    read it

  • Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models

    We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model M and a sampling oracle for the distribution μ_M̂ of an unknown model M̂, can we efficiently determine if the two models M and M̂ are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. In particular, for n-vertex graphs of maximum degree d, we prove that if |β| d = ω(n) (where β is the inverse temperature parameter), then there is no polynomial running time identity testing algorithm unless RP=NP. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. Our proofs utilize insights into the design of gadgets using random graphs in recent works concerning the hardness of approximate counting by Sly (2010). In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing is hard in the same range of parameters where structure learning is known to be hard.

    01/22/2019 ∙ by Ivona Bezakova, et al. ∙ 0 share

    read it