Andrej Risteski will present his Generals on Oct. 14th at 10:30am in CS 302 The members of his committee are Sanjeev Arora, Moses Charikar, and David Blei. Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: Variational methods are a fairly commonly used tool in machine learning to solve inference problems of various kinds. The way they work is to reduce the problem of calculating some posterior probability to a suitable, usually non-convex, mathematical program. This is then solved using some form of alternating minimization. The vanilla form of this is expectation maximization (EM), and some more sophisticated flavors are variational Bayes, expectation propagation, etc. Unfortunately, all of these rarely come with any guarantees, and even in practice are prone to local optima. I will discuss some simple cases where these methods, along with suitable initialization, converge to the right value, mostly in the setting of topic models. Reading list: 0. Algorithm Design; Kleinberg, Tardos 1. Graphical Models, Exponential Families, and Variational Inference; Jordan, Wainwright [Chapters 1,2,3,4,7,9] 2. Latent Dirichlet Allocation; Blei, Ng, Jordan 3. Learning Topic Models - Going beyond SVD; Arora, Ge, Moitra 4. A Practical Algorithm for Topic Modeling with Provable Guarantees; Arora et al. 5. Computing a Nonnegative Matrix Factorization --- Provably; Arora, Ge, Kannan, Moitra 6. Complexity of Inference in Graphical Models; Chandresekaran, Srebro, Harsha 7. Understanding Belief Propagation and its Generalizations; Yedidia, Freeman, Weiss 8. Convexity Arguments for Efficient Minimization of the Bethe and Kikuchi Free Energies; Heskes 9. Convexifying the Bethe Free Energy; Meshi, Jaimovich, Globerson, Friedman 10. Counting independent sets up to the tree threshold; Weitz 11. Counting Independent Sets Using the Bethe Approximation; Chandrasekaran, Chertkov, Gamarnik, Shah, Shin 12. Clustering with Spectral Norm and the k-means Algorithm; Kumar, Kannan