Andrej Risteski

I am an Assistant Professor at the Machine Learning Department in Carnegie Mellon University. I received my PhD in the Computer Science Department at Princeton University under the advisement of Sanjeev Arora. My work lies in the intersection of machine learning and theoretical computer science. The broad goal of my research is theoretically understanding statistical and algorithmic phenomena and problems arising in modern machine learning.

Papers

(In alphabetical order, following the tradition in theoretical computer science)

Understanding representations in supervised and unsupervised learning

• Benefits of Overparameterization in Single-Layer Latent Variable Generative Models. With Rares Buhai, Yoni Halpern and David Sontag. Manuscript 2019.
• Approximability of Discriminators Implies Diversity in GANs. With Yu Bai and Tengyu Ma. ICLR 2019.
• Representational Power of ReLU Networks and Polynomial Kernels: Beyond Worst-Case Analysis. With Frederic Koehler. ICLR 2019.
• Do GANs learn the distribution? Some theory and empirics. With Sanjeev Arora and Yi Zhang. ICLR 2018
• Linear algebraic structure of word senses, with applications to polysemy. With Sanjeev Arora, Yuanzhi Li, Yingyu Liang and Tengyu Ma. Transactions of the Association for Computat ional Linguistics (TACL), 2018
• Automated WordNet Construction Using Word Embeddings. With Mikhail Khodak, Christiane Fellbaum, Sanjeev Arora. EACL Workshop on Sense, Concept and Entity Representation s and their Applications, 2017
• On the ability of neural nets to express distributions. With Holden Lee, Rong Ge, Tengyu Ma, Sanjeev Arora. COLT 2017
• RAND-WALK: a latent variable model approach to word embeddings. With Sanjeev Arora, Yuanzhi Li, Yingyu Liang and Tengyu Ma. Transactions of the Association for Computational Linguistics (TACL), 2016

Provable algorithms for learning and inference in Bayesian models

• Diffusing along manifolds of local optima via Langevin dynamics. With Ankur Moitra. Manuscript 2019, coming soon!
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo. With Rong Ge and Holden Lee. NeurIPS 2018
• Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective. With Vishesh Jain and Frederik Koehler. STOC 2019.
• Provable learning of noisy-or networks. With Sanjeev Arora, Rong Ge, and Tengyu Ma. STOC 2017
• How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods. COLT 2016, long talk
• Approximate maximum entropy principles via Goemans-Williamson with applications to provable variational methods. With Yuanzhi Li. NeurIPS 2016
• Non-negative matrix factorization using a decode-and-update approach. With Yuanzhi Li and Yingyu Liang. NeurIPS 2016
• Recovery guarantee of weighted low-rank approximation via alternating minimization. With Yuanzhi Li and Yingyu Liang. ICML 2016
• On some provably correct cases of variational inference for topic models. With Pranjal Awasthi. NeurIPS 2015, Spotlight

Computational issues around online and improper learning

• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion. With Dylan J. Foster. COLT 2019
• Tight algorithms and lower bounds for approximately convex optimization. With Yuanzhi Li. NeurI PS 2016
• Label optimal regret bounds for online local learning. With Pranjal Awasthi, Moses Charikar and Kevin A. Lai. COLT 2015

Talks

• Diffusing along manifolds of local optima via Langevin dynamics
• Microsoft Research New England, 03/19
• Mean-field approximation and variational methods via convex relaxations
• Harvard Physics and Computation Seminar, 10/18
• MIT Seminar on Stochastic Processes, 11/18
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• MIT Algorithms and Complexity Seminar, 11/01/17
• Provable algorithms for learning noisy-OR networks
• STOC (Montreal, 2017)
• Theoretical aspects of representation learning
• Simons Institute for the Theory of Computing, 03/27/17
• New techniques for learning and inference in probabilistic graphical models
• MIT Stochastics and Statistics Seminar, 09/08/17
• Microsoft Research Redmond, 02/08/17
• How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
• Stanford Theory Seminar, 02/02/17
• Los Alamos National Laboratory, 11/07/16
• Rutgers University, 10/19/16
• COLT (New York City, 2016) [Video]
• On some provably correct cases of variational inference for topic models
• NeurIPS (Montreal, 2015) [Video, talk starts circa 11:45]
• Random walks on context spaces: towards an explanation of the mysteries of semantic word embeddings
• China Theory Week (Jiao Tong University, Shanghai, 2015)
• Label optimal regret bounds for online local learning
• COLT (Paris, 2015) [Video]

Blog posts about my work

• On approximating partition functions via variational methods.
• Theoretical limitations of modern GAN architectures.
• Formalizations of representation learning.
• Word embeddings.

Teaching

• Instructor for 18.200A (Principles of Discrete and Applied Mathematics) at MIT: Fall 2017/18 and Fall 2018/19
• Teaching assistant for COS445 (Networks, Economics and Computing) at Princeton: Spring 2014
• Teaching assistant for COS451 (Computational Geometry) at Princeton: Fall 2013/14
• Grader for COS433 (Cryptography) at Princeton: Fall 2011/12

Contact

• The easiest way to reach me is email. My address is lastname at mit.edu