【MIT博士论文】机器学习应用中稀疏和低秩矩阵优化的进展

在运筹学、机器学习和统计学的众多基本问题中，自然地表现为稀疏性或秩约束的优化问题。稀疏解因其可解释性和存储效率而备受青睐。此外，在机器学习环境中，稀疏解通常展现出更好的模型泛化能力，并在高维数据集中自然地诠释为特征提取的过程。另一方面，由于矩阵的秩等价于其奇异值向量的基数，因此秩可以被理解为矩阵的稀疏性推广。相应地，低秩解继承了稀疏解的类似优点，同时具备更为灵活的建模能力。不幸的是，对基数和秩的优化是非凸且一般为NP难的，这使得我们在很大程度上依赖于凸松弛和启发式方法，但这些方法往往只能提供次优解。本论文推动了稀疏和低秩矩阵优化的理论和应用，重点关注统计学和机器学习中的问题。我们通过利用混合整数和混合投影优化的技术，开发了面向基数和秩约束问题的算法方法。所提出的算法优于现有的凸松弛和启发式方法。我们的严谨分析和实验证明旨在为优化的理论基础做出贡献，同时开发用于统计学和机器学习复杂挑战的实用工具。第二章研究了稀疏加低秩矩阵分解问题。我们提出了一种交替最小化算法，可计算高质量的可行解，性能超越基准方法，并可在几分钟内扩展到维度为n=10000n = 10000n=10000 的情况。此外，我们设计了一种定制的分支定界算法，可在几分钟内全局求解维度达n=25n = 25n=25 的问题实例。第三章探讨了压缩感知问题，我们提出了一种定制的分支定界算法，可以计算全局最优解。与最新的基准方法相比，我们的方法在合成数据上获得的解平均稀疏性提升6.22%，在真实的心电图（ECG）数据上稀疏性提升9.95%。此外，当用作多标签学习算法的一部分时，我们的方法在性能上也优于基准方法。第四章研究了学习一个能够预测完全观测的辅助信息的部分观测矩阵的问题，这扩展了矩阵补全问题的一个重要泛化。我们将该问题重新表述为一个混合投影优化问题，并提出了交替方向乘子法（ADMM）算法，能够在不到一分钟内解决行数为n=10000n = 10000n=10000、列数为m=10000m = 10000m=10000 的问题。在大规模真实数据上，我们的算法比基准方法的样本外误差低67%，执行时间减少97%。