重庆师范大学数学科学学院，重庆

收稿日期：2023年4月12日；录用日期：2023年5月15日；发布日期：2023年5月22日

摘要

许多机器学习问题，如对抗学习、强化学习和图像处理的一些典型问题大都可归结为极小极大优化问题。因此，极小极大优化问题最近已经成为最优化领域与机器学习交叉领域中的一个重要研究前沿和热点，吸引了众多学者的关注和研究。如何有效求解极小极大优化问题，是优化领域及应用中的关键科学问题之一。考虑到极小极大三次正则化牛顿法中，三次正则化项的系数是相对固定的，会影响算法的收敛性。本文首先针对非凸–强凹极小极大优化问题，采用信赖域半径的选取策略，提出了一类自适应极小极大三次正则化牛顿法。然后证得了算法的迭代复杂度为 $\mathcal{O}\left(T^{-1/3}\right)$ 。最后，通过一类对抗攻击神经网络问题，验证了该算法的有效性。

关键词

极小极大优化问题，三次正则化牛顿法，非凸优化，自适应性，复杂度分析

One Class of Cubic Regularized Newton Methods for Min-Max Optimization Problems

Ruicheng Gao

School of Mathematical Sciences, Chongqing Normal University, Chongqing

Received: Apr. 12^th, 2023; accepted: May 15^th, 2023; published: May 22^nd, 2023

ABSTRACT

Many machine learning problems, such as adversarial learning, reinforcement learning and image processing, can be reduced to min-max optimization problem. Therefore, min-max optimization has recently become an important research frontier and hot spot in the intersection of optimization and machine learning, attracting the attention and research of many scholars. How to effectively solve min-max problem is one of the key scientific problems in optimization field and application. Considering that the coefficient of cubic regularization term in min-max cubic regularization Newton method is relatively fixed, it will affect the convergence of the algorithm. In this paper, a class of adaptive min-max cubic regularization Newton method is proposed based on the selection strategy of the radius of the trust region for the nonconvex-strongly concave minimax optimization problem. Then, the iterative complexity of the algorithm is bounded by $\mathcal{O}\left(T^{-1/3}\right)$ . Finally, the effectiveness of the proposed algorithm is verified by a class of adversarial attack neural network problems.

Keywords:Min-Max Optimization Problem, Cubic Regularized Newton Method, Nonconvex Optimization, Adaptability, Complexity Analysis

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

许多机器学习问题，如对抗学习、强化学习的一些典型问题大都归结为极小极大优化问题 [1] [2] 。还有一些著名的数学和优化难题也可看成是某类极小极大问题的特例，例如，著名数学家S. Smale在1998年提出的18个数学公开问题的第7个：球面点散布问题。它可看成是在三维空间单位球面上的一个特殊的非凸极小极大问题。带等式或不等式的约束优化问题，对应的拉格朗日对偶问题也可看成是一类极小极大优化问题。因此，极小极大优化问题最近已经成为最优化领域与机器学习领域中的一个重要研究前沿和热点，吸引了众多学者的关注和研究。如何有效求解极小极大优化问题是优化领域及应用中的关键问题之一。

目前针对凸–凹极小极大优化问题的算法和理论研究已经取得许多较为成熟的研究结果。但是，机器学习中的大多数极小极大优化问题的目标函数都是非凸的，相比于凸–凹极小极大优化问题，非凸极小极大优化问题在理论研究和求解难度上都更具有挑战性。针对非凸极小极大优化问题的算法研究，目前大致包含两类，分别为单循环算法和多循环算法。单循环算法的好处是不需要求解子问题，因其实现起来简单，受到众多学者的关注和研究。其中最简单的是梯度下降–上升算法(GDA)。但是，Takeuchi等人 [3] 在2019年的研究表明：算法GDA即使是对于简单的双线性极小极大优化问题也难以保证算法收敛。Lu等人 [4] 借鉴类似于块上界梯度下降–上升算法的思想，提出混合分块序列近似算法求解非凸–凹极小极大问题，该算法找到一阶平稳点的迭代复杂度为 $\mathcal{O}\left({\epsilon }^{-4}\right)$ 。

另外一大类极小极大优化是多循环算法。Sanjabi等人 [5] 在2018年提出一种基于非凸随机梯度下降算法求解GANs问题，并证得算法找到近似一阶平稳点的迭代复杂度为 $\mathcal{O}\left({\epsilon }^{-2}\right)$ 。Nouiehed等人 [6] 在2019年提出一种多步上升–下降梯度算法，并给出该算法内层循环的迭代复杂度为 $\mathcal{O}\left({\epsilon }^{-1/2}\right)$ ，外层循环的迭代复杂度为 $\mathcal{O}\left({\epsilon }^{-3}\right)$ ，最终算法得到目标函数的一阶纳什均衡点的复杂度为 $\mathcal{O}\left({\epsilon }^{-3.5}\right)$ 。Kong等人 [7] 提出了一种加速非精确临近点光滑化方法求解非凸–凹极小极大优化问题，得到算法的迭代复杂度为 $\mathcal{O}\left({\epsilon }^{-3}\right)$ ，但该方法子问题的求解复杂度没有计算在内。2020年，Lin等人 [8] 提出了一类加速算法求解光滑非凸–凹极小极大优化问题，并得到该算法可以达到 $\mathcal{O}\left({\epsilon }^{-2.5}\right)$ 的迭代复杂度。但是，以上这些算法大都属于一阶优化算法。

Nesterov等人 [9] 在2006年通过引入一个目标函数的三次正则化项的二次近似模型，设计出了一类三次正则化牛顿法来求解无约束非凸优化问题，并得到该算法的全局收敛性和局部二次收敛性。由于三次正则化牛顿法具有良好的鲁棒性，全局收敛性和逃离鞍点的能力，这使得它已经成为求解无约束优化问题的一类重要方法。但是该算法中的三次正则化系数是固定的。于是，Cartis等人 [10] [11] 引入信赖域半径选取的方法，提出一类自适应三次正则化牛顿法，其好处是能自适应调节三次正则化项系数。为求解非凸–强凹极小极大优化问题，Luo等人 [12] 借助于三次正则化牛顿方法思想，设计了一类双循环算法，其中外层循环使用了三次正则化牛顿法(简称为：极小极大三次正则化牛顿法，MCN)，并证得算法达到二阶平稳点时的迭代复杂度为 $\mathcal{O}\left({\epsilon }^{-3/2}\right)$ 。尽管该算法在外层循环使用了三次正则化牛顿法，但是其三次正则化项的系数是相对固定的。

受文献 [10] [11] [12] 工作的启发，本文采用信赖域半径选取的策略，提出一类自适应极小极大三次正则化牛顿法(A-MCN)来求解非凸–强凹极小极大优化问题，并得到了算法的迭代复杂度为 $\mathcal{O}\left(T^{-1/3}\right)$ 。最后，通过数值实验验证了该算法的有效性。相比于文献 [12] 提出的算法MCN，本文提出的算法A-MCN能自适应调节三次正则化项的系数，数值结果表明算法A-MCN优于算法MCN。

本文在第2节中，介绍考虑的问题及其相关假设。在第3节中，给出相应的算法迭代步骤。在第4节中，针对算法进行收敛性分析，并证明算法的收敛速率。在第5节中，给出数值实验结果。最后在第6节中，总结本文的主要研究内容。

2. 极小极大优化问题

考虑如下一类极小极大优化问题：

$\underset{x\in {ℝ}^{d_x}}{\min }\left\{Q\left(x\right)\triangleq \underset{y\in {ℝ}^{d_y}}{\max }f\left(x,y\right)\right\}$ ， (1)

其中 $f\left(x,y\right)$ 是一个二次连续可微函数，且对任意固定的y关于x是非凸的，对任意固定的x关于y是 $\mu$ -强凹的。

下面给出关于问题(1)的一些假设。

假设1 a) 对任意给定的 $y\in {ℝ}^{d_y}$ ，函数 $f\left(x,y\right)$ 的梯度 $\nabla f\left(x,y\right)$ 关于x是l-Lipschitz连续的，即存在一个常数 $l>0$ ，使得对于 $\forall x,x^{\prime }\in {ℝ}^{d_x}$ ，有 $\Vert \nabla f\left(x,y\right)-\nabla f\left(x^{\prime },y\right)\Vert \le l\Vert x-x^{\prime }\Vert$ 。

b) 对任意给定的 $y\in {ℝ}^{d_y}$ ，函数 $f\left(x,y\right)$ 关于x是二次可微的。并且关于x的Hessian矩阵 ${\nabla }_{xx}^{2}f\left(x,y\right)$ 是 $L_H$ -Lipschitz连续的，即对 $\forall x,x^{\prime }\in {ℝ}^{d_x}$ ，存在一个常数 $L_H>0$ ，有

$\Vert {\nabla }_{xx}^{2}f\left(x,y\right)-{\nabla }_{xx}^{2}f\left(x^{\prime },y\right)\Vert \le L_H\Vert x-x^{\prime }\Vert .$

c) 对任意给定的 $x\in {ℝ}^{d_x}$ ， $f\left(x,y\right)$ 关于y是 $\mu$ -强凹的，即对 $\forall y,y^{\prime }\in {ℝ}^{d_y}$ ，存在一个常数 $\mu >0$ ，有

$f\left(x,y\right)\le f\left(x,y^{\prime }\right)+{\nabla }_{y}f{\left(x,y\right)}^{\top }\left(y-y^{\prime }\right)-\frac{\mu }{2}{\Vert y-y^{\prime }\Vert }^2.$

假设2：函数 $Q\left(x\right)\triangleq \underset{y\in {ℝ}^{d_y}}{\max }f\left(x,y\right)$ 有下界，即 $Q^{*}=\underset{x\in {ℝ}^{d_x}}{\inf }Q\left(x\right)>-\infty$ 。

下面的两个引理给出了 $Q\left(x\right)$ 的一些性质。

引理1 [13] 若f满足假设1中的a)和c)，那么有：a) $Q\left(x\right)$ 的梯度 $\nabla Q\left(x\right)={\nabla }_{x}f\left(x,y^{*}\left(x\right)\right)$ 是 $\left(\zeta +1\right)l$ -Lipschitz连续的，这里 $\zeta =l/\mu$ ；b) $y^{*}\left(x\right)=\underset{y\in {ℝ}^{d_y}}{\arg \max }f\left(x,y\right)$ 是唯一，且是 $\zeta$ -Lipschitz连续的。

引理2 [12] 若f满足假设1，那么有：a) $Q\left(x\right)$ 在点 $y^{*}\left(x\right)$ 处有

${\nabla }^{2}Q\left(x\right)={\nabla }_{xx}^{2}f\left(x,y\right)-{\nabla }_{xy}^{2}f\left(x,y\right){\left[{\nabla }_{yy}^{2}f\left(x,y\right)\right]}^{-1}{\nabla }_{yx}^{2}f\left(x,y\right),$

b) ${\nabla }^{2}Q\left(x\right)$ 是 $\omega$ -Lipschitz连续的，其中 $\omega =4\sqrt{2}{\zeta }^3{L}_H$ ，即 $\forall x,x^{\prime }\in {ℝ}^{d_x}$ ，有

$\Vert {\nabla }^{2}Q\left(x\right)-{\nabla }^{2}Q\left(x^{\prime }\right)\Vert \le \omega \Vert x-x^{\prime }\Vert .$

3. 自适应极小极大三次正则化牛顿法

为求解一类非凸–强凹极小极大优化问题，基于Luo等人 [12] 提出的极小极大三次正则化牛顿法(MCN)框架，为调节该算法中固定的三次正则化项的系数，借助Cartis等人 [10] [11] 提出的算法中信赖域半径的选取策略，本文设计了一类自适应极小极大三次正则化牛顿法(A-MCN)求解问题(1)，其中针对外层循环设计了一种自适应的三次正则化牛顿法，针对内层子问题设计了一种加速梯度算法。下面给出具体算法框架：

算法1. Adaptive Min-Max Cubic Regularized Newton Method (A-MCN)

算法2. $y_t=\text{AGD}\left(x_{t-1},y_{t-1},K_t,\alpha ,\beta \right)$ (Accelerated Gradient Descent Algorithm, AGD)

