基于动态约束自适应方法抵御高维鞍点攻击

李德权 许 月 薛 生

1(安徽理工大学数学与大数据学院 安徽淮南 232001) 2(安徽理工大学能源与安全学院 安徽淮南 232001)dqli@aust.edu.cn)

随着传感器和智能设备技术的快速发展以及在实际中的广泛运用，协同收集来自多个信息源的大量数据成为现实.面对具有空间分布的海量数据的处理，作为能够从中提取有价值信息的主要有效工具，机器学习在计算机视觉、医疗保健和金融市场分析等广泛领域的应用取得了巨大成功.其中分布式随机梯度下降算法(stochastic gradient descent， SGD)作为最常用的机器学习方法之一，在每步迭代中只随机训练一个样本数据，大大减少了训练时间，但容易受到Byzantine攻击[1]的影响.由于系统故障、软件bug[2]、数据损坏和通信延迟等原因造成的个体或机器之间共享信息错误[3]，统称为Byzantine攻击.所以，在Byzantine环境下研究分布式机器学习如何高效处理共享信息的数据是极为重要的.

Byzantine弹性指的是存在Byzantine攻击的情况下算法仍能正常执行的弹性区间[5].文献[6]分析了经典Byzantine与高维Byzantine的区别与联系，如图1所示.文献[6]也将Byzantine攻击类型分成了3种：高斯攻击、全知型攻击和位翻转型攻击.但仅仅用了SGD去解决上述3种类型的Byzantine攻击的优化问题.

Fig. 1 Two types of Byzantine图1 Byzantine的2种不同方式

文献[7]提出用自适应方法代替传统的SGD来有效解决陷入鞍点而无法达到最优值的困境.通过调整随机梯度噪声的方向，使得噪声能在鞍点处是等方向的，有助于朝正确的方向快速逃离鞍点.但自适应方法则面临两大问题：1)与SGD相比泛化能力差；2)由于不稳定或者极端的学习率会导致算法不收敛.文献[8]不仅验证了极端学习率会导致算法性能差，而且提出了给学习率加上动态约束实现从自适应方法到SGD平缓过渡的方法——具有动态约束的自适应矩估计(adaptive moment estimation with dynamic bound， ADABOUND).结果表明这2种动态约束自适应方法消除了自适应方法和SGD的泛化差异，并且提高了学习速度.

为了解决在分布式高维Byzantine环境下，能最大弹性限度抵御攻击问题，从而高效求解优化问题.仿真分析了当目标函数陷入鞍点时，动态约束自适应相比较于自适应和非自适应方法逃离鞍点要更快，并在数据集分类问题上同样进行了比对实验.其次，提出了一种过滤Byzantine个体的聚合规则Saddle(·)，理论证明了它是高维Byzantine弹性的.因此，在分布式高维Byzantine环境下，采用动态约束的自适应优化方法结合聚合规则Saddle(·)能够有效避免鞍点攻击.

1 预备知识

判断鞍点的一个充分条件是：函数在一阶导数为0处的Hessian矩阵为不定矩阵.

定义3.严格鞍函数.对于所有的x，满足下列条件：

3) 点x位于局部极小值附近;

则函数f(x)是严格鞍函数[11-12].

2) 对于指数r=2,3,…,r1+r2+…+rn-q=r，E[Aggr]r≤c1E[G]r1+c2E[G]r2+…+cn-qE[G]rn-q，其中c1,c2,…,cn-q为线性组合的相关系数.

聚合规则Aggr(·)指的是满足规则Aggr(·)的被认为是非Byzantine个体共享的真实信息，相反则被认为是Byzantine个体共享的虚假信息，需要被过滤掉.

Reddi等人[13]提出深度学习[14]优化方法的一般框架(包括自适应和非自适应方法)：

②m|t=φt((g1,g2,…,gn)t)和v|t=Φt((g1,g2,…,gn)t);

其中，g|t为f(x|t)梯度，α为深度学习步长，t为迭代时间，x|t为第t步迭代的解(x1,x2,…,xn)t，β1和β2分别对应一阶梯度和二阶梯度移动平均的指数，φt和Φt在自适应和非自适应中分别对应如表1所示的值.

Table 1 Adaptive and Non-adaptive Corresponding Values表1 自适应和非自适应对应值

2 优化方法与模型建立

2.1 动态约束自适应方法

通过上述分析，自适应方法易受极端学习率影响.为有效克服这一困难，动态约束自适应的算法思想是[8]：通过给梯度加一个阈值区间，并且上下阈值都随时间变化最后收敛到SGD的学习率，从而实现自适应方法向SGD的平缓过渡.

2.2 鞍点攻击与聚合规则Saddle(·)

定义5.鞍点攻击类型为

