BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/259
DTSTAMP:20230914T125917Z
SUMMARY:Is Machine Learning Easy?
DESCRIPTION:Speaker: Sanjeev Arora (Princeton University\nDepartment of Com
 puter Science\nNew Jersey 08544\nUnited States of America)\n\nAbstract: \n
 Machine learning is a flourishing field with a plethora of algorithmic tec
 hniques. In almost all cases\, we have no provable guarantees on the perfo
 rmance of these algorithms/heuristics ---neither on their running time\, n
 or on the quality of solutions they return. In fact in many settings\, the
  underlying algorithmic problems are provably intractable (e.g.\, NP-hard 
 or worse)! This talk will argue that this seeming intractability may arise
  because many models used in machine learning are more general than they n
 eed to be.\n \nThis point will be illustrated using our recent results on
  designing provable algorithms for nonnegative matrix factorization (NMF)\
 , a well-known NP-hard problem that is popular in many areas of machine le
 arning. We present the first algorithms that can find factorizations of ra
 nk $r$ in polynomial time (in the matrix size\, not $r$).  We also introd
 uce a natural new subcase of NMF called "separable NMF" which we think is 
 the proper notion to use in many contexts. We give fully polynomial-time a
 lgorithms for separable NMF. We go on to use these algorithms for more gen
 eral problems involving learning of topic models (such as the wellknown La
 tent Dirichlet Allocation of Blei et al).\n \nJoint work with Rong Ge\, R
 avi Kannan\, Ankur Moitra.\n
URL:https://www.tcs.tifr.res.in/web/events/259
DTSTART;TZID=Asia/Kolkata:20120320T143000
DTEND;TZID=Asia/Kolkata:20120320T153000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR