Skip to Main content Skip to Navigation
Conference papers

Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs

K. S. Sesh Kumar 1, 2 Francis Bach 2, 1 
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider the problem of learning the structure of undirected graphical models with bounded treewidth, within the maximum likelihood framework. This is an NP-hard problem and most approaches consider local search techniques. In this paper, we pose it as a combinatorial optimization problem, which is then relaxed to a convex optimization problem that involves searching over the forest and hyperforest polytopes with special structures, independently. A supergradient method is used to solve the dual problem, with a run-time complexity of $O(k^3 n^{k+2} \log n)$ for each iteration, where $n$ is the number of variables and $k$ is a bound on the treewidth. We compare our approach to state-of-the-art methods on synthetic datasets and classical benchmarks, showing the gains of the novel convex approach.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : KS SeshKumar Connect in order to contact the contributor
Submitted on : Tuesday, December 11, 2012 - 6:43:15 PM
Last modification on : Thursday, March 17, 2022 - 10:08:44 AM
Long-term archiving on: : Tuesday, March 12, 2013 - 10:30:58 AM


Files produced by the author(s)


  • HAL Id : hal-00763921, version 1
  • ARXIV : 1212.2573



K. S. Sesh Kumar, Francis Bach. Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs. International Conference on Machine Learning, Jun 2013, Atlanta, United States. ⟨hal-00763921⟩



Record views


Files downloads