Learning discrete Markov random fields with nearly optimal runtime and sample complexity

Speaker: Adam Klivans

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

Public: Yes

Location: 32-G449

Event Type: Seminar

Room Description:

Host: Ankur Moitra

Contact: Nardos Abbay, nardos@csail.mit.edu

Relevant URL:

Speaker URL:

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Nardos Abbay Email at Wednesday, September 20, 2017 at 4:53 PM.