Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Learning Graphical Models Using Multiplicative Weights   We give a simple, multiplicative-weight update algorithm for learning
undirected graphical models or Markov random fields (MRFs). The approach is
new, and for the well-studied case of Ising models or Boltzmann machines, we
obtain an algorithm that uses a nearly optimal number of samples and has
quadratic running time (up to logarithmic factors), subsuming and improving on
all prior work. Additionally, we give the first efficient algorithm for
learning Ising models over general alphabets.
  Our main application is an algorithm for learning the structure of t-wise
MRFs with nearly-optimal sample complexity (up to polynomial losses in
necessary terms that depend on the weights) and running time that is
$n^{O(t)}$. In addition, given $n^{O(t)}$ samples, we can also learn the
parameters of the model and generate a hypothesis that is close in statistical
distance to the true MRF. All prior work runs in time $n^{\Omega(d)}$ for
graphs of bounded degree d and does not generate a hypothesis close in
statistical distance even for t=3. We observe that our runtime has the correct
dependence on n and t assuming the hardness of learning sparse parities with
noise.
  Our algorithm--the Sparsitron-- is easy to implement (has only one parameter)
and holds in the on-line setting. Its analysis applies a regret bound from
Freund and Schapire's classic Hedge algorithm. It also gives the first solution
to the problem of learning sparse Generalized Linear Models (GLMs).

20
The categories of this paper are: acc-phys
23
The categories of this paper are: solv-int
3
The categories of this paper are: physics
34
The categories of this paper are: chem-ph
19
The categories of this paper are: eess
30
The categories of this paper are: q-alg
10
The categories of this paper are: q-bio
15
The categories of this paper are: nucl-ex
8
The categories of this paper are: hep-ex
13
The categories of this paper are: quant-ph
27
The categories of this paper are: comp-gas
32
The categories of this paper are: atom-ph
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th
18
The categories of this paper are: econ
11
The categories of this paper are: hep-lat