其中，(gi)j表示第j维第i个个体的梯度值，j∈[d].i∈B时，同时满足Hessian矩阵是不定的.鞍点攻击影响梯度，从而影响学习率，导致目标函数不收敛,所以需要寻求一种聚合规则过滤Byzantine个体.下面提出的聚合规则[15]可以过滤高维鞍点个体，实现抵御攻击的目的.

定义6.聚合规则Saddle(·)为

定理1.噪声梯度下降法能够在多项式时间内找到严格鞍函数的局部最小值点[10].

定理1验证了聚合规则Saddle(·)是能在有限时间内找到函数最优值，即逃离了鞍点.为了验证聚合规则Saddle(·)更具有一般性，下面证明它是高维Byzantine弹性的.

3 聚合规则Saddle(·)

证明.

根据Jensen不等式,

以上验证了聚合规则Saddle(·)满足高维Byzantine弹性的条件1).

根据等价范数的定义：有限维空间上的任何2个范数必是等价的.存在常数c1，使得

其中，r1+r2+…+rm-q=r.所以验证了聚合规则Saddle(·)满足高维Byzantine弹性的条件2).

以上证明了聚合规则Saddle(·)是更具有一般性的高维Byzantine弹性，即过滤鞍点的聚合规则是泛化的.

证毕.

4 实验结果

4.1 动态约束自适应方法与其他优化算法的比较

以凸函数：

为例，其中b1，b2为随机系数.由鞍点判定条件知，函数ft(x1,x2)的Hessian矩阵是不定的，所以该函数存在鞍点.通过不断对(x1,x2)进行梯度更新，最终找到目标函数的最优值.因为不同的优化方法对梯度更改规则不同(即学习率不同)，所以达到目标函数最优值的快慢不同.

如图2(a)所示，动态约束自适应(ADABOUND)方法相比较于自适应梯度算法(adaptive gradient， ADAGRAD)、平方根改进算法(root mean square prop， RMSPROP)、ADAM和SGD逃离鞍点的速度明显比较快.图2(b)表示动态约束自适应的上下阈值随时间变化，最后都收敛到与SGD学习率一致，实现了自适应到非自适应的平缓过渡.

Fig. 2 Comparison of the optimization methods used to escape from saddle point图2 优化方法用于逃离鞍点的快慢比较

不仅如此，在随机生成的(50 000×30)数据集中，分别用不同的优化方法将该数据集分成10个类.逻辑回归用以解决该分类问题，对于输入的x|t，其对应的类标签为y|t，我们的目标是训练分类模型y|t=wx|t+b的参数w和b，使得属于当前类的概率最大.下面实验通过比较错误率(error rate)与误差(error)来分析方法的优劣.

Fig. 3 Performance comparison of data set classification by different optimization methods图3 不同优化方法分类的性能比较

4.2 Byzantine环境下的动态约束自适应

根据2.2节提出的鞍点攻击，该攻击方式会影响梯度，所以对于基于梯度的优化方法就会有一定程度的影响.为了证明动态约束自适应能控制极端梯度的影响，在Byzantine和非Byzantine环境下做了动态约束自适应受环境影响程度的对比实验.并且与文献[6]作比对实验，观察SGD受Byzantine攻击的影响大小.

Fig. 4 Performance comparison of optimization methods in Byzantine and non-Byzantine environments图4 Byzantine和非Byzantine环境下的性能比较

如图4(a)(b)，动态约束自适应方法相比较于SGD在Byzantine环境下不会受很大的影响.因为经过梯度裁剪的自适应，不会因为梯度的忽大忽小而导致不收敛.图4(c)表示从误差角度分析，在Byzantine和非Byzantine环境下动态约束自适应受影响的情况.

4.3 分布式高维Byzantine环境下的动态约束自适应

第3节已经验证了聚合规则Saddle(·)具有高维Byzantine弹性，所以在分布式环境下鞍点攻击的是任意维的个体.不同个体对应不同的工作机器，分布式计算模型参数，然后它们向主机发送局部模型参数[16].所以在分布式环境下研究鞍点攻击，通过观察不同个体总数目的错误率.

如图5所示，不同个体总数目下动态约束自适应方法的分类效果不一样[17].由于高维Byzantine在每一维的随机性较大，所以这也是影响图5结果的直接原因.

5 总结与展望

结合文献[8]提出的动态约束自适应并应用于分布式Byzantine环境，本文主要提出一种具有高维Byzantine弹性的聚合规则Saddle(·)，可有效过滤鞍点攻击的个体，从而实现在确保算法收敛的情况下抵御鞍点攻击的目的.针对数据集分类结果的错误率和误差2个重要指标，通过大量数值仿真比较分析动态约束自适应与自适应和非自适应方法的优劣性.结果表明：结合聚合规则Saddle(·)的动态约束自适应在分布式Byzantine环境下受鞍点攻击的影响较小.

下一步工作希望能够给出不同个体总数所对应不同错误率大小的理论解释，并且能够更大限度地降低错误率.