Latent variable models, which assume that certain latent variables are absent from the observed data, have long been studied and found numerous applications in practice. Machine learning with latent variables not only improves predictive accuracies, but also plays a crucial role in enhancing interpretability of and discovering the principles underlying the data. This thesis is dedicated to developments of efficient and provable algorithms for learning a variety of latent variable models.

The first and second topics are concerned about learning mixture models with unlabeled samples, which is a powerful technique for modeling heterogeneous and complex data. Two concrete settings are considered: (1) mixtures of low-rank models, which incorporates low- complexity structural priors into high-dimensional mixed linear regression; (2) mixtures of linear dynamical systems, where model estimation is challenging especially due to the tem- poral dependence among time-series data. For both problems, we design principled and modular algorithms, and formally derive sample complexities under which reliable model estimation is guaranteed. Furthermore, empirical evidence confirms that our approaches have the potentials of generalizing to much broader settings, beyond those covered by our theoretical studies.

The third topic is concerned about ranking a set of items, which constitute a connected graph, based on pairwise comparisons on the edges. We focus on the classical Bradley-Terry- Luce model, which assumes that noisy measurements of pairwise comparisons are generated by a probabilistic model, based on certain unknown latent scores of the items. With a focus on latent score estimation, we first derive near-optimal entrywise errors for maximum likeli- hood estimation under general graph topologies, which is proved by observing a connection between statistical estimation and iterative optimization algorithms. Furthermore, we ini- tiate the study of ranking in graphs with locality, which arise in practice due to physical constraints; our contributions include (1) identifying conditions under which locality does not hurt, and (2) design novel divide-and-conquer algorithms that are guaranteed to achieve near-optimal errors even with the minimal sample complexities, while enjoying certain com- putational advantages.

Advisers:  Yuxin Chen and H. Vincent Poor

Zoom Link: https://princeton.zoom.us/j/8329071779