随着机器学习技术深入研究,高维数据问题逐步引起学术界和产业界的广泛兴趣,机器学习模型、求解算法在高维数据上面临着新的挑战。研究人员通过增加正则项,改进传统的机器学习模型,形成各种正则化机器学习模型。正则化机器学习将隐藏在变量之间的结构信息表达为正则函数。正则函数能够有效利用特定的结构信息,增强传统机器学习模型的表达能力,提高传统机器学习模型的性能,同时,因其具有稀疏引导等作用使其在模型应用时也带来潜在的计算优势,这使得正则化机器学习在以高分辨图像处理、生物工程,以及信息检索等代表的实际场景中得到广泛应用。实际应用中,大规模正则化机器学习问题的求解面临着数据规模大、模型维度高,以及不易求解等巨大挑战。数据规模大,主要是指数据样本数量巨大,而且,数据的规模还随时间而不断累积。模型维度高,主要是指模型中变量的维度高,并随着应用需求的出现而不断增加。模型不易求解主要是指模型目标函数具有非平滑、非线性、非凸,以及不可导等难于计算的性质,同时,由于组合正则函数的引入使得传统求解算法的子问题往往不再具有解析解而加剧了求解难度。本论文主要对上述问题开展研究,寻找求解该类问题的有效方法,取得的主要成果与创新工作概括如下:1.面向正则化机器学习大规模数据集泛化凸正则的快速随机算法(SPDHG)首先,论文考虑在大规模数据集下求解具有泛化凸正则函数的正则化机器学习问题,其中,泛化正则项与经验风险误差函数通过线性函数组成学习问题的凸目标函数。这是在机器学习中广泛存在的一类优化问题,如:具有稀疏引导的SVM、Lasso,以及具有图结构引导正则的最小化问题。由于附加的线性组合的存在,正则项相关的近点映射的解析解往往不存在,这使得这类问题不易求解。一般使用ADMM类算法来求解这类问题,需要迭代求解原对偶变量及拉格朗日乘子相关的子问题。本文通过观察发现,在这类问题中,部分正则项的结构可以允许将原问题重新形式化为一个凸凹鞍点问题,进一步使用原对偶混合梯度方法(PDHG)求解。然而,在实际应用中,原对偶混合梯度方法需要计算目标函数的全梯度,这使得该方法在数据密集型应用中可能失效。特别是在数据样本数量相对较大时,求解问题的空间开销和时间开销往往都变得不可接受。为解决数据样本量增大带来的难题,本文提出随机原对偶混合梯度方法(SPDHG),并从理论上分析提出算法在目标函数为一般凸和强凸的情况下,在采用均匀和非均匀迭代策略时,算法所分别具有的收敛速率。当目标函数为一般凸函数时,论文的算法预期以0(1/(?))的速率收敛。当目标函数为强凸函数时,在均匀迭代策略下,论文的算法预期以O(log(t)/t)的速率收敛;在非均匀迭代策略下,论文的算法预期以O(1/t)的速率收敛。提出的SPDHG算法较现有的ADMM类算法具有更低的时间开销,在多个数据集上的数值实验结果表明本文提出的SPDHG算法超越了对比算法。2.面向正则化机器学习大规模数据集具有线性等式约束非平滑凸正则的随机算法(SEGADM)然后,论文尝试在大规模数据集下求解具有线性等式约束和非平滑正则函数的复杂正则化机器学习问题,这类问题可形式化为由两个可能非平滑凸函数加和构成的凸目标函数,其中,一个函数是随机复合函数的期望,另一个函数具有相对易于求解的近点映射。这类优化模型涵盖了机器学习中很大一部分重要的应用,例如:邻近趋同逻辑回归,以及具有图结构引导正则的最小化问题。本文提出基于外梯度的随机变方向方法(SEGADM)来求解,SEGADM算法结合外梯度方法和随机梯度算法,获得了外梯度方法带来的求解性能上的稳定性,同时还具有处理大规模问题的能力。论文从理论上分析了 SEGADM在均匀和非均匀迭代更新时的收敛性质。采用均匀迭代更新策略时,SEGADM算法在目标函数一般凸和强凸的情况下分别具有0(1/(?))和O(log(t)/t)的收敛速率。在采用非均匀更新策略时,SEGADM算法在目标函数强凸的情况下能达到O(1/t)的预期收敛速率。3.面向正则化机器学习高维变量泛化非凸正则的自适应快速算法(AdaL-ADMM)进一步,论文考虑在高维变量下具有优良统计特性的泛化非凸正则函数的正则化机器学习问题,这类问题可形式化为经验风险函数与泛化非凸正则函数通过线性组合形成的非凸问题。相比于凸正则项,在统计特性上,非凸正则项在机器学习中能得到更好的统计性质。然而,在计算过程中,与非凸正则项相对应的近点映射往往不易获得,特别是加入非凸正则项之后的线性组合的存在使求解更加困难。幸运的是,问题的结构允许论文引入附属变量,然后将原问题重新形式化为具有线性约束的优化问题。重新形式化之后的问题可以通过线性化变方向乘子法(LADMM)求解。尽管,LADMM在实际中显示出高效的性能,但将LADMM用于求解非凸正则优化时是否收敛,仍然没有一个明确的结论。论文首先对LADMM求解非凸正则优化时的收敛性进行理论分析,分析涵盖了一大类非凸正则函数。进一步,本文提出带有线性搜索准则的自适应线性化变方向乘子法(AdaLADMM)算法,并给出理论上的收敛性分析。在不同的数据集上的数值实验结果表明了提出算法的有效性。4.面向正则化机器学习超面向高维变量具有线性不等式约束非平滑非凸正则的并行算法(PPF-BCD)最后,论文考虑在超高维变量下非凸非平滑的复杂正则化机器学习问题,许多有趣而重要的机器学习模型都符合该优化问题的形式。然而,当前还缺少用于该类问题的有效一阶算法。这主要是由于两方面的原因,一方面是求解该问题的计算复杂度与模型的维度成正比,在数据驱动的应用中这会导致巨大的计算开销;另一方面是用一阶算法求解具有不等式约束的非凸非平滑的目标函数时,其收敛性难以得到保证。论文结合具有全局优化解提升的路径跟随算法(Path-Following)和在大规模优化问题中具有突出表现的块坐标下降法(BCD),并应用随机更新策略提出并行路径跟随块坐标下降法(PPF-BCD)。论文分析PPF-BCD算法在循环和随机块变量选择策略下的收敛性质。数值实验结果表明提出的PPF-BCD算法在串行版本和并行版本中都取得优良的性能结果。值得一提的是,在并行版本上,提出的PPF-BCD算法达到近乎线性的加速比。