We study computational and sample complexity of parameter and structure
learning in graphical models. Our main result shows that the class of factor
graphs with bounded factor size and bounded connectivity can be learned in
polynomial time and polynomial number of samples, assuming that the data is
generated by a network in this class. This result covers both parameter
estimation for a known network structure and structure learning. It implies
as a corollary that we can learn factor graphs for both Bayesian networks
and Markov networks of bounded degree, in polynomial time and sample
complexity. Unlike maximum likelihood estimation, our method does not
require inference in the underlying network, and so applies to networks
where inference is intractable. We also show that the error of our learned
model degrades gracefully when the generating distribution is not a member
of the target class of networks.