【博士论文】机器学习中部分非凸和随机优化算法研究

机器学习中部分非凸和随机优化算法研究

机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算 法复杂度理论等多门学科。算法理论与应用是机器学习中最为重要的核心之一。其中一阶优化算法因其简单有效性，而被广泛研究与应用。另一方面由于近年来 数据规模的不断增大，数据集的规模使得二阶或更高阶的算法应用受阻。这使得 一阶算法进一步成为机器学习的研究重点。随着机器学习中问题模型的不断扩张， 例如深度学习，非凸问题和模型也激发了学者们广泛的研究兴趣。这使得研究非 凸算法显得更加急迫。而且由于数据集的庞大性，确定算法难以逃出鞍点，因此 随机算法受到了史无前例的关注。本文主要结果可以归纳如下：

一、研究了三种 ADMM 算法。第一个 ADMM 的工作是关于一般的 ADMM 收 敛性分析统一框架。在此框架下，很多现有的 ADMM 收敛性分析可以归纳进该 框架。除了现有的 ADMM 算法，根据统一框架还能够设计出新的 ADMM 算法。第二个和第三个 ADMM 都是针对结构非凸优化问题提出的：一个是针对泛 ℓq 正 则化约束优化问题，而另一个是针对 ℓ1−2 正则化约束优化。给出了后面两种非凸 ADMM 算法的收敛性分析，所得到的结果可以指导用户选择合适的超参数。

二、研究了两种一阶优化领域常用的非精确算法。第一种是非精确的加速算 法。相较于之前的研究，该算法的假设更为真实。而且还囊括了一大类随机噪声 的情况，使得算法更为实用。而机器学习中的一阶催化剂算法由于是该加速算法 带上了随机噪声，因此可以看做本算法的特例。在第二部分给出了非精确非凸算 法的收敛性框架理论。可以被广泛应用到各种一阶非凸算法。

三、证明了在有界和无界延迟以及随机和确定性块选择下异步并行梯度下降法 的收敛结果。这些结果不需要迄今为止绝大多数其他工作中出现的独立性假设。这是由于本文使用了 Lyapunov 函数技术，可直接处理延迟，而不是像之前的工作 一样仅仅将它们建模为噪声。

四、分析了马尔可夫链随机梯度下降法，其中样本采用了某个马尔可夫链的轨迹。主要贡献之一是给出了马尔可夫链随机梯度下降法的在凸情况下的非遍历收 敛分析。结果然后扩展到不精确的格式。这种分析使得能够建立不可逆有限状态 马尔可夫链和非凸最小化问题的收敛性。这样的结果适用于不知道具体的概率分 布，但可以通过马尔可夫链进行采样的情形。