Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Seminar on Thursday

Shashwat Silas silas at
Mon Oct 23 15:30:18 PDT 2017

Hi All,

There will be a theory seminar on Thursday at 415pm in Gates 463A. Hope you can make it!

Raghu Meka (UCLA)
Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity.
We give an algorithm for learning the structure of an undirected graphical model that has essentially optimal sample complexity and running time. We make no assumptions on the structure of the graphical model. For Ising models, this subsumes and improves on all prior work. For general t-wise 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 Adam Klivans.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list