注记：1) 算法A-MCN是先固定变量 $x_{t-1}$ ，利用算法AGD更新 $y_t$ ，然后固定 $y=y_t$ 利用信赖域的概念来判断每次迭代所得的牛顿更新步骤是否成功，只有当更新步骤成功时，才会使用得到的牛顿更新步骤替代上一次的迭代，以此更新 $x_t$ ，同时在更新判断的过程中，算法的三次正则化项的系数 ${\sigma }_t$ 是可以自适应调节的。

2) 对比算法MCN [12] ，本文借助信赖域半径的选取策略，通过信赖域半径作为判断准则，判断牛顿更新步是否成功，并在判断过程中调节三次正则化项的系数。与文献 [12] 中算法MCN相比，本文提出的自适应三次正则化牛顿法，可以自适应的调节三次正则化项的系数。

4. 收敛性分析

下面为证明全局收敛性，介绍如下两个引理。

引理3 [10] [11] 对所给的初始迭代点 $x_0$ ，存在的一个闭凸集 $\mathcal{F}$ ，使得水平集 $\mathcal{L}\left(x_0\right):=\left\{x:Q\left(x\right)\le Q\left(x_0\right)\right\}\subseteq \mathcal{F}$ ，对 $\forall x,x^{\prime }\in \mathcal{F}$ ， $\exists {\kappa }_H\ge 0$ ，有 $\Vert {\nabla }^{2}Q\left(x\right)\Vert \le {\kappa }_H$ 。

引理4 [9] [10] 如果 $d_{t-1}\in \underset{d}{\arg \min }\left\{m_{t-1}\left(d\right):=Q\left(x_{t-1}\right)+g_t^{\top }d+\frac{1}{2}{d}^{\top }{H}_{t}d+\frac{{\sigma }_{t-1}}{6}{\Vert d\Vert }^3\right\}$ ，则有

$Q\left(x_{t-1}\right)-m_{t-1}\left(d_{t-1}\right)\ge \frac{1}{12}{\sigma }_{t-1}{\Vert d_{t-1}\Vert }^3.$ (2)

此外，设 $\mathcal{S}:=\left\{t:{\rho }_t>{\eta }_1\right\}$ 表成功更新的索引集合，则对任意 $t\in \mathcal{S}$ ，有

$Q\left(x_{t-1}\right)-Q\left(x_t\right)\ge {\eta }_1\left(Q\left(x_{t-1}\right)-m_t\left(s_{t-1}\right)\right))\ge \frac{{\eta }_1}{12}{\sigma }_{t-1}{\Vert d_{t-1}\Vert }^3.$ (3)

下面给出自适应惩罚参数 ${\sigma }_t$ 的一个上界。

引理5 在假设1和2下，自适应惩罚参数 ${\sigma }_t$ 不能任意大，即

${\sigma }_t\le \max \left\{\omega {\gamma }_1,{\sigma }_{\min }\right\}={\sigma }_{\max }.$ (4)

证明：令：

$r_t=Q\left(x_t+d_t\right)-m_t\left(d_t\right)+\left(1-{\eta }_2\right)\left(m_t\left(d_t\right)-Q\left(x_t\right)\right),$

若 $x_t$ 不是局部最小解，由文献 [10] [11] 知

$m_t\left(d_t\right)<Q\left(x_t\right),$

再由引理1有

$\left|Q\left(x\right)-Q\left(x^{\prime }\right)-\nabla Q\left(x^{\prime }\right)\left(x-x^{\prime }\right)-\frac{1}{2}{\left(x-x^{\prime }\right)}^{\top }{\nabla }^{2}Q\left(x\right)\left(x-x^{\prime }\right)\right|\le \frac{\omega }{6}{\Vert x-x^{\prime }\Vert }^3,$ (5)

若 ${\sigma }_t\ge \omega$ 时，由式(5)可得

$Q\left(x_t+d_t\right)-m_t\left(d_t\right)\le \left(\frac{\omega }{6}-\frac{{\sigma }_t}{6}\right){\Vert d_t\Vert }^3\le 0$

此时 $r_t<0$ ，等价于

${\rho }_t>{\eta }_2,$

