# Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs

2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - 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.
Type de document :
Communication dans un congrès
International Conference on Machine Learning, Jun 2013, Atlanta, United States. 2013
Domaine :

Littérature citée [31 références]

https://hal.inria.fr/hal-00763921
Contributeur : Ks Seshkumar <>
Soumis le : mardi 11 décembre 2012 - 18:43:15
Dernière modification le : jeudi 7 février 2019 - 16:56:42
Document(s) archivé(s) le : mardi 12 mars 2013 - 10:30:58

### Fichiers

convextjt_long.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• 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. 2013. 〈hal-00763921〉

### Métriques

Consultations de la notice

## 382

Téléchargements de fichiers