【MIT博士论文】大规模机器学习算法：效率、估计误差及其拓展

优化算法是机器学习和统计推断的基石。随着大规模数据集的出现，计算挑战日益增加，迫使人们追求更高效的算法。现代优化技术通常针对特定的机器学习问题进行定制，这些方法利用问题的独特结构特征，使其比当前应用于这些问题的方法效率更高。另一个关键方面是理解所得到估计量的估计精度。在某些情况下，尽管在训练集上实现精确优化可能不切实际，但某些简单而有效的启发式方法在适当的统计框架内可以表现出令人赞叹的估计精度。 在本文中，我们从优化和统计的角度研究了几种大规模算法。第2章和第3章研究了两种针对结构约束的连续优化算法。第2章集中讨论了具有圆柱形约束的无界约束的一种广义Frank-Wolfe方法。第3章则研究了具有少量极点的多面体约束的类似坐标下降（CD）方法。这两种方法由于对问题结构的敏感性而表现出最先进的性能。 第4章研究了一种带有解释器-响应对之间可能存在不匹配的线性回归变体。我们研究了一种简单且高效的启发式方法，并在统计环境中对其估计误差进行了严格分析。 第5章和第6章研究了两种决策树算法。第5章研究了最优决策树的计算，并引入了一种新的分支定界方法，用于具有一般连续特征的最优决策树。第6章则转向在足够杂质减少条件下对CART算法的分析。我们为满足该条件的信号函数证明了严格的误差界，并讨论了一些满足该条件的函数类。 第7章研究了一种具有形状约束的密度估计问题。我们提出了一种立方-牛顿法框架用于计算，并研究了有限混合的逼近性质。