意味着此时迭代非常成功，迭代点 $t\in \mathcal{S}$ .

若 $t-1\notin \mathcal{S}$ ，则有

${\sigma }_{t\text{-}1}<\omega ,$

那么

$\omega \le {\sigma }_t={\gamma }_1{\sigma }_{t-1}\le {\gamma }_1\omega ,t\in \mathcal{S},$

故

${\sigma }_t\le \max \left\{{\gamma }_1\omega ,{\sigma }_{\min }\right\}={\sigma }_{\max }.$ 证毕

下面给出不成功更新集合的一个上界和成功更新总集合的一个下界。

引理6 记 ${\mathcal{S}}_j:=\left\{t<j:{\rho }_t>{\eta }_1\right\}$ ， ${\mathcal{U}}_j:=\left\{t<j:{\rho }_t\le {\eta }_1\right\}$ ，有

$\left|{\mathcal{U}}_j\right|\le \lceil \log \frac{\max \left\{{\gamma }_1\omega ,{\sigma }_{\min }\right\}}{{\sigma }_{\min }}\rceil \left|{\mathcal{S}}_j\right|,$ (6)

和

$\left|{\mathcal{S}}_T\right|\ge \frac{T}{1+\lceil \log \frac{\max \left\{{\gamma }_1\omega ,{\sigma }_{\min }\right\}}{{\sigma }_{\min }}\rceil }.$ (7)

证明：根据引理5，若当前迭代是成功的，则距下一次成功迭代，最多需要

$\lceil \log \frac{{\sigma }_{\max }}{{\sigma }_{\min }}\rceil$

步不成功迭代，那么式(6)成立。

下证式(7)成立，由式(6)以及

$\left|{\mathcal{S}}_T\right|+\left|{\mathcal{U}}_T\right|=T,$

即证得式(7)成立。证毕

在这里给出收敛性证明。

引理7 对于所有给出的 $d_t$ 以及 ${\mathcal{S}}_T$ ，有以下关系成立

$\underset{t\in {\mathcal{S}}_T}{\max }\Vert d_t\Vert \le {\left(\frac{12\left(Q\left(x_0\right)-Q^{*}\right)}{{\eta }_1{\sigma }_{\min }}\right)}^{\frac{1}{3}},$ (8)

$\underset{t\in {\mathcal{S}}_T}{\min }\Vert d_t\Vert \le {\left(\frac{12\left(Q\left(x_0\right)-Q^{*}\right)}{\left|{\mathcal{S}}_T\right|{\eta }_1{\sigma }_{min}}\right)}^{\frac{1}{3}}.$ (9)

证明：由引理4，有

$\begin{array}{c}{\displaystyle \underset{t\in {\mathcal{S}}_T}{\sum }\frac{1}{12}{\eta }_1{\sigma }_{t-1}{\Vert d_{t-1}\Vert }^3}\le {\displaystyle \underset{t\in {\mathcal{S}}_T}{\sum }Q}\left(x_{t-1}\right)-Q\left(x_t\right)\\ ={\displaystyle \underset{t=1}{\overset{T}{\sum }}\left(Q\left(x_{t-1}\right)-Q\left(x_t\right)\right)}\\ \le Q\left(x_0-Q^{*}\right),\end{array}$ (10)

其中等式成立是因为对任意的 $t\notin {\mathcal{S}}_T$ ，有

$Q\left(x_t\right)=Q\left(x_{t-1}\right),$

因此

${\displaystyle \underset{t\in {\mathcal{S}}_T}{\sum }{\Vert d_t\Vert }^3}\le \frac{12\left(Q\left(x_0\right)-Q^{*}\right)}{{\eta }_1{\sigma }_{\min }},{\sigma }_{t-1}>{\sigma }_{\min }.$

最后式(10)结合

$\underset{t\in {\mathcal{S}}_T}{\max }{\Vert d_t\Vert }^3\le \underset{t\in {\mathcal{S}}_T}{\sum }{\Vert d_t\Vert }^3,$

得到式(8)，由

$\underset{t\in {\mathcal{S}}_T}{\min }{\Vert d_t\Vert }^3\le \frac{1}{\left|{\mathcal{S}}_T\right|}{\displaystyle \underset{t\in {\mathcal{S}}_T}{\sum }{\Vert d_t\Vert }^3},$

