潜在变量模型假设某些潜在变量在观测数据中缺失,这种模型已经被长期研究,并在实践中找到了众多应用。使用潜在变量的机器学习不仅可以提高预测的准确性,而且在增强数据的可解释性以及发现数据背后的原理上起到了关键作用。本论文致力于为各种潜在变量模型的学习开发高效和可证明的算法。第一和第二个主题涉及使用无标签样本学习混合模型,这是一种对异质和复杂数据进行建模的强大技术。考虑了两种具体设置:(1) 低秩模型的混合,将低复杂性的结构先验整合到高维的混合线性回归中;(2) 线性动态系统的混合,由于时间序列数据之间的时间依赖性,模型估计尤为具有挑战性。对于这两个问题,我们设计了有原则的和模块化的算法,并正式导出了可靠模型估计所需的样本复杂度。此外,实证证据证实,我们的方法有潜力推广到更广泛的设置,超出我们的理论研究所涵盖的范围。第三个主题涉及根据边缘上的成对比较对一组项目进行排名,这些项目构成了一个连接图。我们关注经典的Bradley-Terry-Luce模型,该模型假设成对比较的噪声测量是基于项目的某些未知潜在分数生成的。在关注潜在得分估计的前提下,我们首先导出了在一般图形拓扑下最大似然估计的接近最优的逐项错误,这是通过观察统计估计和迭代优化算法之间的关联来证明的。此外,我们开始研究具有局部性的图形中的排名,这在实践中由于物理约束而出现;我们的贡献包括(1)确定局部性不受影响的条件,以及(2)设计新颖的分而治之算法,即使在最小的样本复杂度下也能保证达到接近最优的错误,同时享有某些计算优势。