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

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