得到式(9)。证毕

为证明该算法求解问题(1)的收敛速率，给出如下引理。

引理8 [9] 假设1和2成立，序列 $\left\{\left(x_t,y_t\right)\right\}$ 由算法1产生，则有

$\Vert \nabla Q\left(x_t\right)\Vert \le \frac{1}{2}\left({\sigma }_t+\omega \right){\Vert d_t\Vert }^2,$

以及

${\lambda }_{\min }\left({\nabla }^{2}Q\left(x_t\right)\right)\ge -\left(\frac{1}{2}{\sigma }_t+\omega \right)\Vert d_t\Vert .$

定义1 下面定义如下局部优化度量

$\tau \left(x\right)=\max \left\{\sqrt{\frac{2}{{\sigma }_t+\omega }\Vert \nabla Q\left(x_t\right)\Vert },-\frac{1}{\frac{1}{2}{\sigma }_t+\omega }{\lambda }_{\min }\left({\nabla }^{2}Q\left(x_t\right)\right)\right\}.$

定理1 若假设1成立，序列 $\left\{\left(x_t,y_t\right)\right\}$ 由算法1产生，则对任意给定的 $T\; \ge 1$ ，有

$\underset{1\le t\le T}{\min }\tau \left(x_{t-1}\right)\le {\left(\frac{12\left(Q\left(x_0\right)-Q^{*}\right)}{{\eta }_1{\sigma }_{\min }T}\left(1+\lceil \log \frac{\max \left\{{\gamma }_1\omega ,{\sigma }_{\min }\right\}}{{\sigma }_{\min }}\rceil \right)\right)}^{\frac{1}{3}}.$

证明：由引理8可得 $\forall t\in {\mathcal{S}}_T$ ，有

$\tau \left(x_t\right)\le \Vert d_t\Vert ,$

则有

$\underset{1\le t\le T}{\min }\tau \left(x_{t-1}\right)\le \underset{t\in {\mathcal{S}}_T}{\min }\Vert d_t\Vert .$

结合式(9)和(7)，有

$\begin{array}{c}\underset{1\le t\le T}{\min }\tau \left(x_{t-1}\right)\le \underset{t\in {\mathcal{S}}_T}{\min }\Vert d_t\Vert \\ \le {\left(\frac{12\left(Q\left(x_0\right)-Q^{*}\right)}{\left|{\mathcal{S}}_T\right|{\eta }_1{\sigma }_{min}}\right)}^{\frac{1}{3}}\\ \le {\left(\frac{12\left(Q\left(x_0\right)-Q^{*}\right)}{T{\eta }_1{\sigma }_{\min }}\left(1+\lceil \log \frac{\max \left\{{\gamma }_1\omega ,{\sigma }_{\min }\right\}}{{\sigma }_{\min }}\rceil \right)\right)}^{\frac{1}{3}}\\ =\mathcal{O}\left(T^{-1/3}\right).\end{array}$

证毕

5. 数值实验

下面通过一个对抗神经网络模型(DANN) [14] 来测试本文提出的算法A-MCN的数值表现。

DANN是一种经典的迁移学习方法，假设源域数据集 $\mathcal{S}=\left\{\left(a_i^{\mathcal{S}},b_i^{\mathcal{S}}\right)\right\}$ ，其中 $a_i^{\mathcal{S}}$ 是第i次采样的特征向量， $b_i^{\mathcal{S}}$ 是对应的标签。目标域数据集是 $\mathcal{T}={\left\{a_i^{\mathcal{T}}\right\}}_{i=1}^{N_{\mathcal{T}}}$ ，该数据集只包含特征向量。实验环境为笔记本电脑AMD Ryzen 5 4600U处理器，16GB RAM，所有算法均使用Python3.8.3 (TensorFlow框架)编码实现。

考虑DANN中具有如下形式的一类非凸–强凹极小极大优化问题 [14] ：

$\underset{\left[x_1;x_2\right]\in {ℝ}^{d_x}}{\min }\underset{y\in {ℝ}^{d_y}}{\max }{L}_1\left(x_1,x_2\right)-q\cdot L_2\left(x_1,y\right),$

