[talks] R Ge preFPO

Melissa M. Lawson mml at CS.Princeton.EDU
Wed Mar 6 13:38:26 EST 2013

Rong Ge will present his preFPO on Monday March 11 at Noon in Room 401 (note room!) 
The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Sham 
Kakade (MSR New England), readers; Mark Braverman and Zeev Dvir, nonreaders. 
Everyone is invited to attend his talk. His abstract follows below. 
Title: Provable Algorithms for Machine Learning 

Many tasks in machine learning are computationally intractable. Nevertheless, researchers have developed 
heuristic algorithms that successfully solve these problems in practice. This phenomena can be explained using 
average case complexity. However, in many situations the details supporting this explanation are still missing: what 
properties of the input make it possible to be solved efficiently? What is the chance that real-life inputs satisfy 
these properties and how robust is the algorithm if they don't? 

In this talk I use topic modeling as an example to show our attempts of answering these problems. The first 
part of the talk gives a new algorithm for learning topic models with provable guarantees. This algorithm 
relies on a reasonable simplifying assumption, and runs 20 times faster than existing software like mallet 
with comparable output quality. The second part of the talk gives a new analysis for method of moments 
algorithms (AHK12, AFHKL12) using tensor decomposition. The new algorithm has a better perturbation 
analysis and can therefore tolerate more modeling error. 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20130306/b591695d/attachment.html>

More information about the talks mailing list