On Learning Discrete Graphical Models using Group-Sparse Regularization

摘要: We study the problem of learning graph structure associated with a general discrete graphical models (each variable can take any m > 1 values, clique factors have maximum size c ≥ 2) from samples, under high-dimensional scaling where number variables p could be larger than samples n. provide quantitative consistency analysis procedure based on node-wise multi-class logistic regression group-sparse regularization. first consider m-ary pairwise – each factor depends at most two variables. show that when scale as n K(m − 1) 2 d log((m −1) (p −1))– is degree and K fixed constant succeeds in recovering high probability. For c-way factors, natural multi-way extension method quickly becomes very computationally complex. So we studied effectiveness using even while true model has higher order factors. Surprisingly, slightly more stringent conditions, still recovers structure, 3 ).