其中

$L_1\left(x_1,x_2\right)=\frac{1}{N_{\mathcal{S}}}{\displaystyle \underset{i=1}{\overset{N_{\mathcal{S}}}{\sum }}\theta }\left(x_2;\Phi \left(x_1;a_i^{\mathcal{S}}\right),b_i^{\mathcal{S}}\right),$

是监督学习损失总和，且有分类损失总和：

$L_2\left(x_1,y\right)=\frac{1}{N_{\mathcal{S}}}{\displaystyle \underset{i=1}{\overset{N_{\mathcal{S}}}{\sum }}{D}_{\mathcal{S}}}\left(h\left(y;\Phi \left(x_1;a_i^{\mathcal{S}}\right)\right)\right)-\frac{1}{N_{\mathcal{T}}}{\displaystyle \underset{i=1}{\overset{N_{\mathcal{T}}}{\sum }}{D}_{\mathcal{T}}}\left(h\left(y;\Phi \left(x_1;a_i^{\mathcal{T}}\right)\right)\right)+\lambda {\Vert y\Vert }^2,$

其中

$\left(y;z\right)=1/\left(1+\exp \left(-y^{\top }z\right)\right),$

$D_{\mathcal{S}}\left(z\right)=1-\log \left(z\right),$

以及

$D_{\mathcal{T}}\left(z\right)=\log \left(1-z\right)$

作为 $L_2$ 的常用逻辑损失函数。这里 $\Phi$ 是一个以 $x_1$ 为参数，大小为(28 × 28) × 200的单层神经网络； $\theta$ 是一个以 $x_2$ 为参数，大小为200 × 20 × 10的三层神经网络。神经网络中选择sigmoid函数作为激活函数，并选择 $q=1,\lambda =0.2$ 作为模型参数，算法GDA和算法A-MCN中AGD步的学习速率设为 $\left\{c\cdot {10}^{-i}:c\in \left\{1,5\right\},i\in \left\{1,2,3,4,5\right\}\right\}$ ，由于在实验前无法获取 $Q\left(x\right)$ 的显示解，因此在实验中使用AGD算法预估了 $Q\left(x\right)=\underset{y}{\max }f\left(x,y\right)$ 的值。

实验中用到的数据集为MNIST [15] 和MNIST-M数据集 [14] 。MNIST数据集包含60,000个用于训练的示例和10000个用于测试的示例，其中包含的手写数字图像已经过尺寸标准化且位于图像中心，图像是固定大小(28 × 28像素)，其值为0到1。并且每个图像都被平展并转换为784 (28 × 28)个特征的一维numpy数组。MNIST-M数据集是由MNIST中的数字图像与BSDS500数据集中的随机色块混合而成。

5.1. 参数对算法的影响分析

超参数的调节是影响机器学习算法数值效果的重要因素，合适的超参数设置往往能够提升算法对数据的表达效果，然而参数的调节是很困难的。在工程实践中，通常利用数值实验的方式确定算法最佳超参数。考虑到算法A-MCN中参数 ${\eta }_1,{\eta }_2$ 以及求解三次正则化牛顿法子问题的Lanczos方法终止步条件对算法A-MCN的收敛性影响较大，这里的 ${\eta }_1,{\eta }_2$ 为算法中检验牛顿迭代步是否成功的判断标准，且 $1>{\eta }_2>{\eta }_1>0$ ，Lanczos方法在每次迭代中的终止步为记为 $Lanmax$ 。

本节数值实验目的是，分析算法A-MCN中的几个参数选取对算法性能的影响。在实验中选择精度 $\epsilon =1\text{e}-4$ 。固定 ${\eta }_2=0.8$ ， $Lanmax$ 设为5，分析参数 ${\eta }_1$ 对算法A-MCN性能的影响。如表1所示。可以看到在最终迭代步时，算法A-MCN选取参数 ${\eta }_1=0.1$ 的损失函数值均低于其他情形下的损失函数值，且 ${\eta }_1$ 选取在0.2~0.5之间对算法的性能影响不大。因此算法A-MCN选取参数 ${\eta }_1$ 的最优值为0.1。

