一类非光滑随机优化问题的随机二阶算法

The nonsmooth stochastic optimization problem, that involving smooth expectation function and nonsmooth convex terms in the objective, frequently arises in the fields of machine learning and statistics. Stochastic first order algorithms have been taken the stage as the primary method for solving this problem due to the affordable computational costs. To accelerate the convergence, stochastic second order algorithms have gained more and more attention. However, the research on stochastic second order algorithms is quite limited in literature so far. This project will substantially study the stochastic second order algorithms for solving nonsmooth stochastic optimization problem. Specifically, the research includes: propose a hybrid stochastic second order algorithm by combining semismooth subsampled Newton steps with globalization technique; study the semismooth Newton-Sketch algorithm based on matrix sketching; develop the stochastic smoothing Newton algorithms with line search. In particular, we will analyze the global and local convergence of these algorithms in both convex and nonconvex settings, and study the numerical performance and the applications in machine learning. It is expected that the proposed algorithms are more robust and effective than the existing stochastic first order algorithms. We hope to make a significant contribution in the development of stochastic optimization algorithms and furtherly to solve some real-world problems efficiently in machine learning.

极小化一个光滑期望函数和一个非光滑凸函数之和的非光滑随机优化问题是机器学习和统计领域中最重要的模型之一。随机优化算法是求解这类问题最有效最常用的算法，其中随机一阶算法的研究已经取得了很重要的进展。为了得到收敛速度更快的数值算法，随机二阶算法的研究引起了学者们越来越多的关注和兴趣，但是目前相关研究成果还不是很多。本项目将对非光滑随机优化问题的随机二阶算法进行深入的研究，研究内容包括：半光滑子采样牛顿方法和全局化技巧相结合的随机二阶算法；基于矩阵素描技巧的半光滑牛顿-素描算法；带线搜索的随机光滑化牛顿算法。其中我们将重点研究这些算法在凸和非凸两种情况下的全局收敛性和局部收敛速度，以及这些算法的数值实现和在机器学习中的应用。预期的研究成果具有重要的理论意义和应用价值，不但可推进随机优化算法的理论研究进展，并且可为机器学习中的一些重要应用提供高效算法。

本项目的主要研究内容为求解随机复合优化问题的随机二阶算法，包括这些算法在凸和非凸情况下的全局收敛性和局部收敛速度，以及这些算法的数值实现和应用。本项目取得的主要成果和进展如下: 1)构造了求解随机复合优化问题的随机半光滑牛顿法，系统证明了随机半光滑牛顿法的概率1意义下的全局收敛性。数值试验结果表明，相较于目前流行的随机一阶算法，我们构造的算法有明显的优势。2)系统研究了随机非光滑牛顿算法的局部收敛性。证明了，在最优解的附近该算法在很大概率下会变成一个单纯的随机半光滑牛顿步，通过适当增大随机梯度和随机海森阵的样本大小，从而达到超线性甚至二阶的局部收敛速度。3)提出了一类基于模型的随机邻近乘子法求解带期望约束的随机优化问题，它可以看作是带邻近项的随机增广拉格朗日型算法。在一定的假设条件下，在期望意义下建立了关于目标函数下降量和约束违反度的次线性收敛速度。4)随机一阶算法的收敛性分析通常假设目标函数的梯度是李普希兹连续的以及随机梯度的方差是一致有界的。我们提出了一个统一的收敛性分析框架，在不需要这两个常见假设的前提下，分析了随机临近梯度法和随机外梯度法的概率1意义下的全局收敛性和期望意义下的收敛速度。5)考虑了一类带有非凸不等式约束的非凸在线优化问题，提出了一个带有二阶近似的临近乘子法。详细分析了该算法的违反KKT条件的后悔度。6)提出了一类求解随机优化问题的无导数无投影随机Frank-Wolfe算法。系统分析了该算法的收敛性，包括约束随机优化问题和随机复合优化问题的求解，以及在凸和非凸两种情况下的全局收敛性和收敛速度。