随机邻近牛顿型交替极小化算法

Stochastic Proximity Newtonian Alternating Miniaturization Algorithm

摘要: 本文研究一类大规模有限和形式的非凸非光滑复合优化问题，其目标函数为适当下半连续凸函数与连续可微函数(有限和形式)之和。邻近交替线性极小化算法在求解这类问题上有显著优势，但考虑到针对大规模优化问题，该算法需在每一迭代计算全梯度，成本较高，故本文将目标函数光滑部分的随机梯度引入到已有算法，以降低算法的计算成本。此外，考虑到一阶算法在求解病态问题时速度较慢，故本文在算法中引入目标函数的二阶信息，提出了一种随机邻近牛顿型交替极小化算法。在适当的步长边界的基础上，我们建立了算法在期望意义下的全局收敛性。本文提出的随机邻近牛顿型交替极小化算法，不仅提升了算法在机器学习、统计学和图像处理等领域实际应用中的效率和实用性，也为非凸非光滑优化领域的理论发展提供了新的理论基础和算法框架。

Abstract: This article investigates a class of large-scale finite and structured nonconvex nonsmooth composite optimization problems, where the objective function is the sum of an appropriately lower semicontinuous convex function and a continuous differentiable function (finite and structured). The alternating linear minimization algorithm has significant advantages in solving such problems. However, considering the large-scale optimization problems, this algorithm requires computing the full gradient at each iteration, which is costly. Therefore, this article introduces the stochastic gradient of the smooth part of the objective function into the existing algorithm to reduce the computational cost. Additionally, considering that first-order algorithms are slow in solving ill-conditioned problems, this article incorporates the second-order information of the objective function into the algorithm and proposes a stochastic proximal Newton-type alternating minimization algorithm. Based on appropriate step size bounds, we establish the global convergence of the algorithm in the expected sense. The stochastic neighborhood Newton-type alternating minimization algorithm proposed in this paper not only improves the efficiency and practicability of the algorithm in practical applications in the fields of machine learning, statistics and image processing, but also provides a new theoretical foundation and algorithmic framework for the theoretical development in the field of nonconvex nonsmooth optimization.