表1. 参数 ${\eta }_1$ 对算法A-MCN性能影响分析

接着固定上轮得到的最优参数 ${\eta }_1=0.1$ ， $Lanmax$ 设为5，分析参数 ${\eta }_2$ 对算法A-MCN性能的影响。如表2所示。可以看到在在最终迭代步时，算法A-MCN选取参数 ${\eta }_2=0.8$ 的损失函数值均低于其他情形下的损失函数值，且 ${\eta }_2$ 选取在0.5~0.7之间对算法的性能影响不大。因此算法A-MCN选取参数 ${\eta }_2$ 的最优值为0.8。

表2. 参数 ${\eta }_2$ 对算法A-MCN性能影响分析

最后固定选取的最优参数 ${\eta }_1=0.1,{\eta }_2=0.8$ ，分析参数 $Lanmax$ 对算法A-MCN性能的影响，如表3所示，可以看到在最终迭代步时，算法A-MCN选取参数 $Lanmax=5$ 的损失函数值均低于其他情形下的损失函数值，因此在固定最优参数 ${\eta }_1=0.1,{\eta }_2=0.8$ 下，参数 $Lanmax$ 最优选取为5。在通过本节数值实验之后，本文选取的最佳参数为： ${\eta }_1=0.1,{\eta }_2=0.8,Lanmax=5$ 。

表3. 参数 $Lanmax$ 对算法A-MCN性能影响分析

5.2. 正文算法对比实验

本节对比算法A-MCN、随机梯度上升下降算法(SGDA) [16] 和极小极大随机三次正则化牛顿法(MSCR) [12] 在两个不同的数据集：MNIST和MNIST-M之间的自适应学习问题，由前文参数对算法A-MCN性能影响实验可知，算法A-MCN中参数 ${\eta }_1=0.1,{\eta }_2=0.8,Lanmax=5$ 。并将算法A-MCN、算法SGDA和算法MSCR计算得到的损失函数值与迭代次数进行对比，数值结果如图1和图2所示。图1为数据集MNIST到数据集MNIST-M的自适应学习结果，图2为数据集MNIST-M到数据集MNIST的自适应学习结果，在两次实验中均通过迭代次数来比较算法A-MCN和算法SGDA、算法MSCR的性能。无论是图1还是图2均可以看到，在达到相同计算精度时，算法A-MCN在预测比较中显著优于算法SGDA和算法MSCR。

图1. MNIST到MNIST-M的自适应学习结果

图2. MNIST-M到MNIST的自适应学习结果

6. 总结及展望

首先对本文的工作进行总结，然后对未来的进一步工作进行展望。

6.1. 总结

针对非凸–强凹极小极大优化问题，采用信赖域半径的选取策略，首先提出了一类自适应极小极大三次正则化牛顿法(A-MCN)，其中针对外层循环设计了一种自适应的三次正则化牛顿法，针对内层子问题设计了一种加速梯度算法。

然后，得到了算法的迭代复杂度为 $\mathcal{O}\left(T^{-1/3}\right)$ 。最后，通过DANN中的一类对抗攻击神经网络问题验证了该算法的有效性。相比于文献 [12] 提出的算法MCN，本文提出的算法A-MCN能自适应调节三次正则化项的系数。

6.2. 展望

可行的未来研究工作主要有以下几个方面。

1) 在极小极大优化问题的算法设计中，提高算法的收敛速度是非常必要的。受文献 [17] 工作的启发，本文下一步研究的工作是借鉴文献 [17] 中的动量加速机制，来加速本文提出的自适应极小极大三次正则化牛顿法，并建立算法的收敛性理论。

2) 本文主要研究了针对非凸–凹极小极大优化问题的两类算法和理论，但针对非凸–非凹极小极大优化问题的相关算法和理论研究还有待进一步研究 [18] 。

文章引用

高瑞成. 极小极大优化问题的一类自适应三次正则化牛顿法
One Class of Cubic Regularized Newton Methods for Min-Max Optimization Problems[J]. 理论数学, 2023, 13(05): 1255-1266. https://doi.org/10.12677/PM.2023.135129

参考文献