Skip to Main content Skip to Navigation

# Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs

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.
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [31 references]

https://hal.inria.fr/hal-00763921
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

convextjt_long.pdf
Files produced by the author(s)

### Identifiers

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

### Citation

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