机器学习中的一阶优化算法收敛性研究

摘要

由于具有对目标函数的假设较弱，收敛速度快和易于实现等特点，一阶优化算法被广泛应用于求解机器学习模型参数。然而传统的一阶优化算法在实现时会遇到各种各样的问题。一方面，随着数据规模的爆发式增长和深度神经网络等机器学习模型中参数规模不断增加，传统的确定性数值优化算法有计算量过大的问题。另一方面，数值优化领域中讨论的一阶算法分析往往基于最坏计算复杂度。由于实际当中最坏情况往往不会出现，实际中传统的随机梯度下降等方法在求解过程中可能浪费大量的迭代。为此，机器学习领域的研究者们提出了ADAGRAD等针对凸问题的随机自适应算法，这些方法通过利用随机梯度的历史信息来自适应地更新步长，在实际应用中通常有更好的性能。但是，目前大量的机器学习任务（如深度神经网络）的目标函数为非凸函数，在非凸情况下大部分上述算法在理论层面尚缺乏收敛性保证。综上，研究实用、收敛速度更快的优化算法是机器学习理论中的一个重要挑战。 为此，本文重点研究能同时提升理论收敛速度和实际表现的一阶优化算法，具体包括四个方面:1)研究了KL不等式在非凸矩阵秩最小化问题上的应用，证明了当日标函数满足KL性质时关于奇异值的非凸规范化项可被传统的近邻映射算法求解，给出了近邻映射的闭形式，并证明当函数的可微部分的梯度是利普斯西连续时，算法有O(1/ε)的渐进计算复杂度;2）提出了求解满足强凸和局部误差界条件的问题的强自适应随机优化算法(SADAGRAD)，证明了该算法具有关于随机次梯度范数的自适应计算复杂度，且复杂度在最坏情况下分别为O(1/ε)和O（1/ε2（1-α），其中α∈[0，1）为函数的局部误差界常数。当随机梯度稀疏时，SADAGRAD可以有效降低计算复杂度，并减少优化变量规模对算法效率的影响;3)提出了阶段化的一阶优化算法框架，该算法框架通过把求解非凸问题转化为递归求解凸问题，将自适应算法等成熟的凸优化方法扩展到非凸优化当中。可以证明在该算法框架下，大量成熟的凸优化算法求解非凸问题时可以达到目前最优的收敛速度;4）最后，针对非凸问题提出了阶段化加速的方差减小随机梯度下降法(Stagewise-Katyusha)，当μ-weakly convex的目标函数由n个L-smooth的函数和一些相对简单的项组成时，该算法在条件数L/μ≥4n/3时可以达到算法复杂度的下界，且比在该条件下取得最优计算复杂度的其它算法内存开销更低。

目录

声明

摘要

第一章绪论

1．1基本问题描述

1．2本文贡献

第2章背景介绍

2．1 基本性质和标记定义

2．1．1计算复杂度和收敛速度

2．1．2标记定义

2．2相关工作

2．2．1 误差界和Kurdyka(L)ojasiewicz性质

2．2．2 随机梯度下降法和自适应算法简介

2．2．3非凸优化算法简介

2．2．4方差减小的随机一阶算法

第3章基于迭代阈值收缩的非凸矩阵秩最小化算法

3．1 矩阵秩最小化问题和非凸规范化项

3．2重加权的非凸奇异值规范化项收敛结果分析

3．3多个矩阵的秩最小化问题

3．4实际实现中的问题和解决方案

3．5矩阵补全问题中的算法验证

3．5．1人造数据集

3．5．2图像数据集

3．5．3多个域的推荐问题

第4章 SADAGRAD:强自适应的随机梯度算法

4．1 二阶增长条件下的强自适应的随机次梯度算法

4．2 SADAGRAD算法基于近邻算法的变种

4．3 实际应用中的SADAGRAD算法变种

4．4 SADAGRAD算法在满足局部误差界假设下的扩展

4．5实验验证

第5章非凸优化中统一的阶段化学习方法框架

5．1阶段化优化算法框架

5．2具体的阶段化优化算法

5．2．1阶段化的随机梯度下降法

5．2．2阶段化的动量随机梯度法

5．2．3阶段化的自适应算法

5．3实验验证

第6章Stagewise-Katyusha:阶段化的加速的方差减小随机梯度下降法

6．1 Stagewise-Katyusha算法和假设

6．2收敛性分析

第7章总结

参考文献

附录

致谢

在读期间发表的学术论文与取得的研究成果