Learning discrete Markov random fields with nearly optimal runtime and sample complexity
Date: Tuesday, September 26, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Event Type: Seminar
Host: Ankur Moitra
Contact: Nardos Abbay, firstname.lastname@example.org
TALK: Learning discrete Markov random fields with nearly optimal runtime and sample complexity
Abstract: We give an algorithm for learning the structure of an undirected graphical model over a binary alphabet that has nearly optimal runtime and sample complexity. We make no assumptions on the structure of the graph. For Ising models, this subsumes and improves on all prior work. For higher-order MRFs, these are the first results of their kind.
Our approach is new and uses a multiplicative-weight update algorithm. Our algorithm-- Sparsitron-- is easy to implement (has only one parameter) and holds in the online setting. It also gives the first provably efficient solution to the problem of learning sparse Generalized Linear Models (GLMs).
Joint work with Raghu Meka
Created by Nardos Abbay at Wednesday, September 20, 2017 at 4:53 PM.